lambda.py

# booleans
TRUE = lambda a: lambda b: a
FALSE = lambda a: lambda b: b

assert TRUE(1)(0) == True
assert FALSE(1)(0) == False





# negation
NOT = lambda x: x(FALSE)(TRUE)

assert NOT(TRUE) is FALSE
assert NOT(FALSE) is TRUE





# conjuction and disjunction
AND = lambda x: lambda y: x(y)(x)
OR = lambda x: lambda y: x(x)(y)

assert AND(FALSE)(FALSE) is FALSE
assert AND(FALSE)(TRUE) is FALSE
assert AND(TRUE)(FALSE) is FALSE
assert AND(TRUE)(TRUE) is TRUE

assert OR(FALSE)(FALSE) is FALSE
assert OR(FALSE)(TRUE) is TRUE
assert OR(TRUE)(FALSE) is TRUE
assert OR(TRUE)(TRUE) is TRUE





# nand, nor, xor
NAND = lambda x: lambda y: NOT(AND(x)(y))
NOR = lambda x: lambda y: AND(NOT(x))(NOT(y))
XOR = lambda x: lambda y: AND(OR(x)(y))(NAND(x)(y))

assert NAND(FALSE)(FALSE) is TRUE
assert NAND(FALSE)(TRUE) is TRUE
assert NAND(TRUE)(FALSE) is TRUE
assert NAND(TRUE)(TRUE) is FALSE

assert NOR(FALSE)(FALSE) is TRUE
assert NOR(FALSE)(TRUE) is FALSE
assert NOR(TRUE)(FALSE) is FALSE
assert NOR(TRUE)(TRUE) is FALSE

assert XOR(FALSE)(FALSE) is FALSE
assert XOR(FALSE)(TRUE) is TRUE
assert XOR(TRUE)(FALSE) is TRUE
assert XOR(TRUE)(TRUE) is FALSE





# integers
def incr(x): return x + 1       # arbitrary helpers
def star(x): return x + "*"

ZERO = lambda f: lambda x: x
ONE = lambda f: lambda x: f(x)
TWO = lambda f: lambda x: f(f(x))
THREE = lambda f: lambda x: f(f(f(x)))
FOUR = lambda f: lambda x: f(f(f(f(x))))
FIVE = lambda f: lambda x: f(f(f(f(f(x)))))
SIX = lambda f: lambda x: f(f(f(f(f(f(x))))))

assert TWO(incr)(0) == 2
assert FOUR(star)("") == "****"


def eval(n): return n(incr)(0)

assert eval(FIVE) == 5
assert eval(SIX) == 6





# successor
SUCC = lambda n: lambda f: lambda x: f(n(f)(x))

assert eval(SUCC(ONE)) == 2
assert eval(SUCC(FOUR)) == 5
assert eval(SUCC(SUCC(SIX))) == 8





# addition and multiplication
ADD = lambda x: lambda y: y(SUCC)(x)
MUL = lambda x: lambda y: lambda f: y(x(f))

assert eval(ADD(ONE)(TWO)) == 3
assert eval(ADD(FOUR)(FIVE)) == 9

assert eval(MUL(ONE)(FIVE)) == 5
assert eval(MUL(TWO)(THREE)) == 6





# exponentiation
assert eval(TWO(THREE)) == 3**2     # note: it's backwards
assert eval(THREE(FOUR)) == 64





# ... subtraction?
PAIR = lambda a: lambda b: lambda p: p(a)(b)
LGET = lambda f: f(TRUE)
RGET = lambda f: f(FALSE)

t = PAIR(2)(3)
assert LGET(t) == 2
assert RGET(t) == 3





# predecessor ...
T = lambda p: PAIR(RGET(p))(SUCC(RGET(p)))      # (n, n+1)

t = FOUR(T)(PAIR(ZERO)(ZERO))
assert eval(LGET(t)) == 3
assert eval(RGET(t)) == 4


PRED = lambda n: LGET(n(T)(PAIR(ZERO)(ZERO)))

assert eval(PRED(FIVE)) == 4
assert eval(PRED(THREE(FOUR))) == 4**3 - 1





# subtraction!
SUB = lambda x: lambda y: y(PRED)(x)

assert eval(SUB(SIX)(FIVE)) == 1
assert eval(SUB(FOUR)(TWO)) == 2





# branching
IS_ZERO = lambda n: n(lambda _: FALSE)(TRUE)

assert IS_ZERO(ZERO) is TRUE
assert IS_ZERO(ONE) is FALSE
assert IS_ZERO(TWO) is FALSE





# factorials
def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

assert fact(3) == 6


FACT = lambda n: IS_ZERO(n)\
                (ONE)\
                (MUL(n)(FACT(PRED(n))))

try:
    FACT(FOUR) == 24
except RecursionError:
    pass    # Pythons eager evaluation of func args makes this blow up...
else:
    raise Exception



LAZY_TRUE = lambda a: lambda b: a()     # hack: fix eager recursion problem
LAZY_FALSE = lambda a: lambda b: b()
LAZY_IS_ZERO = lambda n: n(lambda _: LAZY_FALSE)(LAZY_TRUE)

FACT = lambda n: LAZY_IS_ZERO(n)\
                (lambda: ONE)\
                (lambda: MUL(n)(FACT(PRED(n))))
                            #   ^^^^ self-reference ?

assert eval(FACT(FOUR)) == 24


# rewrite it without self-reference
fact = (lambda f: lambda n: 1 if n==0 else n*f(f)(n-1))\
       (lambda f: lambda n: 1 if n==0 else n*f(f)(n-1)) # DRY: Do Repeat Yourself

assert fact(5) == 120


FACT = (lambda f: lambda n: LAZY_IS_ZERO(n)(lambda: ONE)(lambda: MUL(n)(f(f)(PRED(n)))))\
       (lambda f: lambda n: LAZY_IS_ZERO(n)(lambda: ONE)(lambda: MUL(n)(f(f)(PRED(n)))))

assert eval(FACT(SIX)) == 720





# Y combinator
Y = lambda f: (lambda x: f(lambda z: x(x)(z)))(lambda x: f(lambda z: x(x)(z)))

R_fact = lambda f: lambda n: 1 if n==0 else n*f(n-1)
fact = Y(R_fact)

assert fact(4) == 24


R_FACT = lambda f: lambda n: LAZY_IS_ZERO(n)(lambda: ONE)(lambda: MUL(n)(f(PRED(n))))
FACT = Y(R_FACT)

assert eval(FACT(FIVE)) == 120





# fibonacci
R_fib = lambda f: lambda n: 1 if n <= 2 else f(n-1)+f(n-2)
fib = Y(R_fib)

assert fib(10) == 55


R_FIB = lambda f: lambda n: LAZY_IS_ZERO(PRED(PRED(n)))(lambda: ONE)(lambda: ADD(f(SUB(n)(ONE)))(f(SUB(n)(TWO))))
FIB = Y(R_FIB)

TEN = MUL(TWO)(FIVE)
assert eval(FIB(TEN)) == 55


# Source: [PyCon 2019 - Lambda Calculus from the Ground Up - David Beazley] (https://www.youtube.com/watch?v=pkCLMl0e_0k)