DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets Manager

Snippets has posted 5883 posts at DZone. View Full User Profile

Avoid 'stack Level Too Deep' In Ruby

06.09.2009

| 5223 views |


#!/usr/local/bin/ruby

##!/opt/local/bin/ruby1.9

# Update Ruby via MacPorts:
# port info ruby19
# sudo port install ruby19
# http://www.macports.org/install.php 
# http://trac.macports.org/wiki/InstallingMacPorts


# See:
# - Tailin' Ruby, http://judofyr.net/posts/tailin-ruby.html
# - Re: Ruby and recursion (Ackermann benchmark), http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/145593

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



# tail-call optimization test

# example 1

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                                  


# example 2

class TCOTest2
   def addnum(i) 
      p i
      addnum(i+1) 
   end
end


#TCOTest2.new.addnum 0   # stack level too deep (SystemStackError)

# enable tail-call optimization
class TCOTest2
  tailcall_optimize :addnum
end

TCOTest2.new.addnum 0

Tags: