Go Generic Native Types proposal

gnt-prop.md

This proposal is to add generic native types (GNTs) to Go: generic versions of each of the native builtin types (e.g., map = generic map, slice = generic slice, number = generic number, float = generic float, signed = generic signed integer, unsigned = generic unsigned integer, etc).

GNTs support a substantial proportion of generic programming functionality, without adding any new syntax to the language: generic code looks identical to regular Go code, except for the use of these generic type names, and a few extra functions that access the type parameters of container objects such as maps and slices (e.g., elem(x) is the type of the elment in a slice or map; key(m) is the type of the key of a map; field(s, fieldName) is the type of the given named field in a struct; return(f) is the type of return value from function, and type(x) is the type of a generic var, e.g., for use in return signature).

The generic struct is the most challenging case, because of its unlimited number of type parameters. The proposed strategy is to adopt the interface concept, but specialized for the struct type, as a struct interface -- see golang/go#23796 for discussion of a related proposal, where most of the objections were about "polluting" the existing interface concept with struct-specific functionality -- this problem is avoided by having a special type of interface only for structs, which provides all the benefits from that proposal, as well as supporting the definition of a generic struct type.

Here are some examples of some of the main generics use-cases under this proposal:

func Keys(m map) []key(m) {
    s := make([]key(m), len(m))
    idx := 0
    for k := range m {
        s[idx] = k
        idx++
    }
    return s
}

// note: all args in same list (x,y) must be of same concrete type
func Min(x, y number) type(x) {
  if x < y {
     return x
  }
  return y
}

// A struct interface is like an interface, specialized for struct -- any struct
// with the specified fields gets the generic methods, instantiated for concrete type
type Vec2 struct interface {
    X, Y number // or float
}

func (v Vec2) Add(u Vec2) Vec2 {
    return Vec2{v.X + u.X, v.Y + u.Y}
}

// Vec2f32 instantiates the generic Vec2 struct interface for the float32 type
type Vec2f32 struct {
    X, Y float32
}

func myfunc() {
    v1 := Vec2f32{1,2}
    v2 := Vec2f32{3,4}
    sum := v1.Add(v2)
}

package graph

// Edge defines a connection between two nodes, as a struct interface.
// Any type with fields named From and To that are pointers to a 
// concrete struct that implements the Node struct interface will satisfy
// the Edge interface.
type Edge struct interface {
    From, To *Node 
}

// Node defines a node in a graph, which has Edges connecting it to other
// nodes.  Any concrete struct with a slice of structs satisfying the 
// Edge struct interface, named Edges, will satisfy this interface.
type Node struct interface {
    Edges []Edge // concrete slice of a struct interface type..
}

// Unlike the draft proposal, methods can be defined with struct interface args
// just like any interface type can be passed around currently.  A boxing penalty
// is likely but perhaps not inevitable.
func (n *Node) ShortestPathTo(to *Node) []Edge {
    for _, e := range n.Edges {
        if e.To == to {
            return []Edge{e}
        }
        se := e.To.ShortestPathTo(to) // all just std interface virtualization method calls..
        if len(se) > 0 {
            return se // actually would need to sort by path length and return shortest, but whatever..
        }
    }
    return nil
}

In summary, GNTs leverage the "contracts" associated with the existing native types in the language, instead of introducing an entirely new syntax to specify novel such contracts. This makes programming with these types immediately intuitive and natural for any Go programmer, and the code as shown in the above examples inherits the simplicity and elegance of the existing Go syntax, as compared to other generics proposals that require additional type parameters etc.

The major limitation is that generic functionality is limited to these existing native types. You cannot define Min / Max functions that work across all native numbers and on non-native numbers such as big.Int. The bet here is that GNTs solve 80% or more of the use-cases in the cleanest, simplest way -- i.e., the defining feature of Go.

Several of the required keywords are repurposed from existing ones, and thus would have no compatibility impact:

• Type kinds: map, chan, interface, struct, struct interface (combination)
• Type parameters: type(x), return(f) (with optional 2nd arg specifying which return val if multiple -- could be index or name if named)

These new ones would create potential conflicts:

• Type kinds: slice, array, number, unsigned, signed, float, complex
• Type parameters: elem(x), key(x), field(x, fieldName)