関数型プログラミング事始め (35) ラムダ計算(2)

関数型プログラミングがはじめての方へ贈る入門の書
前節：ラムダ計算(1)　次節：イミュータブル(1)
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)

ラムダ計算は３個の規則だけで関数の動作が記述できます。ここではラムダ計算の例としてカリー化とチャーチ数を取り上げて、ラムダ計算の様子を見ていきます。
ラムダ計算は関数型プログラミングの計算モデルのひとつですが、これを知らなくても関数型は使えます。しかしラムダ計算を知っていると関数型プログラミングの本質に触れることができます。

(4) ラムダ計算の例

ラムダ計算はたった３個の規則だけで関数の動作がすべて記述できる万能な計算モデルです。しかし逆に考えれば、3個だけの少数の規則であるため、計算は長大になり面倒になってしまいます。

実際の関数型プログラミングでは、ラムダ計算は言語処理系が自動的に実行し、関数型プログラマはこの計算を頭の中だけで暗黙的に実施し、意識していないでしょう。しかしラムダ計算を知っていると関数型プログラミングの本質に触れることができます。

ここではOK! ISLispを使ってラムダ計算を見ていきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。

> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>

(a) カリー化

カリー化(currying)とは２個以上の引数を取る関数を、１個の引数を取る関数に変換することです。

その変換の原理は、第１引数を取る関数に変換し、その関数では第２引数以降の残りの引数を取る関数を返す高階関数にします。例としてf(x,y)を考えます。これはf(x,y)の関数を、g(x)に変換して、g(x)はh(y)の関数を返す関数になります。

これを匿名関数のラムダ式で表記すると、λx.λy.fxyとなります。ラムダ計算では束縛変数は1個ですが、λx.λy.fxyをλxy.fxyと略記することで、複数の束縛変数を表記しています。
しかし実際には複数引数の関数適用は、カリー化をして、1引数の関数適用を複数回実施することになります。

これをLispで見ていきます。雰囲気的には(lambda (x y) (f x y))を(lambda (y) (lambda (x) (funcall (f x) y)))のように変換するイメージです。なお直接の関数適用の((f x) y)はISLispやCommon Lispでは第1引数が関数名でもラムダ式でもないのでエラーになりますので、funcallを使っています。

例としてx - yのプログラムを考えます。これをLispのプログラムで見ていきます。

ISLisp>((lambda (x y) (- x y)) 2 1)
1

2引数のラムダ式(lambda (x y) …)は、引数xに2、引数yに1を適用することで、(- 2 1)が実行され、1を返します。

ISLisp>((lambda (x) (lambda (y) (- x y))) 2)
#<UFUNCTION 0026D236: #<LAMBDA>>

上記の2引数の関数をカリー化すると、((lambda (x) (lambda (y) (- x y))) 2)となります。つまり(lambda (y) (- 2 y))の関数を返します。

ISLisp>(funcall ((lambda (x) (lambda (y) (- x y))) 2) 1)
1

上記は(lambda (y) (- 2 y))の匿名関数に、引数yに1を適用することになり、(- 2 1)となり、1を返します。

このように、複数引数を1引数として関数適用をすることができます。なお、実際のLisp処理系では、効率化のためにカリー化をせずに、複数の引数をそのまま関数適用する実装になっています。

(b) チャーチ数

ラムダ計算では以下のように数値をラムダ式で表記できます。これをチャーチ数(Church number)と言います。

数値: 対応するラムダ式
0: λfx.f
1: λfx.fx
2: λfx.f(fx)
3: λfx.f(f(fx))
4: λfx.f(f(f(fx)))
…
n: λfx.f(f(…fx…))

引数をプラス1する関数suc(x)は、λxfy.f(xfy)となります。

suc(0)が1になることを見ていきます。つまりsuc(λfx.f)がλfx.fxになることを見ていきます。なお見やすくするために、0をλf'x'とのようにして、名前の変更をしておきます。

suc(λf'x'.f') =
(λxfy.f(xfy))λf'x'.f' = λfx.f((λx'f'.f')fx) = λfx.(f(λf'.f')y) = λfy.fy = λfx.fx = 1

なおSUC(1)が2になることは（私は面倒なので）みなさまにお任せします。

このようにラムダ式で整数の表現が可能になり、ラムダ計算は万能（チューリング完全）です。・・・でも面倒で疲れます。

これをLispでは以下のようになります。
0: (lambda (f x) f)
1: (lambda (f x) (funcall f x))
…
SUC(x):(lambda (x) (lambda (f) (lambda (y) (funcall f (funcall (funcall f x) y)))))

今回はラムダ計算の例を見てきました。カリー化でも面倒でしたが、チャーチ数になると、これはもう人類では魑魅魍魎の面倒さです。

でも安心してください。Lispはラムダ計算を（比較的）真面目に実装していますので、（比較的）安心してください。
ここで(比較的)と書いているのは、実はLispは（Lisperの検閲によって削除されました）。

(予告) 3.5 イミュータブルデータ

次回は値が不変であるイミュータブルなデータ構造を見ていくことにします。