proposal: Go 2: Const generics

[dawidl022]

Introduction

#44253 proposes to introduce generic parameterization of array sizes. The issue has been open for 3 years, with seemingly no recent progress.

The new proposal differs in that it introduces an explicit numerical const type parameter, and restricts the kinds of expressions that can be used to instantiate a const type parameter to existing constant expressions evaluating to non-negative integers, and lone const type parameters, in the same fashion as Rust.

Having this restriction in place limits the problems const generics can solve, but it also eliminates a lot of complexity associated with implementing const generics, which were discussed in the issue of the previous proposal.

If the community is happy to proceed with this proposal, I would like to have a go at implementing the feature. As such, any concerns regarding potential implementation difficulties would be appreciated!

Proposal

The basis of this proposal is to introduce a new set of types that can be used as type arguments. This new type set would be made up of constant non-negative integers. Since interfaces represent type sets in Go, we can (conceptually) define such a type as:

type const interface {
    0 | 1 | 2 | 3 | ...
}

where the ... denotes that the pattern continues for all non-negative integers supported by Go. The const interface can be used to constrain a type parameter, and since it is a non-basic interface it cannot be used as the type of a variable (we can already use const declarations to hold values, but they are broader than this proposed interface).

Array types accept two "type" parameters - the length and the element type. The constraint of the length parameter is exactly the const interface. This proposal generalises the const interface to be applicable to user-defined type parameters - those we know from generics.

Since all type parameters also implement their own constraints (i.e. a type parameter constrained by T can be used as a type argument constrained by the same type, or a supertype of T), it means that const type parameters can be used to instantiate other const type parameters, including array lengths.

Expressions involving type parameters, other than a lone const type parameter N, cannot be used as const type arguments. This approach is used by Rust and can make the implementation much more feasible. E.g. the following would not be allowed:

func foo[N const]() {
    // compile-time error: the expression `N + 1` cannot be used as a type argument
    foo[N + 1]()
}

In addition, despite const type parameters implementing const themselves, when used as a value, as opposed to a type parameter, they would evaluate to a non-constant int. E.g. the following would not be allowed:

func foo[N const]() {
    // compile-time error: type parameter N cannot be used as constant value
    const n = N
}

This is to avoid n being used as part of another constant expression that is then used as a const type argument, in effect enforcing the previous limitation of no "no complex generic expressions in const arguments".

The above restriction also resolves the issue that was heavily discussed in #44253 (comment) of exploiting const type parameters to perform complex compile-time computation, such as SAT solving.

Expressions that are formed from a const type parameter, would follow the same rule, i.e. evaluate to a non-constant value, even if their non-generic counterparts would be computable at compile time. E.g. len of a generic array would evaluate to a non-constant integer.

func foo[N const]() {
    // compile-time error: expression containing type parameter N cannot be used as constant value
    const n = len([N]int{})
}

The const interface would be a predeclared type.

Examples

One of the simplest useful examples is declaring a square matrix type:

type Matrix[T any, N const] [N][N]T

which can then be instantiated as follows:

myMatrix := Matrix[int, 2]{{1, 2}, {3, 4}}

Of course, const type parameters can also be used directly in functions:

func reversed[T any, N const](arr [N]T) [N]T {
    for i := 0; i < N/2; i++ {
        arr[i], arr[n-i-1] = arr[n-i-1], arr[i]
    }
    return arr
}

Who does this proposal help, and why?

This proposal is aimed at experienced Go users, who have justified use cases for using arrays over slices, and would enjoy the benefits of reduced code duplication with const generics, or would like to expose some generic functionality using underlying arrays as part of a library.

Language Spec Changes

Array types would also accept TypeNames, which (in my understanding) type parameters fall under.

ArrayLength = Expression | TypeName .

Types would also include constant expressions, more precisely constant expressions that evaluate to non-negative integers. They would be used to instantiate const type parameters.

Type = TypeName [ TypeArgs ] | TypeLit | Expression | "(" Type ")" .

Type constraints would accept the keyword const to denote the interface containing all non-negative integer types.

TypeConstraint = TypeElem | "const" .

Other considerations

Is this change backward compatible?

Yes, this change is backwards compatible. It is not possible to name a regular interface the keyword const, so no existing code would break.

Orthogonality: How does this change interact or overlap with existing features?

Explicit numerical type parameters would make generic arrays a first-class feature of Go, consistent with the rest of the language. All the existing compound data types in Go can already be fully type parameterised (slices: []T, maps: map[K]V and channels: chan T), except for arrays, so this feature would bridge that gap with [N]T.

Numerical type parameters would also become first class. Currently, arrays are the only types that accept a numerical type parameter, to parameterize the length of an array type. The const interface would allow any type or function to accept a constant integer (or another const-bounded type parameter) as a type argument.

