Les の遅延評価を Lean で形式化してみる — 観測から実行可能モデル、そして証明へ
英語版 Formalizing Lazy Evaluation in Les with Lean — From Observation to an Executable Model, and on to Proofs小さなプログラミング言語の実装を観察し、その振る舞いを Lean でモデル化して、性質を証明する実験を始めました。
対象は、usa さん(GitHub 等では unak さん)が Go で実装しているスクリプト言語 Les です。
この実験を進めているリポジトリは gotoken/les-spec です。
ここでやろうとしているのは、Go で書かれた評価器を別の言語に移植することではありません。Les のプログラムを実際に動かして振る舞いを観測し、必要に応じて Go のコードも調べながら、その振る舞いを説明できる概念的なモデル(どんな情報を保持し、どんな規則で計算を進めるのか)を推定します。それを Lean という、プログラムを書くことも数学的な証明を検査することもできる言語で記述します。
目指すのは、個々のプログラムが期待どおりに動くことを確かめるだけでなく、モデルが満たすべき性質を数学的な命題として記述し、その仮定を満たすすべての場合について成り立つことを証明することです。対象となる入力や実行途中の状態は無限にあり得るので、これはテストとは異なる仕事です。
通常の Les CLI は、ソースコードを字句解析・構文解析して抽象構文木(AST)を作り、型推論と型検査を行った後、そのプログラムを Go の評価器で実行します。今回の形式化は、主としてこの最後の評価段階を対象にしています。
そこで、Lean の評価器に渡すのは Les のソースコードそのものではありません。Go 版の字句解析・構文解析・型推論を再利用する lesdump というツールが、プログラムの構造を表す AST と型解析結果を JSON に変換し、Lean 側で読み込んで評価します。元の Go CLI の実行結果は別に取得し、比較に使います。
2026年11月15日現在、Les の一部について実行可能な Lean 評価器を作り、Go 実装と35件のプログラムで観測結果が一致することを確認しました。さらに、遅延した計算が正常に終われば結果が保存され、同じ保存場所から再び値を求めても計算をやり直さないことなど、モデルの内部の性質を Lean で証明しました。その定理の仮定を満たす具体例も構成しました。
まだ Les 全体を形式化したわけではありません。また、Go 実装と Lean モデルが数学的に同値であると証明したわけでもありません。観測に基づいて仕様を推定すること、そのモデルを実行して元の処理系と比較すること、モデル自体の性質を証明することは、それぞれ区別して進めています。
この記事では、何を作ったのか、どう進めたのか、何が分かったのか、そして今後どこを目指すのかを整理します。
1. Les はどんな言語か
Les(Lazy Evaluation Script)は、Python に似たインデントベースの構文を持つ、Go で実装されたスクリプト言語です。
Ruby のような簡潔な記述、Go に影響を受けた型システム、型推論、構造的インターフェースなどを備えています。
そして、大きな特徴は変数や関数引数などが原則として要求時に評価されることです。
例えば、次のプログラムを考えます。
def choose(first: Int, second: Int): Int:
first
print choose(42, 1 / 0)
このプログラムの出力は 42 です。
通常の先行評価(call-by-value)なら、関数の呼び出し前に 1 / 0 が評価され、ゼロ除算になります。しかし Les では使われない第2引数を評価しないため、エラーになりません。
明示的に評価を要求する force や後置の ! も用意されています。
Les を手元にインストールしなくても、Les Playground でブラウザからサンプルを実行したり、自分でコードを書き換えて試したりできます。
遅延評価自体は、Haskell や R をはじめ、多くのプログラミング言語で研究・実装されてきました。Les が興味深いのは、遅延評価に加えて、再束縛と環境捕捉の振る舞いに特徴があることです。
作成時に存在する変数を捕捉する
a = 1
b = a + 1
a = 10
print b
結果は 2 です。
b の右辺はすぐには評価されません。しかし b を作成した時点で見えていた a の束縛を捕捉しているため、その後に a を再束縛しても b から見える参照先は変わりません。
作成時に存在しない変数は後から見つける
一方、次のプログラムは異なる振る舞いをします。
b: Int = a + 1
a = 5
a = 7
print b
結果は 8 です。
b を作った時点では a が存在しないため、a は捕捉されません。b が実際に評価される時点で、生きたスコープから a を探し、そのときの束縛である 7 を参照します。
つまり、Les の遅延評価では次の二つが共存しています。
- Thunk 作成時に解決できた名前は、その時点の束縛を捕捉する。
- 作成時に解決できなかった名前は、後の評価時に解決する。
これは単純な call-by-name や、通常の静的スコープを持つ call-by-need の説明だけでは捉えきれません。
さらに Les では、同じスコープに既存の名前を再束縛すると、右辺がその場で強制評価されます。初回束縛と再束縛で評価時期が異なるのです。
このような規則を個別に理解するだけでなく、互いに組み合わせても矛盾なく説明できるモデルを作ることが、今回の形式化の出発点でした。
2. 今回の実験で何を目指したのか
最初から Les 全体の仕様書を作ったり、Go 実装をすべて Lean に移植したりするつもりはありませんでした。
まず、次の三つを別々の目標として設定しました。
第一は、観測可能な振る舞いの記録です。
特定の Les プログラムを実行したとき、標準出力、標準エラー出力、終了コードが何になるのかを固定します。
第二は、その振る舞いを説明する小さな実行可能モデルです。
たとえば第1節の二つのプログラムでは、変数 a を後から束縛し直しているにもかかわらず、b が参照する値の決まり方が異なります。この違いを説明するには、変数名と値の対応だけでなく、いつ参照先を決め、何を保存するのかを考える必要があります。多数の観測例を矛盾なく説明できるように規則と状態の表現を組み立て、それを Lean で実行できるようにします。これが今回の意味論(semantics、プログラムが何を意味し、どう計算されるかを定める規則)のモデルです。Go の内部構造をそのままコピーする必要はありませんが、観測に反するモデルになっていないかは差分テストで調べます。
第三は、モデルの性質の証明です。
「一般的な性質を証明する」とはどういうことか
簡単な数学の例を考えてみます。自然数 n について、n + 1 > n が成り立つことを確かめたいとします。n = 0, 1, 2, ... と値を代入していけば、いくらでも成功例を増やせます。しかし自然数は無限にあるので、有限回のテストによってすべてを調べ終えることはできません。一方、特定の値を代入せず、任意の自然数 n について成り立つ理由を示す数学的な証明なら、まだ試していない値も含めて扱えます。
今回の評価器で知りたいのも、これに似たことです。例えば、ある遅延された式を評価し、結果を保存したあとで再びその値を求めたとします。いくつかのプログラムを実行して同じ値が返ることを観察するのはテストです。しかし、式の種類、変数の束縛、保存場所、実行途中の状態などの組み合わせは膨大で、モデル上は無限にあり得ます。
そこで第4節で紹介する定理では、特定の式や値を選ぶ代わりに、それらを任意のものとして扱います。未評価の式が所定の場所に保存されており、その計算が正常に終了するという仮定のもとで、結果がその場所に保存されること、そしてその直後の状態から再び同じ場所の値を要求すると、同じ値が返り、実行状態も変わらないことを示します。このとき、Lean は命題だけでなく、それを導く数学的な証明も検査します。
「一般的」とは、試したプログラムだけでなく、定理で定めた対象のうち仮定を満たすすべての場合を扱うという意味です。 あらゆる Les プログラムで計算が成功することや、途中に別の操作を挟んでも常に同じ値になることまで示したわけではありません。
このテストと証明の違いは、P2 の終了後に知った Sam Xifaras 氏の ruby-lean の記事の導入部 でも分かりやすく説明されています(第9節で両者を比較します)。
この三つは別々の仕事です。観測結果との一致はモデルの妥当性を支持しますが、Go 実装との同値性を証明するものではありません。モデルについての定理も、直ちに元の Go 実装についての定理になるわけではありません。
3. P0〜P1:観測から Lean 評価器を作る
P0:対象を固定して、再現可能にする
最初に Les の対象コミットを固定しました。
aa78fdcfc76b156e6b5ab4735516fcefadce954b
このコミットから Go の CLI をビルドし、最小限のテストを実行しました。同時に Lean 4.25.0 と Lake のビルド環境を用意しました。
固定コミットを使うのは、実験中に upstream の実装が変化して、観測結果や証明対象がいつの間にか変わるのを避けるためです。
最初の5件のテストでは、print、exit、未使用引数の遅延評価、ゼロ除算などを確認しました。
ここで意外に重要だったのが、Go CLI と Go の評価器テストが同じ経路ではないことでした。固定コミットの CLI の runPipeline は、通常の実行を次の三段階に分けています。
- 字句解析・構文解析(
parser.ParseProgram):ソースコードを読み、AST を構築します。構文エラーがあればここで停止します。 - 型推論・型検査(
InferProgram):プログラムの型を推論し、型の整合性を検査します。型エラーがあれば停止し、型警告は標準エラー出力に書き出します。 - 評価(
EvalProgram):構文解析で得た AST と型推論器を使い、必要になった式を評価します。
実際、CLI の -c オプションは第1段階まで、-t は第2段階までを実行するもので、いずれも評価は行いません。遅延評価という性質は第3段階の計算についてのものであり、実行前の構文解析や型検査まで遅延させるわけではありません。
したがって CLI の標準エラー出力には、評価器が返すエラーだけでなく、実行前の型警告なども含まれ得ます。そこで、評価器の振る舞いと型推論の警告を混同しないよう、テスト入力と期待値を整えました。
P1:Go CLI で何を観測し、lesdump で何を渡したのか
ここは二つの仕事を区別する必要があります。
- 実行結果の観測:固定コミットからビルドした Go 製 Les CLI に
*.lesを渡し、stdout・stderr・終了コードを調べて*.expect.jsonに固定する。 - Lean に渡す入力の構築:Go 版の字句解析・構文解析・型解析を再利用した
lesdumpが、同じ*.lesの抽象構文木(AST)と型解析結果を JSON で出力する。Lean はその JSON をデコードして、自分の評価規則で計算する。
AST は、例えば a + 1 を「加算という操作、その左側の変数名 a、右側の整数リテラル 1」という木構造で表したものです。a が実際にいくつなのか、加算の結果がいくつなのかは AST を作る段階では決まりません。
つまり、lesdump は実行結果を採取するオラクルではなく、フロントエンド(評価に先立つ解析処理)を共有するための橋渡しです。対応する部分言語について Go CLI と同じ字句解析・構文解析・型推論の処理を再利用しますが、Go の評価器は呼び出しません。Lean 側も構文解析や型推論の正しさを独立に検証しているわけではなく、JSON を受け取って評価を行います。
実際のディレクトリは、例えば次の対応になっています。
実際のコマンドは次のとおりです。
bash scripts/bootstrap.sh
.work/bin/lesdump difftest/corpus/snapshot-late-rebind.les > /tmp/snapshot.json
python3 difftest/run.py # 固定 Go CLI と *.expect.json の照合
python3 lesdump/test.py # AST JSON と golden の照合
cd lean
lake build
lake exe les-syntax-test ../lesdump/golden 35
lake exe les-eval-test ../lesdump/golden ../difftest/corpus
Go の stdout・stderr・終了コードを採取する実装は difftest/run.py にあります。環境固有のファイルパスを <CASE> に置き換える以外は、期待値を自動的に正解として更新しません。lesdump の JSON は lesdump/test.py によって、決定性や未対応構文を明示的に拒否することも検査します。
先に用語を整理する:Thunk、Cell、Heap、Scope、Env、Machine
ここからは Les のソースコードに現れない、評価器の内部構造を説明する用語が増えます。初めて読む人のために、由来を先に整理しておきます。
遅延評価の研究で使われる thunk(サンク) は、まだ計算していない式を「必要になったら計算するもの」として持っておく仕組みです。単なる式の保存ではなく、後でその式を評価するための環境も必要です。同じ計算結果を保存して二度目に再利用する方式を call-by-need と呼びます。
元の Go 実装の Thunk には、実際に Expr、Env *Environment、Value、Evaluated、Evaluating というフィールドがあります。Environment は store map[string]Value と parent を持ち、captureEnv は作成時に見えていた束縛をコピーしています。
一方、以下の Cell や Machine は、この実験の Lean 評価器で選んだ表現と名前です。Go の構造体を一対一で移植したわけではありません。
| 用語 | 何を指すか | 由来・今回の使い方 |
|---|---|---|
| Thunk | 未評価の式と、後で評価するための情報 | 遅延評価で一般的な語。Go の Les も Thunk と呼ぶ |
| Cell | 評価済みの値、未評価の式、評価中の印のいずれかを入れるひとつの保存場所 | Lean モデルの Cell。Thunk だけでなく評価済みの値も入る |
| Heap | Cell をアドレスで管理する保存領域と、スコープの一覧 | Lean モデルの Heap。OS のヒープ領域そのものを指すのではない |
| Scope | 現在の変数名から Cell アドレスへの対応と、親スコープ | 言語処理系で一般的なスコープ。Lean では ScopeId で参照する |
| Env | 式を後で評価するとき、名前をどこから解決するかという参照環境 | environment の略。Go の Environment に対応する問題を、Lean では snap と scope に分けて表現する |
| Machine | 評価途中で変化する状態をまとめたもの | 抽象機械・評価器の状態という意味。今回は Heap と蓄積中の stdout。物理的なコンピューターではない |
Go の Environment が値や Thunk への参照を持つのに対し、Lean では変数名を Cell の**アドレス(配列の添字)**へ対応させます。この間接参照が、再束縛で名前の行き先が変わっても、古い Thunk が元の Cell を使い続けられる仕組みです。
用語の意味を押さえたところで、実際のプログラムを動かし、どのアドレスが残るのかを見てみます。
観測例1:束縛を捕捉する(E14)
冒頭で示した snapshot-late-rebind.les は、次の4行です。
a = 1
b = a + 1
a = 10
print b
固定 Go CLI の期待結果は、実際に snapshot-late-rebind.expect.json にこう記録しています。
{"stdout": "2", "stderr": "", "exit_code": 0, "rules": ["E14"]}
lesdump の golden JSON では、第2文 b = a + 1 は VarDecl で、右辺は Binary です。次はその文だけを抜き出したものです(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}
}
}
重要なのは、この JSON には「a の値は1」「b の値は2」という評価結果が入っていないことです。VarDecl・Binary・Ident とソース位置だけを表しています。型解析の analysis.status はこのケースでは ok ですが、それも値を実行して得たものではありません。
出力が 2 になる理由は、b の Thunk を作るときに、その時点の a の値ではなく Cell アドレスを捕捉し、a = 10 の再束縛後も古い Cell を参照するからです。この規則を Lean の評価器が実装し、P2c の証明がその参照関係の一部を保証します。
これを Lean の保存領域に置き換えて図示すると、print b の直前は概念的に次の状態です。#0・#1 は組込み関数用の Cell なので、この例では a の最初の Cell は #2 になります。矢印の数字は値ではなく、Cell 配列内のアドレスです。
1行目の a = 1 が #2、2行目の b = a + 1 が #3、3行目の再束縛 a = 10 が #4 を作ります。Heap.scopes[1] にある名前 a の行き先は #4 になりますが、#3 に保存された env_b.snap は #2 を指したままです。したがって b の評価では 1 + 1 が計算されます。
これはGo の内部メモリアドレスを観測した図ではなく、Go の出力を説明するために作った Lean の Heap モデルの図です。実際の Go はポインターと Environment を使い、Lean は整数のアドレスと配列を使っています。
観測例2:まだ束縛されていない名前を後から解決する(E15)
対照的な forward-ref-rebound.les は次のとおりです。
b: Int = a + 1
a = 5
a = 7
print b
期待結果は forward-ref-rebound.expect.json の {"stdout": "8", "stderr": "", "exit_code": 0} です。
AST の形は先ほどとほぼ同じで、b の右辺はやはり Binary(Ident("a"), "+", Int(1)) です。しかし b の生成時には a の束縛が存在しません。したがって a はスナップショットへ入らず、print b が初めてその値を要求した時点で、現在のスコープの最新の a = 7 を見つけます。
ここが、単に AST を作るだけでは分からない、実行時の環境捕捉・名前解決に関する意味論です。二つの例が同じ Binary の AST なのに 2 と 8 を返すことが、Heap と Env を Lean に用意する動機になりました。
ここでは b の Thunk を作ったときに a がまだないので、env_b.snap は空です。評価時は env_b.scope = 1 をたどって現在の束縛を探します。
先ほどの 2 と今回の 8 の違いは、Binary という構文の違いではなく、同じ名前 a を Env.snap から解決するか、後から生きた Scope で検索するかという違いになります。
観測例3:遅延評価の結果は共有される(E9)
メモ化を検査する memo-binding.les は次のプログラムです。
def g(): Int:
print "side;"
1
x = g()
print "before;"
print x
print x
固定 Go CLI の期待値は以下です。
{"stdout": "before;side;11", "stderr": "", "exit_code": 0, "rules": ["E9"]}
x = g() の宣言時には g が呼ばれず、最初の print x で一度だけ g が評価されます。二度目の print x は共有された結果を再利用します。したがって side; は一度しか出ません。lesdump 側では g は FuncDef、x = g() は右辺に Call を持つ VarDecl として出力され、評価や副作用の回数は JSON には書かれません。
さらに失敗系の blackhole.les では、
x: Int = x + 1
print "ok"
print x
が stdout ok と終了コード1、stderr Runtime Error: blackhole: circular reference detected in lazy thunk(末尾改行付き)になります。後に Lean で導入する Cell.blackhole はこの観測を説明するための状態です。
Lean 側は何を比較するのか
Lean のデコーダーは、lesdump の {"kind":"Binary",…} を Expr.binary に、{"kind":"VarDecl",…} を Stmt.varDecl に変換します。型解析が成功した Program だけを CheckedProgram にして実行します。ただし、Lean が Go の型推論の正しさを証明したわけではありません。
lean/Tests/Eval.lean の比較処理は、要点を抜き出すと次の形です。
def verdictOf (fuel : Nat) (src : String) : Except String Verdict := do
return (run fuel (← progOf src)).verdict
テスト本体は各ケースについて lesdump/golden/*.json と difftest/corpus/*.expect.json を読み、verdictOf の返した stdout・stderr・exitCode と期待値を比較します。
UNSUPPORTED や OUT_OF_FUEL は一致として数えません。現時点の35件はすべて PASS です。Lean の構文テストは JSON 35件のデコードと再エンコード等を、個別テスト41件は AST を直接組んだ評価を検査しています。
例えば個別テストでは、3回要求しても副作用が1回であることだけでなく、評価後に共有 Cell が本当に .done へ書き換わったことを runMachine から取り出した Heap で確認しています。また b の Env.snap が再束縛前の a を指していることも Cell アドレスを比較して検査しています。
これらは「観測・実行テスト」です。次の P2 では、これと対応する Lean 評価器について、有限個のテストに依存しない性質を証明します。
4. P2:実際に何を Lean で証明したのか
P1 の35件は stdout などの観測結果の一致を調べます。P2 では、その比較に使っている同じ Lean 評価器を対象に、「どういう初期状態でも、この条件が成り立てば必ずこの結果になる」という定理を作りました。
中心となるのは、lean/Les/Proofs/Memo.lean の whnf_suspended_ok_memo です。名前の whnf は weak head normal form(弱頭正規形) の略で、関数型言語の遅延評価で使われる用語です。このモデルでは「指定した Cell を、値が分かるところまで強制する処理」の名前として使っています。whnf は Lean の組込み関数でも Les の構文でもなく、今回の Lean 評価器で定義した関数です。定理の具体的な意味を読むために、まず Machine と Cell を確認します。
4.1 評価器のデータ型:名前ではなくアドレスを共有する
ここで、先ほどの用語が Lean のどのデータ型に対応するかを図で確認します。
Machine は「プログラム全文を保持したオブジェクト」ではなく、評価のあいだに更新される部分だけをまとめています。実行する式 Expr、その環境 Env、再帰の深さを制限する fuel は、evalE・demand・whnf などの関数の引数です。Machine.stdout は print による出力を、実際に端末へ書き込む代わりに文字列として保持します。だから例外が起きても、その時点までの出力を比較できます。
以下は実際の lean/Les/Eval/Types.lean からの抜粋です。
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 は Cell の配列で、Addr はその添字です。スコープの変数は値を直接持つのではなく Cell のアドレスを持っています。
Env.snap は Thunk 作成時に解決できた名前とアドレスの組、Env.scope はまだ捕捉していない名前を探す生きたスコープの番号です。Scope.vars は現在の名前とアドレスの対応を持ち、Scope.parent は親スコープを参照します。Env が「式をどこから評価するか」を記録し、Scope が「その時点でどの名前がどの Cell に結び付いているか」を保持する、という役割分担です。
EvalM も Lean の標準型そのものではなく、今回の評価器が付けた別名です。Machine の状態を読み書きし、途中でエラーや exit により停止する可能性がある計算を表します。StateM Machine が実行状態を扱い、ExceptT Halt が正常終了(Except.ok)と停止理由(Except.error)を扱います。
Cell の3状態は、次の遷移を実装するためにあります。
evalE・whnf・demand:式、アドレス、値の違い
ここは Lean のコードを読むうえで重要です。評価器には、名前の似た3つの関数があります。
| 関数 | 名前の意味と役割 | 入力から結果へ |
|---|---|---|
evalE | evaluate expression の略。式を処理して、結果が入る Cell のアドレスを返す。識別子なら既存の Cell を返し、ここではまだ強制しない | Expr → EvalM Addr(fuel と Env は省略) |
whnf | weak head normal form の略。指定された Cell を要求時に強制し、値を返す。未評価ならその式を実行し、成功時に done としてメモ化する | Addr → EvalM Value |
demand | 英語の demand(値を要求する)。evalE で得たアドレスを whnf に渡し、式の値を要求する。エラー時には式の位置情報も付ける | Expr → EvalM Value |
例えば b = a + 1 の右辺を evalE に渡すのと demand に渡すのでは、結果の型と強制する範囲が違います。変数 b が未評価の Cell を指すとき、evalE (Ident "b") に相当する処理はそのアドレスを返し、whnf はアドレスの先にある式を評価して値を返します。
WHNF を一般的な遅延評価の用語として言うと、式全体を完全に正規化するのではなく、外側の値が何なのかを判別できるところまで評価した状態です。例えば遅延リストなら、先頭の構成子が空リストか cons か分かれば、その要素や後続のリストは評価されていなくても WHNF に達しています。ただし、これは一般的な説明であり、現在の Les の Lean モデルにリストは実装していません。ここでの whnf は Cell を Value にする関数で、あらゆる入れ子の計算を再帰的に完全評価する「全正規化」の意味ではありません。
これらの関数には実際には先頭に fuel : Nat も渡します。fuel は自然数で与える再帰の制限で、ゼロなら outOfFuel になります。実行全体の命令数や計算量を数えるものではありません。
この遷移の中心になるのが lean/Les/Eval/Eval.lean の whnf です。以下は実際の定義です。
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 は式を評価してから、その結果の Cell を whnf で強制する関数です。EvalM の順序が ExceptT Halt (StateM Machine) なので、途中でエラーが起きても、エラー前に書き込んだ stdout や Heap の状態は残ります。
先ほどの memo-binding.les で、最初の print x が副作用を生み、2度目は生まない理由を、このモデルでは同一アドレスの Cell が suspended から done へ変わるためと表現します。
4.2 P2a:Heap の局所操作
このモデルのために、まず Proofs/Heap.lean で alloc、setCell、bind を調べました。例えば、次は実際の補題です。
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?]
「Cell を新しく割り当てたら、返されたアドレスには、その Cell が入っている」という、当たり前に思える性質です。ただし、ここを補題として確定しておけば、後で状態を変更する証明に引用できます。
反対に、Heap.bind は任意のアドレスを登録できるので、すべての Heap が自動的に整合的になるわけではありません。必要な仮定を明示することが、P2d の仕事につながりました。
4.3 P2c:2 と 8 の違いをアドレスで証明する
P1 の snapshot-late-rebind.les は 2、forward-ref-rebound.les は 8 でした。この差を生むのが、Eval.lean の名前解決と環境捕捉です。
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 }
capture は式に現れる識別子について、解決できるものだけを snap に入れます。未束縛の名前は入りません。
Proofs/Capture.lean の capture_preserves_under_bind は、捕捉済みの名前について、後の Heap.bind でも同じアドレスを返し、その再束縛操作は元の Cell の中身を変更しないことを示します。capture_unbound_lookup と forward_ref_rebound は、捕捉されなかった名前の検索が後の再束縛を見られることを、条件付きで示します。
つまり、テストで観測した 2 と 8 に対応する名前解決の部品は Lean で証明済みです。ただし、これらの補題だけで「任意の Les のソースを実行すると必ず 2 になる」というプログラム全体の定理になるわけではありません。
4.4 P2d:Cell を消さないことから、元のアドレスが残ることへ
初回強制で必要なのは、demand の実行が終わったあとも、元の Thunk のアドレスが有効であることです。
ここでは一見遠回りに見える性質を証明しました。
Proofs/Monotone.lean にある定義は次のとおりです。
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 は数学の monotone(単調) に由来する、今回定義した命題の名前です。Lean の組込みの検証コマンドではありません。Mono x は、どんな開始 Machine で x を実行しても、最終 Machine の Cell 配列が短くならないという意味です。成功時だけでなく、例外で終わる場合も含めます。中間状態のすべてについて述べた定理ではありません。
それを実際の相互再帰評価器について示したのが Proofs/MonotoneEval.lean の次の定理です。
theorem demand_mono (fuel : Nat) (e : Expr) (env : Env) :
Mono (demand fuel e env) :=
(monoAt fuel).2.2.1 e env
monoAt は evalE、whnf、demand、関数呼び出し、引数準備、文実行など相互再帰する11個の関数の Mono をまとめた命題です。これを fuel に関する帰納法で証明しています。
Cell が配列から消えなければ、開始時に有効だった添字は終了時にも有効です。そこから demand_validAddr を導き、以前は別途必要だった hvalid(実行後もアドレスが有効という仮定)を削除しました。
ここで大切なのは、配列の長さが減らないことは、各 Cell の中身が変わらないことではないという点です。suspended を blackhole や done に更新することは認めています。
4.5 最終的な定理:whnf_suspended_ok_memo(P2d-5)
以上を組み合わせて得られた定理が、Memo.lean の whnf_suspended_ok_memo です。次は実際の定理文と証明全文です。
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 の記法
定理の中の ((demand n e env).run).run m は、demand を実行状態 m から実行し、結果と実行後の状態の組を得る式です。run が二度あるのは、EvalM が ExceptT と StateM という二つの層で構成されており、それぞれを取り出すためです。値と状態を区別すると、結果の型は概ね次のとおりです。
Except Halt Value × Machine
Except.ok v は正常終了して値 v を得たこと、Except.error h は停止理由 h を得たことです。(結果, m₂) のように Machine が組の第2成分に残るため、エラー終了時の Heap や stdout も検査できます。
また、Lean の定理の読み方には、次の記号だけ押さえておけば十分です。
| 記法 | この定理での読み方 |
|---|---|
theorem 名前 (引数) : 命題 := by ... | 命題を宣言し、by 以下で証明する |
h : ...、hd : ... | 仮定に名前を付けている。任意に成り立つと宣言したわけではない |
∧ | 「かつ」。ここでは結論が3つある |
∀ k | 「すべての自然数 k について」 |
{ m₂ with heap := ... } | Machine m₂ の heap フィールドだけを更新したもの |
h1・h2、exact | 既に証明した補題を結合し、要求された結論を渡す |
この run.run や ∀ はLean の表記です。それに対して whnf、demand、Mono は、この記事の対象である les-spec が定義した名前です。両者を区別して読むと、定理の意味を追いやすくなります。
Lean の記法に慣れていなければ、二つの仮定と三つの結論に分けると読みやすくなります。
仮定
h:最初の Machinemのアドレスaに、未評価の式eと環境envが入っている。hd:その Cell をblackholeにした状態でdemand n e envを実行したところ、値vを返して正常終了し、Machinem₂になった。
ここで m₃ を「m₂ のアドレス a の Cell を done v に書き換えた Machine」と呼ぶことにします。
結論
- 最初の
whnf (n+1) aはok vを返し、最終状態はm₃である。 m₃のアドレスaには、本当にdone vが入っている。- 以後の
whnf (k+1) aはどんなk : Natについてもok vを返し、m₃を変更しない。
これは、memo-binding.les の「g() を最初の要求で実行し、後から同じ x を要求しても副作用を繰り返さない」という観測を支える、Cell レベルの一般的性質です。
特に2番目は重要です。単に「強制したら同じ値が返った」というだけでなく、共有されたアドレスにメモ化された値が残ることを保証しています。3番目は Machine 全体の等式なので、再強制で stdout も変わりません。
ただし、この定理は hd、すなわち demand が正常終了することを仮定しています。自己参照のブラックホールやゼロ除算のような失敗時のメモ化は含みません。また、任意の Les プログラムから x への参照が必ず同じ Cell を指すという性質まで、この一つの定理が保証するわけではありません。その部分は評価器の実装と個別の共有テストで検査しています。
4.6 定理の仮定を満たす実例も Lean で構成した
定理に hd という条件を置くだけでは、「実際には誰も満たさない条件なのではないか」という疑問が残ります。
そこで Proofs/NonVacuity.lean では、実際の評価器が使う Heap.initial に未評価 Cell を一つ割り当てた具体例を用意しました。
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
証明 memoWitness_suspended は、そのアドレスの Cell が未評価であることを示します。memoWitness_demand_ok は、その Cell を blackhole にした状態から demand 2 を実行すると ok (.int 42) になることを示します。memoWitness_structWF は、初期 Heap が定義済みの構造的整合性を満たすことを示します。
この三つを使い、whnf_suspended_ok_memo_nonvacuous は、whnf_suspended_ok_memo の2つの仮定が同時に成立する Machine・式・環境が少なくとも一組あることを証明しています。memoWitness_integrated は、そこへ統合定理を適用して3つの結論を導く例です。
つまり関係は、次のようになります。
図のテストと証明は、同じ Lean 評価器を対象にしている一方で、論理的に同じ主張ではありません。Go との35件の一致から定理を導いたわけではなく、Lean の定理から Go の実装全体の正しさを導いたわけでもありません。
4.7 どのように検証したか
定理は #print axioms でも確認しています。修正後の PR #22 の CI では、Lean 4.25.0 の lake build が成功し、whnf_suspended_ok_memo_nonvacuous と memoWitness_integrated の依存公理は propext と Quot.sound のみで、sorryAx はありませんでした。コーパス35件の比較もすべて PASS でした。
実は非空虚性の最初の実装では、memoWitness_demand_ok を単に rfl で示そうとしてコンパイルが失敗しました。その後、整数リテラルの評価が done Cell を割り当てることを確かめ、whnf_done を使って成功を証明する補題 demand_int_ok へ修正しています。
この失敗も含めて、実行結果を合わせる作業と、Lean カーネルが受け付ける証明を作る作業は別物であることが分かりました。現在は PR の段階で Lean のビルドと評価器のコーパステストを行う GitHub Actions も用意しています。
5. Lean を使って何がうれしかったのか
この実験で得られたものは、単なる別言語での再実装だけではありません。
まず、意味論上の前提条件を明確にできました。
たとえば Heap.bind は、無効な Cell アドレスも引数として受け取れます。したがって、Heap の整合性が無条件で保存されるとは言えません。
証明を進めることで、どの操作にどの条件が必要なのかが明確になりました。実際に、無効なアドレスを束縛すると整合性が壊れる反例も記録しています。
次に、具体的なテスト結果と一般的な性質を区別できました。
「このプログラムを実行すると同じ値になる」というのはテストです。
「任意の Machine について、評価済み Cell を再び強制しても値と状態が変わらない」というのは定理です。
今回の Lean による証明は後者です。対象となる Lean モデルについて、その定理の仮定を満たすすべての状態を扱います。
もう一つは、形式化そのものを小さく進められることです。
最初から言語全体の完全な意味論を設計する必要はありませんでした。観測し、必要なデータ型を用意し、小さな評価器を作り、そこで証明できる性質を増やしていく、という方法でも成果を積み上げられました。
6. 実際にどうやって作業したか
このプロジェクトでは、AI に実装と証明を支援させています。
主な実装と Lean の証明作業は Claude Sonnet 5.5 に担当させ、仕様の切り分けと設計、Pull Request のレビューについては別のモデルも使いました。GitHub 上では Codex によるレビューも利用しています。
重要視したのは、長い指示で一度にすべてを完成させることではなく、作業単位を小さくし、それぞれに停止条件を設けることです。
基本的なサイクルは次のとおりです。
- Go CLI で観測し、期待値と根拠を記録する。
- 必要な場合だけ Go の実装を調べ、Lean のモデルを設計する。
- 一つの機能、あるいは一組の定理を実装する。
lake build、差分テスト、個別テストを実行する。- 証明できた性質と未証明の性質を記録する。
- PR を作成し、レビュー後に次へ進む。
難しい意味論の解釈で詰まった場合だけ、より高コストなモデルへ相談する方針も設けました。ここまでの後半工程では、そのための semantics-opus を利用せずに進められています。
ただし、モデルのトークン使用量は十分に計測できておらず、この方法が人手の開発や別の AI 構成より安価である、という結論はまだ出せません。
今回確認できたのは、AI の支援を受けながら、Lean のコンパイラに検査される証明を段階的に構築できたということです。
7. まだ証明していないこと
ここまでの成果には、明確な限界があります。
第一に、Go の Les 実装全体と Lean モデルの同値性は証明していません。
Go CLI と Lean の観測結果が35件で一致していることと、Lean モデルのいくつかの性質が証明されていることは別の事実です。
第二に、Les の全機能は対象にしていません。
Lean モデルが扱うのは、現時点では9種類の構文ノードからなる小さな部分言語です。元の Les が持つ構造体、パターンマッチ、複雑な型システムなどは対象外です。
第三に、型安全性は証明していません。
現在の Lean 評価器は、Go 側の型解析が成功したことを示す CheckedProgram を入力として受け取ります。これは Lean が独立に型検査の正しさを証明したという意味ではありません。
第四に、Heap の完全な整合性もまだ証明していません。
スコープの基本的な参照関係は検査していますが、Thunk の環境内に保存されたアドレスや、クロージャが保持するスコープなど、Cell の内部に含まれる参照までは対象にしていません。
こうした未証明の性質を明示的に残していることも、今回の実験では重要だと考えています。
8. これから何を目指すのか
現時点では、次の順序を考えています。
近い目標:P2 の成果を参照点として確定する
初回強制の成功、Cell 数の単調性、メモ化、再強制の安定性は、P2d-5 の whnf_suspended_ok_memo に統合しました。具体的な証人も用意し、証明範囲の一覧 に観測・実行照合・定理の違いを記録しています。
次は、失敗した demand の後に残る Heap と blackhole の状態、Cell 内部の参照関係を含む整合性など、まだ条件付きでしか扱えていない部分を検討します。ただし、新機能の追加と同時にすべてを証明するわけではなく、必要な不変条件を選んで進めます。
中期目標:対象となる言語機能を広げる
P3 では、if、Tuple、Dict、パターンマッチなど、Les の機能を一つずつ追加することを検討しています。順序は固定せず、Go 実装での観測可能性と既存の証明への影響を調べて選びます。
機能を増やすたびに、Go で観測し、意味論を整理し、Lean に実装し、必要な性質を証明するというサイクルを繰り返します。
一度に言語全体を移植するのではなく、各段階で動作する成果を維持したいと思っています。
長期目標:実装と形式モデルの関係を強くする
もっと先には、Go 実装と Lean モデルの関係を、現在の有限個の差分テストより強く説明できるようにしたいと考えています。
そのためには、対象部分言語の範囲を明確にしたうえで、より網羅的なテスト生成や、実装と仕様の対応関係の検討が必要になるでしょう。
Go 実装そのものの意味論的な正しさを形式的に証明するのは、さらに大きな課題です。
そこをいきなり最終目標とするのではなく、観測可能な仕様が蓄積され、Lean のモデルが検査可能な参照モデルとして役立つところをまず目指します。
9. P2 完了後に知った ruby-lean ——先行例との答え合わせ
P2 の証明を一区切りにした 2026年11月、Sam Xifaras 氏が同年9月26日に公開した 「ruby-lean: A Ruby semantics with a type soundness proof」 の存在を知りました。技術付録 と ソースコード も公開されています。
記事自体は本実験を始めるより先に公開されていますが、私がこの仕事を知ったのは P2 を終えた後です。したがって、P0〜P2 の設計や実装が ruby-lean を参考にして行われたわけではありません。以下は事後的な答え合わせと、今後の選択肢の検討です。
同じ方法を、異なる言語と異なる定理へ適用している
ruby-lean は Ruby を Lean 4 で実行できるモデルにし、実際の CRuby との比較を行い、さらに Sorbet を参考にした限定的な型判定とその健全性を証明しています。こちらの les-spec は、Go 製の Les の一部を Lean で評価できるようにし、共有 Thunk のメモ化、環境捕捉、アドレスの有効性などを証明しました。
| 観点 | les-spec(P2 完了時点) | ruby-lean(2026年9月の報告) |
|---|---|---|
| 元の処理系と対象 | Go 製 Les。遅延評価、再束縛、捕捉、前方参照に注目 | CRuby。メソッド呼び出し、クラス、動的な変更なども扱う |
| Lean への入力 | Go のパーサーと型解析を通した lesdump の JSON AST | Ruby の表層構文をより小さなコア言語へ変換する desugaring |
| 評価器 | evalE・whnf・demand の fuel 付き再帰関数。Machine は Heap と stdout を保持 | CESK 抽象機械。制御、環境、ストア、継続を明示して遷移する |
| 差分検査 | 固定 Go CLI と35件の stdout・stderr・終了コードを比較 | CRuby の bootstraptest と生成テスト等を使用。技術付録では意味論について 995/1,309件の bootstraptest 適合を報告 |
| 証明の中心 | 成功した初回強制のメモ化と再強制の安定性など、評価器内部の性質 | 型検証器が受理したプログラムについて、定義された種類の型関連エラーに陥らないこと |
最後の行は成果の優劣を表していません。証明したい性質が違います。ruby-lean の結果は Ruby や Sorbet の全機能の健全性を保証するものではなく、les-spec の結果も Go と Lean の一般的な同値性を保証するものではありません。
答え合わせ 1:実行可能な意味論と、実装への適合性は別問題
まず確かめられたのは、Lean が定理を検証できることと、Lean の評価器が元の言語を正しくモデル化していることを分離する方針の妥当性です。
Xifaras 氏は、ruby-lean が大規模な差分テストに合格している一方で、Ruby の to_str を用いた暗黙の文字列変換について、CRuby との未解消の不一致を具体例とともに公表しています。モデルに対する定理の存在だけでは、そのモデルが元の処理系の全挙動を表す保証にはなりません。
こちらでも、whnf_suspended_ok_memo が証明しているのは、Lean の whnf による成功時の Cell の更新と再強制です。Go の Les がすべての入力でそれと同じ振る舞いをすることまでは証明していません。35件の一致を「意味論的同値性」と呼ばなかったことは、この先行例に照らしても重要です。
さらに、ruby-lean の技術付録では、既存の適合性テスト(Tier 0)、生成したテスト(Tier 1)、途中に print を挿入して副作用の発生順序を調べるテスト(Tier 1.5)、AI に生成させた複雑なテスト(Tier 3)を区別しています。Les の場合も、E9 の共有 Thunk、E14/E15 の束縛、E17/E19 の評価順序を、単なる最終値だけでなく副作用の出現箇所によって区別するテストを増やせそうです。
答え合わせ 2:同じ Machine でも評価器の構造は異なる
ruby-lean の評価器は CESK(control, environment, store, continuation)を採用しています。次に実行することを表す ctl と、残りの計算を保持する継続スタック kont が、Machine に含まれています。
これに対して、les-spec の Machine は Heap と stdout を保持します。どの式を次に評価するかは、evalE、whnf、demand の再帰呼び出しとして表れ、明示的な kont スタックを持っていません。
また、同じ Heap という名前でも、les-spec では Thunk の状態を表す Cell の配列を管理し、ruby-lean では Ruby のオブジェクトを格納する配列が中心です。用語が似ていても、一対一に同じモデルではありません。
この違いから、現在の Les モデルをすぐ CESK へ書き換える必要はありません。しかし、将来 return / break、例外、I/O、評価の中断と再開などを拡張した場合、継続を明示することが証明を簡単にするかは比較する余地があります。技術付録では継続スタックの分解に関する補題が証明の助けになったことも述べられています。
答え合わせ 3:テスト件数の増加だけではなく、証明を維持する進め方
もう一つ共通していたのは、AI に大きな仕様を一度に実装させるのではなく、小さな達成条件を積み重ねるという方針です。
Xifaras 氏はこれを ratchet(ラチェット、一方向へ進める仕組み) と呼びます。特に型の判定規則を追加するときは、個別のテストが通るだけでなく、追加した規則の証明義務を満たし、全体の型健全性の定理も維持することを完了条件にしています。
les-spec でも観測、モデル、証明を小さな PR に分けました。しかし、P2d-5 の非空虚性を示す NonVacuity.lean が最初の lake build で失敗したように、分割だけでは不十分です。その後に lake build と既存のコーパステストを GitHub Actions に追加しました。ここは、先行例の方法と自分たちの失敗経験が符合するところです。
今後の追加プランとして検討できること
1. 差分テストを複数の方法で増やす。 手作りの35件に加え、型検査を通る Les プログラムの生成、観測可能な副作用の挿入、既存の Thunk 共有・環境捕捉の例の組合せなどを検討します。単にテスト数を増やすより、どの評価規則を区別できるかを指標にする方が、この題材には合っています。生成テストに対する Go と Lean の一致は引き続き観測であり、証明ではありません。
2. P3 の機能追加でも既存の定理を維持する。 if、Tuple、Dict などを増やすときには、Go のオラクルと Lean の結果が一致することに加え、demand_mono、アドレス有効性、メモ化の証明を維持することを完了条件にします。追加した評価規則で新しい前提が必要なら、その理由と適用範囲を明示します。先行例のラチェットを、実行コーパスと証明の二つの軸に適用する案です。
3. コア言語への変換が必要かを検討する。 ruby-lean は表層 Ruby の構文を小さなコアへ変換しています。Les も対応構文が増えたとき、表層構文をそのまま一つずつ Lean に追加するより、小さなコアへ変換した方が証明を短くできるかもしれません。一方で、その desugaring 自体が元のプログラムの挙動を変えないかを新たに検証する必要があります。lesdump の現状を直ちに置き換える計画ではありません。
4. 型については「推論器全体の移植」以外も候補にする。 今の CheckedProgram は Go 側の型解析の成功を信頼しています。ruby-lean は、型導出の候補を信頼しない生成器が作り、Lean の検証器がそれを検査する方法を選びました。これは将来 Les の型を検証する際の選択肢になります。ただし、遅延評価、再束縛、前方参照を持つ Les では、まずどのエラーを排除することが型安全性なのかを定義しなければなりません。これは現行の P3 に追加すると決めた作業ではなく、長期的な検討事項です。
先行例を後から知ったことで、P2 の仕事をやり直す必要が生じたわけではありません。むしろ、実装の観測と形式的証明を分けて進める方向性を別の実践と照合できました。一方、CESK や型健全性の大きな証明は、その目的が必要になってから採否を決めるべきであり、方法だけをそのまま移すものではないと考えています。
この節は、本文、技術付録、ruby-lean の公開コード に基づく比較です。上記の追加プランは候補であり、実装済みの成果ではありません。
10. おわりに
今回 Les を題材にしてみて、言語処理系の形式化は、最初から巨大な仕様書を作らなくても始められることが分かりました。
Les は比較的小さな実装でありながら、遅延評価、メモ化、クロージャ、環境捕捉、前方参照、再束縛など、意味論的に興味深い要素を持っています。
特に、作成時に存在した名前は捕捉し、未束縛だった名前は後から解決するという仕組みは、どのような環境モデルが必要かを考えるよい題材になりました。
そして、Go 実装の観測から構築した Lean モデルについて、実際に一般的な性質を証明するところまで進められました。
まだ小さな部分言語に限った成果ですが、ここから先も観測と証明を少しずつ積み重ねていく予定です。
最後に、Les を公開してくださった usa さんに感謝します。また、本稿を読んでくださったことにも、この場を借りてお礼を申し上げます。
関連リポジトリ
- unak/les — 形式化の対象となる Go 製言語
- gotoken/les-spec — 今回の実験
- 評価器の設計メモ — E1〜E22 の規則と根拠
- 差分テストのコーパス — 観測に使ったプログラムと期待結果
- Lean の証明 — Heap、メモ化、環境捕捉、単調性などの証明