Add const generics

[shuklaayush]

Problem

The type system treats generic arguments as a NamedGeneric irrespective of whether they're normal types or numerical constants.

It would be great if you could explicitly declare generic types as comptime (analogous to rust's const generics) and be able to do something like the following:

global M: comptime Field = 2;

fn f<N: comptime Field>() -> [Field; M + N] {
    ...
}

The N here would be treated as a Constant instead of a NamedGeneric and thus we'd be allowed to do operations over it.

Happy Case

Make something like this work:

global M: comptime Field = 2;

fn f<N: comptime Field>() -> [Field; M + N] {
    ...
}

Alternatives Considered

Declare N as a global constant instead

global M: comptime Field = 2;
global N: comptime Field = 1;

fn f() -> [Field; M + N] {
    ...
}

Additional Context

No response

Would you like to submit a PR for this Issue?

Maybe

Support Needs

I'm happy to help out if this is useful and not too difficult to implement.

[jfecher]

One issue with allowing comptime type parameters is that comptime is slightly different from rust's const. Namely, it is a bit more flexible in that normal functions can accept comptime parameters. This is used to e.g. verify an array index is known at compile-time. Note that the "known at compile-time" here means "known after function inlining is performed while optimizing the program" and not "known during type-checking." So if we allowed comptime type parameters we still wouldn't know the value of any comptime variable passed in as function parameters.

To fix this there are a few options:

1. Add a separate const concept to mirror the concept of the same name in Rust. I think this would be too confusing for users having two separate concepts for whether something is known at compile-time or not, with only subtle differences between the two.
2. Disallow comptime on function parameters. Although this is a breaking change, it is something we may do eventually since we now allow dynamic indexing for arrays anyway. So there is no technical need to typecheck these indices are known at compile-time anymore, there would just be a slight performance loss if they are not. This would probably be the cleanest method to get const generics working but would be a breaking change.
3. Try a hacky solution of keeping comptime and adding a check when a variable is used in a comptime type position that it is not a comptime parameter. Presumably we'd issue an error message to users explaining why comptime parameters cannot be used as comptime type parameters.
4. Go the nuclear route and make all comptime parameters known to the typechecker by adding a selective inlining pass before type checking to inline all comptime parameters into their use site. This could work but would be a very large change, effectively requiring an entire partial interpreter able to interpret any bit of Noir code but also able to do so only partially, leaving any non-comptime code unaffected.

Each of these options come with their own fair share of difficulties which is why this feature isn't present yet in Noir.

[kevaundray]

Noting that #2178 removes the concept of comptime

[vezenovm]

Going to close this issue now that #5155 is merged.