Would this change make Go easier or harder to learn, and why?

Seeing that this is an additional language feature, it would make Go more difficult to learn simply because there is one feature more. The rest of the language will be unaffected in terms of easiness of learning.

Cost Description

• What is the compile time cost?

The cost should be approximately the same as the existing cost of compiling generic code.

• What is the run time cost?

This depends on how the feature will be implemented. Using a full monomorphisation model, there would be no runtime costs over using non-generic arrays. Using the GC shape stencilling approach would likely have the same runtime cost as existing generic code.

Prototype

I am working on a paper in the style of Featherweight Go, that formalises arrays and numerical type parameters that would be implemented as part of this proposal. It will come with prototype interpreters (with static type checking) for the new language feature in the style of https://github.com/rhu1/fgg (i.e. for a subset of Go). I hope to make this publicly available, sometime post-May this year.

Has this idea, or one like it, been proposed before?

In this new proposal, the const type parameter is explicit, which is consistent with the existing generics system in Go, and makes it immediately obvious to the programmer when a type is parameterised on an integer value.

In addition, this new proposal places restrictions on how const type parameters can be used, in particular when used as values they evaluate to non-constant integers, and cannot be part of a more "complex" expression used as a type argument. This means that the example presented in the previous proposal's design document cannot be implemented using const generics as presented in this new proposal. The feasibility of lifting some of the restrictions to make constructs as in the example possible is a topic for a potential future language extension.

Go Programming Experience

Experienced

Other Languages Experience

Rust, Kotlin, Java, TypeScript, Python

Related Idea

• Has this idea, or one like it, been proposed before? Yes
• Does this affect error handling? No
• Is this about generics? Yes
• Is this change backward compatible? Yes

Is this about generics?

Yes, this change fits into the existing generics design in Go by making the const constraint an interface type.

[ianlancetaylor]

CC @griesemer

[ianlancetaylor]

Thanks, this is an interesting idea. I'm concerned that using const as the constraint will make it difficult for us to add any other type of numeric constraint. It's not clear that we would ever want any such constraint. But if we ever do, it's not going to be able to look like const. We should also bear in mind that there are other kinds of constraints that we can't express, like saying that one type parameter must be assignable to another. We want to make sure that the "constraint language" is consistent and has good support for everything we might want to do in the future.

[leaxoy]

Some grammar references in other languages:
CPP:

template<class T, int L>
struct vec {
    std::array<T, L> arr;
    ...
};

RUST:

fn foo<const N: usize>(arr: [i32; N]) {
    // Used as a type within a function body.
    let x: [i32; N];
    // Used as an expression.
    println!("{}", N * 2);
}

Go and rust have similar type syntax structures, both of which are type-postfix syntax.

So I think another possible syntax is to add the const keyword in front of the type parameter.

func anyLenArr[E any, const Size ~int, A ~[Size]E]() A {}

// const mark Size is value, not a type.
// Size can be any type that underlying is int or other core types.

// usage:
func x() {
    a := anyLenArr[int, 10]()
    then a is [10]int
}

[dawidl022]

I'm concerned that using const as the constraint will make it difficult for us to add any other type of numeric constraint. It's not clear that we would ever want any such constraint. But if we ever do, it's not going to be able to look like const.

One potential way of expressing other numerical constraints could be to make const itself generic. E.g. we could have const[uint8], const[float64], that would accept numerical type arguments from the range of the type const is instantiated with.

As far as I'm aware, there is no explicit numerical type for array lengths. The spec says:

it must evaluate to a non-negative constant representable by a value of type int

so having the lone const constraint represent that concept seems reasonable.

Another possibility for creating other types of numerical constraints, could be to set some explicit bounds on the constraint, e.g. using the familiar slicing notation. const[1:] would represent any numerical (int) type parameter greater than equal to 1. This could be used to e.g. define the allowed compile-time checked operations on an array of such a length.

In the current proposal, indexing a generic array by a constant is not allowed, since the code should be valid for all instantiations. E.g.

func first[N const](arr [N]int) {
    return arr[0] // compile-time error
}

would not compile, since [0]int is a valid instantiation of [N]int. However, if we constrain the type parameter to const[1:], then this operation becomes valid, since the function first now only accepts arrays of at least length 1:

func first[N const[1:]](arr [N]int) {
    return arr[0] // allowed and safe (no runtime panics can occur)
}

Explicit lower and upper bounds could also be used to loosen some of the restrictions imposed by this proposal, namely of using constant expressions that involve const type parameters and other constants as type arguments, to make the examples presented in the #44253 proposal possible.

We can of course combine the two concepts, and define the constraint that can be used for any array lengths as the spec defines it:

