Rust will likely not support tail call optimization

https://mail.mozilla.org/pipermail/rust-dev/2013-April/003557.html

by steveklabnik • 13 years ago

157 152 13 years ago

mail.mozilla.org

pcwalton9• 13 years ago

Note that we do sibling call optimization per LLVM, and you can use trampolines like Clojure does. Sibling call optimization, most notably, includes all self-calls. This means that calls to the currently executing function in tail position will be tail call optimized, if there are no destructors in scope.

The biggest problem here is ABIs: you have to use Pascal calling conventions instead of C calling conventions. It's also difficult when you have destructors: there are not many tail call positions when destructors are in scope.

tsewlliw2• 13 years ago

I'd vote getting to use RAII is a better win than TCO.

And really its by definition not a tail call when you have to run destructors after a "tail" call, and tricky/annoying to express that destructors should be run prior to a tail call.

edwintorok• 13 years ago

How about the other two calling conventions that support tail call optimization? (cc 10 and cc11) Do those have the same performance penalty as fastcall + tailcallopt?

masklinn• 13 years ago

Wouldn't it be possible to have some sort of macro able to "manually" convert calls in a recursive style into loops? Something along the lines of Clojure's `loop/recur` but less tricky (and maybe with a single "word")?

pcwalton9• 13 years ago

Yes, I think so.

ufo2• 13 years ago

Self recursion is only a particular case and you can often represent it with loops or folding patterns as you are imagining. However, the really cool use for tail call elimination is when you are calling other functions since you can't rewrite the code without breaking encapsulation. Out of the top of my head, one important example of this would be continuation passing style (you need TCO to turn the continuations into real "gotos")

gngeal2• 13 years ago

That would be useless. I believe the point of proper tail calls is that the set of functions that may be called from a particular call site is not closed. The callee may be a parameter of the caller, for example in combinator-style libraries. You can't convert that in advance.

protomyth• 13 years ago

It seems like part of decision was reached because of limitations in LLVM[1]. This makes me a bit uneasy, but I guess it has to follow C to meet its goals.

1) "LLVM does support tail call optimization, but it requires using a different calling convention than C and slowing down all function calls" from https://mail.mozilla.org/pipermail/rust-dev/2013-April/00355... and http://llvm.org/docs/CodeGenerator.html#tail-call-optimizati...

cwzwarich2• 13 years ago

They could also add their own calling convention to LLVM to support what they want like GHC and HiPE have done.

saidajigumi• 13 years ago

No they can't, at least not without compromising on several points laid out in TFA. Mainly these two:

    - 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.

See other posts in this discussion for examples of the impacts of some alternate calling convention choices.

anonymous• 13 years ago

Then how can GCC and clang do TCE in C programs?

aidenn0• 13 years ago

1) They can't do it all the time

2) Some of the times they can do it, they do it when they control both the caller and the callee. In that case you can violate the ABI to your heart's content.

3) I don't really see TCE as an issue in Rust, since they seem to be going the RAII route and, as others have commented, RAII and TCE don't play well together (for the same reason a call at the end of a dynamic binding can't be TCE'd in common-lisp).

dewitt2• 13 years ago

Clojure also doesn't support TCO, and from what I can tell the explicit loop/recur is sufficient, which also has the advantage that it is very clear (i.e., the compiler will tell you) when TCO is not being invoked. With implicit TCO you might think you're getting the benefit, only to have a stack blow up unexpectedly at runtime with an edge-case input.

pcwalton9• 13 years ago

Especially with destructors. Whenever you have a destructor in the frame, you're not in tail-call position. This means that tail-call positions in Rust are going to be few anyway.

cpeterso2• 13 years ago

Does this mean Rust's `be` keyword can be retired? :)

qznc5• 13 years ago

That calls for an interesting optimization: Using escape+liveness analysis you could probably call some of those destructors earlier.

kvb2• 13 years ago

Doesn't loop/recur only help in directly self-recursive calls, as opposed to mutual recursion or tail calls to function arguments?

anonymoushn• 13 years ago

That's correct. It should be possible to have an explicit guarantee of TCO while maintaining the ability to write things that aren't trivially reducible to loops...

dewitt2• 13 years ago

Right. In Clojure you'd use an explicit trampoline for stack-free mutual recursion.

pekk• 13 years ago

