Research / 2022 –

Programs as data: point-free combinators in JSON

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

A small combinator language whose programs are JSON arrays: its reduction rules, what its combinators can and cannot express, and why programs without variables are easy to store, hash and evaluate deterministically.

Combinatory logicPoint-free styleHomoiconicity
0
variable binders in the language; every program is a closed term
18
library functions in the evaluator on this page, four of them pure combinators
5,000
call budget per evaluation; without it a two-term program diverges

Some programs are better kept as data: access rules, triggers, scheduled jobs. These are values that one machine writes and many machines evaluate, so the program has to be serialized, hashed, compared and run in a sandbox, and every evaluator has to reach the same result. A general-purpose language makes all of these hard, because it has variables, closures over a host environment, and a large standard library.

This article looks at the other extreme: a language with no variables at all, whose programs are plain JSON arrays and whose only operation is applying named functions. It is combinatory logic written in Lisp syntax. I give the reduction rules of its evaluator with a Lean model, prove a currying law for it, show what its four pure combinators can and cannot express, and list the trade-offs.

Combinators: computing without variables

Schönfinkel (1924) and later Curry observed that bound variables can be removed from logic altogether. Take the two combinators

K x y=x,S x y z=x z (y z),\mathbf{K}\,x\,y = x, \qquad \mathbf{S}\,x\,y\,z = x\,z\,(y\,z),

with application written by juxtaposition and associating to the left. The identity is not primitive, because S K K x=K x (K x)=x\mathbf{S}\,\mathbf{K}\,\mathbf{K}\,x = \mathbf{K}\,x\,(\mathbf{K}\,x) = x, so I=SKK\mathbf{I} = \mathbf{S}\mathbf{K}\mathbf{K}.

Combinatory completeness. For every term MM built from variables, S\mathbf{S} and K\mathbf{K}, and every variable xx, there is a term [x]M[x]M that does not contain xx and satisfies ([x]M) N=M[N/x]([x]M)\,N = M[N/x] for every NN.

Proof sketch. Define [x]M[x]M by bracket abstraction: [x]x=I[x]x = \mathbf{I}; [x]M=K M[x]M = \mathbf{K}\,M if xx does not occur in MM; [x](M N)=S ([x]M) ([x]N)[x](M\,N) = \mathbf{S}\,([x]M)\,([x]N). Each clause is checked by direct reduction. For the third, S ([x]M) ([x]N) P=([x]M) P (([x]N) P)\mathbf{S}\,([x]M)\,([x]N)\,P = ([x]M)\,P\,(([x]N)\,P), which equals M[P/x] N[P/x]M[P/x]\,N[P/x] by induction.

So every λ-term has a variable-free equivalent. The translation can be much larger than the source. Curry’s optimized abstraction, which Turner (1979) used to compile functional programs, also uses the combinators B f g x=f (g x)\mathbf{B}\,f\,g\,x = f\,(g\,x) and C f x y=f y x\mathbf{C}\,f\,x\,y = f\,y\,x to keep it smaller.

Two programming ideas follow from this. Currying treats a function of nn arguments as a function of one argument that returns a function of n−1n-1 arguments, so partial application costs nothing. Point-free style writes a function as a composition of other functions and never names its argument. For example, compose(neg, add) is the function that negates a sum, and no variable appears in it.

JSON arrays as expression trees

Lisp is homoiconic: its programs are written as its own list data structure. JSON has lists too, so the same trick works there. In the language described here, an array whose first element names a function is an application, and anything else is data. The snippets on this page are Lean 4. They write programs with Lean’s json% literal, so each program is the JSON text itself, and the values in the comments are checked by running the Lean model of the evaluator given in the next section:

-- Programs are plain JSON; Lean's `json%` literal writes them verbatim.
import Lean.Data.Json
open Lean

