Christian Neukirchen <chneukirchen <at> gmail.com> writes:
> The real question is why the Ruby interpreter doesn't do tail-call
> optimization...

The interpreter doesn't do this automatically. You have to tell him :-)

  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


Here's the missing code, based on an idea from Sam Stephenson in
[ruby-talk:113700]

  class Class
    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

Note that this is just a proof of concept and hasn't been tested thoroughly.

Regards,
Pit