Skip to content

Instantly share code, notes, and snippets.

@pboyer
Created April 1, 2013 01:27
Show Gist options
  • Save pboyer/5282757 to your computer and use it in GitHub Desktop.
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
// 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