Adapton in Rust
A general-purpose Incremental Computation (IC) library for Rust.
available on crates.io
Based on:
- The paper Incremental Computation with Names, OOPSLA 2015.
- A prior OCaml implementation.
Library Components:
-
The library exposes a small core interface.
See theAdapton
trait. -
The library uses rust macros to provide syntactic sugar.
Seemacros.rs
. -
The library implements this interface with an imperative data structure, and without garbage collection.
Seeengine.rs
. -
The library provides generic incremental data structures and algorithms.
See also:collection_traits.rs
: Generic trees and lists.
And:collection_algo.rs
: Simple algorithms over generic trees and lists. -
The library provides interfaces to script interactions using generic DSLs for editing and querying
See also:collection_edit.rs
: -
Next:
- tries that represent sets, maps,
- generic fixed-point loop
- graphs, graph exploration algorithms (e.g., search)
Supported Incremental Computation Paradigms:
-
Pure Function Caching:
Incremental computation via function caching
Bill Pugh and Tim Teitelbaum.
POPL 1989.- hash-cons'd, purely-functional data structures
- memoized function calls (to pure computations)
-
Structural Adapton:
Adapton: Composable, Demand-Driven Incremental Computation.
Matthew A. Hammer, Yit Phang Khoo, Michael Hicks and Jeffrey S. Foster.
PLDI 2014.- changeable input cells
- bidirectional DCG structure
- dirtying traversal; repair traversal.
-
Nominal Adapton:
Incremental Computation with Names
Matthew A. Hammer, Joshua Dunfield, Kyle Headley, Nicholas Labich, Jeffrey S. Foster, Michael Hicks, David Van Horn.
OOPSLA 2015.- first-class names
- nominal memoization
Future work
- Benchmarking based on tests:
- report time statistics
- report memory statistics
Technical Debt
Rust-Specific:
- In
engine.rs
I wroteProducer::copy
and theShapeShifter
trait. Both avoid returning aSelf
.
Is there a better way?
See also: 0255-object-safety - Do I need really need
Rc<Box<Fn (_) -> _>>
instead ofRc<Fn (_) -> _>
?
Why? - Done: