spec: add generic programming using type parameters

[ianlancetaylor]

We propose adding support for type parameters to Go. This will change the Go language to support a form of generic programming.

A detailed proposal document has been published, with input from many members of the Go community. We are now taking the next step and proposing that this document become a part of the language.

A very high level overview of the proposed changes:

• Functions can have an additional type parameter list that uses square brackets but otherwise looks like an ordinary parameter list: func F[T any](p T) { ... }.
• These type parameters can be used by the regular parameters and in the function body.
• Types can also have a type parameter list: type MySlice[T any] []T.
• Each type parameter has a type constraint, just as each ordinary parameter has a type: func F[T Constraint](p T) { ... }.
• Type constraints are interface types.
• The new predeclared name any is a type constraint that permits any type.
• Interface types used as type constraints can have a list of predeclared types; only type arguments that match one of those types satisfy the constraint.
• Generic functions may only use operations permitted by their type constraints.
• Using a generic function or type requires passing type arguments.
• Type inference permits omitting the type arguments of a function call in common cases.

For more background on this proposal, see the recent blog post.

In the discussion on this issue, we invite substantive criticisms and comments, but please try to avoid repeating earlier comments, and please try to avoid simple plus-one and minus-one comments. Instead, add thumbs-up/thumbs-down emoji reactions to comments with which you agree or disagree, or to the proposal as a whole.

If you don't understand parts of the design please consider asking questions in a forum, rather than on this issue, to keep the discussion here more focused. See https://golang.org/wiki/Questions.

[tsal]

Why any and not interface{} ?

an interface{} wouldn't make sense here since we're describing a generic trait that needs to be implemented. This is more meta-code and interface{} is still concrete - even if it is "generic" in some senses of the word.

I'm also having trouble thinking how you could implement any interface{} generic parameters, since you don't know what the interface will actually be - and if you're doing interface type-checking here, it's defeating the entire point of generics (IMO).

[bcmills]

