Go: proposal: Go 2: generic types (GT)

[rcoreilly]

This proposal changes the syntax for type parameters on functions, to eliminate the extra parens which are widely raised as a problem with the draft proposal. It retains type parameters for types, and should otherwise be very similar to the draft proposal, just with a simpler syntax.

The key idea is: use generic type names just as we use concrete types now, instead of having separate type parameters. (Generic Types, GT)

GT puts all the type information in one place, instead of distributing it across two locations, greatly reducing cognitive load, and eliminates the extra parens in function calls which are confusing and a constant complaint about the draft proposal.

• Constraints are now interface types, so use these interface types directly as type names.
• For fully generic, unconstrained types, use the keyword type.
• Semantically, there are two categories of interface types: generic, and non-generic.
  
  
  
  • Generic interfaces have a type list, non-generic do not.
  
  
  • To create an unconstrained yet generic interface, specify a type list of type type.
  
  

Compare the following examples against those in the draft proposal -- starting at the start:

func Print(s []type) {
    for _, v := range s {
        fmt.Println(v)
    }
}

Print([]int{1, 2, 3})

For constrained types:

type Stringer interface {
    type type  // this marks as a generic interface
    String() string
}

// Because Stringer is defined as a generic interface (type type),
// any type satisfying Stringer can be used directly, without explicit conversion.
func Stringify(s []Stringer) (ret []string) {
    for _, v := range s {
        ret = append(ret, v.String())
    }
    return ret
}

// s1 and s2 are slices of any type, and each can be any type
func Print2(s1 []type, s2 []type) { ... }

Compare this to:

// s1 and s2 can be slice of any type, but it must be the *same* type
func Print2Same(s1, s2 []type) { ... }

To emphasize the difference from the draft proposal, here's a direct comparison:

func StrAndPrint(type L interface{}, T Stringer)(labels []L, vals []T) { ... }

func StrAndPrint(labels []type, vals []Stringer) { ... }

GT consolidates the type information in one place, where it has always been.

Type expressions

To refer to the concrete type of a generic arg, use type(x) -- this is needed for return values etc:

func Min(x, y Numeric) type(x) {
  if x < y {
     return x
  }
  return y
}

For slices, maps and channels, type(x) returns the element type -- for maps, type(m[]) returns the key type:

func Keys(m map[comparable]type) []type(m[]) {
    r := make([]type(m[]), 0, len(m))
    for k := range m {
        r = append(r, k)
    }
    return r
}

For func types with generic arg / rval types, you must name any args or return values you need the type of, and access like a named field: type(f.arg2).

This is the main downside of the GT proposal -- referring to the type elsewhere is now more cumbersome. Fortunately, Go's type inference means that this doesn't happen that much. And if a given arg type is going to be used a lot, you can define an inline type alias as is done in the draft proposal (see Container example below).

Generic types

Generic types are essentially identical to the draft proposal (except with the different type naming convention).

Additional proposal (emailed to go-nuts):

• In methods, do not replicate the type params -- just refer back to the original type parameter names using field access syntax (e.g., m.T)
• In case of an anonymous embedded field of same type as type param, use type(m.T) to refer to the type and m.T to refer to the field (can define a type alias fof the type expression if used frequently).

type Vector(T type) []T

var v Vector(int)

func (v *Vector) Push(x v.T) { *v = append(*v, x) }

type List(T type) struct {
    next *List(T) // this reference to List(T) is OK
    val  T
}

type StringableVector(T Stringer) []T

func (s StringableVector) String() string { ... }

Methods may not take additional type arguments

From the draft proposal:

Although methods of a generic type may use the type's parameters, methods may not themselves have additional type parameters. Where it would be useful to add type arguments to a method, people will have to write a suitably parameterized top-level function.

There would seem to be no reason to have such a constraint under GT, as generic args are really no different syntactically than concrete ones -- no extra parens, etc.

Type Lists in Constraints

Type lists are exactly as in the draft proposal, and their presence is essential for making the type a generic interface type (type type being the fully unconstrained version of this).

