Two Y Combinators for Code Mobility in JavaScript

If you’re sending some code to another machine for evaluation, you may not have the opportunity to send function definitions beforehand. While it’s handy to build up calculations from functions that you’ve defined, as in

var square = function (x) {return x * x;};
var addOne = function (x) {return x + 1;};
addOne(square(3)); ~~> 10

the server may not allow you to define square and addOne, for instance. The reason is that definitions get added to the symbol table on the destination machine, putting memory pressure on it. The server may only permit you stateless evaluations: you may be limited to applications of anonymous functions only, or, in C# lingo, lambda expressions. This is ok if you’re evaluating non-recursive functions, as in

(function (x) {return x + 1;})((function (x) {return x * x;})(3)) ~~> 10

But what if you need to evaluate a recursive function, like factorial:

var fact = function (n) {return n < 2 ? 1 : n * fact(n - 1);}
fact(13) ~~> 6227020800

How on earth are you going to compute factorial recursively without defining the symbol fact? An answer is the Y combinator, and it’s all but essential for this scenario of remoting code. Another scenario for anonymous recursive functions is LINQ for JavaScript, which is a hugely valuable “multi-master” power tool for the JavaScript programmer.

In case you’re skeptical and tired of factorial and fibonacci as examples of recursive functions, take a look at this stackoverflow answer.

From this point on, I’m taking it as given that you understand and accept that we need recursive functions, and we need them anonymously.

To give you the punchline before the joke, the following shows two implementations of the Y combinator that are completely suitable for self-contained evaluation of recursive functions on stateless evaluation machines using only anonymous functions. After you rub your eyes a bit, I promise to present a clear and memorable derivation of both of these, so clear that you can remember it and rederive the Y combinator from memory whenever you need it for real work:

(function (h) {return function(f) {return f(function(n) {return h(h)(f)(n);});};})(function (h) {return function(f) {return f(function(n) {return h(h)(f)(n);});};})(function(g) {return function (n) {return n<2 ? 1 : n*g(n-1);};})(13)

(function (f) {return (function (h) {return f(function (n) {return h(h)(n);});})(function (h) {return f(function (n) {return h(h)(n);});});})(function(g) {return function (n) {return n<2 ? 1 : n*g(n-1);};})(13)

You can check that these work by keyboarding them into the JavaScript console in Google Chrome; just press F12 on an empty browser tab, find the console, and keyboard away to your heart’s content.

