.md

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:

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:

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

In the example

type List [T interface] struct {
    Value T
    next *List[T]
}

a)

type List_Foo struct {
    Value Foo
    next *List_Foo
}

or
b)

type List_Foo struct {
    Value interface{}
    next *List_foo
}

Questions:

1. How is the memory layout of the struct expanded? (a or b?) If I declare a variable var List[Foo] where Foo is a struct.

2. Do you mean that b) is always the case?

3. Is is possible to make it always a)? One of the advantages of generics is the ability to eliminate the indirectness of struct fields. And I suppose it's also possible to do what b) does in a) if we deliberately pass an interface object as T.

4. For case a), if we change the 'call site' of the type constructor, say, changing List[Foo] to List[Bar]` of a variable declaration, do we have to re-compile all downstream objects/packages that references to the generic type? Note that I am not sure whether it's already the case even without implementing this generics. For b), I guess it's easier to do separate compilation.

Those are my not-very-thought-out impressions/questions to the idea.

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.

package main

import "fmt"

type T generic{}
type D generic{}

func Foo(t T) T {
    return t
}

func main() {
    var t T
    var d D
    t = 1
    d = t
    t = Foo(d)
   fmt.Println("Value is :", t)
}

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.