owned this note changed 2 years ago
Published Linked with GitHub

Keyword generics initiative update (2023-06-14)

Topics to Discuss

  1. An acknowledgement of failure (2 mins)
  2. Rename to "Effects Initiative" (3 mins)
  3. The path to minimum viable "polymorphic effect types" (55 mins)

1. An Acknowledgement of Failure (2 mins)

In February of this year we published "Keyword Generics Progress Report: February 2023" which missed the mark pretty badly. I (Yosh) was too eager to show off what we could do, and didn't spend enough time motivating why any of it would be a good idea, or how it would work. And that understandibly put people off.

Because the Keywords Generic Initiative exists under the Lang Team, I imagine this has caused y'all extra work as well, and for that I'm sorry. As for me: lesson learned about sharing syntax before semantics.

2. Rename to "Effects Initiative" (3 mins)

Note: Because we only have limited time in this meeting, we should spend no more than 5 mins on this topic. We were unsure about the process involved in renaming ourselves - so we figured a good starting point would be to inform you all that we would like to rename our initiative.

The Keyword Generics Initiative was named that because we realized there was a form of generic missing for "modifier keywords". The only thing we knew about effects is that they looked like fancy co-routines, and that seemed different. So we dubbed ourselves the "keyword generics initiative" because that seemed good enough. After studying the literature, we've since realized that "effects" can refer to roughly two things:

  1. Effect Types: which you can think of as semantic function notations
  2. Effect Handlers: which you can think of as typed co-routines

When we talk about "keyword generics", what we're actually talking about is known in literature as "effect type polymorphism". That's effects in the first sense: semantic annotations of functions and contexts. This compliments what we call "generics" in Rust, or "data type polymorphism". Because we finally know that we are indeed working on enabling Rust's effect types to be more polymorphic, we want to rename us to the "Effects Initiative" instead.

3. The Path to Minimum Viable Polymorphic Effect Types (55 mins)

3.1 Motivation

Broadly speaking the goal of the Keyword Generics initiative is to extend Rust's effect system to become polymorphic. We have some (limited) polymorphism in Rust already today:

  1. const: const fn may be const-evaluated, they don't have to
  2. try:fn main optionally accepts a top-level Result being returned
  3. unsafe: Closures carry any enclosing unsafe {} contexts, bypassing the need for an UnsafeFn family of traits

But by making Rust's effects polymorphic, we could make all of Rust's effects polymorphic, consistently. This would resolve a number of issues we're currently facing:

  1. stdlib: Most APIs in the stdlib can't carry effects. We know we want APIs such as "async iterator", but we don't want to have to duplicate the entire APIs surface. That would be a lot of modules.
  2. combinatorics: Effects are combinatorial in nature. We know we probably want AsyncFn and TryFn traits. But nobody is excited to have to write all eventual variations on AsyncTryFn.
  3. effect sandwich: It would give us an out on the "effect sandwich problem". When designing an API today you have to choose the set of effects which it operates with ahead of time. With effect polymorphism we would instead be able to write code in such a way that we instead operate on the effects provided by the caller.

3.2 Breaking down effect polymorphism

Effect polymorphism can be split can be thought of as a collection of features, which together enable what we call "full" effect polymorphism. Those features are:

  1. effect-polymorphic trait declarations: This is the idea of "maybe-traits"; traits which may conditionally carry an effect. For example: a Read trait which may or may not be async.
  2. effect-polymorphic function declarations and bounds: This could be for example the Vec::new function, but it would only return a Result if the caller asked for it. It would potentially panic otherwise.
  3. effect-polymorphic types: This could for example be the File type, but it would only be async if the caller initialized it as async.

Our plan is to start by focusing on the first feature: "effect-polymorphic trait declarations". This will enable us to ship much-requested versions of async traits such as Read and Iterator. And it would likely play a role in enabling core async language features such as async closures and async Drop.

3.3 A minimum-viable design

Because the design space of effect polymorphism is large, we need to carefully choose what we want to ship first. We believe that the best place to start is to enable polymorphic trait declarations which can only be used for monomorphic implementations. This should enable shipping async versions of the Read and Iterator traits sooner, which are some of the most requested async features. For the Read trait, we imagine this could look roughly something like this:

#[maybe(async)]
trait Read {
    #[maybe(async)]
    fn read(&mut self, buf: &mut [u8]) -> Result<usize>;
}

// An non-async implementation
struct MyStruct {}
impl Read for MyStruct { .. }

