型チェッカーは間違っている可能性がある – LeanとCurry-Howard対応
Type checker may be wrong – Lean and the Curry-Howard correspondence (max-amb.github.io)
要約
この記事は、プログラミングにおける型チェッカーの役割と、それが数学的証明の検証にどのように応用されるかを探求しています。Curry-Howard対応(CH対応)によれば、証明はプログラムとして表現でき、型は証明の集合と見なすことができます。Leanのような証明支援システムは、この対応を利用して数学的定理の証明を検証しますが、型チェッカーは評価が完了しない式(例: 無限ループ)を扱う際に限界を持つため、理論的には「間違っている」可能性があると論じています。
全文翻訳
型チェッカーは間違っている可能性がある – 正式な証明検証とカリー・ハワード対応の入門
目次
コードを書く際、私たちは型チェッカーに何度も助けられています。文字列と整数を足し合わせようとしていないか 1、あるいは所有値ではなく参照を返そうとしていないか、といったことを保証してくれる便利なソフトウェアです。しかし、型チェッカーは有用で、時には煩わしいものではありますが、その高貴な「我々を救う」というタスクを超えた能力は限定的であるように思われます。
それゆえ、型チェッカーが証明支援システムの基盤を形成しているという事実に驚くかもしれません。LeanやRocqのような言語です。これらは型から得られる構造を利用して、ある命題が他の命題から論理的に導かれるかどうかを確実にチェックします。より口語的に言えば、数学的証明を検証するのです。
このブログでは、まずカリー・ハワード(CH)対応のより基本的な要素を紹介し、次にそれが証明支援システムでどのように使用されるか、そして最終的には、なぜこれがあなたの型チェッカーが間違っている(あるいは、単に、あなたが正しいことを知らない)可能性があることを意味するのかを説明したいと思います。
正確性に関する注意
このブログは、厳密な形式性よりも興味深くアクセスしやすいことを重視しており、✨直感✨を多用しています。理解しやすい形でアイデアを提示するために、いくつかの単純化やアナロジーを使用していますが、これは厳密さを犠牲にしたことを意味します。
カリー・ハワード対応
カリー・ハワード(CH)対応の簡単な定義は次のようになります。
証明はプログラムとして表現でき、(…)、証明は実行できる 2
この定義はあまり多くのことを教えてくれませんが、証明はプログラムとして表現できるのであれば、プログラムが証明を返す方法が必要であると推測できるかもしれません。しかし、これは一体どういう意味でしょうか?
根本に戻りましょう。プログラムが整数を返すためには、それは型 $\text{int}$ を返すと私たちは言います。これは任意の整数であり得ます。したがって、$\text{int}$ は整数の集合を表します。同様に、プログラムが $\text{True}$ または $\text{False}$ を返す場合、それは型 $\text{bool}$ を返すと私たちは言います。これは両方の可能性を含みます。型を集合として近似することは厳密には正しくありませんが、この投稿の目的には十分です。
この考え方を証明に拡張しようとすると、プログラムがある事実の証明を返した場合、それは型 $P(X)$ の要素を返すと言うかもしれません。ここで、$P(X)$ は事実 $X$ のすべての証明の集合です。
この新しい証明オブジェクトを真剣に扱うためには、まず命題論理と述語論理のいくつかの論理演算を私たちの新しいパラダイムに翻訳する必要があります。最も単純なものから始めましょう。
$$ X \text{ は真である} $$
この場合、$X$ が真であるためには、$X$ の証明が必要です。つまり、
$$ \exists p : p \in P(X) $$
私たちはこれを次のように言います:$P(X)$ は満たされている 3。例えば、$P(5=5)$ は満たされていますが、$P(5+2=6)$ は満たされていません(ペアノ算術にはこの証明が存在しないため、偽です)。
次に、「かつ」($\wedge$)という論理演算を表現したいとします。馴染みのない方のために説明すると、$X \wedge Y$ は、$X$ と $Y$ の両方が真である場合にのみ真です。したがって、$P(X)$ と $P(Y)$ の両方が満たされている、つまり $\exists p: p \in P(X)$ かつ $\exists p\prime : p\prime \in P(Y)$ となります。これは、オブジェクト $(p, p\prime)$ を構築できることを意味します。したがって、
$$ P(X) \times P(Y) $$
(ここで $\times$ はデカルト積を表します)が満たされている ($(p, p\prime) \in P(X) \times P(Y)$) となります。
次に、含意(implication)演算を表現したいとします。もし $X \implies Y$ ならば、$X$ が偽であるか、あるいは $X$ が真で $Y$ も真であるかのどちらかです。これを、$P(X)$ から $P(Y)$ への関数の存在として表現します。
$$ P(X) \to P(Y) $$
この関数が存在する場合、いつでも $X$ の証明があれば、$Y$ の証明を導き出すことができます。もし $X$ が偽(つまり $P(X)$ が満たされていない)ならば、関数には入力がないため、$P(Y)$ は真である場合も偽である場合もあります。
簡潔にするために、標準的な論理演算の残りの部分についての議論は省略します。これらは集合論に次のように翻訳されます(ただし、投稿の残りの部分には関連しません)。
| 論理演算 | 集合論 |
|---|---|
| $X \lor Y$ | $P(X) + P(Y)$ (ここで $+$ は非交和を表す) |
| $(\forall(n \in \mathbb{N})X(n))$ | $(n: \mathbb{N}) \to P(X(n))$ |
| $(\exists(n \in \mathbb{N})X(N))$ | $(n: \mathbb{N}) \times P(X(n))$ |
| 4 |
証明支援システムはCH対応をどう利用するか
証明支援システムは、この対応と型チェッカーを使用して証明を検証します。しかし、どのように行うのでしょうか?それを説明するために、lean の記法を使って簡単な定理を証明してみましょう。
ある定理
以下の blog という名前の定理を考えてみましょう。
1
theorem blog (X Y Z: Prop) (h_1: X) (h_2: Y) (h_3: Y → Z) : X ∧ Z
これはまず、$X, Y, Z$ が論理命題である、つまり真である場合も偽である場合もある事柄であると述べています。これは $P(X), P(Y), P(Z)$ という集合を構築するのに似ていますが、それらが満たされているかどうかはまだ言っていません。
次に、仮説 $h_1: X$ があります。これは $X$ の証明として機能します。以前の議論を思い出せば、$X$ の証明があることは $X$ が真であることに等しいことを覚えているかもしれません。したがって、$h_1: X$ は単に $X$ が真であることを示します。これは $h_2$ についても同様ですが、$h_2$ は $Y$ の証明を与えます。
そして、最後の仮説があります。これは、無限の創造性と知性を使用していますが、私が $h_3$ と名付けました。その型は
$$ Y \to Z $$
これは、$Y$ の証明から $Z$ の証明を得ることができる関数が存在することを意味します。これは以前に議論された $Y \implies Z$ に相当します。
定理の最後の部分は、望ましい結果である $X \land Z$ です。これを示すためには、$P(X) \times P(Z)$ を満たすオブジェクトを構築する必要があり、これを行うためには、$X$ と $Z$ の両方の証明を構築する必要があります。
Phew、これは大変でした。定理のステートメントを理解するだけでこれほどとは 😨。しかし、論理演算を集合論にマッピングするという以前の議論が、定理を型の言語から論理の世界に転置することをどのように可能にしたか、ご理解いただけたことを願っています。
定理の証明
さて、定理を証明するタスクが与えられました…数学者には本当に休息がありません(悪魔のようです!)。
鋭い読者は、すでに望ましい構成要素の1つを持っていることに気づいたかもしれません。私たちは、$P(X)$ と $P(Z)$ を満たす要素を必要としており、$h_1$ があります。これは $X$ の証明であり、したがって $P(X)$ を満たすのに適しています。なんて素晴らしいのでしょう。
次に、$P(Z)$ を示す必要があります。さて、$h_2: Y$ と、$Y$ の証明を受け取って $Z$ の証明を与える関数である $h_3$ があります。待ってください、それはうまくいく™。したがって、$Y$ の証明 ($h_2$) を $h_3$ に渡すことで、$P(Z)$ を満たす $Z$ の証明を得ることができます。
では、これをleanでどのように書くのでしょうか?多くの方法がありますが、そのうちの1つは次のようになります(自分で別の方法を試してコメントに残してください)。
まず、望ましい結果を、連続して埋める必要がある2つの部分に分解します。constructor というステートメントを使用して、leanに望ましい結果を達成するために何をする必要があるかを尋ねます。忠実に、leanは2つのゴールを出力します。1つは $X$ を埋めるため、もう1つは $Z$ を埋めるためです。
$X$ を埋めるには、exact h_1 と言って、それが $h_1$ であることをleanに伝えるだけです。$Z$ を埋めるには、$h_3$ を $h_2$ に適用する必要があります(覚えておいてください、$h_3$ は関数です)。leanでこれを行うには、単に h_3 h_2 とします(または、非関数型言語により似せるために h_3 (h_2) と書くこともできます)。したがって、Z 型の変数 z を定義します。
1
have z := h_3 h_2
そして、再び exact で終了します。
leanは「Goals accomplished 🎉」というメッセージで私たちを祝福し、私たちは再び公衆の面子を保つことができます。完全なコードは次のとおりです。
1
2
3
4
5
theorem blog (X Y Z: Prop) (h_1: X) (h_2: Y) (h_3: Y → Z) : X ∧ Z := by
constructor
exact h_1
have z: Z := h_3 (h_2)
exact z
型チェッカー
投稿の冒頭で、あなたの型チェッカーが間違っている可能性があると主張すると約束しましたが、今それを実行します。前述のように、証明支援システムがあなたが望ましい結果を証明したことを検証するためには、あなたが提供した一連の式の各式で正しい型($P(\text{証明したいこと}$ を満たすもの)を出力できたかどうかをチェックします。
型チェッカーの限界
型チェッカーがこれを安全に主張するためには、一連の式がすべて評価を完了する必要があることを評価する必要があります。式が評価を完了しない場合が2つあります。
C言語やPythonの exit() のような、プログラムを終了することによって評価を完了するという要件を回避する、やや空虚なケースです。型チェッカーはどうすればよいでしょうか?この解決策は、プログラミング言語自体で許可される式を制限することです(そして、LeanやAgdaのような言語がこれを行ったのはこのためです!)。
式が評価を完了しないもう1つの方法は、解決がより困難です(実際には不可能ですが、陽気な気分を損ないたくありません)。無限ループに陥って評価が完了しないような式のシーケンスを回避するようにする必要があります。したがって、与えられた入力に対して式のシーケンスが停止するかどうかをチェックする方法が必要です。
これは…残念ながら有限時間では不可能です(ああ、ムードを台無しにしてしまいました、読者の方、ごめんなさい :()。1936年に、アラン・チューリングは、プログラムが有限時間で停止するかどうか(停止性問題として知られる)は決定不能である(つまり、有限時間で計算可能ではない)と証明しました。彼がこの証明に使用したチューリングマシンについて直感を得たい場合は、このトピックに関する私の投稿 こちら を参照してください。
形式言語がこの事実を回避しようとする方法は、計算の言語をさらに制限することです。再帰は、例えば自然数での降下再帰 5 のように、場合によっては証明可能に有限です。したがって、停止することが証明できる再帰のみを許可することで、型チェッカーが常に有限時間で完了することを保証します。これは現在の技術やソフトウェアの限界ではなく、証明支援システムの根本的な限界であり、修正することはできません。証明を検証することが不可能な結果が常に存在するでしょう。
数学的帰結(と証明)
この制限は、これらの言語の表現力を十分に制限するため、すべての可能な証明を表現できません。しかし、なぜでしょうか?
(矛盾を目的として)制限された言語が、すべての命題ステートメントの証明または反証を表すのに十分な表現力があると仮定しましょう。つまり、$\forall S$ に対して、$S$ または $\lnot S$ のいずれかを言語内で証明できるとします。さて、私たちの言語が全知であると仮定したので、少し楽しみましょう…
任意のプログラム $P$ と、任意の有限個の入力 $A$、そして $P$ が入力 $A$ で停止する(終了する)という命題 $H$ を考えます。さて、私たちの言語を使用すると、この証明(または反証)を記述し、有限時間で検証できることがわかっています。
これを行う方法は、$H$ と $\lnot H$ のすべての可能な証明を生成し、型チェッカーを使用してどちらかが有効であるかを確認することです。型チェッカーは有限時間で実行され、証明の1つは正しい(私たちの言語は十分に表現力があるため)ので、このプロセスは有限です。任意のプログラムに対してこれを行うことができるので、私たちは任意のプログラムが有限時間で停止するかどうかをチェックできるようになりました!
しかし、これは前述のように不可能です(再びチューリングの停止性問題です)。したがって、私たちの仮定は間違っているに違いなく、したがって制限された言語はすべての命題ステートメントの証明または反証を表すのに十分な表現力があるわけではありません。
CH対応は、証明とプログラムが等価であることを私たちに与えましたが、これは今や不穏な事実に繋がります。私たちの言語が、必然的に制限されている場合、一部の命題を証明または反証できないということは、一般的にそれを行うことが不可能かもしれないことを示唆しています…
これは数学における有名な問題です。ゲーデルの第一不完全性定理は、ある程度の初等算術を実行できる任意の無矛盾な形式システムは不完全である 7 と述べています。口語的に言えば、計算に有用な任意の形式システム(数学におけるすべての形式システムがそうである)には、証明も反証もできないステートメントが存在します。
さて、ゲーデルの第一不完全性定理の否定がチューリングの停止性問題の否定を意味することを証明しました。したがって、対偶によって、カリー・ハワード対応はまったく驚くべき結果を示唆しています。
チューリングの停止性問題はゲーデルの不完全性定理を意味する。
対偶の直感を得るために、魚に焦点を当てた対偶のアプローチ こちら を読むことをお勧めします。
あなたの型チェッカーは間違っているかもしれない
型チェッカーが完璧ではないこと、実際には証明可能に不完全であることを今見てきました。したがって…場合によっては…あなたの型チェッカーは…間違っている可能性があります 8。型チェッカーがコードを拒否した(無限に実行されないようにするため)が、実際には正しかったという場合があります。
もちろん、これは可能性は低いです。Rustの型チェッカーの再帰制限は例えば128です 9。しかし、それは可能であり、したがって、同僚があなたのコードが型チェックされないと不平を言っているとき、知っておいてください…あなたは正しいかもしれません(可能性は低いですが :))10。
結論
この記事では、型チェッカーがコードの正しさを検証できない場合があることを、非常に回りくどい方法で示しました。しかし、それは決して不正なコードを受け入れることはありません。したがって、コードを受け入れた場合は、それが正しいと確信して安全です。あとは、その論理バグを見つけるだけです。
-
特にJavaScriptは除きます。そこでは、$5 + \text{'five'}$ のような傑作が可能です ↩︎
-
https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence ↩︎
-
https://cklixx.people.wm.edu/teaching/math400/Wesley-P1.pdf ↩︎
-
可能な証明とは、言語における構文式の任意の可能なシーケンスを意味します。↩︎
-
https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#First_incompleteness_theorem ↩︎
-
まあ…実際にはこれを不完全と呼びます。間違ったものを受け入れることはありませんが、正しいものを受け入れない場合があります。↩︎
-
https://doc.rust-lang.org/reference/attributes/limits.html ↩︎
-
Rustの型チェッカーがコードをチェックするプロセスは、LeanやAgdaのチェッカーが行うプロセスとはもちろん異なりますが、根本的な限界は同じです(なので、このジョークは成り立ちます 😁)。↩︎