Pythonでラムダ計算

いままでラムダ計算を直視してなかったので、せっかくなのでPyhonのlambdaで実装してみよう。わーいラムダだー何でもできるぞー。いえーい。

参考資料

ラムダ計算基礎文法最速マスター - 貳佰伍拾陸夜日記

チャーチ数

ZERO  = lambda s, z: z
ONE   = lambda s, z: s(z)
TWO   = lambda s, z: s(s(z))
THREE = lambda s, z: s(s(s(z)))
FOUR  = lambda s, z: s(s(s(s(z))))
FIVE  = lambda s, z: s(s(s(s(s(z)))))

S = lambda n: n + 1
Z = 0
INT = lambda n: n(S, Z)

INT(ZERO)
#=> 0
INT(ONE)
#=> 1
INT(TWO)
#=> 2
INT(THREE)
#=> 3
INT(FOUR)
#=> 4
INT(FIVE)
#=> 5

リスト

FST = lambda p: p(lambda x, y: x)
SND = lambda p: p(lambda x, y: y)
LIST = lambda m, n: lambda x: x(m, n)

L1 = LIST(ONE, TWO)
L2 = LIST(THREE, FOUR)

INT(FST(L1))
#=> 1
INT(SND(L2))
#=> 4

L3 = LIST(L1, L2)
INT(SND(FST(L3)))
#=> 2

L4 = LIST(ONE,LIST(TWO,LIST(THREE,LIST(FOUR,FIVE))))
INT(SND(SND(SND(SND(L4)))))
#=> 5

条件分岐

TRUE = lambda x, y: x
FALSE = lambda x, y: y
IF = lambda expr, x, y: expr(x, y)

INT(IF(TRUE, ONE, TWO))
#=> 1
INT(IF(FALSE, ONE, TWO))
#=> 2

EXPR = lambda pyexpr: pyexpr and TRUE or FALSE
BOOL = lambda expr: expr('TRUE', 'FALSE')

BOOL(EXPR(ONE==ONE))
#=> 'TRUE'
INT(IF(EXPR(ONE==TWO), ONE, TWO))
#=> 2
BOOL(IF(EXPR(INT(ONE)<INT(TWO)), TRUE, FALSE))
#=> 'TRUE'

計算

import functools
P = functools.partial

S = lambda n: n + 1
Z = 0
INT = lambda n: n(S)

SUM = lambda m,n: m(S,n(S,Z))
MUL = lambda m,n: n(P(m,S),Z)
#=> 25

うむ。チャーチ数に保ったまま出力する方法がわからん。下手にSみたいな函数を適用してしまふのがいけないのか……?

疲れたので、けふはここまで。