My Own Javascript Y Combinator

By anders pearson 15 Sep 2008

I came across a link to the slides for Xavier Leroy’s course on Functional programming languages this weekend and have been slowly making my way through them.

It’s just slides from the lectures so it can be a bit of a struggle to follow them without, you know, the actual lectures. On the other hand, having to struggle a bit and figure out what’s going on from just the slides has been kind of good for forcing me to really pay attention and not gloss over the parts that aren’t immediately obvious.

Judging by the slides, the lectures are fantastic. They’re incredibly ambitious in scope. In the first lecture, it starts by introducing the Lambda Calculus (well, that part is fast enough that I think it’s assumed that the reader is already basically familiar), shows reduction strategies, implements a lambda calculus interpreter in a couple lines of Caml, makes it efficient, adds lexical scoping and closures, and keeps it all tied back to the Lambda Calculus. Further lectures go on to describe abstract machines, compile the enriched Lambda Calculus for the abstract machine, do tail call elimination and lazy evaluation, proves the correctness of the abstract machine and compiler, gets into exception returning vs state passing vs continuation passing implementations, monads and monad transformations (including the concurrency monad transformer), and then gets into some even deeper optimizations. It basically connects the theoretical, mathematical underpinnings of programming all the way to the tricks that are used in compiler optimization. Highly recommended if that sounds interesting to you.

Anyway, in the course of making my way through that material, I decided that I needed to refresh my understanding of the Lambda Calculus and combinators since I haven’t really done much of that since undergrad. I’ve been writing a lot of JavaScript lately for work and, while I still don’t really like the syntax that much, JavaScript does have proper closures so it’s suitable for lambda calculus experimentation.

So I decided to implement the Y Combinator in JavaScript as an exercise. I remember it being covered in class long ago, and, while I could see why it was interesting, I don’t think it ever quite clicked for me exactly how it worked. There’s a good page explaining the how and why of the Y Combinator here. The example code is all in Scheme, so I just went through the page and translated each example to JavaScript, making sure I understood what was going on at each step. I kind of like this approach to learning CS. Just reading a text with code samples, it’s all too easy to accept that the samples do what it says they do and not really spend the extra effort to understand exactly what’s going on. Translating it into a different programming languages forces you to really grasp every detail.

So, this is my JavaScript Y Combinator. There are many like it, but this one is mine:

:::javascript
function Y (X) {
  return (function(procedure) {
    return X(function(arg) {
      return procedure(procedure)(arg);
    });
  })(function(procedure) {
    return X(function(arg) {
      return procedure(procedure)(arg);
    });
  });
}

It’s not as pretty as the scheme version:

:::scheme
(define Y
  (lambda (X)
    ((lambda (procedure)
       (X (lambda (arg) ((procedure procedure) arg))))
     (lambda (procedure)
       (X (lambda (arg) ((procedure procedure) arg)))))))

And neither is as pretty as the original untyped Lambda Calculus:

Y = λf·(λx·f (x x)) (λx·f (x x))

But it works.

Tags: programming functional javascript lambda calculus y combinator