[lang-team-minutes] Const generics


#62

Personally, I agree with comex : shouting upper case is a heritage from C that only make sense to warn about global variables. I don’t see any benefit to warn about constness, and it is not distinguished from static anyway.

I think the rule of shouting uppercase should be applied only to global variables. const and static defined locally should look like normal variables.


#63

This shows a little use case for Const generics, in C++ (run-time about 0.32 seconds):

#include <stdio.h>

const int N_BOWLS = 40;
const int N_ORANGES = 9;

typedef int Used[N_BOWLS];
typedef int Oranges[N_ORANGES];

template <int turn>
int solve(int x, Used used, Oranges oranges) {
    int count = 0;

    for (; x < N_BOWLS - (N_ORANGES - turn - 1); x++) {
        if (!used[x]) {
            used[x]++;
            for (int y = 0; y < turn; y++) {
                const int tmp_index = x + x - oranges[y];
                if (tmp_index >= 0 && tmp_index < N_BOWLS)
                    used[tmp_index]++;
            }
            oranges[turn] = x;
            count += solve<turn + 1>(x + 1, used, oranges);
            for (int y = 0; y < turn; y++) {
                const int tmp_index = x + x - oranges[y];
                if (tmp_index >= 0 && tmp_index < N_BOWLS)
                    used[tmp_index]--;
            }
            used[x]--;
        }
    }

    return count;
}

template <>
inline int solve<N_ORANGES>(int, Used, Oranges) {
    return 1;
}

int main() {
    Used used = {0};
    Oranges oranges = {0};
    printf("%d\n", solve<0>(0, used, oranges) == 7555794);
}

Similar code in Rust without const generics (run-time about 0.52 seconds):

// rustc -C opt-level=3 -C target-cpu=native

const N_BOWLS: usize = 40;
const N_ORANGES: usize = 9;

type Used = [usize; N_BOWLS];
type Oranges = [usize; N_ORANGES];

fn solve(turn: usize, mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
    if turn == N_ORANGES {
        1
    } else {
        let mut count = 0;

        while x < N_BOWLS - (N_ORANGES - turn - 1) {
            if used[x] == 0 {
                used[x] += 1;
                for y in 0 .. turn {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] += 1;
                    }
                }
                oranges[turn] = x;
                count += solve(turn + 1, x + 1, used, oranges);
                for y in 0 .. turn {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        count
    }
}

fn main() {
    //let mut used: Used = Default::default();
    let mut used: Used = [0; 40];
    let mut oranges: Oranges = Default::default();
    println!("{}", solve(0, 0, &mut used, &mut oranges) == 7_555_794);
}

You can regain the same performance in Rust unrolling the template manually (run-time about 0.33 seconds):

// rustc -C opt-level=3 -C target-cpu=native

const N_BOWLS: usize = 40;
const N_ORANGES: usize = 9;

type Used = [usize; N_BOWLS];
type Oranges = [usize; N_ORANGES];

fn solve0(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
    if 0 == N_ORANGES {
        1
    } else {
        let mut count = 0;

        while x < N_BOWLS - (N_ORANGES - 0 - 1) {
            if used[x] == 0 {
                used[x] += 1;
                for y in 0 .. 0 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] += 1;
                    }
                }
                oranges[0] = x;
                count += solve1(x + 1, used, oranges);
                for y in 0 .. 0 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        count
    }
}

fn solve1(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
    if 1 == N_ORANGES {
        1
    } else {
        let mut count = 0;

        while x < N_BOWLS - (N_ORANGES - 1 - 1) {
            if used[x] == 0 {
                used[x] += 1;
                for y in 0 .. 1 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] += 1;
                    }
                }
                oranges[1] = x;
                count += solve2(x + 1, used, oranges);
                for y in 0 .. 1 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        count
    }
}

fn solve2(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
    if 2 == N_ORANGES {
        1
    } else {
        let mut count = 0;

        while x < N_BOWLS - (N_ORANGES - 2 - 1) {
            if used[x] == 0 {
                used[x] += 1;
                for y in 0 .. 2 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] += 1;
                    }
                }
                oranges[2] = x;
                count += solve3(x + 1, used, oranges);
                for y in 0 .. 2 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        count
    }
}

fn solve3(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
    if 3 == N_ORANGES {
        1
    } else {
        let mut count = 0;

        while x < N_BOWLS - (N_ORANGES - 3 - 1) {
            if used[x] == 0 {
                used[x] += 1;
                for y in 0 .. 3 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] += 1;
                    }
                }
                oranges[3] = x;
                count += solve4(x + 1, used, oranges);
                for y in 0 .. 3 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        count
    }
}

