I once read this Python implementation of Y-combinator in a legacy code deposit:
def Y_combinator(f):
return (lambda x: f(lambda *args: x(x)(*args)))(
lambda x: f(lambda *args: x(x)(*args))
)
And there exists an example usage:
factorial = Y_combinator(
lambda f: lambda n: 1 if n == 0 else n * f(n - 1)
)
Could anyone be so kind to teach how should I read the code to interpret it? I am totally lost in trying to connect those lambdas altogether...
With some hesitation I will try to answer your question. I have been programming in Python for more than twenty years and it took me more than an hour to unravel this.
I'll start with a simple observation about lambda - one that we all know. Lambda expressions create anonymous functions, and therefore they can always be replaced with an explicitly named def function.
def square(x):
return x * x
sq = lambda x: x * x
print(square)
print(square(2))
print(sq)
print(sq(2))
sq = square
print(sq)
print(sq(2))
In this trivial example, sq and square are, for all intents and purposes, the same thing. Both are function objects. This code prints:
<function square at 0x7f25b2ebc040>
4
<function <lambda> at 0x7f25b2ebc2c0>
4
<function square at 0x7f25b2ebc040>
4
Notice that once we have defined square, we can literally cut and paste "square" in place of "lambda x: x * x".
Now look at this code from your example.
factorial = Y_combinator(
lambda f: lambda n: 1 if n == 0 else n * f(n - 1)
)
Start replacing lambda expressions with def functions. Begin with the innermost one, lambda n:.
def fn(n):
return 1 if n == 0 else n * f(n-1)
There's a problem here because "f" is not defined. That's because this function must be nested inside another one, the lambda f: part.
def ff(f):
def fn(n):
return 1 if n == 0 else n * f(n-1)
return fn
Everything is defined now, and this function ff is equivalent to the original line of code containing the two nested lambda expressions. We can check that - I'm borrowing the exact definition of Y_combinator and factorial from your code.
factorial2 = Y_combinator(ff)
print(factorial)
print(factorial(3))
print(factorial2)
print(factorial2(3))
The result:
<function <lambda>.<locals>.<lambda> at 0x7f25b2ebc220>
6
<function ff.<locals>.fn at 0x7f25b2ebc540>
6
Note that Y_combinator takes one argument, a function, and returns another function.
In your code, the argument to Y_combinator is also a function that takes one argument, a function, and returns another function. lambda f: returns another lambda.
The new function ff is also a function that takes one argument, a function, and returns another function.
Are you confused yet?
Now I'm going to apply the same trick to Y_combinator. Start with the innermost lambda and work outward. Eventually you get this, which I named combinator1. It's the equivalent of Y_combinator but it's be "de-lambda-ized" (delambdinated?):
def combinator1(f):
def fx(x):
def fargs(*args):
return x(x)(*args)
return f(fargs)
return fx(fx)
factorial3 = combinator1(ff)
print(factorial3)
print(factorial3(3))
Output:
<function ff.<locals>.fn at 0x7f25b2ebc720>
6
It works.
Yes, it's a function inside of a function inside of another function. That's what all those nested lambdas give you.
Notice how the recursive call is implemented as fx(fx). It's a function that can call itself. It's a rather neat trick in an insane sort of way. There is only one line in this entire plate of spaghetti that actually does anything (the if else statement). The rest of the code is messing around with function objects.
I can see no reason ever to do this. With Python's ability to do recursion and its ability to nest one function inside another, I just don't see any use case. But I haven't thought about it very hard. If I'm wrong I bet someone here will enlighten me.
For the record, here is a complete implementation of factorial in python:
def nice_factorial(n):
return 1 if n == 0 else n * nice_factorial(n-1)
print("Nice solution:")
print(nice_factorial)
print(nice_factorial(3))
Output:
Nice solution:
<function nice_factorial at 0x7f25b2ebc860>
6
I'll leave it up to others to decide which approach you like better.