JavaScriptで学ぶ・プログラマのためのラムダ計算 - 檜山正幸のキマイラ飼育記 (はてなBlog)

「JavaScriptによるテンプレート・モナド、すっげー簡単!」にて：

紙と鉛筆でラムダ計算を実行できることは必要だな、やっぱり。

なんて強調したので、ラムダ計算の入門、いってみよう。

[追記]練習問題集を追加しました。説明を読みながら、あるいは読んだ後で是非やってみてください。→「JavaScriptで学ぶ・プログラマのためのラムダ計算問題集」[/追記]

※印刷のときはサイドバーが消えます。
内容：

JavaScriptの関数リテラル
ラムダ式ってなんだ
ラムダ計算の体系と適用操作
ラムダ式の例をいくつか
β変換 -- ラムダ計算のキモ！
β変換を何度か実行してみる
中間まとめ、まだ続きがあるよ

JavaScriptの関数リテラル

最初に、JavaScriptに関する知識を確認しておきましょう。なお、JavaScriptの対話的実行環境については「もっともお手軽な対話的JavaScript処理系」を参照。

JavaScriptでは、次の2つの関数定義は同じ効果を持ちます。

/* 普通の関数定義 */
function square(x) {
 return x*x;
}

/* function式と代入による関数定義 */
var square = function (x) {return x*x;};

function (x) {return x*x;}は、式、つまり値を持つ表現であり、その値は関数オブジェクトになります。予約語functionから始まるこの形の式は、関数オブジェクト（単に関数ということが多い）を直接的に表すので関数リテラルとも呼ばれます。念のため、“function式＝関数リテラル”の構文を示しておきましょう。

'function' '(' 引数並び ')' '{' 関数定義の本体 '}'

“引数並び”は、引数変数（仮引数＜かりひきすう＞とも呼びます）をカンマで区切って並べたものです。引数が1つならカンマはなく、引数なしなら何もありません。

関数リテラルを変数に代入すれば、それは関数に名前を付けたことになります。例えば先の例では、二乗する関数にsquareという名前を付けていますね。でも、いつでも名前を付ける必要はなくて、関数リテラルそのものにいきなり引数を渡してもかまいません。

js> (function (x) {return x*x;})(4)
16
js> (function (x) {return x*x;})(123)
15129
js>

ただし、この書き方だと、一度書いた関数がどこにも保存されないので、使うたびにまるまる関数定義を書く必要があります。

ラムダ式ってなんだ

ラムダ式とは、事実上、JavaScriptの関数リテラル（function式）とまったく同じものです。ラムダ式の構文や解釈にはいくつかの流儀がありますが、ここでは、JavaScriptと親和性が高い構文を紹介します。これさえ憶えておけば、あとは何とでも融通が効きます。

とにかく次のルールをシッカリ頭に、いや体にたたき込んでください。

予約語functionの代わりにギリシャ文字のλ（ラムダ）を使う。
return 式; というJavaScript文は、returnを省略して式だけを書く。
関数定義の本体を囲む波括弧の代わりに丸括弧を使う。
「λ＋仮引数リスト」と「関数定義の本体」のあいだの区切りにピリオドを打つ。

実例でやってみましょう。

function (x) {return x*x;} → λ(x) {return x*x;} ；λ（ラムダ）を使う
λ(x) {return x*x;} → λ(x) {x*x} ；式だけを書く
λ(x) {x*x} → λ(x) (x*x) ；丸括弧を使う
λ(x) (x*x) → λ(x).(x*x) ；ピリオドを打つ

はいっ、これでラムダ式いっちょ出来上がり： λ(x).(x*x)

ラムダ式の書き方に関する注意事項：

プログラムコードと違って、空白はあまり入れずに、詰めて書くことが多いようです。
引数が1つのときは、引数リストの丸括弧は省略してもかまいません。例：λx.(x*x)
関数定義の本体が短いときは、本体を囲む丸括弧を省略してもかまいません。例：λx.x*x

ラムダ計算の体系と適用操作

前節で導入したラムダ式が、関数を表現するものであることは分かりますね。ラムダ計算とは、要するに関数の計算のことです。計算を不自由なく行うには、ラムダ式以外に次の表現達も必要です。

