Skip to content

Loading…

Add a mechanism for implict and/or explicit tail call optimisation #138

Closed
harukizaemon opened this Issue · 3 comments

2 participants

@harukizaemon

Performing TCO for a method that calls itself is a great start however 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 Rubinius could provide a mechanism for implicit or explicit tail-call elimination for any returning statement that no longer requires the stack.

I have a project for which I REALLY need this and thus I'm VERY motivated to work on it. I just need a little direction as to how to proceed.

@evanphx
Rubinius member

No todos in github issues.

@evanphx
Rubinius member

No todos in github issues.

This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.