No Let, No Rec, No Problem · Irfan Ali

No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z combinators

Let’s try to solve a simple enough puzzle in JavaScript: You have to write a function fact(n) which calculates the<br>factorial of a number n, but you can not use loops (for, while, etc), recursion, or even declarations (let,<br>const, etc)

We start with a canonical recursive non-solution to know what we're aiming for, in terms of behaviour:

function fact(n) {<br>if (n === 0) {<br>return 1<br>else {<br>return n * fact(n - 1)

This is a non-solution because we can not use recursion, which means we can not call the function fact from inside the<br>definition of the function fact.

So, running for loops or calling fact from itself is not allowed. Then, what should we do? Can we call fact from<br>some other function and try to arrive at the same behaviour?

After some thinking, we can write a function factf which calculates factorial but doesn't call itself:

function factf(n) {<br>if (n === 0) {<br>return 1<br>else {<br>return n * factg(n - 1)

function factg(n) {<br>if (n === 0) {<br>return 1<br>else {<br>return n * factf(n - 1)

This works. factf(n) does calculate the factorial. So, are we done? Well, we did avoid explicit call for factf but<br>it'd be a lie to say that this doesn't use recursion.

This solution calls for a new rule: mutual recursion is also NOT allowed.

But, can we still learn something from the previous attempt? We know that if we decide to avoid loops, we definitely<br>need to emulate a call to something like fact inside fact. What if we don't call fact inside fact directly but<br>define a generator function factgen and pass a function which gets called instead:

function factgen(self, n) {<br>if (n === 0) {<br>return 1<br>else {<br>return n * self(self, n - 1)

let fact = n => factgen(factgen, n)

To see how it works, take fact(4). It is just factgen(factgen, 4) which evaluates to 4 * self(self, 3) which is<br>just 4 * factgen(factgen, 3), which just reduces to 4 * 3 * factgen(factgen, 2) and so on. Every factgen(factgen, n) call essentially becomes n * factgen(factgen, n - 1) until n becomes 0.

It seems like we've solved our puzzle:

fact did not call itself in its own definition (explicit recursion)

fact also did not call any other function which called fact indirectly (mutual recursion).

But alas, even though fact did NOT call itself directly or indirectly, factgen did receive a reference to itself and<br>used the reference in the definition of fact. And if we look closely at our challenge, we should NOT use a<br>declaration.

If we really vowed to let go of declarations, we should avoid using function too. This calls for another rule: all<br>declarations (including function) are not allowed.

We'd use only anonymous functions like (x, y) => { .. } in our solution.

But like before, let's see if we can get some intuition from the definition above. If we zoom in on the recursive part,<br>we see that self(self, n) has a curious property. Evaluating it does not eliminate the self-reference. Instead, it<br>eventually produces another call involving the same pattern, namely self(self, n - 1) embedded inside a larger<br>expression. The argument changes, but the self-application survives. This is not even specific to the definition of<br>fact given here. If, say, there was a function f defined like this:

function f(g, n, s) {<br>console.log(s)<br>if (n<br>and then called like this: f(f, 0, "hello, world"). We'd get "hello, world" printed repeatedly until n reaches<br>10 (if stack size allows). That's basically a while loop

So, our venture teaches us that the pattern g(g, ...) captures the core mechanism needed to create recursion. It<br>results in itself when it executes, which allows it to use the same behaviour but with different inputs to emulate<br>iteration.

Let's see if we can extract this pattern into a function to gain more insight:

let rep = x => x(x)

(Don't worry about the let, this is NOT an attempt at solving the challenge and we'd remove it later.)

Clearly, rep doesn't do anything in particular. It just takes a higher-order function x and calls x with argument<br>x. But something interesting happens when we call rep with itself as an argument. If we reason purely in terms of<br>expressions and forget evaluation for a moment, then rep(rep) rewrites to rep(rep) again.

(Operationally, however, a JavaScript engine attempting to evaluate this expression would recurse forever and eventually<br>overflow the stack. We'd handle this problem later. For now, we are interested only in the equational behaviour of the<br>expression.)

In other words, if written without rep, the code (x => x(x))(x => x(x)) evaluates to itself. Please note that we<br>just obtained self-application without loops, recursion, or declarations. We just used an anonymous function and<br>literally wrote the function twice by hand.

But what good is a self-replicating code like rep if we can't use this machinery to do some real task, like<br>calculating the factorial. To get something useful with rep, we'd need to...