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.
disclaimers:
now the explanation:
def Y(f):
return (lambda x: f(lambda *args: x(x)(*args)))(
lambda x: f(lambda *args: x(x)(*args))
)
factorial = Y(lambda f: lambda n: 1 if n == 0 else n * f(n - 1))
factorial(5) # 120
# Y = λf.(λx.f (x x))(λx.f (x x)) # Y-combinator definition
def λf(f):
λx = lambda x: f(lambda *args: x(x)(*args))
return (λx)(λx)
Y = λf
def λf2(f):
λn = lambda n: 1 if n == 0 else n * f(n - 1)
return λn
factorial = Y(λf2)
factorial(5) # 120
def λf(f):
def λx(x):
# x_x = lambda *args: x(x)(*args) # corresponds to (x x) expression in the definition
def x_x(*args):
return x(x)(*args)
return f(x_x)
return (λx)(λx)
Y = λf
def λf2(f): # f will be λf2
def λn(n):
return 1 if n == 0 else n * f(n - 1)
return λn
factorial = Y(λf2)
factorial(5) # 120
import inspect
def λf(f):
print(f"[{len(inspect.stack()):2d}] λf(f={f.__name__})")
def λx(x):
print(f"[{len(inspect.stack()):2d}] λx(x={x.__name__})")
def x_x(*args):
print(f"[{len(inspect.stack()):2d}] x_x(args=(", end="")
for a in args:
if callable(a):
print(f"{a.__name__}", end="")
else:
print(a, end="")
print("))")
return x(x)(*args)
return f(x_x)
return (λx)(λx)
Y = λf
def λf2(f):
print(f"[{len(inspect.stack()):2d}] λf2(f={f.__name__})")
def λn(n):
print(f"[{len(inspect.stack()):2d}] λn(n={n})")
return 1 if n == 0 else n * f(n - 1)
return λn
factorial = Y(λf2)
print(f"factorial={factorial.__name__}")
# after this it prints (in ipython, so stack doesn't start with 0th frame):
# [24] λf(f=λf2) # y-combinator (λf) gets called with λf2, and
# [25] λx(x=λx) # λx gets called and it now has captured reference to λf2 (from parent's arguments)
# [26] λf2(f=x_x) # λf2 gets called with x_x, it returns λn
# factorial=λn # but λn now has reference to x_x function
print("=============")
factorial(2)
# prints:
# [24] λn(n=2) # factorial (λn) gets called
# [25] x_x(args=(1)) # it calls to x_x(n-1)
# [26] λx(x=λx) # loop
# [27] λf2(f=x_x)
# [26] λn(n=1) # we call factorial (λn) with (n-1) now
# [27] x_x(args=(0)) # loop
# [28] λx(x=λx)
# [29] λf2(f=x_x)
# [28] λn(n=0) # factorial(0)
so basically, we need to feed some function λf2, that returns another function λn, that just gets called infinitely. we can substitute λn with a simpler function, that just prints the iteration number:
def λf2(f):
print(f"[{len(inspect.stack()):2d}] λf2(f={f.__name__})")
def loop(iteration):
if iteration > 5:
return # break the loop
print(f"[{len(inspect.stack()):2d}] loop({iteration=})")
return f(iteration+1)
return loop
loop5 = Y(λf2)
print("====")
print(f"loop5={loop5.__name__}")
loop5(0)
# output:
# [24] λf(f=λf2)
# [25] λx(x=λx)
# [26] λf2(f=x_x)
# ====
# loop5=loop
# [24] loop(iteration=0)
# [25] x_x(args=(1))
# [26] λx(x=λx)
# [27] λf2(f=x_x)
# [26] loop(iteration=1)
# [27] x_x(args=(2))
# [28] λx(x=λx)
# [29] λf2(f=x_x)
# [28] loop(iteration=2)
# [29] x_x(args=(3))
# [30] λx(x=λx)
# [31] λf2(f=x_x)
# [30] loop(iteration=3)
# [31] x_x(args=(4))
# [32] λx(x=λx)
# [33] λf2(f=x_x)
# [32] loop(iteration=4)
# [33] x_x(args=(5))
# [34] λx(x=λx)
# [35] λf2(f=x_x)
# [34] loop(iteration=5)
# [35] x_x(args=(6))
# [36] λx(x=λx)
# [37] λf2(f=x_x)
of course, you can just step through this in a debugger, but i think printing in this case gives a better picture of what gets called.
