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
with application written by juxtaposition and associating to the left. The identity is not primitive, because , so .
Combinatory completeness. For every term built from variables, and , and every variable , there is a term that does not contain and satisfies for every .
Proof sketch. Define by bracket abstraction: ; if does not occur in ; . Each clause is checked by direct reduction. For the third, , which equals 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 and to keep it smaller.
Two programming ideas follow from this. Currying treats a function of arguments as a function of one argument that returns a function of 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 , which makes ["filter", ["gt", 2], xs] mean “keep the elements greater than 2”.
Reduction trace
Reduction rules
Let be the library: a finite map from names to pairs of an arity and a host function. Values are JSON values plus closures with , meaning is waiting for more arguments. The one-element array of a library name evaluates to the empty closure ; the bare string is data.
Application. For a closure and argument values , let (concatenation).
- If , then (partial application).
- Otherwise let . If , the result is . If there are arguments left over, the result is (over-application), and it is an error if is not a closure.
Every call of , 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. 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 xEvaluation 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 , an argument list and a non-empty argument list , , whenever both sides finish within the budget. Consequently, if is a closure, then for ; for both sides are that closure.
Proof. Let . If , the left side is , which concatenates to the same as the right side. Otherwise both sides compute the same from the first arguments. The left side then gives with leftover , and the right side gives . These are equal by induction on the total number of arguments (if is not a closure, both sides fail with the same error). If is empty, both sides are , because is non-empty. The condition is needed: with , and 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]. takes and "ignored" and returns , and the leftover 42 goes to , so the result is 42. That is . 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 ) and compose. compose is a slightly uncurried . compose(f, g) has arity , where is the number of arguments already holds, and it passes all of its arguments to . So compose(neg, add) applied to 2 and 3 gives . There is no .
The B, C, K, I fragment cannot duplicate. Let be any term built from by application. Then every reduct of contains each variable at most once. In particular, and cannot be expressed.
Proof. The right-hand sides , , and 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 occurs once.
These are the affine combinators of substructural logic: they allow weakening ( discards) and exchange ( 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 . Once duplication is available, so is self-application. reduce(I, I, [x, x]) computes , because I over-applied to the accumulator and an element applies one to the other. So with , the program is the classic . 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 . 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, , which passes without evaluating it. (Writing the program would also evaluate .) 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 is a deterministic function of its arguments, then is determined by and : the same value, the same error, or budget exhaustion.
Proof sketch. Every clause of and 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, , so that replicas agree when they start from the same 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 is
true. For example,["compose", ["gt", 17], ["prop", "age"]]accepts a document whoseageis 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, visits each node of the program once, so the cost is 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
flipandcompose. Thedupterm 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 , so every variable used more than once would have to be compiled through an iterating primitive, as indup, and the compiled terms can be much larger than the source. - Equality.
eqcompares serializations, so it agrees with equality of JSON values only when the serialization orders object keys canonically. The model reads programs through Lean’sJsontype, 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. is a closed finite map. A head names a function only if it is one of the 18 names in
arity?, which is a closedmatch, 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,flipandcomposeis total. A saturated call ofI,Korflipconsumes that combinator’s occurrence, andcomposeconsumes 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 , every other call comes from an application written in the program, and so evaluation stops. The fragment with iteration is not total, as shows.) Can a cost model for metering be stated that every replica computes the same way?