An immutable loop structure `loop let`

language design
1

One of Rust core features is immutability. But Rust currently doesn't have an immutable loop structure, just iterator methods. My proposal is the loop let structure which sorta allow for recursion that auto unwraps into an iteration. Actually, every tail call recursive algorithm could be implemented using loop let being tail-call-optimized for free.

Idea

The loop let could be used as a looping structure that is also an expression. It has an initial value, then at the end of each iteration the developer must return the value for the next iteration or the final value of the loop expression finishing it.

loop let <pattern> = <initial-value> {
    // ...
    continue <next-iter-value>;
    // ...
    break <final-value>;
}

This syntax wouldn't add any new reserved keywords, which let's the implementation easier and not introduce any breaking change. Also it's similar to current if let and while let syntax, except it won't accept fallible patterns if used as an expression.

Also besides accepting break b and continue c statements to short-circuit an iteration, loop let could accept a value of type ControlFlow<B, C> at the end of the block where B is the output type (type of the loop let when used as an expression) and C is the input type (type of the initial value).

Example

The example below implements a simple fibonacci function that doesn't need recursion, but rather uses loop let with (u64, u64, u64) as its input and outputs u64.

fn fibonacci(n: u64) -> u64 {
    loop let (n, curr, next) = (n, 0, 1) {
        if n == 0 {
            break curr;
        } else {
            continue (n - 1, next, curr + next);
        }
    }
}

Those are just some scratches so any feedback would be appreciatable

5 Likes
3

Here's an implementation of your loop construct without needing new syntax. I think that this structure is too niche to need new syntax.

use std::ops::ControlFlow::{self, Break, Continue};

fn repeat<T, S>(initial: S, mut f: impl FnMut(S) -> ControlFlow<T, S>) -> T {
    let mut state = initial;
    loop {
        match f(state) {
            Continue(new_state) => state = new_state,
            Break(output) => break output,
        }
    }
}

fn fibonacci(n: u64) -> u64 {
    repeat((n, 0, 1), |(n, curr, next)| {
        if n == 0 {
            Break(curr)
        } else {
            Continue((n - 1, next, curr + next))
        }
    })
}
6 Likes
4

Nit arguably, but I don't really agree with this.[1][2][3]

Put another way, it’s become clear to me over time that the problems with data races and memory safety arise when you have both aliasing and mutability. The functional approach to solving this problem is to remove mutability. Rust’s approach would be to remove aliasing. This gives us a story to tell and helps to set us apart.

Focusing on ownership · baby steps

  1. E.g. you can make all bindings of any program mut without changing the semantics, so requiring mut on bindings is arguably nothing more than a lint. ↩︎

  2. E.g. in a generic or foreign type context you can't rule out interior mutability, and no, the unstable Freeze trait doesn't help as that covers shallow interior mutability only (for example nothing on the other side of a Box or other pointer, or that round-trips through the OS or other I/O). ↩︎

  3. Though unfortunately most learning resources, including official ones, present (or at least open with) a mutable-vs-immutable model verus the more accurate exclusive-vs-shared model. ↩︎

2 Likes
5

If we had become for guaranteed tail call elimination, would you still want to write these things like this instead of recursively?

If all you need is direct tail recursion, here's a combinator for that which has worked since at least 2018: When will Rust have TCO/TCE? - #3 by scottmcm - help - The Rust Programming Language Forum

3 Likes
6

Same could be said about pub: you could make everything pub and it would still compile.

A "lint" isn't the right word for this. It's a permission marker.

1 Like
7

The real benefit of tail calls is when you have different functions calling each other in a tail-recursive way. You cannot do that with a loop like this.

4 Likes
8

First of all guys thanks for the feedback, as I said this is just a scratch of the idea in my mind, but trust me, it can go beyond the current ways to achieve similar behaviour

Your repeat function is just a partial implementation of loop let since repeat doesn't support fallible patterns, while loop let does support.

If fact, loop let would need some special treatment to support this crossed recursion

We still don't have become and i dont think we'll ever see it. Also become is a terrible choice of name, recur would be a better option.

Again thanks for the feedback it helps me strengthen the proposal

9

7 posts were split to a new topic: Should the tail recursion expression be called become, or something else?

10

This should probably be spelled like this:

fn fibonacci(n: u64) -> u64 {
    loop let (n, curr, next) = (n, 0, 1) {
        if n == 0 {
            break (n, curr, next);
        } else {
            continue (n - 1, next, curr + next);
        }
    }
    curr
}

As in, the result of this loop let example is defining the bindings n, curr and next not just inside its block but also into the enclosing block (like a let), rather than ultimately evaluating into an expression without defining any bindings.

1 Like
17

The behaviour or loop let is sorta a mix of loop and while let

The value passed to continue must be the same as in the input. The value passed to break is the value of the loop let expression, they don't need to be the same. Also, just like in if let and while let binds are local to the block, so curr isn't defined outside the loop block.

1 Like
18

What value would the loop let block evaluate to if the pattern is fallible?

19

With fallible patterns loop let can't be used as an expression

20

Moderator note: discussion about the name of the tail recursion expression, become, as been moved to a new topic

1 Like
21

Wouldn't this be enough?