Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
# coding: utf-8
# Python code to demonstrate the Y-combinator using
# the working example presented by Jim Weirich.
def demo():
fact_1 = lambda n: 1 if n == 0 else (n * fact_1 (n - 1))
# 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('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('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')
# 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')
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')
# 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.')
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')
# 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')
# checking y-combinator as a proper fix function
working_function = fact_2(ycombinator(fact_2))
print('testing ycombinator works as a `fix` function')
# 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')
if __name__ == '__main__':
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.