Open exFalso opened 2 years ago
Could you reframe the title to be somewhat more productive? These are useful questions but the tone is really offputting.
Fair enough. Changed the title
If there is some form of "branching" which allows compile-time detection of which "mode" the function is called in - how is this different to macros?
Rust macros are TokenStream -> TokenStream
transformations, so although theoretically they can be almost arbitrarily powerful, in practice they are limited by
For example, the introduction of const fn
over type level computation. As presented in the charter, compile time computation can be implemented with type level computation. Just for fun (type level Turing machine) people wrote macros to make that easier. But:
If 1 and 2 can still theoretically be solved by the ingenuity of some crate author, 3 is, dare I say, almost hopeless without some leadership structure, which this initiative can serve as. I will leave the practical difficulties of 1 and 2 to actual experts.
Been thinking about this a bit more from a different angle: parametricity.
Generics are a way to implement parametric polymorphism. Or in other words, functions whose "core" behaviours are invariant under a certain input.
When you have a function such as
fn get_something<A>(map: &HashMap<String, A>) -> Option<&A> {
map.get("something")
}
this function is parametric in A
, because in a way, it doesn't matter what A
is, the function will "behave" the same. There is no way to "branch" the behaviour based on how A
is specialized. This is also true if we add trait bounds(!), we just need to deconstruct what a trait bound ultimately is (a hidden function parameter).
However, the genericity in this proposal is explicitly not parametric in this way, the intent is precisely to branch on the specialization, which makes this "genericity" more akin to C++ template specialization, than to true parametric polymorphism.
To clarify, we can look at how "polymorphic effects" could look like in Rust. In functional languages like Haskell, you can have functions such as
fmap :: Functor f => (a -> b) -> f a -> f b
or
filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]
In these functions the effects (m
and f
) are polymorphic, they are not yet specified. But this means that the implementations of these functions cannot branch on the "specialization", they must not make any assumptions on them aside from the Applicative
and Functor
constraints.
To have the above in Rust, we need "higher-kinded polymorphism", i.e. a way to create a generic out of the Result
part of Result<A, B>
, or the Future
part of Future<Item=A>
. Iirc there is already an effort underway to implement something like this in the form of GATs: https://blog.rust-lang.org/2021/08/03/GATs-stabilization-push.html.
So how would this look like for this proposal? Well, it would be quite awkward to implement, but it would clarify e.g. my 2nd question in the original post. To address the "non-effectful" version of a function we would need something like the Id
monad from Haskell, and something like do notation for the function bodies to abstract over e.g. await
or ?
, which are the effect-specific monadic bind operations. It would look something like this for the mapM
function from Haskell:
fn mapM<A, B, M: Monad>(f: fn(A)->M::App<B>, list: Vec<A>) -> M::App<Vec<B>> {
let mut result = vec![];
for a in list {
let b <- f(a); // Monadic bind, which can substitute for e.g. await or ?
result.push(b);
}
monadic_return result // No idea what this would look like
}
The Monad
trait then would implement what <-
and monadic_return
ultimately means for the effect. The non-effecting monad looks like this:
struct Id<A>(A);
and the Monad
instance is trivial. For Future<Item=A>
it would be much more interesting.
Anyway, this is all to say that to me, generics are not the right syntactic construct to implement polymorphic behaviour that branches on specialization, as this kind of behaviour doesn't abide by parametricity.
Hi, thanks for asking questions! I'll do my best to answer them, but please keep in mind that this is a work in progress, and what I'm sharing is our understanding so far.
- Can you give a real world example (like, from an actual crate) where this feature would be helpful?
Sure, in the blog post we highlighted multiple examples of people authoring crates which support both async and non-async Rust. We expect this feature would be helpful for all those crate authors - but also for most of the stdlib.
We're in a similar situation with async today as const was prior to 2018. Duplicating entire interfaces and wrapping them in block_on calls is the approach taken by e.g. the mongodb [async, non-async], postgres [async, non-async], and reqwest [async, non-async] crates [...]
- Can you clarify how effects like
async
andResult<>
are not intrinsically, fundamentally different to the non-effecting variants? Kind of what this question asks, only applied to.. well, any actual function that properly uses these effects. At some point in the.await
chain there is aFuture
which is gettingpoll()
ed. At some point in aResult
function there is anErr()
constructed. How is this reconciled with the genericity?
I'm not sure I follow, can you elaborate?
- If there is some form of "branching" which allows compile-time detection of which "mode" the function is called in - how is this different to macros?
As @louy2 mentioned in https://github.com/rust-lang/keyword-generics-initiative/issues/5#issuecomment-1197886228, macros are fundamentally limited in their functionality. They are just simple token expansions, which can't really interact with the type system in the way that we'd want to here. That means that for example things like propagating "asyncness" across multiple calls is hard. And balancing that with good ergonomics, diagnostics, and performance is nigh impossible. As we mentioned in the post, there are existing attempts in the ecosystem to provide async polymorphism entirely through proc macros, but these very clearly run into these limitations:
The ecosystem has come up with some solutions to this, perhaps most notably the proc-macro based maybe-async crate. Instead of writing two separate copies of foo, it generates a sync and async variant for you:
#[maybe_async] async fn foo() -> Bar { ... }
While being useful, the macro has clear limitations with respect to diagnostics and ergonomics. That's absolutely not an issue with the crate, but an inherent property of the problem it's trying to solve. Implementing a way to be generic over the async keyword is something which will affect the language in many ways, and a type system + compiler will be better equipped to handle it than proc macros reasonably can.
For an example of people's experience attempting to implement async polymorphism using proc macros, see: [1], [2], [3], [4], [5].
- In fact, let's turn this around: why isn't this feature a meta-language feature? Piggybacking on such a "primitive" concept as generic parameters for essentially a macro expansion step seems very off.
This seems like a rephrasing of the third question. The answer is the same: macros are insufficient to handle this, so we're looking at integrating it into the type system instead.
I hope that mostly answers your questions!
Ok so this clarifies question 1 somewhat, thank you! Looking at the examples in more detail however makes it even harder to understand what the intention of the proposal is.
Take the first example, mongodb
. The sync implementation is actually not sync! It's simply a wrapper around the tokio block_on
call... (the "sync" crate has a dependency on tokio). So we can't actually use this example as a way to understand how an "async-generic" function specializes, I'm sure the proposal isn't to extend the type system so that the compiler can insert a block_on
call...
reqwest
is a bit more interesting, however if you dig deeper into the code, it turns out the blocking implementation actually also isn't sync! There is a sync mpsc wrapper around a separate thread that in turn runs an async tokio runtime... So again, we cannot take this as an example, as there is no function we can look at that has a proper sync and async variant.
Taking a look at postgres now... and just by looking at the dependencies of the "sync" crate we can tell that it's also just a sync facade on top of an async implementation.
Ok, perhaps a "real-life" example is a weird thing to ask, given that the feature should provide a completely new mechanism for handling the sync-async fiasco. So let's try to take an existing async function and see how the sync version would look like.
From tokio_postgres
(https://docs.rs/tokio-postgres/latest/src/tokio_postgres/client.rs.html#264):
pub async fn query_one<T>(
&self,
statement: &T,
params: &[&(dyn ToSql + Sync)],
) -> Result<Row, Error>
where
T: ?Sized + ToStatement,
{
let stream = self.query_raw(statement, slice_iter(params)).await?;
pin_mut!(stream);
let row = match stream.try_next().await? {
Some(row) => row,
None => return Err(Error::row_count()),
};
if stream.try_next().await?.is_some() {
return Err(Error::row_count());
}
Ok(row)
}
Ok so let's assume for now that we somehow come up with a syntactic construct that abstracts over the bind operation .await
. Unfortunately, even this isn't sufficient at all! self.query_raw(..)
returns a RowStream
, which directly implements the futures_core::Stream
interface with poll_next
. So we have no way of specializing the original function to a "non-async" invariant, unless we literally write two different pieces of code, one using e.g. a different stream struct.
Does this clarify my 2nd question in the original post? async
functions are intimately tied to Future
s and will ultimately call some kind of poll
function, which doesn't align at all with a non-effecting function signature.
Ok so let's assume for now that we somehow come up with a syntactic construct that abstracts over the bind operation
.await
. Unfortunately, even this isn't sufficient at all!self.query_raw(..)
returns aRowStream
, which directly implements thefutures_core::Stream
interface withpoll_next
. So we have no way of specializing the original function to a "non-async" invariant, unless we literally write two different pieces of code, one using e.g. a different stream struct.Does this clarify my 2nd question in the original post?
async
functions are intimately tied toFuture
s and will ultimately call some kind ofpoll
function, which doesn't align at all with a non-effecting function signature.
So for some context here: I'm also a member of the Rust Async WG, so I can speak at least to the intent our group has. In the case of Stream
, we've recently renamed this to be AsyncIterator
, to properly reflect that is in fact an async version of Iterator
. We don't yet have async traits, but when we do the poll_next
method will be replaced with an async fn next
in the trait.
If the database driver chose to implement itself in terms of keyword generics, the method could choose to either return a sync or async iterator, depending on which mode it was compiled in.
Regarding the use of block_on
in the internals of existing crates: we posit that the only reason why this is the case is because there is a desire by crate authors to balance the need to provide a non-async version of the crate, with the need to keep the maintenance burden in check. Taking an existing async API and wrapping it in a block_on
call seems like a reasonable tradeoff.
We expect that keyword generics would make supporting this even easier, and would remove the existing downsides of wrapping async APIs in block_on
calls.
So how would the keyword-generic version of query_one
look like?
I think we need to differentiate between "combinators" and "primitives". "Primitives" are those directly implementing Future
, Stream
(AsyncIterator
), etc. In the case of query_one
, RowStream
is a primitive, and query_one
is a combinator. For primitives like RowStream
, we need a way for the author to supply effectful or effectless versions of implementations, for the compiler to specialize with. For combinators, we want those which can be polymorphic over the effect be such.
To that end, I don't think the keyword-generic version of query_one
would be very different. That is, assuming Stream
will be able to gracefully turn into Iterator
, which I believe is what async WG is trying at?
Possibly we can have a simple single-threaded local executor block the primitives, and make that the blessed blocking specialization, or the default blocking specialization until the author supplies one.
The status quo in Rust is keyword and conversion driven higher-kinded polymorphism, with only built in higher kinded types, that is: for
loop for impl IntoIterator<IntoIter=I>
, ?
for impl Try<Residual=R>
, and await
for impl Future<Output=T>
, neglecting the inconsistent formulation of higher-kinded-ness. I feel like this initiative asks for a re-evaluation of that, and that is both exciting and uneasy.
So how would the keyword-generic version of query_one look like?
Likely exactly the same as the existing async variant, with the addition of the keyword-generic param being carried. There are some restrictions though: generic async code can't use async-only concurrency operations, so limitations definitely apply. And the language is currently still missing primitives like async closures, traits, drop - so the code would likely change based on that too.
But assuming async reaches feature parity with non-async Rust, then going from async -> maybe async should mostly only require making the async keyword generic.
That is, assuming Stream will be able to gracefully turn into Iterator, which I believe is what async WG is trying at?
Yep, that's right. We're definitely wondering whether we could expose both the sync and async variants using a single definition, something along the lines of:
async<A> trait Iterator {
type Item;
async<A> fn next(&mut self) -> Self::Item;
}
Possibly we can have a simple single-threaded local executor block the primitives, and make that the blessed blocking specialization, or the default blocking specialization until the author supplies one.
To clarify: we expect concrete types to be able to compile down into their sync counterparts. Take for example std::fs::File
: right now it's sync only. But if we made it generic over "asyncness" you could select the async variant, and any code that's generic over asyncness could switch between the sync and async version depending on which variant is selected.
To clarify: we expect concrete types to be able to compile down into their sync counterparts. Take for example std::fs::File: right now it's sync only. But if we made it generic over "asyncness" you could select the async variant, and any code that's generic over asyncness could switch between the sync and async version depending on which variant is selected.
Now that is a surprise to me, since I have been thinking about only the async fn
side of things. By "sync only", do you mean the difference between std::fs::File
and async_std::fs::File
, making the former sync only and latter async only? And that the compiler would be responsible for choosing between those two, depending on the operations which have been called on the File
type? If that's the case, will async_std::fs::File
become included in std
as a variant of std::fs::File
as part of this initiative? How would that work with File
types in other runtimes, e.g. tokio::fs::File
?
Excuse me, but you don't have to answer those questions immediately. But do those questions indicate I am on the right mental track?
That is a very reasonable user story, and one I probably would like to have, but it does make the theory side a lot harder to comprehend for me. I was only thinking about types on which the keywords would directly operate. But now that you have mentioned, I have realized that indeed the infection of async
extends to struct
. In turn, this initiative seems to be even more ambitious than how I recognized it.
async
andResult<>
are not intrinsically, fundamentally different to the non-effecting variants? Kind of what this question asks, only applied to.. well, any actual function that properly uses these effects. At some point in the.await
chain there is aFuture
which is gettingpoll()
ed. At some point in aResult
function there is anErr()
constructed. How is this reconciled with the genericity?