beazley.py

# https://www.youtube.com/watch?v=5C6sv7-eTKg

# helpers
def _incr(num):
    return num + 1

def show(num):
    return print(num(_incr)(0))


# using named function to get better __repr__ when printing
def TRUE(x): return lambda y: x
def FALSE(x): return lambda y: y


NOT = lambda x: x(FALSE)(TRUE)
AND = lambda x: lambda y: x(y)(x)
OR = lambda x: lambda y: x(x)(y)

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

CONS = lambda a: lambda b: (lambda s: s(a)(b))
CAR = lambda c: c(TRUE)
CDR = lambda c: c(FALSE)

T = lambda p: CONS(SUCC(CAR(p)))(CAR(p))
PRED = lambda n: CDR(n(T)(CONS(ZERO)(ZERO)))

ADD = lambda x: lambda y: y(SUCC)(x)
MUL = lambda x: lambda y: lambda f: y(x(f))
SUB = lambda x: lambda y: y(PRED)(x)

ISZERO = lambda n: n(lambda f: FALSE)(TRUE)

# note on SUB, if second argument is greater or equal, the result is always ZERO
GTE = lambda x: lambda y: ISZERO(SUB(y)(x))
LTE = lambda x: lambda y: ISZERO(SUB(x)(y))
EQ = lambda x: lambda y: AND(GTE(x)(y))(LTE(x)(y))
# could probably be done using ISZERO as well:
GT = lambda x: lambda y: AND(GTE(x)(y))(NOT(EQ(x)(y)))
LT = lambda x: lambda y: AND(LTE(x)(y))(NOT(EQ(x)(y)))

# Y-Combinator, enables to create recursion without referring global variables
Y = (lambda f:
        (lambda x: f(lambda z: x(x)(z)))  # used "lambda z:" to lazy evaluate
        (lambda x: f(lambda z: x(x)(z)))
     )

# local function to calculate factorial of a number "n"
R = lambda f: (
    lambda n: (
        ISZERO(n)
        (lambda: ONE)  # used lambda to lazy evaluate
        (lambda: MUL(n)(f(PRED(n))))
    )()  # evaluate
)

# create final factorial function
FACT = Y(R)

R2 = lambda f: (
    lambda n: (
        LTE(n)(TWO)
        (lambda: ONE)
        (lambda: ADD(f(PRED(n)))(f(PRED(PRED(n)))))
    )()
)

FIB = Y(R2)

# factorial of 5 = 120
show(FACT(FIVE))

# 10th fibonacci = 55
show(FIB(MUL(FIVE)(TWO)))