I'm puzzled: if Rust and Clojure won't support TCO and they are both cool, why is there such bitter complaining every time it comes up that Python won't support TCO?

kyllo• 13 years ago

Because Rust and Clojure have have better excuses, maybe?

Rust is supposed to be as fast as C/C++ and TCO will slow it down.

Clojure can't have TCO because the Java Virtual Machine doesn't support it. So they have a workaround (trampolines).

Python doesn't support TCO because... it screws up stack traces?

Rickasaurus8• 13 years ago

We'll just have to put Rust up against MLton and see if tail calls really are so expensive.

groovy2shoes• 13 years ago

> Rust is supposed to be as fast as C/C++ and TCO will slow it down.

TCO doesn't slow programs down. If anything, it might even make them a tiny bit faster. But speed isn't the reason you'd want TCO: you want it as a stack optimization so that tail-recursive functions use constant stack space. Furthermore, although the C specification places no TCO requirement on implementors, it's actually a very reasonable optimization even in C. GCC actually does do TCO in some cases (I'm using 4.5.3, and tail-call elimination occurs with -O2 and higher).

> Clojure can't have TCO because the Java Virtual Machine doesn't support it. So they have a workaround (trampolines).

This is true. There was a time when TCO support was slated for Java 7. That time has come and gone; unofficially, it looks like it may make an appearance in Java 9 at the earliest.

> Python doesn't support TCO because... it screws up stack traces?

That's the cited reason, but it's horseshit. As others have pointed out on this thread, it's feasible to simply disable TCO when doing debugging if you need a stack trace. Even fancier, there are algorithms to recover the stack even after the calls have been eliminated (see Lua for example).

mcguire• 13 years ago

Well, technically, "it screws up stack traces" is the usual excuse given for why the JVM doesn't support it.

andolanra3• 13 years ago

I can't speak for Clojure, but Rust's rationale for omitting TCO is based on sound engineering issues (as articulated) whereas Guido's sole reason for omitting it (as far as I've seen) is that you lose stack trace information, which is considered something of a red herring (as you can always selectively disable TCO for debugging, and there are ways of retaining stack information anyway.) Note that the original article here is quite disappointed that they can't include TCO, because it would be a valuable tool and allow for different, efficient styles of programming.

tsewlliw2• 13 years ago

Amusingly, "losing stack trace information" is among the reasons the JVM doesn't do TCO -- it needs to keep it around for the security manager to do its thing. Its especially annoying there because references are held by higher stack frames and prevent GC, and the destructor excuse isn't present.

rit• 13 years ago

I can't answer fully for Clojure's reasons for not supporting TCO, but it will at least be fundamentally rooted in the fact that the JVM, as a platform, does NOT support TCO.

Scala is usually the language brought up as a counter argument here, but Scala has the same limitations as Clojure - the JVM can't do the TCO. Scala's compiler tries, with certain types of tail calls, to optimize via (I believe) a trampoline – it reduces those calls into a loop, so they are no longer a function call.

But, only certain types of calls (specifically, the last line of code in a recursive function must be a call to the hosting function) can be TCO in Scala. There is an annotation, scala.annotation.tailrec, which can be placed above a method you want to tail recurse.

@tailrec does not, however, "force" the compiler to do TCO – it simply forces compilation to fail if the method in question cannot be Tail Call Optimized. It's a developer hook for saying "I realize the compiler tries to do TCO where possible, but I require this method to be trampolined". If it can't be, you'll get a compilation error with details on why the TCO failed.

bcoates3• 13 years ago

A debugging switch that, when enabled, turns a valid program into an invalid one is madness.

Python has decided to place very conservative requirements on what an implementation's stack must be capable of. This might indicate a certain lack of ambition but it's a justifiable engineering tradeoff.

papsosouid• 13 years ago

Who says they are both cool? HN isn't a single person. It is quite possible that group A thinks rust and clojure are "cool", and group B thinks that languages without TCO (including python, clojure and rust) are bad.

kragen19• 13 years ago

I imagine the same people who complain about lack of TCO in Python are also complaining about lack of TCO in rust and Clojure.

TheCoelacanth• 13 years ago

Python doesn't optimize any tail calls at all. Rust optimizes sibling calls, which includes all self-tail calls. It's only tail calls to a different function that Rust doesn't eliminate.

btipling• 13 years ago

