Skip to content

Instantly share code, notes, and snippets.

@bmershon
Last active January 13, 2023 13:06
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save bmershon/d332ba9b06975562979efba7b367e162 to your computer and use it in GitHub Desktop.
Y Combinator
border: no

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.

<!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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment