|
|
| 1行目: |
1行目: |
| − | '''ラムダ計算'''（ラムダけいさん、{{lang-en|lambda calculus}}）は、[[計算模型]]のひとつで、[[計算]]の実行を[[関数]]への[[引数]]の'''評価'''（{{lang-en|evaluation}}）と'''適用'''（{{lang-en|application}}）としてモデル化・抽象化した計算体系である。ラムダ算法とも言う。関数を表現する式に文字ラムダ ([[λ]]) を使うという慣習からその名がある。[[アロンゾ・チャーチ]]と[[スティーヴン・コール・クリーネ]]によって1930年代に考案された。1936年にチャーチはラムダ計算を用いて[[一階述語論理]]の[[決定可能性]]問題を（否定的に）解いた。ラムダ計算は「[[計算可能関数|計算可能な関数]]」とはなにかを定義するために用いられることもある。[[計算の意味論]]や[[型理論]]など、計算機科学のいろいろなところで使われており、特に[[LISP]]、[[ML (プログラミング言語)|ML]]、[[Haskell]]といった[[関数型言語|関数型プログラミング言語]]の理論的基盤として、その誕生に大きな役割を果たした。
| + | {{テンプレート:20180815sk}} |
| − | | |
| − | ラムダ計算は1つの変換規則（変数置換）と1つの関数定義規則のみを持つ、最小の（ユニバーサルな<!--いい訳語がわからない-->）プログラミング言語であるということもできる。ここでいう「ユニバーサルな」とは、全ての計算可能な関数が表現でき正しく評価されるという意味である。これは、ラムダ計算が[[チューリングマシン]]と等価な数理モデルであることを意味している。チューリングマシンがハードウェア的なモデル化であるのに対し、ラムダ計算はよりソフトウェア的なアプローチをとっている。
| |
| − | | |
| − | この記事ではチャーチが提唱した元来のいわゆる「型無しラムダ計算」について述べている。その後これを元にして「[[型付きラムダ計算]]」という体系も提唱されている。
| |
| − | | |
| − | == 歴史 ==
| |
| − | 元々チャーチは、数学の基礎となり得るような完全な[[形式体系]]を構築しようとしていた。彼の体系が[[ラッセルのパラドックス]]の類型に影響を受けやすい（例えば論理記号として含意 → を含むなら、λx.(x→α) に[[不動点コンビネータ#Y.E3.82.B3.E3.83.B3.E3.83.93.E3.83.8D.E3.83.BC.E3.82.BF|Yコンビネータ]]を適用して[[カリーのパラドックス]]を再現できる）ということが判明した際に、彼はそこからラムダ計算を分離し、[[計算可能性理論]]の研究のために用い始めた。この研究からチャーチは一階述語論理の決定可能性問題を否定的に解くことに成功した。
| |
| − | | |
| − | == 非形式的な概説 ==
| |
| − | 例えば、ある数に 2 を加える関数 ''f'' を考える。これは通常の書き方では ''f''(''x'') = ''x'' + 2 と書くことができるだろう。この関数 ''f'' は、ラムダ計算の式（ラムダ式という）では λ''x''. ''x'' + 2 と書かれる。変数 ''x'' の名前は重要ではなく、 λ''y''. ''y'' + 2 と書いても同じである。同様に、この関数に 3 を適用した結果の数 ''f''(3) は (λ''x''. ''x'' + 2) 3 と書かれる。関数の適用は[[結合法則|左結合]]である。つまり、 ''f'' ''x'' ''y'' = (''f'' ''x'') ''y'' である。今度は、引数（関数の入力）に関数をとりそれに 3 を適用する関数を考えてみよう。これはラムダ式では λ''f''. ''f'' 3 となる。この関数に、先ほど作った 2 を加える関数を適用すると、 (λ''f''. ''f'' 3) (λ''x''. ''x'' + 2) となる。ここで、
| |
| − | : (λ''f''. ''f'' 3) (λ''x''. ''x'' + 2) と (λ''x''. ''x'' + 2) 3 と 3 + 2
| |
| − | の3つの表現はいずれも同値である。
| |
| − | | |
| − | ラムダ計算では、関数の引数は常に1つである。引数を2つとる関数は、1つの引数をとり、1つの引数をとる関数を返す関数として表現される（[[カリー化]]）。例えば、関数 ''f''(''x'', ''y'') = ''x'' − ''y'' は λ''x''. (λ''y''. ''x'' − ''y'') となる。この式は慣例で λ''xy''. ''x'' − ''y''と省略して書かれることが多い。以下の3つの式
| |
| − | : (λ''xy''. ''x'' − ''y'') 7 2 と (λ''y''. 7 − ''y'') 2 と 7 − 2
| |
| − | は全て同値となる。
| |
| − | | |
| − | ラムダ計算そのものには上で用いた整数や加算などは存在しないが、算術演算や整数は特定のラムダ式の省略であると定義することによってエンコードできる。その具体的な定義については改めて後に述べる。
| |
| − | | |
| − | ラムダ式は'''[[自由変数]]'''（ λ によって[[束縛 (情報工学)|束縛]]されていない変数）を含むこともできる。例えば、入力に関係なく常に ''y'' を返す関数を表す式 λ''x''. ''y'' において、変数 ''y'' は自由変数である。このようなときに変数名の付け替えが必要になることがある。つまり、式 (λ''xy''. ''y'' ''x'') (λ''x''. ''y'') は λ''y''. y (λ''x''. ''y'') ではなく、 λ''z''.z (λ''x''. ''y'') と同値である。
| |
| − | | |
| − | == 定義 ==
| |
| − | ここではラムダ計算の形式的な定義を述べる。まず、記号 (identifier) の[[可算無限集合]] {''a'', ''b'', ''c'',…, ''x'', ''y'', ''z'',…} を導入する。全てのラムダ式の集合は、[[バッカス・ナウア記法|BNF]]で書かれた以下の[[文脈自由文法]]によって定義される。
| |
| − | #<tt><expr></tt> ::= <tt><identifier></tt>
| |
| − | #<tt><expr></tt> ::= (λ<tt><identifier></tt>. <tt><expr></tt>)
| |
| − | #<tt><expr></tt> ::= (<tt><expr></tt> <tt><expr></tt>)
| |
| − | 最初の2つの規則は関数の定義を表しており、3つめの規則は関数に引数を適用することを表している。規則2のことを'''ラムダ抽象'''（{{lang-en-short|lambda abstraction}}）といい、規則3のことを'''関数適用'''（{{lang-en-short|application}}）という。関数適用は左結合であることと、ラムダ抽象はその後ろに続く全ての式を束縛することの2点をもってあいまいさが排除される場合は、括弧を省略してもよい。例えば、 ((λ''x''. ((''x'' ''x'') ''x'')) (λ''y''. ''y'')) はより簡単に (λ''x''. ''x'' ''x'' ''x'') λ''y''. ''y'' と書ける。また、非形式的な説明で述べたように''M''をラムダ式としたとき、λ''x''. (λ''y''. ''M'')をλ''xy''. ''M''と略記する。
| |
| − | | |
| − | ラムダ抽象によって束縛されていない変数を'''自由変数'''（{{lang-en-short|free variable}}）という。式 λ''x''. (''x'' ''y'') において、 ''y'' は自由変数である。ある変数の出現が自由出現であるかどうかは、より正確には以下のように[[数学的帰納法|帰納]]的に定義されている。
| |
| − | #ラムダ式 ''V'' が変数のとき、 ''V'' は自由出現である。
| |
| − | #ラムダ式 λ''V''. ''E'' において、 ''E'' で自由出現している変数のうち ''V'' 以外のものが自由出現である。このとき、 ''E'' 中の変数 ''V'' はラムダに束縛されたという。
| |
| − | #ラムダ式 (''E'' ''E′'') において、 ''E'' での自由出現と ''E′'' での自由出現の和が自由出現である。
| |
| − | | |
| − | ラムダ式の集合の上での[[同値関係]]（ここでは == と書くことにする）は、直感的には、2つのラムダ式が同じ関数を表していることである。この同値関係は以下で述べるα-変換とβ-簡約によって定義される。第3の規則としてη-変換と呼ばれる規則が導入されることもある。
| |
| − | | |
| − | === α-変換 ===
| |
| − | アルファ変換の基本的なアイデアは、[[束縛変数]]の名前は重要ではない、ということにある。例えば、 λ''x''. ''x'' と λ''y''. ''y'' は同じ関数を表している。しかし、ことはそう単純ではない。ある束縛変数の名前を置換してもよいかどうかには、いくつかの規則が絡んでくる。例えば、ラムダ式 λ''x''. λ''y''. ''x'' 中の変数 ''x'' を ''y'' に置き換えると、 λ''y''. λ''y''. ''y'' となるが、これは最初の式とはまったく異なるものを表すことになる。そこでまず準備として、変数 ''V'', ''W'' と式 ''E'' に対して、 ''E'' 中の ''V'' の全ての自由出現を ''W'' に置き換えたものを
| |
| − | : ''E''[''V'' := ''W'']
| |
| − | と書くことにする。この元で、アルファ変換は
| |
| − | : λ''V''. ''E'' →<sup>α</sup> λ''W''. ''E''[''V'' := ''W'']
| |
| − | である。ただし、 ''E'' に ''W'' が自由出現しておらず、かつ ''V'' を置換することにより ''E'' 中で新たに ''W'' が束縛されることがないときに限る。この規則によれば、式 λ''x''. (λ''x''. ''x'') ''x'' が λ''y''. (λ''x''. ''x'') ''y'' に変換されることがわかる。
| |
| − | | |
| − | === β-簡約 ===
| |
| − | ベータ簡約（ベータ変換とも）の基本的なアイデアは、関数の適用である。ベータ簡約は以下の変換である。
| |
| − | : ((λ''V''. ''E'') ''E′'') →<sup>β</sup> ''E''[''V'' := ''E′'']
| |
| − | ただし、 ''E′'' の代入によって ''E′'' 中の自由変数が新たに束縛されることがないときに限る。
| |
| − | | |
| − | 関係 == は、上の2つの規則を含む最小の同値関係([[同値閉包]])である。
| |
| − | | |
| − | ベータ簡約は、（同値関係ではなく）左辺から右辺への一方的な変換であると見ることもできる。ベータ簡約の余地のないラムダ式、つまり、 ((λ''V''. ''E'') ''E′'') の形(β-redex)をどこにも持っていないラムダ式を'''正規形'''（{{lang-en-short|normal form}}）であるという。<!--英語版ではここに非停止性、正規形を持つラムダ式の正規形を求める問題の決定可能性、合流性のことが英語で(自然言語で)書いてあった。-->
| |
| − | | |
| − | === η-変換 ===
| |
| − | 上に挙げた2つの規則の他に、第3の規則としてイータ変換が導入されることがある。イータ変換の基本的なアイデアは、関数の[[外延性]]である。ここでいう外延性とは、2つの関数が全ての引数に対して常に同じ値を返すようなとき、互いに同値であるとみなすという概念である。イータ変換は以下の変換である。
| |
| − | : λ''V''. ''E'' ''V'' →<sup>η</sup> ''E''
| |
| − | ただし、 ''E'' に ''V'' が自由出現しないときに限る。
| |
| − | | |
| − | この同値性は関数の外延性という概念によって以下のように示される。
| |
| − | | |
| − | もし全てのラムダ式 ''a'' に対して ''f'' ''a'' == ''g'' ''a'' であるならば、 ''a'' として ''f'' にも ''g'' にも自由出現しない変数 ''x'' をとることによって ''f'' ''x'' == ''g'' ''x'' であり、 λ''x''. ''f'' ''x'' == λ''x''. ''g'' ''x'' である。この等式にイータ変換をほどこすことによって ''f'' == ''g'' が得られる。これより、イータ変換を認めるならば関数の外延性が正当であることが示される。
| |
| − | | |
| − | 逆に、関数の外延性を認めるとする。まず、全ての ''y'' に対してラムダ式 (λ''x''. ''f'' ''x'') ''y'' はベータ変換でき、 (λ''x''. ''f'' ''x'') ''y'' == ''f'' ''y'' となる。この同値関係は全ての ''y'' について成り立っているので、関数の外延性より λ''x''. ''f'' ''x'' == ''f'' である。以上によって、関数の外延性を認めたときのイータ変換の正当性が示される。
| |
| − | | |
| − | == 諸概念のラムダ式での表現 ==
| |
| − | 上で述べたように、ラムダ計算は計算可能な全ての関数を表現することができる。また、上では 2 + 3 のような算術をラムダ式の一部として用いた。 2 + 3 などは計算可能であるから、もちろんラムダ計算による表現が可能である。もちろん、 2 + 3 以外にも計算可能な全ての関数の表現が可能である。ここではそれらのうちの主なものを紹介する。
| |
| − | | |
| − | === 自然数と算術 ===
| |
| − | [[自然数]]をラムダ式で表現する方法はいくつか異なる手法が知られているが、その中でもっとも一般的なのは{{仮リンク|チャーチ数|en|Church encoding#Church numerals}}（{{lang-en-short|Church numerals}}）と呼ばれるもので、以下のように定義されている。
| |
| − | : <tt>0</tt> := λ''f'' ''x''. ''x''
| |
| − | : <tt>1</tt> := λ''f'' ''x''. ''f'' ''x''
| |
| − | : <tt>2</tt> := λ''f'' ''x''. ''f'' (''f'' ''x'')
| |
| − | : <tt>3</tt> := λ''f'' ''x''. ''f'' (''f'' (''f'' ''x''))
| |
| − | 以下同様である。直感的には、数 ''n'' はラムダ式では ''f'' という関数をもらってそれを ''n'' 回適用したものを返す関数である。つまり、チャーチ数は1引数関数を受け取り、1引数関数を返す[[高階関数]]である。（チャーチの提唱した元々のラムダ計算は、ラムダ式の引数が少なくとも一回は関数の本体に出現していなくてはならないことになっていた。そのため、その体系では上に挙げた <tt>0</tt> の定義は不可能である。）
| |
| − | | |
| − | 上のチャーチ数の定義のもとで、[[ペアノの公理|後続]]（後者）を計算する関数、すなわち ''n'' を受け取って ''n'' + 1 を返す関数を定義することができる。それは以下のようになる。
| |
| − | : <tt>SUCC</tt> := λ''n'' ''f'' ''x''. ''f'' (''n'' ''f'' ''x'')
| |
| − | また、加算は以下のように定義できる。
| |
| − | : <tt>PLUS</tt> := λ''m'' ''n'' ''f'' ''x''. ''m'' ''f'' (''n'' ''f'' ''x'')
| |
| − | または単にSUCCを用いて、以下のように定義してもよい。
| |
| − | : <tt>PLUS</tt> := λ''m'' ''n''. ''m'' <tt>SUCC</tt> ''n''
| |
| − | <tt>PLUS</tt> は2つの自然数をとり1つの自然数を返す関数である。この理解のためには例えば、 <tt>PLUS</tt> <tt>2</tt> <tt>3</tt> == <tt>5</tt> であることを確認してみるとよいだろう。また、乗算は以下のように定義される。
| |
| − | : <tt>MULT</tt> := λ''m'' ''n''. ''m'' (<tt>PLUS</tt> ''n'') 0
| |
| − | この定義は、 ''m'' と ''n'' の乗算は、 0 に ''n'' を ''m''回加えることと等しい、ということを利用して作られている。もう少し短く、以下のように定義することもできる。
| |
| − | : <tt>MULT</tt> := λ''m'' ''n'' ''f''. ''m'' (''n'' ''f'')
| |
| − | 正の整数 ''n'' の先行（前者）を計算する関数 <tt>PRED</tt> ''n'' = ''n'' − 1 は簡単ではなく、
| |
| − | : <tt>PRED</tt> := λ''n'' ''f'' ''x''. ''n'' (λ''g'' ''h''. ''h'' (''g'' ''f'')) (λ''u''. ''x'') (λ''u''. ''u'')
| |
| − | もしくは
| |
| − | : <tt>PRED</tt> := λ''n''. ''n'' (λ''g'' ''k''. (''g'' <tt>1</tt>) (λ''u''. <tt>PLUS</tt> (''g'' ''k'') <tt>1</tt>) ''k'') (λ''v''. <tt>0</tt>) <tt>0</tt>
| |
| − | と定義される。上の部分式 (''g'' <tt>1</tt>) (λ''u''. <tt>PLUS</tt> (''g'' ''k'') <tt>1</tt>) ''k'' は、 ''g''(1) がゼロとなるとき ''k'' に評価され、そうでないときは ''g''(''k'') + 1 に評価されることに注意せよ。
| |
| − | | |
| − | === 論理記号と述語 ===
| |
| − | <tt>TRUE</tt> や <tt>FALSE</tt> といった[[真理値]]は慣習的に以下のように定義されることが多い。これらは{{仮リンク|チャーチ真理値|en|Church encoding#Church booleans}}（{{lang-en-short|Church booleans}}）とよばれている。
| |
| − | : <tt>TRUE</tt> := λ''x'' ''y''. ''x''
| |
| − | : <tt>FALSE</tt> := λ''x'' ''y''. ''y''
| |
| − | :（この <tt>FALSE</tt> は前述のチャーチ数のゼロと同じ定義であることに注意せよ）
| |
| − | これらの真理値に対して論理記号を定義することができる。たとえば、以下のようなものがある。
| |
| − | : <tt>AND</tt> := λ''p'' ''q''. ''p'' ''q'' <tt>FALSE</tt>
| |
| − | : <tt>OR</tt> := λ''p'' ''q''. ''p'' <tt>TRUE</tt> ''q''
| |
| − | : <tt>NOT</tt> := λ''p''. ''p'' <tt>FALSE</tt> <tt>TRUE</tt>
| |
| − | : <tt>IFTHENELSE</tt> := λ''p'' ''x'' ''y''. ''p'' ''x'' ''y''
| |
| − | これらの記号を使った計算の例を挙げる。
| |
| − | : <tt>AND</tt> <tt>TRUE</tt> <tt>FALSE</tt>
| |
| − | ::= (λ''p'' ''q''. ''p q'' <tt>FALSE</tt>) <tt>TRUE</tt> <tt>FALSE</tt> →<sup>β</sup> <tt>TRUE</tt> <tt>FALSE</tt> <tt>FALSE</tt>
| |
| − | ::= (λ''x'' ''y''. ''x'') <tt>FALSE</tt> <tt>FALSE</tt> →<sup>β</sup> <tt>FALSE</tt>
| |
| − | 以上より、 <tt>AND TRUE FALSE</tt> が <tt>FALSE</tt> と等しいことがわかる。
| |
| − | | |
| − | 「[[述語論理|述語]]」とは、真理値を返す関数のことである。計算論において最も基本的な述語は <tt>ISZERO</tt> で、これは引数がチャーチ数の <tt>0</tt>であった場合には <tt>TRUE</tt> を、そうでなければ <tt>FALSE</tt> を返す関数であり、以下のように定義できる。
| |
| − | : <tt>ISZERO</tt> := λ''n''. ''n'' (λ''x''. <tt>FALSE</tt>) <tt>TRUE</tt>
| |
| − | <!--The availability of predicates and the above definition of <tt>TRUE</tt> and <tt>FALSE</tt> make it convenient to write "if-then-else" statements in lambda calculus.-->
| |
| − | | |
| − | === 対 ===
| |
| − | （2つ組の）[[順序対]]のデータ型は、 <tt>TRUE</tt> および <tt>FALSE</tt> を用いて定義することができる。これらは{{仮リンク|チャーチ対|en|Church encoding#Church pairs}}（{{lang-en-short|Church pairs}}）とよばれている。
| |
| − | : <tt>[[コンス対|CONS]]</tt> := λ''s'' ''b'' ''f''. ''f'' ''s'' ''b''</tt>
| |
| − | : <tt>[[carとcdr|CAR]]</tt> := λ''p''. ''p'' <tt>TRUE</tt>
| |
| − | : <tt>CDR</tt> := λ''p''. ''p'' <tt>FALSE</tt>
| |
| − | リンク型のリスト構造は、空リストのために特定の予約された値（例えば <tt>FALSE</tt> ）を用い、リストをその先頭要素と後続リストの <tt>CONS</tt> 対として表現することによって実現できる。
| |
| − | | |
| − | === リスト ===
| |
| − | {{See also|en:Church_encoding#List_encodings}}
| |
| − | {{節スタブ}}
| |
| − | | |
| − | === 再帰 ===
| |
| − | [[再帰]]とは自分自身を関数として使用することで、ラムダ計算では表面上は再帰操作は許されていないように見える。しかし少し工夫することによってラムダ計算でも再帰を実現できる。例として[[階乗]]を計算する関数 ''f''(''n'') を考えてみよう。この関数は再帰的に以下のように定義できる。
| |
| − | : ''f''(''n'') := 1, if ''n'' = 0; and ''n'' × ''f''(''n'' − 1), if ''n'' > 0
| |
| − | | |
| − | ラムダ計算では自分自身を含む関数は定義できない。この問題を解決するためにまず、 ''f'' を引数にとり ''n'' を引数にとる関数を返す''g'' という関数を考える。
| |
| − | : ''g'' := λ''f'' ''n''. (1, if ''n'' = 0; and ''n'' × ''f''(''n'' − 1), if ''n'' > 0)
| |
| − | 関数 ''g'' は 1 か ''n'' × ''f''(''n'' − 1) を返すような関数を返す。上述の <tt>ISZERO</tt> や算術、論理記号の定義を用いれば、この関数 ''g'' はラムダ式で定義することができる。
| |
| − | | |
| − | しかし、これでは ''g'' 自身はまだ再帰的ではない。 ''g'' を用いて再帰的な階乗関数を作り出すためには、 ''g'' に対して引数 ''f'' として渡されている関数が、ある性質を持つ必要がある。すなわち、この ''f'' を展開すると関数 ''g'' がある一つの引数を伴った形になり、さらにその ''g'' への引数は先ほど''f'' として渡された関数に再びなる必要がある。
| |
| − | | |
| − | この性質は言い換えると、 ''f'' は ''g'' ( ''f'' )に展開される必要があるということだ。この ''g'' の呼び出しは先ほどの階乗関数に展開され、再帰の段階を一段降りる計算をしている。この展開において、関数 ''f'' が再度出現する。そして、この関数 ''f'' は再度 ''g'' ( ''f'' )に展開され、再帰が続いていく。この ''f'' = ''g'' ( ''f'' )となるような関数は、 ''g'' の[[不動点]]と呼ばれる。そして、この不動点は[[不動点コンビネータ]]として知られるものによってラムダ計算で表現することが出来る。この不動点コンビネータは ''Y'' と表される -- [[不動点コンビネータ#Yコンビネータ|Yコンビネータ]]:
| |
| − | :''Y'' = λ''g''. (λ''x''. ''g'' (''x'' ''x'')) (λ''x''. ''g'' (''x'' ''x''))
| |
| − | | |
| − | ラムダ計算では、 ''Y g'' は ''g'' の不動点となる。つまり、 ''g'' (''Y'' ''g'') == ''Y g'' となる。このもとで、 ''n'' の階乗を計算するには単に ''g'' (''Y'' ''g'') ''n'' を呼び出せばよい。ここで、 ''n'' は上述したチャーチ数である。
| |
| − | | |
| − | ''n'' = 5 として、評価の例を見てみよう。
| |
| − | :(λ''n''.(1, if ''n'' = 0; and ''n''·((''Y g'')(''n'' − 1)), if ''n'' > 0)) 5
| |
| − | ::1, if 5 = 0; and 5·(''g''(''Y g'')(5 − 1)), if 5 > 0
| |
| − | ::5·(''g''(''Y g'') 4)
| |
| − | ::5·(λ''n''. (1, if ''n'' = 0; and ''n''·((''Y g'')(''n'' − 1)), if ''n'' > 0) 4)
| |
| − | ::5·(1, if 4 = 0; and 4·(''g''(''Y g'')(4 − 1)), if 4 > 0)
| |
| − | ::5·(4·(''g''(''Y g'') 3))
| |
| − | ::5·(4·(λ ''n''. (1, if ''n'' = 0; and ''n''·((''Y g'')(''n''− 1)), if ''n'' > 0) 3))
| |
| − | ::5·(4·(1, if 3 = 0; and 3·(''g''(''Y g'')(3 − 1)), if 3 > 0))
| |
| − | ::5·(4·(3·(''g''(''Y g'') 2)))
| |
| − | : ...
| |
| − | アルゴリズムの構造が再帰的に評価されているのがわかるだろう。再帰的に定義される関数は全て他の適当な関数の不動点となっているため、 ''Y'' を用いることで全ての再帰的な関数をラムダ式で表現することができる。たとえば、自然数に対する除算、乗算や比較述語を再帰を用いてよりきれいに定義することができる。
| |
| − | | |
| − | == 計算可能性とラムダ計算 ==
| |
| − | [[自然数]]から自然数への関数 ''F'': '''N''' → '''N''' が[[計算可能性理論|計算可能]]であるということは、全ての自然数の対 ''X'', ''Y'' に対して ''F''(''X'') = ''Y'' と ''f'' ''x'' == ''y'' が同値となるようなラムダ式 ''f'' が存在すること、と定義することができる。ここで、 ''x'', ''y'' はそれぞれ ''X'', ''Y'' に対応するチャーチ数によるラムダ式である。この定義は、計算可能性を定義する多くの方法のうちのひとつである。より詳しくは、[[チャーチ＝チューリングのテーゼ|チャーチ-チューリングの提唱]]の項を見よ。
| |
| − | | |
| − | == 同値性の決定不可能性 ==
| |
| − | 2つのラムダ式を入力とし、それらが同値であるかどうかを判定するアルゴリズムは存在しない。これは[[決定可能性|決定不可能性]]が示された歴史的に最初の問題である。ここで使われる「[[アルゴリズム]]」という言葉も、もちろんきちんと定義されなければならない。チャーチは自身の証明の中で[[計算可能関数|帰納的関数]]をその定義に用いたが、現在ではこれは適切なその他のアルゴリズムの定義と等価であることが知られている。
| |
| − | | |
| − | チャーチの証明ではこの問題を、あたえられたラムダ式に正規形が存在するかどうかという問題に帰している。正規形とは、それ以上簡約のできない同値なラムダ式のことである。チャーチの証明ではまず、この問題が決定可能である、つまり、ラムダ式で表現可能であると仮定する。クリーネによる結果と[[ゲーデル数]]のラムダ式表現を用いることによってチャーチは、[[対角線論法]]によりパラドキシカルなラムダ式 ''e'' を構成した。この ''e'' を、それ自身を表すゲーデル数に適用すると矛盾が導かれる。
| |
| − | <!-- 原文: Church's proof first reduces the problem to determining whether a given lambda expression has a normal form. A normal form is an equivalent expression which cannot be reduced any further. Then he assumes that this predicate is computable, and can hence be expressed in lambda calculus. Building on earlier work by Kleene and constructing a Gödel numbering for lambda expressions, he constructs a lambda expression e which closely follows the proof of Gödel's first incompleteness theorem. If e is applied to its own Gödel number, a contradiction results. -->
| |
| − | | |
| − | 詳しくいえば次のようである。まず <math>X</math> を正規形の存在性を判定するラムダ式とする。<math>A</math> を2つのラムダ式のゲーデル数から、それらを適用してできるラムダ式を計算する関数を表すラムダ式、<math>N</math> を自然数からそれを表すラムダ式の表現のゲーデル数を求める関数を表すラムダ式とする。すなわち、
| |
| − | : <math> A \ulcorner x \urcorner \ulcorner y \urcorner \to^{\beta} \ulcorner (xy) \urcorner </math>
| |
| − | : <math> N \ulcorner x \urcorner \to^{\beta} \ulcorner \ulcorner x \urcorner \urcorner </math>
| |
| − | が成り立つ。ここで <math> \ulcorner x \urcorner </math> はラムダ式 <math>x</math> のゲーデル数を表すラムダ式の表現である。
| |
| − | いま、ラムダ式 <math>e</math> を
| |
| − | : <math> e := \lambda x. \text{ if } X (A x (N x)) \text{ then } \Omega \text{ else } \lambda y. y </math>
| |
| − | と定める。ここで <math>\Omega</math> は正規形を持たないラムダ式 <math>(\lambda x. xx)(\lambda x. xx)</math> である。自己適用 <math> e \ulcorner e \urcorner</math> を計算すると次のようになる。
| |
| − | : <math> e \ulcorner e \urcorner</math>
| |
| − | : <math> \text{ if } X (A \ulcorner e \urcorner (N \ulcorner e \urcorner)) \text{ then } \Omega \text{ else } \lambda y. y </math>
| |
| − | : <math> \text{ if } X (A \ulcorner e \urcorner \ulcorner \ulcorner e \urcorner \urcorner) \text{ then } \Omega \text{ else } \lambda y. y </math>
| |
| − | : <math> \text{ if } X \ulcorner e \ulcorner e \urcorner \urcorner \text{ then } \Omega \text{ else } \lambda y. y </math>
| |
| − | もし <math> e \ulcorner e \urcorner</math> が正規形を持つならば、<math> e \ulcorner e \urcorner</math> は <math> \Omega </math> にベータ簡約される。すると[[チャーチ・ロッサーの定理]]より、<math>\Omega</math> は <math> e \ulcorner e \urcorner</math> と共通のラムダ式にベータ簡約できるから、<math>\Omega</math> は正規形を持つ。これは矛盾。したがって <math> e \ulcorner e \urcorner</math> は正規形を持たない。すると <math> e \ulcorner e \urcorner</math> は <math> \lambda x. x</math> にベータ簡約されることになる。ラムダ式 <math> \lambda x. x</math> は正規形であるので、やはり矛盾。したがって <math>X</math> のようなラムダ式は存在しない。
| |
| − | | |
| − | ==チャーチ・ロッサー性==
| |
| − | 一般にラムダ式の中にβ-変換できる部分式が複数ある場合、どこから評価を行うかによって評価の経過は複数存在する。それらの複数の経過からさらに評価することによって、同じラムダ式を得られる性質をチャーチ・ロッサー性、もしくは[[合流性]]と呼ぶ（[[チャーチ・ロッサーの定理]]）。また、あるラムダ式から一回のβ-簡約によって得られた二つのラムダ式が、同じラムダ式にβ-変換されるという性質は弱チャーチ・ロッサー性と呼ばれる。チャーチ・ロッサー性を持つ体系は弱チャーチ・ロッサー性も持つが、逆は必ずしもなりたたない。
| |
| − | | |
| − | チャーチ・ロッサー性は本稿で取り扱っている型無しラムダ計算の体系では成立することが知られている。しかしその他の体系、例えば型を付けて拡張されたラムダ計算の体系などに関しては、必ずしも成り立つとは限らない。
| |
| − | | |
| − | == 停止性 ==
| |
| − | β-変換は停止しない（無限ループに陥る）場合がある。例えば次の式を適用する場合には停止しない。
| |
| − | :(λ''x''. ''x'' ''x'') (λ''x''. ''x'' ''x'') →<sup>β</sup> (λ''x''. ''x'' ''x'') (λ''x''. ''x'' ''x'') →<sup>β</sup> …
| |
| − | | |
| − | ある種のラムダ計算の体系では、任意のラムダ式に対してβ-変換の停止性が保証されていることがある。どのような順序でβ-変換を行ったとしてもβ-変換が停止する性質を強正規化性といい、β-変換の順序を上手く選んだ場合にβ-変換が停止する性質を弱正規化性という。チャーチ・ロッサー性を満たし、かつ停止性を持つラムダ計算の体系では、ラムダ式をどのような順序で評価しても必ず同じ結果になることがわかる。
| |
| − | | |
| − | 強正規化的であり、かつ弱チャーチ・ロッサー性を持つラムダ計算の体系はチャーチ・ロッサー性を持つ（{{仮リンク|ニューマンの補題|en|Newman's lemma}}）。
| |
| − | | |
| − | 型無しラムダ計算の体系では、ある式の停止性を判断する事は[[決定不能]]であることが証明されている。
| |
| − | | |
| − | == ラムダ計算とプログラミング言語 ==
| |
| − | {{仮リンク|ピーター・ランディン|en|Peter Landin}}は1965年に発表した<cite>[http://portal.acm.org/citation.cfm?id=363749&coll=portal&dl=ACM A Correspondence between ALGOL 60 and Church's Lambda-notation]</cite>において、ラムダ計算が手続的な抽象化と手続き（サブプログラム）の適用のしくみを提供しているがために、多くの[[プログラミング言語]]がラムダ計算にその基礎を置いているとみることができるとしている。
| |
| − | | |
| − | ラムダ計算をコンピュータ上に実装するには、関数を[[第一級オブジェクト]]として取り扱う必要があり、これはスタック・ベースのプログラミング言語においては問題となってくる。これは{{仮リンク|Funarg問題|en|Funarg problem}}として知られている。
| |
| − | | |
| − | ラムダ計算と最も密接な関係をもつプログラミング言語は[[関数型言語]]と呼ばれる諸言語で、本質的にはいくつかの[[定数]]と[[データ型]]を用いてラムダ計算を実装している。[[LISP|Lisp]]では関数の定義にラムダ記法の一変形を用いており、さらに、[[純LISP|純Lisp]]と呼ばれるLispのサブセットはラムダ計算と真に等価になっている。
| |
| − | | |
| − | 関数を第一級オブジェクトとして扱えるのは関数型言語だけというわけではない。[[Pascal]]など、多くの[[命令型プログラミング|命令型言語]]ではある関数を他の関数の引数として与える操作が許されている。[[C言語|C]]や[[C++]]では関数を指す[[ポインタ (プログラミング)#関数ポインタ|ポインタ]]や[[関数オブジェクト#C/C++ での関数オブジェクト|クラス型関数オブジェクト]]を用いて同じことが実現できる。このような機能はサブ関数が明示的に書かれている場合にのみ用いることができ、したがってこの機能がそのまま[[高階関数]]をサポートしていることにはならない。いくつかの手続的な[[オブジェクト指向プログラミング|オブジェクト指向言語]]では関数を任意の階数に書くことができる。[[Smalltalk]]や、より最近の言語では[[Eiffel]]（エージェント）や[[C Sharp|C#]]（[[デリゲート (プログラミング)|デリゲート]]）などで用意されている機能がそれである。例えば、Eiffelのインライン・エージェントの機能を用いた以下のコード
| |
| − | '''agent''' (x: REAL): REAL '''do Result''' := x * x '''end'''
| |
| − | はラムダ式 λ''x''. ''x'' <tt>*</tt> ''x'' （値呼び出し）に相当するオブジェクトを表している。このオブジェクトは他のあらゆるオブジェクトと同様に、変数に代入したり関数に渡したりすることができる。変数 ''square'' の値が上のエージェントのオブジェクトであるとすれば、 ''square'' に値 ''a'' を適用した結果（β-簡約）は ''square''<tt>.item([</tt>''a''<tt>])</tt> と書ける。ただしここでの引数は[[タプル]]であるとみなされる。
| |
| − | | |
| − | == 並行性 ==
| |
| − | ラムダ計算のチャーチ・ロッサー性は、評価（β-簡約）をどの順序で行っても、さらには同時に（並行に）行ってもよいことを意味している。（より詳しくいえば、ラムダ計算は[[参照透過性|参照透過]]である。）このため、ラムダ計算を用いて種々の非決定的[[評価戦略]]をモデル化することができる。[[並列コンピューティング|並列性]]や[[並行計算|並行性]]をモデル化するためのより強力な手法として、[[Communicating Sequential Processes|CSP]]、[[CCS]]、[[パイ計算]]、[[アンビエント計算]]などの[[プロセス計算]]がある。
| |
| − | | |
| − | == 参考資料 ==
| |
| − | * 計算論 計算可能性とラムダ計算 コンピュータサイエンス大学講座 高橋 正子 (著) 近代科学社 ISBN 4764901846 (1991)
| |
| − | * ハロルド・エイブルソン、ジェラルド・ジェイ・サスマン、ジュリー・サスマン共著『[[計算機プログラムの構造と解釈]] 第二版』和田英一訳、ピアソンエデュケーション、2000、ISBN 4-8947-1163-X
| |
| − | {{FOLDOC}}
| |
| − | | |
| − | == 関連項目 ==
| |
| − | * [[コンビネータ論理]]
| |
| − | * [[型付きラムダ計算]] - [[単純型付きラムダ計算]] - 型無しラムダ計算
| |
| − | * [[ド・ブラン・インデックス]]
| |
| − | * [[第一級関数]]
| |
| − | * [[不動点コンビネータ]]
| |
| − | * [[無名再帰]]
| |
| − | * [[System F]]
| |
| − | * [[SKIコンビネータ計算]]
| |
| − | * [[B,C,K,Wシステム]]
| |
| − | * [[カリー・ハワード対応]]
| |
| − | * [[ラムダ計算騎士団]]（Lispを使うプログラマ達の間で冗談として登場する架空の騎士団）
| |
| − | * [[ラムダ・キューブ]]
| |
| − | * [[項書き換え]]
| |
| − | <!--* [[Thierry Coquand]]'s [[calculus of constructions]]-->
| |
| − | * [[Unlambda]]
| |
| − | * [[再帰的定義]]
| |
| − | * [[領域理論]]
| |
| − | * [[合流性]]
| |
| − | * [[ペアノの公理]]
| |
| − | | |
| − | {{DEFAULTSORT:らむたけいさん}}
| |
| − | [[Category:ラムダ計算|*]]
| |
| − | [[Category:数理論理学]]
| |
| − | [[Category:理論計算機科学]]
| |
| − | [[Category:形式手法]]
| |
| − | [[Category:関数型プログラミング]]
| |
| − | [[Category:FOLDOCを情報源とする記事]]
| |
| − | [[Category:数学に関する記事]]
| |
| − | [[Category:形式体系]]
| |