What is tail call optimization? How does it usually work? There's an implementation example on the Wikipedia page to answer this question a little bit:

http://en.wikipedia.org/wiki/Tail_call

arb99• 13 years ago

also http://stackoverflow.com/questions/310974/what-is-tail-call-... gives a decent overview

ericbb2• 13 years ago

And, of course, "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO" by Guy Steele. Available here: http://library.readscheme.org/page1.html

Rickasaurus8• 13 years ago

Screw it, we might as well use Go

Seriously though, why not just use a rec keyword and then disallow any of the things that don't play nicely when you're in the recursive function? If you really wanted to be cool you could put those things right into the type system.

coldtea3• 13 years ago

They don't want to be cool. They want to create a usable, pragmatic and fast language.

Rickasaurus8• 13 years ago

Sounds mostly like a pile of empty words to me. Usable and pragmatic are purely contextual. Is rust faster than Haskell?

nnq• 13 years ago

at what point did people start to use the word "pragmatic" for "opinionated"? (and I've heard it a lot lately...) I'm ok with opinionated technologies, but stop calling them "pragmatic": when the implementer of a language or technology makes a choice that restricts how its users can do some things, it makes an opinionated decision, that just happens to be pragmatic in the use-context he has thought of, but may not be pragmatic at all for the use-context that some technology user imagines, like a language feature that may be hard-to-impossible to implement but that when done properly (and it only has to be done once) would simplify the lives of a large group of programmers that just want to do things in a certain way.

cpeterso2• 13 years ago

Rust has/had a `be` keyword reserved for potentially implementing TCO.

ufo2• 13 years ago

As they mentioned in the original post, a big problem is that TCO does not play nice with two other important features they want.

1. deterministic destructors that run at the end of functions (therefore making things that look like tail calls not actually tail calls) and

2. binary compatibility with C and C++ libraries and tools (they say that tail recursion doesn't let you usethe C calling conventions that these tools and libraries expect you to use)

There is no point in allowing tail recursion in restricted contexts if you can't use these restricted functions to do the sort of stuff Rust was actually made to do

ihnorton4• 13 years ago

> binary compatibility with C and C++ libraries and tools >(they say that tail recursion doesn't let you use the C > calling conventions that these tools and libraries expect > you to use)

I've read variations of this comment about Rust C++ compatibility a few times, but haven't managed to find a source. Any references you could point me to?

derefr3• 13 years ago

> 1. deterministic destructors that run at the end of functions (therefore making things that look like tail calls not actually tail calls) and

Couldn't owned boxes (~) passed through the jump transfer their ownership to the next frame (so they'll be destructed by whoever finally does return), and everything else just get destructed before the jump?

mike_ivanov• 13 years ago

A TCO-support discussion on Y combinator.

OH IRONY.

zxcdw• 13 years ago

Elaborate for the ignorant.

kd0amg• 13 years ago

The Y combinator is a way to express recursion in lambda calculus. Tail call optimization (turning certain function calls into GOTOs) is the traditional way to keep from overflowing the control stack in languages based on lambda calculus.

qznc5• 13 years ago

The Y Combinator is something important in the theory of functional programming. It takes one function as argument and applies it to itself ad infinitum. Together with lazy evaluation this is how you can implement recursion in a language which does not natively support it, namely (lazy) lambda calculus.

http://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combin...

Actually, TCO and Y are not really related with each other apart from the fact that you usually learn about them in the same course about functional programming.

beagle32• 13 years ago

Please, for the sake of $DIETY, stop calling it "Tail Call Optimization". It is not an optimization, and the wrong term causes lots of useless discussions and misunderstanding. Call it "Tail Call Elimination", because that's what it is.

With finite memory (that is, in the real world), a program that relies on tail recursion will blow up if TCE is not implemented even though it can run forever with TCE. Thus, it changes actual program results (rather than just runtime speed or amount of memory required), and cannot be considered just an "optimization", since it is functionally required.

And to future-language designers: Please, for the sake of $DIETY2, make the syntax for guaranteed-eliminated-tail-call different than a regular call: It's really a bad idea that a function such as:

    def f(x):
       ...
       return 0+f(x-1)

cannot in general be TCEd (adding 0 to a floating point imporper denormal will make it proper), whereas

     def f(x):
        ...
        return f(x-1)

can. I suggest "chain y" instead of "return y" so that the compiler can verify that a TCE can indeed happen.

gngeal2• 13 years ago

"Please, for the sake of $DIETY"

If you worship food, that is. But you're right, people calling proper tail calls "an optimization" should be shot. Those who survive the subsequent generation scavenging should be shot again. :-)

kibwen4• 13 years ago

As a historical note, this was also the original plan for Rust, where the presence of the `be` keyword rather than the `return` keyword would indicate tail-calling.

millstone• 13 years ago

cannot be considered just an "optimization", since it is functionally required

Here is a C program:

    #include <stdio.h>
    int main(void) { while (1) malloc(64); }

With clang, when compiled with -O0, this consumes all the memory on my system. When compiled with -O2, it runs forever in constant memory, because clang has optimized out the call to malloc. If I replace the call with, say, 'malloc((size_t)(-1) >> 1)', it even changes the output of the program.

Here is another example:

    int factorial(long long x) { return x * factorial(x-1); }

With gcc, when compiled with -O2, the factorial function can correctly compute the factorial of a very large number. When compiled with -O0, it cannot.

I would call both of these optimizations, even though someone may rely on either for correctness. So I don't think tail calls are unique in this respect.

make the syntax for guaranteed-eliminated-tail-call different than a regular call

Agreed.

kragen19• 13 years ago

The reason people are so interested in TCO/TCE is not just that someone might rely on them for correctness, which as you point out is true of any optimization, but rather that they are so predictable that you can omit looping constructs from your core language if you have them.

baddox• 13 years ago

In the finite world beagle3 talks about, don't all optimizations potentially qualify as "functionally required"? If the finite world you're operating in can only run a program that requires at most N steps ("steps" being deliberately vague "computing resources," like CPU cycles or memory usage), then any optimization that makes an (N+1)-step program complete in N steps qualifies as a "functional requirement."

bcoates3• 13 years ago

Both of those programs are playing with C's infamously broad undefined behavior rules, the first for a non-terminating loop and the second for using too much stack (when called with a sufficiently large number). -O2 being nice to you is a coincidence, not something you should rely on.

In a language which prefers diagnosing programmer error over punting both should be errors.

beagle32• 13 years ago

> even though someone may rely on either for correctness.

That someone is playing with fire. It's the kind of optimization that might be removed in a hotfix because it turns out to break something else.

It's even worse than relying on things like byte order -- and if you rely on them, you are definitely outside the realm of "C language", and into the realm of "Specifically LLVM v.37x patchlevel 2, on an SSE4 architecture"

ericbb2• 13 years ago

Or follow Alef (http://www.cs.bell-labs.com/who/rsc/thread/ug.pdf) and use "become". The Alef become statement is a kind of generalized tail-call form because you can use it to drop the current stack frame from anywhere, not just in tail-position.

kragen19• 13 years ago

I suggest "chain y" instead of "return y" so that the compiler can verify that a TCE can indeed happen.

I think the rust syntax for this was `be y` instead of `return y`.

srean• 13 years ago

If I remember correctly the new version of TCL will have special syntax to enforce TCE. Unfortunately I did not book mark the relevant online discussion.

jevinskie2• 13 years ago

Here is some information about TCE in LLVM from the lead developer: http://nondot.org/sabre/LLVMNotes/GuaranteedEfficientTailCal...

asbut• 13 years ago

The problem seems to be that you can't do tail calls with the C calling convention.

For example, let's say a 0-argument function tail calls a 1-argument one: the 1-argument function expects an argument on the stack, so the 0-argument function must push one.

However, when the 1-argument function returns, the argument will still be on the stack, because with the C calling convention the caller removes arguments from the stack.

But the caller called a 0-argument function, so he won't remove any argument, and thus the stack is now misaligned due to the argument left over there, which will crash the program soon.

However, just switching to the Pascal/stdcall convention, where the callee removes arguments from the stack should just work; it might be slightly slower, but on all modern architectures (i.e. those that aren't x86-32) parameters are going to be passed in registers anyway for must functions, so it shouldn't matter.

The problem of that is that non-varags functions cannot be called with a varargs prototype; this is an issue with K&R C that allows calling undeclared functions, but isn't an issue with Rust.

So, I'm not quite sure why Rust doesn't just switch calling conventions and support tail calls.

Rust will likely not support tail call optimization

Related Stories