Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

spec: add generic programming using type parameters #43651

Closed
ianlancetaylor opened this issue Jan 12, 2021 · 453 comments
Closed

spec: add generic programming using type parameters #43651

ianlancetaylor opened this issue Jan 12, 2021 · 453 comments

Comments

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Jan 12, 2021

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.

@ianlancetaylor ianlancetaylor added this to the Proposal milestone Jan 12, 2021
@ianlancetaylor ianlancetaylor added this to Incoming in Proposals (old) Jan 12, 2021
@atdiar

This comment has been minimized.

@ALTree

This comment has been minimized.

@atdiar

This comment has been minimized.

@hanneshayashi

This comment has been minimized.

@tsal
Copy link

tsal commented Jan 12, 2021

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).

@coder543

This comment has been minimized.

@bcmills
Copy link
Contributor

bcmills commented Jan 12, 2021

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
Copy link

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
Copy link
Contributor

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
Copy link

michaelwilner commented Jan 12, 2021

```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
Copy link

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
Copy link

coder543 commented Jan 12, 2021

@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
Copy link
Contributor

fzipp commented Jan 12, 2021

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
Copy link

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
Copy link
Contributor

@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
Copy link
Contributor

fzipp commented Jan 12, 2021

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
Copy link

coder543 commented Jan 12, 2021

@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.

@p-kraszewski

This comment has been minimized.

@DeedleFake
Copy link

@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.

@ianlancetaylor

This comment has been minimized.

@knz

This comment has been minimized.

@griesemer
Copy link
Contributor

griesemer commented Jan 12, 2021

@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
Copy link

DeedleFake commented Jan 12, 2021

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.

@steeling

This comment has been minimized.

@knz

This comment has been minimized.

@stigsb
Copy link

stigsb commented Jan 12, 2021

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
Copy link
Contributor

zikaeroh commented Jan 12, 2021

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.

@ianlancetaylor

This comment has been minimized.

@fzipp
Copy link
Contributor

fzipp commented Feb 13, 2021

Maybe the FAQ on generic types https://golang.org/doc/faq#generics can be updated to reflect the fact that there is now an accepted proposal that is actively being worked on.

@inliquid

This comment has been minimized.

@beoran

This comment has been minimized.

@inliquid

This comment has been minimized.

@zephyrtronium

This comment has been minimized.

@gopherbot
Copy link

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

gopherbot pushed a commit that referenced this issue Feb 15, 2021
For #43651

Change-Id: Idb511f4c759d9a77de289938c19c2c1d4a542a17
Reviewed-on: https://go-review.googlesource.com/c/go/+/291990
Trust: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
@ianlancetaylor
Copy link
Contributor Author

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

@gopherbot
Copy link

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

gopherbot pushed a commit to golang/website that referenced this issue Feb 16, 2021
Ported CL 291990 to this repo.
For golang/go#43651.

Change-Id: I3680b32ef7a53b3901e54d4d1dbf680231870490
Reviewed-on: https://go-review.googlesource.com/c/website/+/292290
Trust: Russ Cox <rsc@golang.org>
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Dmitri Shuralyov <dmitshur@golang.org>
@truesilver92
Copy link

truesilver92 commented Feb 16, 2021

@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
Copy link

@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

@KumarGanesha1996

This comment has been minimized.

@GoldsteinE

This comment has been minimized.

@m-ivanov

This comment has been minimized.

@billinghamj

This comment has been minimized.

@GoldsteinE

This comment has been minimized.

@rsc
Copy link
Contributor

rsc commented Feb 20, 2021

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.

@rsc rsc closed this as completed Feb 20, 2021
@golang golang locked as off-topic and limited conversation to collaborators Feb 20, 2021
@gopherbot
Copy link

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

@gopherbot
Copy link

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

@ianlancetaylor ianlancetaylor added the generics Issue is related to generics label Apr 9, 2021
@gopherbot
Copy link

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

@dmitshur dmitshur modified the milestones: Backlog, Go1.18 May 30, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
No open projects
Development

No branches or pull requests