I started with Matthew Might’s note on using the Y-combinator for memoizing, I noticed he presented two different versions of the Y-combinator but only derived one. One of them is explicitly a function from a function f to its fixed point, and the other is an application of a function to itself, which returns a function from f to its fixed point. Since Matthew didn’t actually explain the angle he actually took, I’ll fix (-: that here.

Start by stating our objective: we want a closure — a function — that computes some recursive function on its input, n. The typical example is factorial; we need a function that illustrates the principle without being distractingly complicated. Don’t get distracted by the function itself: focus on the general derivation of the Y-combinator.

For reasons to become clear, I’ll call this function yf. This is our fact, almost; we’re not allowed to call yf inside the body of yf — that’s the rule. We can make definitions while we’re figuring out Y, but, at the end, we must be purely anonymous. The only names allowed in the final answers will be function parameters. No free variables — no closed-over variables — no variables that refer to locations outside local function scope — no definition-injection allowed in the server.

Don’t forget that you can keyboard all the following examples into the JavaScript console in Google Chrome to check me out.

var yf = function(n) {return n < 2 ? 1 : n * g(n-1);}

Our function yf calls some other function g, which it gets from somewhere else. g is supposed to do exactly what yf does, that is, compute factorial. But, we haven’t defined g, so if we try to call yf, JavaScript should give us a “not-defined” error:

yf(13) ~~> ReferenceError: g is not defined

Great, so far we know what we’re doing, but we need to get g from somewhere, and the only thing allowed is a parameter to some other function:

var f = function(g) {return function(n) {return n < 2 ? 1 : n * g(n - 1);};}

We couldn’t say function (g) {return yf;} because yf is actually a closure, and the function g in yf is already bound to a non-existent global symbol, g, and JavaScript won’t rebind it to the parameter g of our new function f.

No problem. Just reiterate the body of yf and JavaScript binds the g in that body to the parameter g of f; again:

var f = function(g) {return function(n) {return n < 2 ? 1 : n * g(n - 1);};}

Great. Now, if we could call f on some function that does what g does then we would have that function of n that we seek. What does g do? Everything that yf does and no more. They’re both supposed to be factorial. Remember that we must paste the bodies of the functions to make sure that JavaScript binds g to the parameter, so lets try

var yf = (function(g) {return function(n) {return n < 2 ? 1 : n * g(n-1);};})/*applied to*/(function(n) {return n < 2 ? 1 : n * g(n-1);})

yf(13) ~~> ReferenceError: g not defined.

Ahh — the first g got bound, but not the second one. How can we fix (-: that?

What we really need is a way to call this function of g on the result of applying this function of g to the function of n. But that result is yf itself. We’re stuck between a chicken and an egg, or are we?

Just imagine that we had the result of applying f — this function of g — to the function of n, which is the old yf:

f(yf)

This function would be yf itself, so yf would satisfy the mathematical equation

yf = f(yf)

yf is called a fixed point of f because yf equals the result of applying f to yf. Solving for yf given f is just the same kind of activity as solving for x in the fixed-point equation x = sin(x).

Now imagine just one more thing: that we had a magical function Y that could convert the function f into its fixed point, the function yf. In other words, just imagine that we could solve the fixed-point equation yf = f(yf) for any f. The analogy in school math would be a magical function Z that could convert sin into x, where x is a fixed-point of sin, that is, a solution to x = sin(x).

var Y = function(f) {return f(Y(f));}

If we had Y, we would be home, at least mathematically. But we can’t actually use the definition of Y above because it will immediately call itself and stackoverflow (go ahead, try it).

Y(f) ~~> RangeError: Maximum call stack size exceeded.

We just need to slow it down by inserting another layer of function-ness. We know, mathematically, that Y(f), which is our function of n, is exactly equal to function(n) {return (Y(f))(n);}, just that, represented as a function of n, Y doesn’t get called immediately, only later when it’s actually applied to an argument n. Let’s try that:

var Y = function(f) {return f(function(n) {return (Y(f))(n);});}
Y(f) ~~> function(n) {return n < 2 ? 1 : n * g(n - 1);}
Y(f)(13) ~~> 6227020800

Good God, that works!  But of course it does, because we thought out every step.

Go over it again, make sure you can do it right out of your head without referring to notes. It’s already a power tool. We just have one problem: Y calls itself, and, unless Y is installed as a primitive on our stateless server, we can’t have that. We must remove the recursive call of Y in the body of Y itself.

Suppose we could write Y as the application of some other function to itself (this is genius — all the above is merely hard work and inspiration!). Then we’d write, mathematically

Y = (function (h) {...})(function(h) {...})

The dots must return a function of f, because we want Y(f) to be yf, a function of n.

Y = (function (h) {return function (f) {...};})(function (h) {return function (f) {...};})

What’s the function of f we need? We already derived that above; just copy-paste

Y = (function (h) {return function(f) {return f(function(n) {return (Y(f))(n);});};})(function (h) {return function(f) {return f(function(n) {return (Y(f))(n);});};})

This is getting ugly, but it’s conceptually simple and if we strip away the noise just to look at it, maybe using C#’s notation for lambda expressions, we see

Y = (h => (f => f(n => (Y(f))(n))))(h => (f => f(n => (Y(f))(n))))

Still painful, but not so bad if we just elide the fact that this is a function applied to itself, and look at it like this

Y = (h => (f => f(n => (Y(f))(n))))(...)

Now we clearly see that everything is made up from bits and pieces we already made up. We’ve composed this solution from building blocks created along the way. We just need to get rid of the recursive call to Y on the inside, so that we can use Y, inline, just the way we use f, inline, without defining it.

We’ve said that “Y is some function applied to itself”. This function is (h => …). Since it’s applied to itself, in its own body, it is, itself, h. So “some function” is equal to h, and “some function applied to itself” is h(h), so Y MUST BE h(h). We can write this all out, in pseudo-C#, by pasting h(h) over the top of every occurrence of Y, as

Y = (h => (f => f(n => (h(h)(f)(n))))(...)

or, in JavaScript, as

(function (h) {return function(f) {return f(function(n) {return h(h)(f)(n);});};})(function (h) {return function(f) {return f(function(n) {return h(h)(f)(n);});};})

Now, for the money shot, just apply this to our original function f, written out inline, and applied to our argument 13, and go ahead and do this in the Google Chrome JavaScript console window

(function (h) {return function(f) {return f(function(n) {return h(h)(f)(n);});};})(function (h) {return function(f) {return f(function(n) {return h(h)(f)(n);});};})(function(g) {return function (n) {return n<2 ? 1 : n*g(n-1);};})(13)

and really believe your eyes, this works, producing 6227020800.

Suppose we said “Y is a function of f that returns some function applied to itself?” This reverses the roles of h and f. Instead of

Y = (h => (f = > ...))(h => (f = > ...))

could we say

Y = f => (h => ...)(h => ...) ?

Well sure we could. But since our definition of Y has changed, we must be careful on the insides. Before, we said that Y was h(h), some function h applied to itself that returned a function of f. To use f on the insides, we apply Y to f, that is, we write h(h)(f), and then we apply that to the slowed-down argument n. In other words, we write h(h)(f)(n)

Here, we say that Y is a function of f that returns h(h), some function h applied to itself. So here, h(h) means Y(f), not Y. Thus, on the insides, we must write h(h)(n) and not h(h)(f)(n).

Grit your teeth and do it in JavaScript:

(function (f) {return (function (h) {return f(function (n) {return h(h)(n);});})(function (h) {return f(function (n) {return h(h)(n);});});})

and, applying it,

(function (f) {return (function (h) {return f(function (n) {return h(h)(n);});})(function (h) {return f(function (n) {return h(h)(n);});});})(function(g) {return function (n) {return n<2 ? 1 : n*g(n-1);};})(13)

Oh, yes, the magic is still there.

Recapping, then, we first imagined that we had a function, yf, that had a closed-over reference, g, to itself

var yf = function(n) {return n < 2 ? 1 : n * g(n-1);}

Then we promoted the closed-over free variable g to a parameter

var f = function(g) {return function(n) {return n < 2 ? 1 : n * g(n - 1);};}

We want g to be yf (and it would be if we were letting ourselves use recursion-by-name), but we can’t call f on yf directly because the g in yf is already bound too early to an undefined global.

But we really want yf to actually, mathematically, be the result of calling f on yf. We really need yf to be a solution to an auxiliary mathematical problem, namely

yf = f(yf)

Then we supposed yf were the result of an imaginary function, Y, applied to f, which then satisfies the mathematical equation

Y(f) = f(Y(f))

But, we can’t write that in JavaScript, because Y(f) gets evaluated too early. We slow it down with a lambda (now, in pseudo-C#)

Y(f) = f(n => (Y(f))(n))

and, by gum, it works.

Then, we must remove the internal reference to Y, and we clairevoyantly imagined that if Y were a function applied to itself, we could win

Y = (h => f => f(n => h(h)(f)(n))(h => ...)

and also that we could twist this around and write Y as a function of n that returns h(h), a function h applied to itself, that encapsulates Y(f)

Y = (f => (h => f(n => h(h)(n)))(h => ...))

Unbelievably, these guys work and produce the same results when just keyboarded in to the JavaScript console, with no names used at all, only anonymous functions everywhere. In other words, if you translate the pseudo-C# to JavaScript, you will get the expected answer 6227020800

(h => (f => f(n => h(h)(f)(n))))(h => ...)(g => (n => n<2 ? 1 : n*g(n-1)))(13)

(f => (h => f(n => h(h)(n)))(h => ...))(g => (n => n<2 ? 1 : n*g(n-1)))(13)

The bigger point is that these formulae are ACTUALLY WORTH MEMORIZING. These are NOT merely academic curiosities; there are many real-world-programming scenarios in which we need anonymous recursive functions, and this is a real shortcut to getting there.

Advertisements

~ by rebcabin on July 27, 2012.

6 Responses to “Two Y Combinators for Code Mobility in JavaScript”

  1. really impressed! everything is very open and very clear explanation of issues. it contains truly information. your website is very useful. thanks for sharing. looking forward to more!http://www.boliche.com.br/email.htm

  2. […] apply the Y combinator (which we can keyboard in from memory because we remember this prior blog post, this time with the internal arguments of h(h) promoted to a pair of arguments, namely the visitor […]

  3. Reblogged this on The Code Decanter.

  4. This also works in Internet Explorer Version 9’s console (F12 to access it)

  5. […] an earlier post, we derived the Y combinator for converting self-parameterized functions into anonymous recursive functions. We suggested […]

  6. […] had one example of applying the Y combinator to generate a recursive function of one argument: the factorial function. Then, we had another example of applying the Y combinator to generate a […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: