E-Graphによるコンパイラ正当性の自動検証
Automatic Checking of Compiler Correctness with E-Graphs (stng.substack.com)
要約
本記事では、E-Graphというデータ構造とアルゴリズムを用いて、コンパイラの正当性を自動的に形式検証する新しい研究を紹介しています。この手法は、プログラミング言語の機能モジュールを独立して検証し、それらを組み合わせてコンパイラ全体を構築するPyrosomeフレームワークと連携し、コンパイラ開発の迅速な実験と信頼性向上を可能にします。
全文翻訳
E-Graphによるコンパイラ正当性の自動検証
この記事は、Adam Chlipala教授のブログ「Structure and Guarantees」と、議論されている研究が行われたMITの研究所であるCSAILのブログでクロスポストされています。
私は、証明された書き換えルールを用いて、正しい効率的なプログラムを段階的に構築するという一連の記事の最終段階にいます。これは、今日広く使われているAIコーディングエージェントの方法に対する重要な代替手段であると私は主張します。以前の例には、テンソルプログラム、デジタルハードウェア、および低レベル暗号ソフトウェアが含まれていました。前回の記事では、代数式の多くの代替的な書き方を効率的に探索するためのデータ構造と関連アルゴリズムであるe-graphを紹介しました。この技術は、プログラム検証とプログラム最適化の両方に非常に役立つことが証明されています。
ここで、このアプローチの実例を、最新の研究から紹介します。来年1月にメキシコシティで開催されるPOPL 2027で発表される予定の私たちの論文では、e-graphを使用してコンパイラの形式検証を自動化しています。これは、ツールがこれまで見たことのない新しいプログラミング言語のコンパイラ定義を入力として受け取り、定理証明をガイドするためだけの追加のアノテーションなしに、自動的にその正しさを証明できる、汎用的な証明自動化ツールの最初の例のようです。(CobaltやRhodiumのような、固定されたプログラミング言語に適用された過去の例はあります。)本稿執筆時点では論文の最終版はまだ公開されていませんが、詳細は筆頭著者であるDustin Jamnerの博士論文で見つけることができます。学部生のTilek Askerbekovもこの論文に貢献しました。
どのようなコンパイラか?
まず、どのような種類のコンパイラについて話しているのかを正直に説明する必要があります。これは、業界でその言葉の標準的な解決策であるGCCやClangのように見えるものではありません。代わりに、数学的に興味深い並列宇宙である関数型プログラミング言語のコンパイラの世界へようこそ。私たちの研究プロジェクトが扱うコンパイラは、古典的な研究論文「From System F to Typed Assembly Language」の伝統に沿っています。私はこのアイデアのセットについて公平な評価者ではありません。論文の教員著者であるGreg Morrisettの元でポスドクをし、彼の元博士課程指導教員であるBob Harperと学部研究を行いました。しかし、この種のコンパイラがどのように機能するかを簡単に見てみましょう。その考え方は、コンパイルが段階に分割され、プログラムのすべての途中形式が、クラッシュの欠如を保証するサウンドな型システムでチェックされるということです。これは、すべての安全性の保証が無効になる中間言語にすぐに低下する古典的なコンパイラとは大きく異なります。
関数型プログラミングの知識への不必要な依存を避けるために、Pythonからの例プログラムを使用し、それを徐々にアセンブリ言語](https://en.wikipedia.org/wiki/Assembly_language)に十分に似たものになるまでコンパイルします。私たちの最初のプログラムは、シンプルで良いものです。
def square(x):
return x * x
def compute(x):
return square(x + 1) + 3
print(compute(4))
プログラマーは一般的に、ある関数が別の関数を呼び出し、それがさらに別の関数を呼び出すといった能力を当然のこととして受け入れています。この自由は通常、バックグラウンドでコールスタックを用いて実装されます。私たちの最初のコンパイラ変換は、コールスタックを明示的にします。実際、コールスタックは、それぞれがスタックの次の下位レベルの関数を呼び出す、ファーストクラス関数の連鎖として現れます。この変換は継続渡しスタイルへの変換であり、「継続」という言葉は導入する関数を指すために使用します。
def square(x, k):
k(x * x)
def compute(x, k):
def after_square(y):
k(y + 3)
square(x + 1, after_square)
compute(4, print)
何が起こったかに注目してください。各関数は now、継続 k を明示的な引数として取ります。関数が返るはずだった場所で、代わりに結果とともに継続を呼び出します。これで、特定のプリミティブを除くどの関数も返さなくなり、ハードウェア実行が実際にどのように機能するかとよく一致します。コールスタックは、私たちの脳が同様の構造を持つ自然言語を理解するように進化してきたため、自然に感じるオプトインのフィクションでした(これは、このフィクションにあまりにも多くの特別な地位を与えることの、実用的なプログラミングにおけるいくつかの欠点について説明するために、将来の記事で再び取り上げる予定の話題です)。この例はまた、Pythonが実際には提供していない末尾呼び出し最適化にいくぶん依存していますが、それが提供されていると想像してみましょう。
このコードの何が、ハードウェアが直接サポートできるものからまだ遠すぎますか? after_squareの関数定義は、囲むスコープから変数 k をさりげなく参照しています。専門用語では、after_squareは変数をキャプチャするレキシカルクロージャです。この種のメカニズムは、ハードウェアで実装するのに自然なものからはかなりかけ離れているため、キャプチャされた変数の使用を削除し、代わりにそれらの変数をファーストクラスの環境にパッケージ化された明示的な関数引数に変更するクロージャ変換コンパイラフェーズも必要とします。私たちの実行中の例の結果は次のとおりです。
def invoke(closure, value):
code, env = closure
code(env, value)
def square(env, x, k):
invoke(k, x * x)
def after_square(env, y):
k = env["k"]
invoke(k, y + 3)
def compute(env, x, k):
continuation = (after_square, {"k": k})
square({}, x + 1, continuation)
def print_result(env, value):
print(value)
initial_continuation = (print_result, {})
compute({}, 4, initial_continuation)
以前はファーストクラス関数値が表示されていたすべての場所で、今では明示的なクロージャ、つまり関数の参照と、その関数がアクセスできるキャプチャされたすべての変数をパッケージ化する環境辞書のペアが表示されます。このコードの有用な特性は、すべての制御フロー、つまりどのコードが実行されるかを決定するコードが、アセンブリ言語にかなり直接的にマッピングされる機能を使用していることです。対照的に、変数キャプチャを伴うネストされた関数定義のようなプログラム機能は、アセンブリではかなり異なるように見えます。生成されたコードはまだタプルや辞書のようなデータ構造を使用しているため、それらの機能をよりプリミティブな構造で説明するためにさらなるコンパイルフェーズが必要ですが、ここでは例を終了します。
このセクションで前に引用した論文は、このようなプログラムと変換を静的型に関連付けており、クラッシュやその他の問題の欠如を保証するためにチェックできます。コードで見たすべてを処理するために必要な型システムの機能すべてをレビューするのは、あまりにも脱線しすぎますが、型も私たちの新しい検証フローの中心的な部分です。
言語とコンパイラ、モジュール式に
この種のコンパイラを正しく実装するのはすでに十分難しいですが、私たちの新しい結果は、Dustinの博士論文の前半部分であるPyrosomeのフレームワークに基づいています。これは、プログラミング言語とその形式的に検証されたコンパイラをモジュール式に定義する方法を示しています。つまり、Pyrosomeを使用すると、プログラミング言語に追加する価値のある機能を表す言語機能モジュールを定義でき、それらの機能を実装するために使用されるコンパイラコードのスニペットがタグ付けされます。さらに重要なことに、モジュールは独立して形式的に検証できます。その結果、特定の構文的な意味で互換性のある任意のモジュールのセットをリンクして、コンパイラがすぐに使用できる完全なプログラミング言語を形成でき、そのコンパイラの正当性定理を「無料で」取得できます。
この設定の課題は、コンパイラスニペットを、それが他の任意の Сnippets とリンクされたときに正しい動作を保証する方法で検証できるようにすることです。これは、有効な機能モジュールを構成するものと、リンクが許可される時期に関するフレームワークレベルのルールに従います。
Pyrosomeは、私が推進してきた書き換えルールと論理的保証の世界観と非常に互換性のある方法で構成されています。以下は、言語機能モジュールの基本的な構造です。(この記事のために、構文やその他の側面を簡略化するためにいくつかの自由を取ります。)
モジュールが最も根本的に行うことは、構文的な言語機能の文法を拡張することです。ここではバッカス・ナウア記法に触発された構文を使用してこれを記述します。以下は、長さ2のタプルを導入するモジュールが式の文法をどのように拡張するかです。
exp ::= ... | (exp, exp) | exp.1 | exp.2
タプルの新しい形状の型を導入し、タプル式の型付けルールを与える必要があります。ここでは、式 e が型 t を持つという事実を e : t と記述します。ルールは、それらが言及するすべての変数に対して暗黙的に量化されていると見なされます。
type ::= ... | type * type
rule: e1 : t1 && e2 : t2 -> (e1, e2) : t1 * t2
rule: e : t1 * t2 -> e.1 : t1
rule: e : t1 * t2 -> e.2 : t2
次の2つの要素は、Pyrosomeでコンパイラの正当性がどのように定式化されるかにおいて最も興味深いものです。第一に、モジュールは式の評価方法を説明する等式ルールを宣言します。これらのルールを提供することは、ある意味で自動定理証明者を助けるための追加作業ですが、ルールはコンパイラの正当性の定義にも寄入します。それらがなければ、定理ステートメントを明確にするためだけに必要になります。ここでは、v 変数はサブタームが値、例えばあるプリミティブ型の定数であることを強制します。この制限は、以下の等式が重要な副作用を生み出すサブタームをドロップしないようにするために重要です。記述している言語機能モジュールが副作用を直接使用しない場合でも、後でそれを行うモジュールとリンクされる可能性があります。
rule: (v1, v2).1 = v1
rule: (v1, v2).2 = v2
第二に、モジュールは言語機能のコンパイラフェーズのケースを提供します。以下は、継続渡しスタイルへの変換のサンプルです。ここでは、現在の関数の継続引数を表すために、生成されたプログラムで変数 k が利用可能であると仮定します。(プログラム変数と、論理的推論のメタ変数のような異なる種類の変数の間で物事が少し曖昧になり始めますが、完全な形式的な分離については、研究論文を参照してください。)ここでは、アンビエント継続 k に特定の値を代入するために使用される、式 e1 における変数 x への式 e2 の代入を e1[x |-> e2] と記述します。また、匿名関数(Pythonのlambdaのような)の構文として fun x => ... を使用します。
cps_conv((e1, e2)) = cps_conv(e1)[k |-> fun x1 => cps_conv(e2)[k |-> fun x2 => k((x1, x2))]]
このタプル化式の、ややトリッキーな展開は、各コンポーネント式を順番に評価し、結果に x1 と x2 という名前を割り当て、それらの値をタプルに結合して現在の継続に渡します。
Pyrosomeは、言語機能モジュールの正当性をどのように定式化するのでしょうか? スニペットごとに1つの証明義務を生成すると仮定するのは魅力的です。Pyrosomeは代わりに、より明白でないことを行います。つまり、ソース言語の機能を表す等式ルールの各スニペットに対して1つの証明義務を取得します。この証明義務は何を言っているのでしょうか? ソース言語の式の両辺がルールに一致する場合、それらの2つの式のコンパイル結果が、その言語のために宣言された等式を使用して、ターゲット言語で証明可能に等しいことを示しています。この定式化が魅力的にモジュール式である理由にはいくつかの微妙な点がありますが、言語機能とそれらのコンパイラコードを別々に定義し、完全な言語とそのコンパイラに簡単にリンクすることを実際に可能にします。この正当性の概念が、コンパイラ正当性の以前の定式化にどのようにうまくマッピングされるかの説明については、博士論文を参照してください。例えば、特定の整数を返すソースプログラムが、同じ整数を返すターゲットプログラムにコンパイルされることを示すことも含まれます。これは、コンパイラがプログラムが評価する整数を普遍的に事前に把握する希望がないチューリング完全言語の場合でも当てはまります。
上記の最初の等式ルールの例では、義務 cps_conv((v1, v2).1) = cps_conv(v1) を得ます。この等式の左辺は、タプル構築の場合(上記で示した)やタプルの最初の要素を射影する場合(まだ示していませんが)など、cps_conv の定義を使用して簡略化できます。次に、証明を完了するためにターゲット言語の等式ルールを適用する必要があります。Pyrosomeに関する私たちの元の論文では、「From System F to Typed Assembly Language」に触発されたケーススタディで、ほとんどの義務を処理できる証明自動化を提示しました。しかし、かなりの数の手動証明ケースが残りました。
E-Graphを使用してコンパイラ正当性の義務の証明を自動化する
元の自動化は、すべての言語機能モジュールの等式ルールに、バックトラッキングなしの貪欲なアプローチでぶつかっていました。前回の記事でカバーしたように、この魅力的にシンプルなアプローチは局所最適に陥る可能性があります。つまり、証明すべき方程式の両辺が実際には同じ形式に書き換えられない場合でも、それらを一致させる書き換えシーケンスが存在する可能性があります。このプロジェクトからの具体的な例のクラスは、eta則の使用を必要とする証明です。これは、例えば f = fun x => f(x) を関数型の任意の f に対して主張するように、式を単純化するのではなく、展開するために使用されることがあります。私たちの新しい解決策は、まさに前の記事の解決策です。つまり、e-graphに基づいた自動定理証明者の使用です。式の多くの可能な書き換えを探索し、可能性のセットをコンパクトに表現し、新しい書き換え機会を検索するために高速な操作を使用します。
私たちのe-graphエンジンは、e-graph操作をDatalogデータベースクエリ言語に削減する人気のあるツールであるegglogに触発されています。DustinはegglogのコアをRocq Proverの論理内に再実装しました。つまり、この実装は、Rocqが推論を好むネイティブ言語での純粋関数型プログラムであり、egglogの元の命令型言語での実装とは異なる新しい実装上の課題がいくつか生じました。Rocqのネイティブ言語を使用しているおかげで、Dustinはエンジンを実装するために使用できた可能性のある一般的な命令型言語の曖昧さを扱うことなく、エンジンの正当性を証明することができました。また、Pyrosomeに固有のエンジン機能と、その証明義務をegglogスタイルのクエリとしてエンコードする方法もあり、これらの機能も証明されています。
最終結果は、Rocq内の関数であり、言語機能モジュールのコードを入力として受け取り、その正当性に関する判定(「証明済み」または「正当性の証明に失敗」)を提供します。この関数自体が証明されているため、Rocq開発内での適用にさらなる人間の労力は必要ありません。この設計上の選択は、個々の実行の結論を正当化する証明を出力するという、もう1つの一般的な選択肢とは対照的です。これは、証明生成のための継続的なパフォーマンスコストを課します。
検証が失敗することがあります。これは、実際のコンパイラバグによる場合もあれば、e-graphエンジンの不完全性による場合もあります。このような不完全性は避けられません。なぜなら、ある開始点からのすべての可能な書き換えシーケンスを探索すると、共有を使用した巧妙なデータ構造でも、格納するにはあまりにも多くの項バリアントを生成する可能性があるため、通常は検索ラウンド数に数値的なカットオフが使用されるからです。検証が失敗した場合にプログラマーに有用なフィードバックを提供することが重要です。プログラマーに、可能な限り最も単純な言葉で、どの等式が確立できなかったかを説明したいと考えています。部分的にはその目的のために、この新しいエンジンには、前回の記事で議論したような抽出機能が含まれており、ある値を表すためにこれまでに見つかった最も短い項を生成します。
前回の投稿では、e-graphをツリーとして構造化する抽出アプローチの概要を説明しました。eggに従って、私たちの新しいエンジンは、一般的なe-graphからの抽出を、加法的なコスト関数のやや柔軟な概念で処理できます。これは、値の最適なエンコーディングを見つける際に最適化するメトリックを提供します。トリックは、先を読んでおくことです。e-graphのすべてのノードは、選択されたコスト関数に従って常に値で注釈付けされており、e-graphの変更はこれらの値を修正する必要があります。その後、単純な線形時間グラフトラバーサルで任意のノードの低コスト表現を抽出できます(ただし、その表現は共有を持つグラフとして表される場合があるため、ツリーとして単純に印刷すると線形時間以上かかる場合があります)。
[
[画像]
](https://substackcdn.com/image/fetch/$s_!unq7!,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fdfd4a574-0d9b-4516-be10-96787b7bac23_1536x1024.png)
私たちの論文からの評価は、ソース言語で多相性を避けるように制限した場合、このエンジンが「From System F to Typed Assembly Language」に触発されたコンパイラに関連するすべての義務の証明を自動化することを示しています。他のケーススタディ(多相性の追加を含む)がいくつかあり、手動証明で数個の残りの義務(すべてのケーススタディで約200の義務のうち約5つ)を生成します。完全な実装には、型推論のためのe-graphの使用も含まれており、これは便利なサーフェス構文で記述されたルール内の欠落している型アノテーションを埋めるために適用されます。
結論
この新しい機能により、新しいプログラミング言語機能とそのコンパイラコードの迅速な実験が可能になります。なぜなら、私たちは自動的に正当性をチェックするオラクルを持っているからです。AIコーディングエージェントがツール呼び出しを通じてそのチェックに訴えかけ、言語とコンパイラ設計でしばらく実験した後、形式的に検証されたコンパイラを配信することを想像できます。ただし、チェックは逐次的な関数型プログラムとして実装されており、適度に複雑に見える目標に対しては、メモリを使い果たしたり、効果的にタイムアウトしたりする可能性があります。私たちは、伝統的な低レベルのパフォーマンス最適化されたDatalog実装のようなものを、それでも形式的に検証されたものとして持っていることを本当に望んでいます。実装がより並列であるほど、おそらく良いでしょう。私は、Datalogの実装がどのように機能するか、そして定理証明とプログラム最適化におけるさまざまなクエリをDatalogに削減する方法についての詳細とともに、これらのテーマに後続の記事で戻ってくる予定です。
次に、比較的オープンエンドなCプログラミングのために、論理的に健全なステップで正しいプログラムを段階的に導出するもう1つの例を挙げたいと思います。2週間後にそこに行く前に、来週は、他のAIエージェントの正当性を強制するためにAIエージェントを使用することの増加、そのスタイルの固有の信頼性の弱点、そして形式手法のような決定論的なアプローチがどのように救済に来ることができるかについて、私のスタートアップNectryからの新しいベンチマークスイートで実証しながら、意見を述べます。