func foo[N const[int][0:]](arr [N]int) {
    // some code
}

But since const[int][0:] seems like a common use case, using const as a shorthand for the same type would be convenient anyways.

Of course whether or not we'd like to introduce such elaborate numerical type constraints is a topic for a future discussion, but I believe introducing a simple const constraint to begin with would not make defining the elaborate constraints building on top of const impossible.

We should also bear in mind that there are other kinds of constraints that we can't express, like saying that one type parameter must be assignable to another.

Do I understand correctly, that by "one type parameter must be assignable to another" we mean that one must implement the other? I believe this could be expressed by making one type parameter the constraint of the other (which is not currently allowed in Go).

func foo[B any, A B](a A) {
    var myVar B = a
    // some more code
}

We want to make sure that the "constraint language" is consistent and has good support for everything we might want to do in the future.

Is there a list I can check out of things we might want to express using type parameter constraints in the future? I would be happy to have a look and consider how this might affect the design of const generics. So far, having type-set interfaces seems to work well, and we already have "special" constraints for built-in operations such as comparable. So we can either view const as in the same bucket as comparable, or as type-set interfaces being extended with "value sets" (such as numerical values of specific types or subranges of those types, or even individual values such as 0 | 1, similar to literal types in TypeScript). Value sets could also be used as enum types.

[ianlancetaylor]

Do I understand correctly, that by "one type parameter must be assignable to another" we mean that one must implement the other?

No, I mean something like

func ConvertSlice[T1, T2 any](s []T1) []T2 {
    r := make([]T2, len(s))
    for i, v := range s {
        r[i] = T2(v)
    }
    return r
}

This could be used, for example, to convert a []int8 to a []int16 or to convert a []int to a []any.

We can't write this today because we have no way to say that we can convert a value of type T1 to a value of type T2, so the expression T2(v) is a compilation error.

To be clear, I don't think that this issue is a good place to discuss how to handle this case. I'm only mentioning that we may not want to limit our future handling of constraints by reserving const for this rather special-purpose, although useful, case. It's not too hard to see how to solve one problem today, but before taking that step we should at least consider how to solve several problems tomorrow.

[dsnet]

This particular proposal focuses on Go arrays as the motivation, but I want to present two concrete use cases for the concept of parameterized constants:

1. We have a rate.Value that computes the rate of something using an exponentially weighted average. The algorithm is tuned with a single constant, which can be expressed as a "half life", which is a time.Duration. In practice, there is only a small and finite number of half-life values that we would realistically use (e..g, 1s, 1min, 15min, etc.). Right now, the HalfLife is embedded as a field in the rate.Value struct, wasting memory to represent the mostly the same value repeatedly. Ideally, we could specify something like rate.Value[time.Second] to specify a rate with a half-life of 1s.

