Grids in Rust, Part 2: const generics
blog.adamchalmers.com
blog.adamchalmers.com
(source Wikipedia)
So rusts const generics are (very limited) dependent types.
C++ templates on the other hand you could argue are not types (but templates), but that is nit-picking.
Weather or not dependent types are can be runtime evaluated often is a separate question then weather or not a language has dependent types.
EDIT: The following part is partial nonsense, very POV dependent. I wanted to delete it but that wouldn't be right, so I just added this note.
Through not allowing run-time creation of dependent types makes them much more limited in usability. But then allowing it requires either reflections (still likely very limited/slow/etc.), or part of the type being stored as a "magic" field of the type instance (fast but is that still a dependent type?), or a interpreted language).
> The return type of a dependent function may depend on the value (not just type) of one of its arguments. For instance, a function that takes a positive integer n may return an array of length n, where the array length is part of the type of the array.
second:
> A dependent pair may have a second value of which the type depends on the first value. Sticking with the array example, a dependent pair may be used to pair an array with its length in a type-safe way.
Generally, it's the same nomenclature as with the explanation of static vs dynamic type systems: in static type systems, types are attributes of variables, functions and expressions, whereas in dynamic type systems types are attributes of values. And in the static type system of C, 5 has type int, because it's an expression. It representing a value is secondary. A side effect of it is: you can write a compile-time constant in C that will overflow its type, because the type is assigned based on the lexical category, not on the value.
As far as I understand, in a dependent type system it should be possible to implement a resizable array "std::vector<int, n>", where n is the length of the array (a variable), then write a "concat" function which concatenates two such arrays, and whose return (static) type depends on the lengths of the arrays passed as arguments. This is different than parametric polymorphism, such as the one that C++ has, since we can't know at compile-time all the possible lengths of arrays that we're going to get at runtime. Idris example here: https://idris2.readthedocs.io/en/latest/tutorial/typesfuns.h...
If someone has a better understanding of the topic, I'd be delighted to be shown wrong.
worksforme https://gcc.godbolt.org/z/x9GjE7KGM (ok, except the "resizeable" bit - but since we're doing functional programming we want immutable data structures, no ? :p)
Not only is it nitpicking, it seems wrong even in an academic sense of the term. Whether the template itself is a type or not probably depends on what theoretical language you use to discuss it.
The template is monomorphized into a new type per instantiation, yes, but the moment it actually has a number in it it's a type.
In D the template can quite happily accept pretty much anything as a parameter (particularly structs i.e. better code quality), and I'm surprised other languages don't allow this. Why have a bunch of template parameters on a line when you can just program the way you normally would.
Rust doesn't (arbitrary values, anyway, const generics is the start of this being possible) because we don't have templates, we have generics. I agree if you're going with a template-based system, it makes a lot of sense to accept whatever, but if you aren't, then things are more complicated.
* https://github.com/rust-lang/rfcs/pull/1657
* https://github.com/rust-lang/rfcs/issues/1930
* https://github.com/rust-lang/rfcs/pull/2000 (the design that was accepted, in the end)
(I am not actually 100% sure if rfc 2000 meets the by-the-book definition of "dependent types", my copy of Pierce has been collecting dust. Really gotta study up more on this stuff.)
One roundabout way of doing this - which is very much possible in D but not worth doing because you can't really do useful work with it for the most part due to pain - is that if you extend (say) const-generics to work with basically anything evaluable at compile time, you can build up a data structure to represent and hold true some predicate about a runtime value in a type (as a template/generic parameter), then define how these combine under binary operations (trivial so far in D at least, impossible in C++, no idea about Rust - monomorphization differences aside), then use this datastructure for evil and profit (like giving invariants to the optimizer).
I would like to see how far the aforementioned idea can go, however it quickly becomes "write a compiler at compile time" or worse "write an SMT solver at compile time", both of which do not thrill me.
fn make_array(n: usize) -> [u8; n]
I am guessing this isn't actually the feature though, and that it's not allowing dependence in this way, but rather promoting some const values and const functions to the type level (which is really useful, but not exactly dependent types)
For dynamically-sized arrays you'd typically use a `Vec<T>` in Rust (or a `Box<[T]>`). These imply the array is stored as a separate heap allocation.
It is. C used to have variable-length arrays as a required part of the standard, but that was made an optional feature in C99. C++ (like Rust) does not have variable-length arrays at all.
If you need a dynamically-sized array in any language, usually you allocate the array on the heap — for instance, with malloc/free, or with a vector type like C++’s std::vector or Rust’s Vec.
As for why, I’m not entirely sure — hopefully someone with more expertise than me can chime in. I’m not sure if it adds too much complexity in the compiler, or if they were simply deemed too unsafe even for C/C++ (since it’s way too easy to accidentally overflow the stack with VLAs).
https://play.rust-lang.org/?version=stable&mode=debug&editio...
If you need an array of unknown size, then you can heap allocate it or use std::vec::Vec (usually via the vec! macro) to provide a nice interface for doing so.
If you need nested structs, e.g. for a tree, then you need to make the field, e.g. the children nodes, pointers or a Box type.
Rust tries to make what it's doing with memory obvious. Other languages with unknown array sizes do a lot of potentially unpredictable memory allocations and copies.
Having a known-length array type in a programming language:
* allows the compiler to make certain optimizations using the information it has on the length, especially if the length is small
* allows the programmer to enforce constraints on the length of arrays at compilation time, which can make program correctness more evident and easier to accomplish
> This restriction is not found in other programming languages.
Ever heard about C or C++ or Go? Even dynamic languages like Julia allow defining such types.
OutOfBounds errors aren't checked at compile time unless it's a `const` type IIRC.
There are circumstances where Rust can calculate the array index at compile time and, if it can, it will result in a compilation error if the index is out of bounds. Of course, this is a best-effort analysis and doesn't work for all possible cases. Here's some Rust code, the first three indexing operations fail at compile-time, but the last doesn't:
let x = [1,2,3];
x[4]; // compile error
const FOUR: usize = 4;
x[FOUR]; // compile error
let y = 4;
x[y]; // compile error
fn foo() -> usize { 4 }
x[foo()]; // runtime error
This should provide interesting reading -- it's a discussion on unsized local variables, e.g. VLA's on the stack.
I think the rest of these replies are presenting a false dichotomy; having a compile-time sized array doesn't change that.
Rust could easily have all three (compile-time-sized, runtime-sized, and Vec) but they chose not to. Probably because Vec is mostly good enough (albeit wasting a bit of memory).
Box<[T]> is close, but it's a pointer + length, where the pointer is to the heap, whereas [T; N] is a series of values, and can be on the stack. That's why it's a "boxed slice" and not an "array."
And yes, any slice type is runtime sized. That's why slices exist; they have a length stored in them to keep track of how long they are. This goes for &[T], Box<[T]>, Arc<[T]>, any of them.
// returns a heap-allocated buffer of length new_arr_length
fn my_malloc<T>(new_arr_length: usize) -> Box<[T]> {
todo!()
}
I guess what it comes down to is: slices can't own their data, can they (I'm genuinely not sure)? If so, and this is indeed a slice, then it should be impossible for this to work in this way
Though, in that case it would also seem fairly pointless (as opposed to a &[T])
// returns a heap-allocated buffer of length new_arr_length
fn my_malloc<T: Default + Clone>(new_arr_length: usize) -> Box<[T]> {
vec![T::default(); new_arr_length].into_boxed_slice()
}
The problem is that "slice" can mean both &[T] and [T]. [T] is an unsized type, so it needs to be behind a pointer. Putting it behind a & is the common case, and doesn't have ownership because &T doesn't own T, but you can also put it behind Box<T>, which does have owership over T.
> Though, in that case it would also seem fairly pointless (as opposed to a &[T])
Yes, it's very niche. I've never used one in all my years of Rust. But Box<[T]> is two thirds of the size of Vec<T> (no need for capacity, since capacity == length) and maybe there are cases where that is significant, for example.
use std::sync::Arc;
fn foobar(s: &str) -> Arc<str> {
Arc::from(s.to_string())
}
It's just that you (for now(1)) can't put dynamic sized types (DST) on the stack, but you can coerce a `&[T; SIZE]` to a `&[T]`. The later has the size encoded in the pointer. Which combined with rusts system to compiler time enforce proper aliasing and RAII allows nice sub-slicing like e.g the `split` at method which allows splitting a `&[T]` into two non-overlapping `&[T]`'s.
(1): There is ongoing work to allow DST on the stack in some limited circumstances which would help with some things, but I'm not the biggest fan of it. For example because this is in many but not all cases incompatible with `async/await` and the not yet existing generators.
Off-topic but the JVM will be the second platform to get const generics support -> https://www.reddit.com/r/java/comments/m2dfb5/parametric_jvm...
Are there other languages than rust that supports it?
I'm no expert on the terminology, but C++ templates can take values as template arguments (I think this is what is called "const generics" in Rust), and languages such as Julia are even more powerful.
Const generics are essentially a really small subset of fully dependent types, which are implemented in Idris 2 and other research languages.