Y Combinator

See Mike Vanier’s blog post explaining the Y Combinator as it is introduced in The Little Schemer and derived by Eli Barzilay.

Presented here is a JavaScript implementation of the Y Combinator, which The Little Schemer implements with, well, Scheme. More specifically, the desired flavor of Y combinator is the applicative-order Y Combinator:

Racket

(define Y
  (lambda (f)
    ((lambda (x) (x x))
     (lambda (x) (f (lambda (g) ((x x) g)))))))

JavaScript

var Y = function(fix) {
  return (function(again) {
    return again(again);
  })(function (again) {
    return fix(function(x) {
      return (again(again))(x);
    });  
  });
};

• combinator because the function Y contains only bound variables.
• applicative-order because in a language that does not support lazy evaluation of arguments, the functions produced by the Y Combinator will only be evaluated when arguments are applied to them. The alternative is a normal-order Y combinator.
• Y because why not? Thank you, Haskell Curry.
• why? So that recursion can be implemented without explicit language support for calling a function recursively. Closures come to the rescue, and anonymous (lambda) functions wrapping functions which produce functions helps avoid the Y Combinator “blowing up” under strict-evaluation.

Pay careful attention to these lines.

See also code snippets from my attempts at working through The Little Schemer.