切削拙作記事『Schemeプログラミング一時間体験講座』で言及したこともあって，ラムダ計算の基礎表現をまとめておこうと思ったが，そのような記事はQiitaにもWeb全体にも星の数ほどあり（こちらの動画がおすすめ），それらを参照…で済ませようと思ったのだが，ふと，あらためてラムダ（λ）記法から説明するのではなく，最初からプログラミング言語のlambda式を用いたラムダ計算基礎としてまとめようと思い，この記事を書いてみた．
なお，元記事のSchemeではなくPythonにしたのは，Schemeだとあまりに簡単に書けてしまうのと，Pythonの方が需要がありそうだから（元記事どこ吹く風）．実行例については，Python3で確認している．
Pythonのlambda式の基礎
関数$f(x)=x$（引数に与えた値がそのまま戻ってくる）を表現したい時，関数名fは特に必要なく，Pythonではlambdaを用いて，次のように関数名なしの『lambda式』として表現できる．これを，ラムダ計算ではラムダ抽象（lambda abstraction）と呼ぶ．
lambda x: x
x:として記載したxが元の式の左辺の引数であり，その後のxが右辺の計算式である．
このlambda式を，Pythonインタプリタでxに実際に値を与えて実行したい場合は，次のように，lambda式全体を括弧でくくり，その後ろに，与える値を同じく括弧でくくって記述する．
>>> (lambda x: x)(10)
10
値を与えて関数を呼び出すことを，ラムダ計算では関数適用（application）と呼ぶ．なお，引数なしのlambda式も定義できる．
>>> (lambda: print("Hello"))()
Hello
引数として指定して実際に計算式で用いられている名前は束縛変数（bound variable）と呼ばれ，同じ名前を用いなければならない．逆に言えば，同じ名前であればどのようなものでもよく，次の通り，引数yを用いたlambda式も，$f(x)=x$と同じ関数と考えることができる．これを，ラムダ計算ではα変換（α-conversion）と呼ぶ．
>>> (lambda y: y)(10)
10
ラムダ計算では，関数の引数は原則としてひとつのみである（複数指定も可）．同様の表現を$g(x,y)=x+y$で行いたい場合は，lambdaと引数の記述を続けて記述する．関数適用したい時は，括弧でくくった値を同じく続けて記述する．
>>> (lambda x: lambda y: x + y)(10)(20)
30
複数の引数をもつ関数をひとつの引数の関数の組合せで表現することをカリー化（currying）と呼ぶ．カリー化された関数についてもα変換は有効であり，たとえば，上記のlambda式のうち，引数xの名前をzに変更しても，同じlambda式として扱われる．
>>> (lambda z: lambda y: z + y)(10)(20)
30
ただし，zではなく，もう一方の引数で用いられているyと同じ名前にしてしまうと，計算式そのものが変化してしまうため，同じlambda式とはならない（α変換できない）．次の実行例では，ひとつ目の引数の値(10)は次の引数の値(20)に上書きされ，20+20=40が出力されている．
>>> (lambda y: lambda y: y + y)(10)(20)
40
関数の引数は，数値だけでなく関数定義も指定できる．次の例では，引数fと引数xをとってf(x)*2の計算を行うlambda式に，引数fに(lambda y: y + 1)を，引数xに(10)を指定して関数適用している．
>>> (lambda f: lambda x: (f)(x) * 2)(lambda y: y + 1)(10)
22
上記は，fをlambda x: x + 1で書き換えることで，次のlambda式と同じ計算を行う．
>>> (lambda x: (x + 1) * 2)(10)
22
束縛変数に引数の値を適用して書き換えることを，ラムダ計算ではβ簡約（β-reduction）と呼ぶ．
なお，関数を引数に指定する場合は，指定する関数をdefで定義して渡すことも可能である．
>>> def inc(y): return y + 1
...
>>> (lambda f: lambda x: (f)(x) * 2)(inc)(10)
22
また，関数の戻り値として関数定義のlambda式を返すこともできる．これは，引数として受け取った関数定義を用いて構成した関数定義を返すことも含まれる．
>>> def inc_ret(): return lambda y: y + 1
...
>>> inc = inc_ret()
>>> def fnc_ret(f): return lambda x: (f)(x) * 2
...
>>> fnc = fnc_ret(inc)
>>> (fnc)(10)
22
関数の引数や戻り値にできる関数定義は，第一級オブジェクト（first-class object）と呼ばれる．また，関数定義を引数や戻り値とする関数を，高階関数（higher-order function）と呼ぶ．
応用例
真理値
ラムダ式によって，チャーチ真理値（Church booleans）と呼ばれる真偽表現が可能である．これは，引数をふたつとるlambda式をふたつ考え，真のlambda式では必ずひとつ目の引数を返し，偽のlambda式では必ずふたつ目の引数を返すというものである．
>>> (lambda x: lambda y: x)(10)(20) # 真
10
>>> (lambda x: lambda y: y)(10)(20) # 偽
20
ここで，True Falseを返す比較演算子>の代わりに，上記の真偽のlambda式を返すGTを定義する．
>>> def GT(a,b):
... if a > b:
... return lambda x: lambda y: x # 真
... else:
... return lambda x: lambda y: y # 偽
...
>>>
このGTを用いて判断分岐を行わせたのが次の実行例である．なお，print文もlambda式で記述して()で実行しているのは，真偽を判断して必要になった方のlambda式のみを実行させるためである．
>>> (GT)(20,10)('True')('False')
'True'
>>> (GT)(10,20)('True')('False')
'False'
>>> a = 10; b = 20
>>> (GT)(a,b)(lambda: print('a>b'))(lambda: print('a<=b'))()
a<=b
>>> a = 20; b = 10
>>> (GT)(a,b)(lambda: print('a>b'))(lambda: print('a<=b'))()
a>b
自然数と演算
ラムダ式によって，チャーチ数（Church numerals）と呼ばれる自然数を表現できる．考え方としては，引数として指定した関数が，同じく引数として指定された初期値に何回適用されたかによって表す．
>>> def zero(f): return lambda x: x
...
>>> def one(f): return lambda x: (f)(x)
...
>>> def two(f): return lambda x: (f)((f)(x))
...
>>> def three(f): return lambda x: (f)((f)((f)(x)))
...
>>> def four(f): return lambda x: (f)((f)((f)((f)(x))))
...
次は，適用関数をlambda x: x + 1，初期値を0とすることによって，チャーチ数を整数に変換している実行例である．
>>> def ToINT(ch): return (ch)(lambda x: x + 1)(0)
...
>>> (ToINT)(zero)
0
>>> (ToINT)(one)
1
>>> (ToINT)(two)
2
>>> (ToINT)(three)
3
>>> (ToINT)(four)
4
チャーチ数に+1する関数は，単純に，適用関数をもう一回適用する関数を返せば良い．次の記述例では，+1する関数ChINCが，チャーチ数chに適用関数fと初期値xを与えた関数を引数にした適用関数fを返している．
>>> def ChINC(ch): return lambda f: lambda x: (f)((ch)(f)(x))
...
>>> (ToINT)((ChINC)(two))
3
>>> (ToINT)((ChINC)(one))
2
>>> (ToINT)((ChINC)(three))
4
+1する関数を用いて，足し算が表現できる．
>>> def ChADD(ch): return lambda ch1: ((ch1)(ChINC))(ch)
...
>>> (ToINT)((ChADD)(one)(three)) # 1 + 3 = 4
4
>>> (ToINT)((ChADD)(four)(zero)) # 4 + 0 = 4
4
>>> (ToINT)((ChADD)(three)(two)) # 3 + 2 = 5
5
-1する関数は，関数適用を減らす必要があるため複雑であり，lamda式の中でlambda式を適用するラムダ計算を行う必要がある．
>>> def ChDEC(ch): return lambda f: lambda x: (ch)(lambda g: lambda h: (h)((g)(f)))(lambda u: x)(lambda u: (u))
...
>>> (ToINT)((ChDEC)(three))
2
>>> (ToINT)((ChDEC)(one))
0
>>> (ToINT)((ChDEC)(four))
3
-1する関数を用いて，引き算が表現できる．ここで想定されるチャーチ数は自然数であるため，結果は0以上であり，したがって，第1引数＞第2引数でなければならない．
>>> def ChSUB(ch): return lambda ch1: ((ch1)(ChDEC))(ch)
...
>>> (ToINT)((ChSUB)(three)(one)) # 3 - 1 = 2
2
>>> (ToINT)((ChSUB)(four)(one)) # 4 - 1 = 3
3
>>> (ToINT)((ChSUB)(four)(three)) # 4 - 3 = 1
1
掛け算とべき乗は，-1や引き算はもちろん，+1や足し算の関数よりも単純に表現できる．これは，チャーチ数自身が関数の適用回数で表現されており，その性質をそのまま利用すれば良いためである．
>>> def ChMUL(ch): return lambda ch1: lambda f: (ch1)((ch)(f))
...
>>> (ToINT)((ChMUL)(two)(three)) # => 2 * 3 = 6
6
>>> (ToINT)((ChMUL)(four)(three)) # => 4 * 3 = 12
12
>>> def ChPOW(ch): return lambda ch1: (ch1)(ch)
...
>>> (ToINT)((ChPOW)(two)(three)) # => 2^3 = 8
8
>>> (ToINT)((ChPOW)(two)(four)) # => 2^4 = 16
16
>>> (ToINT)((ChPOW)(one)(four)) # => 1^4 = 1
1
再帰関数
プログラミング言語で再帰関数を定義するには，通常，自分自身を呼び出すための関数名が必要である．しかし，ラムダ計算では，関数定義を関数名なしで表現する．ここでは，Yコンビネータ（Zコンビネータ）と呼ばれるlambda式を用いて，再帰関数の定義を行う．
まず，次のlambda式を考える．
(lambda x: ((x)(x)))(lambda x: ((x)(x)))
このlambda式をβ簡約，すなわち，左のlambda式の((x)(x))のxそれぞれに，右の(lambda x: ((x)(x)))を自己適用すると，同じlambda式が導かれる．このため，このlambda式をPythonで実行すると，いつまでも自己適用することになり，ループが発生する．
>>> (lambda x: ((x)(x)))(lambda x: ((x)(x)))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 1, in <lambda>
File "<stdin>", line 1, in <lambda>
File "<stdin>", line 1, in <lambda>
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
このループするlambda式のそれぞれ((x)(x))を引数にとる関数定義fを引数としてとるlambda式を考える．
lambda f: (lambda x: (f)((x)(x)))(lambda x: (f)((x)(x)))
ここで，引数として与えられた関数定義fの引数の名前をgとすると，gには左のlambda式の自己適用パターン((x)(x))が適用される．gを呼び出して((x)(x))を実行すると，((x)(x))のxには，関数定義fを含む右の同じlambda式がそれぞれ適用される．
したがって，関数定義f内で引数gが関数として呼び出されると，fおよび自己適用パターン((x)(x))を含む同じlambda式が適用されることになり，fについて再帰的な適用を繰り返すことが可能となる．
(f)(g)(lambda x: (f)((x)(x))
=> (f)((x)(x))(lambda x: (f)((x)(x)) # gの呼び出し1回目
=> (f)(lambda x: (f)((x)(x))(lambda x: (f)((x)(x))
=> (f)(f)(g)(lambda x: (f)((x)(x))
=> (f)(f)((x)(x))(lambda x: (f)((x)(x)) # gの呼び出し2回目
=> (f)(f)(lambda x: (f)((x)(x))(lambda x: (f)((x)(x))
=> (f)(f)(f)(g)(lambda x: (f)((x)(x))
=> (f)(f)(f)((x)(x))(lambda x: (f)((x)(x)) # gの呼び出し3回目
=> (f)(f)(f)(lambda x: (f)((x)(x))(lambda x: (f)((x)(x))
=> (f)(f)(f)(f)(g)(lambda x: (f)((x)(x))
=> ...
この式はYコンビネータ（Y combinator）と呼ばれ，名前のない関数定義に対して，その関数定義の引数の名前を用いて自分自身を呼び出す機能を提供する．しかし，Pythonでは引数の実行を先に行おうとするため，Yコンビネータを用いた場合でも，関数本体を実行する前に，ループするlambda式と同じ自己適用が先に起こってしまう．次は，Yコンビネータに，階乗計算を行う関数定義lambda g: lambda n: 1 if n == 0 else n * (g)(n-1)と値5を渡して実行『しようとした』例である．
>>> (lambda f: (lambda x: (f)((x)(x)))(lambda x: (f)((x)(x))))(lambda g: lambda n: 1 if n == 0 else n * (g)(n-1))(5)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 1, in <lambda>
File "<stdin>", line 1, in <lambda>
File "<stdin>", line 1, in <lambda>
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
自己適用の先行実行を避けるため，（真理値の最後の実行例のprint文と同じく）((x)(x))の部分を新しく設けたlambda式内の定義とし，実際に実行が必要になるまで，すなわち，上記で言う引数gが関数として呼び出されるまで，自己適用を据え置くようにする．ラムダ計算としては，η簡約（η-reduction）と呼ばれる書き換えの逆であるη展開（η-expansion）を行い，((x)(x))に余分な変数（ラムダ計算では自由変数と呼ばれる）yを導入してlambda y: ((x)(x))(y)に書き換える．
lambda f: (lambda x: (f)(lambda y: ((x)(x))(y)))(lambda x: (f)(lambda y: ((x)(x))(y)))
この記述によって，引数gに適用されるのは((x)(x))ではなくlambda y: ((x)(x))(y)であり，gがその引数と共に呼び出された時に初めてxに右の同じlambda式がそれぞれ適用されると共に，gの引数がyに適用されてfが実行される．Yコンビネータをこのように修正したlambda式を，Zコンビネータと呼ぶ．
次は，Zコンビネータに，階乗計算を行う関数定義lambda g: lambda n: 1 if n == 0 else n * (g)(n-1)と値5を渡して実行『した』例である．
>>> (lambda f: (lambda x: (f)(lambda y: ((x)(x))(y)))(lambda x: (f)(lambda y: ((x)(x))(y))))(lambda g: lambda n: 1 if n == 0 else n * (g)(n-1))(5)
120
次の例は，Zコンビネータに名前を付け，フィボナッチ数を求めるlambda式を適用したものである．
>>> def Z(f): return (lambda x: (f)(lambda y: ((x)(x))(y)))(lambda x: (f)(lambda y: ((x)(x))(y)))
...
>>> (Z)(lambda fib: lambda x: lambda f1: lambda f2: f1 if x == 0 else (fib)(x-1)(f2)(f1+f2))(40)(0)(1)
102334155
なお，次のように，関数本体と引数の値をYコンビネータに適用したlambda式でも再帰関数となる．この場合は，いずれの引数適用も関数本体と実際の値であるため，ループが先に実行されることはない．
>>> (lambda fib: ((fib)(fib))(40)(0)(1))(lambda fib: lambda x: lambda f1: lambda f2: f1 if x == 0 else ((fib)(fib))(x-1)(f2)(f1+f2))
102334155
備考
記事に関する補足
- Yコンビネータ（Zコンビネータ）の説明は（実は）かなりいいかげん．
-
lambdaの式を=で変数に代入するのはPEP8で非推奨なのがつらたん． - λ記法との対応付けのため，
f(10)を(f)(10)といった表記にしている箇所多数． - Scheme（Gauche）での記述例（GitHubリポジトリ）
参考文献
- Wikipedia：Lambda calculus, Church encoding
- Computerphile (YouTube)：Lambda Calculus, Essentials: Functional Programming's Y combinator
変更履歴
- 2020-07-29：Yコンビネータ（Zコンビネータ）の例に追記
- 2020-07-28：Yコンビネータ（Zコンビネータ）の例を追加
- 2020-07-27：初版公開