search

tdg5 / tco_method

Simplifies compiling code with tail call optimization in MRI Ruby
https://rubygems.org/gems/tco_method
MIT License
21 stars 1 forks source link

still getting stack level too deep error #1

Open bcavileer opened 9 years ago

bcavileer commented 9 years ago

Please have a look at my example over here: https://github.com/bcavileer/ack/blob/master/lib/ack.rb#L19 compiled:7: stack level too deep (SystemStackError) ruby 2.1.2p95 (2014-05-08) [x86_64-linux-gnu]

I'm trying to get a method to be TCO without hacking with Ruby VM =)

tdg5 commented 9 years ago

Hey! Sorry for the delayed response. I kind of thought I dreamt this issue haha.

Anyway, you'll have to forgive me, but I'm not especially familiar with the Ackerman function.

I played with the code for a few minutes and couldn't get it to optimize the tail calls. My hypothesis is that it's because this version of Ackerman is not fully tail-recursive. My leaning is that Ackerman can't be tail call optimized in a naive fashion.

I don't know for a fact that this is the case, but I've come to recognize lines like this one as the hallmark of tail recursive functions that can't be tail call optimized:

ack(m-1, ack(m, n-1))

I tried to dig around a little on the subject, but found nothing conclusive on this matter. Here's what I did find though.

I found multiple sources that indicate that Ackerman can be expressed in a tail recursive fashion, but I haven't found anything that leads me to believe that those tail calls can be optimized on the stack.

I added some puts statements, and it's definitely the line I referenced above where the stack begins to grow.

This stackoverflow suggests that though the presented Ackerman function is tail-recursive it's still going to accumulate stack. It's suggested that continuation passing might be a way around this, but I suspect it doesn't really change the issue, it just moves the issue somewhere else where the Ruby VM won't get angry about how many calls are queued up.

LISP isn't my strong suit, but it's possible this version might be more readily tail call optimized since the call signature at the end of the function is more obviously tail call optimizable: http://lambda-the-ultimate.org/node/2673

This paper seems interesting in regard to Ackerman (search the PDF for Ackerman) It gives some indication that Ackerman is a kind of hybrid recursive call in that two of it's three recursive calls are tail recursive, but the third call isn't. The code for the benchmark is in the appendix and looks similar to yours.

Though examples are in flavors of basic, the tail recursive example here suggests that their tail recursive Ackerman still uses significant stack.

That's all I've got for now. Do you mind taking a look at some of these resources and seeing if any of them lead you to believe that Ackerman isn't friendly to tail call optimization?

Let me know what you find!