Chad Perrin: SOB

20 August 2008

Ruby and Tail Call Optimization

Filed under: Geek — apotheon @ 10:06

1.8.x is the current stable version of Ruby's reference implementation. It, like its predecessors, does not support tail call optimization for recursive functions.

A couple times in recent months I set out to write something in Ruby and found myself thinking "I should do this with a recursive function." Then I'd rattle around inside my head, trying to figure out why I can't remember how to write tail recursive functions in Ruby. Finally, I'd realize "Oh, damn — that's right! Ruby doesn't support tail call optimization." At that point, I'd just throw away my initial idea of how to write the code and reorganize the idea to use one of Ruby's excellent block-fed iterators instead.

Ruby's iterators that take blocks as parameters are beautiful things to behold, for what they are. Unfortunately, they are sometimes not the ideal solution — just the necessary solution if you don't want to drag your code to a painstaking crawl, filling up all available RAM on your system, because there's no tail call optimization. This is one of Ruby's biggest, ugliest warts, in my opinion: the lack of support for tail call optimization. I wants my tail call optimization.

I started searching for information on future planned support for tail call optimization tonight, and found a Weblog post talking about how bare recursion is much faster in Ruby 1.9 than Python 2.5. This is not even tail recursive code in the example. Discussion in comments there suggests that Python 2.5 does not support tail call optimization, and whether Ruby 1.9 will support tail call optimization is essentially impossible to determine from this discussion, since support for tail call optimization wouldn't make any difference in this case and the people involved in the discussion seem confused about the matter in any case.

I've searched around elsewhere on the Web for this information (though not exhaustively), and still found nothing that gives me any credible sense of whether Ruby 1.9 incorporates tail call optimization.

Is there someone out there who can answer this question for me?

6 Comments

  1. YARV supports tail-call optimization, but it's currently disabled by default, see vm_opts.h:

    #define OPT_TAILCALL_OPTIMIZATION    0
    

    It's mentioned in this interview. JRuby supports it too.

    Comment by Thomas — 21 August 2008 @ 12:36

  2. Thanks for the information, Thomas. Do you know if there will be a reference implementation of Ruby 1.9, distinct from YARV — or is YARV now it? I'm still not 100% clear on whether YARV is the new Ruby or a new Ruby.

    . . . and do you happen to know why support for tail call optimization is disabled by default?

    JRuby, on the other hand, is likely to mean very little to me, since as things currently stand it seems to be in my best interest to avoid mucking about with the JVM.

    Comment by apotheon — 21 August 2008 @ 12:59

  3. Python does not support TCO out of the box, but many people have written decorators (functions or classes that transform functions) in order to add TCO support to Python. Basically, you import the library, add @TCO to the line before the def, and you're done.

    Comment by Carl — 21 August 2008 @ 03:07

  4. From the linked interview, it sounds like YARV is the new Ruby VM. I'd like to see tail call optimization on by default — the lack thereof is only useful for debugging AFAIK, and you rarely need to debug Ruby anyway.

    Comment by Sterling Camden — 21 August 2008 @ 09:39

  5. Carl:

    It's not surprising to know it's possible, but I didn't really expect someone to have actually tackled the problem of adding tail call optimization via a library. Good to know.

    Reports I've read of what's being done with YARV seem to suggest that it can perform tail call analysis, but that it doesn't actually optimize tail call recursive code. Seems kinda weird to me.

    Thomas pointed out that tail call optimization is available as a compile option, however, so I wonder if what I've read about YARV before this is out of date.

    Sterling Camden:

    it sounds like YARV is the new Ruby VM

    I thought so, too — but I just wasn't sure from that alone, especially since I'm not positive that wasn't a case of "This is what we think we're doing for now." I mean, if I were basing my understanding on this interview alone, I'd probably be convinced that YARV is the next official reference implementation of Ruby, but I kinda wonder since some of the language of other references to YARV being added to the Ruby development trunk sound a little . . . vague on the subject.

    I'd like to see tail call optimization on by default

    I'm interested in the reasoning behind turning off tail call optimization by default. It seems like an odd decision to make, and makes me think there must be some benefit to be gained by turning it off in the general case (where one uses Ruby iterators rather than recursion).

    you rarely need to debug Ruby anyway.

    Y'know, that's my experience too — but I'm not 100% sure why that should be. Sure, I can come up with a whole lot of reasons that Ruby should require significantly less debugging (maybe as a somewhat predictable fraction of debugging required for another language such as Java, all else being equal), but I haven't yet figured out why it should so often require no debugging at all. When I rewrite any Ruby code, it's usually because of a typo, because I had a brain fart and thought I was writing code in some other language for a moment, or because I decided to refactor something.

    It just seems there's something more significant at work than greater syntactic clarity and semantic power, but I haven't pinned down whatever that significant factor might be.

    Comment by apotheon — 21 August 2008 @ 10:25

  6. Yes; YARV is in Ruby trunk, and the 1.9 developer snapshot releases; svn co http://svn.ruby-lang.org/repos/ruby/trunk. As to why it's disabled, I'm not sure; it doesn't seem to have got any attention on any mailing lists. Maybe that's what it needs :)

    Comment by Thomas — 21 August 2008 @ 11:52

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

All original content Copyright Chad Perrin: Distributed under the terms of the Open Works License