# Y combinator in small steps

Representation recursion without a named function, in JavaScript.

The Y combinator is an interesting construct, allowing recursion without referring the function being recursed. In other words, call a function recursively, without naming it. We will go through one approach of deriving it.

This approach mostly follows WhyOfY by Richard P Gabriel^{} . We will derive it in JavaScript, in steps. Each step is complete. Click on the 'Edit in JSFiddle' to explore the steps.

## Premise & setup

Lets pick a simple example, so we can concentrate on exploring recursion. Given a number, `n`

, return the sum of numbers from `1`

to `n`

. To start with, below is a recursive solution for the problem. Individual steps are hosted in JSFiddle, for you to play around.

var sum = function (n) {return n === 1 ? 1 : n + sum(n - 1);};console.assert(sum(5) === 15, sum(5));

## The process

We have to remove the reference to `sum`

, inside the function, which
fortunately leads to the Y combinator. One approach to calling a
function, without using its name, is to pass the function as
parameter.

var s1 = function (f, n) {return n === 1 ? 1 : n + f(f, n - 1);}console.assert(s1(s1, 5) === 15);

We have just moved the function name (reference) from inside the function, to the function call. As a next step, we could pass the function as a curried param.

This helps later, in abstracting the passing of function as parameter, out of the logic for the problem.

var s2 = function (h) {return function (n) { // inner functionreturn n === 1 ? 1 : n + h(h)(n - 1);};};console.assert(s2(s2)(5) === 15);

The double call inside the inner function, is quite irrelevant to the
problem of calculating sum. The logic of `sum`

shouldn't know that
`h(h)`

gives the next function call. The recursive function should
just receive a function, to continue the recursion with. We could
abstract that in another function. Ex:

// replacereturn function (n) {return n === 1 ? 1 : n + h(h)(n-1);};// withreturn (function(f) {return function (n) {return n === 1 ? 1 : n + f(n-1);};})(function (n) {return h(h)(n);});

Why not pass `h(h)`

as parameter? Why do we have to wrap it in a
function?

Here is the complete version.

var s3 = function (h) {return (function (f) { // sum functionreturn function (n) {return n === 1 ? 1 : n + f(n - 1);};})(function (n) {return h(h)(n);});}console.assert(s3(s3)(5) === 15, s3(s3)(5));

In the current version, the function dealing with the sum logic,
doesn't have any dependency on context, or specific knowledge about
how to get the next function. Lets name it as `sum`

(for the time
being). Ex.

var sum = function(f) {return function (n) {return n === 1 ? 1 : n + f(n-1);};};

This is just so we can see the real changes in code. Here is the
recursion with `sum`

.

var sum = function (f) {return function (n) {return n === 1 ? 1 : n + f(n - 1);};};var s4 = function (h) {return sum(function (n) {return h(h)(n);});};console.assert(s4(s4)(5) === 15);

To evaluate the recursion, we had to call `s4`

with itself, ex
`s4(s4)`

. To not use a name, we would have to abstract it in a
function. We can define a function which `s4`

as parameter, and call
it with itself as parameter.

var s5 = (function (f) {return f(f);})(s4);console.assert(s5(5) === 15);

Expanding the definition of `s4`

gives.

var sum = function (f) {return function (n) {return n === 1 ? 1 : n + f(n - 1);};};var s5 = (function (g) {return g(g);})(function (h) {return sum(function (n) {return h(h)(n);});});console.assert(s5(5) === 15);

We are almost done. Now, we just need to pass the actual function (ex
`sum`

in our case) as a parameter. Here is the `Y`

combinator.

var Y = function (fn) {return (function (g) {return g(g);})(function (h) {return fn(function (n) {return h(h)(n);});});};var sum = function (f) {return function (n) {return n === 1 ? 1 : n + f(n - 1);};};console.assert(Y(sum)(5) === 15);

Or in its inlined form:

((function (fn) {return (function (g) {return g(g);})(function (h) {return fn(function (n) {return h(h)(n);});});})(function (f) {return function (n) {return n === 1 ? 1 : n + f(n - 1);};}))(5); // => 15

## Explorations

If you would like to think more about this, here are a few thoughts to explore.

We have only explored function with single argument. How could we make this work with multiple arguments.

Could we come up with a combinator, which doesn't take curried version of sum. Ex a combinator which takes

`sum`

defined as`function sum(f, n) { return n + f(n-1); }`

as argument.