def addP     := json% ["add", 1, 2]                      -- add(1, 2)          = 3
def curryP   := json% [["add", 1], 2]                    -- add(1)(2)          = 3
def mapP     := json% [["map", ["inc"]], [1, 2, 3]]      -- map(inc)([1,2,3])  = [2, 3, 4]
def sortP    := json% ["sortBy", ["prop", "age"],        -- sort by a key, no lambda
                        [{"n": "b", "age": 30}, {"n": "a", "age": 24}]]
def bareName := json% ["map", "inc", [1, 2, 3]]          -- error: "inc" is not a function
def filterP  := json% ["filter", ["gt", 2], [1, 2, 3, 4]] -- keep elements > 2 = [3, 4]

A function is always referred to as the array ["inc"]. The bare string "inc" is only a string, so ["map", "inc", [1, 2, 3]] fails with “inc” is not a function. The library is data-last, as in Haskell: ["gt", 1, 2] is 2>12 \gt 1, which makes ["filter", ["gt", 2], xs] mean “keep the elements greater than 2”.

Value
Reduction trace
    Fig. 1Interactive. Edit a JSON program and see its value and the reduction trace. Each trace line is one saturated call, indented by nesting depth. Partial applications build a closure and add no line.

    Reduction rules

    Let L\mathcal{L} be the library: a finite map from names to pairs (nf,implf)(n_f, \mathit{impl}_f) of an arity and a host function. Values are JSON values plus closures ⟨f;u1…uk⟩\langle f; u_1 \ldots u_k \rangle with k<nfk \lt n_f, meaning ff is waiting for nf−kn_f - k more arguments. The one-element array [s][s] of a library name ss evaluates to the empty closure ⟨s;⟩\langle s; \rangle; the bare string ss is data.

    Application. For a closure ⟨f;uˉ⟩\langle f; \bar u \rangle and argument values vˉ\bar v, let wˉ=uˉ+ ⁣ ⁣+vˉ\bar w = \bar u \mathbin{+\!\!+} \bar v (concatenation).

    • If ∣wˉ∣<nf|\bar w| \lt n_f, then apply=⟨f;wˉ⟩\mathrm{apply} = \langle f; \bar w \rangle (partial application).
    • Otherwise let r=implf(w1,…,wnf)r = \mathit{impl}_f(w_1, \ldots, w_{n_f}). If ∣wˉ∣=nf|\bar w| = n_f, the result is rr. If there are arguments left over, the result is apply(r,wnf+1,…)\mathrm{apply}(r, w_{n_f+1}, \ldots) (over-application), and it is an error if rr is not a closure.

    Every call of apply\mathrm{apply}, partial or saturated, takes one unit from a budget of 5,000, and the recursive call made by over-application counts as another. The 5,001st call aborts the evaluation.

    The Lean model below follows these rules. Values are a Val type with two closure forms, one for library functions and one for the functions that compose builds. Evaluation runs in a state monad that holds the remaining budget and can fail with an error message. Figure 1 is an interactive evaluator for the language. The results quoted on this page are those of the Lean model.

    -- continues the definitions above
    /-- JSON values plus closures ⟨f; u₁ … uₖ⟩. Numbers are modelled as `Int`. -/
    inductive Val where
      | null | bool (b : Bool) | num (n : Int) | str (s : String)
      | arr (xs : List Val) | obj (kvs : List (String × Val))
      | prim (name : String) (args : List Val)           -- a library function
      | comp (f g : Val) (arity : Nat) (args : List Val) -- built by `compose`
      deriving Inhabited
    
    /-- The library 𝓛: names and arities (implementations come below). -/
    def arity? : String → Option Nat
      | "I" | "inc" | "neg" | "not" => some 1
      | "K" | "add" | "mul" | "gt" | "eq" | "prop" | "map" | "filter"
      | "sortBy" | "difference" | "range" | "compose" => some 2
      | "reduce" | "flip" => some 3
      | _ => none
    
    def library := ["I", "K", "inc", "neg", "add", "mul", "gt", "eq", "not", "prop",
      "map", "filter", "reduce", "sortBy", "difference", "range", "compose", "flip"]
    
    example : library.length = 18 ∧ library.all (arity? · |>.isSome) := by decide
    
    /-- Closures carry their arity n_f and the k < n_f arguments they hold. -/
    def Val.closure? : Val → Option (Nat × List Val)
      | .prim s us     => (arity? s).map (·, us)
      | .comp _ _ n us => some (n, us)
      | _              => none
    -- continues the definitions above
    /-- The printer used in error messages and the trace (strings are quoted). -/
    partial def Val.show : Val → String
      | .null => "null" | .bool b => toString b | .num n => toString n
      | .str s => (Json.str s).compress
      | .arr xs => "[" ++ ", ".intercalate (xs.map Val.show) ++ "]"
      | .obj kvs => "{" ++ ",".intercalate (kvs.map fun (k, v) => (Json.str k).compress ++ ":" ++ v.show) ++ "}"
      | .prim s [] => s
      | .prim s us => s ++ "(" ++ ", ".intercalate (us.map Val.show) ++ ")"
      | .comp f g _ us =>
          let h := s!"({f.show} ∘ {g.show})"
          if us.isEmpty then h else h ++ "(" ++ ", ".intercalate (us.map Val.show) ++ ")"
    
    /-- Evaluation runs in a state monad holding the call budget, and can fail. -/
    abbrev M := StateT Nat (Except String)
    
    def num : Val → M Int
      | .num n => pure n
      | v      => throw s!"expected a number, got {v.show}"
    def list : Val → M (List Val)
      | .arr xs => pure xs
      | v       => throw s!"expected a list, got {v.show}"
    def truthy : Val → Bool
      | .null | .bool false | .num 0 | .str "" => false
      | _ => true
    def key : Val → String     -- property names: non-strings use their printed form
      | .str s => s
      | v => v.show
    def jsonEq (a b : Val) : Bool := a.show == b.show   -- compares serializations

    The library implementations take apply as a parameter, because map, filter, reduce, sortBy and flip call functions they were given.

    -- continues the definitions above
    /-- impl_f for each library name, given `call` (= apply) for higher-order ones. -/
    def impl (call : Val → List Val → M Val) : String → List Val → M Val
      | "I", [x] | "K", [x, _] => pure x
      | "inc", [x]     => return .num ((← num x) + 1)
      | "neg", [x]     => return .num (-(← num x))
      | "add", [a, b]  => return .num ((← num a) + (← num b))
      | "mul", [a, b]  => return .num ((← num a) * (← num b))
      | "gt", [a, b]   => return .bool ((← num b) > (← num a))   -- data-last: b > a
      | "eq", [a, b]   => pure (.bool (jsonEq a b))
      | "not", [x]     => pure (.bool !truthy x)
      | "prop", [k, .obj kvs] => pure ((kvs.lookup (key k)).getD .null)  -- missing: null
      | "prop", [_, _] => pure .null
      | "map", [f, xs]    => return .arr (← (← list xs).mapM (call f [·]))
      | "filter", [p, xs] => return .arr (← (← list xs).filterM fun x => truthy <$> call p [x])
      | "reduce", [f, z, xs] => do (← list xs).foldlM (fun acc x => call f [acc, x]) z
      | "sortBy", [f, xs] => do          -- one key call per element, then a stable sort
          let ks ← (← list xs).mapM fun x => return ((← num (← call f [x])), x)
          pure (.arr ((ks.mergeSort (·.1 ≤ ·.1)).map (·.2)))
      | "difference", [a, b] => do
          let bs ← list b
          return .arr ((← list a).filter fun x => !bs.any (jsonEq x))
      | "range", [a, b] => do
          let a ← num a; let b ← num b
          return .arr ((List.range (b - a).toNat).map fun (i : Nat) => .num (a + i))
      | "compose", [f, g] => match g.closure? with
          | some (n, us) => pure (.comp f g (max 1 (n - us.length)) [])
          | none => throw "compose expects functions"
      | "flip", [f, a, b] => call f [b, a]
      | s, _ => throw s!"{s} is not a function"

    apply is a partial def: it terminates only because of the budget, and the self-application example below shows that nothing else bounds it.

    -- continues the definitions above
    /-- The same closure holding a new argument list. -/
    def Val.withArgs : Val → List Val → Val
      | .prim s _, ws     => .prim s ws
      | .comp g h n _, ws => .comp g h n ws
      | v, _              => v
    
    /-- apply: every call costs one unit; the 5,001st call aborts. -/
    partial def apply (f : Val) (vs : List Val) : M Val := do
      let some (n, us) := f.closure? | throw s!"{f.show} is not a function"
      let budget ← get
      if budget = 0 then throw "step budget exhausted"
      set (budget - 1)
      let ws := us ++ vs
      if ws.length < n then return f.withArgs ws              -- partial application
      let r ← match f with
        | .comp g h _ _ => do apply g [← apply h (ws.take n)] -- compose(g, h)
        | .prim s _     => impl apply s (ws.take n)
        | v             => pure v
      if ws.length = n then pure r else apply r (ws.drop n)   -- over-application

    Evaluation. E\mathcal{E} is defined by the first clause that matches. An array whose head is a library name is an application, an array whose head is itself an array is evaluated according to what the head evaluates to, and every other array is data.

    -- continues the definitions above
    /-- 𝓔: the first matching clause wins. Arguments are evaluated left to right. -/
    partial def eval : Val → M Val
      | .arr [] => pure (.arr [])
      | .arr (.str "[]" :: as) => .arr <$> as.mapM eval        -- list constructor
      | .arr (.str s :: as) =>
          if (arity? s).isSome then                            -- s a library name
            if as.isEmpty then pure (.prim s []) else do apply (.prim s []) (← as.mapM eval)
          else .arr <$> (.str s :: as).mapM eval               -- unknown name: data
      | .arr (h@(.arr _) :: as) => do
          let v ← eval h
          match v.closure?, as with
          | some _, [] => pure v
          | some _, _  => apply v (← as.mapM eval)
          | none, _    => return .arr (v :: (← as.mapM eval))  -- a data array
      | .arr xs => .arr <$> xs.mapM eval                       -- any other head
      | x => pure x

    Evaluation is strict: arguments are evaluated before the call, from left to right. Objects, integers and strings evaluate to themselves. (The model reads every JSON number as an integer, so a non-integer such as 1.5 is truncated to 1 when the program is read.) An array whose head is a number, an object or an unknown string is data, so [1, 2, ["add", 1, 2]] evaluates to [1, 2, 3]. The "[]" head is a list constructor, not a full quote. Its elements are still evaluated, but the list itself is never applied. It is needed when a data list begins with a function name: ["[]", "add", 1] is the list ["add", 1], and ["[]", ["add", 1], ["inc"]] is a list of two closures.

    -- continues the definitions above
    /-- Read a JSON program and run it with a fresh budget of 5,000 calls. -/
    partial def ofJson : Json → Val
      | .null => .null | .bool b => .bool b | .str s => .str s
      | .num n => .num (n.mantissa / 10 ^ n.exponent)
      | .arr xs => .arr (xs.toList.map ofJson)
      | .obj kvs => .obj (kvs.fold (fun acc k v => acc ++ [(k, ofJson v)]) [])
    
    /-- The printed outcome of a run: a value or an error message. -/
    structure Out where
      text : String
      deriving DecidableEq
    instance : Repr Out := ⟨fun o _ => o.text⟩
    
    def run (p : Json) : Out :=
      match (eval (ofJson p)).run' 5000 with
      | .ok v => ⟨v.show⟩
      | .error e => ⟨"Error: " ++ e⟩

    Currying law. For a closure cc, an argument list aˉ\bar a and a non-empty argument list bˉ\bar b, apply(apply(c,aˉ),bˉ)=apply(c,aˉ+ ⁣ ⁣+bˉ)\mathrm{apply}(\mathrm{apply}(c, \bar a), \bar b) = \mathrm{apply}(c, \bar a \mathbin{+\!\!+} \bar b), whenever both sides finish within the budget. Consequently, if E([s,a1..an])\mathcal{E}([s, a_1..a_n]) is a closure, then E([[s,a1..an],b1..bm])=E([s,a1..an,b1..bm])\mathcal{E}([[s, a_1..a_n], b_1..b_m]) = \mathcal{E}([s, a_1..a_n, b_1..b_m]) for m≥1m \ge 1; for m=0m = 0 both sides are that closure.

    Proof. Let c=⟨f;uˉ⟩c = \langle f; \bar u \rangle. If ∣uˉaˉ∣<nf|\bar u \bar a| \lt n_f, the left side is apply(⟨f;uˉaˉ⟩,bˉ)\mathrm{apply}(\langle f; \bar u \bar a \rangle, \bar b), which concatenates to the same wˉ\bar w as the right side. Otherwise both sides compute the same rr from the first nfn_f arguments. The left side then gives apply(apply(r,aˉ′),bˉ)\mathrm{apply}(\mathrm{apply}(r, \bar a'), \bar b) with leftover aˉ′\bar a', and the right side gives apply(r,aˉ′bˉ)\mathrm{apply}(r, \bar a' \bar b). These are equal by induction on the total number of arguments (if rr is not a closure, both sides fail with the same error). If aˉ′\bar a' is empty, both sides are apply(r,bˉ)\mathrm{apply}(r, \bar b), because bˉ\bar b is non-empty. The condition is needed: with c=⟨add;1⟩c = \langle \mathit{add}; 1 \rangle, aˉ=[2]\bar a = [2] and bˉ\bar b empty, the right side is 3 and the left side fails with 3 is not a function.

    The closure condition matters. [["add", 1, 2], 3] is not ["add", 1, 2, 3]. The inner call is saturated and returns the number 3, so the outer array is data and evaluates to [3, 3]. The flat form over-applies 3 to 3 and fails with 3 is not a function. Over-application also explains the trace of [["K", ["I"]], "ignored", 42]. K\mathbf{K} takes I\mathbf{I} and "ignored" and returns I\mathbf{I}, and the leftover 42 goes to I\mathbf{I}, so the result is 42. That is K I x y=y\mathbf{K}\,\mathbf{I}\,x\,y = y. The model confirms each of these results, and two instances of the currying law are checked by evaluation:

    -- continues the definitions above
    #eval run addP      -- 3
    #eval run curryP    -- 3
    #eval run mapP      -- [2, 3, 4]
    #eval run sortP     -- [{"age":24,"n":"a"}, {"age":30,"n":"b"}]
    #eval run bareName  -- Error: "inc" is not a function
    #eval run filterP   -- [3, 4]
    #eval run (json% [1, 2, ["add", 1, 2]])          -- [1, 2, 3]
    #eval run (json% ["[]", "add", 1])               -- ["add", 1]
    #eval run (json% ["[]", ["add", 1], ["inc"]])    -- [add(1), inc]
    #eval run (json% [["add", 1, 2], 3])             -- [3, 3]
    #eval run (json% ["add", 1, 2, 3])               -- Error: 3 is not a function
    #eval run (json% [["K", ["I"]], "ignored", 42])  -- 42
    #eval run (json% [["compose", ["neg"], ["add"]], 2, 3])  -- -5
    #eval run (json% ["gt", 1, 2])                   -- true
    
    -- instances of the currying law
    example : run (json% [["add", 1], 2]) = run (json% ["add", 1, 2]) := by native_decide
    example : run (json% [["reduce", ["add"]], 0, [1, 2, 3]])
            = run (json% ["reduce", ["add"], 0, [1, 2, 3]]) := by native_decide

    What the combinators can and cannot express

    The library has four pure combinators: I, K, flip (which is C\mathbf{C}) and compose. compose is a slightly uncurried B\mathbf{B}. compose(f, g) has arity max⁡(1,ng−kg)\max(1, n_g - k_g), where kgk_g is the number of arguments gg already holds, and it passes all of its arguments to gg. So compose(neg, add) applied to 2 and 3 gives −5-5. There is no S\mathbf{S}.

    The B, C, K, I fragment cannot duplicate. Let FF be any term built from B,C,K,I\mathbf{B}, \mathbf{C}, \mathbf{K}, \mathbf{I} by application. Then every reduct of F x1⋯xnF\,x_1 \cdots x_n contains each variable xix_i at most once. In particular, λx. f x x\lambda x.\,f\,x\,x and λx. x x\lambda x.\,x\,x cannot be expressed.

    Proof. The right-hand sides f (g x)f\,(g\,x), f y xf\,y\,x, xx and xx each contain every argument of their rule at most once. So a reduction step never copies a subterm, and the number of occurrences of a variable never increases. Initially each xix_i occurs once.

    These are the affine combinators of substructural logic: they allow weakening (K\mathbf{K} discards) and exchange (C\mathbf{C} swaps), but not contraction. The library gets duplication back through its iterating primitives, because a function given to map or reduce is used once per element. Two examples, both checked against the evaluator:

    -- continues the definitions above
    /-- Apply a program to arguments: the JSON array [f, a₁, …, aₙ]. -/
    def ap (f : Json) (as : List Json) : Json := .arr (f :: as).toArray
    
    -- x ↦ x² with x used once: the sum of the first x odd numbers
    def square := json% ["compose", ["reduce", ["add"], 0],
      ["compose", ["map", ["compose", ["inc"], ["mul", 2]]], ["range", 0]]]
    #eval run (ap square [7])                        -- 49
    
    -- dup: x ↦ [x, x], via map(K x) over [0, 1]
    def dup := json% ["compose", ["flip", ["map"], ["range", 0, 2]],
                                 ["compose", ["K"], ["I"]]]
    #eval run (ap dup [5])                           -- [5, 5]
    
    -- reduce(I, I, [f, x]) computes f x, so on [x, x] it computes x x
    #eval run (json% ["reduce", ["I"], ["I"], ["[]", ["inc"], 4]])  -- 5
    
    -- δ = compose(reduce(I, I), dup) and Ω = [δ, δ]
    def δ := json% ["compose", ["reduce", ["I"], ["I"]],
      ["compose", ["flip", ["map"], ["range", 0, 2]], ["compose", ["K"], ["I"]]]]
    #eval run (ap δ [δ])                             -- Error: step budget exhausted

    The inner compose(K, I) is there because compose(f, K) would have arity 2. Wrapping K in I makes the arity 1, so the result is the closure K x\mathbf{K}\,x. Once duplication is available, so is self-application. reduce(I, I, [x, x]) computes x xx\,x, because I over-applied to the accumulator and an element applies one to the other. So with δ=compose(reduce(I, I), dup)\delta = \texttt{compose(reduce(I, I), dup)}, the program [δ,δ][\delta, \delta] is the classic Ω=(λx. x x)(λx. x x)\Omega = (\lambda x.\,x\,x)(\lambda x.\,x\,x). Run in the Lean model above, it stops with step budget exhausted. The budget is therefore not a safety margin. It is the only thing that makes evaluation total.

    Why variable-free programs are convenient

    A closed vocabulary. A program can do nothing except call functions in L\mathcal{L}. It has no eval, no property access on host objects, no I/O and no name that reaches outside the library. Sandboxing then means auditing a finite table of functions, not a general-purpose runtime. A host that wants to give the program some input applies the program to that input as a value, apply(E(p),[doc])\mathrm{apply}(\mathcal{E}(p), [\mathit{doc}]), which passes doc\mathit{doc} without evaluating it. (Writing the program [p,doc][p, \mathit{doc}] would also evaluate doc\mathit{doc}.) Nothing reaches the program through an environment.

    Serialization, hashing and diffing. A program is already a JSON value, so it is stored and sent like any other document. There are no bound variable names, so two programs are α-equivalent exactly when they are syntactically equal. Hashing a canonical serialization then identifies programs up to renaming without de Bruijn indices. This identification is intensional, not extensional: ["inc"] and ["add", 1] compute the same function but hash differently. Diffing two versions of a rule is a tree diff on nested arrays.

    Determinism. If every implf\mathit{impl}_f is a deterministic function of its arguments, then E(p)\mathcal{E}(p) is determined by pp and L\mathcal{L}: the same value, the same error, or budget exhaustion.

    Proof sketch. Every clause of E\mathcal{E} and apply\mathrm{apply} is a function of its inputs, and the only state is the budget counter, which starts at the same value on every run. The claim follows by induction on the evaluation.

    The hypothesis has to be checked one primitive at a time, and it covers cost as well as value. Every call spends budget, so a primitive that calls its function argument a number of times not fixed by its inputs (for example, a sort whose number of comparator calls depends on the sorting algorithm) would make the point of budget exhaustion depend on the evaluator. The model’s sortBy calls the key function exactly once per element and then runs a stable merge sort, so its cost depends only on the input. The model’s numbers are exact integers. IEEE doubles would also be deterministic here, because addition and multiplication on them are correctly rounded.

    Variable stores break purity. Point-free programs get hard to read once one value is needed in three places. The usual fix is a let form that writes into a dictionary shared across evaluations. The value of a program then depends on that dictionary and on the order in which earlier programs ran, so evaluation order becomes observable. Purity can be recovered by making the store explicit, E(p,σ)=(v,σ′)\mathcal{E}(p, \sigma) = (v, \sigma'), so that replicas agree when they start from the same σ\sigma and apply programs in the same order. At that point the language is a state machine, and the agreement on order has to come from outside the language.

    Logic stored as data

    The pattern I keep using is a database or replicated log that stores rules next to documents:

    • Access rules. A write is accepted if apply(E(rule),[request])\mathrm{apply}(\mathcal{E}(\mathit{rule}), [\mathit{request}]) is true. For example, ["compose", ["gt", 17], ["prop", "age"]] accepts a document whose age is greater than 17.
    • Triggers. A function from a changed document to a list of follow-up writes, evaluated after each commit.
    • Scheduled jobs. A program paired with a schedule. Each replica evaluates it at the same logical tick, not at its own wall-clock time, so all replicas derive the same writes.

    In each case the rule is itself a document. It can be versioned, hashed into the state commitment, diffed in review and changed by an ordinary write.

    Costs, limitations and open questions

    • Cost. Apart from calls, E\mathcal{E} visits each node of the program once, so the cost is O(∣p∣)O(|p|) plus the calls and the primitives’ own work. The budget counts calls, not work: ["range", 0, 1000000] uses one unit of budget and builds a million-element array. A fair metering scheme has to charge the primitives by the size of their output.
    • Readability. Without names, sharing a value means plumbing it through flip and compose. The dup term above is short, but it is not obvious what it does. A compiler from a λ-syntax by bracket abstraction would help, but the library has no S\mathbf{S}, so every variable used more than once would have to be compiled through an iterating primitive, as in dup, and the compiled terms can be much larger than the source.
    • Equality. eq compares serializations, so it agrees with equality of JSON values only when the serialization orders object keys canonically. The model reads programs through Lean’s Json type, which keeps object keys sorted, so {"a":1,"b":2} and {"b":2,"a":1} compare equal. Equality is part of the semantics, so the canonical key order is too.
    • Name lookup. L\mathcal{L} is a closed finite map. A head names a function only if it is one of the 18 names in arity?, which is a closed match, and every other string is data.
    • Open questions. Is there a typing discipline for this untyped JSON syntax that rules out is not a function errors before a program is stored? Which subset of the library is total without a budget? (The fragment built from I, K, flip and compose is total. A saturated call of I, K or flip consumes that combinator’s occurrence, and compose consumes its occurrence to build one composite that is consumed when it is called; no call copies a subterm. So there are at most twice as many saturated calls as combinator occurrences in the program, each makes at most three further calls of apply\mathrm{apply}, every other call comes from an application written in the program, and so evaluation stops. The fragment with iteration is not total, as Ω\Omega shows.) Can a cost model for metering be stated that every replica computes the same way?