type SignedInteger interface {
    type int, int8, int16, int32, int64
}

...

// again much simpler to use type name directly, and note use of type(s) expression for return
func Smallest(s []constraints.Ordered) type(s) { ... }

Type args

To enable New functions, and any other case where type values need to be specified as such, we need to support explicit type arguments -- these are just like regular arguments, in the same parenthesized list, but start with the type keyword and must be passed a type expression (a type literal or a type() expression).

Instantiated generic function

Edit: based on comments below:

To refer to a concrete instantiated version of a generic function, specify the args as types -- that clearly differentiates from actually calling the function, and looks like the equivalent with explicit type args:

func StringerFunc(s []Stringer) (ret []string) { ... }
...
sf := StringerFunc([]MyStringer) // type-only args = instantiated version

Containers Example

This provides a good example of how it all works -- very similar to the draft example overall because parameterized types are essentially the same, so it doesn't really show off the main strengths of the GT proposal, but at least concretely demonstrates that it should have the same overall expressive scope.

// Package orderedmap provides an ordered map, implemented as a binary tree.
package orderedmap

import "chans"

// Map is an ordered map.
// note: presence of type args defines a generic struct.
// if wrote: `K, V type` then K and V would be constrained to be the *same* generic type.
// could have written: `K number, V type` etc to specify constraints.
type Map(K type, V type) struct {
    root    *node(K, V)
    compare func(K, K) int
}

// node is the type of a node in the binary tree.
type node(K type, V type) struct {
    k           K
    v           V
    left, right *node(K, V)
}

// New returns a new map.
// note: first two args are type args (type comes first), not generic var args
func New(type K, type V, compare func(K, K) int) *Map(K, V) {
    return &Map(K, V){compare: compare}
}

// find looks up k in the map, and returns either a pointer
// to the node holding k, or a pointer to the location where
// such a node would go.
// note: methods do NOT need to keep re-specifying the type params!
// using explicit field access to refer to type parameters so it is clearer where they are defined.
// this is portable to draft proposal.
func (m *Map) find(k m.K) **node(m.K, m.V) {
    pn := &m.root
    for *pn != nil {
        switch cmp := m.compare(k, (*pn).k); {
        case cmp < 0:
            pn = &(*pn).left
        case cmp > 0:
            pn = &(*pn).right
        default:
            return pn
        }
    }
    return pn
}

// Insert inserts a new key/value into the map.
// If the key is already present, the value is replaced.
// Reports whether this is a new key.
func (m *Map) Insert(k m.K, v m.V) bool {
    pn := m.find(k)
    if *pn != nil {
        (*pn).v = v
        return false
    }
    *pn = &node(m.K, m.V){k: k, v: v}
    return true
}

// Find returns the value associated with a key, or zero if not present.
// The bool result reports whether the key was found.
func (m *Map) Find(k m.K) (m.V, bool) {
    pn := m.find(k)
    if *pn == nil {
        var zero m.V // see the discussion of zero values, above
        return zero, false
    }
    return (*pn).v, true
}

// keyValue is a pair of key and value used when iterating.
type keyValue(K type, V type) struct {
    k    K
    v    V
}

// InOrder returns an iterator that does an in-order traversal of the map.
func (m *Map) InOrder() *Iterator(m.K, m.V) {
    type kv = keyValue(m.K, m.V)
    sender, receiver := chans.Ranger(kv)
    var f func(*node(m.K, m.V)) bool
    f = func(n *node(m.K, m.V)) bool {
        if n == nil {
            return true
        }
        // Stop sending values if sender.Send returns false,
        // meaning that nothing is listening at the receiver end.
        return f(n.left) &&
            sender.Send(kv{n.k, n.v}) &&
            f(n.right)
    }
    go func() {
        f(m.root)
        sender.Close()
    }()
    return &Iterator(m.K, m.V){receiver}
}

// Iterator is used to iterate over the map.
type Iterator(K type, V type) struct {
    r *chans.Receiver(keyValue(K, V))
}

