Robot Has No Heart

Xavier Shay blogs here

A robot that does not have a heart

Understanding the Y Combinator

Many people have written about this, it still took me a long while to figure it out. It’s a bit of a mindfuck. So here is me rehashing what other people have said in a way that makes sense to me.

The Problem

I’ll start with the same example of hash autovivication (that’s what perl calls it) used by Charles Duan in his article. We want the following code to work:

1
2
3

hash = Hash.new {|h, k| h[k] = default } # We need to implement default later, read on!
hash[1][2][3][4][5] = true
hash # => {1=>{2=>{3=>{4=>{5=>true}}}}}

To do this, we need to specify an appropriate default value for the hash. If we set the default to {}, we only get one level of autovivication.

1
2
3

hash = Hash.new {|h, k| h[k] = {} }
hash[1]    # => {} 
hash[1][2] # => nil

Clearly we need a recursive function to support infinite depth, which we can do with a normal ruby method.

1
2
3
4
5
6

def make_hash
  Hash.new {|h, k| h[k] = make_hash }
end  

hash = make_hash
hash[1][2][3][4][5] # => {}

The problem here is we’ve introduced a new method into the namespace (make_hash), which isn’t really necessary. The Y Combinator allows us to achieve the same result, without a named method or variable.

The Solution

We can avoid the need for a named method by wrapping the Hash creation code in an anonymous lambda that passes in the callback as an argument.

1

lambda {|callback| Hash.new {|h, k| h[k] = callback.call }}.call(some_callback)

We just need a way to pass in a callback function that is the same as the initial function. If you try to copy and paste in the hash maker code, you’ll find it doesn’t quite work because we then need a way to get a callback for that callback.

1
2
3
4
5
6
7

lambda {|callback| 
  Hash.new {|h, k| h[k] = callback.call }
}.call(
  lambda { 
    Hash.new {|h, k| h[k] = callback.call }
  }
}) # fails because the second callback isn't defined

But we’re getting closer. What if we pass in our initial callback function as a parameter to itself? Then it will know how to call itself over and over again. This is pretty tricky – the first example illustrates the concept using a named method for clarity, the second example is what we actually want.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# With named method
def make_hash(x) 
  Hash.new {|h,k| h[k] = x.call(x)}
end 
hash = make_hash(method(:make_hash))

# With lambdas
hash = lambda {|callback| 
  Hash.new {|h, k| h[k] = callback.call(callback) }
}.call(
  lambda {|callback| 
    Hash.new {|h, k| h[k] = callback.call(callback) }
  })
hash[1][2][3][4][5] # => {}, hooray!

And that’s really the guts of it. If you understand that you’ve pretty much got it. From here on in it’s just extra credit.

Making it DRY

The previous code repeats itself somewhat – you copy and paste the hash maker function into two spots. Basically, the code is hash = x.call(x). So let’s use another lambda to express it as such.

1
2
3
4

lambda {|x| x.call(x) }.call(
  lambda {|callback| 
    Hash.new {|h, k| h[k] = callback.call(callback) }
  })

Making it work for callbacks with an arbitrary number of parameters

By passing in the callback to itself, we’re restricting ourselves to a callback with no parameters. You’ll notice we’re not able to pass in any parameters to the hash maker above. As you may have guessed, we add another level of abstraction with a lambda that passes in a callback_maker function.

1
2
3
4
5
6

hash = lambda {|x| x.call(x) }.call(lambda {|callback_maker| 
  lambda {|*args| 
    callback = callback_maker.call(callback_maker)
    Hash.new {|h, k| h[k] = callback.call(*args) }
  }
}).call("an argument!")

So yes, that example is kind of useless because we don’t use the arguments. Let’s try something a bit meatier, say a factorial function.

1
2
3
4
5
6
7

lambda {|x| x.call(x) }.call(lambda {|callback_maker| 
  lambda {|*args| 
    callback = callback_maker.call(callback_maker)
    v = args.first
    return v == 1 ? 1 : v * callback.call(v - 1)
  }
}).call(5) # => 120

Making it generic and pretty

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def y_combinator(&generator)
  lambda {|x| x.call(x) }.call(lambda {|callback_maker| 
    lambda {|*args| 
      callback = callback_maker.call(callback_maker)
      generator.call(callback).call(*args)
    }
  })
end

y_combinator {|callback|
  lambda {|v|
    return v == 1 ? 1 : v * callback.call(v - 1)
  }
}.call(5) # => 120
end

