Focus of Rust evolution

[newpavlov]

The main difference between SIMD and unchecked indexing is that later can lead to horrible bugs and security vulnerabilities, which radically goes against Rust goals. Maybe some functionality of safe “explicitly provable unchecked indexing” could be an alternative option. In other words for given new syntax Rust compiler (not LLVM back-end) will eliminate checks if necessary proof is available, and if not it will produce compile-time error. But I have no ideas how this functionality could look.

UPD: I think in early days of Rust it had a capability to list restrictions on input arguments (a la Ada?), but it was removed due to the noisiness. Maybe its revival in some form could help?

[gbutler]

Can’t one do unchecked indexing effectively with “unsafe” and pointer manipulation? Couldn’t this be put in an unsafe trait/trait with unsafe methods? It you really want to do “unchecked” indexing, that is clearly “unsafe”.

EDIT: Might a possible syntax for this be?

let i = computeNextIndexToUseBasedOnMyAlgorithm( ... );
unsafe { let el = a[!:i]; }

where the “[!:]” is the "unchecked/unsafe index operator (bike-shedding on syntax welcome). Basically, you are asserting that your algorithm is such that the index you’ve computed is guaranteed to be in-bounds for the given array and that the compiler does not need to check. It needs to be in an unsafe block because you are asking the compiler to trust you.

[HadrienG]

Some compilers have pragmas which basically state “please vectorize this loop if you can, and throw a compiler error otherwise”. Rust could probably take a similar approach for bounds checks, with some kind of #[elide_bound_checks] loop attribute.

The main problem with this approach is that like -Werror, it turns aspects of a compiler which are not covered by any strong stability guarantee into sources of compiler error. Therefore, it is only suitable for debugging, and should not be used in production builds, which somewhat undermines its usefulness.

[HadrienG]

Unchecked array accesses are most certainly unsafe, there is no disputing that. They can cause serious bugs which are hard to track down, such as data races, and should thus be kept in small and focused code regions (e.g. inner loop, high-level abstraction implementations).

What I am saying is just that names like “get_unchecked” and “ptr::offset” are often much too long for use in numerical computations, where having tens of array accesses per line in the heart of a kernel is not uncommon. A shorter unsafe indexing syntax, such as the one that you are proposing would be needed to make this kind of use cases practical. Even a simple “at()” unsafe method, which can be added today by a trait, would help already

[gbutler]

unsafe { let el = a[!:i]; }

Better yet:

let el = unsafe { a[!:i] }

[gbutler]

What I am saying is just that names like “get_unchecked” and “ptr::offset” are often much too long for use in numerical computations,

OK, so, something like this would be a solution?

let result = unsafe { a[!:i] * a[!:i+3] / a[!:i*2+5] } 

EDIT: Of course, in the above, for it not to be a disaster at run-time, our “algorithm” would’ve needed to compute i such that i, i+3, and i*2+5 are guaranteed in-bounds for our array.

[HadrienG]

As I said, that would be one workable approach, assuming that the syntax is available (possible issue: can you define a unary not operator on a type which is usable as an array index?)

Another approach which has been suggested in the past would be to annotate blocks of code as using unchecked indexing. Not sure if that is better/worse.

[gbutler]

assuming that the syntax is available

Well, that’s why I suggested, “[!:]” and not just “[!]” to avoid the problem of unary ! (I hope). Alternatively, what about?