2. There's a binary format called CBOR that supports type tags (i.e., essentially a numeric ID that identifies the concrete type of a serialized value). I would like a generic way to wrap any arbitrary Go type and annotate it with a type ID that a serialization package would then know to emit in serialized output. For example:

   type TaggedValue[T any, N const] struct { Value T }
   
   func (v TaggedValue[T, N]) TypeID() uint64 { return N }
   func (v TaggedValue[T, N]) Unwrap() any { return v.Value }

   The advantage of using generics is that it results in unique instances of TaggedValue that maps to a particular combination of T and N. This allows a serialization library to reflect on instances of TaggedValue and cache how to serialize them. If TaggedValue were just a non-generic struct with a TypeID field, then the serialization library can't reason that the TypeID is static for all possible instances of TaggedValue.

   It also simplifies the API for registering known type tags, since you just need to pass in types that implement interface { TypeID() uint64 }. (There's an implicit requirement that the TypeID method for a particular type statically returns the same value)

In both of my use cases, the constant is typed to time.Duration or uint64. IIUC, the current proposal doesn't provide a way to express this constraint.

[atdiar]

If I am not misunderstanding, is the goal to be able to parameterize an instantiation by a (const) value instead of a type?

In which case, the more general handling could also be to consider a value as a subtype (where the set of values for this type is a singleton).

type Un int {1}
type someints int { 1, 2, 3}

That would also deal with questions about enums especially if we have generalized interfaces/unions. (enums would not be a specific construct but simply stem from subtyping + unions, for the kind of subtypes that would be allowed to be written in Go).

In a sense, that should be a form of dependent typing but more limited, practical and tractable.

[dawidl022]

Syntax for general const types

It's clear from the comments that it's worth considering generalising the proposal to other const types, not just for array lengths.

In which case, apart from the const keyword, the type of values should be specifiable in the constraint, e.g. uint8, or int64.

Syntactically, we have a number of options, e.g.:

1. chan T style postfix: const T

   func foo[N const int]() {
       // some code
   }

2. map[K]V style postfix: const[T]

   func foo[N const[int]]() {
       // some code
   }

3. Rust style: const N T

   func foo[const N int]() {
        // some code
   }

My preference is for 1 or 2 because it plays better with using a single constraint for multiple type parameters:

type Matrix[N, M const[int]] [N][M]int

With option 3 this would be a bit awkward:

type Matrix[const N, M int]

const T or const[T] can be seen as a type, just as chan T and map[K]V are types, as opposed to const being some sort of type constraint modifier in option 3.

Array length type

According to the spec, the length of an array type:

must evaluate to a non-negative constant representable by a value of type int

This means that neither int nor uint captures the valid values for array lengths, and so in theory neither const[int] nor const[uint] could be used to constrain a numerical type parameter used to size an array since the programmer could instantiate such a type parameter with:

1. a negative value for const[int]
2. a value larger than math.MaxInt for const[uint]

We could either loosen the restrictions and allow arrays to be sized by uint (not sure how this would affect things internally), or introduce a new way of expressing such a type, e.g. aint (array int).

Then const[aint] could be used to denote the type parameter that can be used to size an array. Alternatively (or in addition to), we could have a lone const be the shorthand constraint for const[aint].

Types with underlying const types

To address the issue of using types such as time.Duration as a const type parameter, we have a couple of options (or we can use all of them):

1. Allow types which have underlying types that can be const to be used as const constraints, e.g. const[time.Duration]. Such a constraint can only be instantiated with constants of type time.Duration (or untyped constants).
2. Allow type set const constraints, e.g. const[~int64]. Such a constraint can be instantiated with any typed constant whose underlying type is int64 or an untyped constant.
3. Use conversions where necessary to convert const type parameters to other types, e.g. time.Duration(N) where N is a type parameter bound by const[int64]. If the underlying type of the target type matches with the const constraint type (int64 in the example), then this conversion can be done at compile time. This avoids the problem of determining whether a type conversion can be allowed at compile time, discussed in proposal: spec: generic parameterization of array sizes #44253 (comment).

Value-set types

If I am not misunderstanding, is the goal to be able to parameterize an instantiation by a (const) value instead of a type?

Yes, the goal is to parameterise an instantiation of a type parameter by a const value, instead of a type.

In which case, the more general handling could also be to consider a value as a subtype (where the set of values for this type is a singleton).

Indeed, when writing this proposal and the formal work on the topic, I did view the values used to instantiate const type parameters as subtypes of the const constraint.

As briefly mentioned in my previous comments, we could extend interface types to include value sets (or use an entirely different construct altogether), and allow constructs like the following:

type myAlgorithmParameters interface {
    time.Second | time.Minute | 15 * time.Minute
}

And then use myAlgorithmParameters as a type parameter constraint that can be instantiated with one of the three constant values.

I think the specifics of such constructs and their usefulness could be a topic for a future discussion (e.g. whether value-set types should be wrapped in const when used as a constraint, whether they can be used as types of regular variables to express the enum concept, etc.).

[atdiar]

Ahhh this const... I'd hope for const to not be necessary.
A type is always a value set but if the value set is a singleton, then it's const by definition.

The thing is that const is mainly a modifier token for an identifier. It doesn't really modify the type but rather constrains the identifier.

A way to see it is that it constrains a variable to not be reassignable, neither in totality nor in parts (via interior mutability).

The difficulty might reside in the handling of interior aliasing/mutability in order to ensure value equality.
Probably the reason why we do not have const struct values.

Probably doable in conservative ways.
Either find and disable mutating method but that might require a mix of intra- and inter-procedural analyses.
Or establish the rule that, for those extensionally/discretely defined subtypes, calling the methods defined on the supertype requires an assertion/assignment/conversion.

[ianlancetaylor]

From the discussion it seems that while this proposal would be useful, there are several other uses of constant type arguments that would also be useful. If we do anything in this area we should aim for something that solves several problems rather than just this one. Therefore, this is a likely decline. Leaving open for four weeks for final comments. Thanks.

[dawidl022]

@ianlancetaylor I believe I have addressed how we can generalise const generics in my comment above based on the discussion. Please let me know if there is anything I have missed out, and I would be happy to give it some thought.

I agree that we should aim to solve several problems, rather than just this one, as such, I am happy to adapt my initial proposal as many times as necessary.

[ianlancetaylor]

Thanks, but I think we should restart with a consistent proposal that covers all the important cases, rather than a list of options.

[ianlancetaylor]

No change in consensus.

[dawidl022]

If anyone is interested, I've made available a prototype (interpreter) implementation along with a more detailed theoretical discussion (in the style of Featherweight Go) at https://github.com/dawidl022/go-const-generics.