And let’s make it a bit less ugly by doing what Tom Mortel did and using [] instead of call (they’re equivalent), and moving the callback_maker inline.

1
2
3
4
5

def y_combinator(&f)
  lambda {|x| x[x] } [
    lambda {|maker| lambda {|*args| f[maker[maker]][*args] }}
  ]
end

Thus ends my exploration of the Y Combinator. Practically useless in any language you’d be using today, but hey, don’t you feel smarter?

UPDATE: Added dmh’s suggestion from the comments.

  1. dmh2000 says:
    December 20, 2007 at 5:12 PM

    You might also add a section just before ‘the solution’ that uses a named recursive function that calls itself, but using a parameter. this might make it more clear later on when you explain x.call(x) for anonymous functions

    I think this is right (I’m not a Ruby guy)

    def make_hash(x) Hash.new {|h,k| h[k] = x.call(x)} end

    hash = make_hash(method(:make_hash)) hash13[5]

  2. Xavier Shay says:
    December 20, 2007 at 9:15 PM

    Yes good idea, I added it where I introduce x.call(x)

  3. pluskid says:
    December 21, 2007 at 8:56 AM

    Since Ruby allow named recursive function, we can simply write a y combinator in named recursive syntax:

    def y_combinator(f) # lambda used to delay evaluation lambda { |args| f.call(y_combinator(f)).call(args) } end

    which can then be used to construct anonymous recursive functions. :)

  4. Xavier Shay says:
    December 22, 2007 at 5:15 AM

    If you’re going to use named recursion, you may as well just do:

    result = (func = lambda {|n| n == 1 ? 1 : n * func[n - 1]})[5]

    ... which is my prefferred way of doing once off recursion in everyday coding.

    In other news, I really need to get code highlighting and preview in comments…

  5. jeff says:
    April 17, 2008 at 7:01 AM

    Breaking it down like this helped me:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    hash = lambda {|callback| 
  puts "First lambda: callback=#{callback.inspect}"
  Hash.new do |h, k| 
    puts "First Hash.new: h=#{h.inspect}, k=#{k.inspect}, callback=#{callback.inspect}"
    h[k] = callback.call(callback)
  end
}.call(
  lambda {|callback2|
    puts "Second lambda: callback2=#{callback2.inspect}"
    Hash.new do |h, k|
      puts "Second Hash.new: h=#{h.inspect}, k=#{k.inspect}, callback2=#{callback2.inspect}"
      h[k] = callback2.call(callback2)
    end
  })

puts 'A--'
puts hash[1][2][3].inspect
puts 'B--'
puts hash[1][2][3].inspect
puts 'C--'
puts hash.inspect

    output:
    1
2
3
4
5
6
7
8
9
10
11
12
13

    First lambda: callback=#<Proc:0x00028b2c@example.rb:8>
A--
First Hash.new: h={}, k=1, callback=#<Proc:0x00028b2c@example.rb:8>
Second lambda: callback2=#<Proc:0x00028b2c@example.rb:8>
Second Hash.new: h={}, k=2, callback2=#<Proc:0x00028b2c@example.rb:8>
Second lambda: callback2=#<Proc:0x00028b2c@example.rb:8>
Second Hash.new: h={}, k=3, callback2=#<Proc:0x00028b2c@example.rb:8>
Second lambda: callback2=#<Proc:0x00028b2c@example.rb:8>
{}
B--
{}
C--
{1=>{2=>{3=>{}}}}

    Also the solution can be further unrolled to make the internals clearer:
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    callback=  lambda {|callback2|
    puts "Second lambda: callback2=#{callback2.inspect}"
    Hash.new do |h, k|
      puts "Second Hash.new: h=#{h.inspect}, k=#{k.inspect}, callback2=#{callback2.inspect}"
      h[k] = callback2.call(callback2)
    end
  }

hash = Hash.new do |h, k| 
    puts "First Hash.new: h=#{h.inspect}, k=#{k.inspect}, callback=#{callback.inspect}"
    h[k] = callback.call(callback)
  end
    
puts 'A--'
puts hash[1][2][3].inspect
puts 'B--'
puts hash[1][2][3].inspect
puts 'C--'
puts hash.inspect

Hungry for more? Try these related posts, or find more in the archives.

Post a comment


(lesstile enabled - surround code blocks with ---)

A pretty flower Another pretty flower