// Next returns the next key and value pair. The bool result reports
// whether the values are valid. If the values are not valid, we have
// reached the end.
func (it *Iterator) Next() (it.K, it.V, bool) {
    kv, ok := it.r.Next()
    return kv.k, kv.v, ok
}

Note: this GT proposal builds on the core idea from the Generic Native Types (GNT) proposal, but is much simpler and closer to the draft proposal.

[ianlancetaylor]

It seems very subtle to change a function from a normal function to a parameterized function based on whether the parameter type is an interface that says type type.

In this approach is there a way to instantiate a function without calling it?

[rcoreilly]

It seems very subtle to change a function from a normal function to a parameterized function based on whether the parameter type is an interface that says type type.

Generic types will likely be fairly special and widely recognized as such? constraints.* types should be clear, etc.

In this approach is there a way to instantiate a function without calling it?

Edit: ignore this -- better idea just below, now added to main proposal:

hmm.. I guess you could introduce a "function address" syntax that disambiguates calling the function from instantiating it:

func StringerFunc(s []Stringer) (ret []string) { ... }
...
s := []MyStringer{"a", "b"}
sf := &StringerFunc(s)

I'm not sure what happens currently if you try to take the address of a function like that, but anyway, maybe something like this might work? To be clear, it would just return the same thing as you would get normally when you refer to a function, which is implicitly a pointer anyway -- not a pointer-to-a-pointer..

[ianlancetaylor]

I guess I don't see any particular reason to think that type constraints will be clearly different from interface types. Some will, some won't.

To me &StringerFunc(s) seems quite different from other ways that Go works.

[rcoreilly]

Actually a better idea is to just use type expressions for the args -- not an actual variables -- that would clearly disambiguate and is more semantically appropriate -- basically just like you'd do with the type parameters:

func StringerFunc(s []Stringer) (ret []string) { ... }
...
sf := StringerFunc([]MyStringer) // type-only args = instantiated version

Edit: just added this to proposal

[rcoreilly]

I guess I don't see any particular reason to think that type constraints will be clearly different from interface types. Some will, some won't.

I'm not sure I understand your point: I'm just saying that anything in the constraints package would clearly be a generic interface, so it would be clear that you're dealing with that case, from the type signature of the arg variables.

[ianlancetaylor]

I said that it seems fairly subtle to decide whether a function is generic or not based on the characteristics of the parameter types. You said it would be clear if the type comes from the constraints package. I agree, but I said that in general I don't see any particular reason to think that type constraints will be clearly different from interface types. If they come from the constraints package, it will be clear. If they don't, it won't.

[rcoreilly]

Ok, right. well, that was my other claim that the generic types would be relatively rare and well known. I've seen discussion with this assumption before, e.g., in saying that not many people would be writing constraints in the first place (back when they were contracts), so it wasn't so important that it be easy to write them...

But anyway you're obviously correct in pointing out this important limitation for the GT proposal: if people don't generally know that they're dealing with a generic type, and understand the implications of that, it could be confusing.

Some further ideas:

• Add an explicit keyword, e.g., genfunc instead of func, to explicitly mark the function as generic. Seems like overkill but maybe better to be more explicit than not?
• Rely on function documentation comments -- e.g., could have some kind of styling convention such as: // MyFunc (Generic) returns xyz.. that could be enforced by vet. In any case, one would generally expect the function documentation to mention the generic nature of the args in some way.
• Also, presumably this is not an issue with methods (the generic type makes it pretty obvious), just standalone functions -- not sure what the relative frequency of such functions randomly showing up outside of a context that is obviously tied to associated generic types, where these confusions might arise.

[rcoreilly]

Also, from go-nuts just now, you said:

Our limited experience suggests that by far the common case is that type parameters have no constraints. It seems annoying to force everyone to write interface{} all the time when it is normally not needed.

In which case, the function signature would contain the generic type keyword which would immediately identify it as a generic function..

[kokizzu]

I commented on wrong issue, moved here: https://github.com/golang/go/issues/39684