let el = unsafe { a[#i] }

Where now the unsafe index operator is, “[#]”

[birkenfeld]

Even a simple “at()” unsafe method, which can be added today by a trait, would help already

But that’s just as easy to add yourself, no?

[HadrienG]

Yes, I said it because I just thought about this workaround

[Centril]

Let’s not forget that Rust is a very young language, and given time, I’m confident it will rise to the task in the number crunching department. So although the road may me long, there’s light at the end of the tunnel.

Const generics and functions in particular will address many of these issues, at the expense of potentially causing a big language community split between compile-time and run-time Rust.

With an RFC similar to “const bounds and methods” (which needs to be significantly rewritten) we can also almost entirely get rid of the ecosystem split between const and non-const.

Rust’s slice/iterator ecosystem is heavily biased towards dynamically sized containers, and interoperates poorly with statically sized arrays. For example, collecting an iterator into an array is a pain.

I think we can have fixed size iterators using const generics, see: Fixed-size lazy iterators? Also, I’d like to see some form of ArrayVec in the standard library.

Better ways to initialize arrays and avoid double initializations

There’s also “const repeat expressions” which recently got accepted.

I think this should be solved not by making unsafe unchecked indexing more ergonomic (buffer overflows in Rust? No, thank you…), but by making Rust smarter around proving bounds checks redundancy (e.g. sometimes you have to use explicit slices instead of assert_eq!)

I think the solution here should be more of dependent types (we’ll get dependent types for const values, let’s also get them for runtime values) and refinement types atop of that. Dependent types also gives the user an extreme amount of power to program the type system for comparatively little complexity, that is: the power / complexity ratio is small.

and by developing an ergonomic tool which will be able to highlight indexing operations for which LLVM can’t remove bounds checks.

This BsC thesis discussing a compiler explorer for CakeML might be of interest, http://publications.lib.chalmers.se/records/fulltext/251308/251308.pdf

EDIT: Might a possible syntax for this be?

let i = computeNextIndexToUseBasedOnMyAlgorithm( ... );
unsafe { let el = a[!:i]; }

where the “[!:]” is the "unchecked/unsafe index operator (bike-shedding on syntax welcome).

Instead of special syntax, we can instead introduce forms of effect polymorphism where you can say: x: Arr , Arr: unsafe Index<usize> and now you can use unsafe fn index(&self, index: Idx) -> &Self::Output; without changing the trait like so: arr[0] (see the const bounds and methods RFC for a discussion).

[aturon]

Just a quick note that I’d personally be quite interested to see a Numerics WG in 2019, hopefully after a couple more foundational features (like const generics) are available.

[gbutler]

I think the solution here should be more of dependent types (we’ll get dependent types for const values, let’s also get them for runtime values) and refinement types atop of that.

Would you be willing to elaborate on that a bit more (for those not fully familiar with “Dependent Types”)?

[varkor]

I think the solution here should be more of dependent types (we’ll get dependent types for const values, let’s also get them for runtime values) and refinement types atop of that. Dependent types also gives the user an extreme amount of power to program the type system for comparatively little complexity, that is: the power / complexity ratio is small.

I may be reading too much into your comment, but I think it’s useful to clarify something about this:

Const generics lead to a very limited form of dependent types that are very far removed from full dependent typing. Though full dependent types do lead to a leap in expressiveness, I think it’s completely untrue that this would lead to “comparatively little complexity”, both in their implementation and in their understanding (for users inexperienced with dependent types, which is going to be most users).

I certainly think that increasing the expressiveness of the type system is a good thing, but I think this is significantly understating the complexity involved.

[Centril]

Would you be willing to elaborate on that a bit more (for those not fully familiar with “Dependent Types”)?

Certainly; But please do consult https://en.wikipedia.org/wiki/Dependent_type for a more elaborate review.

If we consider the question “Can X depend on X?” where X = {values, types}, and categorize languages by that then we get the following questions:

• Can values depend on values?
  • If yes, we get the simply typed lambda calculus (λ→)
• Can values depend on types?
  • If yes, we get System F, 2nd order lambda calculus (λ2), or just parametric polymorphism / generics, and we can encode: fn id<T>(x: T) -> T { x }
• Can types depend on types?
  • If yes, we get λω or type operators where you can encode type Foo<X> = Vec<Vec<T>>; and specifically to rust, you can encode type level functions such as trait TypeFn<X> { type Y }.
• Can types depend on values?
  • If yes, then you get (value) “dependent types”.

So, what (value) dependent types such as in languages like Idris, Agda, Coq, F*, etc. allow is for types to be dependent on values. And so you could encode things such as (with Agda notation):

repeat : {A : Set} // Quantify the type of elements.
      -> (x : A)   // The element x : A we wish to repeat.
      -> (n : Nat) // The number of elements to repeat.
      // Notice how Vec a n  depends on the input n passed!
      -> Vec A n   // A list of exactly n As.

append : {A : Set}
      -> {n m : Nat}
      // Concatenating a list of n elements and one with m gives you n + m elements.
      -> Vec A n -> Vec A m -> Vec A (n + m)

index  : {A : Set}
      -> {n : Nat}
      -> {prfLess : idx < n} // Proof that: idx < n
      -> (idx: Nat) // The index we wish to extract.
      -> Vec A n
      -> A // We know that idx < n, so we can safely get an A out always.

This roughly corresponds to the following with pseudo-Rust notation:

fn repeat<A>(x: A, n: usize) -> Vec<A, n> {..}

fn append<A, n: usize, m: usize>(a: Vec<A, n>, b: Vec<A, m>) -> Vec<A, {n + m}> {..}

fn index<A, n: usize>(idx: usize, vec: Vec<A, n>) -> A where idx < n {..}

Thus far, we’ve only considered what are called pi-types, that is, types of the form: Π (x: A) B(x). But there are also so called sigma-types, or dependent sum types of the form Σ(x: A) B(x). With these sigma types, you can encode things such as (pseudo-Rust, so I’m quite heavily making things up):

struct AnyLenVec<A> {
    n: usize,
    v: Vec<A, n> // Notice how we are referring to the field `n`!
}

fn index_gvec<A>(idx: usize, vec: AnyLenVec<A>) -> Option<A> {
    if idx < vec.n {
        Some(index(idx, vec))
    } else {
        None
    }
}

Finally, I’d like to leave a few assorted resources on dependent typing:

• “Dependent Types in Haskell” by Stephanie Weirich
• Part I: Dependent Types in Haskell
• Types for Programs and Proofs (a course at Chalmers University of Technology)
• Dependent types at Work
• Dependent types in Idris
• Idris: General Purpose Programming with Dependent types
• Type-Driven Development in Idris — Edwin Brady
• David Christiansen - Coding for Types: The Universe Patern in Idris

I may be reading too much into your comment, but I think it’s useful to clarify something about this:

Yes, I think you are.

Const generics lead to a very limited form of dependent types that are very far removed from full dependent typing.

I will agree to it being limited - and more so in the RFC than what const generics could be. You can still build some pretty powerful abstractions with it (cf. the fixed size iterators). The “only” difference, from a user’s perspective, between constant and run-time dependent types is that the former does not allow types to be parameterized by run-time values. So the former allows you to encode Π (const x: A) B x while the latter allows you to encode Π (x: A) B x. This does of course translate into large differences in expressiveness.

I think it’s completely untrue that this would lead to “comparatively little complexity”, both in their implementation and in their understanding (for users inexperienced with dependent types, which is going to be most users).

I was only comparing the complexity of dependent typing relative to the gain in expressiveness, not the the complexity of dependent typing in absolute terms (which of course will be complicated), wherefore I think it is entirely true wrt. the ratio between power and complexity. I was not referring to complexity in understanding at all.

[leonardo]

Just a quick note that I’d personally be quite interested to see a Numerics WG in 2019, hopefully after a couple more foundational features (like const generics) are available.

As quick answer: just a small part of the things discussed here are about what is usually called numerics, and only a part of the things here are going to be solved by the const generics feature.

[crlf0710]

By the way, tuples in Rust is in very bad shape. It is deeply associated with fn_traits and make things like callback closure composition very hard if not possible at all.

[comex]

Just a reminder that you can already emulate dependent types in Rust :

https://docs.rs/indexing/0.3.2/indexing/

In fact, I think it’s possible to take a much more general approach than that crate. Instead of special-casing the idea of a range that might or might not have been proved to be non-empty, go for arbitrary integer relations:

fn index<A: Slice<i32>, I: Usize>(a: &A, i: I, lt_proof: Lt<I, Len<A>>) { ... }

…Now I really want to write a proof-of-concept of this.

[Centril]

Just a reminder that you can already emulate dependent types in Rust :

Oh noes I think (?) this falls under the “type hackery” of the singletons hackage package that Haskell folks are using cause we don’t have full dependent types in Haskell yet ^,- Tho the encodings in indexing are quite interesting.

[JustAPerson]

As someone not currently working in number-crunching, can you explain some use cases in which arrays are a pain to use? I think that identifying precise use cases it will help people outside the problematic area to be more aware of the problem.

Perhaps not just fixed sized arrays, but slices in general:

The thing that repeatedly annoys me is that you cannot index a slice with anything but a usize. I’m sure this has annoyed everyone at times, but using usize everywhere is often fine. In my specific application with hundreds of millions of indices, using u32 over usize is an important optimization, but it clutters code with conversions everywhere (in both directions). It would be much more convenient and tidier if there was an implicit as usize cast for indexing. That’s what is always meant, so please save me the effort. This is easily accomplished by adding a few impls for std::slice::SliceIndex.