Generics for Go

July 1, 2020

This article was contributed by Ben Hoyt

The Go programming language was first released in 2009, with its 1.0 release made in March 2012. Even before the 1.0 release, some developers criticized the language as being too simplistic, partly due to its lack of user-defined generic types and functions parameterized by type. Despite this omission, Go is widely used, with an estimated 1-2 million developers worldwide. Over the years there have been several proposals to add some form of generics to the language, but the recent proposal written by core developers Ian Lance Taylor and Robert Griesemer looks likely to be included in a future version of Go.

Background

Go is a statically typed language, so types are specified in the source code (or inferred from it) and checked by the compiler. The compiler produces optimized machine code, so CPU-intensive code is significantly more efficient than languages like Python or Ruby, which have bytecode compilers and use virtual machines for execution.

Generics, also known as "parameterized types" or "parametric polymorphism", are a way to write code or build data structures that will work for any data type; the code or data structure can be instantiated to process each different data type, without having to duplicate code. They're useful when writing generalized algorithms like sorting and searching, as well as type-independent data structures like trees, thread-safe maps, and so on. For example, a developer might write a generic min() function that works on all integer and floating-point types, or create a binary tree that can associate a key type to a value type (and work with strings, integers, or user-defined types). With generics, you can write this kind of code without any duplication, and the compiler will still statically check the types.

Like the first versions of Java, Go doesn't ship with user-defined generics. As the Go FAQ notes , generics " may well be added at some point "; it also describes how leaving them out was an intentional trade-off:

Generics are convenient but they come at a cost in complexity in the type system and run-time. We haven't yet found a design that gives value proportionate to the complexity, although we continue to think about it. Meanwhile, Go's built-in maps and slices, plus the ability to use the empty interface to construct containers (with explicit unboxing) mean in many cases it is possible to write code that does what generics would enable, if less smoothly.

Part of the reason actual users of the language don't complain loudly about the lack of generics is that Go does include them for the built-in container types, specifically slices (Go's growable array type), maps (hash tables), and channels (thread-safe communication queues). For example, a developer writing blog software might write a function to fetch a list of articles or a mapping of author ID to author information:

// takes ID, returns "slice of Article" (compiler checks types)
    func GetLatestArticles(num int) []Article {
        ...
    }

    // takes "slice of int" of IDs, returns "map of int IDs to Author"
    func GetAuthors(authorIDs []int) map[int]Author {
        ...
    }

Built-in functions like len() and append() work on these container types, though there's no way for a developer to define their own equivalents of those generic built-in functions. As many Go developers will attest, having built-in versions of growable arrays and maps that are parameterized by type goes a long way, even without user-defined generic types.

In addition, Go has support for two features that are often used instead of generics or to work around their lack: interfaces and closures. For example, sorting in Go is done using the sort.Interface type, which is an interface requiring three methods:

type Interface interface {
        Len() int           // length of this collection
        Less(i, j int) bool // true if i'th element < j'th element
        Swap(i, j int)      // swap i'th and j'th elements
    }

If a user-defined collection implements this interface, it is sortable using the standard library's sort.Sort() function. Since sort.Slice() was added in Go 1.8, developers can use that function and pass in a "less-than closure" rather than implementing the full sorting interface; for example:

// declare a struct for names and ages and a slice of those structs with four entries
    people := []struct {
        Name string
        Age  int
    }{
        {"Gopher", 7},
        {"Alice", 55},
        {"Vera", 24},
        {"Bob", 75},
    }

    // sort people using the "less-than closure" specified in the call
    sort.Slice(
        people,
        func(i, j int) bool { // i and j are the two slice indices
            return people[i].Name < people[j].Name
        },
    )

There are other ways to work around Go's lack of generics, such as creating container types that use interface{} (the "empty interface"). This effectively boxes every value inserted into the collection, and requires run-time type assertions, so it is neither particularly efficient nor type-safe. However, it works and even some standard library types like sync.Map use this approach.

Some developers go so far as to argue that generics shouldn't be added to Go at all, since they will bring too much complexity. For example, Greg Hall hopes " that Go never has generics, or if it does, the designers find some way to avoid the complexity and difficulties I have seen in both Java generics and C++ templates ".

The Go team takes the complexity issue seriously. As core developer Russ Cox states in his 2009 article " The Generic Dilemma ":

