5 ms·

Why Object-Oriented Languages Need Tail Calls

39 points by gioele 15y ago

Flow 15y ago
I remember one of the PLT Scheme guys talking about how without TCO in OO languages you can't even express state machines without creating new state holder objects. In a way, without TCO you must manually abstract each step and the next one and drive the stepping from outside. Not too unlike using an iterator instead of asking a collection to call f() for each entry. Having read what he said I too feel that TCO is a very nice addition to other language features.
- primodemus 15y ago
  Relevant LtU thread: http://lambda-the-ultimate.org/node/3702 http://lambda-the-ultimate.org/node/3702
  - gioele 15y ago
    Sadly it links a blog entry on the old projectfortress.sun.com site (available at http://web.archive.org/web/20110716163344/http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion http://web.archive.org/web/20110716163344/http://projectfort... but without the nice formatted code snippets). Too bad that the new project fortress blog at oracle.com is almost empty and filled with garbage (non-processed TeX sources).
    - mquander 15y ago
      Yeah, does anyone know what the deal with that is? I was really enjoying following Steele's notes on Fortress. I hope that neither the language nor the blog has been binned.
primodemus 15y ago
mirror of the post by Guy Steele: http://www.eighty-twenty.org/index.cgi/tech/oo-tail-calls-20111001.html http://www.eighty-twenty.org/index.cgi/tech/oo-tail-calls-20...
drblast 15y ago
Why is there even an argument about this? Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I'd venture to say it's a "bug." And TCO is so handy in so many instances that it's silly not to have it. And you gain performance.
- raganwald 15y ago
  Why is there even an argument about this? Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I'd venture to say it's a "bug.” You aren’t going to like Python: I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool. http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi... (I’m not advocating this view, just pointing out that there are programmers who appear in all other respects to be reasonable, intelligent, contributing members of computing society who actually feel that TCO is a bug, that 1000 calls ought to be enough for anybody, and so forth.)
  - drblast 15y ago
    I don't like this in a lot of languages. But it's not a showstopper, just an annoyance to be aware of. That said, there should be no reason not to have your new modern programming language support tail calls. It's short-sighted, and can negatively affect more than just the trivial recursive case. So, new programming language inventors, if you're reading this, support tail call optimization and proper tail recursion from the beginning. Your language will be better for it.
    - bascule 15y ago
      > there should be no reason not to have your new modern programming language support tail calls There's many valid reasons not to support TCO. The first one that comes to mind: it makes generating stack traces more difficult. Another reason: the JVM doesn't natively support TCO. This means to implement it you'll either need to use a trampoline (e.g. Erjang) or convert recursion to iteration (e.g. Clojure) The latter isn't too difficult, but when tail recursion merely provides an alternate syntax for iteration, and mutual tail recall recursion isn't supported, is there really as much of a point if your language is something like Ruby and already provides multiple means of iteration?

39 points by gioele 15y ago

Flow 15y ago

I remember one of the PLT Scheme guys talking about how without TCO in OO languages you can't even express state machines without creating new state holder objects. In a way, without TCO you must manually abstract each step and the next one and drive the stepping from outside. Not too unlike using an iterator instead of asking a collection to call f() for each entry. Having read what he said I too feel that TCO is a very nice addition to other language features.

primodemus 15y ago
Relevant LtU thread: http://lambda-the-ultimate.org/node/3702 http://lambda-the-ultimate.org/node/3702
- gioele 15y ago
  Sadly it links a blog entry on the old projectfortress.sun.com site (available at http://web.archive.org/web/20110716163344/http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion http://web.archive.org/web/20110716163344/http://projectfort... but without the nice formatted code snippets). Too bad that the new project fortress blog at oracle.com is almost empty and filled with garbage (non-processed TeX sources).
  - mquander 15y ago
    Yeah, does anyone know what the deal with that is? I was really enjoying following Steele's notes on Fortress. I hope that neither the language nor the blog has been binned.

primodemus 15y ago

mirror of the post by Guy Steele: http://www.eighty-twenty.org/index.cgi/tech/oo-tail-calls-20111001.html http://www.eighty-twenty.org/index.cgi/tech/oo-tail-calls-20...

drblast 15y ago

Why is there even an argument about this? Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I'd venture to say it's a "bug." And TCO is so handy in so many instances that it's silly not to have it. And you gain performance.

raganwald 15y ago
Why is there even an argument about this? Not being able to make a recursive call without potentially blowing the stack is a major drawback in any language. I'd venture to say it's a "bug.” You aren’t going to like Python: I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool. http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi... (I’m not advocating this view, just pointing out that there are programmers who appear in all other respects to be reasonable, intelligent, contributing members of computing society who actually feel that TCO is a bug, that 1000 calls ought to be enough for anybody, and so forth.)
- drblast 15y ago
  I don't like this in a lot of languages. But it's not a showstopper, just an annoyance to be aware of. That said, there should be no reason not to have your new modern programming language support tail calls. It's short-sighted, and can negatively affect more than just the trivial recursive case. So, new programming language inventors, if you're reading this, support tail call optimization and proper tail recursion from the beginning. Your language will be better for it.
  - bascule 15y ago
    > there should be no reason not to have your new modern programming language support tail calls There's many valid reasons not to support TCO. The first one that comes to mind: it makes generating stack traces more difficult. Another reason: the JVM doesn't natively support TCO. This means to implement it you'll either need to use a trampoline (e.g. Erjang) or convert recursion to iteration (e.g. Clojure) The latter isn't too difficult, but when tail recursion merely provides an alternate syntax for iteration, and mutual tail recall recursion isn't supported, is there really as much of a point if your language is something like Ruby and already provides multiple means of iteration?