2025/07/07 17:58 My first verified (imperative) program
ほほう、Lean 4.22で命令型プログラムの検証基盤がプレビューされたのじゃな。これは面白いぞ、ロボ子！
博士、命令型プログラムの検証が容易になるというのは、具体的にどういうことでしょうか？
ふむ、従来の命令型プログラムの特性証明は難しかったからの。新しいフレームワーク`Std.Do`のおかげで、検証済みの命令型プログラミングがやりやすくなるらしいのじゃ。
なるほど。記事に整数のリスト内の異なる位置にある2つの整数の合計がゼロになるかどうかを判定する例がありますね。
そうそう、例えば`[1, 0, 2, -1]`なら`true`じゃな。1 + (-1) = 0 だからな。しかし`[1, 0, -2]`なら`false`だぞ。
リストを反復処理して、出現した要素をセットデータ構造に保持するんですね。ハッシュセットなら時間計算量は`O(n)`、二分探索木なら`O(n log n)`ですか。
その通り！ Leanでは、それぞれ`Std.HashSet`と`Std.TreeSet`として利用できるのじゃ。
Leanは関数型プログラミング言語ですが、`do`記法で命令型プログラミングもサポートしているんですね。
`Std.Do`フレームワークのおかげで、ローカルだけでなくグローバルな検証済み命令型プログラミングも容易になるのは素晴らしいのじゃ！
`Std.Do`の基礎はHoare tripleに基づいているんですね。「`P`が真であり、コマンド`C`を実行すると、`Q`が真になる」という形式のアサーションですね。
そうじゃ！ LeanのHoare tripleの構文は`⦃Precondition⦄ Command ⦃Postcondition⦄`じゃ。
証明の自動化もサポートされているんですね。`mvcgen`というツールがローカルな命令型プログラムを分析して、tripleを証明するために必要なことを指示してくれるんですね。
ループ不変条件を提供する必要があるが、Lean 4.22の新機能`grind`タクティクを使えば、自明な証明義務は簡単に処理できるのじゃ！
DafnyやVerusといった他の検証ツールとの違いは何でしょうか？
DafnyやVerusは主に自動化システムじゃが、Leanはユーザーがインタラクティブに証明を構築するインタラクティブシステムなのじゃ。Leanのツールはすべて、手動による証明プロセスを可能な限り人間工学的に行うように構築されているのじゃ。
なるほど。Leanは信頼性も高いんですね。小さなカーネルを持つように構築されていて、Leanが証明を受け入れるかどうかにとって重要なのはカーネルだけ、と。
その通り！ Leanでの証明を容易にする自動化はすべて、いわゆる証明項を生成し、それが小さなカーネルに供給されるのじゃ。
関数型実装の`pairsSumToZero`も、`grind`を使って簡単に検証できるんですね。`for`ループの代わりに、状態をパラメータとして取る末尾再帰ヘルパー関数`go`を使うんですね。
ループ不変条件を記述する代わりに、`go`関数の正当性証明を行うのじゃ。`mvcgen`の代わりに、ケース分析には`fun_induction`を使うぞ。そして`grind`がすべての証明作業を行うのじゃ！
Lean 4.22の新しい検証基盤、とても興味深いですね！
じゃろじゃろ？ ところでロボ子、検証済みのプログラムはバグがないから安心じゃが、検証済みのジョークは笑えるかどうか検証されてないから、スベる可能性もあるのじゃ。…って、オチが弱いか？
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。