定数：整数1, 2, 3とか、文字列"Hello, world."とか。データ・リテラルのことです。
変数：引数変数も変数ですが、その他に変数を使ってかまいません。
組み込み演算子、組み込み関数：足し算+、掛け算*、平方根を求めるsqrtとか（実際のJavaScriptではMath.sqrt）。

これらの表現を組み合わせる方法は一種類しかありません。それは、適用（application）と呼ばれる操作です。適用とは、関数（を表現する式）の直後に付けられた括弧内に別な式を入れることです。簡単な例は、(λx.(x*x))(4) です。これは、λx.(x*x) というラムダ式（関数を表現）に、定数4を適用したものです。「定数4に、関数λx.(x*x)を適用」というほうが“正しい”用法ですが、以下では、「関数を適用」ではなくて「引数を適用」と表現することにします*1。

「適用」を普通のプログラミング用語で言えば、ほぼ「関数に引数を渡すこと」です。しかし、適用はあくまで形のうえだけの操作であり、実際の計算や処理が進行することはありません。適用により、2つの式から新しい式が作られるだけです。

λx.(x*x)に 4 を適用すると、(λx.(x*x))(4)
λx.(x*x)に 123 を適用すると、(λx.(x*x))(123)
λx.(x*x)に z を適用すると、(λx.(x*x))(z)
λx.(x*x)に y + 2*z を適用すると、(λx.(x*x))(y + 2*z)
λx.(x*x)に (λy.(2*y))(2) を適用すると、(λx.(x*x))（(λy.(2*y))(2)）

分かりにくかったら、λx.(x*x) にsquareという名前を付けてみて：

squareに 4 を適用すると、square(4)
squareに 123 を適用すると、square(123)
squareに z を適用すると、square(z)
squareに y + 2*z を適用すると、square(y + 2*z)
squareに (λy.(2*y))(2) を適用すると、square（(λy.(2*y))(2)）

squareのように名前を付けると、関数の仕組みは見えなくなりますが、ラムダ式では関数の中身が透けて丸見えです。いわば、ラムダ式はスケルトン（透明）ケースに詰め込まれた関数。名前（関数名）の代わりにラムダ式を使うと括弧が多くなりますが、落ち着いて見れば分かるはず。

ここでひとつだけ注意；先頭がλではじまる式は、もちろんラムダ式と呼びますが、これは狭い意味のラムダ式です。定数／変数／組み込み演算子／組み込み関数など（を表す記号）を、何度か（0回でもよい）の適用操作により組み立てた表現もまたラムダ式と呼ぶことがあります -- こっちは広い意味のラムダ式、ラムダ計算体系内の表現のことです*2。

ラムダ式の例をいくつか

簡単なラムダ式をいくつか挙げましょう。a, x, yは変数、f, g, hは前もって与えられた関数（を表す記号）です。

λx.5
λx.x
λa.(λx.a)
λ(x, y).f(y, x)
λx.f(x, x)
λx.h(g(x))
λ(x, y).g(f(x, y))

f(x, y) ＝ x + 3y、g(x) ＝ 2x、h(x) ＝ x² という状況で実験してみましょう。ラムダ式をJavaScriptに翻訳して、1つの式に対して1回だけ値を求めてみます。値を求めるために、具体的な数値をラムダ式に適用してます。結果の値がどのようにして出てきたか、考えてみてください（今、完全にはわからなくてもいいです。）

js> function f(x, y) {return x + 3*y;}
js> function g(x) {return 2*x;}
js> function h(x) {return x*x;}
js> 
js> (function (x) {return 5;})(2)
5
js> (function (x) {return x;})(2)
2
js> (function (a) {return (function (x) {return a;});})(5)(2)
5
js> (function (x, y) {return f(y, x);})(2, 5)
11
js> (function (x) {return f(x, x);})(2)
8
js> (function (x) {return h(g(x));})(2) 
16
js> (function (x, y) {return g(f(x, y));})(2, 5)
34
js>

ここで、関数に引数を適用したのは僕（JavaScript インタープリタを操作している当人）ですが、適用された式を実際に計算したのはJavaScript インタープリタです。くどいけど、適用と実際の計算（評価とも呼ぶ）は区別してください。ラムダ計算の適用は、関数に引数を渡した形を作るだけです。

