#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 -------------------------------------+-------------------------------------- Description changed by lsansonetti@…: Old description:

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.

New description: 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#comment:2> MacRuby <http://macruby.org/>

#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 -------------------------------------+-------------------------------------- Comment(by jvoorhis@…): Replying to [comment:3 haruki.zaemon@…]:

I'm not worried about wasteful calls. Recursively descending through a large data structure is the problem.

+1 Guy Steele made a good argument for supporting mutually recursive method calls for the same reason at http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRec.... -- Ticket URL: <http://www.macruby.org/trac/ticket/528#comment:4> MacRuby <http://macruby.org/>

#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 -------------------------------------+-------------------------------------- Comment(by conradwt@…): Replying to [comment:3 haruki.zaemon@…]:

...

In regards to writing recursive methods, one would usually use memoization technique(s) in conjunction with recursion to eliminate wasteful calls.

I'm not worried about wasteful calls. Recursively descending through a large data structure is the problem.

If you need tail call optimization, then you're definitely concerned about the wasteful calls because the goal of tail call optimization is to transform recursive alogithm into iterative algorithm. Thus, reducing the overall stack space used and approve the efficiency of the running algorithm. Memoization is a manual way of achieving this that greatly decreases stack frame usage but I guess that you're looking for something automatically done with MacRuby VM.

...

Also, all core data structures or containers within Ruby Programming Language provide mechanisms for easily iterating through their contents.

Perhaps the example was misleading, these are custom application data structures with thousands of nodes.

Yes, there could be thousands of nodes within your custom application data structure but it's still your requirement to implement the appropriate traversal algorithm for the data set that you're operating on. In short, one should use the best algorithm for the job and not rely so heavily on what's happening within the language's internals. -- Ticket URL: <http://www.macruby.org/trac/ticket/528#comment:7> MacRuby <http://macruby.org/>

#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 -------------------------------------+-------------------------------------- Comment(by haruki.zaemon@…): Replying to [comment:7 conradwt@…]:

If you need tail call optimization, then you're definitely concerned about the wasteful calls because the goal of tail call optimization is to transform recursive alogithm into iterative algorithm.

The aim of TCO is to allow recursive algorithms to perform within a constrained stack frame. Whether you choose to implement this as re- writing the algorithm iteratively or instead throwing away the stack frame is a choice.

I guess that you're looking for something automatically done with MacRuby VM.

I don't mind if it's explicit :)

It's still your requirement to implement the appropriate traversal algorithm for the data set that you're operating on. In short, one should use the best algorithm for the job and not rely so heavily on what's happening within the language's internals.

And I have, twice: once recursively; then again iteratively actually make it perform. The former being MUCH simpler, the latter being horribly complex. I I'm not accusing MacRuby of being flawed, I'm merely suggesting that, as per the links posted, OO algorithms and data structures can be greatly improved by languages that support TCO. Yes, it's possible to write complex algorithms without TCO; it's also much easier to write them with it. -- Ticket URL: <http://www.macruby.org/trac/ticket/528#comment:9> MacRuby <http://macruby.org/>

#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 -------------------------------------+-------------------------------------- Comment(by haruki.zaemon@…): Replying to [comment:8 conradwt@…]:

TCO would be nice to have but I feel that Ruby specs for both core and language for the MacRuby VM are the most important at this time. Also, this is an open-source project. Thus, one can feel free and receive support for working on any of the internals of the MacRuby VM.

Having looked at the code, I see the TCO stuff is all in LLVM anyway. Guess I'll throw up my hands in defeat. -- Ticket URL: <http://www.macruby.org/trac/ticket/528#comment:11> MacRuby <http://macruby.org/>

#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 -------------------------------------+-------------------------------------- Comment(by lsansonetti@…): We should be able to do much more sophisticated tall call elimination with the new VM changes I'm working on (which allow method inlining). I will investigate that, for 0.6. -- Ticket URL: <http://www.macruby.org/trac/ticket/528#comment:13> MacRuby <http://macruby.org/>