fn solve4(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
    if 4 == N_ORANGES {
        1
    } else {
        let mut count = 0;

        while x < N_BOWLS - (N_ORANGES - 4 - 1) {
            if used[x] == 0 {
                used[x] += 1;
                for y in 0 .. 4 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] += 1;
                    }
                }
                oranges[4] = x;
                count += solve5(x + 1, used, oranges);
                for y in 0 .. 4 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        count
    }
}

fn solve5(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
    if 5 == N_ORANGES {
        1
    } else {
        let mut count = 0;

        while x < N_BOWLS - (N_ORANGES - 5 - 1) {
            if used[x] == 0 {
                used[x] += 1;
                for y in 0 .. 5 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] += 1;
                    }
                }
                oranges[5] = x;
                count += solve6(x + 1, used, oranges);
                for y in 0 .. 5 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        count
    }
}

fn solve6(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
    if 6 == N_ORANGES {
        1
    } else {
        let mut count = 0;

        while x < N_BOWLS - (N_ORANGES - 6 - 1) {
            if used[x] == 0 {
                used[x] += 1;
                for y in 0 .. 6 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] += 1;
                    }
                }
                oranges[6] = x;
                count += solve7(x + 1, used, oranges);
                for y in 0 .. 6 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        count
    }
}

fn solve7(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
    if 7 == N_ORANGES {
        1
    } else {
        let mut count = 0;

        while x < N_BOWLS - (N_ORANGES - 7 - 1) {
            if used[x] == 0 {
                used[x] += 1;
                for y in 0 .. 7 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] += 1;
                    }
                }
                oranges[7] = x;
                count += solve8(x + 1, used, oranges);
                for y in 0 .. 7 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        count
    }
}

