Documentation

Adapton in Rust

A general-purpose Incremental Computation (IC) library for Rust.

Based on:

Development Activities

  • Building Adapton in Rust around core interface, the Adapton trait.

  • The library implements this interface with an imperative data structure, AdaptonState.

  • I am learning Rust in the process. See detailed Q&A below.

Testing:

  • Lazy Evaluation (simple, pure caching).

  • Function Caching:

    • Implements Bill Pugh's notion of IC, pure function caching.
  • Structural Adapton:

    • changeable input cells
    • bidirectional DCG structure
    • dirtying traversal; repair traversal.
  • Nominal Adapton:

    • first-class names
    • nominal memoization
  • Incremental Data Structures and Algorithms.

    • generic list and tree traits
    • balanced trees from lists ("unfold")
    • tree folds (left-to-right, right-to-left, bottom-up)
    • mergesort

Future work

Data Structures and Algorithms

  • tries that represent sets, maps,
  • generic fixed-point loop
  • graphs, graph exploration algorithms (e.g., search)

Technical Debt

Pending issues:

  • Canonical balanced trees for sequences: Where should data go? Only at leaves (B-Tree style)?
  • List/Tree intro forms should take unboxed, references, or boxes? error: type annotations required: cannot resolve <_ as structures::ListT<A, _>>::List == _ [E0284]
  • Implement ArtId::Structural for cell and thunk to do hashing internally, not externally.

Rust Q&A

src/adapton_impl.rs:653:51: 653:111 error: cannot convert to a trait object because trait `adapton_impl::Producer` is not object-safe [E0038]
...
src/adapton_impl.rs:653:51: 653:111 note: method `eq` references the `Self` type in its arguments or return type

I sidestepped this problem in adapton_state.rs twice: by writing Producer::copy and the ShapeShifter trait. Both avoid returning a Self.

  • Do I need really need Rc<Box<Fn (_) -> _>> instead of Rc<Fn (_) -> _>? (Why?)