bmershon/.block

## .block
border: no

## README.md

      
    Raw
  

              README.md
            
          
    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.

  
## index.html
<!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>
	<!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>