Formalizing Lazy Evaluation in Les with Lean — From Observation to an Executable Model, and on to Proofs
I have started an experiment: observe the implementation of a small programming language, model its behavior in Lean, and prove properties of that model. The subject is Les, a scripting language that usa (unak on GitHub
I have started an experiment: observe the implementation of a small programming language, model its behavior in Lean, and prove properties of that model.
The subject is Les, a scripting language that usa (unak on GitHub and elsewhere) is implementing in Go.
The experiment lives in the repository gotoken/les-spec.
The aim here is not to port the evaluator written in Go to another language. I run Les programs, observe their behavior, and consult the Go code when necessary to infer a conceptual model that explains that behavior: what information the evaluator keeps and what rules govern its computation. I describe that model in Lean, a language in which we can both write programs and have mathematical proofs checked.
The goal is not merely to check that individual programs behave as expected, but to express properties of the model as mathematical propositions and prove that they hold in every case satisfying their hypotheses. There can be infinitely many inputs and intermediate execution states, so this is a different task from testing.
In normal execution, the Les CLI first performs lexical analysis and parsing to construct an abstract syntax tree (AST), then performs type inference and checking, and finally runs the program with the Go evaluator. This formalization focuses primarily on that last stage.
The Lean evaluator therefore does not receive the Les source code directly. A tool called lesdump reuses the Go implementation's lexer, parser, and type inference to produce a JSON representation of the AST and type analysis results. Lean reads and evaluates that representation. The original Go CLI's execution results are collected separately for comparison.
As of November 15, 2026, I have an executable Lean evaluator for part of Les and have confirmed that it agrees with the Go implementation on what can be observed for 35 programs. I have also proved internal properties of the model in Lean, including that a delayed computation which finishes successfully has its result stored, and that requesting the value again from the same storage location does not repeat the computation. I also constructed a concrete example satisfying the theorem's hypotheses.
I have not formalized all of Les. Nor have I proved that the Go implementation and the Lean model are mathematically equivalent. Inferring a specification from observations, running the model and comparing it against the original implementation, and proving properties of the model itself are separate tasks.
This post sets out what I built, how I went about it, what I learned, and where I want to go next.
1. What kind of language is Les?
Les (Lazy Evaluation Script) is a scripting language implemented in Go, with an indentation-based syntax similar to Python's.
It offers Ruby-like concise notation, a type system influenced by Go, type inference, structural interfaces, and more.
Its most distinctive feature is that variables, function arguments, and so on are, as a rule, evaluated only when needed.
Consider the following program.
def choose(first: Int, second: Int): Int:
first
print choose(42, 1 / 0)
This program prints 42.
Under ordinary eager evaluation (call-by-value), 1 / 0 would be evaluated before the call and you would get a division by zero. Les never evaluates the unused second argument, so there is no error.
Les also provides force and a postfix ! to request evaluation explicitly.
You can try Les without installing it locally: the Les Playground lets you run examples in your browser and edit the code to experiment on your own.
Lazy evaluation itself has been studied and implemented in many programming languages, including Haskell and R. What makes Les interesting is that, on top of lazy evaluation, its rebinding and environment capture behave in distinctive ways.
Variables that exist at creation time are captured
a = 1
b = a + 1
a = 10
print b
The result is 2.
The right-hand side of b is not evaluated right away. But b captures the binding of a that was visible when b was created, so rebinding a afterwards does not change what b refers to.
Variables that do not exist at creation time are found later
The following program, on the other hand, behaves differently.
b: Int = a + 1
a = 5
a = 7
print b
The result is 8.
When b is created, a does not exist yet, so a is not captured. When b is actually evaluated, a is looked up in the live scope, and the binding found then, 7, is used.
In other words, two things coexist in Les's lazy evaluation:
- A name that can be resolved when the thunk is created captures the binding of that moment.
- A name that cannot be resolved at creation time is resolved later, at evaluation time.
Neither plain call-by-name nor the usual account of call-by-need with static scoping fully captures this.
Furthermore, in Les, rebinding an existing name in the same scope forces the right-hand side on the spot. Initial binding and rebinding are evaluated at different times.
The starting point of this formalization was to build a model that explains these rules not just one by one, but consistently even when they are combined.
2. What the experiment set out to do
From the start, I had no intention of writing a specification of all of Les or of porting the entire Go implementation to Lean.
Instead, I set three separate goals.
The first is to record observable behavior.
For a given Les program, pin down what its standard output, standard error, and exit code are.
The second is a small executable model that explains that behavior.
For example, in the two programs from Section 1, a is rebound later, yet the value that b refers to is determined differently. Explaining that difference requires more than a mapping from variable names to values: we need to work out when references are resolved and what gets stored. I build rules and a representation of state that explain the observed cases consistently, and make them executable in Lean. This is the model of the language's semantics (the rules defining what programs mean and how they compute) used here. There is no need to copy Go's internal structures, but differential testing helps check that the model does not contradict observations.
The third is to prove properties of the model.
What does it mean to prove a general property?
Consider a simple mathematical example. We want to establish that n + 1 > n for a natural number n. Substituting n = 0, 1, 2, ... gives us as many successful examples as we want. But there are infinitely many natural numbers, so no finite series of tests can exhaust them. A mathematical proof can instead explain why the inequality holds for an arbitrary natural number n, covering values that have never been tried.
What we want to know about this evaluator is similar. Suppose a delayed expression is evaluated and its result is stored, and we then ask for its value again. Running several programs and observing that the same value comes back is testing. But the combinations of expressions, variable bindings, storage locations, and intermediate execution states are vast and can be infinite in the model.
In the theorem introduced in Section 4, instead of picking a particular expression or value, we treat them as arbitrary. Under the hypotheses that an unevaluated expression is stored in a given location and that its evaluation finishes successfully, we show that its result is stored in that location, and that requesting the value of the same location again from the resulting state returns the same value without changing the execution state. Lean checks not only the statement but also the mathematical proof that establishes it.
General means that the theorem covers every case in its stated domain that satisfies its hypotheses, not just the programs we have tried. It does not establish that every Les program evaluates successfully, or that the value always stays the same if arbitrary other operations intervene.
The distinction between testing and proving is also explained very clearly in the introduction to Sam Xifaras's ruby-lean post, which I discovered after finishing P2 (see Section 9 for a comparison).
These are three separate tasks. Agreement with observations supports the model's adequacy, but does not prove equivalence to the Go implementation. Nor is a theorem about the model automatically a theorem about the original Go implementation.
3. P0–P1: From observation to a Lean evaluator
P0: Pin down the target and make it reproducible
First I pinned the target commit of Les:
aa78fdcfc76b156e6b5ab4735516fcefadce954b
I built the Go CLI from this commit and ran a minimal set of tests. At the same time I set up a build environment with Lean 4.25.0 and Lake.
The reason for pinning a commit is to keep changes in the upstream implementation during the experiment from silently changing the observed results or the subject of the proofs.
The first five tests checked print, exit, lazy evaluation of unused arguments, division by zero, and the like.
Something that turned out to matter more than I expected: the Go CLI and Go's evaluator tests do not take the same path. At the pinned commit, the CLI's runPipeline separates normal execution into three stages.
-
Lexical analysis and parsing (
ParseProgramon the parser): read the source and construct an AST. Syntax errors stop the pipeline here. -
Type inference and checking (
InferProgram): infer types and check their consistency. Type errors stop the pipeline, and type warnings are written to standard error. -
Evaluation (
EvalProgram): use the parsed AST and the type inferencer to evaluate expressions as they are needed.
Indeed, the CLI's -c option stops after the first stage and -t after the second; neither evaluates the program. Lazy evaluation concerns the computation in the third stage, not postponing parsing or type checking.
The CLI's standard error can therefore contain not only runtime errors from the evaluator but also warnings from type inference before execution. I arranged the test inputs and expected values so as not to confuse these two kinds of behavior.
P1: What was observed with the Go CLI, and what lesdump passes on
Two jobs need to be kept apart here.
-
Observing execution results: give
*.lesto the Les CLI built in Go from the pinned commit, examine stdout, stderr, and the exit code, and pin them down in*.expect.json. -
Building the input for Lean:
lesdump, which reuses the lexer, parser, and type analysis of the Go version, emits the abstract syntax tree (AST) and type analysis results for the same*.lesas JSON. Lean decodes that JSON and computes using its own evaluation rules.
An AST represents a + 1, for example, as a tree consisting of an addition operation, the variable name a on the left, and the integer literal 1 on the right. Neither the actual value of a nor the result of the addition is determined when this AST is constructed.
In other words, lesdump is not an oracle that collects execution results but a bridge for sharing the front end (the analysis performed before evaluation). For the supported sublanguage, it reuses the Go CLI's lexical analysis, parsing, and type inference routines, but does not invoke the Go evaluator. The Lean side does not independently verify the correctness of parsing or type inference either; it receives the JSON and performs evaluation.
In the actual directory layout, for example, the correspondence looks like this.
The actual commands are as follows.
bash scripts/bootstrap.sh
.work/bin/lesdump difftest/corpus/snapshot-late-rebind.les > /tmp/snapshot.json
python3 difftest/run.py # check the pinned Go CLI against *.expect.json
python3 lesdump/test.py # check the AST JSON against the golden files
cd lean
lake build
lake exe les-syntax-test ../lesdump/golden 35
lake exe les-eval-test ../lesdump/golden ../difftest/corpus
The code that collects Go's stdout, stderr, and exit code is in difftest/run.py. Apart from replacing environment-specific file paths with <CASE>, it never automatically updates the expected values to whatever came out. lesdump/test.py also checks that the lesdump JSON is deterministic and that unsupported syntax is explicitly rejected.
Terms first: Thunk, Cell, Heap, Scope, Env, Machine
From here on, more and more terms describing the internal structure of the evaluator appear that do not occur in Les source code. For readers new to them, let me first sort out where they come from.
A thunk, a term from research on lazy evaluation, is a way of holding an expression that has not been computed yet as "something to compute when it is needed." It is not just the stored expression: it also needs the environment in which to evaluate that expression later. The strategy of storing the result and reusing it the second time is called call-by-need.
The Thunk of the original Go implementation really does have the fields Expr, Env *Environment, Value, Evaluated, and Evaluating. Environment holds store map[string]Value and parent, and captureEnv copies the bindings that were visible at creation time.
On the other hand, Cell, Machine, and the others below are representations and names chosen for the Lean evaluator in this experiment. They are not one-to-one ports of Go's structs.
| Term | What it refers to | Origin / how it is used here |
|---|---|---|
| Thunk | An unevaluated expression plus the information needed to evaluate it later | A common term in lazy evaluation. Go's Les also calls it Thunk
|
| Cell | A single storage location holding an evaluated value, an unevaluated expression, or a marker meaning "being evaluated" |
Cell in the Lean model. It holds not only thunks but also evaluated values |
| Heap | The storage area that manages cells by address, plus the list of scopes |
Heap in the Lean model. Not the operating system's heap |
| Scope | The mapping from current variable names to cell addresses, plus the parent scope | Scope in the usual language-implementation sense. In Lean it is referred to by ScopeId
|
| Env | The reference environment that says where names are resolved when the expression is evaluated later | Short for environment. The problem that Go's Environment handles is split into snap and scope in Lean |
| Machine | The state that changes during evaluation, bundled together | In the sense of an abstract machine or evaluator state. Here, the Heap and the accumulated stdout. Not a physical computer |
Whereas Go's Environment holds references to values and thunks, Lean maps variable names to cell addresses (array indices). This indirection is what lets an old thunk keep using its original cell even after rebinding changes where a name points.
With the terms in place, let's run actual programs and see which addresses remain.
Observation 1: capturing a binding (E14)
snapshot-late-rebind.les, shown at the start, is these four lines.
a = 1
b = a + 1
a = 10
print b
The expected result from the pinned Go CLI is recorded like this in snapshot-late-rebind.expect.json.
{"stdout": "2", "stderr": "", "exit_code": 0, "rules": ["E14"]}
In the golden JSON from lesdump, the second statement b = a + 1 is a VarDecl whose right-hand side is a Binary. Here is that statement alone (equivalent to jq '.body[1]').
{
"kind": "VarDecl",
"name": "b",
"pos": {"col": 1, "line": 2},
"type_annot": "",
"value": {
"kind": "Binary",
"left": {"kind": "Ident", "name": "a", "pos": {"col": 5, "line": 2}},
"op": "+",
"pos": {"col": 7, "line": 2},
"right": {"kind": "Int", "pos": {"col": 9, "line": 2}, "value": 1}
}
}
The important point is that this JSON contains no evaluation results such as "a is 1" or "b is 2". It only represents VarDecl, Binary, Ident, and source positions. The type checker's analysis.status is ok in this case, but that too was not obtained by running anything.
The output is 2 because, when the thunk for b is created, it captures not the value of a but its cell address, and keeps referring to the old cell even after the rebinding a = 10. The Lean evaluator implements this rule, and the proofs in P2c guarantee part of this reference structure.
Translated into Lean's storage, the state just before print b looks conceptually like this. Cells #0 and #1 are for built-in functions, so in this example the first cell of a is #2. The numbers the arrows point to are not values but addresses in the cell array.
Line 1, a = 1, creates #2; line 2, b = a + 1, creates #3; and the rebinding on line 3, a = 10, creates #4. The name a in Heap.scopes[1] now points to #4, but the env_b.snap stored in #3 still points to #2. So evaluating b computes 1 + 1.
This is not a picture of Go's internal memory addresses. It is a picture of the Lean Heap model built to explain Go's output. The real Go implementation uses pointers and Environment; Lean uses integer addresses and arrays.
Observation 2: resolving a not-yet-bound name later (E15)
By contrast, forward-ref-rebound.les is:
b: Int = a + 1
a = 5
a = 7
print b
The expected result is {"stdout": "8", "stderr": "", "exit_code": 0} in forward-ref-rebound.expect.json.
The shape of the AST is almost the same as before: the right-hand side of b is again Binary(Ident("a"), "+", Int(1)). But when b is created, there is no binding for a. So a does not go into the snapshot, and when print b first demands its value, the latest a = 7 in the current scope is found.
This is the semantics of runtime environment capture and name resolution, which you cannot see just by building the AST. The fact that two examples with the same Binary AST return 2 and 8 is what motivated having a Heap and Env in Lean.
Here, when the thunk for b is created, a does not exist yet, so env_b.snap is empty. At evaluation time, the current binding is looked up by following env_b.scope = 1.
The difference between the earlier 2 and this 8 is not a difference in syntax such as Binary, but whether the same name a is resolved from Env.snap or looked up later in the live Scope.
Observation 3: results of lazy evaluation are shared (E9)
memo-binding.les, which checks memoization, is the following program.
def g(): Int:
print "side;"
1
x = g()
print "before;"
print x
print x
The expected value from the pinned Go CLI is:
{"stdout": "before;side;11", "stderr": "", "exit_code": 0, "rules": ["E9"]}
g is not called when x = g() is declared; it is evaluated exactly once, at the first print x. The second print x reuses the shared result. That is why side; appears only once. On the lesdump side, g is output as a FuncDef and x = g() as a VarDecl whose right-hand side is a Call; the JSON says nothing about how many times anything is evaluated or how many side effects occur.
In addition, for the failure case blackhole.les,
x: Int = x + 1
print "ok"
print x
the result is stdout ok, exit code 1, and stderr Runtime Error: blackhole: circular reference detected in lazy thunk (with a trailing newline). Cell.blackhole, introduced later in Lean, is the state that explains this observation.
What the Lean side compares
The Lean decoder turns lesdump's {"kind":"Binary",…} into Expr.binary and {"kind":"VarDecl",…} into Stmt.varDecl. Only a Program that passed type checking becomes a CheckedProgram and is run. This does not mean, however, that Lean has proved Go's type inference correct.
The comparison in lean/Tests/Eval.lean (comments in Japanese), reduced to its essentials, looks like this.
def verdictOf (fuel : Nat) (src : String) : Except String Verdict := do
return (run fuel (← progOf src)).verdict
For each case, the test reads lesdump/golden/*.json and difftest/corpus/*.expect.json and compares the stdout, stderr, and exitCode returned by verdictOf with the expected values.
UNSUPPORTED and OUT_OF_FUEL are not counted as agreement. All 35 current cases are PASS. Lean's syntax tests check decoding and re-encoding of the 35 JSON files, and 41 unit tests check evaluation on ASTs built directly.
For example, the unit tests check not only that demanding three times produces the side effect once, but also, using the Heap taken out of runMachine, that the shared cell really was rewritten to .done after evaluation. They also compare cell addresses to check that b's Env.snap points to the a from before the rebinding.
These are "observation and execution tests." In P2, next, I prove properties of the corresponding Lean evaluator that do not depend on a finite set of tests.
4. P2: What exactly was proved in Lean
The 35 cases in P1 check agreement of observed results such as stdout. In P2, for the same Lean evaluator used in that comparison, I built theorems of the form "from any initial state, if these conditions hold, the result is always this."
The centerpiece is whnf_suspended_ok_memo in lean/Les/Proofs/Memo.lean (comments in Japanese). whnf stands for weak head normal form, a term used in lazy evaluation in functional languages. In this model it is the name of "the process that forces a given cell until its value is known." whnf is neither a Lean built-in nor Les syntax; it is a function defined in this Lean evaluator. To read what the theorem says concretely, let's first look at the Machine and the Cell.
4.1 The evaluator's data types: sharing addresses, not names
Here is a diagram of which Lean data types the terms above correspond to.
A Machine is not "an object holding the whole program"; it bundles only the parts that are updated during evaluation. The expression Expr to run, its environment Env, and the fuel that bounds the recursion depth are arguments of functions such as evalE, demand, and whnf. Machine.stdout keeps what print outputs as a string instead of actually writing to a terminal. That is why the output up to an exception can still be compared.
The following is an excerpt from the actual lean/Les/Eval/Types.lean (comments in Japanese).
abbrev Addr := Nat
abbrev ScopeId := Nat
structure Env where
snap : List (String × Addr)
scope : ScopeId
inductive Cell where
| done (v : Value)
| suspended (e : Expr) (env : Env)
| blackhole (e : Expr)
structure Scope where
vars : List (String × Addr)
parent : Option ScopeId
structure Heap where
cells : Array Cell
scopes : Array Scope
structure Machine where
heap : Heap
stdout : String
abbrev EvalM := ExceptT Halt (StateM Machine)
Heap.cells is an array of cells, and an Addr is an index into it. A scope's variables do not hold values directly; they hold cell addresses.
Env.snap is the list of names that could be resolved when the thunk was created, paired with their addresses, and Env.scope is the number of the live scope in which names not yet captured are looked up. Scope.vars holds the current mapping from names to addresses, and Scope.parent refers to the parent scope. The division of labor is that Env records "where an expression is evaluated from," and Scope holds "which name is tied to which cell right now."
EvalM is not a standard Lean type either; it is an alias defined by this evaluator. It represents a computation that reads and writes the Machine state and may stop partway because of an error or exit. StateM Machine handles the execution state, and ExceptT Halt handles normal completion (Except.ok) and the reason for stopping (Except.error).
The three states of Cell exist to implement the following transitions.
evalE, whnf, demand: expressions, addresses, and values
This matters when reading the Lean code. The evaluator has three functions with similar-sounding names.
| Function | Meaning of the name and its role | From input to result |
|---|---|---|
evalE |
Short for evaluate expression. Processes an expression and returns the address of the cell that will hold the result. For an identifier it returns the existing cell and does not force it yet |
Expr → EvalM Addr (fuel and Env omitted) |
whnf |
Short for weak head normal form. Forces the given cell on demand and returns its value. If the cell is unevaluated, it runs the expression and, on success, memoizes it as done
|
Addr → EvalM Value |
demand |
From the English demand (to require a value). Passes the address obtained from evalE to whnf and requires the expression's value. On error it also attaches the expression's position |
Expr → EvalM Value |
For example, passing the right-hand side of b = a + 1 to evalE and passing it to demand give results of different types and force different amounts. When the variable b points to an unevaluated cell, the equivalent of evalE (Ident "b") returns that address, and whnf evaluates the expression behind the address and returns a value.
As a general lazy-evaluation term, WHNF is the state reached by evaluating not the whole expression to full normal form, but only far enough to tell what the outermost value is. For a lazy list, for example, once you know whether the outermost constructor is the empty list or cons, the list is in WHNF even if its elements and tail are unevaluated. This is only the general explanation, though; the current Lean model of Les does not implement lists. Here, whnf is a function that turns a cell into a Value, not "full normalization" that recursively evaluates every nested computation.
These functions actually also take fuel : Nat as their first argument. Fuel is a limit on recursion given as a natural number; when it reaches zero the result is outOfFuel. It does not count the number of instructions or the amount of computation of the whole run.
At the heart of these transitions is whnf in lean/Les/Eval/Eval.lean (comments in Japanese). Here is the actual definition.
def whnf : Nat → Addr → EvalM Value
| 0, _ => throw .outOfFuel
| n + 1, a => do
match (← getHeap).cell? a with
| none => throw (.error "internal: dangling address" .absent)
| some (.done v) => pure v
| some (.blackhole _) =>
throw (.error "blackhole: circular reference detected in lazy thunk" .absent)
| some (.suspended e env) => do
modHeap (·.setCell a (.blackhole e))
let v ← demand n e env
modHeap (·.setCell a (.done v))
pure v
demand evaluates an expression and then forces the resulting cell with whnf. Because EvalM is layered as ExceptT Halt (StateM Machine), the stdout and Heap written before an error survive even if an error occurs partway.
In memo-binding.les above, the reason the first print x produces the side effect and the second does not is expressed in this model as the cell at the same address changing from suspended to done.
4.2 P2a: Local operations on the Heap
For this model, I first studied alloc, setCell, and bind in Proofs/Heap.lean (comments in Japanese). For example, here is an actual lemma.
theorem Heap.alloc_cell?_new (h : Heap) (c : Cell) :
(h.alloc c).1.cell? (h.alloc c).2 = some c := by
simp [Heap.alloc, Heap.cell?]
It is a property that seems obvious: "when you allocate a new cell, the returned address holds that cell." But once it is established as a lemma, later proofs that change the state can cite it.
Conversely, Heap.bind can register any address, so not every Heap is automatically well-formed. Making the needed assumptions explicit led to the work in P2d.
4.3 P2c: Proving the difference between 2 and 8 with addresses
In P1, snapshot-late-rebind.les gave 2 and forward-ref-rebound.les gave 8. What produces the difference is name resolution and environment capture in Eval.lean (comments in Japanese).
def lookupEnv (heap : Heap) (env : Env) (n : String) : Option Addr :=
match env.snap.find? (·.1 == n) with
| some (_, a) => some a
| none => heap.lookup env.scope n
def capture (e : Expr) (env : Env) : EvalM Env := do
let heap ← getHeap
let names := (exprNames e).eraseDups
let snap := names.filterMap fun n => (lookupEnv heap env n).map (n, ·)
return { snap, scope := env.scope }
For the identifiers that occur in an expression, capture puts only the ones that can be resolved into snap. Unbound names are left out.
capture_preserves_under_bind in Proofs/Capture.lean (comments in Japanese) shows that, for a captured name, a later Heap.bind still returns the same address, and that rebinding operation does not change the contents of the original cell. capture_unbound_lookup and forward_ref_rebound show, under conditions, that looking up a name that was not captured can see a later rebinding.
So the name-resolution pieces that correspond to the observed 2 and 8 are proved in Lean. These lemmas alone, however, do not amount to a whole-program theorem such as "running this Les source always yields 2."
4.4 P2d: From never removing a cell to keeping the original address
What the first force needs is that the original thunk's address is still valid after demand finishes.
Here I proved a property that may look like a detour.
The definitions in Proofs/Monotone.lean (comments in Japanese) are as follows.
def Machine.CellsMono (m m' : Machine) : Prop :=
m.heap.cells.size ≤ m'.heap.cells.size
def Mono {α : Type} (x : EvalM α) : Prop :=
∀ m : Machine, m.CellsMono ((x.run).run m).2
Mono is the name of a proposition defined here, taken from the mathematical term monotone. It is not a built-in Lean verification command. Mono x means that from any starting Machine, running x never leaves the final Machine's cell array shorter. This covers runs that end in an exception, not only successful ones. It is not a theorem about every intermediate state.
The following theorem in Proofs/MonotoneEval.lean (comments in Japanese) shows this for the actual mutually recursive evaluator.
theorem demand_mono (fuel : Nat) (e : Expr) (env : Env) :
Mono (demand fuel e env) :=
(monoAt fuel).2.2.1 e env
monoAt is a proposition that bundles Mono for the 11 mutually recursive functions, including evalE, whnf, demand, function calls, argument preparation, and statement execution. It is proved by induction on fuel.
If no cell is removed from the array, an index that was valid at the start is still valid at the end. From this I derived demand_validAddr and removed hvalid (the assumption that the address is still valid after execution), which had previously been needed separately.
The important point here is that the array length not decreasing does not mean the contents of each cell stay the same. Updating suspended to blackhole or done is allowed.
4.5 The final theorem: whnf_suspended_ok_memo (P2d-5)
Putting all of this together gives whnf_suspended_ok_memo in Memo.lean (comments in Japanese). Below is the actual statement and the full proof.
theorem whnf_suspended_ok_memo (n : Nat) (a : Addr) (e : Expr) (env : Env) (m m₂ : Machine)
(v : Value) (h : m.heap.cell? a = some (.suspended e env))
(hd : ((demand n e env).run).run (m.blackholed a e) = (Except.ok v, m₂)) :
((whnf (n + 1) a).run).run m =
(Except.ok v, { m₂ with heap := m₂.heap.setCell a (.done v) }) ∧
({ m₂ with heap := m₂.heap.setCell a (.done v) }).heap.cell? a = some (.done v) ∧
∀ k, ((whnf (k + 1) a).run).run { m₂ with heap := m₂.heap.setCell a (.done v) } =
(Except.ok v, { m₂ with heap := m₂.heap.setCell a (.done v) }) := by
have h1 := whnf_suspended_ok n a e env m m₂ v h hd
have h2 := whnf_suspended_ok_cell_valid n a e env m m₂ _ v h hd h1
exact ⟨h1, h2, fun k => whnf_done k a v _ h2⟩
Lean notation for reading the statement
In the theorem, ((demand n e env).run).run m is an expression that runs demand from the execution state m and yields a pair of the result and the state after execution. run appears twice because EvalM consists of two layers, ExceptT and StateM, and each has to be unwrapped. Distinguishing the value from the state, the type of the result is roughly:
Except Halt Value × Machine
Except.ok v means it finished normally with value v; Except.error h means it stopped for reason h. Since the Machine remains as the second component of the pair, as in (result, m₂), the Heap and stdout can be inspected even after an error.
To read the Lean theorem, it is enough to know just the following notation.
| Notation | How to read it in this theorem |
|---|---|
theorem name (args) : proposition := by ... |
Declares a proposition and proves it after by
|
h : ..., hd : ...
|
Names given to hypotheses. It does not declare them to hold unconditionally |
∧ |
"and." Here there are three conclusions |
∀ k |
"for every natural number k" |
{ m₂ with heap := ... } |
Machine m₂ with only its heap field updated |
h1, h2, exact
|
Combine lemmas already proved and hand over the required conclusion |
run.run and ∀ are Lean notation. By contrast, whnf, demand, and Mono are names defined by les-spec, the subject of this post. Keeping the two apart makes the theorem easier to follow.
If you are not used to Lean notation, it is easier to read the theorem as two hypotheses and three conclusions.
Hypotheses
-
h: in the initial Machinem, addressaholds the unevaluated expressionewith environmentenv. -
hd: runningdemand n e envfrom the state in which that cell has been made ablackholefinishes normally, returning the valuevand leaving the Machinem₂.
Let m₃ be "the Machine m₂ with the cell at address a rewritten to done v."
Conclusions
- The first
whnf (n+1) areturnsok v, and the final state ism₃. - Address
ainm₃really does holddone v. - Every later
whnf (k+1) areturnsok vfor anyk : Natand leavesm₃unchanged.
This is a general, cell-level property behind the observation in memo-binding.les that "g() runs on the first demand, and demanding the same x later does not repeat the side effect."
The second conclusion matters in particular. It guarantees not merely that "forcing returned the same value," but that the memoized value stays at the shared address. The third is an equation about the whole Machine, so re-forcing does not change stdout either.
Note, however, that the theorem assumes hd, that is, that demand finishes normally. It does not cover memoization on failure, such as a self-referential blackhole or division by zero. Nor does this single theorem guarantee that every reference to x from an arbitrary Les program points to the same cell. That part is checked by the evaluator's implementation and by individual sharing tests.
4.6 An example that satisfies the theorem's hypotheses, also built in Lean
Putting a condition like hd in a theorem leaves a nagging question: "Is this a condition that nothing ever actually satisfies?"
So in Proofs/NonVacuity.lean (comments in Japanese), I prepared a concrete example in which one unevaluated cell is allocated in Heap.initial, the one the real evaluator uses.
def memoWitnessExpr : Expr := .int { line := 1, col := 1 } 42
def memoWitnessEnv : Env := { snap := [], scope := globalScope }
def memoWitnessCell : Cell := .suspended memoWitnessExpr memoWitnessEnv
def memoWitnessMachine : Machine :=
{ heap := (Heap.initial.alloc memoWitnessCell).1, stdout := "" }
def memoWitnessAddr : Addr := (Heap.initial.alloc memoWitnessCell).2
The proof memoWitness_suspended shows that the cell at that address is unevaluated. memoWitness_demand_ok shows that running demand 2 from the state in which that cell is a blackhole gives ok (.int 42). memoWitness_structWF shows that the initial Heap satisfies the structural well-formedness defined earlier.
Using these three, whnf_suspended_ok_memo_nonvacuous proves that there is at least one Machine, expression, and environment for which both hypotheses of whnf_suspended_ok_memo hold at once. memoWitness_integrated is an example that applies the integrated theorem there and derives its three conclusions.
So the relationships are as follows.
The tests and proofs in the diagram target the same Lean evaluator, but they are not logically the same claim. The theorem was not derived from the 35 agreements with Go, and the correctness of the whole Go implementation was not derived from the Lean theorem.
4.7 How it was verified
The theorems are also checked with #print axioms. In the CI for PR #22, after the fix, lake build with Lean 4.25.0 succeeded, the only axioms whnf_suspended_ok_memo_nonvacuous and memoWitness_integrated depend on are propext and Quot.sound, and there was no sorryAx. All 35 corpus comparisons were also PASS.
In fact, the first implementation of non-vacuity tried to prove memoWitness_demand_ok simply with rfl, and compilation failed. After confirming that evaluating an integer literal allocates a done cell, I changed it to a lemma, demand_int_ok, that proves success using whnf_done.
That failure included, I learned that making the execution results agree and producing proofs the Lean kernel accepts are separate jobs. There is now a GitHub Actions workflow that runs the Lean build and the evaluator's corpus tests at the PR stage.
5. What Lean bought me
What came out of this experiment is more than a reimplementation in another language.
First, I could make the semantic preconditions explicit.
For example, Heap.bind accepts even an invalid cell address as an argument. So you cannot say that Heap well-formedness is preserved unconditionally.
Working through the proofs made clear which operation needs which condition. I also recorded a counterexample in which binding an invalid address actually breaks well-formedness.
Next, I could separate concrete test results from general properties.
"Running this program gives the same value" is a test.
"For every Machine, forcing an evaluated cell again changes neither the value nor the state" is a theorem.
The Lean proofs here are of the latter kind. For the Lean model in question, they cover every state that satisfies the theorem's hypotheses.
One more: the formalization itself can proceed in small steps.
I did not need to design a complete semantics of the whole language from the start. Observing, preparing the data types I needed, building a small evaluator, and growing the set of properties I could prove about it was enough to build up results.
6. How the work was actually done
In this project, I have AI assist with implementation and proofs.
Claude Sonnet 5.5 did most of the implementation and the Lean proof work, and I used a different model for carving up the specification, design, and pull request reviews. On GitHub I also used reviews by Codex.
What I emphasized was not finishing everything at once with long instructions, but keeping units of work small and giving each one a stopping condition.
The basic cycle is as follows.
- Observe with the Go CLI and record the expected values and their basis.
- Look into the Go implementation only when needed, and design the Lean model.
- Implement one feature, or one set of theorems.
- Run
lake build, the differential tests, and the unit tests. - Record which properties were proved and which were not.
- Open a PR and move on after review.
I also set a policy of consulting a more expensive model only when stuck on interpreting difficult semantics. In the later stages so far, I have not needed semantics-opus, which is set up for that.
I have not measured the models' token usage well enough, however, so I cannot yet conclude that this approach is cheaper than manual development or a different AI setup.
What I could confirm is that, with AI assistance, proofs checked by the Lean compiler can be built step by step.
7. What has not been proved yet
The results so far have clear limits.
First, I have not proved the equivalence of the whole Go implementation of Les and the Lean model.
That the Go CLI and Lean agree on observed results for 35 cases, and that some properties of the Lean model are proved, are separate facts.
Second, not all of Les's features are covered.
The Lean model currently handles a small sublanguage made of 9 kinds of syntax nodes. The original Les's structs, pattern matching, complex type system, and so on are out of scope.
Third, type safety is not proved.
The current Lean evaluator takes as input a CheckedProgram, which says that type checking on the Go side succeeded. This does not mean that Lean independently proved the type checker correct.
Fourth, full Heap well-formedness is not proved yet either.
The basic reference structure of scopes is checked, but references held inside cells, such as addresses stored in a thunk's environment or scopes held by closures, are not covered.
I think leaving these unproved properties explicitly stated is also an important part of this experiment.
8. Where to go from here
For now, I am thinking of the following order.
Near term: settle the P2 results as a reference point
A successful first force, monotonicity of the number of cells, memoization, and the stability of re-forcing are integrated into whnf_suspended_ok_memo in P2d-5. I also prepared a concrete witness, and the list of proof coverage records the differences between observation, execution checks, and theorems.
Next, I will look at the parts that can still only be handled conditionally, such as the Heap and blackhole state left after a failed demand, and well-formedness that includes references inside cells. I will not try to prove everything while adding new features, though; I will pick the invariants that are needed and proceed.
Medium term: widen the language features covered
In P3, I am considering adding Les features one at a time, such as if, Tuple, Dict, and pattern matching. The order is not fixed; I will choose by looking at how observable each one is in the Go implementation and how it affects the existing proofs.
Each time a feature is added, I will repeat the cycle: observe in Go, sort out the semantics, implement in Lean, and prove the needed properties.
Rather than porting the whole language at once, I want to keep a working result at every stage.
Long term: strengthen the relationship between the implementation and the formal model
Further out, I would like to be able to explain the relationship between the Go implementation and the Lean model more strongly than the current finite set of differential tests does.
That will probably require making the scope of the target sublanguage clear, and then more exhaustive test generation and a closer look at the correspondence between implementation and specification.
Formally proving the semantic correctness of the Go implementation itself is an even bigger challenge.
Rather than making that the final goal right away, I will first aim for a state where observable specifications accumulate and the Lean model serves as a checkable reference model.
9. ruby-lean, which I learned about after finishing P2 — comparing notes with prior work
In November 2026, when I had brought the P2 proofs to a stopping point, I learned of “ruby-lean: A Ruby semantics with a type soundness proof”, published by Sam Xifaras on September 26 of the same year. A technical appendix and the source code are also available.
The post was published before I started this experiment, but I only learned about it after finishing P2. So the design and implementation of P0–P2 were not based on ruby-lean. What follows is an after-the-fact comparison of notes and a look at options for the future.
The same method, applied to a different language and different theorems
ruby-lean makes Ruby into a model executable in Lean 4, compares it with the real CRuby, and further proves a restricted typing judgment inspired by Sorbet and its soundness. les-spec, on the other hand, makes part of Les, written in Go, evaluable in Lean and proves things such as memoization of shared thunks, environment capture, and address validity.
| Aspect |
les-spec (at the end of P2) |
ruby-lean (as reported in September 2026) |
|---|---|---|
| Original implementation and focus | Les in Go. Focus on lazy evaluation, rebinding, capture, and forward references | CRuby. Also handles method calls, classes, dynamic modification, and more |
| Input to Lean | JSON AST from lesdump, which goes through Go's parser and type checker |
Desugaring of Ruby's surface syntax into a smaller core language |
| Evaluator | Fuel-bounded recursive functions evalE, whnf, demand. Machine holds the Heap and stdout |
A CESK abstract machine that makes control, environment, store, and continuation explicit and steps through transitions |
| Differential checks | Compares stdout, stderr, and exit code of 35 cases against the pinned Go CLI | Uses CRuby's bootstraptest, generated tests, and more. The technical appendix reports 995 of 1,309 bootstraptest cases conforming on semantics |
| Center of the proofs | Internal properties of the evaluator, such as memoization on a successful first force and the stability of re-forcing | That programs accepted by the type checker do not fall into the defined kinds of type-related errors |
The last row is not a ranking of the results. The properties each wants to prove are different. The ruby-lean result does not guarantee the soundness of all of Ruby or Sorbet, and the les-spec result does not guarantee general equivalence of Go and Lean.
Comparison 1: an executable semantics and conformance to the implementation are separate problems
The first thing confirmed was that the approach of separating Lean being able to check theorems from the Lean evaluator correctly modeling the original language is sound.
Xifaras reports that while ruby-lean passes a large set of differential tests, there is an unresolved discrepancy with CRuby around Ruby's implicit string conversion via to_str, and publishes a concrete example. Having theorems about a model does not by itself guarantee that the model represents all the behavior of the original implementation.
Likewise here, what whnf_suspended_ok_memo proves is the cell update on success and re-forcing by Lean's whnf. It does not prove that Go's Les behaves the same way on every input. In light of this prior work too, it matters that I did not call the 35 agreements "semantic equivalence."
In addition, the ruby-lean technical appendix distinguishes existing conformance tests (Tier 0), generated tests (Tier 1), tests that insert print in the middle to check the order in which side effects occur (Tier 1.5), and complex tests generated by AI (Tier 3). For Les as well, it looks feasible to add tests that distinguish the shared thunks of E9, the bindings of E14/E15, and the evaluation order of E17/E19 not just by final values but by where side effects appear.
Comparison 2: same Machine name, different evaluator structure
ruby-lean's evaluator uses CESK (control, environment, store, continuation). Its Machine contains ctl, which says what to execute next, and kont, a continuation stack holding the rest of the computation.
In contrast, les-spec's Machine holds a Heap and stdout. Which expression to evaluate next shows up as recursive calls to evalE, whnf, and demand; there is no explicit kont stack.
Also, the same name Heap refers in les-spec to an array of cells representing thunk states, while in ruby-lean it is centered on an array storing Ruby objects. The terms are similar, but the models do not correspond one to one.
These differences do not mean the current Les model must be rewritten as CESK right away. But if it is extended with return / break, exceptions, I/O, suspending and resuming evaluation, and so on, there is room to compare whether making continuations explicit makes the proofs easier. The technical appendix also mentions that lemmas about decomposing the continuation stack helped the proofs.
Comparison 3: not just more tests, but a way of working that keeps the proofs intact
Another thing in common was the policy of stacking up small completion conditions rather than having AI implement a large specification all at once.
Xifaras calls this a ratchet (a mechanism that only moves one way). In particular, when adding typing rules, the completion condition is not just that individual tests pass, but that the proof obligations of the added rule are met and the overall type soundness theorem still holds.
In les-spec too, observation, model, and proofs were split into small PRs. But as the failure of the first lake build of NonVacuity.lean for P2d-5's non-vacuity showed, splitting alone is not enough. After that, I added lake build and the existing corpus tests to GitHub Actions. This is where the prior work's method and my own experience of failure line up.
Additional plans worth considering
1. Grow the differential tests in more than one way. In addition to the 35 handwritten cases, I am considering generating Les programs that pass type checking, inserting observable side effects, and combining the existing examples of thunk sharing and environment capture. For this subject, which evaluation rules a test can distinguish is a better yardstick than the sheer number of tests. Agreement between Go and Lean on generated tests is still observation, not proof.
2. Keep the existing theorems intact while adding features in P3. When adding if, Tuple, Dict, and so on, the completion condition will include keeping the proofs of demand_mono, address validity, and memoization, in addition to agreement between the Go oracle and Lean. If an added evaluation rule needs a new precondition, its reason and scope will be stated explicitly. The idea is to apply the prior work's ratchet along two axes: the execution corpus and the proofs.
3. Consider whether translation to a core language is needed. ruby-lean translates surface Ruby syntax into a small core. As Les's supported syntax grows, translating to a small core might make the proofs shorter than adding each piece of surface syntax to Lean as is. On the other hand, it would then need to be verified that the desugaring itself does not change the behavior of the original program. There is no plan to replace the current lesdump right away.
4. For types, consider options other than "porting the whole inference engine." The current CheckedProgram trusts the success of Go's type checking. ruby-lean chose to have an untrusted generator produce candidate typing derivations and have a Lean checker verify them. That is an option for verifying Les's types in the future. But in Les, with lazy evaluation, rebinding, and forward references, I would first have to define which errors type safety is supposed to rule out. This is a long-term consideration, not work I have decided to add to the current P3.
Learning about the prior work after the fact did not mean redoing the P2 work. Rather, it let me check the direction of keeping implementation observation and formal proof separate against another practice. On the other hand, I think large undertakings such as CESK or a type soundness proof should be adopted or not once their purpose becomes necessary, not by transplanting the method as is.
This section is a comparison based on the main post, the technical appendix, and the published ruby-lean code. The additional plans above are candidates, not completed results.
10. Closing
Taking Les as the subject, I found that formalizing a language implementation can begin without first writing a huge specification.
Les is a relatively small implementation, yet it has semantically interesting elements: lazy evaluation, memoization, closures, environment capture, forward references, rebinding, and more.
In particular, the mechanism of capturing names that existed at creation time and resolving names that were unbound later was a good subject for thinking about what kind of environment model is needed.
And for the Lean model built from observations of the Go implementation, I was able to go as far as proving general properties.
This is still a result limited to a small sublanguage, but I plan to keep adding observations and proofs bit by bit from here.
Finally, my thanks to usa for publishing Les. And thank you for reading this post.
Related repositories
- unak/les — the Go language being formalized
- gotoken/les-spec — this experiment (most documents have English translations; discussion in issues and PRs is mostly in Japanese)
- Evaluator design notes — rules E1–E22 and their rationale
- Differential test corpus — the programs used for observation and their expected results
- Lean proofs — proofs about the Heap, memoization, environment capture, monotonicity, and more
Originally published by Dev.to AI. Aggregated on AIWithGhost for educational purposes — full credit and traffic to the original publisher.