// An always-async implementation
struct MyAsyncStruct {}
impl async Read for MyStruct { .. }

Our goal with our approach is to be minimally disruptive for existing code. We've learned our lesson from ~const, and want to make sure we don't cause any significant maintenance burden to the libs team while we develop the feature. We'll want to start by manually authoring the desugared version for a single trait in a way that doesn't show up in rustdoc. And once we have that working we can uplift it into a compiler attribute.

Speaking of lessons learned: we would like to emulate the success had by the gradual constification of the stdlib. Just like with inherent methods, it should be possible to gradually add effect polymorphism to individual default methods. This would allow us to for example stabilize parts of maybe-async iterator without being blocked on features such as async closures.

Another design constraint is that in some cases we want to provide access to non-async methods to the async variant of a trait. The classic example for this is the Iterator::size_hint method which should never async, even if the trait is monomorphized to be async. This should be possible to do with another notation, similar to the#[maybe(async)] notation we're proposing. If we add both requirements, we can imagine a more complicated trait such as maybe-async Iterator could be written like this:

#[maybe(async)]
trait Iterator {
    type Item;
    
    #[maybe(async)]
    fn next(&mut self) -> Option<Self::Item>;
    
    #[never(async)]
    fn size_hint(&self) -> (usize, Option<usize>)
    
    // We don't want this function to be available for `async Iterator`
    // for now, because it is a maintenance issue for the libs team,
    // because it requires changing a lot of code.
    #[rustc_maybe_in_future_todo(async)]
    fn for_each<F>(self, f: F)
    where
        Self: Sized,
        F: FnMut(Self::Item);
}

By starting with a polymorphic definition, but only allowing monomorphic implementations, we should immediate be able to make headway on creating shared interfaces for async Rust. That's one of the most requested features of the Async WG. Our approach would even allow us to stabilize the async trait definitions without needing to also stabilize the underlying mechanism, enabling us to ship the requested feature sooner [1].

3.4 Desugaring

The previous example will desugar to existing or simple future features.

//#[maybe(async)]
trait Iterator<const ASYNC: bool = false> {
    type Item;
    // TODO(oli): explain why can't we just use this without `helper`
    type NextReturnType<'a>: Future<Output = Option<Self::Item>>
    where
        Self: Iterator<true>;
    //#[maybe(async)]
    fn next(&mut self) -> <Self as helper::Dummy<ASYNC>>::Ret<'_>;
    
    fn size_hint(&self) -> (usize, Option<usize>) { (0, None) }
    
    fn for_each<F>(self, f: F)
    where
        Self: Sized,
        F: FnMut(Self::Item),
        Self: Iterator<false>;
}

mod helper {
    trait Dummy<const ASYNC: bool> {
        type Ret<'a>;
    }
    
    impl<T: Iterator<true>> Dummy<true> for T {
        type Ret<'a> = T::NextReturnType<'a>;
    }
    
    impl<T: Iterator<false>> Dummy<false> for T {
        type Ret<'a> = Option<T::Next>;
    }
    
    // specialization hack so that `<Self as Dummy<ASYNC>>` works in the `Read` trait.
    // alternatively we can just implement something like https://github.com/rust-lang/rust/pull/104803
    impl<const ASYNC: bool, T: Iterator<ASYNC>> Dummy<ASYNC> for T {
        type Ret<'a> = !;
    }
}

// An non-async implementation
struct MyStruct {}
impl Iterator for MyStruct {
    type Item = ();
    // no type NextReturnType<'a>, because the `where Self: Iterator<true>` does not hold.
    // just like on stable today:
    fn next(&mut self) -> Option<()> {
        todo!()
    }
}

// An always-async implementation
struct MyAsyncStruct {}
impl Iterator<true> for MyStruct {
    type Item = bool;
    type NextReturnType<'a> = impl Future<Output = Option<bool>>;
    fn next(&mut self) -> Self::NextReturnType<'a> {
        todo!()
    }
}

Ideally we could write this:

//#[maybe(async)]
trait Iterator<const ASYNC: bool = false> {
    type Item;
    // TODO(oli): explain why can't we just use this without `helper`
    type NextReturnType<'a> = Option<Self::Item>;
    //#[maybe(async)]
    fn next(&mut self) -> Self::NextReturnType<'_>;
    
    fn size_hint(&self) -> (usize, Option<usize>) { (0, None) }
    
