Pre-RFC: Integer Templating

[Amanieu]

This RFC duplicates a lot of work of https://github.com/rust-lang/rfcs/pull/1062. Maybe this one should be postponed until the other RFC is merged, because then this RFC can simply be sugar for desugaring the following

If we go down this route then we could avoid the need for const to differentiate between types and values for generic parameters. Instead, a keyword could be used to turn a constant expression into a type that contains the resulting value as an associated constant, similar to std::integral_constant in C++.

Example:

trait<T> Const  {
    const VALUE: T,
}
fn adder<N: Const<usize>>(m: usize) -> usize { N::VALUE + m }
fn main() {
    assert_eq!(adder<const_usize!(42)>(66), 108);
}

[Uther]

I understand why it may be necessary to distinct types from variables, but is it necessary for literals too? I’m not expert with the compiler, but shouldn’t it be able to know literals are not types?

[dgrunwald]

I think it should be possible to special-case integer literals to avoid the necessity for the const keyword when using the type.

Also, identifiers/paths are allowed both in type syntax and expression syntax, so we could parse those and then later (during typeck) decide whether they represent a type or a constant value.

These two special cases would allow the use of StackVec<T, 32> and StackVec<T, n>. Only complex cases like StackVec<T, const n+1> would still require the const keyword.

[Johnson_A]

