@@ -0,0 +1,238 @@
# Ideas on generics in Go
As we all know, Go 2 is on its way and despite the hesitations, it's clear that without generics, it
would end up being a disappointment. And although we are still gathering real-life use-cases, or
experience reports, there's nothing bad about starting to think about how generics in Go could look
like. I've come up with a few ideas which I'd love to share. So, here we go!
## What's already achievable?
Now, Go 1 has no generics, but has interfaces. Interfaces (sometime accompanied by reflection)
actually let you write all kinds of generic code. Generic collections, generic functions, all are
doable.
Let's take a look, here's a very simple linked list:
``` go
type List struct {
Value interface {}
Next *List
}
```
This * is* a generic linked list. How do we use it?
``` go
var l *List
l.PushFront (2 )
l.PushFront (3 )
l.PushFront (l.Value .(int ) + l.Next .Value .(int ))
```
The trouble is all these type assertions. They come with these three downsides:
1 . More code.
2 . No compile errors, only runtime errors.
3 . Worse performance, because of boxing/unboxing.
Let's take a look at another trivial example:
``` go
func Identity (x interface {}) interface {} {
return x
}
func main () {
x := 3
y := Identity (x).(int )
}
```
We know that the return type is same as the argument type and we probably document it. * We just
can't express it in the language* . And we want to express it in the language.
## The problem
If we think about the examples above, what we wanted to express was that ** some of those interface
types are the same** .
``` go
func Identity (x interface {}) interface {} { // these two interface types are always same
return x
}
```
``` go
type List struct {
Value interface {}
Next *List // the interface value in Next is same as here
}
```
## Idea number one - a bad idea
Upon realizing what the problem is (ability to express the "sameness" of interfaces) I came up with
this simple solution: bind the interface types by a name. Here's what I mean:
``` go
func Identity (x T interface {}) T interface {} {
return x
}
```
As you can see, I added another identifier between ` x ` and ` interface{} ` and I added the same
identifier before the return type. This indicates that the types are the same and thus it's possible
to avoid type assertions.
Now, why is this idea bad? It doesn't work with generic types.
``` go
type List struct {
Value T interface {}
Next *List
}
```
You see, there's nothing to bind. Even if we figured out a way to bind the ` Value ` type and the type
inside ` Next ` , this would still be problematic:
``` go
func EmptyList () *List {
return nil
}
```
The returned list is typeless, or is it? No one knows, it's ambiguous.
## Idea number two - probably a good one
As we saw above, ` List ` type needs something like an "associated type" of its element. This type
needs to be not only inferred by the compiler, it needs to be a part of the ` List ` type. Let's come
up with a syntax:
``` go
type List [T interface {}] struct {
Value T
Next *List[T]
}
```
First of all, I hate angle brackets, so that's why I use square ones. Second thing to note is that
` T ` is followed by ` interface{} ` . What this means is that all things of type ` T ` are basically
` interface{} ` , * but* they have the same type. This also let's us express the identity function:
``` go
func Identity [T interface {}](x T ) T {
return x
}
```
Again, this let's us express that the argument and the return type are anything, but they are the
same.
## Translating to Go 1
A very important thing about this form of generics is that it's * fully translatable to Go 1* . Which
means, that all Go 2 libraries utilizing generics would be perfectly usable from Go 1. Let's take a
look:
``` go
// Go 2
type Map [K, V interface {}] struct { /* ... */
// Go 1
type Map struct { /* ... */
// Go 2
func NewMap [K, V interface {}]() *Map[K, V ]
// Go 1
func NewMap () *Map
// Go 2
func (m *Map) Get[K, V interface{}](key K ) (val V )
// Go 1
func (m *Map ) Get (key interface {}) (val interface {})
// Go 2
m := go2pkg.NewMap [string , int ]()
m.Set (" hello" 2 )
x := m.Get (" hello"
// Go 1
m := go2pkg.NewMap ()
m.Set (" hello" 2 )
x := x.Get (" hello" int )
// Go 2
func Dictionary () *Map [string , string ]
// Go 1
func Dictionary() *Map // but it's more than *Map[interface{}, interface{}], see below
// Go 2
dict := go2pkg.Dictionary()
dict.Set("yay", 2) // compile error
// Go 1
dict := go2pkg.Dictionary() // type of dict is *go2pkg.Map
dict.Set("yay", 2) // runtime error
```
What you gain compared to Go 1 is *less typing*, *type safety* and *better performance* if the
compiler takes care of true specializing (but it doesn't have to).
## Generic interfaces
How about generic interfaces? For example:
```go
type Producer[T interface{}] interface {
Produce () T
}
```
The question is: what do I need to do to satisfy the ` Producer ` interface? And the answer is: that's
not possible, you can't satisfy the ` Producer ` interface. You can only satisfy a
` Producer[SomeType] ` interface. And ` Producer[int] ` type is not assignable to
` Producer[interface{}] ` type. The reasons are the same as with "why isn't ` []float64 ` assignable to
` []interface{} ` ". Because the representations are different and taking generics this far would be
too much.
One problem arises with generic interfaces and that is: self-referential generic interfaces. A prime
example of this is the ` Equaler ` interface. In Go 1, we can write:
``` go
type Equaler interface {
Equal (Equaler) bool
}
```
The thing is, this is not type safe, because we can pass any equaler to the ` Equal ` function, but
just the same type as the receiver. The Java way of solving this would be:
``` go
type Equaler [T Equaler [T]] interface {
Equal (T) bool
}
```
However, I really don't like this. Supporting recursive generic type definitions is a too big hammer
for something like this. It's quite unclear too. Ideally, something like this would be nice:
``` go
type Equaler [T interface {}] interface {
(T) Equal (T) bool
}
```
This way, we bound the type of the receiver to the type of the argument. I'm not sure this is the
good solution. Perhaps Go should not even support creating recursive generic interfaces at all.
## Thanks for reading
I'm really glad you got this far. This ideas are not complete, that's why I'm not making it a Go 2
proposal. This is to be improved, inspired from, or trashed.
Michal Štrba
faiface created this gist