[urandom]

Why is the syntax T type for a struct, but, type T for a function?

[seankhliao]

how would you declare the equivalent of:

func F(type T)(slice []T, elem.T) {}

like this?

func F(slice []T, elem type(slice)) {}

[rcoreilly]

@seankhliao I assume you meant this (no .):

func F(type T)(slice []T, elem T) {}

and yes that is how it would work, although T would generally be either type for a fully generic type or some other named interface that would generally be more descriptive than T:

func F(slice []type, elem type(slice)) {}

[rcoreilly]

@urandom I'm not sure exactly what you're asking -- in general type is the generic type name, which would be used in functions and structs in the usual order of name typename so T type would be typical.

However, there is one exception which might be what you're asking about. To support the ability to pass type parameters to functions like New so you can create a new token of a parameterized type, the idea was to also support passing parameters that are type expressions, not the usual value expressions. That is when you'd use the type T ordering for the function arg, indicating that the arg must be a type, not a value. This might be too subtle and confusing to rely on the ordering, but it avoids using a new keyword and seemed reasonably semantic to me..

[ydnar]

Would this proposal allow currying for generic functions? e.g.

func F(type T, slice []T) {}

type A struct {}

fa := F(A)

fa([]A) // allowing this

[rcoreilly]

The draft proposal specifically omits currying, and it doesn't seem to be common practice, or particularly elegant, in Go. And in your example, the first arg is just a type parameter, not a real parameter that the function uses, so I think that would be called defining an instance of the function with a concrete type parameter, not currying per se.

In any case, the first arg would be omitted under this proposal, yielding:

func F(slice []type) {}

type A struct {}

fa := F([]A) // this is defining an instance of the function with a concrete type

sa :=make([]A, 2) // or whatever

fa(sa) //works fine

if you wanted to do Go style currying, this is what it would look like I guess:

func F(a type, s []type(a)) {}

type A struct {}

// curried function -- return function arg type explicitly defined in terms of arg type of a
func C(a type) func([]type(a)) {
    return func (s []type(a)) {
        return F(a, s)
    }
}

AV := A{}

fc := C(A) // given the explicit connection between 'a' type and 's' type,
           // compiler COULD instantiate everything, such that function C can be fully concretely complied..

sa :=make([]A, 2) // or whatever

fc(sa) // if arg is not []A, it is an err given instantiated type of fc

This is sufficiently complex that maybe it wouldn't make sense to support such a thing. And if one or more of the arg types remains undefined when the curry function is instantiated, then that wouldn't work I think..

The more typical way this works in Go is to use methods with a "curried receiver", which is very convenient for "callback" functions to pass additional state etc.

[ydnar]

In this proposal, would type replace interface{} for most use cases?

[rcoreilly]

That would be easier to "type" :) Some similar discussion on go-nuts about any keyword replacing interface{}

[ydnar]

That would be easier to "type" :) Some similar discussion on go-nuts about any keyword replacing interface{}

Could an any keyword help this proposal as well?

// Package orderedmap provides an ordered map, implemented as a binary tree.
package orderedmap

import "chans"

// Map is an ordered map.
// note: presence of type args defines a generic struct.
// if wrote: `K, V any` then K and V would be constrained to be the *same* generic type.
// could have written: `K number, V any` etc to specify constraints.
type Map(K any, V any) struct {
    root    *node(K, V)
    compare func(K, K) int
}

// node is the type of a node in the binary tree.
type node(K any, V any) struct {
    k           K
    v           V
    left, right *node(K, V)
}

// New returns a new map.
// note: first two args are type args (type comes first), not generic var args
func New(type K, type V, compare func(K, K) int) *Map(K, V) {
    return &Map(K, V){compare: compare}
}

[ydnar]

@rcoreilly the OP specifies two arguments must have the same type if specified as a, b type. Given that form is used for reducing stutter in function declarations, it seems like that implicit constraint would be easy to miss.

If type arguments can be omitted if the type can be inferred, what do you think of this alternative?