β変換 -- ラムダ計算のキモ！

前節で、「ラムダ式に別な式を適用しても計算は進行しない」と言いました。では、計算を進行させるにはどうしたらいいでしょうか。ここで、β＜ベータ＞変換（β還元、あるいは単に還元とも呼ぶ）操作が登場します。β変換により、実際の計算が進行するのです。（[追記]「還元」は"reduction"の翻訳のつもりです。他に、「簡約」って訳語もあります。簡約のほうが感じが出ているかもしれません。reduction を contraction と言うこともあって、"contraction"の訳語は「縮約」が普通だと思います。[/追記]）

まず、β変換の具体例をいくつか出します。矢印の左から右への変換（書き換え）がβ変換です。

(λx.(x*x))(4) → 4*4
(λx.5)(2) → 5
(λx.x)(2) → 2
(λa.(λx.a))(5) → λx.5
(λx.(x*x))(z) → z*z
(λx.(x*x))(y + 2*z) → (y + 2*z)*(y + 2*z)

β変換を行うには、次の形を探します。

(λx.(…x…))(式)

これは、“λではじまるラムダ式”へ任意の式を適用した形ですね。(…x…) と書いてある部分はラムダ式の本体（関数定義の本体）を表します。この形を次の形に書き換えるのがβ変換です。

…式…

ちょっと分かりにくいな、手順を書いておこう：

まず、先頭の'λx.'は取り去って、ラムダ式（関数定義）本体を取り出します。
その本体内に出現する変数xをすべて（0箇所かもしれないし、100箇所かもしれない）、引数の式で置き換えます。
もちろん、変数の名前は'x'じゃなくてもいいです。
λ(x, y).(…x…y…) のようなときは、変数xだけじゃなくて変数yも対応する式で置き換えます。

先に挙げたβ変換の例で手順を確認してください。

β変換を何度か実行してみる

β変換は1度で終わることもありますが、何度か続けて実行できることもあります。次の例を見てください*3。

(λx.x*x)（(λy.2*y)(2)）

この式では、β変換を実行できる場所が外側と内側の二箇所あります*4。

外側を先にβ変換して、その結果をまたβ変換すると：

　(λx.x*x)（(λy.2*y)(2)）
→（(λy.2*y)(2)）*（(λy.2*y)(2)）
→ (2*2)*(2*2) // 二箇所ともβ変換した

内側を先にβ変換して、その結果をまたβ変換すると：

　(λx.x*x)（(λy.2*y)(2)）
→(λx.x*x)（(2*2)）
→ (2*2)*(2*2)

この例のように、β変換を何度か（0回かもしれない）続けて実行すると、いずれはβ変換ができなくなる（実行が停止する）気がしますが、そうとも限らないのです*5。が、実行順序をうまく選べば止まる場合だけを考えることにすると、次の事実が成立します。

β変換を何度か行うとき、どんな方法でやろうと（どこに注目して、どんな順序でやっても）、最終結果に到達したなら、その結果は変わらない。

このことは、“β変換による計算の最終結果＝ラムダ式の値”が存在するなら一意であることを保証します*6。あっ、言い忘れてたけど、2*2→4 のような変換（書き換え）はβ変換とは呼ばないので注意。組み込み演算子、組み込み関数の実行はラムダ計算とは切り離して考えたほうがいいですね。

中間まとめ、まだ続きがあるよ

疲れたので、今日はここまで。以下に用語のまとめ。表の「いつ？」蘭に「次回」と書いてあることは、次回に述べる予定。「参考」は特に言及しないけど憶えておいてもいい言葉。

いつ？	ラムダ計算の用語	JavaScriptの用語
今回	（狭い意味の）ラムダ式	関数リテラル、function式
参考	ラムダ変数、束縛変数	引数変数、仮引数
参考	ラムダ式の本体	関数定義の本体
今回	適用	関数に引数を渡した形を作ること
次回	自由変数	関数／プログラム内の未宣言変数
次回	α変換	引数変数の改名
今回	β変換、β還元	引数変数の置き換えによるマクロ展開