非形式的な概説

ウィキペディア小見出し辞書

非形式的な概説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/12 16:37 UTC 版)

「ラムダ計算」の記事における「非形式的な概説」の解説

例えば、ある数に 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) と同値である。