The What, How, and Why of Y
The What of Y
The following JavaScript expression is called the applicative-order Y combinator
f => (g => g(g))(g => f(y => g(g)(y)))
What is interesting about this incomprehensible mess of lambda expressions, which
includes something as strange as g(g) not once but twice?
The first Y combinators were conceived by Haskell Curry
to show that a minimal language (called the lambda calculus) consisting just of expressions E
of the forms x => E (that we call here lambda abstraction) and E1(E2) (function application)
in principle suffices to express every algorithm. More specifically, the applicative-order
Y combinator allows
us to express recursive algorithms in a sublanguage of JavaScript that does not include
declarations.
Take for example the factorial function, and recall
factorial(5) = 5 * 4 * 3 * 2 * 1 = 120. Using the applicative-order Y combinator as Y, we can compute factorial(5)
as follows (click on the link to run the program, also in rest of this post):
Y(given_fact => n => n <= 1 ? 1 : n * given_fact(n - 1))(5);
// returns 5! = 120
The How of Y
But how does this Y applicative-order combinator achieve this? The property needed in a language that
uses applicative-order reduction, such as JavaScript and most other popular programming languages,
is as follows:
An application Y(f) where f is a lambda abstraction should lead after some function applications
to a lambda abstraction E such that E(x) leads to f(E)(x).
If Y has this property, we can compute 5! by applying Y to the following function as f:
given_fact => n => n <= 1 ? 1 : n * given_fact(n - 1)
Now Y(f)(5) leads to f(E)(5), and the recursive call given_fact(5 - 1) in f
will become E(5 - 1), which will become f(E)(4), and so on, until we reach
the base case n <= 1, which leads to 1 and E is no more needed. Then we only need
to carry out the accumulated multiplications 5 * (4 * (3 * (2 * 1))) to obtain the correct
result 120.
The Why of Y
The following explanation is adapted from a blog post by Kestas Kuliukas, who in turn was inspired by Douglas Crockford on JavaScript - Act III: Function the Ultimate. I took the liberty to modernize the JavaScript, and revise the presentation.
It is hard to figure out how the Y combinator achieves recursion because of its lack of declarations; declarations are what make computer programs understandable, and the Y combinator is specifically designed to work without them, to prove the point Curry was making.
Consider a conventional implementation of the factorial function in JavaScript, using a constant declaration:
const recursive_fact = n => n <= 1 ? 1 : n * recursive_fact(n - 1);
If n is less than or equal to 1 return 1, otherwise multiply n by
recursive_fact(n - 1).
However, we would like to achieve this without declarations.
The recursive_fact function refers to recursive_fact within its own body.
How can we
recursively call the factorial function without creating a reference to
the factorial function? The first idea is to pass the factorial function as
a parameter, and have a function which returns the factorial function
rather than declare it.
const make_fact =
given_fact => {
const fact = n => n <= 1 ? 1 : n * given_fact(n - 1);
return fact;
};
The problem is that without a “given_fact” function (such as recursive_fact above)
we can’t call make_fact.
It seems like we can’t use this approach because we can’t use make_fact to
make a factorial function without already having a factorial function to begin with!
It turns out that it is possible though, because the fact function which
make_fact makes doesn’t always call given_fact. Instead of passing in a
pre-made given_fact we can make given_fact itself use make_fact, until
make_fact makes a fact call which doesn’t need to call given_fact.
const make_real_fact =
make_fact => {
const try_fact = n => {
const next_try_fact = make_fact(try_fact);
return next_try_fact(n);
};
return make_fact(try_fact);
};
The function make_real_fact (the first version of our Y combinator)
uses a given make_fact function to make the actual factorial function.
The try_fact function is passed to make_fact to be used as its given_fact function.
If make_fact needs to use given_fact it will call try_fact,
which will make another try_fact using make_fact and try again.
Eventually make_fact will be able to return a factorial function which doesn’t
use given_fact, which can then be used to find a given_fact, and that used to
find another given_fact, and so on. Using make_real_fact we can compute
the factorial function as follows.
make_real_fact(given_fact => n => n <= 1 ? 1 : n * given_fact(n - 1))(5);
This approach is like using make_fact to keep working on the try_fact function,
assuming make_fact will always need a simpler try_fact function until it finds
a way to make_fact without needing try_fact. Note the recursion in action,
without having to declare a recursive factorial function.
The application next_try_fact(n) will lead to recursive calls
try_fact(n)-next_try_fact(n)-try_fact(n - 1)-next_try_fact(n - 1)-etc until
next_try_fact(1) is reached, returning a value without needing to use given_fact.
There is still a problem though; try_fact references itself in
const next_try_fact = make_fact(try_fact);, so it doesn’t solve the problem of getting
rid of all declarations.
Another function needs to be created to keep on cycling through try_fact-next_try_fact,
without try_fact having to reference itself.
The get_next_try_fact function will return the next try_fact function to try_fact,
so it doesn’t have to refer to itself, as shown here:
const make_real_fact =
make_fact => {
const get_next_try_fact =
() => {
const try_fact = n => {
const next_try_fact = get_next_try_fact();
const result = next_try_fact(n);
return result;
};
const next_try_fact = make_fact(try_fact);
return next_try_fact;
};
return get_next_try_fact();
};
Instead of try_fact passing itself to make_fact until it isn’t needed it calls
get_next_try_fact, which passes try_fact to make_fact for it.
But now get_next_try_fact needs to refer to itself, so we need a way to refer to
get_next_try_fact without declaring it.
This is done by passing get_next_try_fact to itself as a parameter, and is
the final adjustment needed to remove all self-referencing functions.
const make_real_fact =
make_fact => {
const get_next_try_fact =
get_next_try_fact_ref => {
const try_fact =
n => {
const next_try_fact =
get_next_try_fact_ref(get_next_try_fact_ref);
const result = next_try_fact(n);
return result;
};
const next_try_fact = make_fact(try_fact);
return next_try_fact;
};
return get_next_try_fact(get_next_try_fact);
};
Now we have a function which can make a factorial function using the make_fact
function recursively, without ever needing to refer to its own variables/functions
via labels; everything can be accessed via parameters. (get_next_try_fact_ref is a
reference to the get_next_try_fact function, maintained using parameters rather
than a declaration.)
Obviously declarations are still used though, so now we need to eliminate them. From here on the function gets much less readable, but we show that it truly doesn’t need declarations, and thus show how it is equivalent to the Y function above.
First the try_fact function is passed directly to make_fact, without being declared.
const make_real_fact =
make_fact => {
const get_next_try_fact =
get_next_try_fact_ref => {
const next_try_fact =
make_fact(n => {
const next_try_fact =
get_next_try_fact_ref(get_next_try_fact_ref);
const result = next_try_fact(n);
return result;
});
return next_try_fact;
};
return get_next_try_fact(get_next_try_fact);
};
Next the inner-most next_try_fact function is used to generate a result without being declared.
const make_real_fact =
make_fact => {
const get_next_try_fact =
get_next_try_fact_ref => {
const next_try_fact =
make_fact(n => {
// Already it's becoming cryptic
const result = get_next_try_fact_ref(
get_next_try_fact_ref)(n);
return result;
});
return next_try_fact;
};
return get_next_try_fact(get_next_try_fact);
};
Next the result is returned without being declared.
const make_real_fact =
make_fact => {
const get_next_try_fact =
get_next_try_fact_ref => {
const next_try_fact =
make_fact(n => get_next_try_fact_ref(
get_next_try_fact_ref)(n));
return next_try_fact;
};
return get_next_try_fact(get_next_try_fact);
};
Next the outer next_try_fact function is returned directly without being declared.
const make_real_fact =
make_fact => {
const get_next_try_fact =
get_next_try_fact_ref =>
make_fact(n => get_next_try_fact_ref(
get_next_try_fact_ref)(n));
return get_next_try_fact(get_next_try_fact);
};
Because get_next_try_fact is used twice on the same line a label is needed to refer to
the same thing twice. This has to be done by passing it to a function as a parameter,
so the parameter can be used as a label to refer to the same thing twice.
const make_real_fact =
make_fact => {
const get_next_try_fact =
get_next_try_fact_ref =>
make_fact(n => get_next_try_fact_ref(
get_next_try_fact_ref)(n));
return (get_next_try_fact_ref =>
get_next_try_fact_ref(get_next_try_fact_ref))
(get_next_try_fact);
};
Finally the get_next_try_fact function is passed directly to the nameless function
which calls get_next_try_fact on itself to start the recursion going.
const make_real_fact =
make_fact => (get_next_try_fact_ref =>
get_next_try_fact_ref(get_next_try_fact_ref))
(get_next_try_fact_ref =>
make_fact(n => get_next_try_fact_ref(
get_next_try_fact_ref)(n)));
We’ve gotten rid of the declarations of try_fact, next_try_fact, result, and
get_next_try_fact, leaving a function which has no declarations, only parameters.
All that is needed now is to rename
make_fact to f,
get_next_try_fact_ref to g,
n to y, and
make_real_fact to Y,
get rid of some white-space,
and we have the Y combinator function as it was given above.
const Y = f => (g => g(g))(g => f(y => g(g)(y)));
Although we made it for the factorial function the Y combinator can be used for any recursive function, showing that recursion can be done without declarations, just with lambda abstractions and function application. The same Y combinator can be used to make a factorial function…
const make_fact = given_fact =>
n => n <= 1 ? 1 : n * given_fact(n - 1);
const fact = Y(make_fact);
display(fact(5)); // Outputs 120
…and a fibonacci function:
const make_fib = given_fib =>
n => n <= 2 ? 1 : given_fib(n - 1) + given_fib(n - 2);
const fibonacci = Y(make_fib);
display(fibonacci(5)); // Outputs 5
Or, if you want to get rid of all declarations completely:
(Y => {
display(Y(given_fact =>
n => n <= 1 ? 1 : n * given_fact(n - 1))(5));
display(Y(given_fib =>
n => n <= 2 ? 1 : given_fib(n - 1) + given_fib(n - 2))(5));
})(f => (g => g(g))(g => f(y => g(g)(y))));
Not a declaration in sight!
In our examples, we used numbers, +, -, and *, which are not part of the lambda calculus.
The inventor of the lambda calculus, Alonzo Church,
showed how these can be expressed also
using just lambda abstraction and function application.