fn solve8(mut x: usize, used: &mut Used, oranges: &mut Oranges) -> usize {
    if 8 == N_ORANGES {
        1
    } else {
        let mut count = 0;

        while x < N_BOWLS - (N_ORANGES - 8 - 1) {
            if used[x] == 0 {
                used[x] += 1;
                for y in 0 .. 8 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] += 1;
                    }
                }
                oranges[8] = x;
                count += solve9(x + 1, used, oranges);
                for y in 0 .. 8 {
                    let tmp_index = x + x - oranges[y];
                    if tmp_index < N_BOWLS {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        count
    }
}

fn solve9(_: usize, _: &mut Used, _: &mut Oranges) -> usize {
    1
}

fn main() {
    //let mut used: Used = Default::default();
    let mut used: Used = [0; 40];
    let mut oranges: Oranges = Default::default();
    println!("{}", solve0(0, &mut used, &mut oranges) == 7_555_794);
}

And the same code with D language templates and “static if” (with the LDC compiler the run-time is about 0.33 seconds):

enum uint BOWLS = 40;
enum uint ORANGES = 9;

alias Used = uint[BOWLS];
alias Oranges = uint[ORANGES];

uint solve(uint turn)(uint x, ref Used used, ref Oranges oranges) {
    static if (turn == ORANGES) {
        return 1;
    } else {
        uint count = 0;

        while (x < BOWLS - (ORANGES - turn - 1)) {
            if (used[x] == 0) {
                used[x] += 1;
                foreach (immutable uint y; 0 .. turn) {
                    immutable tmp_index = x + x - oranges[y];
                    if (tmp_index >= 0 && tmp_index < BOWLS) {
                        used[tmp_index] += 1;
                    }
                }
                oranges[turn] = x;
                count += solve!(turn + 1)(x + 1, used, oranges);
                foreach (immutable uint y; 0 .. turn) {
                    immutable tmp_index = x + x - oranges[y];
                    if (tmp_index >= 0 && tmp_index < BOWLS) {
                        used[tmp_index] -= 1;
                    }
                }
                used[x] -= 1;
            }
            x += 1;
        }

        return count;
    }
}

void main() {
    import std.stdio;

    Used used = 0;
    Oranges oranges = 0;
    writeln(solve!0(0, used, oranges) == 7_555_794);
}

Is the current minimal Rust proposal including a “static if”?


#64

No, but static if is only needed if the function can’t compile with plain if, they’ll optimize the same.

And in Rust, you typically want a trait to dispatch on types or type-level constants anyway, if you can’t use a single body.


#65

Right, as in the example I’ve shown, solve9() is so short to avoid those errors. And it’s a quite common situation (that’s why D has static if since lot of time).

And in Rust, you typically want a trait to dispatch on types or type-level constants anyway, if you can’t use a single body.

That’s roughly how the C++ code above does, with the solve<N_ORANGES>() case. But from my long experience with using templates in D, having multiple bodies is not handy, expecially if your function is templated on more than one constant. The advantage of “static if” is that you can specialize only parts of a function, even multiple times inside one function. I can show a (not artificial) C++ example where this gives hairy code, while the equivalent D code is still readable.

Thankfully a “static if” feature is quite independent from constant generics, so we can add it later if we want it.


#66

Huh?

The point is that as long as the program still typechecks with regular if, it can be used as a replacement for static if with equivalent codegen, since LLVM will optimize away always-taken or never-taken branches.

That seems to be the case with your solve.

Actually, not quite, because the recursive call will go on to infinity during type checking. There are ways around that though…


#67

There are more problems, like the line of code like:

oranges[9] = x;

That gives a “index out of bounds” at compile-time, and there are expressions like “(N_ORANGES - 9 - 1)” that give “expression will panic at run-time” at compile time.

Right, the simplest for the programmer is probably the “static if” as implemented in D language.


#68

Not in Rust, you need the C++ template expansion model (which D has to use for most of its metaprogramming) to even have this as an error.

IIRC the only such “post-monomorphization” errors left in Rust are from inline assembly, which LLVM has to check.


#69

(What about the thing with specialization and lifetimes, which I can’t remember the details of atm?)


#70

We decided to take the approach where we never error from it and never specialize on lifetimes, but it hasn’t been implemented yet.


#71

It only just occurred to me: regarding syntax, can we pick something that is easy to capture with macro patterns? My guess is that interspersing const is not, while the ; separated one is pretty trivial to match. In the latter case, though, it would help to allow ; even when it’s not syntactically necessary.


#72

Assuming we keep kind ordering (I want to), wouldn’t the match be

macro_rules! _ {
    ($(const $c:ident : $t:ty),*) => {}
}

#73

O, with kind ordering, that’s trivial, I agree. Was that fact made explicit? I thought that wouldn’t be the case, in order to support, e.g. not needing to specify default type parameters. Again, this would be trivial with the ; version, but not obviously so with kind-ordered const version unless it were designed to support that (i.e. the presence of the first const would imply the rest of the unspecified type parameters were defaulted).


#74

My implicit question for this thread was: what’s going to look a Rust version of the D language solution above using the proposed const generics? Could you show how the code is going to look?

(More generally, in my opinion important language enhancement proposals should be presented&discussed with few little example usages different from each other, that show how the feature will look in a reasonable range of tiny but practical real-world use cases, like the tiny use case example I’ve shown above).

Other possible use cases are the tuples/tuple_windows of Itertools: https://docs.rs/itertools/0.6.0/itertools/trait.Itertools.html

Is this correct?

for (a, b, c) in (1..5).tuple_windows::<3>() {}    

for (a, b) in (1..5).tuples::<2>() {}

And similarly for permutations (this is lazy and similar to the itertools.permutations of Python):

for (a,b,c,d) in (0 ... 10).permutations::<4>() {}

#75

I think that would be blocked on the tuple generics RFC. In any case it would not be possible with the first basic version of integer generics.


#76

Specialization.

pub fn solve<const TURN: usize>(args...) -> usize {
   <() as Solver<TURN>>::solve(args...)
}

trait Solver<const TURN: usize> {
    fn solve(args...) -> usize;
}

default impl<const TURN: usize> Solver<TURN> for () { ... }
impl Solver<ORANGES> for () { }

Specializations’ dependence on traits, and traits requirements for a type input parameter, is a little unfortunate in examples like this. But in theory I believe we could specialize free functions someday. More important to me is that instead of appearing in the body of the function as a conditional, static if is lifted into the type signatures of multiple specializations, making the code much more clearly organized.

Examples involving multiple such parameters just need intersection impl specialization, which is an anticipated extension of the feature. Again I find this very advantageous: unlike essentially ‘reflecting’ on constants, and having the intersection be whatever happens to fall out of the control flow, you have to explicitly think about the intersection of all of your specialization possibilities.

The primary use case of this feautre is not so extreme: most users just want to be able to == on arrays of arbitrary length.


#77

Not really. You couldn’t get anything you can’t already do with types. We can’t magicallly go from 3 to (A, B, C), you’d need some sort of trait impl which associates 3 with (A, B, C). In practice that’s not different than TupleCollect.

As est31 linked, for that we’d need some kind of variadic generics.


#78

I probably have to use what you say to tell how much organized it becomes, but from my experience of C++/D coding, it’s the “static if” of D that makes my code much more clearly organized/clean/readable compared to the way C++11 templates are.


#79

The example I’ve shown is one of the basic usage cases, it’s far from extreme :slight_smile:


#80

That’s exactly why they adopted static if in C++ as well. And also going to adopt static for too, to replace recursions/specializations with variadics.


#81

D templates are much more similar to C++ templates than to Rust generics. Both operate on a syntactical level, and IMO if the content of static ifs is not type checked, this just does not fit well into the Rust model.

THB I very much prefer the declarative style of Rust generics over the duck typing / compile time introspection of D and I don’t want Rust to become a second D.