UPDATE: The “…” in the title is meant to be a plain English ellipsis! Big thanks to the readers who have pointed out that “…” in this context can (and will) be understood as Go’s ellipsis. In this case the title would of course be complete rubbish.

UPDATE 2: The snappy title is often misunderstood as “Go needs no generics”. This is far from what the article wants to say. I do see the usefulness of generics in certain problem domains, and I am the last one to balk at the idea of generics in Go. If anyone feels misled by the title, I apologize.

UPDATE 3: Go generics are on their way, so this article will soon be of historical interest only. While generics are still a draft, I took my balanced tree code and turned it into a generic tree, to see how easy it is to convert container types into generic ones.

First, an important note

The question about generics in Go is years old, and has been discussed up and down and forth and back across the Go forums, newsgroups, and email lists. It is NOT the goal of this article to re-ignite this discussion. I think that all that can be said, has been said.

A good summary of the state of the discussion is here.

This article solely focuses on alternate ways of achieving some of the goals that other languages try to solve with generics.

Let’s start by briefly looking at the motivation for generics as well as the possible downsides.

The problem

Many data structures and algorithms are applicable to a range of data types. A sorted tree, for example, could be defined to hold elements of type int, or map[string]string, or some struct type. A sorting algorithm is able to sort any type whose elements are comparable to each other. So if you need, say, a sorted tree for strings, you could sit down and write one. Easy enough!

But what if you need a sorted tree for many different types? The tree datatype comes with a couple of methods like Insert, Find, Delete, etc. If there are N tree methods, and M element types to implement the tree for, you would end up with N x M methods to implement! Sounds like days of tedious, repetitive work.

Can’t we let the compiler do that?

Enter generics

To address this problem, many programming languages have a concept called ‘generics’. The point is to write the code only once, in an abstract form, with opaque type placeholders instead of real types, as in this Java example:

// Java pseudo code

public class SortedTree<E implements Comparable<E>> {
	void insert(E comparableSortTreeElement) {
		//...
	}
}

E is a type placeholder; it can appear in class or interface definitions, as well as in function parameter lists. SortedTree is used by substituting a real type for the placeholder:

// Java pseudo code (again)

SortedTree<String> sortedTreeOfStrings = new SortedTree<String>();
sortedTreeOfStrings.insert("abcde");

These lines instantiate a sorted tree with string elements. The insert method then only accepts strings, and the sort algorithm uses string comparison methods. Had we used Integer instead, like in SortedTree<Integer>, the tree would be a sorted tree of integers instead.

To summarize, generics allow to define classes and functions with type parameters. The type parameters can be restricted to a certain subset (e.g., parameter T must be comparable), but otherwise they are unspecific. The result is a code template that can be applied to different types as the need arises.

The downsides

While generics may come in handy, they also have some strings attached.

1. Performance: Turning a generic code template into actual code takes time, either at compile time or at runtime. Or as Russ Cox stated in 2009:

   The generic dilemma is this: do you want slow programmers, slow compilers and bloated binaries, or slow execution times?

   (The ‘slow programmers’ part refers to having no generics at all, nor any suitable substitute.)

2. Complexity: Generics are not complex per se, but they can become complex when integrated with other language features such as inheritance, or when developers start creating nested generics like,

   // C#
   List<dictionary<string,IEnumerable<HttpRequest>>>
   

   (Thanks to Jonathan Oliver for this nice example), or even seemingly recursive inheritance like,

   // Java
   public abstract class Enum<E extends Enum<E>>
   

   (taken from this Java Generics FAQ by Angelika Langer).

Go has no generics

As we all know, Go has deliberately been designed with simplicity in mind, and generics are considered to add complexity to a language (see the previous section). So along with inheritance, polymorphism, and some other features of the ‘state of the art’ languages at that time, generics were left off from Go’s feature list.

Actually, Go does have some generics–sort of…

There are indeed a few ‘generic’ language constructs in Go.

First, there are three generic data types you can make use of (and probably already did so without noticing):

• arrays
• slices
• maps

All of these can be instantiated on arbitrary element types. For the map type, this is even true for both the key and the value. This makes maps quite versatile. For example, map[string]struct{} can be used as a Set type where every element is unique.

Second, some built-in functions operate on a range of data types, which makes them almost act like generic functions. For example, len() works with strings, arrays, slices, and maps.

Although this is definitely not ’the real thing’, chances are that those ‘internal generics’ already cover your needs.

But what if a project just seems to cry for generics?

At times you might come across a problem where generics would seem to be very handy, if not downright indispensable. What can you do then?

Luckily, there are a couple of options.

1. Review the requirements

Step back and revisit the requirements. Review the technical or functional specification (you should have one). Do the specs really demand the use of generics? Consider that while other languages may support a design that is based on type systems, Go’s philosophy is different:

If C++ and Java are about type hierarchies and the taxonomy of types, Go is about composition. (Rob Pike)

So think of the paradigms that come with Go–most notably composition and embedding–and verify if any of these would help approaching the problem in a way more natural to Go.

2. Consider copy & paste

This may sound like a foolish advice (and if applied improperly, it surely is), but do not hastily reject it.

Here is the point:

Every time you think that you need to create a generic object, do a quick Litmus test: Ask yourself, “How many times would I ever have to instantiate this generic object in my application or library?” In other words, is it worth to construct a generic object when there may only be one or two actual implementations of it? In this case, creating a generic object would just be an over-abstraction.

(At this point, I cannot help but thinking of Joel Spolsky’s witty article on Architecture Astronauts who build abstractions on top of other abstractions until they run out of oxygen. (Small caveat: the article is from 2001. Expect a couple of references to outdated software concepts of which you never may have heard if you are young enough.)) <– Yes, I nested two parens here. So?

An excellent real-life example can be found right in the standard library. The two packages strings and bytes have almost identical API’s, yet no generics were used in the making of these packages (or so I strongly guess).

Remember that this article tries to remain neutral and takes no stand on generics. I don’t want to indicate that copy&paste is better than generics. I only want to encourage you to seek out other options even if they look strange at a first glance.

3. Use interfaces

Interfaces define behavior without requiring any implementation details. This is ideal for defining ‘generic’ behavior:

• Find a set of basic operations that your generic algorithm or data container can use to process the data.
• Define an interface containing these operations.
• To ‘instantiate’ your generic entity on a given data type, implement the interface methods for that type.

The sort package is an example for this technique. It contains a sort interface (appropriately called sort.Interface) that declares three methods: Len(), Less(), and Swap().

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

By just implementing these three methods for a data container (say, a slice of structs), sort.Sort() can be applied to any kind of data, as long as the data has a reasonable definition of ’less than’.

A nice aspect here is that the code of sort.Sort() does not know anything about the data it sorts, and actually it does not have to. It simply relies on the three interface methods Len, Less, and Swap.

There are already a couple of examples in the sort package doc, and the following technique makes heavy use of an empty interface, so I’ll skip the code part and move right on to type assertions.

4. Use type assertions

Generic container types usually do not need to care much about the actual type of their contents. (Except maybe for basic operations like sorting, but we already know a solution for that.) Hence the value can be stored in the container as a ’type without properties’. Such a type is already built into Go: the empty interface, declared as interface{}. This interface has no particular behavior, hence objects with any behavior satisfy this interface.

It is quite easy to build a container type based on interface{}. We only need a way to recover the actual data type when reading elements from the container. For that purpose, Go has type assertions. Here is an example that implements a generic container object.

To keep the code short and concise, the container object is kept super-simple. It features only two methods, Put and Get.