mike@christensen.codes ~ $

Exploring Generic Types in Go 2.0

tags
#go #golang

If you’ve ever written any JavaScript, then you’ve likely used a utility library like lodash and underscore. These handy libraries are very flexible thanks to JavaScript’s dynamic typing. For example, we can easily call Lodash’s find method with either an array of numbers or an array of strings:

_.find([1, 2, 3], i => i % 2 === 0) // => 2
_.find(['one', 'two', 'three'], i => i.length === 5) // => 'three'

This has always been a bit more tricky in Go, due to the static type system and lack of generic types.

Nonetheless, similar libraries do exist in the Go ecosystem: one excellent example is gofunk from @thoas. However, restrictions in the Go language mean that tradeoffs must be made in order to implement type-agnostic functions. In this post I’d like to explore these trade-offs and describe a coming change to the Go language that will improve the language’s support for this type of programming.

Go 1: Type-safe Implementation

Traditionally, Go programmers have to write a type-safe implementation of a given function for each type that needs to be supported.

func FindInt(in []int, f func(int) bool) int {
    for i := range in {
        if f(in[i]) {
            return in[i]
        }
    }
    return nil
}

func FindString(in []string, func(string) bool) string {
    for i := range in {
        if f(in[i]) {
            return in[i]
        }
    }
    return nil
}

func main() {
    FindInt([]int{1, 2, 3}, func(i int) bool { return i % 2 == 0 }) // => 2
    FindString([]string{"one", "two", "three"}, func(s string) bool { return len(s) == 5 }) // => "three"
}

You can see that the function bodies for FindString and FindInt are identical. Reimplementing the function for each type leads to code duplication. However, we maintain the type safety we expect from our Go programs.

Go 1: Reflection-based Implementation

How can we can get around duplicating code? Go 1.X provides us with a way to write functions that can handle arguments of unknown type thanks to the empty interface. Since every type implements at least zero methods, the empty interface type can hold values of any type.

As the Go proverb says:

interface{} says nothing

The implication of this is that the behaviour (given by the underlying type) of an interface{} function argument is unknown at compile-time. Therefore we must inspect the argument at run-time to understand what we can do with it. We can achieve this by using reflection.

func Find(in interface{}, f interface{}) interface{} {
    funcValue := reflect.ValueOf(f)
	funcType := funcValue.Type()
	if funcType.Out(0).Kind() != reflect.Bool {
		panic("f should return a boolean")
    }
    inValue := reflect.ValueOf(in)
	for i := 0; i < inValue.Len(); i++ {
        elem := inValue.Index(i)
		result := funcValue.Call([]reflect.Value{elem})[0].Interface().(bool)
		if result {
			return elem.Interface()
		}
    }
    return nil
}

func main() {
    Find([]int{1, 2, 3}, func(i int) bool { return i%2 == 0 }) // => 2
    Find([]string{"one", "two", "three"}, func(s string) bool { return len(s) == 5 }) // => "three"
}

We’ve succeeded in defining the Find function only once. Additionally, we can call Find with whatever type arguments we desire.

However, in reducing code duplication we have lost the benefits of compile-time type-checking and instead we must make these checks at run-time. The onus is no longer on the compiler to ensure the type-safety of your program; instead it is on you, the developer.

To illustrate this point, imagine we make a call to Find with an argument of type map[string]int:

func main() {
    Find(map[string]int{
        "one":   1,
        "two":   2,
        "three": 3,
    }, func(i int) bool { return i%2 == 0 })
}

To the unwitting developer, this looks like a perfectly reasonable program: “take this map and return the first even value you happen to come across”. This program will even compile just fine. However, at run-time you’ll be hit with a panic:

panic: reflect: call of reflect.Value.Index on map Value

goroutine 1 [running]:
reflect.Value.Index(0x10d66e0, 0xc000098180, 0x15, 0x0, 0x10d2b20, 0x30, 0x11c14a0)
...

It turns out that our Find function was implicitly expecting the underlying type of the in interface{} argument to be a slice. When it happened to be a map instead, our call to Index on the reflect value caused a panic.

For this reason, code that uses reflection must be very, very well tested. Additionally, your documentation should be absolutely clear about the argument types your function expects to receive. Even an astute developer who reads your implementation is very likely to miss something. As that other old Go proverb goes:

Reflection is never clear.

Additionally, we incur a performance cost when we rely on code that uses reflection. Our reflection-based implementation of Find is simply less concise and makes more allocations than our type-safe equivalents. We can get an indication of the size of this cost by writing some benchmarks for the Find and FindInt functions:

package main

import (
	"testing"
)

func benchmarkFindInt(i int, b *testing.B) {
	is := make([]int, i)
	for x := range is {
		is[x] = x
	}
	for n := 0; n < b.N; n++ {
		FindInt(is, func(i int) bool { return i == len(is)-1 })
	}
}

func benchmarkFind(i int, b *testing.B) {
	is := make([]int, i)
	for x := range is {
		is[x] = x
	}
	for n := 0; n < b.N; n++ {
		Find(is, func(i int) bool { return i == len(is)-1 })
	}
}

func BenchmarkFindInt10(b *testing.B)    { benchmarkFindInt(10, b) }
func BenchmarkFindInt100(b *testing.B)   { benchmarkFindInt(100, b) }
func BenchmarkFindInt1000(b *testing.B)  { benchmarkFindInt(1000, b) }
func BenchmarkFindInt10000(b *testing.B) { benchmarkFindInt(10000, b) }

func BenchmarkFind10(b *testing.B)    { benchmarkFind(10, b) }
func BenchmarkFind100(b *testing.B)   { benchmarkFind(100, b) }
func BenchmarkFind1000(b *testing.B)  { benchmarkFind(1000, b) }
func BenchmarkFind10000(b *testing.B) { benchmarkFind(10000, b) }

The results on my machine:

❯ go test -bench=. ./...
goos: darwin
goarch: amd64
BenchmarkFindInt10-4            49077010                24.3 ns/op
BenchmarkFindInt100-4            5218797               235 ns/op
BenchmarkFindInt1000-4            558915              2080 ns/op
BenchmarkFindInt10000-4            56361             22674 ns/op
BenchmarkFind10-4                 456028              2519 ns/op
BenchmarkFind100-4                 49142             23174 ns/op
BenchmarkFind1000-4                 5001            240574 ns/op
BenchmarkFind10000-4                 498           2374598 ns/op
PASS
ok      13.679s

From these results we can see that the reflect-based implementation is two orders of magnitude slower than its type-safe counterpart!

Go 2.0: Introducing Generics

This recent design draft proposes adding Type Parameters to the Go language, which would provide support for generic programming without depending on the empty interface or reflection.

Instead of describing the proposal in its entirety, I will instead show how the new syntax can be used to write generic implementations of common utility functions such as those provided in gofunk. I encourage you to read the design draft to gain a deeper understanding of how generics might be implemented in Go.

Type Parameters

In the proposed syntax, type parameters appear before regular parameters and are encapsulated by square brackets. In the same way that regular parameters have types, type parameters have constraints. A special constraint any can be used to match any type.

Using the proposed syntax, we may write a generic implementation of the Find function as:

func Find[T any](s []T, f func(T) bool) T {
    for i := range s {
		if f(s[i]) {
			return s[i]
		}
	}
	return nil
}

func main() {
    Find([]int{1, 2, 3}, func(i int) bool { return i%2 == 0 }) // => 2
    Find([]string{"one", "two", "three"}, func(s string) bool { return len(s) == 5 }) // => "three"
}

The function has a single type parameter T with constraint any. The types of the regular function parameters refer to this type constraint. The first argument is a slice of any type that meets the contraints given by T, i.e. anything. Similarly, the second argument is a function that accepts an argument of any type and returns a boolean.

This new, powerful syntax has several benefits. We have reduced the code duplication incurred when writing multiple type-safe implementations of our function for each type we wish to support. Secondly, we have done so without bloating the function body with complex and unreadable reflection logic. Finally, we have maintained the type-safety of our program. Unlike the empty interface, the usage of type parameters allows us to assert that the type of s must be a slice (not a map!) of T.

Type Constraints

In the draft proposal, type constraints are simply interface types. Therefore the maximally permissive type constraint any is equivalent to interface{}.

We can apply further restrictions to our type parameters by using more specific interfaces. For example:

type Stringer interface {
	String() string
}

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

In this example, a slice of any type that implements a String() string method can be passed to Stringify.

In some cases it is useful to constrain types by the operators that can be used with them. The built-in comparable constraint, for example, ensures our arguments can be compared using the == and != operators.

// Index returns the index of x in s, or -1 if not found.
func Index[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
}

The proposal defines a mechanism to construct type constraints by providing a type list. This allows us to create a type constraint to accept only types that support a given set of operators. Note that these embedded type lists inside interfaces can only be used with interfaces that are to be used as type constraints.

// 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
}

Generic Types

In addition to generic functions, the proposal also supports generic types. This is achieved by passing type parameters to a type definition.

type Vector[T any] []T

Type arguments are then supplied when the type is instantiated.

var v Vector[int]

These types can have methods that use the constraints:

func (v *Vector[T]) Push(x T) { *v = append(*v, x) }

go-funk-generics

In order to get my hands dirty with generics, I set out to implement the go-funk API in Go 2. The result can be found in go-funk-generics. I won’t detail the implementation for each function here, but if you’re interested feel free to check it out (and give it a ⭐!). Hopefully it gives an indication of what a modern utility library might look like if the Go team releases generics support.

One interesting thing I wanted to achieve was the ability to chain methods together like you might in JavaScript. As a toy example:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    .filter(x => x % 2 === 0)
    .map(x => `${x}`)
    .reduce((prev, cur) => `${prev}${cur};`, '')
// => 2;4;6;8;10;

The filter, map and reduce functions can be written as follows in Go2:

func Filter[T any](s []T, f func(T) bool) []T {
	var r []T
	for _, v := range s {
		if f(v) {
			r = append(r, v)
		}
	}
	return r
}

func Map[T1, T2 any](s []T1, f func(T1) T2) []T2 {
	r := make([]T2, len(s))
	for i, v := range s {
		r[i] = f(v)
	}
	return r
}

func Reduce[T1, T2 any](s []T1, initial T2, f func(T2, T1) T2) T2 {
	r := initial
	for _, v := range s {
		r = f(r, v)
	}
	return r
}


// example usage

x1 := Filter[int]([]int{1,2,3,4,5,6,7,8,9,10}, func(i int) bool {
    return i % 2 == 0
})
x2 := Map[int, string](x1, strconv.Itoa)
x3 := Reduce[string, string](x2, "", func (prev, cur string) string {
    return prev + cur + ";"
})
fmt.Println(x3) // => 2;4;6;8;10;

How can we make these functions chainable? One approach is to use a generic type. Then, we can implement methods on each which wrap calls to the relevant functions.

type List[T any] []T

func (l List[T]) Append(e ...T) List[T] {
	return append(l, e...)
}

func (l List[T]) Filter(f func(T) bool) List[T] {
	return Filter(l, f)
}

type Mappable[T1, T2 any] List[T1]

func (m Mappable[T1, T2]) Map(f func(T1) T2) List[T2] { // Mappable[T1, T2] { cant do this as we dont know the types we want to map to! only the caller does
	return Map[T1, T2](m, f)
}

func (m Mappable[T1, T2]) Reduce(initializer T2, f func(T2, T1) T2) T2 {
	return Reduce[T1, T2](m, initializer, f)
}

Here, the generic Mappable type implements both Map and Reduce methods. Therefore it would be great if Map could return a Mappable type too, so that Reduce could be called as part of a chain. Unfortunately this is not possible as we dont know the target types the caller wants to map to. To get around this, the caller can cast the result of a call to the relevant generic type, which isn’t very pretty. If anyone has a brighter idea of how to do this, please reach out on Twitter!

var l List[int]
x := Mappable[string, string](
    Mappable[int, string](
        l.Append(1,2,3,4,5,6,7,8,9,10).
        Filter(func(i int) bool {
            return i % 2 == 0
        }),
    ).Map(strconv.Itoa),
).Reduce("", func (prev, cur string) string {
    return prev + cur + ";"
})
fmt.Println(x)

Conclusion

This is new and exciting territory for Go. On the one hand, I love the expressivity of the proposed syntax. It feels great to implement a function only once, with a simple function body unbloated by reflection logic, and call it on any type I wish.

On the other hand, this code is undoubtedly harder to understand and, in my opinion, detracts from the magic of Go’s simplicity. There is a risk that the average quality and readability of the world’s Go code may decrease as this powerful feature is abused.

I wonder how prudent these changes are given that, for the cases where generics are desirable, there are viable intermediate solutions such as code generation which solve the problem of hand-writing multiple type-safe implementations!

Another concern I have is that using methods to constrain types (via interfaces) is often kind of useless, when you could just use the interface with the regular type parameters. For example:

type Stringer interface {
	String() string
}

type foo struct {
	x string
}

func (f *foo) String() string {
	return f.x
}

func StringifyGeneric[T Stringer](s []T) (ret []string) {
	for _, v := range s {
		ret = append(ret, v.String())
	}
	return ret
}

func StringifyNormal(s []Stringer) (ret []string) {
	for _, v := range s {
		ret = append(ret, v.String())
	}
	return ret
}

func main() {
	a := &foo{"one"}
	b := &foo{"two"}
	fmt.Println(StringifyGeneric([]*foo{a, b}))
	fmt.Println(StringifyNormal([]Stringer{a, b}))
}

While there are certainly examples of useful method-based type constraints, the fact that this is even possible means people will write code that uses both implementations. As Hyrum’s law says:

With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody.

I’d love to hear other opinions on this - as always, you can find me on Twitter. 😇

EDIT

As @joncalhoun pointed out to me on Twitter, in this example it may be more common to have a slice of foo, which the generic implementation happily accepts while the traditional one requires a little more wrangling. He points out the very interesting possibility that perhaps the compiler could solve this by compiling the traditional implementation to the generic one. Personally, I would be thrilled to see an approach that leverages the power of generics without altering the syntax of the language.

package main

import (
	"fmt"
	"strings"
)

type Stringer interface {
	String() string
}

type Upper interface {
	Up() string
}

type foo struct {
	x string
}

func (f *foo) String() string {
	return f.x
}

func (f *foo) Up() string {
	return strings.ToUpper(f.x)
}

func StringifyGeneric[T Stringer](s []T) (ret []string) {
	for _, v := range s {
		ret = append(ret, v.String())
	}
	return ret
}

func UpifyGeneric[T Upper](s []T) (ret []string) {
	for _, v := range s {
		ret = append(ret, v.Up())
	}
	return ret
}

func StringifyNormal(s []Stringer) (ret []string) {
	for _, v := range s {
		ret = append(ret, v.String())
	}
	return ret
}

func UpifyNormal(s []Upper) (ret []string) {
	for _, v := range s {
		ret = append(ret, v.Up())
	}
	return ret
}

func main() {
	// More realistically, you probably already have a slice of foo
	foos := []*foo{
		&foo{"one"},
		&foo{"two"},
		&foo{"three"},
		&foo{"four"},
	}

	// Using generics here it is super easy to use Stringify
	fmt.Println(StringifyGeneric(foos))
	fmt.Println(UpifyGeneric(foos))

	// Using interfaces as they are now is a little more annoying in this case.
	var stringers []Stringer
	for _, foo := range foos {
		stringers = append(stringers, foo)
	}
	fmt.Println(StringifyNormal(stringers))

	// The problem is further exacerbated if you need to call multiple functions with different interface slices
	var uppers []Upper
	for _, foo := range foos {
		uppers = append(uppers, foo)
	}
	fmt.Println(UpifyNormal(uppers))
}

Thanks Jon for your input!

If you’d like to get your hands dirty with generics, try writing some simple programs in the Go2 playground. Feel free to clone the go-funk-generics repo and have a play around!

Thanks for reading.