I appreciate the attention to the social and organizational aspect of implementation here. Every piece of software has a somewhat nonlinear curve in the difficulty of adding new features as the codebase gets more complex, but it's especially bad in compilers. Adding something as complex and all-pervasive as dependent types - and this is dependent types, just in a Rusty costume! - is, clearly, on another level. I'm very excited for a more capable incarnation of this feature, but I'm not holding my breath for its stabilization.
> And before that, in the pre-alpha days of Rust, arrays were defined with a variadic macro. The /* something */ above was a [T, ..$N], where T is the type, and ..$N defines a range (I believe -- old Rust is weird) up to the number of specified elements.
This is just a misunderstanding. The `..$N` was just the array length syntax. Now the syntax is `[T; N]` with no change in meaning - there was no variadic magic.
Great article! I would just like to add to the point about C# generics.
> "generics in Rust are zero-cost abstractions. rustc performs a process called monomorphization, where generic items (methods, structs, etc.) are "flattened" at compile time into only the types that are used. (Compare this to a language like C#, where generics are evaluated at runtime.)"
I believe that generics are evaluated at runtime in C# due to just-in-time compilation. C#'s implementation of generics (which they call reification) is more similar to Rust's monomorphization than, say Go and Java's lookup table type erasure approach.
Good point! Using dyn Trait syntax (aka, dynamic dispatch) uses type erasure and is kind-of like Go and Java's implementation of Generics I guess. You can definitely use that in Rust but the article is about impl Trait syntax which is for concrete types (not type erased)
The only nitpick I'd have is that `impl Trait` doesn't necessarily imply a concrete type. Or rather it does, but in so far `Box<dyn Trait>` is also a concrete type :)
That means that you can have a function that returns `-> impl Trait` with a concrete implementation because it has a single return value, but if you add a second and don't want to create an enum for a simple version of static dispatch, you can change the returned values to be trait objects and the callers don't break.
I think this is only true in C# for value types - I think the same generated code is used for all reference types, so eg. `List<object>` uses the same code as `List<string>` but different from `List<int>`.
This is to be expected with what are essentially pointers to heap objects. The actual code being executed only manipulates machine-word-sized values with the same semantics, so it makes little sense to have copies of the same code.
Well, yes. But you can't devirtualize until you know the types as well as possible, which is after "de-generifying", so as to speak (I don't really know what terminology .NET uses for this).
const functions are really 'maybe const' functions since they can be called with runtime arguments or compile time arguments.
If you want your const function to depend on some trait, for it to even be possible at compile time, those traits would need to be possible to use at compile time too.
But the same idea holds as arguments, we might just want to use it at runtime too, in which case it needs to be a 'maybe const' bound for the const function to be flexible enough for us.
From the naive lens of someone writing C++, this all looks... extremely elementary. The first half of the blog post touts monomorphization, which (to my otherwise uneducated eyes) is nothing other than what template instantiation does in C++, no? And the second half is dedicated to the technicalities of why it's hard to make the compiler support the equivalent of the following C++ signature:
template<int N>
std::array<int, N+1> foo();
I suppose there's some unmentioned "we don't want Rust generics to be Turing complete" in the deeper reasons, but... It sure makes me feel like either I'm taking a lot of things for granted in C++ or Rust painted itself into a strange corner.
Am I missing something that makes Rust generics way more complicated than C++ templates? Or is retrofitting them into Rust really such a hellish adventure?
I think that this is a great example of some of the tradeoffs between Rust and C++!
The main difference is that the C++ code will check everything at instantiation time, and C++ templates can lead to nasty error messages because it's hard to assign _blame_ to either the caller or the callee.
This code will only typecheck if N is even. But that's not written down anywhere, and if I tried to pass in an odd N, then I'd get some template error telling me that _something_ went wrong, and it may even give me a trace. But that error doesn't tell me whether it's a bug in foo, or a bug in how I'm using foo. If it's a bug in using foo, it certainly doesn't tell me how to fix things.
Rust takes the approach of requiring that you specify constraints on generic parameters up front. It then checks whether the function's body will compile _for all_ possible generic parameters, given the constraints. This is much easier to use from a usability perspective, since you know whether to blame the caller or the callee, and it explicitly enumerates the requirements that you need to meet (i.e. the constraints on the generic parameter) in order to get your code to compile. This is why C++ lets you do many more crazy things with templates than Rust currently allows you to with generics (and why is moving more slowly to add things to its type system).
C++'s alternative approach gives up usability for extra flexibility. Neither approach is "right." They're just different trade-offs.
(As an aside, it turns out that the Rust type system was Turing complete even before const generics were added.)
Is monomorphization truly 0-cost? I thought it's basically a different flavor of optimizing inliner (somewhat more under user control) which has a similar tradeoff curve between whether it's better to stamp out a monomorphized version of a function or if it's better to operate on more opaque type signatures.
It’s zero-cost compared to manually copy-pasting code (manual monomorphization). Zero-cost means that it doesn’t cost more than whatever you would do if you didn’t have the feature.
> Let's look at a brief example to get familiar with syntax:
Followed by no explanation, nor is there a target audience laid out in the article.
Now I'm left simply thinking it's a terrible article because it's starts with a poor explanation targeted at anyone.
If it started with "if you're familiar with C++/go/c#/whatever then this syntax should appear familiar", then I would have quietly closed the article. Unfortunately my impression of the article is poor, and continues to be poor of the rust community because of constantly putting out content with this style of hand wavy introduction that makes outsiders feel more alienated.
At least haskellers (of which I am not one) manage to be aware of this trope in their own community.
25 comments
[ 6.5 ms ] story [ 64.8 ms ] threadThis is just a misunderstanding. The `..$N` was just the array length syntax. Now the syntax is `[T; N]` with no change in meaning - there was no variadic magic.
> "generics in Rust are zero-cost abstractions. rustc performs a process called monomorphization, where generic items (methods, structs, etc.) are "flattened" at compile time into only the types that are used. (Compare this to a language like C#, where generics are evaluated at runtime.)"
I believe that generics are evaluated at runtime in C# due to just-in-time compilation. C#'s implementation of generics (which they call reification) is more similar to Rust's monomorphization than, say Go and Java's lookup table type erasure approach.
More information about this can be found here: https://stackoverflow.com/questions/31876372/what-is-reifica...
That means that you can have a function that returns `-> impl Trait` with a concrete implementation because it has a single return value, but if you add a second and don't want to create an enum for a simple version of static dispatch, you can change the returned values to be trait objects and the callers don't break.
btw. it's not called "runtime evaluation" and more or less a kind of runtime substitution. (because nothing gets evaluated it gets substituted)
and btw. c++ allows references types to have specializations, this is not possible in c#
I can see some references in the source code, https://doc.rust-lang.org/src/core/result.rs.html#2057
const functions are really 'maybe const' functions since they can be called with runtime arguments or compile time arguments.
If you want your const function to depend on some trait, for it to even be possible at compile time, those traits would need to be possible to use at compile time too.
But the same idea holds as arguments, we might just want to use it at runtime too, in which case it needs to be a 'maybe const' bound for the const function to be flexible enough for us.
Ah, so just like languages with 'runtime' generics like c# and java!
Am I missing something that makes Rust generics way more complicated than C++ templates? Or is retrofitting them into Rust really such a hellish adventure?
The main difference is that the C++ code will check everything at instantiation time, and C++ templates can lead to nasty error messages because it's hard to assign _blame_ to either the caller or the callee.
As an example, consider the following code:
This code will only typecheck if N is even. But that's not written down anywhere, and if I tried to pass in an odd N, then I'd get some template error telling me that _something_ went wrong, and it may even give me a trace. But that error doesn't tell me whether it's a bug in foo, or a bug in how I'm using foo. If it's a bug in using foo, it certainly doesn't tell me how to fix things.Rust takes the approach of requiring that you specify constraints on generic parameters up front. It then checks whether the function's body will compile _for all_ possible generic parameters, given the constraints. This is much easier to use from a usability perspective, since you know whether to blame the caller or the callee, and it explicitly enumerates the requirements that you need to meet (i.e. the constraints on the generic parameter) in order to get your code to compile. This is why C++ lets you do many more crazy things with templates than Rust currently allows you to with generics (and why is moving more slowly to add things to its type system).
C++'s alternative approach gives up usability for extra flexibility. Neither approach is "right." They're just different trade-offs.
(As an aside, it turns out that the Rust type system was Turing complete even before const generics were added.)
Provides you with an example to play with, as described this is broken for foo<5> but works fine with say, foo<6>
> Let's look at a brief example to get familiar with syntax:
Followed by no explanation, nor is there a target audience laid out in the article.
Now I'm left simply thinking it's a terrible article because it's starts with a poor explanation targeted at anyone.
If it started with "if you're familiar with C++/go/c#/whatever then this syntax should appear familiar", then I would have quietly closed the article. Unfortunately my impression of the article is poor, and continues to be poor of the rust community because of constantly putting out content with this style of hand wavy introduction that makes outsiders feel more alienated.
At least haskellers (of which I am not one) manage to be aware of this trope in their own community.