Still, many Go developers are asking for generics, and there has been a huge amount of discussion over the years on the best way to add them in a Go-like way. Several developers have provided thoughtful rationale in " experience reports " from their own usage of Go. Taylor's entry in the official Go blog, " Why Generics? ", details what adding generics will bring to Go, and lists the guidelines the Go team is following when adding them:

Most importantly, Go today is a simple language. Go programs are usually clear and easy to understand. A major part of our long process of exploring this space has been trying to understand how to add generics while preserving that clarity and simplicity. We need to find mechanisms that fit well into the existing language, without turning it into something quite different.

These guidelines should apply to any generics implementation in Go. That's the most important message I want to leave you with today: generics can bring a significant benefit to the language, but they are only worth doing if Go still feels like Go.

The recent proposal

Taylor, in particular, has been prolific on the subject of adding generics to Go, having written no fewer than six proposals. The first four, written from 2010 through 2013, are listed at the bottom of his document, " Go should have generics ". About them, he notes: " all are flawed in various ways ". In July 2019 he posted the "Why Generics?" blog article mentioned above, which links to the lengthy 2019 proposal written by Taylor and Griesemer for a version of generics based on "contracts". Almost a year later, in June 2020, Taylor and Griesemer published the current proposal, which avoids adding contracts. In Taylor's words :

An earlier draft design of generics implemented constraints using a new language construct called contracts. Type lists appeared only in contracts, rather than on interface types. However, many people had a hard time understanding the difference between contracts and interface types. It also turned out that contracts could be represented as a set of corresponding interfaces; thus there was no loss in expressive power without contracts. We decided to simplify the approach to use only interface types.

The removal of contracts comes in part based on work by Philip Wadler and his collaborators in their May 2020 paper, " Featherweight Go [PDF] " ( video presentation ). Wadler is a type theorist who has contributed to the design of Haskell, and was involved in adding generics to Java back in 2004. Rob Pike, one of Go's creators, had asked Wadler if he would " be interested in helping us get polymorphism right (and/or figuring out what 'right' means) for some future version of Go "; this paper is the response to Pike's request.

The 2020 proposal suggests adding optional type parameters to functions and types, allowing generic algorithms and generic container types, respectively. Here is an example of what a generic function looks like under this proposal:

// Stringify calls the String method on each element of s,
    // and returns the results.
    func Stringify(type T Stringer)(s []T) []string {
        var ret []string
        for _, v := range s {
            ret = append(ret, v.String())
        }
        return ret
    }

    // Stringer is a type constraint that requires the type argument to have
    // a String method and permits the generic function to call String.
    // The String method should return a string representation of the value.
    type Stringer interface {
        String() string
    }

The type parameter is T (an arbitrary name), specified in the extra set of parentheses after the function name, along with the Stringer constraint: type T Stringer . The actual arguments to the function are in the second set of parentheses, s []T . Writing functions like this is not currently possible in Go; it does not allow passing a slice of a concrete type to a function that accepts a slice of an interface type (e.g., Stringer ).

In addition to generic functions, the new proposal also supports parameterization of types, to support type-safe collections such as binary trees, graph data structures, and so on. Here is what a generic Vector type might look like:

// Vector is a name for a slice of any element type.
    type Vector(type T) []T

    // Push adds a value to the end of a vector.
    func (v *Vector(T)) Push(x T) {
        *v = append(*v, x)
    }

    // v is a Vector of Authors
    var v Vector(Author)
    v.Push(Author{Name: "Ben Hoyt"})

Because Go doesn't support operator overloading or define operators in terms of methods, there's no way to use interface constraints to specify that a type must support the < operator (as an example). In the proposal, this is done using a new feature called "type lists", an example of which is shown below:

// Ordered is a type constraint that matches any ordered type.
    // An ordered type is one that supports the <, <=, >, and >= operators.
    type Ordered interface {
        type int, int8, int16, int32, int64,
            uint, uint8, uint16, uint32, uint64, uintptr,
            float32, float64,
            string
    }

In practice, a constraints package would probably be added to the standard library which pre-defined common constraints like Ordered . Type lists allow developers to write generic functions that use built-in operators:

// Smallest returns the smallest element in a slice of "Ordered" values.
    func Smallest(type T Ordered)(s []T) T {
        r := s[0]
        for _, v := range s[1:] {
            if v < r { // works due to the "Ordered" constraint
                r = v
            }
        }
        return r
    }

