Created
April 1, 2013 01:27
-
-
Save pboyer/5282757 to your computer and use it in GitHub Desktop.
This Gist demonstrates how to derive the applicative order y-combinator in JavaScript. It closely follows John Franco's derivation found here: http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
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
// Our initial conception of the factorial function | |
// Uses straightforward recursion to acheive its purpose | |
fact = | |
function(n){ | |
return (n === 1) ? 1 : n * fact(n-1); | |
}; | |
console.log( fact(5) ); // returns 120 | |
// In order to remove the reference to the function | |
// in the function body, we parameterize it by the f | |
// function. We need to call the function internally | |
// (i.e. f(f)(n-1) ) to get the function we need. | |
fact0 = | |
function(f) { | |
return (function(n){ | |
return (n === 1) ? 1 : n * f(f)(n-1); | |
}); | |
}; | |
console.log( fact0(fact0)(5) ); // returns 120 | |
// We want to get rid of the need to directly parameterize | |
// the function fact0 with itself. We'd rather call the | |
// function with a numeric parameter directly. We do | |
// this by calling immediately calling the anonymous | |
// function with a function sharing the same body. | |
fact1 = | |
(function(f) { | |
return (function(n){ | |
return (n === 1) ? 1 : n * f(f)(n-1); | |
}); | |
})(function(f) { | |
return (function(n){ | |
return (n === 1) ? 1 : n * f(f)(n-1); | |
}); | |
}); | |
console.log( fact1(5) ); // returns 120 | |
// Here we use the opposite of eta-reduction in order | |
// to remove the need for the function body to | |
// call f on itself. Note that eta reduction is | |
// removing a redundant lamda expression where | |
// the function could be called more directly. | |
fact2 = | |
(function(f) { | |
return (function(func_arg){ | |
return (function(n){ | |
return (n === 1) ? 1 : n * func_arg(n-1); | |
}); | |
})(function(arg){return f(f)(arg);}) | |
})(function(f) { | |
return (function(func_arg){ | |
return (function(n){ | |
return (n === 1) ? 1 : n * func_arg(n-1); | |
}); | |
})(function(arg){return f(f)(arg);}) | |
}); | |
console.log( fact2(5) ); // returns 120 | |
// Of course, we realize that we can remove the body | |
// of the two functions, parameterizing them with | |
// facto. | |
facto = | |
function(func_arg){ | |
return (function(n){ | |
return (n === 1) ? 1 : n * func_arg(n-1); | |
}); | |
}; | |
fact3 = | |
(function(f) { | |
return (facto)(function(arg){return f(f)(arg);}) | |
})(function(f) { | |
return (facto)(function(arg){return f(f)(arg);}) | |
}); | |
console.log( fact3(5) ); // returns 120 | |
// And finally we can derive the applicative order | |
// y combinator, which abstracts fact3 to support any | |
// function with a similar structure to facto | |
Yb = function(proc) { | |
return (function(f) { | |
return (proc)(function(arg){return f(f)(arg);}) | |
})(function(f) { | |
return (proc)(function(arg){return f(f)(arg);}) | |
}); | |
}; | |
console.log( Yb(facto)(5) ); // returns 120 | |
// And we can go a little bit further to form the same | |
// applicative order y-combinator that Crockford produced | |
// for the Little Javascripter by realizing that we have | |
// two functions with exactly the same body - let's abstract | |
// that away. | |
Y = function(proc) { | |
return (function(g){ | |
return g(g); | |
})(function(f) { | |
return (proc)(function(arg){return f(f)(arg);}) | |
}); | |
}; | |
console.log( Y(facto)(5) ); // returns 120 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment