Async and Await in Rust: a full proposal

First off, do notation desugars to closures. But Rust has three different kinds of closures. How does that work?

Furthermore, Rust has imperative control structures. How does all of this interact with each other? Are you now no longer allowed to use those constructs inside of do notation? That feels inconsistent.

I don't know of any languages that have something like do notation but don't have everything boxed. It makes everything easier, but that's not generally acceptable in Rust. For example, we can use async/await with no dynamic allocation. Could we with do notation?

"Open question" doesn't mean "impossible", mind you. But nobody has ever come up with a design. In the meantime, we have users to support...

Sticking to the first part: an effect system is not what the user I was responded to was talking about. They were talking about building do notation on top of type classes with higher kinded polymorphism, which cannot effectively abstract over the monadic operations in Rust.

When people say that monads and do-notation don't work in Rust, they're talking about a user-level Monad trait and a simple CPS transform built on top of it:

- Such a monad trait is impossible to write even with HKT because it would have to abstract over both Option/Result (type constructors) and Iterator/Future (traits)

- Such a CPS transform would be extremely limited (not composable with built-in loop structures) and/or extremely tricky around TCE, lifetimes, and allocation (the typical type for `>>=` would involve `Fn` trait objects...).

Effects bypass this by leaving the CPS transform in the compiler, instead only exposing delimited continuations to userspace. Which is basically what async/await does, just non-generically.

You might want to do a Google Scholar search on Niko Matsakis and Aaron Turon before making silly claims like this.

Higher kinded polymorphism results in trivially undecidable type inferences without something like currying; the restrictions needed to support it would be arbitrary and weird given that Rust does not have currying (essentially some rules to reconstruct the restrictions of currying in type operator context).

Instances of both Future and Iterator do not implement the Monad type class as defined in Haskell, because the "fmap" operator does not return the "self" type parameterized by a new type, it returns it own new type. This is because the state machine they represent is leaked through their function signature.

Do notation doesn't work with the imperative control flow that Rust has, which other people have already discussed.

Maybe what you have in mind, though, is the traditional argument, that there's no such thing as undelimited continuations. All continuations are naturally "delimited" by the boundary of the language runtime, operating system, etc, even with undelimited, multi-shot continuations. One-shot continuations make this argument more natural, because they have an obvious stack-based implementation for both delimited and undelimited continuations, and stacks are clearly delimited.

You are literally describing stackless coroutines. And the generator state transform is that optimization.

If you want to get this without using generators explicitly, it's still stackless coroutines just not how Rust supports stackless coroutines. There was some discussion about making it more implicit but no progress was made in the implicit direction.

I'm referring specifically to the async/await syntax. Coroutines probably need to be implemented in the compiler, sure, but the actual async/await can be implemented with metaprogramming.

IIRC it doesn't. Coroutines would induce a significant cost (one stack allocation per future) which would make futures unsuitable e.g. for embedded systems.

My understanding is that Rust will compile futures into state machines. So a future would be a closure with a data object that's a sum type with one variant per suspend point, that contains all the variables and references that are in scope at that suspend point. (That's also why Pin needs to be added for futures/generators: This set of variables may be self-referential.)

A Rust future is also "responsible for making sure that it gets resumed appropriately if it suspends." Rust's await is even cheaper than C++/LLVM's- it doesn't do anything with an event loop either; it just returns, without atomically messing with any coroutine handle (which doesn't exist).

Further, Rust futures are poll-based, not callback-based. Your bullet list looks like this:

* Function call to the main entry point (which is really more of a constructor)

* The future creates its frame as a value type (not as a heap allocation) and initializes it with the call arguments

* Function return (not a suspend, because it returns an initialized future rather than Poll::Pending- so again more of a constructor return)

* (sometime later, often immediately) Function call to `poll` (initial resume)

* `poll` executes until a suspend point (function return)

The initial call to `poll` can happen because the constructed future was put on the event loop and scheduled, as you describe, but it can also happen merely because its caller is also a future that is already running somehow.

Also, note that "the event loop" is a rather loose concept here- it's just "the thing that calls top-level `poll` functions." The language doesn't ever submit anything to it, or signal it, or anything. Each call to `poll` receives a handle to that top-level caller, and each leaf future stashes that handle somewhere that will signal it when it's ready to resume. This even works in embedded microcontroller scenarios.

