This is a proposal for generics in Go based on generic versions of existing native types in the language (Generic Native Types or GNT). Instead of supporting completely flexible contracts that can specify all manner of constraints on types that can be used in generic code, use the existing, well-known type kinds already in Go as a fixed set of contracts with builtin (keyword) names.
func Keys(m map) []key(m) {
s := make([]key(m), len(m))
idx := 0
for k := range m {
s[idx] = k
idx++
}
return s
}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..
}-
sliceis a generic slice that supports all of the basic slice operations, and can be used to represent a slice with any type of element. likewise forarray. -
mapis a generic map (hopefully the parsing can be made to work relative to its existing use in defining maps, likewise for others below) -
chanis a generic channel -
numberis a generic number, with appropriate more specific subtypes:unsigned-- all unsigned intssigned-- all signed intsfloat-- both floatsinteger-- do we need this in addition to unsigned and signed? maybe not? might be safer to exclude and ensure that logic is appropriate for either signed or unsigned, and being more restrictive is better than less overall in terms of combinatorics etc.
complex-- both complexes -- not a member of the number category, as it is a vector, not a number, and is not ordered.
-
structis a generic struct type (one of the trickiest but most powerful cases as discussed below) -
interface-- to be consistent with the above naming scheme, could just use the plain interface keyword instead ofinterface{}for the generic version of an interface (looks cleaner too).
Each of these generic types supports their respective native operators, builtin functions, etc, and thus provides in effect a well-understood, established contract for what each can do, instead of creating an entirely new mechanism for specifying novel arbitrary contracts: use the contracts we already know and that have already proven their worth.
We also need to be able to use type expressions that refer to the type parameters of containers, functions, and structs, along with the actual concrete type of a generic variable itself, similar to the corresponding reflect functions:
elem(x)is the element type of a slice, map, or channel.key(x)is the key type of a map.return(f)is the return type of a function, with optional arg to specify which return value if multiple (by index or name if named).field(x, fieldName)is the type of a struct's field with given field name.type(x)is the concrete type of a generic variable.
A major use of these type expressions is in specifying a generic return type in terms of the arguments to a function -- we restrict generic return types to be derived directly from the input argument types, to enable efficient and explicit type inference without requiring the concrete instantiated type.
Another way of thinking about this is that it just exposes the existing generic capabilities and concepts of the language in a way that user code can take greater advantage of -- in this way, it is likely to be the most "natural" way to do generics within Go. But what kinds of expressive power does it buy, and at what cost?
Common operations on slices and maps can be easily and cleanly written, once and for all:
func Delete(s *slice, idx int) {
*s = append((*s)[:idx], (*s)[idx+1:])
}Here is Keys from the draft proposal, which requires the key(x) type expression for specifying the return type and the variable that will be returned:
func Keys(m map) []key(m) {
s := make([]key(m), len(m))
idx := 0
for k := range m {
s[idx] = k
idx++
}
return s
}Here's what a generic Sort would look like, requiring only the essential user-supplied less method and no interface:
func Sort(s slice, less func(i, j int)) {
// these are the main calls embeded in proper sorting algorithm:
for i := range s { // range just works on generic slices..
// j comes from somewhere..
if less(i, j) {
s[i], s[j] = s[j], s[i] // no need to define swap method anymore!
}
}
}
func mycode {
mys := make([]MyType, 20)
...
sort.Sort(mys, func(i, j int) {
return mys[i].Order < mys[j].Order
})
}It would be interesting to see how much of the common functionality of the strings and bytes packages could be replaced with generic slice methods under such constraints. Note that string is such a specialized type that it essentially stands alone and there is nothing else to join it in a possible generic class, so it would be treated as an array of bytes from the generic perspective.
func Min(x, y number) type(x) {
if x < y {
return x
}
return y
}As a special bonus, the ability in Go to specify multiple vars sharing the same type could be leveraged to imply that, when so-specified, both args must actually be of the same underlying type, thus preventing any additional complexity associated with comparing across different types.
The return type must be specified using a type expression operating on one of the arguments to the function (alternatively elem(x), key(x), return(f) or field(x, fieldName)). This is important to make type inference more efficient and feasible "generically" without going through a full concrete instantiation.
For functions like these, the compiler could adopt strategies such as generating the two most popular versions of the method, for int64 and float64, and up-converting any other types to those when calling this function. If somewhere there is a tight inner loop with lots of calls to such a method with a different type, it could just inline the code there, etc.
The key point being that by restricting the space of generic types to the "natural kinds", more performant compiler optimizations are possible. The small finite space of kinds means that precompiling relevant versions does not result in excessive code bloat -- something that is impossible for truly generic generics..
This approach explicitly does not solve the problem of defining Min / Max functions that work on an arbitrary, non-native numerical type such as BigInt. The Go mantra of satisfying 80% of the cases with the simplest possible solution could apply here: many users would rejoice at finally having an official Min / Max for ints etc, while few would likely regret the lack of BigInt support, which is used in much more specialized cases.
Generic versions of the struct type opens up vast new territory for generic programming, because unlike all other types, a struct has an unlimited number and variety of potential "generic type parameters" in the form of its fields. Thus, by defining generic types of structs, we radically expand the space of possible generic operations and functions operating over these fields, enabling entire complex algorithms to be defined generically.
To start small and simple, a struct could define generic types as fields, and methods that operate on them, using all the same logic established so far:
type Vec2 struct {
X, Y number // or float
}
func (v Vec2) Add(u Vec2) Vec2 {
return Vec2{v.X + u.X, v.Y + u.Y}
}Whereas slices and maps are natively type-parameterized containers (i.e., they have existing syntax to specify their type parameters in ways that look like type parameters), there is no existing syntax in the language to specify a struct parameterized with particular concrete types for the X, Y fields, aside from the literal definition of such a struct itself.
One strategy would be to introduce such a syntax, which is done in Michal Štrba's proposal, but given the polymorphic nature of fields, that could get complicated pretty quick.
Instead, we can adopt the interface strategy and introduce the concept of struct interfaces -- i.e., any struct type with generic fields is automatically a struct interface (no need to declare it as such explicitly, though you could for clarity), and furthermore any concrete type that provides a matching set of fields automatically satisfies this struct interface (again, consistent with interface behavior, no need to declare this explicitly). A version of this idea has been discussed before: golang/go#23796 but most of the objections there had to do with not wanting to detract from the generality of the existing interface type, and restrict or specialize it for only struct types. But, to be clear, the proposal here is different because we're instead creating an entirely new type of "interface", specifically for structs, and specifically to deal with a real issue with this proposal. This would leave the existing interface functionality unchanged, and it would in fact be fully orthogonal to the functionality of a struct interface, as elaborated below.
To declare a concrete instantiation of a struct interface type, the user, or, in this and perhaps most cases, the package designer, simply defines a specific struct as usual, and as long as it follows the struct interface template (including names and types), then all relevant methods automatically apply:
// 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)
}Other code can use the Vec2 generic type and you can then pass the specific Vec2f32 instantiation to it, and presumably everything should go through. Small methods could be inlined, and larger ones instantiated for different concrete types etc as discussed above. The combinatorial constraint against mixing types across binary operators becomes increasingly important here to make this all tractable, and minimize boxing costs, etc.
As discussed in golang/go#23796, there would have to be a field offset table etc for each instantiation, which the generic Vec2 would access, to handle accesses to field variables, and getting their addresses etc.
This ability to define struct interfaces is so powerful, that a specific syntax to define a given type as such, even if it doesn't have generic fields, should be introduced:
// Node is a struct interface -- any struct defining these fields automatically satisfies this
// interface, and methods defined on this Node type (which can only refer to the interface Fields)
// are automatically available to any concrete struct that satisfies this interface.
type Node struct interface {
Edges []Edge
}
func (n *Node) IsConnectedTo(b *Node) bool {
for _, e := range n.Edges {
if e.To == b {
return true
}
}
return false
}The struct interface can directly specify its own default implementations, because it has fields to support those implementations. Many existing uses of interfaces could really benefit from this way of coding, by eliminating the need for boilerplate getter / setter methods (as discussed in golang/go#23796), and in particular the name clash that results from wanting exported upper-case names for both the field and the accessor, without also adding the "Get" in front of the accessor.
The Graph, and perhaps most other container-like data structures, seem like they could most naturally be addressed using the struct interface approach. This is consistent with the discussion of Graph in the draft proposal, where the advantages relative to a purely interface-based approach were fairly subtle.
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 short, you just write the whole thing using standard Go code as-if these were concrete types, but this code can be generically applied to any struct types satisfying the relevant interfaces. Under the assumption that the actual concrete types are always known, the compiler can choose between boxing and separately instantiating -- most likely the boxing as used in existing interfaces would make the most sense overall, because unlike other cases, the space of possible concrete types is not finite, and also most likely struct interfaces will define algorithms with higher levels of complexity. Nevertheless, tight inner loops could still be optimized potentially.
package safemap
type M struct interface {
Mu sync.RWMutex
Map map
}
func (m *M) Set(k key(m.Map), v elem(m.Map)) {
m.Mu.Lock()
if m.Map == nil {
m.Map = make(m.Map)
}
m.Map[k] = v
m.Mu.Unlock()
}
…any concrete map that shares that struct interface type signature automatically gets the associated methods:
import safemap
// MySafeMap implements the safemap.M struct interface
type MySafeMap struct {
Mu sync.RWMutex
Map map[string]string
}
func MyFunc() {
m := MySafeMap{}
m.Set(“mykey”, “myval”) // at this point the Set method knows the concrete type of “m”, can compile Set
}Here's another popular container:
type List struct interface {
Next *List
}
func (l *List) InsertAfter(nl *List) {
nl.Next = l.Next
l.Next = nl
}
...
// MyList instantiates the List struct interface...
type MyList struct {
Next *MyList
Data string // any number of additional fields can be added, as long as interface-matching
// ones come first, so it can match and then just ignore after that
}
func mycode() {
l := &MyList{Data: "first node"}
l.InsertAfter(&MyList{Data: "next node"} // automatically gets all the methods with implementation
}As noted above, this proposal was inspired by Michal's proposal, specifically its later revision to include more specialized versions of generic types. A key difference here is to attempt to recover the benefits of constraints (contracts, concepts) on the generic types, by using all of the existing Go type categories. Whereas Michal's proposal has a specific type parameter for the length of an array (gen n), one could presumably just use len(s) on that and a slice or map generic type. Also, a major difference here is in using the interface strategy in the struct interface approach, instead of introducing explicit type parameters to instantiate generic struct types.
Burak proposed using existing types to specify contracts, with the addition of the like() keyword. This is consistent with the idea of using generic versions of native types as the basis of contracts, as in this proposal. This proposal goes further to say that is all you can use, and thereby is able to eliminate explicit separate contract code entirely, and have everything specified at the exact point of usage, with a small number of builtin keywords for each generic type.
Dave Cheney's blog) builds on Roger Pepe's observations to suggest that contracts are types, and function much like interface, so you can simplify the syntax by just using them directly as type names, instead of requiring additional parentheses etc. However, his proposal retains the idea of supporting fully general open-ended contracts, specified separately, whereas the move here is to abandon that additional flexibilty and complexity, while retaining the idea of specifying generic variables directly using type names, instead of requriing the more complex paramterized syntax.
In summary, this proposal seems like it could handle many valuable use-cases for generics, while avoiding many of the thorny issues plaguing other approaches. It does so by embracing the existing Go strategy of adopting simple, restricted approaches that satisfy many real-world use-cases. The existing Go type system has already proven its value and is already familiar to every Go programmer -- this proposal just gives us generic access to this very same type system without having to resort to reflection.
This puts user-defined code on a level playing field with the magic generic-ness of the builtin methods like append, copy, etc, and thereby in some ways completes the language and makes it more self-consistent, by removing this otherwise seemingly arbitrary distinction.
The central constraint of this approach relative to other more completely "generic" generic approaches is that it is restricted entirely to the existing Go type system. You cannot define an entirely generic Min method that will operate on anything from a basic number up to a BigInt or any other complex non-native type. Nevertheless, the key practical question is: are generic native types enough to achieve the magic 80% solution?
In short, this approach to generics retains the premise that most problems can and should be solved using this small set of native types -- you should continue to fit your problem into the "box" of Go, instead of trying to extend Go to fit your problem. By learning to efficiently use this small vocabulary of native types, which can be combined in many powerful ways, you can likely solve most problems efficiently and clearly. The proposed form of generics just give you the ability to express these solutions in more generic terms, so you don't have to keep re-writing those solutions repeatedly.
It is useful to establish two fundamdentally different approaches to achieving the goals of generics.
What do generics seek to achieve?
Write the function or data structure in a way that is generic across a set of applicable types, so that the compiler / run-time can make it work without you having to spell it all out for each such type.
Abstractly, this can be done in two fundamentally different ways:
-
Type-parameterized macros The code is a macro / template that is instantiated with specific types and compiled as usual from there. This is available now in Go using explicit code generation, and is the essence of how C++ templates work, and of the current draft proposal. To make this work as a builtin language feature, the relevant types must be specified as parameters somehow, which in general requires new syntax relative to code that doesn't have such parameters. Furthermore, there is generally a question of which types are valid type parameters -- the instantiated code could simply fail to compile, but it would be nicer if there was a clearer way to specify this, so error messages could be clearer about exactly what the real problem is. This is the problem that contracts, concepts, etc are trying to solve, and it is clear that it is a difficult one.
-
Generic types -> elemental operation abstraction ("boxing") The code is written entirely using functions, methods, and operators that are defined (elsewhere) across a relevant class of types, so when one of those types is used, the existing mechanisms of virtualization / abstraction ("boxing") enable the code to compile and work. This is available now in Go by using
interfaces to define the set of elemental methods available for a given type, but having to fully specify all such methods explicitly in an interface could be as much or more work than the generic code itself. In dynamic "duck typed" languages such as Python, this solution is taken to the extreme, where types no longer exist, and any operation or method can be called on anything, and if it works, then it works, and if it doesn't, it doesn't. In between these extremes, one could imagine a version that allows you to take advantage of existing native operators etc for the actual types being used, so all of that did not have to be redefined. This is perhaps a less well-explored area, and is the basis of the proposal here.
Some important pros / cons of each are:
Type-parameterized macros:
-
Good: fully explicit about the types involved; generated code is strongly typed; can use existing native operators / functions / methods etc without having to define those explicitly for each type.
-
Bad: new syntax, extra complexity and abstraction in reading the code -- mentally having to keep track of not only the actual arguments but also their types etc; the difficulties with contracts / concepts etc restricting the valid types; managing all the issues of when and where the macros are actually instantiated, how to prevent duplicate copies being sprinkled all over the codebase (code bloat), etc (the current explicit code generation has the distinct advantage of avoiding these problems, but at the cost of being entirely static).
Elemental operation abstraction:
-
Good: no need for extra type parameters -- the type itself is the parameter (see e.g., Dave Cheney's blog), resulting in simpler syntax. In Python, you get rid of types entirely, but with Go interfaces, you just specify the interface type and that then tells you a lot about what kind of thing you're operating on, satisfying many of the desiderata for concepts / contracts.
-
Bad: depending on the implementation, there may be a virtualization / abstraction penalty ("boxing" cost) for every single operation / method in the generic code. This is one reason Python is slow. Also, type-checking may need to be done at runtime, elminating all the massive benefits of static typing. However, if the class of types is sufficiently restricted then different versions of the code can be compiled for each type, turning this approach into a simpler way of achieving essentially the same outcome as type-parameterized macros. This is a key point for the proposed approach.
To have a point of reference, this is what the current draft proposal looks like:
type List(type T) []T
func Keys(type K, V)(m map[K]V) []K
var ints List(int)
keys := Keys(int, string)(map[int]string{1:"one", 2: "two"})It is clear that adding the type parameters significantly complicates the syntax. These extra syntax parsing difficulties are well acknowledged in the draft proposal, but it is argued that only a few people will be actually writing these things, and mostly consumers can rely on type inference to avoid having to deal with the extra syntax. Probably this is true (though see: Dave Cheney's blog), but the main hangup has been with the nature of the contracts specifying constraints on the type parameters, and it doesn't appear that there has been a satisfying resolution of this so far?
Michal's proposal simplifies the syntax by dropping the explicit type parameters and just using completely generic type arguments for functions, with no explicit mechanism to restrict the nature of the types. If the code compiles with a given concrete type argument, then it works, and otherwise you get a compile-time error. Although this version of the proposal had many limitations, a subsequent revision included the idea of further specializing these generic types, including the idea of adding a gen num type which represents any type of number. The present proposal picks up from that idea and takes it to the logical extreme of having different generic type names for each existing native Go type kind.
Another approach in the elemental operation abstraction category is Eric S. Raymond's "unwelcome conclusion" that operator overloading is the simplest way to achieve generics in Go. This allows user-defined types to be unified with native types by utilizing the same operators, so you can write functions using such operators and thus achieve elemental operation abstraction. However, there were a number of issues with this approach, which can be avoided with the current proposal.
Go1 already has a great example of the proposed approach: interface{} -- this is a generic version of an interface, and it does a lot of work as a universal generic type. However, is too generic, and thus lacks the built-in operators and functions that you often need. Thus, the proposal can be seen as completing this initial idea and providing all the other generic versions of each builtin type.
It could be possible to write a Min the other way, without the implication that the two args are the same underlying type:
func Min(x number, y number) type(x) {
if x < y {
return x
}
return y
}If x and y are different types, then which version of the operator is used, and why should x's type be used for the return value instead of y? Although some complicated set of standard up-conversion rules could be applied (e.g., an int vs. a float64 would have the int converted to a float64), it likely makes more sense to simply declare such functions illegal -- you can only write generic functions using binary operations involving the same underlying types. To call such functions when dealing with two different types, the user (caller) has to decide which to convert to make them consistent. This would eliminate the combinatorial explosion of dealing with all the different combinations of types, at little practical cost in terms of overall functionality. Also, this avoids having to arbitrarily pick one arg for the return type.
It seems likely that a generic form of the math library could be written using float instead of float64 -- it would automatically be precompiled into float32 and 64 versions, and likewise an appropriate integer math library could be written handling all the relevant integer math, including Max, Min for ints.
The struct interface is orthogonal from the existing interface because it specifies a particular implementation to a problem in a generic way, whereas the interface only specifies an abstract interface and specifically no implementation. Furthermore, a struct interface can not define any un-implemented methods, while an interface only defines such methods.
A given struct interface, by defining various methods, could thereby automatically satisfy various interfaces, and thus anything implementing the struct interface would also implement the interface. Furthermore, the concrete type can define further methods of its own that satisfy interfaces, which the struct interface does not. Again the, two seem entirely complementary.
As such, it might be useful to consider alternative names for a struct interface. It is interface-like in the implicit matching of a concrete implementation. But maybe that is too confusing relative to an API-like interface, and perhaps struct template or genstruct or some other name might avoid potential confusion?
Just as we can use interface as a completely generic interface type, we could presumably use struct as a generic struct type, which can be satisfied by any specific struct. It differs from interface (or currently interface{}) by virtue of supporting the field accessor operations, so you could do something like this:
func StructName(st *struct) string {
return st.Name
}If the specific struct you pass to this function doesn't have a Name field, that should be known at compile time given the constraint that we can only call generic functions with known concrete types, so it can properly warn you about this error. This again opens up a lot of generic territory in providing ways of accessing fields of arbitrary types without requiring that they implement a particular interface. It is not clear how useful this might be, and it might end up being too powerful and overlapping with other functionality, so it might be better to disallow this particular corner of the space, but anyway it is an option. It seems like defining specific named struct interfaces with specific fields will be far clearer and better practice overall.
Nevertheless, perhaps it might be useful to use struct instead of interface for functions that should only operate on struct types, and then you can use the specific type conversion or type switch techniques from there, just as you would now on a interface{} type.
No. Reflection gives explicit access to unknown types, whereas most likely generic types could only be used when a concrete known type is used to instantiate them. In many cases, the generic code should be entirely indistinguishable from that produced by explicitly typing out the code with different type names (or using a code generator) -- i.e., much faster than reflection-based code. Although you can use reflection-like elem, key etc to access the type parameters of containers, you likely could only use the results where a concrete type name would be required, and not for generic reflection-level functionality (though you could presumably use them in a type switch, which could end up avoiding some of the use-cases for reflection).
Here we reiterate and elaborate on the limitations of this proposal. The key question is: are the benefits of simplicity etc worth the costs of these tradeoffs in the overall balance?
A core, defining limitation of this proposal is that you can't use purely arbitrary generic types "T". Thus, you can not have e.g., Min / Max functions operating on anything -- every function accepts only generic versions of existing native type kinds. BigInt will have to remain a special case under this proposal.
As now noted in the Min / Max example above, and pointed out by Michal Štrba and Álvaro López Espinosa, there are challenges associated with the abiilty to explicitly specify that different generic variables should be of the same concrete type. For elements of the same list (e.g., args, fields), using the x, y number expression can nicely express this constraint. But what about connecting e.g., the return type of a function with its arg types? In Michal's proposal, this is a core feature of the proposed syntax:
func Apply(f func(gen T) gen U, x T) U {
return f(x)
}Where the return type U is explicitly connected to the U in the arg expression. Because we don't have fully generic types in the first place, the generic native types version of this would become e.g.,:
func Apply(f func(n number) number, x number) return(f) {
return f(x)
}Previously, this proposal just had a generic number as the return value, but that would put all the burden on type consistency on the compiler working through the return expressions, so now we have introduced the following constraint:
A generic return type must be one of the argument types, or a type parameter of one of the argument types, e.g.,
type(x), elem(x)key(x),return(f),field(x,fieldName).
In practice, this constraint is likely to cover most cases -- where else would a generic type come from except from one of those? If you're going to do some other kind of type conversion, then that type should be known and you should just return that concrete type instead of a generic type.
For concreteness, here's a more "real world" example of an Apply-like function:
func SumFunc(s slice, f func(x elem(s)) number) return(f) {
var sum return(f)
for i, x := range s {
sum += f(x)
}
return sum
}Here is the complete list of the new and repurposed keywords for this proposal:
- Type kinds:
slice,array,number,unsigned,signed,float,complex - Type parameters:
elem(x),key(x),field(x, fieldName)
- 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)
How would I make a generic data structure like a generic linked list? Generic in the sense that I can have a linked list of any type of elements, but all have to be the same type in a single list.