8 ms·

Why Object-Oriented Languages Need Tail Calls (2011)

53 points by tonyg 9y ago

btilly 9y ago
This is an old debate. On the one hand with tail calls you can write recursive code and find that it runs fast without excessive memory. On the other hand when things blow up, it is really nice to have a stack backtrace to help debug why it blew up. But a stack backtrace can't include stack frames that were optimized away. Which makes it far harder to figure out why this call on this object turned into that call on that object.
- dualogy 9y ago
  Probably could be a user option in compilers for debug builds to either disable TCO or include "faked stack" in the tco-generated loop --- in many-maybe-most cases, wouldn't a cleanly recursive stack trace just consist of ever-the-same-callee repeated a gazillion times? Not all and not the more intricate scenarios of course.
  - pdpi 9y ago
    TCO also applies when you have multiple levels of indirection between the caller and the ultimate callee that actually responds to the request.
- steego 9y ago
  > On the other hand when things blow up, it is really nice to have a stack backtrace to help debug why it blew up. But a stack backtrace can't include stack frames that were optimized away. Which makes it far harder to figure out why this call on this object turned into that call on that object. Is that really a concern? If you're writing a loop, do you expect your tools to show you a trace of every iteration in the loop? Of course not, because that would be silly. If you really want to trace each iteration, you can add your own tracing. I think of tail-recursion as parameterized gotos that are wonderfully constrained and are useful for describing state transformations in a predictable way. It's not a regular function call, so the stack trace is probably a very bad idea.
  - tuukkah 9y ago
    Not all calls in tail position are recursive and when they are, they may be mutually recursive. This means it's not possible to detect and optimize recursive calls only.
  - bunderbunder 9y ago
    I think it probably depends on how you think of the abstraction. Everyone readily thinks of loops, in the abstract, as "GOTO line X and do everything over again, but using all the state that has changed since the last time we were at line X." Ideally, you can think of recursion as nearly the same thing: "GOTO line X and do this stuff again, but using these very clearly stated changes to the data." If you think of recursion that way, then it's fairly self-evidently easier to reason about. In practice, though, I've met few developers who think that way and haven't spent significant time doing functional programming. I'm guessing it's because you need to spend a fair bit of time with both abstractions before you can really grok either of them. Without that, they're just kind of intimidating. Recursion more so, because everyone's taught from a young age to think imperatively.
  - sbmassey 9y ago
    Tail recursion optimisation gets rid of all tail calls in functions, not just those that might lead to loops - you cannot in general detect those calls that might be loops. This can put a lot of holes in your stack trace.
    - willtim 9y ago
      It's an optimisation. It can be turned off when debugging with stack traces. If you need stack traces in production code, you have too many partial functions.
      - Rusky 9y ago
        But you can't ever turn it off if you rely on it for loops, which defeats the whole point.
- tsuraan 9y ago
  GHC does non-strict evaluation as well as tail call optimization, and it offers pretty decent stack traces. The team that implemented them wrote a paper on how they did it, including how they fold mutually recursive calls in the call stack representation so that a normal Haskell program won't cause unbounded growth of the stack representation: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/DebugTraces.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... I wouldn't expect the same from an OO language, but I'm not sure that it's impossible either.
- goialoq 9y ago
  The OP addresses that concern with a link to https://www2.ccs.neu.edu/racket/pubs/cf-toplas04.pdf https://www2.ccs.neu.edu/racket/pubs/cf-toplas04.pdf
  - btilly 9y ago
    That is a different concern. That paper is about implementing security models based on what is supposed to be in the stack. My concern is about emitting a debugging stack backtrace on error. If you are concerned with a security model, it is nice to know that you can remove the stack and prove that the security model is satisfied. But you can't provide a programmer with a record of stack frames that you do not have.
rbehrends 9y ago
There are a number of problems with this argument, but the biggest one is that most such calls will not actually be tail-recursive. The very specific `adjoin` example that has been provided only works with `contains` not being in a tail position because `or` is assumed to use short-circuit evaluation, and because the author is apparently willing to live with a set membership test that has linear time complexity. We can see that the `contains` method for `UnionObject` is not tail-recursive, for example, no matter how you cut it. The primes example effectively constructs a linked list with 78,498 elements; any unsuccessful search will iterate over all those elements, and successful searches will (depending on how the search arguments are distributed) also easily traverse tens of thousands of elements. Handwaving performance issues away with "we know lots of ways this code can be optimized, but let us please focus on the behavior of the constructed set" is wrong, simply because efficient and actually usable implementations may exhibit totally different requirements w.r.t. tail recursion and what should be in an interface.
- phkahler 9y ago
  "is wrong, simply because efficient and actually usable implementations may exhibit totally different requirements w.r.t. tail recursion and what should be in an interface." Thank you so much for that!
