owned this note
owned this note
Published
Linked with GitHub
# Keyword Generics
_Not being able to write code which is generic over keywords limits what we can express in Rust, and we should seek to improve that._ _Authored by: Oli and Yosh._
## Introduction
We're in the process of adding new features to Rust. The Const WG is creating an extension to Rust which enables arbitrary computation at compile time.
While the Async WG is in the process of adding capabilities for asynchronous computation. We've noticed that both these efforts have a lot in common, and may in fact require similar solutions. This document describes a framework for thinking about these language features, describes their individual needs, and makes the case that we should be considering a generalized language design for "keywords" (aka "definitely not effects"), so that we can ensure that the Rust language and standard library remain consistent in the face of extensions.
## A broad perspective on language extensions
`const fn` and `async fn` are similar language extensions, but the way they extend the language is different:
- `const fn` creates a *subset* of "base Rust", enabling functions to be executed during compilation. `const` functions can be executed in "base" contexts, while the other way around isn't possible.
- `async fn` creates a *superset* of "base Rust", enabling functions to be executed asynchronously. `async` types cannot be executed in "base" contexts [^bridge], but "base" in `async` contexts _is_ possible.
[^bridge]: In order to bridge async and non-async Rust, functionality such as `thread::block_on` or `async fn` must be used, which runs a future to completion from a synchronous context. `const` Rust does not require such a bridge, since the difference in contexts is "compile time" and "run-time".
```
+---------------------------+
| +-----------------------+ |
| | +-------------------+ | | - numbers
| | | | | | - containers (soon)
| | | const Rust |-------{ - functions
| | | | | | - control flow
- networking | | +-------------------+ | | - traits
- filesystem | | | | - types
- threads }--------| "base" Rust | |
- system time | | | |
- statics | +-----------------------+ |
| | - ad-hoc concurrency
| async Rust |---{ - ad-hoc cancellation
| | - ad-hoc parking/unparking
+---------------------------+
```
In terms of standard library these relationships also mirror each other. "Base" Rust will want to do everything during runtime what `const` rust can do, but in addition to that also things like network and filesystem IO. Async Rust will in turn want to do everything "base" Rust can do, but in addition to that will also want to introduce methods for ad-hoc concurrency, cancellation, and execution control. It will also want to do things which are blocking in "base" Rust as non-blocking in async Rust.
And it doesn't stop with `const` and `async` Rust; it's not hard to imagine that other annotations for "can this panic", "can this return an error", "can this yield values" may want to exist as well. All of which would present extensions to the "base" Rust language, which would need to be introduced in a way which keeps it feeling like a single language - instead of several disjoint languages in a trenchcoat.
## Implementations notes for eval
[Recently](https://rust-lang.zulipchat.com/#narrow/stream/146212-t-compiler.2Fconst-eval/topic/complexity.20of.20constness.20in.20the.20type.20system) I (Oli) have proposed to add a magic generic parameter on all `const fn foo`, `impl const Foo for Bar` and `const trait Foo` declarations. This generic parameter (called `constness` henceforth) is forwarded automatically to all items used within the body of a const fn. The following code blocks demonstrates the way I envision this magic generic parameter to be created (TLDR: similar to desugarings).
### Examples
#### Trait declarations
```rust
const trait Foo {}
```
becomes
```rust
trait Foo<constness C> {}
```
#### Generic parameters
```rust
const fn foo<T: Bar + ~const Foo>() {}
```
becomes
```rust
fn foo<constness C, T: Bar + Foo<C>>() {}
```
#### Function bodies
```rust
const fn foo() {
bar()
}
```
becomes
```rust
fn foo<constness C>() {
bar::<C>()
}
```
#### Call sites outside of const contexts
```rust
fn main() {
some_const_fn();
}
```
becomes
```rust
fn main() {
some_const_fn::<constness::NotConst>();
}
```
#### Call sites in const contexts
```rust
const MOO: () = {
some_const_fn();
}
```
becomes
```rust
const MOO: () = {
some_const_fn::<constness::ConstRequired>();
}
```
### Implementation side:
We add a fourth kind of generic parameter: `constness`. All `const trait Foo` implicitly get that parameter. In rustc we remove the `constness` field from `TraitPredicate` and instead rely on generic parameter substitutions to replace constness parameters. For now such a generic parameter can either be `Constness::Required`, `Constness::Not` or `Constness::Param`, where only the latter is replaced during substitutions, the other two variants are fixed. Making this work as generic parameter substitution should allow us to re-use all the existing logic for such substitutions instead of rolling them again. I am aware of a significant amount of hand-waving happening here, most notably around where the substitutions are coming from, but I'm hoping we can hash that out in an explorative implementation
## Conditions for keywords
When comparing `const fn` and `async fn` we can observe that keywords may find themselves in three different states. Let's start with `async fn`, we can observe that there are two states in which it can find itself using today's syntax:
```rust
// Always non-async
fn copy<R, W>(reader: &mut R, writer: &mut W) -> io::Result<u64>
where
R: Read + ?Sized,
W: Write + ?Sized,
{}
// Always async
async fn copy<R, W>(reader: &mut R, writer: &mut W) -> io::Result<u64>
where
R: AsyncRead + ?Sized,
W: AsyncWrite + ?Sized,
{}
```
Assuming we'd want to enable `async` modifiers on traits, we might instead be able to the async variant as:
```rust
// Always async
async fn copy<R, W>(reader: &mut R, writer: &mut W) -> io::Result<u64>
where
R: async Read + ?Sized,
W: async Write + ?Sized,
{}
```
For `const` there are two states as well, but they're different from the states of `async`:
```rust
// Always non-const
fn add<T: Add>(a: T, b: T>) -> T::Output {
a + b
}
// This will be `const` if called in const contexts, non-const if
// called in non-const contexts.
const fn add<T: ~const Add>(a: T, b: T>) -> T::Output {
a + b
}
```
These states are different from async Rust. We can plot them as such:
| | keyword `async` | keyword `const` |
| --------------------------------- | -------------------- | --------------------- |
| **keyword never applies** | `fn foo() {}` | `fn foo() {}` |
| **keyword always applies** | `async fn foo() {}` | `const FOO: () = {};` |
| **keyword conditionally applies** | `~async fn foo() {}` | `const fn foo() {}` |
For the `async` keyword, we're exploring whether we can make it apply conditionally as well. Because it's a superset of Rust, with wide ranging implications, just making it "async depending on the context you call it in", similar to `const` could have surprising behaviour.
Going back to the previous example, but this time allowing the same function to be called asynchronously and synchronously:
```rust
async fn copy<R, W>(reader: &mut R, writer: &mut W) -> io::Result<u64>
where
R: ~async Read + ?Sized,
W: ~async Write + ?Sized,
{
}
```
Now, if we just allowed non-async readers and writers, we could run into trouble. Consider the following function body:
```rust
let x = reader.read_line().await;
let z = writer.write(x);
let y = reader.read_line().await;
z.await
```
if the reader and writer were in fact synchronous and this were implemented naively, this could already block at the write call instead of the await. Instead what actually happens is that `z` is a "fake future", so basically just an argumentless `FnOnce` closure of the actual logic and `z.await` executes that closure.
The chance of this occurring would would be highest specifically for types which were implemented _incorrectly_: in order for async polymorphism to work, the behavior between async and non-async code paths must be identical. For async this means that side-effects should not start _until `.await` has been called._ This should be not expressable for any code written using async polymorphism. And should be considered a bug for code written using _async overloading_ (more on that in a next section) since behavior should match.
Given we're seeking to provide a complete stdlib experience for _all_ variants of Rust, we have a fair amount of control over this experience through the stdlib, and in addition to guidance we can provide assurances which will limit the practicality of this occuring in the wild.
## Implications of the effect hierarchy
One implication of the subset-superset relationship is that code which is generic over effects will not be able to use all functionality of the superset in the subset case. Though it will need to use the _syntax_ of the superset.
Take for examle the following code. It takes two async closures, awaits them, and sums them:
```rust
// Sum the output of two async functions:
~async fn sum<T>(
lhs: impl ~async FnMut() -> T,
rhs: impl ~async FnMut() -> T
) -> T {
let lhs = lhs().await;
let rhs = rhs().await;
lhs + rhs
}
```
One of the benefits of async execution is that we gain _ad-hoc concurrency_, so we might be tempted to perform the comptutation of `lhs` and `rhs` concurrently, and summing the output once both have completed. However this should not be possible solely using effect polymorphism since the generated code needs to work in both async and non-async contexts.
```rust
// Sum the output of two async functions:
~async fn sum<T>(
lhs: impl ~async FnMut() -> T,
rhs: impl ~async FnMut() -> T
) -> T {
let (lhs, rhs) = (lhs(), rhs()).join().await;
// ^^^^^^^
// error: cannot call an `async fn` from a `~async` context
// hint: instead of calling `join` await the items sequentially
// or consider writing an overload instead
lhs + rhs
}
```
And this is not unique to `async`: in maybe-`const` contexts we cannot call functions from the super-context ("base Rust") since those cannot work during `const` execution. This leads to the following implication: __Conditional effect implementations require the syntactic annotations of the super-context, but cannot call functions which exclusively work in the super-context.__
## Overloading Keyword Generics
In the previous section we saw that we cannot use `join` to await two futures concurrently because in "base Rust" we cannot run two closures concurrently. The capabilities introduced by the superset (async) have no counterpart in the subset ("base Rust"), and therefor we cannot write it.
But sometimes we _do_ want to be able to specialize implementations for a specific context, making use of the capabilities they provide. In order to do this we need to be able to declare two different code paths, and we propose _effect overloading_ as the mechanism to do that.
This problem is not limited to async Rust either; const implementations may want to swap to platform-specific intrinsics at runtime, but keep using portable instructions during CTFE. This is only a difference in implementation, and should not require users to switch between APIs.
The way we envision _effect overloading_ to work would be similar to specialization. A base implementation would be declared, with an overload in the same scope using the same signature except for the effects. The compiler would pick up on that, and make it work as if the type was written in a polymorphic fashion. Taking our earlier example, we could imagine the `sum` function could then be written like this:
```rust
// Sum the output of two functions:
default fn sum<T>(
lhs: impl FnMut() -> T,
rhs: impl FnMut() -> T
) -> T {
lhs() + rhs()
}
async fn sum<T>(
lhs: impl async FnMut() -> T,
rhs: impl async FnMut() -> T
) -> T {
let (lhs, rhs) = (lhs(), rhs()).join().await;
lhs + rhs
}
```
We expect _effect overloading_ to not only be useful for performance: we suspect it may also be required when defining the core (async) IO types in the stdlib (e.g. `TcpStream`, `File`). These types carry extra fields which their base counterparts do not. And operations such as reading and writing to them cannot be written in a polymorphic fashion.
__While we expect a majority of ecosystem and stdlib code to be written using _effect polymorphism_, there is a point at which implementations do need to be specialized, and for that we need _effect overloading_.__
## Grouping Keyword Generics
We expect it to be common that if a function takes generics and has conditional keywords on those, it will want to be conditional over *all* keywords on those generics. So in order to not have people repeat params over and over, we should provide shorthand syntax.
Here is the "base" variant we're changing:
```rust
// without any effects
fn find<I>(
iter: impl Iterator<Item = I>,
closure: impl FnMut(&I) -> bool,
) -> Option<I> {
...
}
```
We could imagine wanting a fallible variant of this which can short-circuit based on whether an `Error` is returned or not. We could imagine the "base" version using a `TryTrait` notation, and the "effect" version using the `throws` keyword. Both variants would look something like this:
```rust
// fallible without effect notation
fn try_find<I, E>(
iter: impl TryIterator<Item = I, E>,
closure: impl TryFnMut<(&I), E> -> bool,
) -> Result<Option<I>, E> {
...
}
// fallible with effect notation
fn try_find<I, E>(
iter: impl Iterator<Item = I> ~yeets E,
closure: impl FnMut(&I) ~yeets E -> bool,
) -> Option<I> ~yeets E {
...
}
```
For `async` we could do something similar. The "base" version would use `AsyncTrait` variants. And the "effect" variant would use the `async` keyword:
```rust
// async without effect notation
fn async_find<I>(
iter: impl AsyncIterator<Item = I>,
closure: impl AsyncFnMut(&I) -> bool,
) -> impl Future<Output = Option<I>> {
...
}
// async with effect notation
~async fn async_find<I>(
iter: impl ~async Iterator<Item = I>,
closure: impl ~async FnMut(&I) -> bool,
) -> Option<I> {
...
}
```
Both the "fallible" and "async" variants mirror each other closely. And it's easy to imagine we'd want to be conditional over both. However, if neither the "base" or the "effect" variants are particularly pleasant.
```rust
// async + fallible without effect notation
fn try_async_find<I, E>(
iter: impl TryAsyncIterator<Item = Result<I, E>>,
closure: impl TryAsyncFnMut<(&I), E> -> bool,
) -> impl Future<Output = Option<Result<I, E>>> {
...
}
// async + fallible with effect notation
~async fn try async_find<I, E>(
iter: impl ~async Iterator<Item = I> ~yeets E,
closure: impl ~async FnMut(&I) ~yeets E -> bool,
) -> Option<I> ~yeets E {
...
}
```
The "base" variant is entirely unworkable since it introduces a combinatorial explosion of effects ("fallible" and "async" are only two examples of effects). The "effect" variant is a little better because it composes, but even with just two effects it looks utterly overwhelming. Can you imagine what it would look like with three or four? Yikes.
So what if we could instead treat effects as an actual generic parameter? As we discussed earlier, in order to lower effects we already need a new type of generic at the MIR layer. But what if we exposed that type of generics as user syntax too? We could imagine it to look something like this:
```rust
// conditional
fn any_find<I, effect F>(
iter: impl F * Iterator<Item = I>,
closure: impl F * FnMut(&I) -> bool,
) -> F * Option<I> {
...
}
```
There are legitimate questions here though. Effects which provide a superset of base Rust may change the way we write Rust. The clearest example of this is `async`: would having an `effect F` require that we when we invoke our `closure` that we suffix it with `.await`? What about a `try` effect, would that require that we suffix it with a `?` operator? The effects passed to the function might need to change the way we author the function body [^implication].
[^implication]: One interesting thing to keep in mind is that the total set of effects is strictly _bounded_. None of these mechanisms would be exposed to end-users to define their own effects, but only used by the Rust language. This means we can know which effects are part of the set. And any change in calling signature (e.g. adding `.await` or `?`, etc.) can be part of a Rust edition.
Another question is about _bounds_. Declaring an `effect F` is maximally inclusive: it would capture all effects. Should we be able to place restrictions on this effect, and if so what should that look like?
## Open Questions
- There is a difference between `File` and `async File`. Files on Windows must be opened in "async mode" and forever remain that way. How do we integrate that distinction into the system?
- Is taking a generic effect at the type-level enough for this?
- How would that interact with effect overloading?
- Should we make the doc more RFC-like?
- Our "implementation" section could probably use more meat?
- We're not listing drawbacks
- Pretty sure we would need to rework when we perform the `async/.await` in the compiler.
- Added syntax / features is another; though that's inherent to the feature and if it's not a language feature people end up implementing worse ad-hoc versions of this themselves.
- We're also not listing future possibilities
- Though I guess we're riffing quite a bit on a shiny future already, so do we even need this?
- Maybe it's fun to spell out the interaction with the `contexts`/`capabilities` work? Conceptually they're related features, even if they don't actually overlap.
- What other sections should we have?
- Should we highlight an alternatives section?
- In particular, it might be worth highlighting the "do nothing" case here.
- Should we list the effects we know of? Maybe in an appendix?
- Should we have "applying the design" sections?
- E.g. explain how the system we've designed would work for the different keywords?
- This might be helpful to make it feel more tangible. `const` and `async` extend Rust in opposite directions after all.
- In particular: we might want to discuss async Rust and const Rust separately. Also so we can explain the exact design and considerations.
- Because async Rust has `.await` notations in the function body there might be more to it.
- Bridging the generics `fn foo<effect F>` notation with the `~const` / `~async` notation isn't super clear right now?
- Do we need both? Can we combine them somehow? Can we remove one?
## Scratchpad
```rust
const fn foo() { // maybe const context
let file = fs::open("hello").unwrap();
// compile error! => `fs::open` is not a maybe const function!
}
~base fn foo() { // assume `const` as the default; invert the relationship
let file = fs::open("hello").unwrap();
// compile error! => `fs::open` is
// a base function which cannot be
// called from a maybe base context
}
~async fn foo() {
let file = my_definitely_async_fn().await;
// compile error!
}
```
```rust
fn foo<effect F: const>(f: impl F * Fn() -> ()) {
f();
}
fn foo<effect F: const>(f: impl effect<F> Fn() -> ()) {
f();
}
// compile error!
// effect `F` is maximally inclusive!
// missing `.await`
// maximally inclusive effects are not forward compatible! - once
// we add a new effect existing code will not compile!
// The calling convention may change each time we add a new effect!
fn main() {
foo(some_fn); // Infer all effects to Not*
}
```
Adding new effects to the language does not break anyone, because effects must be opted in.
Adding a new effect to the opt-in effect generics of a function will break callers that infer
the effect to be required.
Editions can add new effects to the list of defaults.
this is not a breaking change because calling crates can stay on old editions, even if the lib crate got updated to a newer edition. THe lower edition crates don't see the defaults and turn them off.
## The plan
0. keyword generics initiative repo
1. constness generic param to simplify `~const` implementation
2. lang team MCP for keyword generics, but only `async` and `const` for now, further keywords need to be MCPed seperately
3. `async_select` in the spirit of `const_eval_select`
Defer:
- how to do overloading - whether to use `match` on keyword params, or other stuff. We don't need to decide now.
Google Drive
Gist
Clipboard
Sign in with Wallet
