Can you use async to write a generator?


#1

Most of the examples I’ve seen for the upcoming async/await have showed off async I/O. That’s fair, since that’s why it exists, after all :slight_smile: . But I’m interested in simple generators. Will it be possible to use async to write zero-overhead generators that don’t need heap allocation, Arc, or an event loop? I’ve looked, but I can’t find any info about this.

Here’s some Python:

def fib():
    a, b = 0, 1
    while a < 25:
        yield a
        a, b = b, a + b


for n in fib():
    print(n)

Can someone translate this into futures 0.3 so I know what functions/traits to google to learn more?


#2

Async isn’t how you’d write a generator for non-I/O tasks. It only has benefit when non-blocking I/O is involved (spawning processes (threads) / reading and writing to file descriptors). However, you can get the exact behavior that Python is doing without async.

Scoped Closure

A closure can actually be used as a generator:

fn main() {
    let (mut a, mut b) = (0, 1);
    let mut fib = move || -> usize {
        let next = b;
        b += a;
        a = next;
        a
    };

    let mut current = fib();
    while current < 25 {
        println!("{}", current);
        current = fib();
    }
}

Custom Iterator type

This is the preferred means of constructing generators, which can be done without the standard library:

struct Fibber {
    a: usize,
    b: usize,
    limit: usize
}

impl Fibber {
    pub fn new(limit: usize) -> Self {
        Self { a: 0, b: 1, limit }
    }
}

impl Iterator for Fibber {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        if self.a < self.limit {
            let iteration = self.b;
            self.b += self.a;
            self.a = iteration;
            Some(iteration)
        } else {
            None
        }
    }
}

fn main() {
    for value in Fibber::new(25) {
        println!("{}", value)
    }
}

Generator crate

Rust doesn’t support generator abstractions in the standard library, but you can use the generator crate, which would look like so:

#[macro_use]
extern crate generator;

use generator::{Generator, Gn};

fn fib(n: usize) -> Generator<'static, (), usize> {
    Gn::new_scoped(move |mut s| {
        let (mut a, mut b) = (0, 1);
        while a < n {
            s.yield_(a);
            let c = a + b;
            a = b;
            b = c;
        }
        done!();
    })
}

fn main() {
    for value in fib(25) {
        println!("{}", value)
    }
}

#3

Added a scoped closure example, since this is also a possible way of solving the problem of generation.


#4

Thanks for the response! The thing I’m looking for is developer ergonomics, i.e. not having to unroll the generator state machine by hand. I should have known there would be a crate for it!

I also just stumbled on the nightly feature. Not sure how I missed it before. I’m leaving a link here for my future (no pun intended) self
https://doc.rust-lang.org/beta/unstable-book/language-features/generators.html

In the other languages I’m familiar with that have both yield and async, the two are very closely related. I guess in Rust that’s not the case.


#5

The return type of an async function is a generator, but the generator interface isn’t stable yet. So async/await will actually be the only way to write then for a while, but it will not give you the full scope of what generators allow.


#6

@skade Can you clarify, I’m intrigued and I’m trying to piece together what you said.

According to this, the return type of an async fn is a Future—specifically I assume std::future::Future. By “is a generator”, I assume you mean it implements the std::ops::Generator trait. Is that right? If so I would expect to see impl Generator for Future (or maybe the reverse) somewhere, but I don’t see it. Are you referring to from_generator? That function is in nightly std, but not in futures-0.3, does that mean it’s going away? I’ve been assuming futures-0.3 is canonical since development takes place there and std is lagging behind. Is that wrong?

What am I missing?


#7

It would be more like impl Generator for <the actual return type>, and it would be implemented by the compiler, not in source anywhere. But it’s all an internal implementation detail at the moment anyway- not something you can use even on nightly.

There are some fundamental differences between generators as they are exposed to users (on nightly) and async functions, anyway, that likely won’t ever be unified. Keeping them as separate features is useful- for example, it might let users combine the two to produce an “async generator,” or a Stream.


#8

This isn’t really accurate. In fact, it’s self-contradictory: spawning threads does not involve “non-blocking I/O”, at least not when using the common programming vernacular.

In fact, generators and coroutines are explicitly called out as use cases for the development of async/await: https://internals.rust-lang.org/t/help-test-async-await-generators-coroutines/5835

Async/await could definitely be used as a basis for an ergonomic syntax for implementing iterators by way of generators, and is referred to as a “huge benefit” of generators here: https://internals.rust-lang.org/t/help-test-async-await-generators-coroutines/5835/16


#9

A Future is a single value, which is either the Item or Error condition. A generator would be based on Stream, which can produce many futures.

It does involve non-blocking I/O if you are configuring the piped file descriptors between parent and child, and reading/writing to them. In addition, waitpid would disagree with you on threads in general not being a part of the non-blocking I/O paradigm. The status / reaping of multiple PIDs / PGIDs can be polled asynchronously.

Only when coupled with threads, channels, and other I/O does async become useful. Otherwise, as in the fibonacci example above, you would end up with a stream that can never return Async::NotReady, because you’d have a stream of lazy futures. The overhead of the machinery in comparison to an Iterator-based generator isn’t worth it.