🥮 mooncakes.io
    Sign in

    datafrog

    Semi-naive fixed-point relational computation in MoonBit, ported from Datafrog

    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0 OR MIT
    Repository
    Last updated
    12 hours ago
    Downloads
    3

    #Datafrog for MoonBit

    A pure MoonBit port of Rust Datafrog: small, typed building blocks for monotone relational fixed-point computation. Use it for graph reachability, program analysis, permissions, and recursive rules. The module is bobzhang/datafrog, with no external MoonBit dependencies.

    ///|
    test "transitive permissions" {
      let iteration = @datafrog.Iteration()
      let permissions : @datafrog.Variable[(String, String)] = iteration.variable(
        "permissions",
      )
      let parents = @datafrog.Relation([("editors", "alice"), ("staff", "editors")])
      permissions.insert_all([("staff", "read dashboard")])
      while iteration.changed() {
        permissions.from_join(permissions, parents.as_input(), fn(
          _,
          permission,
          person,
        ) {
          (person, permission)
        })
      }
      assert_eq(permissions.complete().to_array(), [
        ("alice", "read dashboard"),
        ("staff", "read dashboard"),
        ("editors", "read dashboard"),
      ])
    }

    #Installation

    moon add bobzhang/datafrog@0.1.0

    GitHub · Mooncakes

    #Model and API

    Relation(tuples) sorts and deduplicates a copy of its input. Relations are immutable sets; to_array() returns a copy. Tuple values themselves must be immutable and have a consistent total Compare order.

    Iteration() creates variables with iteration.variable("name"). insert(relation) or insert_all(tuples) queues facts. Each changed() call moves the old frontier into stable batches and exposes new, previously unseen facts through recent(). Always call every rule inside the loop. A variable may be both input and output of a rule.

    • from_map and from_map_filtered transform only the new frontier.
    • from_join and from_join_filtered join a variable with a dynamic variable or fixed relation using as_input(). Dynamic joins process recent × stable, stable × recent, and recent × recent; old × old pairs are skipped.
    • from_antijoin excludes keys from a fixed relation.
    • from_leapjoin combines an array of multiway constraints. extend_with proposes values, extend_anti excludes values, and filter_with/filter_anti test prefix membership. Leaper::filter and prefix_filter accept pure predicates. At least one leaper must propose values; use Leaper::passthrough() to propose Unit for a prefix-only filter chain.
    • Relation::from_* variants evaluate the same operations over full relations.
    • complete() returns a non-consuming snapshot after the variable stabilizes. You can insert more facts and resume the same iteration. stats() exposes stable/recent/pending tuple counts; round() counts calls to changed().
    • variable("name", distinct=false) allows repeated frontiers. Every recursive cycle must include a distinct variable to ensure duplicate suppression.
    • dispose() unregisters stages and invalidates variable handles. There is no internal iteration/variable reference cycle, including on the native backend.

    #Contracts and limits

    This engine adds facts. It does not retract facts, track timestamps or support concurrent execution. For deletion-aware updates use a differential engine. Static relations used by rules must stay fixed throughout an incremental run. Callbacks must be deterministic and must not mutate or advance the iteration. All variables participating in a rule must belong to the same iteration.

    Finite input does not guarantee termination when rules generate new values. Applications must impose round/resource limits appropriate to their domain. No production-readiness or Rust performance-parity claim is made. See PORTING.md for algorithm and API differences.

    #Validation

    moon fmt --check
