ycombinator.py

# coding: utf-8

# Python code to demonstrate the Y-combinator using
# the working example presented by Jim Weirich.
# https://www.infoq.com/presentations/Y-Combinator


def demo():

    fact_1 = lambda n: 1 if n == 0 else (n * fact_1 (n - 1))

    print('fact_1(5)')
    print(fact_1(5))

    # since we do not have assignments in λ-calculus, we cannot use recursion.
    # we will use a place-holder function called `error`

    error = lambda x: ('Should not be called')

    wrapper = lambda n: 1 if n == 0 else (n * error(n - 1))
    print('Wrapper only works for 0. Therefore we need to set up a tree.')
    print(wrapper(0))
    print('Does not work for n > 0')
    # error
    # print(wrapper(5))

    print('passing error as argument')
    wrapper = lambda f: lambda n: 1 if n == 0 else (n * (error(n - 1)))
    print(wrapper(error)(0))
    print('Does not work for n > 0')
    # error, since we do not update the error call yet
    # print(wrapper(error)(1))

    print('Start up calling `fact` on itself using w(w). Setup the recursive call.')
    wrapper = (lambda w: (w(w)))(lambda f: lambda n: 1 if n == 0 else (n * (f(f)(n - 1))))
    print('first iteration works for n > 0, since we call fact(fact) recursively')
    print(wrapper(5))

    # lets refactor wrapped and separate out recursive and factorial logic
    # using tenannt correspondence principle we have
    wrapper = (lambda w: (w(w)))(lambda f: lambda n: 1 if n == 0 else (n * (lambda: (f(f)(n - 1)))()))
    print('after isolating recursive code-1')
    print(wrapper(5))

    wrapper = (lambda w: (w(w)))(lambda f: lambda n: 1 if n == 0 else (n * (lambda m: (f(f)(m)))(n-1)))
    print('after isolating recursive code-2-after-introducing-binding')
    print(wrapper(5))

    # extract out the recursive code and bind it
    wrapper = (lambda w: (w(w)))(lambda f: ((lambda code: lambda n: 1 if n == 0 else (n * code(n-1)))((lambda m: (f(f)(m))))))

    print('after isolating recursive code-3-after factoring of recursive code.')
    print(wrapper(5))

    fact_2 = (lambda code: lambda n: 1 if n == 0 else (n * code(n-1)))
    wrapper = (lambda f1: (lambda w: (w(w)))(lambda f: (f1(lambda m: (f(f)(m))))))(fact_2)
    print('after factoring out the `fact` function')
    print(wrapper(5))

    # splitting up the above definitions and calls as separate statements
    fact_2 = (lambda code: lambda n: 1 if n == 0 else (n * code(n-1)))
    ycombinator = (lambda f1: (lambda w: (w(w)))(lambda f: (f1(lambda m: (f(f)(m))))))
    working_function = ycombinator(fact_2)
    print('using ycombinator')
    print(working_function(5))

    # checking y-combinator as a proper fix function
    working_function = fact_2(ycombinator(fact_2))
    print('testing ycombinator works as a `fix` function')
    print(working_function(5))

    # making Y-combinator looks like the one on Rosetta
    #Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args))) <- from Rosetta
    # rename f1=f, w=x, f1 , f=y, and args=m (since, our f only takes one argument)
    ycombinator = (lambda f1: (lambda w: (w(w)))(lambda f: (f1(lambda m: (f(f)(m))))))
    ycombinator = (lambda f: (lambda x: (x(x)))(lambda y: (f(lambda m: (y(y)(m))))))
    working_function = fact_2(ycombinator(fact_2))
    print('testing ycombinator after renaming variables to look like the one on Rosetta')
    print(working_function(5))



if  __name__ == '__main__':
    demo()