← Back to context

Comment by tosti

19 hours ago

OIC. Rust doesn't guarantee optimizing tail recursion. How unfortunate for a language that's getting widespread adoption.

18 comments

tosti

Reply
gpm  18 hours ago

For what it's worth there's reasonably active [1] work on implementing opt-in guaranteed tail calls - but it's not particularly fast going. LLVM (the backend rust uses) needs better support for musttail (e.g. some architectures just don't support it [2]).

[1] https://github.com/rust-lang/rust/issues/112788

[2] https://github.com/rust-lang/rust/issues/153827

By-default guaranteed tail calls really isn't rust's style, because it means subtle changes (introducing a destructor, re-ordering code, etc) can change semantics without you realizing it. If you want to guarantee that a call can't allocate a new stack frame you should have to say it.

  • lioeters  18 hours ago

    Not so familiar with this area, but isn't the existing behavior of implicitly creating new stacks more of a problem than implicit tail-call elimination? Seems the latter is a kind of compiler-level optimization, of which there are already many (I think) that change the semantics internally but guarantee the outward behavior stays the same.

    But I can understand the preference for an explicit opt-in, to make clear that it is enforced and not assumed.

    • gpm  18 hours ago

      > implicitly creating new stacks

      I'd argue that it's explicit - that's what a function call does and you don't have implicit function calls in rust.

      > Seems the latter is a kind of compiler-level optimization, of which there are already many (I think) that change the semantics internally but guarantee the outward behavior stays the same.

      What you're asking for here already exists. Tail calls might be optimized into not allocating extra stack frames, the rust compiler just doesn't guarantee that it will perform that optimization (and almost certainly won't when code is compiled without optimizations... for instance).

      What people want is the semantic guarantee that the stack frame won't be allocated. Not just a compiler that often performs the optimization. Otherwise you can't be sure that your code will keep working with new compiler flags/versions/architectures/... You could say "whenever the code is the right shape we'll guarantee the optimization" (C++ famously did this for things like copy elision)... but now the shape of code comes with non-obvious semantic guarantees and that's not rust's style. Hence the proposal for a keyword instead.

      5 replies →

  • jmalicki  9 hours ago

    > because it means subtle changes (introducing a destructor, re-ordering code, etc) can change semantics without you realizing it.

    No, it won't change semantics - if you say @musttail or similar, it will simply fail to compile if you, say, introduce a destructor - the semantics will not subtly change.

shiomiru  3 hours ago

I don't think that's related? The bug alluded to looks something like

    function rm(node) {
        for (const child of ls(node))
            rm(child);
        unlink(node);
    }

and no amount of tail call optimization will save you here, because this isn't tail recursion. Of course you could rewrite it using an explicit stack + tail recursion, but then you might as well be using a while loop.

IshKebab  15 hours ago

Do any widely used languages guarantee tail call optimization? It's a pretty niche feature.

  • gpm  15 hours ago

    Scala, ocaml, racket, clojure, zig.

    For recursion only kotlin.

    (For most of these only with syntax specifying it)