Fun With the Y Combinator in Ruby

Posted September 23, 2007

A while back, I was playing around with anonymous recursive functions. I ended up creating an anonymously recursive lambda function, which I called reclambda, in Ruby. At the time this blog was yet to be created, so Hampton Catlin wrote it up instead.

I didn’t really understand it, though. The code was mostly ported from a Scheme example I found somewhere. I always felt kinda bad about that.

Recently, I decided to remedy my ignorance. I bought and worked through The Little Schemer1.

Although the whole book is fascinating, What really made it for me was the chapter on the Y combinator. After reading that, I felt for the first time that I actually understood how it worked. Feeling renewed confidence, I set out to remake it – by hand – in Ruby.

Let me take a step back here and define what I’m talking about.

First of all, what’s this Y thing? The Y combinator is just a function. It takes as input a function, f, and returns a function, g, such that f.call(g) returns g.

That doesn’t seem possible. What about, say, x + 1?

Y { |x| x + 1 } #=> ???

Well, this actually breaks. Our friend Y only works on functions that expect functions. x will always be a function, so treating it as a number will just cause type errors. Alas.

Now what about anonymous recursive functions? What are these? Well, we all know what a recursive function is. It’s a function that calls itself. The classic example is factorial:

def factorial(n)
  if n == 0
    1
  else
    n * factorial(n - 1)
  end
end

We also know what an anonymous function is. It’s a function that we create “on the fly,” so to speak. They’re used all the time in Ruby. Every block is an anonymous function that gets called when the method yields values. You can also create anonymous functions with proc or lambda:

fun = lambda { |x| x + 1 }
fun.call(1) #=> 2

An anonymous function is just a function without a name. So what’s the big deal about anonymous recursive functions? In order to recurse, it looks like you need to give the function a name. But anonymous functions have no names. Yeep.

Does that mean that anonymity and recursivity are mutually exclusive? Thanks to the Y combinator, no, it does not!

Let’s think this through. What’s preventing us from recursing? We don’t have a reference to our function.

Let’s supposed that we were to be passed such a reference. Then we could make a function that would take the reference and return a new function that used it to recurse:

lambda { |this| lambda { |n| n  0 ? 1 : n * this.call(n - 1) } }

Now think about what would happen if you passed this to Y. It returns a function that, if passed as this in the above expression, returns itself. What function could this be? It must be the inner function:

lambda { |n| n  0 ? 1 : n * this.call(n - 1) }

And now we actually have a this. Moreover, it’s the same function that we’re running right now. In short: we have achieved anonymous recursion. Sweet.

So, um, what is this super-magical Y function? How is it defined? Let’s try see if we can build it ourselves.

We’ll build it around the function we eventually want to pass to Y. Here it is in a more expanded form than before:

lambda do |this|
  lambda do |n|
    if n == 0
      1
    else
      n * this.call(n - 1)
    end
  end
end

For a first try, let’s try just passing this to itself. We’re going for functions having references to themselves, so that seems like a reasonable place to start. We can do so by calling the self-application function:

lambda { |f| f.call(f) }

This just calls a function with itself as an argument. It’s a little mind-bendy, but think about it for a sec and it should make sense. Using it on our old function:

lambda { |f| f.call(f) }.call(
  lambda do |this|
    lambda do |n|
      if n == 0
        1
      else
        n * this.call(n - 1)
      end
    end
  end)

Unfortunately, this doesn’t quite work. this isn’t the inner function, it’s the wrapper function. Thus, this.call(n - 1) doesn’t work, because it’s expecting a function, not an integer.

So what if we call the wrapper function first? We’d want to pass it itself, because that’s what it’ll now be expecting:

lambda { |f| f.call(f) }.call(
  lambda do |this|
    lambda do |n|
      if n == 0
        1
      else
        n * this.call(this).call(n - 1)
      end
    end
  end)

And this works! Calling it on 3 produces 6, calling it on 4 produces 24. That wasn’t so hard, was it?

The code isn’t really what we were going for, though. We had to modify the body of the factorial function to make it work.

But what if we move the whole this.call(this) bit into its own function? Is that possible?

It is if we wrap the wrapper function in yet another function. This allows us to get a reference to what used to be this, which we’ll now call g. We can then pass lambda { g.call(g) } as this:

lambda { |f| f.call(f) }.call(
  lambda do |g|
    lambda do |this|
      lambda do |n|
        if n == 0
          1
        else
          n * this.call.call(n - 1)
        end
      end
    end.call(lambda { g.call(g) })
  end)

The recursion line is still ugly. Do we have to do this.call.call? No, we don’t! We can have this handle the call to the resulting function as well:

lambda { |f| f.call(f) }.call(
  lambda do |g|
    lambda do |this|
      lambda do |n|
        if n == 0
          1
        else
          n * this.call(n - 1)
        end
      end
    end.call(lambda { |n| g.call(g).call(n) })
  end)

And now what we have inside is just what we had before. In fact, we can make this a function and take that chunk as a block:

def Y
  lambda { |f| f.call(f) }.call(
    lambda do |g|
      yield(lambda { |*n| g.call(g).call(*n) })
    end)
end

And that’s the Y combinator. Let’s see it in action:

Y { |this| lambda { |n| n == 0 ? 1 : n * this.call(n - 1) } }.call(12) #=> 479001600

Huzzah!

1 The Little Schemer, by Daniel P. Friedman and Matthais Felleisen, is a classic introduction to the wonderful things you can do with recursion and first-class functions.

Anonymous said September 24, 2007:

Perhaps you have a typo somewhere in your last two code blocks. I tried running them myself and I got: undefined method `n’ for main:Object (NoMethodError)

Ted said September 24, 2007:

Nice write-up, but you’ve got some formatting issues in your code snippets. Some of them are missing the ”==” comparator and one of them has “strong” tags in it.

Nathan said September 24, 2007:

Yikes. Fixed, now. I thought I had smoothed out all those bugs…

Cheba said October 23, 2007:

Great post. But I can’t really find a practical use of this. What is it for?

Nathan said October 23, 2007:

Well, aside from making for some really cool blog posts, I believe it’s useful in lambda calculus, the theory of how functions interact. When you’re just dealing with functions, there’s no other way1 to do recursion. Without recursion, there’s no way to do any sort of looping, etc. So it’s a theoretically useful construct.

In terms of actual day-to-day use, it’s not all that useful, although occasionally you may want an anonymous, recursive function, in which case Y comes in handy. In that case, you could just name it, but Y is more elegant.

1 Actually I think there are other combinators that allow recursion, but Y is the simplest.

binaryten said December 17, 2007:

I disagree. Y combinators are extremely useful for things like memoizing recursive functions.

Make your comments snazzy with Textile!