Created
May 3, 2010 17:38
-
-
Save igstan/388351 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* DERIVING THE Y COMBINATOR IN 7 EASY STEPS | |
* | |
* Ionut G. Stan | ionut.g.stan@gmail.com | http://igstan.ro | http://twitter.com/igstan | |
* | |
* | |
* The Y combinator is a method of implementing recursion in a programming | |
* language that does not support it natively (actually, it's used more for | |
* exercising programming brains). The requirement is the language to support | |
* anonymous functions. | |
* | |
* I chose JavaScript for deriving the Y combinator, starting from the definition | |
* of a recursive factorial function, using a step-by-step transformation over | |
* the initial function. | |
*/ | |
/* STEP 1 | |
* | |
* The initial implementation, using JavaScript's built-in recursion mechanism. | |
*/ | |
var fact = function (n) { | |
if (n < 2) return 1; | |
return n * fact(n - 1); | |
}; | |
/* STEP 2 | |
* | |
* What would be the simplest thing to do to obtain basic recursivity? We could | |
* just define a function which receives itself as an argument and calls that | |
* argument with the same argument. That's an infinite loop of course: | |
* | |
* (function (f) { | |
* f(f); | |
* })(function (f) { | |
* f(f); | |
* }); | |
* | |
* Let's use the above pattern for our factorial function. There is however a | |
* small difference. The factorial function receives an argument which we don't | |
* know yet, so what we want is to return a function which takes that argument. | |
* That function can then be used to compute factorial numbers. Also, this is | |
* what makes our implementation to not result into an infinite loop. | |
*/ | |
var fact = (function (f) { | |
return function (n) { | |
if (n < 2) return 1; | |
// because f returns a function, we have a double function call. | |
return n * f(f)(n - 1); | |
}; | |
})(function (f) { | |
return function (n) { | |
if (n < 2) return 1; | |
// because f returns a function, we have a double function call. | |
return n * f(f)(n - 1); | |
}; | |
}); | |
/* STEP 3 | |
* | |
* At this point we have some ugly duplication in there. Let's hide it away into | |
* a helper function called "dupe" | |
*/ | |
var dupe = function (f) { | |
return f(f); | |
}; | |
var fact = dupe(function (f) { | |
return function (n) { | |
if (n < 2) return 1; | |
// because f returns a function, we have a double function call. | |
return n * f(f)(n - 1); | |
}; | |
}); | |
/* STEP 4 | |
* | |
* The problem with the above version is that double function call. We want to | |
* eliminate it so that the implementation of this factorial is similar with | |
* the recursive version. How can we do that? | |
* | |
* We can use a helper function that takes a numeric argument and performs the | |
* double call. The trick is though to keep this helper function in the same | |
* environment where "f" is visible, so that "g" can actually call "f". | |
*/ | |
var dupe = function (f) { | |
return f(f); | |
}; | |
var fact = dupe(function (f) { | |
var g = function (n) { | |
return f(f)(n); | |
}; | |
return function (n) { | |
if (n < 2) return 1; | |
// no more double call, g is a function which takes a numeric arg | |
return n * g(n - 1); | |
}; | |
}); | |
/* STEP 5 | |
* | |
* The above works nice, but the definition contains so much clutter code. We | |
* could hide it away in yet another helper function, keeping almost just the | |
* definition of factorial. | |
*/ | |
var dupe = function (f) { | |
return f(f); | |
}; | |
var ext = function (h) { | |
return dupe(function (f) { | |
var g = function (n) { | |
return f(f)(n); | |
}; | |
return h(g); | |
}); | |
}; | |
var fact = ext(function (g) { | |
return function (n) { | |
if (n < 2) return 1; | |
return n * g(n - 1); | |
}; | |
}); | |
/* STEP 6 | |
* | |
* Let's inline the definition of "g" inside "ext" because we only call it once | |
*/ | |
var dupe = function (f) { | |
return f(f); | |
}; | |
var ext = function (h) { | |
return dupe(function (f) { | |
return h(function (n) { | |
return f(f)(n); | |
}); | |
}); | |
}; | |
var fact = ext(function (g) { | |
return function (n) { | |
if (n < 2) return 1; | |
return n * g(n - 1); | |
}; | |
}); | |
/* STEP 7 | |
* | |
* Now, if we also inline the definition of the "dupe" function inside "ext" we | |
* end up with the famous Y combinator. | |
*/ | |
var Y = function (h) { | |
return (function (f) { | |
return f(f); | |
})(function (f) { | |
return h(function (n) { | |
return f(f)(n); | |
}); | |
}); | |
}; | |
var fact = Y(function (g) { | |
return function (n) { | |
if (n < 2) return 1; | |
return n * g(n - 1); | |
}; | |
}); | |
/* THE END | |
* | |
* I hope you enjoyed it! | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment