I mostly agree with all of this. Your set of minimal features seems exactly correct as the focus for an MVP.
My one objection is that, even though recursion-based variadics are unsuitable for an MVP, I don’t think we should rule out ever adding them. Notably, they would allow iterating over tuples out of order, which is something that that minimal feature set can’t express. 90% of use cases likely don’t need that, but it would be nice to have a solution eventually for the few cases that do. And none of the “dealbreakers” seem truly insurmountable IMO.
For the First Class Types section, you implement generic types as a difficult-to-parse type function and then state that the problem is "the function doesn’t guarantee it in a way the compiler can easily parse"
Why can't it be something simpler to parse?
fn unwrap_all<Ts: Tuple>(options: (Option<Ts<i>> for i in 0..Ts::LEN)) -> Ts {
(options[i].unwrap() for i in 0..T::LEN)
}
(I'm interested because this is a lang-modifying translation of my typle crate).
I think the variadic recursion isn't nearly as bad as suggested. The strongest point to me is "I really don't want to have to write out trait recursion like this every time", but that's not a technical "won't work" reason.
For example,
We replaced an iterative loop with a tail-recursive loop (well, almost tail-recursive). This is intuitive for users of functional languages, but it’s not quite idiomatic Rust.
Sure, but people can learn. There's lots of things that are nicer expressed as recursion anyway, and if we're discussion hypothetical variadic generics, I'm fine assuming other easier hypothetical things like become, which will change certain things that today can't be recursion into things that plausibly will become idomatically done via recursion.
We’re placing a lot of faith in the inliner. If our tuple has 12 items, that’s 12 levels of inlining the compiler must perform before it can even hope to optimize that function.
Sure, but heavy dependence on the inliner is already normal in rust. You already need to inline 12 times in derive(PartialOrd) for a 12-field tuple struct, for example, to get good codegen. And that's completely fine, especially since we have a MIR inliner. And again become could encourage this strongly too.
We’re also generating a lot of ELF symbols (one per tuple item) that we hope will get garbage collected away.
If they're MIR inlined then they don't need to show up as ELF symbols at all, because we don't generate functions for them at the LLVM level.
Our core logic is split across two functions:
(T0, ...Ts)has the reduction function and()has the initial accumulator.
But that also means I can have (T0, ...Tmid, TN) as the reduction function and (Tonly,) as the initial, which is really helpful in writing things that want to be non-empty to not have to return Option, for example.
Similarly, variadic (A, B, C, D, ...) -> ((A, B), (C, D), ...) would be a good thing to be able to express, and it's done really naturally with trait matching but much less obviously with a for-loop-style single reduction.
Rust does not guarantee that the elements of a tuple are contiguous.
Not a problem if it's a parameter pack rather than a subobject reference.
let (...element_refs) = foo_ref; can turn a reference-to-tuple into a pack of references via match ergonomics, and you can then recurse over that pack however, such as by making an owned tuple of the references.
After all, even without variadic generics I think it'd be nice to be able to do things like
let (...elems) = my_tuple;
let my_array = [...elems];
splatting-style, to use collect up and expand packs of things.
The problem is that the compiler has no way to unify the associated type of
WrapAllwith the requirements ofUnwrapAll.
If this already doesn't work non-variadically, though, perhaps the answer is that it wants ways to express that kind of thing. If it wants "always an option", perhaps that's more GAT-like functionality or similar, so that it sees a single type Foo<T> = Option<T>; instead of a bunch of unconnected things.
That said, I think I still agree with your conclusion, especially this general statement.
If they were easy, they would have been implemented ten years ago.
There's no "oh this should 'just'" solution here, and we'll absolutely want a "the easy things are easy" solution, not just the "hard things are possible" one (though we need that too).
Fwiw variadic recursion is close to how Haskell implements one of its deriving mechanisms.
The original paper is here: https://dreixel.net/research/pdf/gdmh.pdf and some more documentation - here GHC.Generics - HaskellWiki and here GHC.Generics
This is not just variadic generics since it gives access to type information, field names, etc.
From the developer end point of view it gives much better experience compared to dealing with raw tokens in syn, you make a typeclass (a trait), implement it for a small handful of items (metainfo wrappers, algebraic products, algebraic sums and the field wrappers) and you get an ability to derive a related typeclass with minimum amount of code.
Cons for this approach is that it puts a bunch of pressure on compiler being sufficiently smart at optimizing it. In ghc compilation time is super linear and feels somewhat slow around 200-300 fields.
I have some code I wrote to demonstrate this concept at an online Rust meetup where all the boilerplate was written by hand and it kind of works. Again, not quite variadic generics since I was talking about trait deriving, but pretty close.
To take a full advantage of this approach you'll want some kind of type level strings and numbers so you can access field names/indices - my current implementation uses dummy unit structs with "zero sized type literal" trait that does fn(PhantomData<FieldName>) -> &'static str. Works, but not as nice.
Concerns are:
- compilation time
- amount of generated code - 3 copies - for
&,&mutand owning functions - potentially confusing error messages
Yeah, one reason I like the "pack" concept over the "it's literally a tuple" approach is that it potentially gives a way to include things like field: value in a pack that could be expanded out into another struct literal or maybe a whole enum variant for variadic enums.
I still think the obsession with preventing post-monomorphization errors is severely limiting Rust's expressivity.
We still can't do something as simple as "add two const generic parameters together", because the naive approach would allow post-mono errors and the alternatives are dissatisfying (search this document for "huge design issue").[1] Instead we have a const generics feature that works for very specific basic use cases and nothing else.
And @PoignardAzur thinks we can't have first-class types because of (among other reasons) post-mono errors, which in turn means we can't have powerful variadic generics. Instead @PoignardAzur suggests a minimal version of variadic generics which looks like it'll support very specific basic use cases and nothing else. (Where 'something else' would include, as mentioned in the Reddit thread, indexing, filtering, reordering, etc.)
Except Rust already has post-monomorphization errors…
fn foo<const A: usize>() {
const { assert!(A == 0); }
}
And Rust already has macros, which are used for some of the same purposes that first-class types would be used for. Not only can they input and output arbitrary syntax, they can run arbitrary code, so of course badly written ones have terrible error messages. On the other hand, we’ve also seen that the power of procedural macros allows diligent macro authors to provide better error messages than in less-powerful systems. Macros also have the nice debugging feature that you can use -Zunpretty=expanded to see the result of macro expansion; I wish there was something similar for generics.
And Rust already has Turing-complete recursive generics, leading to crates like typenum to approximate const generics and frunk to approximate variadics. This coding style is quite powerful: far less nice than procedural macros, but still Turing-complete. It results in code that technically can't produce post-mono errors, but at the cost of inscrutable interfaces, which I’d argue are worse. At least the impact on the community is limited by these crates being unpopular (because of the inscrutability).
Given that all these things are already in the language, I strongly disagree with @PoignardAzur’s statement that adding first-class types would “fundamentally change Rust as a language, its priorities, its philosophy, and its target demographics”. From an implementation perspective, sure, they would be a huge feature. But from a user’s perspective, not so much. For one thing, I think they could be integrated with the existing procedural macro system. But even if that weren’t the design approach, the feature would be comparable in user-perceived power and complexity to macros, just nicer. If done right, it should allow the patterns people are already using to be expressed in a way that’s easier to understand.
Sorry for the rant.
To be fair, there are also implementation issues blocking const generic expressions, as discussed in the same document. ↩︎
I'm torn on this.
On one hand, I have a background in classic C++, and it is nice that Rust has few post mono errors in comparison. Hard to comprehend errors in C++ that fill pages and pages of the terminal with references to the deep internals of templates in Boost are not a great user experience. (I have not coded C++ with concepts yet, maybe that is much better, I don't know.) I do not long for SFINAE and things of that ilk. Rust traits and impls that just work if their definitions compile are great.
On the other hand, not having variadics in particular does feel limiting. And writing macros to instantiated for tuples up to N tends to lead to poor compile time, and for more complex cases you can easily get combinatorial explosions of combinations (when the traits accepted are of more than one type). And it leads to poor compile times as a result and poor error messages.
Is there space for a design that gives pre-mono errors most of the time, but with an escape hatch for the more complex cases? I'm not a language designer, so I really don't have any clue if this is possible.
Just as proc macros shouldn't be your first option, solutions with post-mono errors shouldn't either. But they should be there when you need them.
This sounds like a great time to link my post about this from when we stabilized that const { assert!(...) }: https://github.com/rust-lang/rust/pull/104087#issuecomment-1453028838
(And obligatory note that those post-mono errors actually existed before stabilizing inline const, they were just more annoying to produce.)
See the linked comment abve for more, but I think the real problem in C++ here isn't actually the post-mono errors, but the ad-hoc extension points. C++ can't tell the difference between me writing x.length() and it being exactly correct because that's what the type is supposed to implement and that just being completely wrong because of course it should have been x.len(). That behaviour in C++ means that compiling the library can't tell you if you typo'd an identifier, which loses one of the most important reasons for even using a precompiled language in the first place.
But getting an error about "Couldn't make a [T; N * M] because the multiplication overflowed" post-mono feels much less impactful overall. It might even be better than needing a where (): MultiplyWithoutOverflow<N, M> bound.
Rust has a sophisticated type system, which post-mono errors fundamentally don’t play well with. Coherence/the overlap check can’t take them into account, and they trigger even in dead code. These issues mean that less code can compile, compared to an equivalent feature based on pre-mono errors. (The document you link mentions this problem: “In general the trait system should be able to fail in arbitrary ways without causing compilation to fail.”)
I don’t entirely disagree with your post. There is a place for PMEs IMO, including in advanced uses of const generics. IMO, the shiny const generics future would ideally involve a combination of pre-mono (via pattern types) and post-mono errors. But post-mono alone is just not enough, it doesn’t play well with the rest of Rust.
I don't much disagree with your post either. If a larger subset of use cases can be made to work without post-mono errors, that's always a good thing.
Though, I'll point out that much of that document is about implementation challenges rather than truly fundamental type system limitations. Of course, implementation challenges matter. But post-mono is not the only approach with implementation challenges. The document also expresses skepticism about a termination checker, which would be a necessary component of a pattern-type-based pre-mono approach. *shrug*