logoalt Hacker News

tosti • yesterday at 4:57 PM • 3 replies • view on HN

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

Replies

gpm • yesterday at 5:40 PM

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.

➕ show 2 replies
shiomiru • today at 8:38 AM

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 • yesterday at 9:05 PM

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

➕ show 1 reply