January 2009

Tailin' Ruby

Ruby doesn’t do tail call optimization. That sucks. However, quite a few month ago I managed to fake it:

RunAgain = Class.new(Exception)
def fib(i, n = 1, result = 0)
  if i == -1
    result
  else
    raise RunAgain
  end
rescue RunAgain
  i, n, result = i - 1, n + result, n
  retry
end

It was extremely slow (see benchmark at the end of this post) since it has to build backtrace for each raise, but at least it worked! I was proud; very proud. Until I discovered this snippet:

class Class
  # Sweet stuff!
  def tailcall_optimize( *methods )
    methods.each do |meth|
      org = instance_method( meth )
      define_method( meth ) do |*args|
        if Thread.current[ meth ]
          throw( :recurse, args )
        else
          Thread.current[ meth ] = org.bind( self )
          result = catch( :done ) do
            loop do
              args = catch( :recurse ) do
                throw( :done, Thread.current[ meth ].call( *args ) )
              end
            end
          end
          Thread.current[ meth ] = nil
          result
        end
      end
    end
  end
end

class TCOTest
  # tail-recursive factorial
  def fact( n, acc = 1 )
    if n < 2 then acc else fact( n-1, n*acc ) end
  end

  # length of factorial
  def fact_size( n )
    fact( n ).size
  rescue
    $!
  end   
end

t = TCOTest.new

# normal method
puts t.fact_size( 10000 )  # => stack level too deep

# enable tail-call optimization
class TCOTest
  tailcall_optimize :fact
end

# tail-call optimized method
puts t.fact_size( 10000 )  # => 14808

Not only was it faster, you could also drop it in wherever you want. Sweet stuff, indeed. My (failed) attempt was sent to /dev/null immediately…

The Ruby Programming Language arrives

A few months later, I received my copy of The Ruby Programming Language and started reading it. Suddenly, on page 151:

The Ruby Programming Language, page 151, 5.5.4 redo: The redo statement restarts the current iteration of a loop or iterator. This is not the same thing as next. next transfers control to the end of a loop or block so that the next iteration can begin, whereas redo transfers control back to the top of the loop or block so that the iteration can start over. If you come to Ruby from a C-like language, then redo is probably a new control structure for you.

I’ve used Ruby for a long time, still I’ve never heard of redo… Here’s an example from the book:

puts "Please enter the first word you think of"
words = %w(apple banana cherry)
response = words.collect do |word|
  # Control returns here when redo is executed
  print word + "> "               # Prompt the user
  response = gets.chop            # Get a response
  if response.size == 0           # If user entered nothing
    word.upcase!                  # Emphasize the prompt with uppercase
    redo                          # And skip to the top of the block
  end
  response                        # Return the response
end

So I started thinking: The reason I used raise/rescue in my implementation was because I needed the retry-keyword… Maybe… What if?

def fib(i, n = 1, result = 0)
  if i == -1
    result
  else
    i, n, result = i - 1, n + result, n
    redo
  end
end

fib(10000)

Unfortunately, “The redo statement restarts the currentiteration of a loop or iterator”, so it only throws a LocalJumpError. However, don’t forget that we’re dealing with Ruby:

### Everything is possible in Ruby!

define_method(:acc) do |i, n, result|
  if i == -1
    result
  else
    i, n, result = i - 1, n + result, n
    redo
  end
end

def fib(i)
  acc(i, 1, 0)
end

fib(10000)  # Yeah!

The Benchmark

So, how fast is it? Take a look below:

Nifty, eh?