3 ms·

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

• gpm 12d 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 https://github.com/rust-lang/rust/issues/112788 [2] https://github.com/rust-lang/rust/issues/153827 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 12d 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 12d 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.
      • lioeters 12d ago
        I see it, certain algorithms need guaranteed tail-call elimination, otherwise they are too inefficient and must be manually unrolled or rewritten to avoid blowing the stack. So a compiler optimization that is "nice to have" is not good enough.
        • clhodapp 11d ago
          No algorithm requires tail-call elimination in a general-purpose language with imperative mutability. It's just another way to express iteration.
          • spider-mario 11d ago
            Sure, but mutual recursion might require `goto` for example. Or an explicit state machine.
            • clhodapp 11d ago
              I can see how it might require an explicit state machine (keep a mutable state number and switch over the inlined bodies of what could be functions), but I'm not seeing how it could require `goto`. Are there more-complex relationships that might require it?
              • spider-mario 11d ago
                I meant it more in the sense that “you need one or the other” rather than “some cases require one and some other cases require the other”.
  • jmalicki 11d 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.
    • gpm 11d ago
      Uh, yes, if you guarantee the semantics only when the code explicitly opts in and not by default then semantics will not subtly change, that is the point of my comment
      • jmalicki 11d ago
        It's not a change in semantics of compiled code. It is only a change of whether or not the code will compile.
        • gpm 11d ago
          Guaranteeing an optimization that otherwise only might run is a change in semantics. The attribute doesn't allow (in any sensible language) the code to simply not compile because the optimizer doesn't feel like it today (or you compiled with -O0), it forces the compiler to not allocate a stack frame wherever the code fits the structure that makes that definitely possible and fails to compile wherever it doesn't (even if after other optimization passes it happens to fit a structure that makes it possible).
    • afdbcreid 11d ago
      Incorrect. `become` does change drop order - https://play.rust-lang.org/?version=nightly&mode=debug&edition=2024&gist=fc0fccce5f43ff4605e08b351e4d98a9 https://play.rust-lang.org/?version=nightly&mode=debug&editi....
      • jmalicki 11d ago
        That's not implementing tail calls breaks things, that's bad design of implementing tail calls breaking things. The whole idea of "let's change semantics to make it easier" is dumb. If you want guaranteed tail calls, change your code until it works.
• IshKebab 12d ago
  Do any widely used languages guarantee tail call optimization? It's a pretty niche feature.
  • gpm 12d ago
    Scala, ocaml, racket, clojure, zig. For recursion only kotlin. (For most of these only with syntax specifying it)
    • lioeters 11d ago
      How interesting. I'd seen LISP(y) implementations like Scheme guarantee tail-call since recursion is a very common technique in that language family. But I didn't know Zig supported it. https://ziglang.org/documentation/master/#call https://ziglang.org/documentation/master/#call They have an @call built-in that guarantees: always/never tail, as well as always/never inline. That's neat, I can see how that would be useful in various situations.
    • chuckadams 10d ago
      JavaScript too, but only implemented in JavaScriptCore, so basically just Safari and Bun.
  • deleted 11d ago
    [deleted]
  • pjmlp 11d ago
    Depends on how widely we consider Scheme and Raket adoption in CS curriculum.
• shiomiru 11d 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.
  • tosti 10d ago
    So it's enumerating all the subdirectories first and unlinks the tree afterwards? I get that this isn't transactional and inherently prone to race conditions, but if this is indeed the problem, it's rediculous. A single while loop could do the job correctly and use less RAM. It'd probably also be faster. But that wouldn't be a rusty thing to do? I look at code from the heirloom project and, despite its warts, I think we've lost something in the past 45 years or so.
    • shiomiru 9d ago
      > A single while loop could do the job correctly and use less RAM. It'd probably also be faster. But that wouldn't be a rusty thing to do? No, the "single while loop" is just harder to implement than a naive recursion, because recursion is a natural way to implement tree traversal. With a while loop, you need an explicit stack, which is more complex. (A stackless traversal seems unrealistic here, as getting the succeeding node would be too expensive. Not that I've tried...) > I look at code from the heirloom project and, despite its warts, I think we've lost something in the past 45 years or so. I've just tried and heirloom rm segfaults on the same test too. Which is no wonder, seeing how that code also recurses. (It's mentioned somewhere else in the thread, but this is exactly the reason why GNU had to specify "no hard limits" as a policy. Unix used to be full of such bugs.)
      • tosti 8d ago
        Thank you for clearing that up. Good points!