    fn for_each<F>(self, f: F)
    where
        Self: Sized,
        F: FnMut(Self::Item),
        Self: Iterator<false>;
}

// An non-async implementation
struct MyStruct {}
impl Iterator for MyStruct {
    type Item = ();
    // no type NextReturnType<'a>, because the `where Self: Iterator<true>` does not hold.
    // just like on stable today:
    fn next(&mut self) -> Option<()> {
        todo!()
    }
}

// An always-async implementation
struct MyAsyncStruct {}
impl Iterator<true> for MyStruct {
    type Item = bool;
    type NextReturnType<'a> = impl Future<Output = Option<bool>>;
    fn next(&mut self) -> Self::NextReturnType<'a> {
        todo!()
    }
}

but: associated type defaults would require an Iterator<true> impl to implement all methods, even the defaulted ones.

3.5 Blocking language features

While working on the implementation of polymorphic trait definitions, we've uncovered a number of limitations in the language which we're looking to fix along the way. This is nice, because it means we can use the feature work we're doing to "finish implementing" existing, accepted language features. This means it's not "working on new features" VS "improving existing features", but instead we're "resolving long standing corner cases of existing features". These are the features which need improving:

Feature Motivation URL
assoc ty sized bound where Self: Sized bounds don't make associated types hidden from trait objects and thus still require mentioning the assoc type in all trait objects https://github.com/rust-lang/rust/pull/112319
Self: Trait<false> bounds assoc types and methods in Trait<true> impls still need to implement methods that have Self: Trait<false> bounds. https://hackmd.io/psi31f7MQzC-oSzmIqAIiw#Breaking-change-users-need-to-specify-the-Rettie-associated-type
Self: Trait bounds old solver can't handle arbitrary where bounds during impl method signature checks (aka adding a Self: Trait bound on a function is a breaking change, even if trivial) https://hackmd.io/psi31f7MQzC-oSzmIqAIiw#breaks-impls-that-use-concrete-types-where-the-trait-has-associated-types

References


Questions and Notes

Write your questions and comments here.

minimal feature set

TC: what's the smallest thing we could ship, even if it didn't address critical use cases?

oli: Yes, the blocking language features are a good place to start. Let's round out the rough edges that we haven't had enough motivation for first.

Focus on motivation

nikomatsakis: How convincing we find the motivation? Yosh, Oli, have you spoken to libs team?

TC: design influences it

tmandry: I definitely find myself wanting this, I've written code that could work fine async/sync, but the iterator example has some outstanding questions e.g., next, poll-next. I can imagine it getting pretty hairy in the fundamental traits, where it's not just "you stick the async keyword here" and it works exactly as you would expect. Maybe we can express all of those using where-bounds, but I'm not sure.

joshtriplett: I've run into this (sync vs async, try vs not-try). I find the proposal of async iterator or async read or similar to be an open question. Nothing near consensus of that being the direction we want to go. I don't think we should treat that as load-bearing for the motivation. I feel it has motivation even if we don't use those things. Worth asking if the motivation works if you don't have async read using effect generics, do you hit a barrier when you try to make code that is generic over async, because you can't instantiate those traits? I don't think we should treat it as consensus.

oli-obk: Even if stdlib never becomes maybe async, solving the blockers that would enable a design like this would allow ecosystem crates (e.g., tokio, async_std) to make things maybe async in their own way.

joshtriplett: Compelling argument that if we had this version, first place we build a "maybe async" version of std should be in crates.io

pnkfelix: I previously asked about const, and I realized that you're motivation the feature by talking about async, asynciterator, other people are wondering about the complexity. I'm trying to figure out. The sol'n you're proposing is going to help with higher-order things that take const functions, right? There's a tension between choosing a simpler domain and someone saying "well that doesn't scale up to async problems". But jumping straight to async makes it seem very complicated. Is there a "gradual ramp-up"? I wonder if starting with a simpler domain like const fns would help.

oli-obk: For const, there are basically no blockers. We're designing the system for that, ignoring libstd. But it doesn't have the complexity because you don't have extra associated types and the like.

pnkfelix: But it does have the higher-order case.

oli-obk: Just a matter of adding a generic parameter. Async case can be done in user code w/o touching compiler, const requires compiler support even though it's simpler because const requires special compiler support.

nikomatsakis: const/panic/ are subset, async not

nikomatsakis: I'm a fan of this, I do want to avoid letting my language geek run away, but if you read the async closure blog posts I wrote, I feel like that model has a lot of simplicity in it, I'm not convinced that portraying it as complex is capturing the full picture.

