Dec 04

Understanding the Y combinator (in JavaScript)

Recursion and anonymous functions are widely used in modern programming languages. But how does one write an function with no name that calls itself? The Y combinator is the answer to that question.

About a year and a half ago, I discovered a fantastic resource called Nathan’s University. Nathan was an instructor at one of the UC universities and this was basically his own self-produced MOOC. It was an online programming languages course that covered a whirlwind tour of several different languages, a guided path using a Parser Expression Generator to create a subset of scheme, how to create a type system and even a little bit about optimization.

What I just recently remembered was how accessible his explanation of the Y combinator was. First he wrote a simple recursive function in scheme, and then he explained the problem and partially converted it into JavaScript. Here’s a link to the video. (start from 1:46 and watch for ~3 minutes).

I’ve taken the liberty to finish converting the Y combinator and his factorial example into JavaScript:

Why bother? Why not just name the function?

It’s interesting to be able to implement recursion on anonymous functions, but the obvious question is “Why bother? Why not just name the function?” Personally, I do just name the functions. Especially in the case of the factorial function, I can’t see any benefit in using a Y combinator instead of just writing the function on its own in a straight-forward manner. I don’t have experience making any really large programs in scheme or similar languages, so I can’t speak to the possible advantages of this kind of structure when passing around a lot of higher order functions.

Combinators can handle memoization and more

There is something interesting in the case of the fibonacci function, though. By using a slightly different Y combinator-like function, it’s possible to do things like handle memoization inside the combinator! Below is an example that will cache the results of calculations of single function argument functions and use them instead each subsequent time they’re needed. It allows many naively written non-tail recursive functions, including the same fibonacci function from above to still perform well.

Why not just use once()?

The functionality from Ymem above is already included in Underscore.js’s _.once() function, and that’s exactly the tool I’ve been using in JavaScript for the last couple of years. I’m interested in the idea of anonymous recursion. I’d love to see examples from anyone who is experiencing benefits from using it but I haven’t yet.

This entry was tagged , , , .
Bookmark the permalink.

One Response to Understanding the Y combinator (in JavaScript)

  1. Pingback: 1p – Understanding the Y combinator (in JavaScript) – Blog

Leave a Reply

Your email address will not be published. Required fields are marked *