Would this eventually incorporate function specialization similar to c++ ? Something I’ve been missing in Rust is the ability to specialize a function for certain values of the type (I think Rust’s algebraic types would be very powerful here). If we had the ability to template by an enum, the compiler could easily tell that all utilized cases have been met, either by a default implementation or by specializing for every possible value like what is currently done with the match statement. It would also be very helpful if we could calculate const values inside the function which would be calculated at compile time [like here] (https://github.com/mcostalba/Stockfish/blob/ONE_PLY/src/movegen.cpp#L101).

I agree that having const specified for each template is clearly implied and having the extra specifier would be very verbose for little gain.

[bbatha]

Rust is getting specialization.

[kainino]

I believe this is the GitHub issue for this feature: https://github.com/rust-lang/rfcs/issues/1038

[notriddle]

I know someone previously proposed separating the const parameters and type parameters using a semicolon. So your examples look like this:

fn adder<; n: u32>(m: u32) -> u32 {
    n + m
}

// There are better ways to implement this, but it's an example
struct StackVec<T; n: usize> where T: Default{
    store: [T; n],
    len: usize,
}

impl<T; n: usize> StackVec<T; n> where T: Default {
    pub fn new() -> StackVec<T, n> {
        StackVec {
            store: [Default::default(); n],
            len: 0,
        }
    }
}

println!("{}", adder::<; 4>(5)) // '9'
// or
let v = StackVec::<_; 16>::new();

[oli-obk]

this is pretty cool due to the symmetry to [T; N] types

[matthieum]

Why not just:

impl<const N, const M> std::opts::Add<Matrix<N, M>> for Matrix<N, M> {
    type Output = Matrix<N, M>
}

That is, introducing the constants requires qualifying them with const to indicate those are values instead of types, but do we really need to make this distinction when using them afterward?

As a parallel, when I compute at run-time I:

• specify the type of the variable when declaring it
• but not when using it

Of course, it means that as far as the AST is concerned, in Matrix<N, M> the N is some generic parameter with no clue about whether it’s a type or value.

Does it really matter?

[notriddle]

[quote=“matthieum, post:19, topic:2974”] Of course, it means that as far as the AST is concerned, in Matrix<N, M> the N is some generic parameter with no clue about whether it’s a type or value.

Does it really matter?[/quote]

Actually, yes, because rustc checks that symbols are declared before type checking. This means that, at the time it needs to check that the symbol exists, it can’t check type definitions to figure out what namespace it’s supposed to be in (Rust allows types and variables to have the same name with no ambiguity).

http://is.gd/QfvaBj

[matthieum]

Ah, I was fearing the namespace issue.

The problem is that as much as I find the “;” nifty I am afraid it’s a bit too smart:

• it’s close to being undiscoverable for a newcomer
• it’s close to being unsearchable

It’s a general issues about symbols; keywords are just much easier to search for.

Does discoverability matters?

[matthieum]

I’ve thought about this proposal a bit more, and I am afraid it’s quite incomplete.

Syntax is debated to no end in every language so being able to settle on the syntax is already something; however there are potentially many other issues to resolve.

For example: the examples only show constants being passed around, but what about expressions? C++ non-type template parameters matterred because you could use expressions from the get go (even if it was quite barebone), so at least I would expect to have a plan on how to deal with expressions even if they are not introduced immediately. Backward compatibility is for life…

Another unresolved question is how to deal with usize and isize. There are two possibilities:

1. Use a “virtual machine” based on the target for which the code is emitted
2. Use symbolic reasoning (so usize::max - 1 is non-reducible and different from 4294967294 even on 32-bits platforms)

It’s possible to limit the RFC to non-target dependent code for now; it’ll require being careful with floating points (probably we’ll want strict IEEE compliance).

A strategy to deal with underflow/overflow in compile-time evaluation need be defined. If the value is necessary at compile-time then it should probably be a hard-error, however there might be impacts on potential evolutions later.

That’s all I could think about in the last day or so; but I suspect there are other issues I did not think off…

[jimb]

I was wondering how a function that is generic over a constant might be compiled.

Specializing the function for each constant it’s applied to, as we do with type parameters, seems like overkill. It’s ungainly to have 33 implementations of Clone in the source as we do now, but it’d also be ungainly to have a separate copy of the machine code for every possible size. Invisible ungainliness is asking for trouble.

Instead, we could produce LLVM code for the function once, having it take the generic constant parameter as an invisible run-time parameter. Each call site must know its value for the generic argument, so it can pass it as needed. Then, LLVM can decide when it’s best to inline the function and propagate the constant, and when it’s best to actually pass it at run time—just as it does now for any other function call.

[notriddle]

Can’t work for any case where the function passes the constant on to types:

fn suck<T, I; len: usize>(input: I) -> [Option<T>; len]
  where I: Iterator<T> {
    let mut buf = [T::default(); len];
    for i in 0..len {
        buf[i] = input.next();
    }
    buf
}

The whole point of generic functions over constants is to have changeable static arrays.

[retep998]

When a generic function is defined it isn’t monomorphized to every possible type parameter but rather when it is actually referred to. If I only clone an array with a size of 273 then only that impl gets monomorphized and the rest of them don’t exist. Having a single generic impl that can be monomorphized as needed is significantly more efficient than having the 33 impls for just the smallest sizes.

[leonardo]

Having integral numbers as template arguments, implemented as in C++, will offer many useful opportunities.

Not having a “const” tag before the value (if this is possible), is a good idea, but having a type annotation is also useful (as in D language):

impl<n: usize, m: usize> std::ops::Add<Matrix<n: usize, m: usize>>
        for Matrix<n: usize, m: usize> {
    type Output = Matrix<n, m>;
}

But in some cases you want to use such compile-time template arguments (like such matrix sizes) only to perform compile-time correctness validation, but you don’t want (to avoid template bloat) to actually instantiate new code with such integral values. So in this case the integral arguments are ghosts, and if necessary they are passed as run-time values in some way to the function(s).

[target_san]

Please fix me if I’m wrong. As I understand, the real discussion around const prefix is about usage site, and not about declaration site. And the main question is, whether parser will be able to handle such cases. Right?

[Uther]

Yes. The parser as he was designed cannot handle this case transparently.

[dobenour]

This will be extremely useful. The part that I am most interested in is that arrays will finally implement all usual traits for all lengths.

[jimb]

When a generic function is defined it isn’t monomorphized to every possible type parameter but rather when it is actually referred to.

Yes; I shouldn’t have written “every possible size”. What I was thinking was “every used size”.

But @notriddle’s objection is much more serious. Although, if C11 can handle dynamically-sized arrays, I assume Rust can as well. The following is valid C:

int f(int n, int i)
{
  int a[n];

  int j;
  for (j = 0; j < n; j++)
    a[j] = j;

  return a[i];
}