tmandry: is it possible to write a fn that's generic over being async with this model?

oli: yes, though it requires unstable features

josh: seems closely related to the desugaring question: it seems like you've part a lot of effort into demonstrating this can desugar into something implementable with const generics. I can see how it makes sense to show that. It feels like that's adding a lot of complexity to the explanation. I'm not really clear on whether you're expecting people to write, at least early on, something that looks like the syntax from 3.4

oli: we do expect that in the beginning. Don't want to hide everything behind compiler magic. Using existing features makes it easier to explain. Some initial concern was that it was too much magic.

yosh: in literature you often find people talk about "effect resolver" in addition to "type resolver". We're trying to not add a new thing. Effect resolution feels really weird and complicated. What you're seeing is the evolution of several failed attempts.

joshtriplett: useful to show that it can be reduced, but I'm questioning whether having that be a presentation / implementation is truly simpler to explain. Doesn't seem simpler to read. Comes across as "this feels very complex". Useful as a proof that this isn't adding new generic mechanisms.

tmandry: I agree. When it comes to teaching Rust, you really want it to have some kind of first-class syntax that operates in an intuitive way. Biggest problem is that I don't think we know exactly what syntax we want. I think you want to get to something that feels intuitive.

yosh: Specifically what we're showing here is kind of tailored for lang-team, diving into the nitty gritty, but when teaching we want to go through that exercise.

nikomatsakis: I wonder if we can put some of these complexity questions to the test in the same way that we are working with Will Crichton.

yosh: I do believe effect polymorphism represents inherent complexity. How we represent it I think is a great question. Problem space, even if we do nothing, will plague us forever.

nikomatsakis: I'm a fan here, and I think we want to build this fairly deeply into the model, I don't really agree with the feedback that it should be desugared for simplicity, I think it makes it more complex. But I also don't see how we address async closures without some mechanism like this.

TC: if we get a try / async iterator it's a lot. One thing I think would help future presentation, going back to what Oli said, going back to things that would be polished, maybe taking it from the POV of building up to the feature, rather than solving the trait problem and going down, motivate the smaller improvements and then build a story about the progress of things we can do and show how it builds up.

More details about MVP surface area

nikomatsakis: For this proposed MVP:

  • Are you considering effects beyond async?
  • It includes declaring
    • #[maybe(async) on traits and functions within traits
    • async Trait as a valid trait name in basically all places, specifically to select the "mode" of a maybe async trait?
    • ability to implement Trait or async Trait (but not a "maybe async" impl)

Are there more bits of syntax?

scottmcm: 3.1 also mentioned combinatorics; does this plan to support #[maybe(async, unsafe)]?

yosh: That would indeed be the idea, though hopefully we would be able to resolve any syntactic questions before we expand to incorporate more effects beyond async.

default functions

Just like with inherent methods, it should be possible to gradually add effect polymorphism to individual default methods

scottmcm: we still haven't stabilized default values on types because of uncertainty on when whether other things can rely on those things. How would this work in similar situations: can one of the default methods call another default method, even though that other method might have been overridden in a way that doesn't support the maybe?

default functions part deux

nikomatsakis: Observation: If you permit #[maybe(async)] fn to have default values, then you must support "maybe-async" generic functions, at which point it's not clear what you get from limiting yourself to "always" or "never" async impls.

Lessons from other languages

TC: Could you talk a bit about how other languages you've researched have solved this problem? What lessons can we take away from what has or hasn't worked elsewhere?

Yosh: There is relatively little adoption of effect polymorphism in industrial languages. The reason why we started this work is because we saw the work done in Swift in async. But Scala is currently on a similar trajectory as us with their work on "Project Caprese". Here is Martin roasting the current state of effect polymorphism.

TC: Are there any research languages that Swift, Scala, and maybe we are or should be taking inspiration from here?

Yosh: Eric and I have been talking to the lead researcher of the Koka language, who is at Microsoft research. The paper "Koka: Programming with Row-polymorphic Effect Types" has informed a lot of the recent work on effect polymorphism.

never(async)

nikomatsakis: I didn't quite understand the point about #[never(async)]. Is it just a design choice, i.e., that it'd be preferable to be explicit about this, vs just writing fn set_len and having it be assumed that it's never async? Do you envision "always" async functions too?

