Recursion for async/.await

language design
1

Rust has exciting feature as async/.await !!

But this feature also have issue: recursion !!

Consider the following example:

async fn recursive() {
        recursive().await;
        recursive().await;
}

This code even does not compile ... To fix it we should do recursion in such way:

use futures::future::{BoxFuture, FutureExt};

fn recursive() -> BoxFuture<'static, ()> {
    async move {
        recursive().await;
        recursive().await;
    }.boxed()
}

But what if you want .await on something inside of recursive also ?? It is not possible ... (

It happens, because internally compiler generates the following code for async:

async step_one() -> u8 {
    1u8
}

async step_third() -> u32 {
    1u32
}

// This function:
async fn foo() {
    step_one().await;
    step_two().await;
}
// generates a type like this:
enum Foo {
    First(u8),
    Second(u32),
}

// So this function:
async fn recursive() {
    recursive().await;
    recursive().await;
}

// generates a type like this:
enum Recursive {
    First(Recursive),
    Second(Recursive),
}

Recursive enum depends on itself !! But what if compiler will generate the following enumeration for recursion function:

async step_one() -> u8 {
    1u8
}

async step_third() -> u32 {
    1u32
}

// So this function:
async fn recursive() {
    step_one().await;
    recursive().await;
    step_third().await;
    recursive().await;
}

// generates types like this:
enum RecursiveHelper {
    First(u8),
    Third(u32),
}

enum Recursive {
    First(u8),
    SecondSelfCall(RecursiveHelper),
    Third(u32),
    FourthSelfCall(RecursiveHelper),
}

This solution will allow such code to compile:

async fn recursive() {
        recursive().await;
        recursive().await;
}

Also take a look at discussion https://users.rust-lang.org/t/tokio-reccursion-error/41750/29

1 Like
2

This desugarring doesn't work because it doesn't actually support recursion, you can only go 1 call deep.

Let's use a more realistic example,

async fn recursive(rx: Reciever<i32>) -> i32 {
    let value = rx.recv().await;
    if value == 0 {
        0
    } else {
        value + recursive(rx).await
    }
}

How would this desugar? We need to keep the rx and value across different await points. Currently this desugars to something like this:

enum Recursive {
    NotStarted(Reciever<i32>),
    Recv(Reciever<i32>),
    Recursive(i32, Recursive),
    Completed,
}

Which doesn't compile until you add indirection

2 Likes
3

Compiler could generate the following code:

async fn recursive(rx: Reciever<i32>) -> i32 {
    let value = rx.recv().await;
    if value == 0 {
        0
    } else {
        value + recursive(rx).await
    }
}

// generated code
enum RecursiveHelper {
    Recv(i32),
}

enum Recursive {
    NotStarted,
    Recv(i32),
    Recursive(RecursiveHelper),
    Completed,
}

Interaction could be removed by adding additional type like RecursiveHelper

4

No you can't, that would not allow unbounded recursion. What's the state when the channel recieves 2 nonzero values and is now waiting on a third number?

In the current desugaring this would be represented as (ignoring indirection dor simplicity)

Recursive(first, Recursive(second, Recv(rx)))
2 Likes
5

But it is an issue of the programmer ?! What happens if the same happens with general function ?

6

With normal functions you just grow the call stack, async functions can't do that. Their stack is allocated all at once, and will never grow.

4 Likes
7

Yes and the new recursion call happens with .await it is possible to create separate coroutine !! I do not see any issues ...

8

Also my current understanding is that every async function:

async fn get_num() -> u8 {
    // Some async operations
    2u8
}

converts to the following code:

fn get_num() -> Future<u8> {
    // Some operations
}

This mean that the same possible to do with recursive async function:

async fn recursive(rx: Reciever<i32>) -> i32 {
    let value = rx.recv().await;
    if value == 0 {
        0
    } else {
        value + recursive(rx).await
    }
}

could converts to the following code:

fn recursive(rx: Reciever<i32>) -> BoxFuture<'static, i32> {
    async move {
        let value = rx.recv().await;
        if value == 0 {
            0
        } else {
            value + recursive(rx).await
        }
    }.boxed()
}

Compiler just need to detect recursive async call and then generate BoxFuture

9

Autoboxing would prevent aync from working on target's without an allocator. Can you provide an implementation of Future under your desugaring?

3 Likes
10

Your specific example can be rewritten to be tail recursive,

async fn recursive_sum_inner(sum: i32, rx: Receiver<i32>) -> i32 {
  let value = rx.recv().await;
  if value == 0 {
    sum
  } else {
    recursive_sum_inner(sum + value, rx)
  }
}
async fn recursive_sum(rx: Receiver<i32>) -> i32 {
  recursive_sum_inner(0, rx)
}

I am not certain, but I think that's a mechanizable transformation. Tail recursion can of course be mechanically lowered to iteration,

