Fibonacci implemented with barely any use of anything that isn't a function

sillyfib.py

def Zero(zero_val):
    return lambda rec_func: zero_val


def Succ(nat):
    return lambda zero_val: lambda rec_func: rec_func(nat)


def add(a):
    return (lambda b:
                a
                (b)
                (lambda prev_a:
                    Succ(add(prev_a)(b))
                )
            )


def sub(a):
    return (lambda b:
                b
                (a)
                (lambda prev_b:
                    a
                    (Zero) # This means 2 - 3 = 0, saturating subtraction
                    (lambda prev_a:
                        sub(prev_a)(prev_b)
                    )
                )
            )


def mult(a):
    return (lambda b:
                a
                (Zero)
                (lambda prev_a:
                    prev_a
                    (b)
                    (lambda _:
                        add
                        (b)
                        (mult(b)(prev_a))
                    )
                )
             )


def funcFalse(a):
    return lambda b: a


def funcTrue(a):
    return lambda b: b


def And(a):
    return lambda b: a(funcFalse)(b(funcFalse)(funcTrue))


def Or(a):
    return lambda b: a(b(funcFalse)(funcTrue))(funcTrue)


def Not(a):
    return a(funcTrue)(funcFalse)


def Eq(a):
    return (lambda b:
                a
                (b(funcTrue)(lambda _: funcFalse)) # If a is zero and b is zero, true, if b isn't zero,
                (lambda prev_a:
                    b
                    (funcFalse)
                    (lambda prev_b:
                        Eq(prev_b)(prev_a)
                    )
                )
           )


def Leq(a):
    return (lambda b:
                a
                (funcTrue)
                (lambda prev_a:
                    b(funcFalse)(lambda prev_b: Leq(prev_a)(prev_b))
                )
           )


def Geq(a):
    return lambda b: Leq(b)(a)


def Le(a):
    return lambda b: And(Leq(a)(b))(Not(Eq(a)(b)))


def Gr(a):
    return lambda b: Le(b)(a)


def flip(f):
    return lambda a: lambda b: f(b)(a)


def pair(a):
    return lambda b: lambda p: p(a)(b)


def left(a):
    return lambda b: a


def right(a):
    return lambda b: b


def let(x):
    return lambda f: f(x)


def let_pair(p):
    return lambda f: f(p(left))(p(right))


def quotRem(n):
    return (lambda d:
                n
                (pair(Zero)(Zero))
                (lambda prev_n:
                    let_pair
                    (quotRem(prev_n)(d))
                    (lambda q:
                        (lambda r:
                            (Eq(Succ(r))(d)
                                (pair(q)(Succ(r)))
                                (pair(Succ(q))(Zero))
                            )
                        )
                    )
                )
           )


One       = Succ(Zero)
Two       = Succ(One)
Three     = Succ(Two)
Four      = mult(Two)(Two)
Five      = Succ(Four)
Six       = Succ(Five)
Seven     = Succ(Six)
Eight     = mult(Two)(Four)
Nine      = Succ(Eight)
Ten       = Succ(Nine)
Eleven    = Succ(Ten)
Twelve    = Succ(Eleven)
Thirteen  = Succ(Twelve)
Fourteen  = Succ(Thirteen)
Fifteen   = Succ(Fourteen)
Sixteen   = mult(Two)(Eight)
Seventeen = Succ(Sixteen)
Eighteen  = Succ(Seventeen)
Nineteen  = Succ(Eighteen)
Twenty    = Succ(Nineteen)


def nat_to_digit(nat):
    return (nat('0')
               (lambda One:
                One('1')
                   (lambda Two:
                    Two('2')
                       (lambda Three:
                        Three('3')
                           (lambda Four:
                            Four('4')
                               (lambda Five:
                                Five('5')
                                   (lambda Six:
                                    Six('6')
                                       (lambda Seven:
                                        Seven('7')
                                           (lambda Eight:
                                            Eight('8')
                                               (lambda Nine:
                                                Nine('9')
                                                (lambda _: 'error, not digit')
                                               )
                                           )
                                       )
                                   )
                               )
                           )
                       )
                   )
               )
           )


def nat_to_string(nat):
    return (Leq(nat)(Nine)
               (lambda:
                    let_pair
                    (quotRem(nat)(Ten))
                    (lambda q:
                        (lambda r:
                            nat_to_string(q) + nat_to_digit(r)
                        )
                    )
               )
               (lambda: nat_to_digit(nat))
           )() # Lambda needed to avoid computing branch not used


def nat_to_int(nat):
    return nat(0)(lambda x: nat_to_int(x) + 1)


def int_to_nat(n):
    nat = Zero
    for _ in range(n):
        nat = Succ(nat)
    return nat


def nat_fib(nat):
    return (
        nat
        (One)
        (lambda nat_prev:
            nat_prev
            (One)
            (lambda nat_prev_prev:
                add
                (nat_fib(nat_prev))
                (nat_fib(nat_prev_prev))
            )
        )
    )


def fibonacci(n):
    return nat_to_string(nat_fib(int_to_nat(n)))