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!
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:
type List struct {
Value interface{}
Next *List
}
This is a generic linked list. How do we use it?
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:
- More code.
- No compile errors, only runtime errors.
- Worse performance, because of boxing/unboxing.
Let's take a look at another trivial example:
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.
If we think about the examples above, what we wanted to express was that some of those interface types are the same.
func Identity(x interface{}) interface{} { // these two interface types are always same
return x
}
type List struct {
Value interface{}
Next *List // the interface value in Next is same as here
}
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:
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.
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:
func EmptyList() *List {
return nil
}
The returned list is typeless, or is it? No one knows, it's ambiguous.
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:
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:
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.
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 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).
How about generic interfaces? For example:
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:
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:
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:
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.
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
I think it would be enough to have a type in most the same as interface{} but with the only restriction, values of different type names isn't assignable.
Assigning t to d and using d as parameter of Foo function that required value of type T should cause error message. The compiler should consider generic types T and D as different because their names differ. It allows an additional type checking and can be easy replaced with standard interface{} after such validation.