計算言語６（ラムダ計算）
このページはマス旅の一部です。
今回は「ラムダ計算（Lambda Calculus）」の世界に飛び込んでみよう。
これまで、計算モデルとして
「チューリングマシン」（テープと状態遷移による制御）や、
「帰納的関数」（初期関数と合成・再帰による構成）を紹介しました。
これらは「計算とは何か」を厳密に教えてくれるが、私たちが普段書くプログラミング言語とはまだ少し距離があります。
そこで登場するのがラムダ計算だ。
ラムダ計算は一言で言えば、「関数定義」と「関数適用（実行）」の2つしか機能が存在しない、究極にシンプルなプログラミング言語だ。
その本質は、C言語の #define や Lisp のマクロのような、単純な「マクロ置換（文字列の置き換え）」にあるのです。
1. ラムダ計算の構文
ラムダ計算の世界にあるのは「ラムダ項（式）」だけです。
構成要素は以下の3つしかありません。
・識別子：
x, y, z （変数）
λ（ラムダ）
（）（カッコ）
.(ピリオド）
・ 関数定義：
λ x. L
（引数ｘ、L が関数の中身で、リターン文は不要です。）
・ 関数実行：
M N
（関数 M に 引数 N を渡すという意味です）
これらを組み合わせるだけで、
あらゆるプログラム（計算式）が作れる。
2. ラムダ計算の仕組み（マクロ展開）
ラムダ計算の計算（実行）とは、単にマクロを展開することだ。
この展開操作を「ベータ簡約」と呼ぶ。
たとえば、次の式を見てみよう。
(λx. x + 1) 2
これは「引数 x に 1 を足す関数」に「引数 2」を適用する式（M N 型）だ。
x の部分を 2 に置換（マクロ展開）すると：
(λx. x + 1) 2 --> 2 + 1 --> 3
いくつか例を見てみよう。
・恒等マクロ（そのまま返す）：
(λx. x) 2 --> 2
・無視マクロ（引数を捨てて定数を返す）：
(λx. y) 5 --> y
・関数の二重適用（高階マクロ）：
(λf. f (f 3)) (λx. x + 1)
（関数 f を 3 に 2 回適用するマクロに、「1 加算する関数」を渡す）
--> (λx. x + 1) ((λx. x + 1) 3)
--> (λx. x + 1) (3 + 1)
--> (λx. x + 1) 4 --> 4 + 1 --> 5
3. ラムダ計算でデータ構造を作る
関数しかない世界で、数や条件分岐、繰り返し（ループ）を表現してみよう。
＜数を作る（チャーチ数）＞
数を「関数を何回適用するかという処理の回数（リピートマクロ）」として定義する。
・0 ≡ λf. λx. x （x に f を 0 回適用）
・1 ≡ λf. λx. f x （x に f を 1 回適用）
・2 ≡ λf. λx. f (f x) （x に f を 2 回適用）
・n ≡ λf. λx. f^n x （x に f を n 回適用）
＜条件分岐（If-Then-Else）＞
真偽値を「2つの引数のうち、どちらを選択するかという選択マクロ」として定義する。
・True ≡ λx. λy. x （1番目の引数を選ぶ）
・False ≡ λx. λy. y （2番目の引数を選ぶ）
これを使うと、「If P Then A Else B」は単なる関数適用
P A B
で実現できる。
P が True なら A が選ばれ、
False なら B が選ばれる仕組みだね。
＜ループと再帰（Y コンビネータ）＞
ラムダ計算には「関数に名前をつける機能」がないため、
自分自身を名前で呼び出す通常の再帰（ループ）は使えない。
そこで、「展開すると自分自身を複製する魔法のマクロ（不動点演算子）」を使う。最も有名なのが Y コンビネータ だ。
Y ≡ λg. (λx. g (x x)) (λx. g (x x))
この Y に任意の関数 f を渡して簡約してみよう。
Y f --> (λx. f (x x)) (λx. f (x x))
--> f ((λx. f (x x)) (λx. f (x x)))
かっこ内の式は、展開前の Y f そのものだ。つまり：
Y f --> f (Y f) --> f (f (Y f)) --> ...
マクロ置換を繰り返すだけで、f が無限に自己増殖していく。
これに先ほどの「条件分岐マクロ」を組み合わせることで、
「ある条件を満たすまで処理を繰り返して止める」という再帰プログラム（ループ）や
無限ループを完璧に作り出せるね。
関数に名前をつけることができないので、実際の記述はもっと複雑にはなるけれど、
たとえば、
λを\とかいて、
factorial = \i. if (iszero i) then 1 else i * factorial(i - 1) と定義すれば、
factorial 5 は次のように展開できる。
factorial 5
--> (\i. if (iszero i) then 1 else i * factorial(i - 1)) 5
--> if (iszero 5) then 1 else 5 * factorial(5 - 1)
--> 5 * (factorial 4)
--> 5 * 4 * (factorial 3)
--> 5 * 4 * 3 * (factorial 2)
--> 5 * 4 * 3 * 2 * (factorial 1)
--> 5 * 4 * 3 * 2 * 1
--> 120
＜ 振り返り＞
私たちが学んできた 3 つの計算モデルは、
アプローチはちがっていても「計算できる能力の限界」は全く同じなのだ（チャーチ＝チューリングのテーゼ）。
・チューリングマシン：「機械のハードウェア（状態とテープ）」による計算のシミュレート
・帰納的関数：「数学的な関数の合成・再帰」による計算の定義
・ラムダ計算：「マクロの文字置換」によるソフトウェア的な計算の実行
ラムダ計算は、ただの「文字の置き換えルール（マクロ）」だけでチューリングマシンと同じ計算がすべて行えるというだけではない。ラムダ計算は現代の関数型言語（Lisp, Haskell, Scala など）の根幹をなす最も洗練されたプログラム言語の原形と言えるし、さらに、後発のPython,julia,java,javascript,...などのモダンな高級言語でも、無名関数の作成用に装備するのが当たり前になっている。
ラムダ計算は、理論的にも実用的にも超重要なものだね。
歴史的には、ラムダ計算は、1930年代にアロンゾ・チャーチとスティーヴン・クリーネによって、
数理論理学における「計算可能性」を探求する過程生み出された。チューリングマシンの考案者であるアラン・チューリングは、後にプリンストン大学でチャーチの弟子となり、
チューリングマシンとラムダ計算の計算能力が完全に同値であることを証明した。
また、クリーネは後に正規表現（オートマトン理論）の基礎となる代数構造を作った人物でもある。
1930年代のプリンストンで若き天才たちが議論を重ね、モダンな高級言語の基盤を作った。
彼らの人的なつながりに思いを馳せると、言語理論の背景にある情熱の連鎖が伝わってきて
とてつもない感動を覚える。
＜geogebraでコード化＞
GeoGebraの文字列操作機能を使って、
ラムダ計算の「関数の適用と置換（(λx. f(x)) v --> f(v)）」
を1ステップずつ展開するシミュレータを作成します。
ただし、、使いたくなるx,expr,argは予約語のx,exp,argとぶつかるので変数名として使うのはやめましょう。
「作成」ボタンのクリック時のスクリプト(Process以外は非表示）
step = 0
k = 3
fnBody = "x + 1"
ans = k + 1
Lamda = "(λx. " + fnBody + ") " + k
Process = "0: 初期状態 -> " + Lamda
「リセット」ボタンのクリック時のスクリプト
SetValue(step, 0)
SetValue(Process, "0: 初期状態 -> " + Lamda )
「ステップ展開」ボタンのクリック時のスクリプト
SetValue(step, step + 1)
SetValue(Process, If(step == 1, "1: " + k + " を x に代入-> ", step == 2, "2: 置換実行 -> " + k + " + 1", "3: 評価完了 -> "+ ans))
GUI（画面表示）用に数式ビューに入力する。
#見出しをxにする。
inArg = InputBox(k)
text = "λ関数:" + fnBody
画面上のボタンを押すたびに、仮引数 x が消え、インプットボックスで入れた値へ置き換わっていくマクロ展開の様子が
テキストビューに表示されます。
タイトルは「λ計算を実感しよう。」