I remain concerned that this proposal overloads words (and keywords!) that formerly had very clear meanings — specifically the words type and interface and their corresponding keywords — such that they each now refer to two mostly-distinct concepts that really ought to instead have their own names. (I wrote up this concern in much more detail last summer, at https://github.com/bcmills/go2go/blob/master/typelist.md.)

---

Specifically, the word type today is defined as:

A type determines a set of values together with operations and methods specific to those values.

Under this proposal, I believe that a type would instead be either a set of values with operations, or a set of sets of values, each with its own set of operations.

And today the word interface, in the context of Go, refers to a type, such that:

A variable of interface type can store a value of any type with a method set that is any superset of the interface.

Under this proposal, a variable of interface type can store a value of any type with a method set that is any superset of the interface, unless that interface type refers to a set of sets of values, in which case no such variable can be declared.

---

I'd like to see more detail on the exact wording proposed for the spec, but for now I am against this specific design, on the grounds that the ad-hoc overloading of terms is both confusing, and avoidable with relatively small changes in syntax and specification.

[flibustenet]

func foo[T Stringer](t T) string {
	return t.String()
}
func foo(t Stringer) string {
	return t.String()
}

The difference are very subtil. How will you document the best practice when a Go1 interface is enough ?
I mean, how to prevent abuse of generic when both can be used ?

[nadiasvertex]

Would still prefer to have the empty interface. How tedious can this really be? Especially since we can define type aliases ourselves...

I think interface{} is a mistake. It is a hack to permit something like void * without any semantic cues to help a user understand what is going on. I would have preferred to have "any" as a type in the language from the beginning, even it it was just an alias for interface{} under the covers.

Of course, the new "any" is different than interface{}. It would be nice to have a named type that means "any type by reference" instead of "any type by substitution".

[michaelwilner]

```go
func foo[T Stringer](t T) string {
	return t.String()
}
func foo(t Stringer) string {
	return t.String()
}

The difference are very subtil. How will you document the best practice when a Go1 interface is enough ?
I mean, how to prevent abuse of generic when both can be used ?

Valid point, in your example, an interface would be the better choice. However, a more apt use case of generics would be sort. Operations on slices of arbitrary types would be distinctly less verbose with generics as compared to interfaces. This talk touches on some of the points: blog.golang.org/why-generics (disclaimer: syntax in this link is different than this generics proposal, but the points are useful to draw comparison)

[JeremyLoy]

What are the plans for amending the standard library to utilize generics? I see two important tracts of work here.

1. retroactively applying generics to packages like sort, container/list
2. Creating new packages and libraries that were previously cumbersome without generics; i.e. mathematical set functions,

[coder543]

@bcmills

Specifically, the word type today is defined as:

A type determines a set of values together with operations and methods specific to those values.

That sentence describes a struct. An interface is also a kind of type in Go, and it does not determine the set of values or operations that are present, only the set of methods.

The fact that a type is not just a struct is why the syntax in the language is type foo interface { ... }, type foo struct { ... }, and even type foo bar or type foo = bar.

A generic type is just as concretely a set of values, operations, and methods as an interface is (which is to say, you an argue that it isn't). So either we should redefine interface to not be a type (by the definition you're quoting), or we should accept that a generic type is also a type, just one that requires type parameters to be resolved before it becomes a concrete type.

If the proposal is misusing the term "type" in place of "type parameter" anywhere, I think that could be valid criticism... but it sounds like you're criticizing some ambiguous/arguably wrong terminology that exists in the Go language spec, which is terminology that is refuted by the language itself, as demonstrated by Go syntax above. If an interface is not a type, we should not prefix the declaration with the word type, but we do.

That whole area of discussion seems off topic here, and clarifications to the existing language spec could be proposed somewhere else? I've read through the generic proposal several times and I haven't come away feeling like the terminology used was ambiguous or confusing, and your statements here do not effectively make the case for that either, in my opinion.

[fzipp]

Of course, the new "any" is different than interface{}.

The new "any" is not different from interface{} as a type constraint. [T any] and [T interface{}] are interchangeable as per the proposal.

[IceWreck]

What are the plans for amending the standard library to utilize generics? I see two important tracts of work here.

1. retroactively applying generics to packages like `sort`, `container/list`

2. Creating new packages and libraries that were previously cumbersome without generics; i.e. mathematical set functions,

Yes, and after generics are implemented, I hope the container package will be expanded to include other common data structures present in c++/java std libs

[zephyrtronium]

@bcmills

Specifically, the word type today is defined as:
A type determines a set of values together with operations and methods specific to those values.

That sentence describes a struct. An interface is also a kind of type in Go, and it does not determine the set of values or operations that are present, only the set of methods.

The interface type definition specifies the methods (which are operations) present on values of that interface type. Because values must implement the interface to be used as that interface type, the interface type does indeed determine a set of values (always a superset of other types').

[fzipp]

func foo[T Stringer](t T) string {
	return t.String()
}
func foo(t Stringer) string {
	return t.String()
}

The difference are very subtil. How will you document the best practice when a Go1 interface is enough ?
I mean, how to prevent abuse of generic when both can be used ?

I'd expect a linter warning: "useless use of type parameter"

[coder543]

@bcmills

Specifically, the word type today is defined as:
A type determines a set of values together with operations and methods specific to those values.

That sentence describes a struct. An interface is also a kind of type in Go, and it does not determine the set of values or operations that are present, only the set of methods.

The interface type definition specifies the methods (which are operations) present on values of that interface type. Because values must implement the interface to be used as that interface type, the interface type does indeed determine a set of values (always a superset of other types').

If you want to go down that route... the same exact thing applies to the "overloading" of "type" to refer to generic types as well. In order for a value to be substituted for a type parameter, it must implement the interface constraints, and to do that, it must be a concrete type. Therefore, a generic type "does indeed determine a set of values (always a superset of other types)".

It's the same thing. Either an interface is a type (in which case, it's fine for the proposal to use its current terminology), or it's not (in which case it's not okay for the Go language to define interfaces as types).

Either way, someone could propose that the Go language spec is written in a confusing way in the quoted section, but it wouldn't change any outcomes regarding this proposal or the current-day reality of Go.

[DeedleFake]

@bcmills

Specifically, the word type today is defined as:
A type determines a set of values together with operations and methods specific to those values.

That sentence describes a struct. An interface is also a kind of type in Go, and it does not determine the set of values or operations that are present, only the set of methods.

The interface type definition specifies the methods (which are operations) present on values of that interface type. Because values must implement the interface to be used as that interface type, the interface type does indeed determine a set of values (always a superset of other types').

In general, methods in Go are tied to type definitions and behave, in a lot circumstances, like any other function except that there's an argument placed before the function name. That's why, unlike most languages, Go allows you to call a method on a nil pointer no problem, meaning that you can handle the nil pointer case in the method itself instead of elsewhere.

Interfaces are a strange exception to this. Despite the fact that a type is defined, as in type Example interface { /* ... */ }, attempting to declare methods on that type will fail, purely because the underlying type is of kind interface. This dichotomy has always existed in Go, and it's always kind of bugged me, but it's a very minor thing that's basically never any kind of problem in practice, and I don't really think that the usage of interfaces in this proposal changes that much at all.

[griesemer]

@p-kraszewski The most up-to-date development is happening on the dev.typeparams branch. The dev.go2go branch was used to develop a prototype and the go2go playground; general development of that has been suspended in favor of a real implementation in dev.typeparams. But we hope to update dev.go2go occasionally to keep the go2go playground in reasonably good shape.

[DeedleFake]

Is it possible to create a chan T when T has constraint any? I did not find mention of channels in the section "Operations permitted for any type".

I think that you're confusing the declaration of a type parameter and the usage. The parameters are declared in function and type declarations and are essentially scoped to those functions and types. For contrived example,

//    declaration       usages
//        v             v    v
func Send[T any](c chan T, v T) {
  c <- v
}

Once they're declared, there basically isn't any difference in terms of usage between the type parameters and any other type, so they can be used as the element type of a channel, or the element type of a slice, or an argument to a function, or basically anything else.

[stigsb]

func foo[T Stringer](t T) string {
	return t.String()
}
func foo(t Stringer) string {
	return t.String()
}

The difference are very subtil. How will you document the best practice when a Go1 interface is enough ?
I mean, how to prevent abuse of generic when both can be used ?

govet or golint could help with that.

[zikaeroh]

func foo[T Stringer](t T) string {
	return t.String()
}
func foo(t Stringer) string {
	return t.String()
}

The difference are very subtil. How will you document the best practice when a Go1 interface is enough ?
I mean, how to prevent abuse of generic when both can be used ?

I'd expect a linter warning: "useless use of type parameter"

@fzipp That wouldn't be entirely accurate as a warning. Depending on the compiler's devirtualization pass, the two would have different performance characteristics. Assuming the "stenciling" approach for implementing generics, each version of foo would be expanded out to each specific type to generate the most efficient code, and the former would be faster as the compiler knows exactly what String to call, while in the latter the compiler may potentially box the value into an interface type and then have to look up the correct String for the type it gets.

[gopherbot]

Change https://golang.org/cl/291990 mentions this issue: doc/faq: update generics entry to reflect accepted proposal

[ianlancetaylor]

@fzipp Thanks, done (for the 1.16 release which should be out quite soon).

[gopherbot]

Change https://golang.org/cl/292290 mentions this issue: _content/doc: add go_faq.html change

[truesilver92]

@beoran

Personally, I don't understand why or how variadic type-parameters would be used, so I can't really envision syntax and semantics for them. But I think we can trust the Go team to pay attention to this.

To build a function for currying functions, etc.

Does anyone know if you can match the parameter types of functions passed in as parameters in this proposal? Small changes to the syntax above for adding that and variable number of types:

func Curry[func[ParamTs ...any], Ts ...any] (funcToCurry[ParamTs ...any] (...ParamTs), args ...Ts) {
  // body of function
}

Writing the above just makes me miss lisp/haskell honestly. I didn't even try doing the return type

[DmitriyMV]

@truesilver92

No variadic type parameters. There is no support for variadic type parameters, which would permit writing a single generic function that takes different numbers of both type parameters and regular parameters.

https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md#omissions

[rsc]

In #43651 (comment) I wrote

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

That is our usual way of using issues, but this issue continues to gather comments that are not relevant to tracking the work of implementing the proposal. Honestly, that was probably inevitable and understandable. But it's no longer the place for comments and questions about the proposal itself.

I'm going to lock this issue and close it. We won't forget about the implementation without a tracking issue, I promise.

[gopherbot]

Change https://golang.org/cl/303389 mentions this issue: design: promote type parameters to a proposal

[gopherbot]

Change https://golang.org/cl/306689 mentions this issue: design: update type parameters design for type sets

[gopherbot]

Change https://golang.org/cl/343732 mentions this issue: cmd/compile: enable -G=3 by default