[MacRuby-devel] [MacRuby] #528: Improve Tail Call Elimination

[MacRuby]

#528: Improve Tail Call Elimination
-------------------------------------+--------------------------------------
 Reporter:  haruki.zaemon@…          |       Owner:  lsansonetti@…                         
     Type:  enhancement              |      Status:  new                                   
 Priority:  minor                    |   Milestone:                                        
Component:  MacRuby                  |    Keywords:  tail call elimination optimisation tco
-------------------------------------+--------------------------------------
 As it currently stands, MacRuby performs TCO for a method that calls
 itself. This is a great start and the implementation appears to be better
 than any other current Ruby implementation.

 When dealing with OO data structures, it's more common to call methods on
 _other_ instances and/or mutual recursion between two methods--be they on
 the same or a different instance.

 For example, imagine traversing a linked list recursively:

     def each
       yield(head)
       tail.each(&block)
     end

 This works great for small-ish lists but when processing larger lists
 stack overflows are common place. To remedy this, it needs to be re-
 written iteratively:

     def each
       list = self
       while !list.empty?
         yield(list.head)
         list = list.tail
       end
     end

 Not only is the latter more verbose, but in either case, without TCO,
 because the code always executes in the context of the first element, the
 traversal must complete before the garbage collector has a chance to reap
 unreferenced elements.

 It would be great if MacRub could do tail-call elimination for any
 returning statement that no longer requires the stack.

-- 
Ticket URL: <http://www.macruby.org/trac/ticket/528>
MacRuby <http://macruby.org/>