Symmetry is a complexity-reducing concept (co-routines include subroutines); seek it everywhere.
--Alan Perlis
Prelude
In the previous post where we discovered the Y-Combinator from scratch, we set out to solve the following odd challenge.
Write a function in Python (or any language for that matter) that calculates the factorial of a given number n. You may only use function calls, but you may not call a function from inside its body i.e. no explicit recursion! In other words, your solution should be rewritable as a lambda expression which returns the factorial of n. Also, assume that you language doesn’t support looping mechanisms.
And we concluded that we can re-write the following definition of calculating factorial of a given number n:
def factorial(n):
return 1 if n == 0 else n*factorial(n-1)
factorial(11) #39916800
as a lambda expression,
(lambda copy0: lambda n: 1 if n==0 else n*copy0(copy0)(n-1))(
lambda copy0: lambda n: 1 if n==0 else n*copy0(copy0)(n-1))(11) # 39916800
To summarize the previous post, we wanted to solve the problem of calculating the factorial of a number recursively, only this time, without calling named functions in their own bodies i.e. without explicit recursion.
So, where is the Y-Combinator?
The lambda expression given above allows for the recursive computation of factorial, and yet, it doesn’t use explicit any recursion i.e. it doesn’t refer to a function by name in its own body. The lambda expression solution guarantees that as long as our programming language environment of choice provides us with a mechanism to write and evaluate lambda expressions, we can achieve recursion, even if explicit recursion is not provided by the language by default!
A combinator, in lambda calculus lingo, is a lambda expression that contains no free-variables. And a Y-Combinator is fixed-point combinator that returns a fixed point of its argument function such that the returned value (i.e. the argument function passed to the Y-combinator) can be called again and again.
In other words, the Y-combinator modifies a function such that the return value of the function can be a copy of the original function itself (which can then be applied again and again)! It shouldn’t come as a surprise then that the Y-Combinator is a mechanism which can achieve recursion by applying the same function again and again, and yet it can be written as a lambda expression i.e. without calling a function in its own body (since the Y-combinator ia combinator).
In the previous post, I claimed that the Y-Combinator is hidden somewhere in the mechanisms of the code above. Now, in the above lambda expression, we notice the following boilerplate code:
lambda x: lambda y: ... x(x)(y)(
lambda x: lambda y: ... x(x)(y))
And most of the actual application specific (in our case, factorial calculation) logic is in the ... part. Let’s try to separate the boilerplate of the recursion mechanism (i.e. the Y-combinator) and the recursive logic.
In this part we will try to decouple our above lambda expression into two parts, 1. a general purpose Y-Combinator (hopefully), and 2. the actual logic for calculating the factorial or whatever you might need recursion for.
Let’s use assignment to make avoid having to use the large lambda expressions.
partial_factorial = lambda copy0: lambda n: 1 if n==0 else n*copy0(copy0)(n-1)
Then, the original lambda expression equivalent would be,
partial_factorial(partial_factorial)(11) #39916800
The partial_factorial(partial_factorial) part can be generalized by
recursive = lambda f: f(f) #recursive(partial_factorial)(11) gives 39916800
Now, we would be able to solve the factorial problem as follows:
recursive(lambda recurse: lambda n: 1 if n==0 else n*recurse(recurse)(n-1))(11) #39916800
Nothing cool here, but can get rid of the ugly bit recurse(recurse) in the above style inside the inner lambda. We can write another lambda expression to avoid having to write recurse(recurse). Let’s call it double_apply_inside to stand for applying the function passed to it applied to itself but in an inner lambda expression.
double_apply_inside = lambda f: lambda g: f(lambda y: g(g)(y))
double_apply_inside needs some explanation since it’s too far from usual style of Python programming. Basically, the outer lambda argument f will point to the definition of the function we pass to it, for example, partial_factorial. Think of it as currying of some flavor. When f is partial_factorial, then lambda f: lambda g: f(lambda y: g(g)(y))(foo) would result in an expression of type lambda g: lambda n: 1 if n==0 else n*foo(foo)(n-1), exactly what we needed.
NOTE Do not ever confuse yourself by thinking that g(g)(y) in lambda y: g(g)(y) would get evaluated right away. g(g)(y) would be evaluated only when the lambda expression is applied to the argument y, otherwise the lambda expression in itself serves as a value.
Equipped with all that we have, we can simplify the definition of partial_factorial as follows:
partial_factorial = lambda recurse: lambda n: 1 if n==0 else n*recurse(n-1)
# Here's how you'd call it
recursive(double_apply_inside(partial_factorial))(11) #39916800
Now we have recursive and double_apply_inside doing our general purpose recursion job, and the factorial job is handled by partial_factorial. Decoupling complete! And what is worth celebrating here is that each decoupled part is a combinator itself- i.e. no free variables. A combinator, since it contains no free-variables, can be used to substitute its name with its lambda expression, or vice-versa, anywhere in the program.
One last time, let’s combine recursive and double_apply_inside into one and, lo and behold, we have something really beautiful:
# expects function 'f' as argument
recursion_combinator = lambda f: recursive(double_apply_inside(f))
# since `recursive` and `double_apply_inside` are both combinators,
# we can substitute their names accordingly.
recursion_combinator = lambda f: \
double_apply_inside(f)(double_apply_inside(f))
# NOTE: Substitute function calls with the result of evaluations!
recursion_combinator = lambda f: \
(lambda g: f(lambda y: g(g)(y)))\
(lambda g: f(lambda y: g(g)(y)))
recursion_combinator(partial_factorial)(11) #39916800
recursion_combinator is the combinator that allows for achieving recursion!
You could use it for any general purpose recursion (without having to use explicit recursion!). For instance, you can reverse a string as follows:
reverse_string = lambda recurse: \
lambda n: '' if len(n)==0 else n[-1]+recurse(n[:-1])
recursion_combinator(reverse_string)('abcde') #edcba
You might be asking yourself- isn’t recursion_combinator exactly the Y-combinator we have been looking for?
Y-Combinator and the Z-Combinator?
Python is a strict programming language and only allows functions whose parameters must be evaluated completely before they may be called. It turns out to be the case that in such a language, the Y-combinator will never halt since it will run into an infinite recursion in an attempt to evaluate the recursive function argument(s).
Therefore, strictly speaking, recursion_combinator is not the ‘common’ Y-combinator, but it is also the closest you will get to in Python. What we have is more precisely what is called the Z-combinator- it prevents the infinite recursive by using a lambda expression as a value.
Practically, the Z-combinator is the ad hoc Y-Combinator for a strict programming language. For the sake of completeness, if Python were not a strict language (Haskell, for example, uses lazy evaluation), the ideal Y-combinator in python would look like this.
# recursive, but would cause stack overflow!
Y_combinator = lambda f: \
(lambda g: f(g(g)))\
(lambda g: f(g(g)))
But this would then run into an infinite recursion, and hence not suitable for a strict language like Python. For practical purposes, you would have to use the Z-combinator instead.
You could, however, refactor recursion_combinator into a beast that resembles a bit of the Y-combinator and a bit of the Z-combinator. You name it yourself, please. Here’s how it looks:
recursion_combinator = lambda f: \
(lambda g: f(g(g)))\
(lambda g: f(lambda *y: g(g)(*y)))
As a bonus, using *y would now also allow for handling multiple arguments in recursive problems. Interestingly enough, RosettaCode entry for the Y-combinator in Python features a ‘Y-combinator’ entry that resembles the above refactored version of recursion_combinator.