jacinabox 9y ago
They don't need tail calls, unless you're planning on doing idiomatic functional programming in an OO language, which, Why??
- FascinatedBox 9y ago
  Some languages, such as Scala, have a mix of FP and OO concepts. Some FP features make use of TCO, so this helps to make them a first class citizen.
- samth 9y ago
  The answer to your question is the entire point of the blog post, which was written by Guy Steele, who worked on the original design of Java.
- pjmlp 9y ago
  Smalltalk, the grandaddy of OOP languages uses idiomatic functional programming for its messages.
- jacinabox 9y ago
  Oh yes, my mistake.
mikeash 9y ago
Why don't languages give tail calls their own syntax rather than making it an optimization? It seems like a lot of the arguments against tail calls boil down either 1) it's confusing when things go wrong and you weren't expecting stack frames to be optimized out or 2) it's hard to safely write tail-recursive code because a small change to the code or, worse, the compiler settings can make it stop being tail-recursive. If you had to explicitly request it, say by doing `tailcall f()` instead of just `f()`, that would mostly fix these problems. Control flow will be a lot less confusing since it'll be explicit in the code (but you still lose information from the optimized-out stack frames, no way around that) and you'll get an explicit error if someone tries to add something that can no longer be tail call optimized, like `tailcall f() + 1`.
- catnaroek 9y ago
  I understand the case for adding O(1) overhead for the sake of debuggability, but not having proper tail calls (it's not an optimization, goddammit) is way more than O(1) overhead.
- cr__ 9y ago
  This is how Clojure does it. https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/trampoline https://clojuredocs.org/clojure.core/trampoline
  - mikeash 9y ago
    Nice. When I wrote that, I was sure there would be some language that had already done it, and I was about 90% sure it would be some sort of Lisp.
    - andreasgonewild 9y ago
      That, or some sort of Forth; the separate keyword also enables calling anonymous functions recursively: https://github.com/andreas-gone-wild/snackis/blob/master/snabel.md#lambdas https://github.com/andreas-gone-wild/snackis/blob/master/sna...
phkahler 9y ago
I'm not a fan of this style of coding. It's not just the stack space. When you call methods all over the place it can result in inefficient code. And yes, I understand that I wrote "can" in that sentence. We're talking about a case where the author wants the compiler to be even smarter than it already is. I guess that's my point. Using these kinds of abstractions results in a reliance on the compiler to make things efficient. OTOH using abstractions can make things simpler and more understandable for the programmer. But there's that word "can" again.
pmontra 9y ago
Ruby's got TCO since 1.9 but it must be enabled at runtime in a pretty ugly way [1]. I'm also working on Elixir which has TCO and it's the basis for running server processes: the server function calls itself passing the server state as argument. I don't see why OO languages shouldn't do the same. The argument about losing the stack trace is pretty weak. Nobody wants a million stack frames to debug. If the program dies we check the last values of the variables and that's it. [1] http://rpanachi.com/2016/05/30/ruby-recursion-stack-size-tail-call-optimization http://rpanachi.com/2016/05/30/ruby-recursion-stack-size-tai...
- rurban 9y ago
  Yes. The same argument can be made against fork(), that fork makes debugging too hard. And we don't know if the value we want to inspect is a common one (before cow) or an already copied. So do we forbid fork()?
cryptonector 9y ago
One would think that by now tail call optimization (TCO) would be understood to be absolutely necessary. TFA makes a very good case, but it's hardly the first or only example of someone making a convincing argument for TCO. Even in jq we found that adding TCO enabled a number of interesting possibilities. For example, the range() builtin in jq can be implemented as a tail-recursive function (and the version that takes two or three arguments is). There are a number of builtins in jq 1.5 which are made possible and practical only by having TCO. Before we added TCO it just didn't seem that interesting, but it's proven to be quite an enabler. I can't think of a language that shouldn't have TCO. C/C++ absolutely should have it (and many compilers do). Java should have it (but doesn't). Lisps badly need it and generally have it -- the same goes for all functional (or mostly functional) languages. Python needs it but apparently lacks it[0]. And so on. Yes, tail calls obscure stack traces by eliding reused frames. This could be ameliorated by leaving a flag in reused frames that could be shown on stack traces to indicate that there are missing frames. Or perhaps syntactic sugar could be used to control which tail calls are to get optimized (since often it does not matter). [0] https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion/13592002#13592002 https://stackoverflow.com/questions/13591970/does-python-opt...
goialoq 9y ago
It's [2009], not [2011]. 2011 is when the current host copied the document from the archive.

