A use case for Go Generics in a Go compiler

This is a (very) rare work-related entry. I mostly work on the compiler for a programming language named “Go”, and one of the problems we face is if and how we should add “generics” to a future version of Go. I can’t possibly summarize easily for a non-technical reader, but the TLDR version is (1) lots of other languages have generics (2) we’re pretty sure they’re useful (3) but they come with associated costs and complexity and we’re not sure they’re worth it. Also, “generics” is not just a single thing, there’s several semantic variants and several ways to implement them (for example, erased versus dictionary-passing versus template-stamping). So our team is collecting example stories of how Go generics would be useful in various situations — the jargon term for this is “use case”. Here’s mine:

The Go compiler uses maps fairly often, but map iteration order changes from one program execution to the next (and there are good reasons for this). It is a requirement that the Go compiler always generate the same output given the same program input, which means that any time the iteration order for a map would affect program output, we can’t directly use it.

The way we usually deal with this is to also build a slice of the elements in the map, where each time a new element is inserted in the map (each time insertion changes its size), that element is also appended to the slice, thus giving us an insertion-ordered map. This makes the code slightly clunkier and also adds a speed bump for new work on the compiler (and especially for new contributors to the compiler), where new code is first expressed plainly in idiomatic Go, but the idiomatic Go lacks a constant order, and then the order is cleaned up in a second pass.

We could also solve our problem with a datastructure handling interface{} elements, but this would add a bit of storage overhead (storing 2-element interfaces instead of 1-element pointers) and a little bit of time overhead, and our users are, for better or worse, remarkably sensitive to the time it takes to compile their programs.

With generics (either templated or dictionary-passing; templated would provide the best performance for us) we could define, say, OrderedMap[[T,U]], that would take care of all the order bookkeepping, be space efficient, and fast. If we could arrange for some “sensible” overloading, the difference between idiomatic Go and the correct Go for compiler implementation would be only the declaration of the data structure itself. I think that the overloading has to be part of the use case; if we have to use different syntax for something that is map-like, and thus could not update a program by updating just the declaration/allocation, that’s not as good.

By sensible overloading, I mean that we could define a generic interface type, say MapLike[[T,U]] with methods Get(T)U, GetOk(T)U,bool, Put(T,U), Delete(T), and Len()int, and any data type that supplied those methods could be manipulated using existing Go map syntax.

Iteration methods are also required, but trickier; a fully general solution would use an iteration state with its own methods, or we could declare that iteration state fits in an integer, which constrains the possible map implementations (though would be a very Go thing to do). The integer version could use three methods on the data structure itself, say, FirstOk(int)int,bool, NextOk(int)int,bool, and GetAt(int)T,U. The you-get-an-integer approach is a little interesting because it allows recursive subdivision as well as iteration, if NextOk works properly given an input that is not itself a valid index.

The iterator-state version could instead use the map method Begin()Iterator[[T,U]] and iterator methods Iterator[[T,U]].Nonempty()bool, Iterator[[T,U]].Next(), Iterator[[T,U]].Key()T, Iterator[[T,U]].Value()U. This doesn’t by itself support recursive subdivision; that would require more methods, perhaps one to split the iterator into a pair of iterators at a point and another to report the length of the iterator itself.