Idiomatic Generics in Go
Go has a fantastic standard library and powerful concurrency primitives, but the type system is notoriously lacking. One of the main features that is sorely missing is generics. In this post I’ll compare different methods of implementing generics in Go, and show you what crazy hoops I jumped through to arrive at something that resembles generics in other languages.
Copy and Paste
A combination of interfaces and good ol’ copy and paste is the way Go currently implements sortable slices. This is of course a terrible, terrible idea. The names of your types will end up being StringSet, IntSet, and FloatSet. When you find a bug you’ll be forced to go through all of the instances where you copied and pasted, fix it and hope you don’t miss any. This is clearly not a sustainable way to ‘implement’ generics.
Reflection
A commonly suggested way to implement higher-order functions such as Map/Reduce/Filter is to use reflection, and you’ll end up with something like this:
This will give you lots of flexibility, at the cost of static type checking. Losing static type checking will force you to do type checking at runtime, which has a big performance impact and you will lose many of the guarantees a type system gives you. The code is also way harder to understand because of the interface{} types everywhere.
Templating
It would be ideal if we could just write Go like this:
I’ve implemented a program that does exactly this. It parses the file, traverses the AST and replaces any reference to the type variable T with the passed type.
This approach has been taken by other projects such as gengen, the issue however is that this is still a pain to use. You will have to manage the correctly typed files yourself, while also juggling packaging issues (as multiple versions of the same template will share a namespace). We need something a bit more powerful.
Go-ing beyond templating: gonerics.io
To fix this issue I’ve created a service called gonerics.io, which delivers easily usable generics as a service (GAAS). Using gonerics.io is as simple as go getting the appropriate package. For example: go get gonerics.io/d/set/string.git. You can then use it as follows:
This will print true false, as you would expect. The code is also super readable, as you don’t have to do any crazy casting or reflection. Converting this to a program that uses ints is as easy as changing the import, like follows:
After running go get gonerics.io/d/set/int.git and compiling, this will also print true false. This makes generics super easy to use!
Let’s go-get functional
This is not where it stops of course. I’ve also implemented the above mentioned Map/Reduce and Filter using gonerics. The template can be found here. If we now do go get gonerics.io/f/functional/int.git we will have access to a bunch of powerful functions, that are also typesafe! For example:
When we run this we get the following output:
[2 4 6 8 10 12 14 16 18 20 22 24]
[13 25 37 49 61 73]
[1 4 9 16 25 36 49 64 81 100 121 144]
I’ve also added support for templates with multiple arguments, so we can do something like this:
Which will print 16 when executed.
We have to Go deeper
The fact that goneric templates are go-gettable opens up some interesting possibilities. Take this simple template for a directed graph datastructure for example:
We can then use it as follows:
Because go get recursively fetches dependencies I can simply refer to another goneric template inside my template and achieve code reusability through generics!
Giving it a Go
Gonerics.io supports custom templates, to use them simply create a gist of your template (like the above set template for example). You can then import it using a URL like the following (the gist ID is without your Github username):
gonerics.io/g/<gist id>/<type arguments seperated by _>.git
The package will then be available under the name of file minus “.go”. Your gist should have only a single file, with the .go extension. There probably won’t be any useful error message when you make a mistake because I haven’t implemented any. The type arguments are accessible under T, U, V etc.
How does this work?!
Through the magic of CGI and shell scripting! In my Nginx config I use a shell script as the CGI program to use. When git request the repository, this script will check if the specific combination of template and arguments has been served before. If it hasn’t, it will first generate the correct file and check it into a new git repo. Finally, it’ll call git-http-backed which will actually serve the http request.
The rest of the (rough) code that powers gonerics.io can be found here: github.com/bouk/gonerics. Don’t use gonerics.io for anything important please. It’s meant as a proof of concept.
The future of generics in Go
Go should have proper support for generics so these shenanigans aren’t necessary. Rob Pike has recently suggested a new command for the go tool called go generate with the intention to also support a simple form of templating. Looking over the design document, I feel like it would not solve the generics problem at all (although that isn’t really what they set out to do). Go would greatly benefit from a proper generics system, and I think it’s way overdue.
Sep 2014