Zombie Zen

Ross's Blog

Why Go Does Not Need Generics

Posted on

(This developed from a thread with some other Cal Poly students discussing Go.)

One of the frequently asked questions about Go is why are there no generics in the language. It’s a fair point from the perspective of other OOP languages, but idiomatic Go code un-asks the question.

First, it is important to understand how interfaces work in Go. The gist is that interfaces use virtual method lookups, but retain the underlying type, so a conversion back to the original type is still type-safe. An empty interface (interface{}) works as a type-safe equivalent of C’s void*: you can put any type inside of an empty-interface variable, and then you can un-box it later.

The simplest way to define a linked list is through the empty interface: interface{}.

type Node struct {
    Value interface{}
    Next *Node

And indeed, this is how the container/list package package works, give or take some complexity. However, my argument is that this is the wrong way to do this. It requires an explicit boxing/un-boxing hit for every access, and this is where (I think) most of the call for generics comes from. There’s a much more idiomatic way to do this. My two case studies here are the sort package and the container/heap package from the standard library.

We start with sort, which defines an interface, sort.Interface:

package sort

func Sort(data Interface)

type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less returns whether the element with index i should sort
    // before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)

This may not strike you as a generic container, but that is precisely the point. You can – with a bit of boilerplate – create a type that wraps a typed slice that implements sort.Interface. Thus, the algorithm can work on any type and only works uses indices. This is much cheaper than boxing/unboxing on access.

The second example is container/heap:

package heap

func Init(h Interface)
func Pop(h Interface) interface{}
func Push(h Interface, x interface{})
func Remove(h Interface, i int) interface{}

type Interface interface {
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.

Admittedly, there is a bit more boxing/un-boxing going on here, but the idea is still similar. We now have a data structure that requires very few box/unbox operations (two per push/pop). It is important to note that this is still type-safe.

You could implement a binary tree structure similarly:

package tree

func Search(root *Node, val interface{}) *Node

type Node struct {
    Index       int
    Left, Right *Node

type Interface interface {
    Len() int
    Less(i, j int) bool
    Push(x interface{})
    Pop() interface{}

The Search function would push the val interface and use it for comparisons against the values stored in the tree, then pop it once finished. Admittedly, this isn’t the prettiest interface, but it works in a pinch. It works out to be only one box/un-box round-trip.

As we’ve seen, by “flipping” around the algorithms and separating them from the data structures using interfaces, we can still reap the benefits of generic containers from other languages.

I’m finishing up my game, “Urge to Merge”, for my Intro to Computer Graphics course. This is the first time I’ve worked with OpenGL shaders; I’m pleased with the results. These are screenshots from the game.

Something about the simplicity of the characters made me laugh even by the fourth panel.

This made me chuckle more than it should have. Hooray for memes!


This is a VT220 serial console (circa 1983) set up as a terminal for my Mac Pro (circa 2010), a nerdy dream I’ve had for a long time that I finally made a reality yesterday.

Some quick history: in the early days of office computers, it was rare that you would actually have one on your desk. Instead there might be a central mainframe (running Unix) and everyone would have a terminal that connected to it over a long serial cable or modem connection. One computer, many users.

The terminal has a keyboard and monitor, but it’s not a full computer and worthless without the mainframe. It’s more like a teletype machine, all it can do is display the text sent to it (like a paperless printer) and send text back. It doesn’t have any knowledge of pixels or colors or graphics of any kind.

In modern times we don’t have mainframes anymore, but Unix is more prevalent than ever. It runs on the servers delivering this page and the iPhone in your pocket. For developers and power users the command line has never gone away, but instead of a dedicated hardware serial console we have Terminal.app (with translucent backgrounds and anti-aliased fonts). The software is just emulating the old hardware, though. The protocols haven’t changed much in 30 years. The Unix underpinnings of OS X still have all the stuff required to use a real serial terminal, it’s just no one actually does it (well, almost no one).

I’ve always thought those old terminals were beautiful, and I’m not the only one—there’s a Mac app called Cathode that does a convincingly wonderful job simulating vintage terminals, using OpenGL to degrade things into a nice analog haze. But it’s not quite the same as the real thing…

Hardware terminals regularly crop up on eBay for around $100. They’re actually still used in a lot of places (old warehouse systems, supermarkets, banks) and there are still companies that support and refurbish them. Back at Vimeo we discovered one abandoned in a server closet when we moved into the office. Finding one isn’t a problem, the main challenge is stringing together the right adapters to use an ancient serial port with modern USB.

My biggest source of information getting this going was Paul Weinstein’s post about setting up an Apple IIc as a terminal for his Mac mini (which is similar, but not quite the same since the IIc still has to emulate the terminal in software). I got the same USB-to-serial adapter, a Keyspan USA-19HS ($27), which has Mac drivers that I can happily confirm work well with 10.7 Lion. I also needed a null modem cable ($7) and 25-pin female/female converter ($4) to connect it to my VT220.

At first I used the same method as Paul to get it working, gluing together the terminal and OS with a utility called screen. As Paul notes, this is less than desirable. It still requires you to open a software terminal to make the connection, and you’re still operating through a layer of emulation. On most Unixes you can simply add a line to /etc/ttys and everything just works via getty, but apparently this has been disabled in OS X since 10.5.

Eventually I found this page, which explains the problem and how to fix it. After adding a line in /etc/gettytab to manually set the terminal type to vt220-8bit everything works perfectly! A real hardware terminal directly connected the old fashioned way, with no emulation. Awesome.

If this is something you want to attempt yourself please drop me a line; I learned a lot about how terminals work over the last couple weeks and the final result is quite satisfying, a soft amber glow and one less window on my desktop. It’s also a nice reminder that we didn’t get to where we are overnight, user interfaces and software development have been evolving in an unbroken chain for a long time and some of the old ideas are so solid that they persist 30 years later. Why not use the proper hardware?

This is too awesome! I don’t think I would be quite committed enough to do it myself, though.