#528: Improve Tail Call Elimination
-------------------------------------+--------------------------------------
Reporter: haruki.zae...@… | Owner: lsansone...@…
Type: enhancement | Status: new
Priority: minor | Milestone:
Component: MacRuby | Keywords: tail call elimination
optimisation tco
-------------------------------------+--------------------------------------
Description changed by lsansone...@…:
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/>
_______________________________________________
MacRuby-devel mailing list
MacRuby-devel@lists.macosforge.org
http://lists.macosforge.org/mailman/listinfo.cgi/macruby-devel