53 points by tonyg 9y ago

This is an old debate. On the one hand with tail calls you can write recursive code and find that it runs fast without excessive memory. On the other hand when things blow up, it is really nice to have a stack backtrace to help debug why it blew up. But a stack backtrace can't include stack frames that were optimized away. Which makes it far harder to figure out why this call on this object turned into that call on that object.

dualogy 9y ago
Probably could be a user option in compilers for debug builds to either disable TCO or include "faked stack" in the tco-generated loop --- in many-maybe-most cases, wouldn't a cleanly recursive stack trace just consist of ever-the-same-callee repeated a gazillion times? Not all and not the more intricate scenarios of course.
- pdpi 9y ago
  TCO also applies when you have multiple levels of indirection between the caller and the ultimate callee that actually responds to the request.
steego 9y ago
> On the other hand when things blow up, it is really nice to have a stack backtrace to help debug why it blew up. But a stack backtrace can't include stack frames that were optimized away. Which makes it far harder to figure out why this call on this object turned into that call on that object. Is that really a concern? If you're writing a loop, do you expect your tools to show you a trace of every iteration in the loop? Of course not, because that would be silly. If you really want to trace each iteration, you can add your own tracing. I think of tail-recursion as parameterized gotos that are wonderfully constrained and are useful for describing state transformations in a predictable way. It's not a regular function call, so the stack trace is probably a very bad idea.
- tuukkah 9y ago
  Not all calls in tail position are recursive and when they are, they may be mutually recursive. This means it's not possible to detect and optimize recursive calls only.
- bunderbunder 9y ago
  I think it probably depends on how you think of the abstraction. Everyone readily thinks of loops, in the abstract, as "GOTO line X and do everything over again, but using all the state that has changed since the last time we were at line X." Ideally, you can think of recursion as nearly the same thing: "GOTO line X and do this stuff again, but using these very clearly stated changes to the data." If you think of recursion that way, then it's fairly self-evidently easier to reason about. In practice, though, I've met few developers who think that way and haven't spent significant time doing functional programming. I'm guessing it's because you need to spend a fair bit of time with both abstractions before you can really grok either of them. Without that, they're just kind of intimidating. Recursion more so, because everyone's taught from a young age to think imperatively.
- sbmassey 9y ago
  Tail recursion optimisation gets rid of all tail calls in functions, not just those that might lead to loops - you cannot in general detect those calls that might be loops. This can put a lot of holes in your stack trace.
  - willtim 9y ago
    It's an optimisation. It can be turned off when debugging with stack traces. If you need stack traces in production code, you have too many partial functions.
    - Rusky 9y ago
      But you can't ever turn it off if you rely on it for loops, which defeats the whole point.
tsuraan 9y ago
GHC does non-strict evaluation as well as tail call optimization, and it offers pretty decent stack traces. The team that implemented them wrote a paper on how they did it, including how they fold mutually recursive calls in the call stack representation so that a normal Haskell program won't cause unbounded growth of the stack representation: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/DebugTraces.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/... I wouldn't expect the same from an OO language, but I'm not sure that it's impossible either.
goialoq 9y ago
The OP addresses that concern with a link to https://www2.ccs.neu.edu/racket/pubs/cf-toplas04.pdf https://www2.ccs.neu.edu/racket/pubs/cf-toplas04.pdf
- btilly 9y ago
  That is a different concern. That paper is about implementing security models based on what is supposed to be in the stack. My concern is about emitting a debugging stack backtrace on error. If you are concerned with a security model, it is nice to know that you can remove the stack and prove that the security model is satisfied. But you can't provide a programmer with a record of stack frames that you do not have.

rbehrends 9y ago

There are a number of problems with this argument, but the biggest one is that most such calls will not actually be tail-recursive. The very specific `adjoin` example that has been provided only works with `contains` not being in a tail position because `or` is assumed to use short-circuit evaluation, and because the author is apparently willing to live with a set membership test that has linear time complexity. We can see that the `contains` method for `UnionObject` is not tail-recursive, for example, no matter how you cut it. The primes example effectively constructs a linked list with 78,498 elements; any unsuccessful search will iterate over all those elements, and successful searches will (depending on how the search arguments are distributed) also easily traverse tens of thousands of elements. Handwaving performance issues away with "we know lots of ways this code can be optimized, but let us please focus on the behavior of the constructed set" is wrong, simply because efficient and actually usable implementations may exhibit totally different requirements w.r.t. tail recursion and what should be in an interface.