The one constraint that can't be written as a type list is a constraint for the == and != operators, because Go allows comparing structs, arrays, and interface types for equality. To solve this, the proposal suggests adding a built-in comparable constraint to allow equality operators. This would be useful, for example, in a function that finds the index of a value in a slice or array:

// Index returns the index of x in s, or -1 if not found.
    func Index(type T comparable)(s []T, x T) int {
        for i, v := range s {
            // v and x are type T, which has the comparable
            // constraint, so we can use == here.
            if v == x {
                return i
            }
        }
        return -1
    }

Taylor and Griesemer have developed a tool for experimentation (on the go2go branch) that converts the Go code as specified in this proposal to normal Go code, allowing developers to compile and run generic code today. There's even a version of the Go playground that lets people share and run code written under this proposal online — for example, here is a working example of the Stringify() function above.

The Go team is asking developers to try to solve their own problems with the generics experimentation tool and send detailed feedback in response to the following questions:

First, does generic code make sense? Does it feel like Go? What surprises do people encounter? Are the error messages useful?

Second, we know that many people have said that Go needs generics, but we don't necessarily know exactly what that means. Does this draft design address the problem in a useful way? If there is a problem that makes you think "I could solve this if Go had generics," can you solve the problem when using this tool?

Discussion

There has been a lot of public discussion about generics on the main golang-nuts mailing list since the latest proposal was published, as well as on Hacker News and reddit.com/r/golang threads.

As Pike said [YouTube] last year, "syntax is not the problem, at least not yet", however, many of the threads on the mailing list have been immediately critical of the syntax. Admittedly, the syntax is unusual, and it adds another set of (round) parentheses to Go, which is already known for having lots of parentheses (for example, Go's method definitions use one set for the method's receiver type, and another for the method's arguments). The proposal tries to preempt the syntax bikeshedding with an explanation of why they chose parentheses instead of angle brackets:

When parsing code within a function, such as v := F<T> , at the point of seeing the < it's ambiguous whether we are seeing a type instantiation or an expression using the < operator. Resolving that requires effectively unbounded lookahead. In general we strive to keep the Go parser efficient.

Most responders on the mailing list are proposing the use of angle brackets like C++, Java, and C#, for example, using List<T> instead of List(T) . Taylor is much more interested in whether the semantics of the new proposal make sense, but has been patiently replying to each of these syntax threads with something like the following:

Let's see what real code looks like with the suggested syntax, before we worry about alternatives. Thanks.

This has happened so many times that one mailing list contributor, Tyler Compton, compiled a helpful list of all the syntax-related threads.

Generics will help eliminate types and functions repeated for multiple types, for example sort.Ints , sort.Float64s , and sort.Strings in the sort package. In a comment on Hacker News, Kyle Conroy showed " a four-line replacement for the various sql.Null* types in the standard library ":

type Null(type T) struct {
        Val   T
        Valid bool // Valid is true if Val is not NULL
    }

Mailing list contributor Pee Jai wondered whether there's a way to constrain a type to only allow structs, but Taylor indicated that's not possible; he noted that " generics don't solve all problems ". Robert Engels said that the reflect package would still be needed for this case anyway.

In one thread, "i3dmaster" asked some questions about custom map types, and Taylor clarified that " custom container types aren't going to support len() or range ". Creators of collection types won't have access to this special syntax, but will need to define their own Len() method, and their own way to iterate through the collection.

Go core contributor Bryan Mills has posted insightful replies on a number of threads. He has also created his own repository with various notes and code examples from his experiments with generics, including an explanation about why he considers type lists less than ideal. The repository also includes various attempts at re-implementing the append() built-in using generics as proposed.

Timeline

In their recent blog entry, Taylor and Griesemer are clear that adding generics to the language won't be a quick process — they want to get it right, and take into account community feedback:

We will use the feedback we gather from the Go community to decide how to move forward. If the draft design is well received and doesn't need significant changes, the next step would be a formal language change proposal. To set expectations, if everybody is completely happy with the design draft and it does not require any further adjustments, the earliest that generics could be added to Go would be the Go 1.17 release, scheduled for August 2021. In reality, of course, there may be unforeseen problems, so this is an optimistic timeline; we can't make any definite prediction.

My own guess is that August 2021 (just over a year away) is optimistic for a feature of this size. It's going to take quite a while to solicit feedback, iterate on the design, and implement generics in a production-ready way instead of using the current Go-to-Go translator. But given the number of proposals and the amount of feedback so far, generics are sure to be a much-used (and hopefully little-abused) feature whenever they do arrive.

to post comments)