lambda_calculus.py

# the switch

def LEFT(a):
    def f(b):
        return a
    return f

def RIGHT(a):
    def f(b):
        return b
    return f

# these strings are illegal, just for demonstration
assert LEFT('5v')('gnd') == '5v'
assert RIGHT('5v')('gnd') == 'gnd'

# the truth

def TRUE(x):
    return lambda y: x

def FALSE(x):
    return lambda y: y

# these strings are illegal, just for demonstration
assert TRUE('5v')('gnd') == '5v'
assert FALSE('5v')('gnd') == 'gnd'

# the bools

def NOT(x):
    return x(FALSE)(TRUE)

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

def AND(x):
    return lambda y: x(y)(x)

def OR(x):
    return lambda y: x(x)(y)

assert AND(TRUE)(TRUE) == TRUE
assert AND(TRUE)(FALSE) == FALSE
assert AND(FALSE)(TRUE) == FALSE
assert AND(FALSE)( FALSE) == FALSE

assert OR(TRUE)(TRUE) == TRUE
assert OR(TRUE)(FALSE) == TRUE
assert OR(FALSE)(TRUE) == TRUE
assert OR(FALSE)( FALSE) == FALSE

# the maths

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))))

# illegal, just for demonstration
def incr(x):
    return x + 1

# illegal, just for demonstration
def star(x):
    return '*' + x

assert THREE(incr)(0) == 3
assert THREE(star)('') == '***'

# the arithmetic

# SUCC(TWO) ---> THREE
SUCC = lambda n: lambda f: lambda x: f(n(f)(x))

assert SUCC(ZERO)(incr)(0) == 1
assert SUCC(ONE)(incr)(0) == 2
assert SUCC(TWO)(incr)(0) == 3
assert SUCC(THREE)(incr)(0) == 4
assert SUCC(SUCC(THREE))(incr)(0) == 5

# api for a number is (fn)(x)

ADD = lambda x: lambda y: y(SUCC)(x)

assert ADD(ONE)(ONE)(incr)(0) == 2
assert ADD(TWO)(THREE)(incr)(0) == 5

MUL = lambda x: lambda y: lambda f: y(x(f))

assert MUL(TWO)(THREE)(incr)(0) == 6
assert MUL(FOUR)(THREE)(incr)(0) == 12