On 10/04/2013 5:43 AM, Artella Coding wrote:
Hi does rust do tail call optimization? The reason I am asking is that
the following tail call recursive implementation results in a stack
overflow. Thanks.
No, and it very likely won't. We have a longstanding bug on this:
https://github.com/mozilla/rust/issues/217
as well as a wiki page and several mailing list threads:
https://github.com/mozilla/rust/wiki/Bikeshed-tailcall
https://mail.mozilla.org/pipermail/rust-dev/2011-August/000689.html
https://mail.mozilla.org/pipermail/rust-dev/2012-January/001280.html
...
The summary of all this is:
- We all know that tail calls are a virtuous language feature.
Further elaboration of their virtues is not required. Many of us
have lisp and ML backgrounds and would quite like them. Their
absence is heartache and sadness, not arrived-at lightly.
- Tail calls "play badly" with deterministic destruction. Including
deterministic drop of ~ boxes. Not to say that they're not
composable, but the options for composing them are UI-awkward,
performance-penalizing, semantics-complicating or all of the above.
- Tail calls also "play badly" with assumptions in C tools, including
platform ABIs and dynamic linking.
- Tail calls require a calling convention that is a performance hit
relative to the C convention.
- We find most cases of tail _recursion_ convert reasonably well to
loops, and most cases of non-recursive tail calls encode state
machines that convert reasonably well to loops wrapped around
enums. Neither of these are _quite_ as pretty as the
tail-call-using variants, but they do work and are "as fast"*,
as well as idiomatic for C and C++ programmers (who are our
primary audience).
I'm sorry to be saying all this, and it is with a heavy heart, but we
tried and did not find a way to make the tradeoffs associated with them
sum up to an argument for inclusion in rust.
-Graydon
* speed-wise, a switch-in-a-loop state machine is indirect dispatch so
will likely run slower than a state machine encoded by tail calls from
state to state; on the other hand if the way to get this performance
"back" is to turn on tail calls everywhere, we'd be trading one isolated
suboptimal-perf case for a cross-all-programs suboptimal-perf tax. We
don't find this trade acceptable.
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
