D3 Examples - Y Combinator

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.

xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<title>Y Combinator</title>
<body>
  <svg width="960px" height="500px"></svg>
</body>
<script src="https://d3js.org/d3.v4.js"></script>
<script>
​
// Applicative-order Y Combinator.
var Y = function(fix) {
  return (function(again) {
    // Closes a lambda function over the defninition of itself.
    return again(again);
  })
  // This is the lambda function closed over the definition of itself.
  (function (again) {
    // When Y(fixFactorial) is called, a lambda function is produced whose
    // argument is has a self-invoking closure; that argument is called
    // when recursion should continue.
    return fix(function(x) {
      // x is the single argument that is passed to inner lambda function
      // of fixFactorial.
      return (again(again))(x);
    });  
  });
};
​
// A non-recursive function which returns a function that recursively
// computes the factorial of n if the function fixpoint actually happens
// to be the fixpoint of fixFactorial. That is, fixFactorial can "fix"
// factorial if it is provided witha function that would... fix factorial.
// It turns out that factorial is equivalent to:
// fixFactorial(fixFactorial(fixFactorial(... ad infinitum ...)));
// Consider:
// (fixFactorial(fixFactorial(fixFactorial(fixFactorial(() => 0)))))(3)
var fixFactorial = function(fixpoint) {
  // Assuming fixpoint will compute the factorial of n, the following
  // lambda function will "recursively" compute the factorial of n.
  return function(n) {
    return(n < 2)
      ? 1 // Base case.
      // The following is an expansion of the recursive call for factorial(3):
      // (Y(fixFactorial))(3)
      // => (fixFactorial([~fixpoint closure~]))(3)
      // => (function(n) { return ... "will produce another fixpoint closure" ... })(3)
      // => 3 * (fixFactorial([~fixpoint closure~]))(2)
      // => 3 * (function(n) { return ... "will produce another fixpoint closure" ... })(2)
      // => 3 * 2 * (fixFactorial([~fixpoint closure~]))(1)
      // => 3 * 2 * (function(n) { return ... "will encounter base case" ... })(1)
      // => 3 * 2 * 1
      : (n * fixpoint(n - 1)); // (*)
  };
};
​
// Don't call me or else!
var eternity = function(x) { while(true) { /* Wait for it... */ } };
​
// Concrete example.
(fixFactorial(
  (fixFactorial(
    fixFactorial(
      fixFactorial(
        fixFactorial(
          fixFactorial(eternity))))))))(6); // We don't reach eternity!
// => 720
​
// Another example.
(fixFactorial(
  (fixFactorial(
    fixFactorial(
      fixFactorial(
        fixFactorial(
          fixFactorial(eternity))))))))(5); // We don't reach this level!
// => 120
​
// Another example.
(fixFactorial(
  (fixFactorial(
    fixFactorial(
      fixFactorial( 
        fixFactorial( // We don't reach this level.
          fixFactorial(eternity))))))))(4);
// => 124
​
// Yet another example. A Different argument at the end, but the same level of
// recursion is achievable! We have overspecified the recursive tower, since
// we won't hit all the levels with an argument of 3.
(fixFactorial(
  (fixFactorial(
    fixFactorial(
      fixFactorial( // We don't even reach this level now.
        fixFactorial( // And therefore not this one either.
          fixFactorial(eternity))))))))(3); // Or this one.
// => 6
​
// factorial() is the result of applying the fixpoint of fixFactorial to
// fixFactorial. This function behaves as we would expect a recursively
// defined factorial function to behave.
var factorial = Y(fixFactorial);
​
d3.select("svg").append("text")
  .text(factorial(10))
  .attr("x", 960 / 2)
  .attr("y", 500 / 2)
  .style("font-family", "helvetica")
  .style("font-size", "48px")
  .style("text-anchor", "middle");
​
</script>
    