And finally, your eager execution example is addressed in Rust in two ways:

* First, ownership and the borrow checker prevent dangling references like this statically. In your particular case, the caller would increment the refcount as part of cloning an `Rc`, and then move the clone into the future. (Unless, of course, the future was short-lived enough, and you decided to take advantage of that to pass in a `&'a Value.Fn` instead.)

* Second, because future construction (the first three bullet points) and future execution (the last two) are decoupled, you can write your own function that does any extra construction work in the cases that it's actually necessary. For example, using Rust's syntax for async blocks:

    pub fn render_to_llvm(.., fn_val: *Value.Fn, ..) -> impl Future<Output = ()> {
        fn_val.base.ref();
        async {
            defer fn_val.base.deref(comp);
            // ...
        }
    }

Rust has gone back and forth on this. Pre-1.0 versions of Rust had a "green threads" mode. It was removed in favor of OS threads because it wasn't worth the complexity.

Go is a language in which "all functions are async" and it's pretty cool. But it needs a runtime, and interop with C / C++ has some real overhead related to switching to a C-style stack. Rust did not want to make those compromises, it wanted to be appropriate for bare-metal or kernel programming, and for libraries used by big high-performance C++ applications. In these cases, Go's model does not work well.

I personally use Go a lot, it's great for network services and command-line tools, and that's mostly what I do.

Making every function call asynchronous is likely to make most programs a lot slower.

If we did the whole problem async (async by default as I interpret it) it would require so much bookkeeping to keep causality that would make it unreasonably difficult. For things that require causality like that, we are lucky that the default mode of computation is synchronous because it fits my problem domain perfectly.

That's why I say "not everything is web" because while async maps well to problems like a server-client type application, it doesn't map well to all problems like my problem for example. Also, as someone else said, sync is easier to reason about for problems that don't require a lot of parallelism.

Which doesn't mean it's bad. I'm excited about tokio and rust's async story. But I love that I get to choose.

Just dealt with that in a .NET app that uses a 3rd party SDK that heavily uses async/wait. I had to build a whole layer of state management to just handle shutdowns. Simple threading would have been much easier.

It's different with server side code. There async/await is very nice.

Note that you don't get the continuation in hand for the async-everywhere advocated by GP, only blocking operations get the continuation, and most of those are implemented by the runtime.

More wasteful than writing each function twice? See C# for endless examples of libraries that have manual duplicate X() and XAsync() for every single method. If you compare the two they're almost always have the exact same body, except the async version has "async" and "await" peppered in and calls duplicate XAsync methods (which are implemented the same, except they call XAsync methods... you might be seeing a pattern here).

If I'm not mistaken most rust doesn't use separate compilation and is built from source. In this case the compiler can treat it just like normal generics and just not compile it until it's used. And even with separate compilation for, e.g. a library, a very basic LTO would trivially trim out the unused methods when compiled into a final binary. And if you don't want 2x library itself, even then you can just use an escape hatch to turn it of on the crate/impl/function level and it's still better for you than the status-quo where you have to manually add a bunch of tokens and junk that the compiler already knows how to do precisely.

If anything is wasted it's human effort because we're wasting our time doing something the computer can do better and faster.

> "annotations in the object file to describe the frame size"

Wouldn't you need this anyway for anything async, even if it's manual? This seems like an argument against async in general, not automatic async.

Perhaps this is just obvious. But I do frequently see people pretending to be objectively objecting -- complaining about traffic that they are themselves the cause of as if they didn't already know the answer to their question.

Yes. That's one thing the rust community has to get right.

async/await was supposed to be that, but it's only a protocol to define what blocks/doesn't and when you allow context switching. An event loop also has the notion of scheduling, getting a reference to what is scheduled, request the result or error on said scheduled thing, or cancel it. And even loop must bridge different implementations of concurrency (e.g: asyncio.run_in_executor). An event loop also has a life cycle, which includes at the very least a setup and a tear down. An event loop must integrates in an environment, like what do you do when you have several loops, or if you run one loop per threads ?

So you need to define a general behavior for all that. Then let anyone write the implementation the way they want.