Can you use async to write a generator?

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?

5 Likes

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)
    }
}
2 Likes

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

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.

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.

@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?

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.

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: Help test async/await/generators/coroutines! - announcements - Rust Internals

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: Help test async/await/generators/coroutines! - #16 by mbrubeck - announcements - Rust Internals

1 Like

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.

No Future, this is an alternative: Rust Playground .

Async/await is built on top of language level generators, the returned type is a small wrapper around the generator that constrains the generator to a specific Yield type and then provides an implementation of Future. If you want waay too many details about this I published a blog post on it recently.

Unlike Python these generators do not implement Iterator, so you cannot use them in a for loop, but it is very easy to write an adaptor struct:

struct W<T>(T);

// This impl isn't safe in general, the Generator passed must not be immovable
impl<T: Generator<Return = ()>> Iterator for W<T> {
    type Item = T::Yield;

    fn next(&mut self) -> Option<Self::Item> {
        match unsafe { self.0.resume() } {
            GeneratorState::Complete(..) => None,
            GeneratorState::Yielded(v) => Some(v),
        }
    }
}

Note the comment there, this is currently unsound to use for all generators, but hopefully very soon the generator API will be updated to make a fully safe wrapper like this possible (and I have a small collection of utilities I might publish once that happens).

3 Likes

That is exactly what I want :grin:

That write-up looks amazing, thanks for the link!