Sign in

    incr

    Adapton-style demand-driven incremental computation in MoonBit

    Download zip
    Author
    Version
    0.1.0
    License
    MPL-2.0
    Last updated
    19 hours ago
    Downloads
    2

    #incr.mbt

    A MoonBit port of Adapton's demand-driven incremental computation model. It provides mutable inputs, lazy cached computations, dynamic dependencies, nominal and structural memoization, projection reads, and incremental collections. There are no external dependencies.

    The port is based on the local Rust Adapton 0.3.31 reference in .repos/adapton. The API is adapted to MoonBit; see PORTING.md for coverage and differences.

    #Install

    moon add bobzhang/incr

    Import "bobzhang/incr" in your package's moon.pkg to use @incr.

    #Interactive example: delivery dispatch

    Dispatch is a city dashboard with 600 delivery quotes powered by this library. Close a bridge, change fuel prices, or take a depot offline, and watch exactly which computations rerun. A guided story shows local invalidation, projection reads, and deferred work for hidden views; every result is checked against an independent full evaluator.

    python3 examples/dispatch/build.py # Open _build/dispatch/index.html in your browser.

    The generated HTML is self-contained and can be shared as a single file.

    #Start with cells and thunks

    Create one engine, put changing inputs in cells, and read them with force inside thunks. Edits invalidate cached work; computation happens only when demanded. No explicit stabilization step is needed.

    ///|
    test "readme incremental total" {
    let engine = @incr.Engine()
    let price = engine.cell(20)
    let quantity = engine.cell(3)
    let total = engine.thunk(() => price.force() * quantity.force())
    assert_eq(total.force(), 60)
    assert_eq(total.force(), 60)
    assert_eq(engine.stats().evaluations, 1)
    quantity.set(4)
    assert_eq(engine.stats().evaluations, 1)
    assert_eq(total.force(), 80)
    assert_eq(engine.stats().evaluations, 2)
    }

    Dependencies can change with control flow. The engine checks old observations in execution order and stops when one changes, so it does not evaluate an obsolete branch. Equal writes do nothing. If an intermediate result remains equal, its parent can reuse its cached result without rerunning.

    #Reuse computations by argument or name

    A Memo[A, T] is a typed family of computations. call(arg) uses structural identity: equal arguments share a result. named(name, arg) uses nominal identity: reusing a name updates its arguments while preserving the articulation's identity. The table identifies the program point, so retain it across edits.

    ///|
    test "readme memoization" {
    let engine = @incr.Engine()
    let fib = @incr.Memo::recursive(engine, (memo, n : Int32) => {
    if n < 2 {
    n
    } else {
    memo.call(n - 1) + memo.call(n - 2)
    }
    })
    assert_eq(fib.call(10), 55)
    assert_eq(engine.stats().evaluations, 11)
    let double = @incr.Memo(engine, x => x * 2)
    let name = @incr.name_of_string("answer")
    let answer = double.named(name, 21)
    assert_eq(answer.force(), 42)
    assert_true(answer == double.named(name, 30))
    assert_eq(answer.force(), 60)
    }

    Cells[T] similarly groups named mutable cells; cells.cell(name, value) allocates or updates one. cells.intern(value) hash-conses immutable values. Typed families have separate name spaces, including when their types happen to be the same. engine.ns(name, body) nests a namespace. Suspended computations retain the namespace in which they were allocated.

    Named allocations inside thunks are tracked as dependencies too. If an allocated cell or a thunk's arguments are overwritten later, its allocator is invalidated and restores its allocation when next demanded. Conflicting writes to names that an actively executing thunk has already observed are rejected.

    #Observe just the part you need

    force_map records a pure projection of a value. For cells, irrelevant changes are pruned before dirtying observers. For thunks, projection equality can avoid rerunning the observer during dependency cleaning.

    ///|
    test "readme projection" {
    let engine = @incr.Engine()
    let record = engine.cell(("Ada", 20))
    let greeting = engine.thunk(() => "Hello, " + record.force_map(x => x.0))
    assert_eq(greeting.force(), "Hello, Ada")
    record.set(("Ada", 21))
    assert_eq(greeting.force(), "Hello, Ada")
    assert_eq(engine.stats().evaluations, 1)
    }

    #Collections and inspection

    The bobzhang/incr/catalog package includes named articulated lists, lazy mapping and filtering, trees, memoized tree folds and merge sort, persistent hash trie sets, and bit strings. See the collection examples.

    engine.stats() returns the current graph node count and cumulative evaluation, cache hit, dirtying, and cleaning counts. Event counters use Int64 and saturate at its maximum instead of wrapping; the node count remains Int. engine.snapshot() returns detached graph metadata with ordered dependency lists. Engine(naive=true) reruns each demanded thunk, which is useful for checking incremental results against fresh evaluation.

    #Computation contract

    • A computation uses one engine. Cross-engine observations are rejected.
    • Thunk bodies are synchronous, deterministic, and non-raising. Represent expected failures as result values. set is allowed only between computations.
    • Store immutable snapshots. Do not mutate an array, map, or mutable record that is already a cached value or memo key. Copy it and write the new value to a cell. Unlike Rust's Clone, MoonBit does not automatically deep-copy stored values.
    • Capture changing values as cells. Other captured closure state must remain fixed for the lifetime of a thunk or memo table. Equality and hashing must be consistent. A force_map callback must neither observe nor allocate graph nodes.
    • Names must be unique within each typed family and namespace for allocations that need independent identities. Use name_fork or nested namespaces to split them deterministically.
    • force_cycle(Some(fallback)) cuts a recursive demand with a supplied value; it is not a fixed-point solver. An unexpected cycle panics. Discard a computation after a panic; panic recovery is not a supported evaluation mechanism.
    • Engines retain their graph and memo tables retain their entries. There is no eviction or graph garbage collection API. Use bounded workloads and call engine.dispose() when their lifetime ends. Disposal clears edges, values, closures, and typed caches, and invalidates existing handles. It is especially important on native backends, where reference cycles are not collected. Very deep demand chains and recursive collection transformations are limited by the backend call stack.

    #Build and test

    Validated with MoonBit 0.1.20261012 / compiler 0.10.15+943464bfa. From the repository root:

    moon check --target all --warn-list +unnecessary_annotation moon test moon test --target js moon test --target native moon run cmd/demo moon fmt moon info

    README examples are executable tests. Generated pkg.generated.mbti files record the public API. The source reference under .repos/ is not needed to build. GitHub Actions runs formatting, interface checks, all-backend type checking, and Wasm GC, JavaScript, and native tests on Linux and macOS, using both the pinned 0.10.15+943464bfa toolchain and latest.

    The stress suite adds seeded differential checks against plain array oracles, reusable-name collection edits, lifecycle tests, and isolated growth/depth probes. Run python3 stress/run.py --profile full --soak-seconds 300 for a sustained native run with replay commands and memory measurements. The manual Extended stress GitHub workflow runs it on Linux and macOS. See the recorded stress results and independent production-readiness review. The reviewed deployment scope is bounded, synchronous workloads following the computation contract above; cache growth and stack depth still need application-specific limits.

    #Benchmarks

    The native comparison harness measures collection workloads and whole-process peak memory against the pinned, unmodified Rust Adapton reference. It includes aggregation, full/prefix sorting, lazy mapping/filtering, sequence edits, and repeated engine disposal. Both implementations are checked against an independent array oracle. See reproduction instructions and measured results and limitations.

    License: MPL-2.0, following the Adapton reference. See LICENSE.

    Art

    pub struct Art[T] {
    // private fields
    }

    A typed articulation: an immutable value, mutable cell, or cached computation. Values and values captured by thunks must be treated as immutable snapshots.
    impl Eq for Art[T]
    impl Hash for Art[T]
    impl Debug for Art[T]

    Art::equal

    fn[T] Art::equal(self : Art[T], other : Art[T]) -> Bool

    Art::force

    fn[T : Eq] Art::force(self : Art[T]) -> T

    Demand a result and record an observation in the calling thunk.

    Art::force_cycle

    fn[T : Eq] Art::force_cycle(self : Art[T], fallback : T?) -> T

    Use fallback when this force encounters an active thunk, or panic if absent. This is cycle cutting, not a fixed-point solver.

    Art::force_map

    fn[T, U : Eq] Art::force_map(self : Art[T], map : (T) -> U) -> U

    Observe a pure projection. Changes outside the projection do not rerun users. The mapping must not read or allocate articulations.

    Art::hash

    fn[T] Art::hash(self : Art[T]) -> Int

    Art::hash_combine

    fn[T] Art::hash_combine(self : Art[T], hasher : Hasher) -> Unit

    Art::map

    fn[T : Eq, U] Art::map(self : Art[T], map : (T) -> U) -> Art[U]

    Create a cached derived articulation in the same engine.

    Art::not_equal

    fn[T] Art::not_equal(x : Art[T], y : Art[T]) -> Bool

    Art::set

    fn[T : Eq] Art::set(self : Art[T], value : T) -> Unit

    Update an input between computations. Panics for immutable values or thunks.

    Art::to_repr

    fn[T] Art::to_repr(self : Art[T]) ->
    Repr

    Cells

    pub struct Cells[T] {
    // private fields
    }

    A typed family of named cells. Each family has its own name space. Keep this object alive and reuse it across edits.

    Cells::Cells

    fn[T] Cells::Cells(engine : Engine) -> Cells[T]

    Cells::cell

    fn[T : Eq] Cells::cell(self : Cells[T], name : Name, value : T) -> Art[T]

    Allocate or update a named cell. Inside a thunk, records an allocation edge: if someone changes the cell, the allocator must run again to restore it.

    Cells::intern

    fn[T : Hash + Eq] Cells::intern(self : Cells[T], value : T) -> Art[T]

    Hash-cons an immutable value using both hash and equality, within this namespace.

    Engine

    pub struct Engine {
    // private fields
    }

    An independent, synchronous incremental computation graph. Use one engine for all articulations in a computation.

    Engine::Engine

    fn Engine::Engine(naive? : Bool) -> Engine

    Engine::cell

    fn[T] Engine::cell(self : Engine, value : T) -> Art[T]

    Create a fresh mutable input. Equal writes do not invalidate observers.

    Engine::dispose

    fn Engine::dispose(self : Engine) -> Unit

    Release graph edges, cached values, closures, and typed memo/cell tables. Call between computations when finished with an engine, especially on native backends where reference cycles are not collected automatically. Idempotent. Previously allocated handles may no longer be forced or edited.

    Engine::ns

    fn[T] Engine::ns(self : Engine, name : Name, body : () -> T raise?) -> T raise?

    Run a body inside a nested namespace. Lazy thunks retain their allocation path.

    Engine::put

    fn[T] Engine::put(self : Engine, value : T) -> Art[T]

    Create an immutable articulation.

    Engine::snapshot

    fn Engine::snapshot(self : Engine) -> Array[NodeInfo]

    Engine::stats

    fn Engine::stats(self : Engine) -> Stats

    Engine::thunk

    fn[T] Engine::thunk(self : Engine, compute : () -> T) -> Art[T]

    Suspend a computation. Its dependencies are discovered by force calls. Bodies must be deterministic and may read cells but may not call set.

    Memo

    pub struct Memo[A, T] {
    // private fields
    }

    A typed memoized function. The table itself identifies the program point. Captured non-incremental state must stay fixed for the lifetime of the table.

    Memo::Memo

    fn[A, T] Memo::Memo(engine : Engine, body : (A) -> T) -> Memo[A, T]

    Memo::call

    fn[A : Hash + Eq, T : Eq] Memo::call(self : Memo[A, T], arg : A) -> T

    Allocate and immediately demand a structurally memoized computation.

    Memo::named

    fn[A : Eq, T] Memo::named(self : Memo[A, T], name : Name, arg : A) -> Art[T]

    Reuse a stable name. Changing arguments invalidates its previous observers and allocators, while preserving the returned articulation's identity.

    Memo::recursive

    fn[A, T] Memo::recursive(engine : Engine, body : (Memo[A, T], A) -> T) -> Memo[A, T]

    Construct a memo table whose body can recursively call the same table.

    Memo::structural

    fn[A : Hash + Eq, T] Memo::structural(self : Memo[A, T], arg : A) -> Art[T]

    Memoize by argument value and current namespace. Hash collisions are resolved by equality; different arguments never overwrite each other's results.

    Name

    pub(all) enum Name {
    Unit
    Int(Int)
    Text(String)
    Pair(Name, Name)
    Left(Name)
    Right(Name)
    } derive(Eq, Hash,
    Debug
    )

    Structural names used by typed cell stores, memo tables, and namespaces.

    Name::equal

    fn Name::equal(Name, Name) -> Bool

    Name::hash

    fn Name::hash(self : Name) -> Int

    Name::hash_combine

    fn Name::hash_combine(Name, Hasher) -> Unit

    Name::not_equal

    fn Name::not_equal(x : Name, y : Name) -> Bool

    Name::to_repr

    NodeInfo

    pub struct NodeInfo {
    id : Int
    kind : String
    path : Array[Name]
    dirty : Bool
    dependencies : Array[Int]
    } derive(Eq,
    Debug
    )

    A detached graph snapshot. Dependencies retain their observation order. Values are intentionally omitted so reflection works across all result types.

    NodeInfo::equal

    fn NodeInfo::equal(NodeInfo, NodeInfo) -> Bool

    NodeInfo::not_equal

    fn NodeInfo::not_equal(x : NodeInfo, y : NodeInfo) -> Bool

    NodeInfo::to_repr

    Stats

    pub struct Stats {
    allocated : Int
    evaluations : Int64
    cache_hits : Int64
    dirtyings : Int64
    cleanings : Int64
    } derive(Eq,
    Debug
    )

    Cumulative 64-bit event counters, saturating at Int64 maximum. Evaluation counts count thunk bodies, not cell reads. allocated is the current graph node count and remains a 32-bit array size.

    Stats::equal

    fn Stats::equal(Stats, Stats) -> Bool

    Stats::not_equal

    fn Stats::not_equal(x : Stats, y : Stats) -> Bool

    Stats::to_repr

    name_fork

    fn name_fork(name : Name) -> (Name, Name)

    name_fork3

    fn name_fork3(name : Name) -> (Name, Name, Name)

    name_fork4

    fn name_fork4(name : Name) -> (Name, Name, Name, Name)

    name_of_int

    fn name_of_int(value : Int) -> Name

    name_of_string

    fn name_of_string(value : String) -> Name

    name_pair

    fn name_pair(left : Name, right : Name) -> Name

    name_unit

    fn name_unit() -> Name

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io