# Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

## Friday, February 27, 2009

### Y Combinator in Python

I've been thinking again, and it hurts (its a good hurt though).

Somehow I came across the term 'Y combinator' again and this time
followed it up. It seems that it is a way to create a function
that adds recursion to functions that don't have recursion in
their definition.

I am still learning from mainly href="http://mvanier.livejournal.com/2897.html">this
explanation 'The Y Combinator (Slight Return)' by Mike Vanier. but I've

Here is a definition of a factorial function in Python:

`factorial = lambda n: (1  color="#804040">if n<2  color="#804040">else n*factorial(n-1))`

it is easy to see that it is recursive as the lambda expression is
assigned to a name and the name, fibonacci, is used in the lambda
expression.

We can mechanically generate a related function by calling the recursed
call 'f' and by wrapping the expression in an outer lambda expression
of f:

`fac = lambda f:  color="#804040">lambda n: (1  color="#804040">if n<2  color="#804040">else n*f(n-1))`

Notice that fac is not a recursive function as fac is not called inside
its definition. The fac function does not, in itself, compute the
factirial, but wrapping it in the Y combinator function Y produces a
function that computes a factorial, i.e:

`Y(fac)(i) == factorial(i)`

I am not too clear on the whole derivation of Y but Y,is itself a non
recursive function and, in Python is given by:

`Y = lambda f: ( color="#804040">lambda x: x(x))( color="#804040">lambda y: f( color="#804040">lambda z: y(y)(z)))`

here follows my interactive session where I am using it to compute
factorials and fibonacci numbers by adding recursion to non-recursive
functions:

`>>> Y = lambda f: ( color="#804040">lambda x: x(x))( color="#804040">lambda y: f( color="#804040">lambda z: y(y)(z)))>>> fac =  color="#804040">lambda f:  color="#804040">lambda n: (1  color="#804040">if n<2  color="#804040">else n*f(n-1))>>> [ Y(fac)(i)  color="#804040">for i  color="#804040">in range(10) ][1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]>>> fib =  color="#804040">lambda f:  color="#804040">lambda n: 0  color="#804040">if n == 0  color="#804040">else (1  color="#804040">if n == 1  color="#804040">else f(n-1) + f(n-2))>>> [ Y(fib)(i)  color="#804040">for i  color="#804040">in range(10) ][0, 1, 1, 2, 3, 5, 8, 13, 21, 34]>>>`

I need to set this investigation aside, then come back to it.

1. One of the problems Y combinator solves is naming and assignment. You can compute recursive functions totally anonymously, like this:

>>> ( lambda func:
... ( lambda f: func(lambda x: (f(f))(x)) ) ( lambda f: func(lambda x: (f(f))(x)) )
... ) (lambda f: lambda n: 1 if n < 2 else n*f(n-1)) (10)
3628800

Neat post! I tried to wrap my head around Y a year or so ago. Definitely a mind-expanding experience :)

2. Thanks Steven, you're encouraging!

One of the things that motivated me at the start, was that most of the explanations were in Lispy languages like scheme. from the start, I wanted to see how to do it in Python as well as gain an insight into the maths of the Y combinator.

3. After some deliberation, I decided to turn the above into a task for Rosetta Code
here: http://www.rosettacode.org/wiki/Y_combinator