// s1 and s2 can be slice of any type, but it must be the *same* type
func Print2Same(type T, s1, s2 []T) { ... }

// Functionally identical to above
func Print2Same(type T, s1 []T, s2 []T) { ... }

[rcoreilly]

@rcoreilly the OP specifies two arguments must have the same type if specified as a, b type. Given that form is used for reducing stutter in function declarations, it seems like that implicit constraint would be easy to miss.

maybe, but OTOH, that expression can only be used with concrete types when the types are the same, so the semantics are the same...

And for your alternative, I think you're using the draft proposal logic, not this GT proposal, which doesn't use the type arg at all, and would look like this:

// s1 and s2 can be slice of any type, but it must be the *same* type
func Print2Same(s1, s2 []type) { ... }

// Functionally identical to above
func Print2Same(s1 []type, s2 []type(s1)) { ... }

So the shared type syntax is definitely a bit simpler.

[ydnar]

@rcoreilly the OP specifies two arguments must have the same type if specified as a, b type. Given that form is used for reducing stutter in function declarations, it seems like that implicit constraint would be easy to miss.

maybe, but OTOH, that expression can only be used with concrete types when the types are the same, so the semantics are the same...

And for your alternative, I think you're using the draft proposal logic, not this GT proposal, which doesn't use the type arg at all, and would look like this:

I think your proposal, overall, is superior to the current draft proposal for Go parametric types. My suggestion was more to do with what I think is the weakest part—declaring that two args must be of the same type by omission of the type from all but the last argument.

This seems to make more sense, and is explicit, particularly to the reader:

func Print2Same(s1 []type, s2 []type(s1)) { ... }

It’d also work if the arguments that must be the same type aren’t sequential:

func f(a type, f func(type(a)), b type(a)) { … }

[ydnar]

Somewhat related: any is easier to understand and doesn’t overload type as much, but wouldn’t be as straightforward to implement in Go 1.x:

func f(a any, f func(type(a)), b type(a)) { … }

[rcoreilly]

@ydnar I agree about the benefits of using the explicit type expression and thanks for the support! And I agree also that any is semantically clearer, and if there is a willingness to allow a new keyword, it has a lot going for it. OTOH, there does seem to be a precedent in Go for minimizing keywords, and using things like interface{} instead of making up a new name..

[ydnar]

@ydnar I agree about the benefits of using the explicit type expression and thanks for the support! And I agree also that any is semantically clearer, and if there is a willingness to allow a new keyword, it has a lot going for it. OTOH, there does seem to be a precedent in Go for minimizing keywords, and using things like interface{} instead of making up a new name..

Would your proposal work with interface{} instead of type?

[ianlancetaylor]

We're going to move forward with the current generics design draft, at least for now (https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md).

One of the cited reasons for this proposal was the extra parens, which have been removed from that draft.

This is a likely decline. We can revisit that decision if the current design draft is not adopted. Leaving open for four weeks for final comments.

[rcoreilly]

Yep the square brackets seem like a good improvement. Ultimately there is X amount of additional complexity associated with generic types, and either you explicitly list them as arguments, as in the design draft and most (all?) other implementations in other languages, or you have to use the various type expressions like those in this proposal, and there are trade-offs either way. The advantages of using the established approach (so people coming from other languages will find it easy to understand) and explicitness of naming the type args are clear, so overall it probably makes sense to pursue the current approach. @ianlancetaylor thanks for all your effort and patience in engaging with this and so many other issues!

[ianlancetaylor]

No change in consensus.

[hdost]

So this doesn't mean that Generics won't be implemented, just that the existing Proposal will be used in the implementation. Correct?

We're going to move forward with the current generics design draft, at least for now (https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md).

One of the cited reasons for this proposal was the extra parens, which have been removed from that draft.

This is a likely decline. We can revisit that decision if the current design draft is not adopted. Leaving open for four weeks for final comments.

[ianlancetaylor]

It means that we are going to turn the existing design draft (https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md) into a proposal, see if that gets approved, and, if it does, implement that.