カリー＝ハワード同型対応

カリー＝ハワード同型対応（カリー＝ハワードどうけいたいおう、）とは、プログラミング言語理論と証明論において、計算機プログラムと証明との間の直接的な対応関係のことである。「プログラム＝証明」(proofs-as-programs)・「型＝命題」(formulae-as-types)などとしても知られる。これはアメリカの数学者ハスケル・カリーと論理学者により最初に発見された形式論理の体系とある種の計算の体系との構文論的なアナロジーを一般化した概念である。通常はこの論理と計算の関連性はカリーとハワードに帰属される。しかしながら、このアイデアはブラウワー、ハイティング、コルモゴロフらが定式化した直観主義論理の操作的解釈の一種（）と関係している。
一般的な定式化.
もっと一般的な観点からいえば、カリー＝ハワード対応は証明計算と計算模型の型システムとの間の対応である。これは2つの対応に分けられる。ひとつは、論理式と型のレベルであり、これは特定の証明体系や計算模型の選択に依存しない。いまひとつは、形式的証明とプログラムのレベルであり、これは証明体系や計算模型の選択に依存する。
論理式と型のレベルにおいて、この対応によれば、含意は関数型、論理積は直積型（タプル、構造体、リストなど、言語によって様々に呼ばれる）、論理和は直和型（バリアント、共用体、Eitherなど）、偽は空な型、真はシングルトン型のように振る舞うという。量化子は依存直積または直和にそれぞれ対応する。
まとめると、次のような表になる：
証明体系と計算模型のレベルにおいて、この対応は主に構造的な同一性を示す。ひとつはヒルベルト流の推論体系とコンビネータ論理、いまひとつはゲンツェンの自然演繹とラムダ計算との間の同一性である。
自然演繹とラムダ計算との間には次のような対応関係が存在する：
ヒルベルト流の推論体系とコンビネータ論理との間の対応.
この対応はCurry and Fays (1958)に於いて指摘された：最も単純なコンビネータ論理の一種におけるコンビネータ K と S が、驚くべきことにヒルベルト流の証明体系における公理図式 formula_1 と formula_2 とにそれぞれ対応するのである。このことから、しばしば上記の公理図式はそれぞれ K と S と呼ばれる。ヒルベルト流の証明と見做せるプログラムの例が与えられる（後述）。
直観主義論理の含意断片に制限するならば、次のようにヒルベルト流の極めて簡明な形式化が存在する。いま formula_3 を論理式の有限集合として、これを仮定と見做す。論理式 formula_4 が formula_3 から導出可能である（formula_6）とは、以下の場合をいう：
これは推論規則を用いて形式化できる。以下に示す表の左の列を参照されたい。
我々は同様の構文により型付きコンビネータ論理を形式化することができる。いま formula_3 を次の形式の有限集合（ただし同じ変数に異なる型が紐付けられてはならない）として、これを変数の型宣言と見做す。
このとき、CL項 formula_23 が formula_3 のもとで型 formula_4 を持つ（formula_26）とは、以下の場合をいう：
型付きCL項の構成規則は以下に示す表の右の列を参照されたい。カリーは各々の行が同型に対応していることを指摘した。この直観論理との対応の制限は、古典論理の恒真式、例えばパースの法則 formula_40 などがこの対応から締め出されていることを意味する。
もっと抽象的なレベルから見ると、この対応は以下の表のようにして述べ直すことができる。とくに、ヒルベルト流の推論体系における演繹定理（のメタ証明）は、コンビネータ論理における抽象の除去手続きと対応している。
この対応によって、コンビネータ論理の結果をヒルベルト流の推論体系の結果に翻訳できる。その逆もまた同様である。例えば、CL項の簡約はヒルベルト流の証明図の簡約手続きと見ることができる。また、正規なCL項は正規な証明図へと翻訳される。ここで正規とは、これ以上簡約できないことを意味する。正規化定理は型付け可能なCL項は必ず正規形を持つという定理であるが、これはヒルベルト流の証明図は必ず正規形を持つという結果に翻訳できる。
反対に、直観主義論理における例えばパースの法則の証明不能性は、コンビネータ論理における次の結果に翻訳できる：型 formula_40 を持つCL項は存在しない。
コンビネータからなる集合の完全性の結果もまた翻訳できる。例えば、 one-point basis formula_42 は任意のCL項を表現できることが知られている。このコンビネータから公理図式
が得られる。これは formula_42 の主要型（formula_42 の可能な型で代入に関して極小なもの）である。formula_46 コンビネータの完全性から、上に挙げた唯一の公理図式から次の公理図式が証明可能であることが従う：
自然演繹とラムダ計算との間の対応.
ハスケル・カリーがヒルベルト流の体系とコンビネータ論理の構文的対応を強調した後、ウィリアム・アルヴィン・ハワードは1969年に単純型付きラムダ計算と自然演繹との構文的な同型性を明確にした。以下、左辺で直観主義的自然演繹の含意断片を形式化し、右辺でラムダ計算の型付け規則を示す。左辺では formula_49 で順序付けられた論理式の列を表す。右辺ではラムダ項で名前付けられた論理式の列を表す。
この対応を言い換えれば、formula_50 を証明するということは、型宣言列 formula_3 のもとで型 formula_15 を持つオブジェクトを構成することに対応する。公理は新しい変数の導入（とその型宣言）に、→ I 規則は関数抽象に、→ E 規則は関数適用に対応する。もし左辺の文脈 formula_3 を単なる論理式の集合と見做す（暗黙の縮約と弱化を認める）ならば、この対応は正確ではないことが分かる。というのも、例えば formula_3 の中にラムダ項 formula_55 と formula_56 で名前付けられた論理式 formula_57 が属していたならば、右辺ではこれらを区別するが、左辺ではこれを同じものと見做す。
ハワードは他の論理の結合子と単純型付きラムダ項の他の構成との間に対応を拡張できることを示した。例えば論理積との対応は次に示す表のようになる：
もっと抽象的に見ればこの対応は次の表として纏められる。とりわけ、ラムダ計算における正規形の概念は自然演繹におけるプラヴィッツの正規な証明に対応する。型付けられたラムダ項は正規形を持つという結果（正規化定理）は、自然演繹の無矛盾性や論理和分離特性の証明に利用できる。型の具体性の問題の決定手続きを直観主義的な証明可能性の決定手続きに変換できる。
ハワードの対応は自然演繹およびラムダ計算の拡張に対しても自然に延長できる。網羅的ではないがここに列挙しておく：
ハワードの対応はまた自然演繹およびラムダ計算の制限に対しても成り立つ。例えばBCKλ計算とBCK論理の対応が挙げられる。ここでBCKλ計算とは、ラムダ項の構成のうち関数適用の規則を
と制限することにより得られる項書換え系である。これにより自由変数の複数回の使用が禁止される。したがってこの体系は1つの仮定を複数回使用する（縮約規則）ことを禁止するBCK論理と対応する。さらにラムダ項の構成のうちラムダ抽象の規則を
と制限することにより得られる体系はBCI論理と対応する。これにより未使用の変数の束縛が禁止される。したがってこの体系は縮約規則に加えて未使用の仮定を解消する（弱化規則）ことを禁止するBCI論理と対応する。
古典論理と制御演算子との間の対応.
カリーおよびハワードの時代では、「証明＝プログラム」対応は専ら直観主義論理においてのみ考察されていた。すなわち、ここでの論理では、とくにパースの法則は導出不能であった。パースの法則すなわち古典論理を含む明確な対応の拡張はグリフィンの仕事による。グリフィンはプログラムの実行における評価文脈（継続）をキャプチャしそれを再度使用するような制御演算子を持つラムダ計算が古典論理と対応することを指摘した。基本的な古典論理のカリー＝ハワード対応は以下で与えられる。なお、古典論理の証明から直観論理の証明への変換（グリベンコの定理）に用いられる二重否定変換は、制御演算子を持つラムダ項から純粋なラムダ項へのCPS変換に対応する。もっと具体的にいえば、名前呼びCPS変換はコルモゴロフの二重否定変換に、値呼びCPS変換は黒田の二重否定変換に関係する。
パースの法則の代りにシークエントの結論に複数の論理式を許容することによっても古典論理の自然演繹を定義できる。この場合もやはり対応が成立する。例えばある種の古典論理の自然演繹とM. Parigotのλμ計算の間に「証明＝プログラム」の対応が存在する。
シークエント計算.
「証明＝プログラム」対応はゲンツェンのシークエント計算においても確立されるが、ヒルベルト流の体系や自然演繹のように、既に知られていたような計算模型との対応関係は存在しない。
シークエント計算は左導入規則、右導入規則、ならびに除去可能なカット規則により特徴づけられる。シークエント計算の構造はある種の抽象機械の構造に似ている。非形式的な対応は次のようである：
再帰型と自己言及.
命題論理式に次のような構成規則を追加する場合を考える：
この論理式の内容的な意味は循環的命題 formula_63 である。ただし formula_64 なる論理式の内容的意味 formula_65 の中の this は命題全体ではなく formula_66 を指示するものである。すなわち formula_62 とは次の論理式の再帰方程式
の解（[[不動点]]）であるというに他ならない。例えば formula_69 は[[嘘つきのパラドックス]]における嘘つき命題 this sentence is false を意味する論理式である。したがってこの論理体系は矛盾している。
この論理式構成に対応する型構成を[[再帰データ型|再帰型]]という。例えば可変長リスト型は再帰型として実現できる：
ここで 1 はトップ型である。この型システムでは [[不動点コンビネータ#Yコンビネータ|Yコンビネータ]] や formula_71 などの項も型を持つことになる。これらの項は通常の型システムでは型を持たない。なおコンビネータ formula_72 の（主要型の）型付けの導出は[[カリーのパラドックス]]の自然演繹による証明と対応する。
以上の体系の対応は次のように纏められる：
<br>
「証明＝プログラム」対応に関連する話題.
ド・ブランの役割.
[[ニコラース・ホーバート・ド・ブラン]]はラムダ記法を証明検証器[[Automath]]において用い、また命題をその証明の類として表現した。これはハワードが（CH対応に関する）原稿を書いた同時期の1960年後半のことであった。ド・ブランはハワードの仕事を知らず独立してこの対応を述べた（Sørensen & Urzyczyn [1998] 2006, pp 98–99）。一部の研究者は、カリー＝ハワード対応という代りにカリー＝ハワード＝ド・ブラン対応という語を使用する。
BHK解釈.
[[BHK解釈]]は直観主義的な証明の含意と全称化を関数として解釈するが、解釈における関数のクラスがどのようなものであるかを指定してはいない。もし関数のクラスとしてラムダ計算を取るならば、BHK解釈は自然演繹とラムダ計算との間の対応と同じことを述べていることになる。
実現可能性解釈.
[[スティーヴン・コール・クリーネ]]の[[実現可能性解釈]]は、直観主義的[[自然数論|算術]]の証明を[[再帰的関数]]とその関数が論理式を実現していることを表す論理式の証明とに分離する。これにより、例えば「任意の自然数 a と b に対して、a と b を割り切る最大の自然数 c が存在する」ことを直観主義的に証明できたならば、ここから最大公約数を計算する再帰的関数と、それが最大公約数を計算していることの証明を抽出できる。
[[ゲオルク・クライゼル]]により変更された実現可能性解釈を高階の直観主義論理に適用することで、もとの論理式の証明からそれを実現する単純型付けされたラムダ項を帰納的に抽出できることが示せる。命題論理の場合、これはカリー＝ハワード対応のステートメントと一致する：抽出されたラムダ項はもとの証明（をラムダ項と見做したもの）と一致し、実現可能性のステートメントは抽出されたラムダ項がもとの論理式の意味する型を持つということの言い換えである。
[[クルト・ゲーデル]]の[[ディアレクティカ解釈]]は計算可能汎関数を備えた直観主義的算術（のある拡張）を実現する。これのラムダ計算との繋がりは自然演繹ほど明白ではない。
カリー＝ハワード＝ランベック対応.
[[ヨアヒム・ランベック]]は1970年始めに直観主義命題論理と[[デカルト閉圏]]の等式理論と対応するある種の型付きコンビネータとの対応関係の証明を示した。このカリー＝ハワード＝ランベック対応は直観主義論理、型付きラムダ計算およびデカルト閉圏との間の対応として知られる。ここでは[[圏_(数学)|オブジェクト]]は型あるいは命題に、[[射 (圏論)|モルフィズム]]は項あるいは証明に解釈される。この対応は等号レベルに於いて働き、カリー＝ハワード対応にあるような構文的・構造的同等性を表現しない：すなわち、デカルト閉圏のモルフィズムの構造と、対応する判定のヒルベルト流あるいは自然演繹の証明の構造と比較することはできない。もちろん構文的に対応するような証明体系を構成することはできる。この区別を明確にするために、デカルト閉圏の構文的な構造を次のように言い換える。すなわちデカルト閉圏を型付きの等式理論として形式化する。
オブジェクト（型）は次のように帰納的に定義される：
モルフィズム（項）は次のように帰納的に定義される：
Well-definedなモルフィズム（型付きの項）は以下の型付け規則にしたがって構成される：
恒等射：
合成:
終対象:
直積:
射影:
[[カリー化]]:
評価:
最後に、圏の等式を次により定める：
このとき、formula_100 なるモルフィズム formula_83 が存在することと、formula_102 なるシークエントが直観論理の含意論理積断片で証明可能であることとは同値である。上記のデカルト閉圏の射の等式体系として得られる計算模型は[[カテゴリカルコンビネータ]]あるいは圏的コンビネータ論理として知られる。
例.
カリー＝ハワード対応により、型付けられた表現は対応する論理式の証明と見做すことができる。以下、いくつかの例を与える。
恒等コンビネータと α → α のヒルベルト流の証明.
簡単な例として formula_103 のヒルベルト流の証明を構成する。ラムダ計算では、これは恒等関数 formula_104 の型であり、コンビネータ論理では恒等関数は formula_105 と formula_106 により formula_107 （ただし慣例によって適用は左結合と見做す）と表現できる。以上の説明は formula_108 の証明の構成を与えている。実際、この論理式は次のようにしてヒルベルト流の証明体系にて証明可能である（慣例に従い含意記号は右結合と見做す）：
合成コンビネータと (β → α) → (γ → β) → γ → α のヒルベルト流の証明.
もっと複雑な例として、formula_113 コンビネータに対応する定理を示そう。formula_113 の型は formula_115 である。formula_113 は formula_117 に対応する（この事実は抽象除去などを用いて得られる）。これは目的の定理の証明の道筋を与えている。
まず formula_118 を構成する。公理 formula_106 の前にまず公理 formula_105 の形を見る。そして公理 formula_106 の formula_15 に公理 formula_105 の論理式を代入する。すると次が得られる：
ここで formula_126 とモーダス・ポネンスにより、
次にこの論理式と公理 formula_105 の最初の部分 formula_129 とが同一になるような代入を求め（[[ユニフィケーション]]）、
を得る。これと先の論理式にモーダス・ポネンスを適用すれば、
この論理式の最初の部分 formula_132 と公理 formula_133 とが同一になるような代入を求めれば、それは formula_134 であるから、
最後にこれらにモーダス・ポネンスを適用すれば次を得る：
適当に命題変数の名前を付け替えれば所望の論理式の証明が得られる。
(β → α) → (γ → β) → γ → α の自然演繹における証明とラムダ項.
次の図は formula_138 の自然演繹における証明である。簡単のため、文脈 formula_139 は省略してある。
formula_140
この証明が型付きラムダ項 formula_141 と解釈できることは明らかである。なお、前述の formula_138 のヒルベルト流の証明は、自然演繹におけるこの証明に対して抽象の除去と[[ラムダ計算#η-変換|η変換]]を何度か使用することで得られる。
その他の応用.
最近ではカリー＝ハワード対応が[[遺伝的プログラミング]]における探索空間のパーティションを定義する方法として提案されている。この手法は遺伝子型（システムにより進化するプログラムの木）の集合に対して（種と呼ばれる）カリー＝ハワード対応する証明を索引付ける。
外部リンク.
[[Category:証明論]]
[[Category:理論計算機科学]]
[[Category:型理論]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]
[[Category:計算機科学哲学]]