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:
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.
The problem
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
}
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:
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.
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:
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.
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 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:
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.
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
Hi! I believe a rather easier solution would be like:
You could also do things like these