yosh: size_hint in iterator should be available in both async and non-async implementations of the trait. We figured some sort of notation might make that clear, so we can individually stabilize non-async-methods-in-async-traits.

yosh: I don't think I know of any examples of "always async" methods in polymorphic async traits which would live in the stdlib? But if there is such a method, then yes, we could certainly add that.

Puzzled by library/ plans

From two adjacent paragraphs:

Our goal with our approach is to be minimally disruptive for existing code. We’ve learned our lesson from ~const, and want to make sure we don’t cause any significant maintenance burden to the libs team while we develop the feature.

Speaking of lessons learned: we would like to emulate the success had by the gradual constification of the stdlib.

scottmcm: So would this start gradually constifying/asyncifying the library, or would it wait for more confidence in the syntax this time?

yosh: The high-order bit here is that we think any "effectification" should be gradual. For nightly just having annotation could probably be enough; but for stabilization, though not technically required, we're happy to go with whatever lang and libs believe is best.

Desugaring

scottmcm: At what level would this desugar happen for something like Iterator? Would it be possible for someone to write where Foo: Iterator<false>?

ad-hoc vs parametric effect polymorphism

pnkfelix: It seems like the primary focus of the effect polymorphism you describe here is so-called "ad hoc" polymorphism, where one describes multiple concrete implementations that you dispatch between based on which effects are in play. However, the high-level sugar doesn't seem to ever express the ability to treat a specific effect as a named-parameter, which I think will be necessary once you get into stuff involving higher-order functions where you will need to describe which functions have which effects, and how those effects are threaded around. (let me know if you need me to spell this out more)

pnkfelix: Is your plan there that naming in the high-level sugar will come later, after it has become clear that its actually necessary? Or is your plan that if you want to name, you need to drop down into the lower level expanded form that uses const-parameters? (Which is fine, IMO)

Non-trivial effect domains?

pnkfelix: All the examples end up desugaring into two-element boolean domains. ASYNC:bool. CONST:bool, etc. Do you anticipate any effects with a richer domain than just boolean?

Effect algebra / combinatory effects

pnkfelix: (this Q might be subsumed by the "non-trivial effect domain" question above.)

pnkfelix: There is literature about Effect Algebras (e.g. are combinations Associative? Commutative? Unitary? Idempotent?) in effect systems that might be relevant. (To be 100% honest, I am not totally sure yet, because your current set of effects under consideration are drawn from "trivial" boolean domains and, if I understand correctly, are not expected to interact with one another so maybe there are not yet any interesting combinations to consider, other perhaps than false being unitary (true / false = true) and true being idempotent (true / true = true).)

tmandry: I'm also interested in this, and how well you can implement an algebra for effects that interact with each other using this trait desugaring.

desugaring

Josh: It feels like this has a lot of focus on a particular desugaring, and that desugaring makes it feel more complex. In particular, you're showing a desugaring for async that depends on const generics, and it's not clear how the generic parameter isn't exposed to users as stable API (Iterator<true>). I'm feeling like it's not obvious which portions of this are load-bearing and which parts are incidental. I honestly feel like the previous straw-syntax (async<T>) was much clearer, in terms of the effect it had on the language and on users of traits/functions. It also felt like that syntax provided more orthogonality with other language features; it felt clearer how it might interact with other features.

The high-level premise of "manual desugaring" might make sense (having to manually impl Trait and impl async Trait), if it turns out to be hard to make impl<T> async<T> Trait work.

Start with effect-polymorphic types?

TC: Starting with effect-polymorphic trait declarations certainly solves the most immediate set of problems such as AsyncRead, but given how many design questions this sort of feature raises, I wonder whether it would be better to start in the less-polymorphic place rather than adding effect polymorphism to traits which themselves live higher on the abstraction stack.

Teaching

A common criticism of Rust I've heard is that in order to code in Rust you have to learn all the concepts at once. I can easily see introducing this feature making that problem worse. Are there reasons we won't?

next vs poll_next

async Iterator is used as the main example here, but there's some debate over whether our fundamental async iterator trait should use async fn next() or fn poll_next. If we went with the latter, how would that affect use cases for the feature?


(Adding space for people to claim without conflicting)


  1. I think of this as comparable, but not the same as, how we created generators in the compiler to support the async language features without immediately stabilizing it. If we want to ship something on the critical path, it can pay off to start by stabilizing exactly what's needed first - and then slowly work our way backwards to stabilize the underlying features later on. ↩︎

Select a repo