async fn iterative_sum(rx: Receiver<i32>) -> i32 {
   let mut sum = 0i32;
   loop {
     let value = rx.recv().await;
     sum += value;
     if value == 0 { break }
   }
   sum
}

and now we don't need a recursive type to represent the state machine. IIRC Rust doesn't currently lower tail recursion to iteration and there are strong arguments for why it's not always desirable, but maybe in the case of async fn it should be at least attempted.

In the general case, this isn't just an issue of the type system not currently supporting recursive types. Each recursive call needs to allocate memory, and we can't do it on the normal call stack, but the compiler already has special knowledge of Box, so, would this work maybe?

enum Recursive {
    NotStarted(Reciever<i32>),
    Recv(Reciever<i32>),
    Recursive(i32, Box<Recursive>),
    Completed,
}
4 Likes
11

Of course mine can be tail recursive, but that's missing the point. It would be trivial to make it non-tail recursive. Rust doesn't guarantee TCO anyways (even with normal functions). As I said before, relying on boxing will mean that async functions can't work on systems without an allocator. If you want a more complex recursive example

async fn recursive(rx: Pin<&mut Reciever>) -> i32 {
    let value = rx.as_mut().await;
    if value == 0 {
        0
    } else {
        value + recursive(rx).await + recursive(rx).await
    }
}

Not tail call recursive. Yes, you can use an explicit stack, but that's pretty much all recursive functions.

6 Likes
12

(You posted this while I was writing my reply.)

I am not OP, but I could live with a rule that recursive async fns would only work in environments where a heap allocator was available -- perhaps with "the compiler will try to lower recursion to iteration, but we don't guarantee it will work".

Given that, in the general case, recursion requires you to put a stack somewhere, and we can't use the hardware procedure call stack, the only way I can think of to avoid needing an allocator is to put a compile-time limit on the recursion depth (so you have a fixed-size stack in the state machine) and there won't always be a limit that can be computed at compile time. I would guess that a majority of nontrivial uses of async non-tail recursion (async recursive descent parser, anyone?) require a runtime-dynamic stack depth.

13

I like your idea !!

Compiler detect recursive async function call and generate such enum for State Machine !!

It is really cool !!

14

Hmm, it has drawbacks ...

Why not to use helper enum for preventing enum to depend on itself ?

enum RecursiveHelper {
    NotStarted(Reciever<i32>),
    Recv(Reciever<i32>),
    Completed,
}

enum Recursive {
    NotStarted(Reciever<i32>),
    Recv(Reciever<i32>),
    Recursive(i32, RecursiveHelper),
    Completed,
}
15

Your helper enum approach doesn't work. If you want proof, please implement my first example using helper enums in a playground link, and implement Future. Here's the desugaring using indirection to get you started. playground

5 Likes
16

Ah, now this thread is less baffling to me. That is missing out most of what async/await sugar does. If that really was all it did, we probably wouldn't have even bothered adding special syntax for it.

The relevant highlights from the async/await RFC (back when it was await!() instead of .await) are:

An async fn foo(args..) -> T is a function of the type fn(args..) -> impl Future<Output = T> . The return type is an anonymous type generated by the compiler.

The await! builtin expands roughly to this:

let mut future = IntoFuture::into_future($expression);
let mut pin = unsafe { Pin::new_unchecked(&mut future) };
loop {
    match Future::poll(Pin::borrow(&mut pin), &mut ctx) {
          Poll::Ready(item) => break item,
          Poll::Pending     => yield,
    }
}

This is not a literal expansion, because the yield concept cannot be expressed in the surface syntax within async functions. This is why await! is a compiler builtin instead of an actual macro.

This should make it more obvious why the only way to have the compiler magically generate a type for recursive async calls requires implicit boxing. And "implicit boxing" is clearly not zero-overhead, which has always been one of the primary goals of futures in general and async/await in particular.

Some languages choose to implicitly allocate/box on their async code, usually because they have different priorities, or because they predate the various innovations that helped make Rust's zero-overhead futures possible. But in Rust, recursion in async/await is just fundamentally not possible without throwing out one of the core goals of the feature or the wider language.

13 Likes
17

Is it really "throwing out one of the core goals" if we say that recursive async fns have allocation overhead, though? That seems more like a "you only pay for this if you need it" situation to me.

1 Like
18

You can just box futures if you need recursion. Implicit overhead is against Rust's values.

3 Likes
19

Fair point. IME at least in Rust and C++ it's usually not considered "zero-overhead" to have any kind of implicit dynamic memory allocation, but that's a semantics game we could quibble about forever.

The important part is just that Rust strongly prefers to make you write Box or Vec or whatever when you need to pay an allocation cost.

1 Like
20

There are more efficient ways to handle these alllocations, for example you could allocate multiple futures into a single allocation instead of one per future. You could use a custom allocator that's specialized for recursive functions, etc. By making this explicit it becomes easier to track when you need to.

2 Likes