phkahler 9y ago
"is wrong, simply because efficient and actually usable implementations may exhibit totally different requirements w.r.t. tail recursion and what should be in an interface." Thank you so much for that!

jacinabox 9y ago

They don't need tail calls, unless you're planning on doing idiomatic functional programming in an OO language, which, Why??

FascinatedBox 9y ago
Some languages, such as Scala, have a mix of FP and OO concepts. Some FP features make use of TCO, so this helps to make them a first class citizen.
samth 9y ago
The answer to your question is the entire point of the blog post, which was written by Guy Steele, who worked on the original design of Java.
pjmlp 9y ago
Smalltalk, the grandaddy of OOP languages uses idiomatic functional programming for its messages.
jacinabox 9y ago
Oh yes, my mistake.

mikeash 9y ago

Why don't languages give tail calls their own syntax rather than making it an optimization? It seems like a lot of the arguments against tail calls boil down either 1) it's confusing when things go wrong and you weren't expecting stack frames to be optimized out or 2) it's hard to safely write tail-recursive code because a small change to the code or, worse, the compiler settings can make it stop being tail-recursive. If you had to explicitly request it, say by doing `tailcall f()` instead of just `f()`, that would mostly fix these problems. Control flow will be a lot less confusing since it'll be explicit in the code (but you still lose information from the optimized-out stack frames, no way around that) and you'll get an explicit error if someone tries to add something that can no longer be tail call optimized, like `tailcall f() + 1`.

catnaroek 9y ago
I understand the case for adding O(1) overhead for the sake of debuggability, but not having proper tail calls (it's not an optimization, goddammit) is way more than O(1) overhead.
cr__ 9y ago
This is how Clojure does it. https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/trampoline https://clojuredocs.org/clojure.core/trampoline
- mikeash 9y ago
  Nice. When I wrote that, I was sure there would be some language that had already done it, and I was about 90% sure it would be some sort of Lisp.
  - andreasgonewild 9y ago
    That, or some sort of Forth; the separate keyword also enables calling anonymous functions recursively: https://github.com/andreas-gone-wild/snackis/blob/master/snabel.md#lambdas https://github.com/andreas-gone-wild/snackis/blob/master/sna...

phkahler 9y ago

I'm not a fan of this style of coding. It's not just the stack space. When you call methods all over the place it can result in inefficient code. And yes, I understand that I wrote "can" in that sentence. We're talking about a case where the author wants the compiler to be even smarter than it already is. I guess that's my point. Using these kinds of abstractions results in a reliance on the compiler to make things efficient. OTOH using abstractions can make things simpler and more understandable for the programmer. But there's that word "can" again.

pmontra 9y ago

Ruby's got TCO since 1.9 but it must be enabled at runtime in a pretty ugly way [1]. I'm also working on Elixir which has TCO and it's the basis for running server processes: the server function calls itself passing the server state as argument. I don't see why OO languages shouldn't do the same. The argument about losing the stack trace is pretty weak. Nobody wants a million stack frames to debug. If the program dies we check the last values of the variables and that's it. [1] http://rpanachi.com/2016/05/30/ruby-recursion-stack-size-tail-call-optimization http://rpanachi.com/2016/05/30/ruby-recursion-stack-size-tai...

rurban 9y ago
Yes. The same argument can be made against fork(), that fork makes debugging too hard. And we don't know if the value we want to inspect is a common one (before cow) or an already copied. So do we forbid fork()?

cryptonector 9y ago

One would think that by now tail call optimization (TCO) would be understood to be absolutely necessary. TFA makes a very good case, but it's hardly the first or only example of someone making a convincing argument for TCO. Even in jq we found that adding TCO enabled a number of interesting possibilities. For example, the range() builtin in jq can be implemented as a tail-recursive function (and the version that takes two or three arguments is). There are a number of builtins in jq 1.5 which are made possible and practical only by having TCO. Before we added TCO it just didn't seem that interesting, but it's proven to be quite an enabler. I can't think of a language that shouldn't have TCO. C/C++ absolutely should have it (and many compilers do). Java should have it (but doesn't). Lisps badly need it and generally have it -- the same goes for all functional (or mostly functional) languages. Python needs it but apparently lacks it[0]. And so on. Yes, tail calls obscure stack traces by eliding reused frames. This could be ameliorated by leaving a flag in reused frames that could be shown on stack traces to indicate that there are missing frames. Or perhaps syntactic sugar could be used to control which tail calls are to get optimized (since often it does not matter). [0] https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion/13592002#13592002 https://stackoverflow.com/questions/13591970/does-python-opt...

goialoq 9y ago

It's [2009], not [2011]. 2011 is when the current host copied the document from the archive.