Y combinator in Python

y_combinator.py

TRUE = lambda x: lambda y: x
FALSE = lambda x: lambda y: y

PAIR = lambda a: lambda b: lambda f: f(a)(b)

D = lambda x: PAIR(x)(x)

FIRST = lambda p: p(TRUE)
SECOND = lambda p: p(FALSE)

ZERO = lambda f: lambda x: x

# not lambda-terms!!! just convenience
succ = lambda x: x + 1
zero = 0
n = lambda _: _(succ)(zero)

Z = lambda n: n(lambda x: FALSE)(TRUE)

SUCC = lambda n: lambda f: lambda x: f(n(f)(x))
ONE = SUCC(ZERO)
TWO = SUCC(ONE)
THREE = SUCC(TWO)

assert n(ONE) == 1
assert n(TWO) == 2
assert n(THREE) == 3

SH = lambda p: PAIR(SUCC(FIRST(p)))(FIRST(p))

PRED = lambda n: SECOND(n(SH)(D(ZERO)))

SUM = lambda n: lambda m: n(SUCC)(m)
MULT = lambda n: lambda m: n(SUM(m))(ZERO)

# Everything is a function of a single variable so
#     x(x)
# is indeed the same as
#     lambda n: x(x)(n)
# only we make the evaluation lazy so that we can
# define new lambda-terms with the combinators.
H = lambda f: lambda x: f(lambda n: x(x)(n))
Y = lambda f: H(f)(H(f))

# Alternatively:
# OMEGA = lambda x: x(x)
# Y = lambda f: OMEGA(lambda x: f(lambda n: x(x)(n)))

# We also need to make PAIR behave lazily, like an
# if ... then ... else statement would. Indeed
#     PAIR(A)(B)(C)  ~  A if C is TRUE else B
LAZY_TRUE = lambda x: lambda y: x()
LAZY_FALSE = lambda x: lambda y : y()
LAZY_Z = lambda n: n(lambda x: LAZY_FALSE)(LAZY_TRUE)

_FACT = lambda g: lambda n: PAIR \
    (lambda: ONE) \
    (lambda: MULT(n)(g(PRED(n)))) \
    (LAZY_Z(n))
FACT = Y(_FACT)

assert n(FACT(THREE)) == 6

# Let's try with if ... then ... else

_FACT = lambda g: lambda n: ONE if Z(n) is TRUE else MULT(n)(g(PRED(n)))
FACT = Y(_FACT)

assert n(FACT(SUCC(THREE))) == 24