That is the Y-combinator implemented using the U-combinator.
The U and Y combinators both enable recursion using only lambdas. These examples are fine as a learning tool and can teach you about the amazing capability of lambdas and the closure property. However, it makes sense to see the expression in a more familiar form -
def foo(f):
# ...
(lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args))) #wtf?
Is effectively the same1 as -
def foo(f):
# ...
return f(lambda *x: foo(f)(*x)) # try it and see ...
Or because bar returns a single-parameter lambda, we can simplify a bit more -
def foo(f):
# ...
return f(lambda x: foo(f)(x))
With eta reduction, that is the same as -
def foo(f):
# ...
return f(foo(f))
Which is alpha equivalent to the Y-combinator -
def Y(f):
# ...
return f(Y(f)) # a wild Y appears!
However, because the eta-reduced form causes immediate recursion of Y in an applicative-order language (like Python), a stack overflow guaranteed. Leaving the eta-expansion in place allows us to use Y safely -
def Y(f):
return f(lambda x: Y(f)(x)) # eta expanded Y(f)
def fact (recur):
def loop (n):
if n < 1:
return 1
else:
return n * recur(n - 1) # <-- uses recur to recur
return loop
def fib (recur):
def loop (n):
if n < 2:
return n
else:
return recur(n - 1) + recur(n - 2) # <-- uses recur to recur
return loop
print(Y(fact)(7)) # 5040
print(Y(fib)(10)) # 55
Notice how fact and fib never call themselves by name. Instead, the recursion mechanism is passed as an argument to the function, recur. And instead of returning a result directly, we return a function, loop, which can recur when recur is called.
Python supports recursion though, so this is all just a big lambda song and dance around this more idiomatic program -
def fact (recur):
def loop (n):
def fact (n):
if n < 1:
return 1
else:
return n * recur(n - 1)
return n * fact(n - 1) # <-- recur by name; call fact
return loop
def fib (recur):
def loop (n):
def fib (n):
if n < 2:
return n
else:
return recur(n - 1) + recur(n - 2)
return fib(n - 1) + fib(n - 2) # <-- recur by name; call fib
return loop
print(Y(fact)(7))
print(fact(7)) # 5040
print(Y(fib)(10))
print(fib(10)) # 55
more than one function argument?
Above we see fact and fib as single-parameter functions. Can this pattern work with functions that accept more arguments?
Before we see Y used in more complex scenarios, let's first look at a curried function in Python using def -
def func (x): # func accepts x and returns inner1
def inner1 (y): # inner1 accepts y and returns inner2
def inner2 (z): # inner2 accepts z and returns x + y + z
return x + y + z
return inner2
return inner1
func(3)(3)(3) # 9
Now that same function using lambda. Note \ is used for a line break in Python -
func = lambda x: lambda y: lambda z: \
x + y + z
func(3)(3)(3) # 9
Okay now that we know those two forms are identical, let's put Y to work -
Y = lambda f: \
f(lambda x: Y(f)(x))
range = lambda r: lambda start: lambda end: \
[] if start > end else [ start, *r(start + 1)(end) ]
reduce = lambda r: lambda f: lambda init: lambda xs: \
init if not xs else r(f)(f(init, xs[0]))(xs[1:])
add = lambda a, b: \
a + b
sum = \
Y(reduce)(add)(0)
nums = Y(range)(3)(9)
print(nums) # [ 3, 4, 5, 6, 7, 8, 9 ]
print(sum(nums)) # 42
but wait...
So if the Y-combinator is meant to enable recursion, why does it have a recursive definition?
Y = lambda f: \ # Y = ...
f(lambda x: Y(f)(x)) # recur with Y ??
This is a simple way to show how Y works, but offloading the actual recursion to Python kinda feels like a cheap trick. Prepare to go off the rails entirely...
U-combinator enters the scene -
U = lambda f: \
f(f) # <-- no named recursion
Y = \
U(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) # <-- no named recursion
fact = lambda r: lambda n: \
1 if n < 1 else n * r(n - 1)
print(Y(fact)(7))
# 5040
That's, U. By passing a function to itself as an argument, a function can recur using its parameter instead of its name!
Now because all our functions are pure and nameless, we can show skip intermediate assignments and show lambdas inline -
# print(Y(fact)(7))
print( \
(lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda n: \
1 if n < 1 else n * r(n - 1)) \
(7) \
)
# 5040
The same can be done in the sum(range) example -
# sum = Y(reduce)(add)(0)
sum = \
(lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda f: lambda init: lambda xs: \
init if not xs else r(f)(f(init, xs[0]))(xs[1:])) \
(lambda a, b: \
a + b) \
(0)
# nums = Y(range)(3)(9)
nums = \
(lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda start: lambda end: \
[] if start > end else [ start, *r(start + 1)(end) ]) \
(3) \
(9)
print(sum(nums))
# 42
And as a single pure expression -
# (sum)((range(3)(9)))
print( \
((lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda f: lambda init: lambda xs: \
init if not xs else r(f)(f(init, xs[0]))(xs[1:])) \
(lambda a, b: \
a + b) \
(0)) \
((lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda start: lambda end: \
[] if start > end else [ start, *r(start + 1)(end) ]) \
(3) \
(9)) \
)
# 42
I recommend you check out this Q&A for further explanation
1technically...
it's not exactly the same. In the orignial -
def foo(f):
global foo_counter
foo_counter += 1 # side effect 1
print("foo = %d" % foo_counter) # side effect 2
return (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args))) # repeats f
By directly using U-combinator (lambda x: x(x)), direct recursion of f is made possible without repeating the side effects 1 and 2.
When we rewrite foo without the U-combinator, we recur foo (instead of just f) and so side effects 1 and 2 are repeated -
def foo(f):
global foo_counter
foo_counter += 1 # side effect 1
print("foo = %d" % foo_counter) # side effect 2
return f(lambda *x: foo(f)(*x)) # repeats all of foo
This is a minor difference but worth mentioning as it shows the disruptive quality of side effects.
