When will Rust have TCO/TCE?

help
1

I know Rust has had some RFCs about the subject. I know there is even a reserved keyword become for explicit tail call elimination. However, the implementation of TCO/TCE seems to be held back. I have read some topics and I understood Rust does not have TCE because of calling conventions. Wouldn't LLVM's tail call instruction solve this?

I have to confess reading "functional features" in descriptions about Rust while Rust not having proper recursion support makes me sad.

EDIT:

Wouldn't LLVM's tail call instruction solve this?

I have been reading. No. In fact, it is the cause of limitation. Still, there should be a way of making unbounded tail recursion.

2 Likes
2

I think the main reason there hasn't been a big push for tail call optimisation is just Rust's iterators are already really well designed, and most places you'd typically use recursion in a functional language can be written using iterators just as easily.

My interpretation of "functional features" is that Rust feels very much like a functional language (i.e. functions as first-class citizens and ubiquitous use of higher-order functions like map) and it lets you express yourself using a functional style when you want to. Whether TCO is a fundamental part of being "functional" is more of a philosophical argument though.

If you feel like the Rust language would benefit from having native support for tail call optimisation, then there's no reason why you can't revisit an old RFC (or write your own) and champion the feature. You may get more feedback on the internals forum, seeing as most discussion on the actual language and toolchain takes place there.

4 Likes
3

This won't help for general tail calls, but if you can just use tail recursion, you can use a combinator:

pub fn factorial(x: usize) -> usize {
    tail_recurse((x, 1), |(a, b)| {
        if a == 0 { RecursionResult::Return(b) }
        else { RecursionResult::Continue((a - 1, a * b)) }
    })
}

Amusingly, that actually generates better code than (1..=x).product() :laughing:

15 Likes
4

one of the reasons why rust could not support tail calls is that a main target , wasm , did not support them which will soon change

5

I actually have wrote a trampoline some time ago. However, I used thunks and I don't feel good writing code using that. In both cases the result is pretty verbose.

The problem with your example is that it does not work with mutual tail recursion, which is the main reason for us to have TCO. I think the only way of handling this is using thunks. Also, converting manually simple recursion into a loop has a pretty readable result, but converting mutual recursion to a loop leads us to a very-big-hard-to-read single function.

1 Like
6

Iterators can handle only simple recursion. It is harder to convert mutual recursion into an iterator.

Converting manually simple recursion into a loop has a pretty readable result, but converting mutual recursion to a loop leads us to a very-big-hard-to-read single function.

7

I am moving this thread to internals.

8

f in tail_recurse doesn't need to be mutable.

9

Please don't revive year old threads, especially for such a small change

f does have to be mutable, because you need to get an exclusive reference to call FnMut(...) -> ..., and that requires f to be mutable.

2 Likes
10

This topic was automatically closed after 3 days. We invite you to open a new topic if you have further questions or comments.