moon check --target all --warn-list +unnecessary_annotation --deny-warn
moon test --target all
moon run cmd/demo
# Restore pinned reference using UPSTREAM.md first:
python3 validation/compare.py

    Tests cover round visibility, duplicate suppression, joins, antijoins, multiway constraints, ownership checks, 80 seeded graphs with four insertion phases, and three 10,000-step fixed-point runs. The Rust harness checks 512 seeds × two insertion phases × three join strategies against pinned upstream and an independent Python graph-search oracle. Results are in validation/results.json.

    CI runs all four backends on Linux and macOS, pinned and latest MoonBit, plus the Rust differential harness. Developed with MoonBit 0.10.15+943464bfa.

    Dual licensed under MIT or Apache-2.0; upstream notices are retained.

    Iteration

    source
    pub struct Iteration {
      // private fields
    }

    Advances all registered variables together, exposing one new frontier per round.

    Iteration::Iteration

    source
    fn Iteration::Iteration() -> Iteration

    Iteration::changed

    source
    fn Iteration::changed(self : Iteration) -> Bool

    Iteration::dispose

    source
    fn Iteration::dispose(self : Iteration) -> Unit

    Unregister all stages. Existing variable handles can no longer be used.

    Iteration::round

    source
    fn Iteration::round(self : Iteration) -> Int

    Iteration::stats

    source
    fn Iteration::stats(self : Iteration) -> Array[VariableStats]

    Iteration::variable

    source
    fn[T : Compare + Eq] Iteration::variable(self : Iteration, name : String, distinct? : Bool) -> Variable[T]

    JoinInput

    source
    pub(all) enum JoinInput[T] {
      Dynamic(Variable[T])
      Static(Relation[T])
    }

    The right input of a semi-naive join is either changing or fixed.

    Leaper

    source
    pub struct Leaper[P, V] {
      // private fields
    }

    One constraint in a multiway join. Callbacks must be pure.

    Leaper::filter

    source
    fn[P, V] Leaper::filter(predicate : (P, V) -> Bool) -> Leaper[P, V]

    Leaper::passthrough

    source
    fn[P] Leaper::passthrough() -> Leaper[P, Unit]

    Supplies the unit value when all other leapers only filter prefixes.

    Leaper::prefix_filter

    source
    fn[P, V] Leaper::prefix_filter(predicate : (P) -> Bool) -> Leaper[P, V]

    Relation

    source
    pub struct Relation[T] {
      // private fields
    }

    Sorted, duplicate-free tuples. Tuples and their comparison order must be immutable.

    Relation::Relation

    source
    fn[T : Compare + Eq] Relation::Relation(elements : Array[T]) -> Relation[T]

    Relation::as_input

    source
    fn[T] Relation::as_input(self : Relation[T]) -> JoinInput[T]

    Relation::contains

    source
    fn[T : Compare + Eq] Relation::contains(self : Relation[T], value : T) -> Bool

    Relation::extend_anti

    source
    fn[K : Compare + Eq, V : Compare + Eq, P] Relation::extend_anti(self : Relation[(K, V)], key : (P) -> K) -> Leaper[P, V]

    Relation::extend_with

    source
    fn[K : Compare + Eq, V : Compare + Eq, P] Relation::extend_with(self : Relation[(K, V)], key : (P) -> K) -> Leaper[P, V]

    Relation::filter_anti

    source
    fn[T : Compare + Eq, P, V] Relation::filter_anti(self : Relation[T], key : (P) -> T) -> Leaper[P, V]

    Relation::filter_with

    source
    fn[T : Compare + Eq, P, V] Relation::filter_with(self : Relation[T], key : (P) -> T) -> Leaper[P, V]

    Relation::from_antijoin

    source
    fn[K : Compare + Eq, A, C : Compare + Eq] Relation::from_antijoin(input : Relation[(K, A)], excluded : Relation[K], logic : (K, A) -> C) -> Relation[C]

    Negation is only sound against a fixed relation of keys.

    Relation::from_join

    source
    fn[K : Compare + Eq, A, B, C : Compare + Eq] Relation::from_join(left : Relation[(K, A)], right : Relation[(K, B)], logic : (K, A, B) -> C) -> Relation[C]

    Relation::from_join_filtered

    source
    fn[K : Compare + Eq, A, B, C : Compare + Eq] Relation::from_join_filtered(left : Relation[(K, A)], right : Relation[(K, B)], logic : (K, A, B) -> C?) -> Relation[C]

    Relation::from_leapjoin

    source
    fn[P, V, O : Compare + Eq] Relation::from_leapjoin(input : Relation[P], leapers : Array[Leaper[P, V]], logic : (P, V) -> O) -> Relation[O]

    Relation::from_map

    source
    fn[A, B : Compare + Eq] Relation::from_map(input : Relation[A], logic : (A) -> B) -> Relation[B]

    Relation::from_map_filtered

    source
    fn[A, B : Compare + Eq] Relation::from_map_filtered(input : Relation[A], logic : (A) -> B?) -> Relation[B]

    Relation::is_empty

    source
    fn[T] Relation::is_empty(self : Relation[T]) -> Bool

    Relation::length

    source
    fn[T] Relation::length(self : Relation[T]) -> Int

    Relation::merge

    source
    fn[T : Compare + Eq] Relation::merge(self : Relation[T], other : Relation[T]) -> Relation[T]

    Relation::to_array

    source
    fn[T] Relation::to_array(self : Relation[T]) -> Array[T]

    Variable

    source
    pub struct Variable[T] {
      // private fields
    }

    Variable::as_input

    source
    fn[T] Variable::as_input(self : Variable[T]) -> JoinInput[T]

    Variable::complete

    source
    fn[T : Compare + Eq] Variable::complete(self : Variable[T]) -> Relation[T]

    Return a non-consuming snapshot after quiescence. More facts may be inserted later.

    Variable::from_antijoin

    source
    fn[K : Compare + Eq, A, C : Compare + Eq] Variable::from_antijoin(self : Variable[C], input : Variable[(K, A)], excluded : Relation[K], logic : (K, A) -> C) -> Unit

    Variable::from_join

    source
    fn[K : Compare + Eq, A, B, C : Compare + Eq] Variable::from_join(self : Variable[C], left : Variable[(K, A)], right : JoinInput[(K, B)], logic : (K, A, B) -> C) -> Unit

    Variable::from_join_filtered

    source
    fn[K : Compare + Eq, A, B, C : Compare + Eq] Variable::from_join_filtered(self : Variable[C], left : Variable[(K, A)], right : JoinInput[(K, B)], logic : (K, A, B) -> C?) -> Unit

    Variable::from_leapjoin

    source
    fn[P, V, O : Compare + Eq] Variable::from_leapjoin(self : Variable[O], input : Variable[P], leapers : Array[Leaper[P, V]], logic : (P, V) -> O) -> Unit

    Variable::from_map

    source
    fn[A, B : Compare + Eq] Variable::from_map(self : Variable[B], input : Variable[A], logic : (A) -> B) -> Unit

    Variable::from_map_filtered

    source
    fn[A, B : Compare + Eq] Variable::from_map_filtered(self : Variable[B], input : Variable[A], logic : (A) -> B?) -> Unit

    Variable::insert

    source
    fn[T] Variable::insert(self : Variable[T], relation : Relation[T]) -> Unit

    Variable::insert_all

    source
    fn[T : Compare + Eq] Variable::insert_all(self : Variable[T], tuples : Array[T]) -> Unit

    Variable::is_stable

    source
    fn[T] Variable::is_stable(self : Variable[T]) -> Bool

    Variable::name

    source
    fn[T] Variable::name(self : Variable[T]) -> String

    Variable::recent

    source
    fn[T] Variable::recent(self : Variable[T]) -> Relation[T]

    Variable::stats

    source
    fn[T] Variable::stats(self : Variable[T]) -> VariableStats

    VariableStats

    source
    pub struct VariableStats {
      name : String
      stable : Int
      recent : Int
      pending : Int
      batches : Int
    }

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io