Golang Diaries: Generics

[This fragment is available in an audio version.]

My coding time this year has been invested in Quamina, an event-filtering library implemented in Go. Just in the last couple of weeks I spotted an opportunity to bring Go’s shiny new generics to bear, and not just anywhere, but for a central data structure. I got good results, but the process was sort of painful; I kept trying things that looked like they ought to work but didn’t. I’m sharing this tour through that experience because I’m a reasonably competent programmer with mainstream tastes and if I hit these bumps in the road others probably will too.

[The title of this piece suggests it’s a continuation of two Golang Diaries entries I wrote back in 2013 when I was first discovering the language. Why not? I have at least one more in mind.]

Why generics? · Quamina is all about building and running finite automata. To do this you need a table-like data structure that represents states and the transitions between them. Quamina uses both deterministic and non-deterministic finite automata, DFAs and NFAs for short. The only real difference is that a transition from a DFA state is always to one other state; in an NFA you can have transitions to multiple others, in practice to a list of states.

I noticed that the NFA and DFA tables were almost identical, as was the code that that built them and stepped through them while matching. I had recently read When To Use Generics on the Go Blog, which has sections entitled:

• When using language-defined container types,

• General purpose data structures, and

• Implementing a common method.

Check, check, and check. Then in the final section, One simple guideline, it says “If you find yourself writing the exact same code multiple times, where the only difference between the copies is that the code uses different types, consider whether you can use a type parameter.” Check. So, off I went. Later that week it was all working. But along the way I yelled at the computer more than I’d have expected.

I don’t recommend diving into the Quamina source at this point, there’s too much else to explain. So…

Back to basics · To help illustrate my bumpy road, I made a toy GitHub project with a file called typing.go. It defines a genericized container type:

type container[S comparable] struct {
  label string
  list  []S
}

And one associated function:

func (c *container[S]) size() int {
  return len(c.list)
}

Now I’m going to define a boring struct type:

type fish struct {
  species string
}

Strong typing oops · Here’s where things started going off the rails. I offered the following and neither the IDE nor the compiler complained:

type fishTank container[fish]

“Wow”, I told myself, “now I have a strongly-typed container, so I can write nice clean code without any generics cruft!” On that basis, I defined another function:

func (t *fishTank) fishCount() string {
  return fmt.Sprintf("How many fishies? %d!", t.size())
}

Ouch! The Goland IDE said Unresolved reference 'size' and the compiler (via go build) said t.size undefined (type *fishTank has no field or method size).

It seems to me like fishTank should have a size() method? After all, it’s a container, and the compiler seemed to be OK with me saying so, and container has size().

Note: Dear reader, as I proceed through this narrative, if you are Go-erudite it will doubtless occur to you that:

1. There’s a better (and supported) way to do what I’m trying to do.

2. I shouldn’t want to do what I’m trying to do.

I welcome the first type of remark; one goal of writing this piece is to provoke them. As for the second, I really don’t care what what you think I should want. As I said above, my hypothesis is that enough others will also want to do this type of thing that the issue’s worth addressing.

Update, the morning after (see #1 above) · So there is a way to accomplish what I want, like so:

type fishTank struct {
  container[fish]
}

Thanks to the commenters below and over at YCombinator for the guidance. It’s not obvious to me that this is “better”, though. Um, would it be rude to say that it’s counter-intuitive and requires understanding things that ordinary folks in the code mines shouldn’t have to? But OK, it works, and I’m going to go back and make some pieces of Quamina a little more readable.

Fat fish · Let’s enrich that fish type a bit:

type dataRichFish struct {
  species string
  datum   [8]float64
}

Now, suppose this: First of all, not all fish have that datum material available. Second, this app goes into production and we start to track a whole lot of fish, millions and millions. And people start yelling at us to use less memory. Well, Go’s interface mechanism should make this easy:

type flexibleFish interface {
  getSpecies() string
  getDatum()   [8]float64
}
func (f *dataRichFish) getSpecies() string {
  return f.species
}  
func (f *dataRichFish) getDatum() [8]float64 {
  return f.datum
}

var dataNotProvided [8]float64
type stingyFish struct {
  species string
}
func (f *stingyFish) getSpecies() string {
  return f.species  
}
func (f *stingyFish) getDatum() [8]float64 {
  return dataNotProvided
}

See how it works? A flexibleFish can either have an attached datum or not and if it doesn’t, it signals the absence by returning the static global dataNotProvided.

Now let’s put those flexibleFish in the tank…

type flexibleTank container[flexibleFish]

Ouch! Quoth the compiler: flexibleFish does not implement comparable.

So interfaces aren’t comparable? Hmm, but I can make(map[interface{}]int) and don’t you have to be comparable to be a map key? I guess an interface could be implemented by something whose type was []int, which isn’t comparable. OK, the shallowness of my understanding is showing here.

But, suppose there was a way to promise that a type was comparable. It looks like there is, at least in Go 1.18. Let’s try it.

type comparableFlexibleFish interface {
  comparable
  getSpecies() string
  getDatum()   [8]float64
}

The compiler seems to be OK with that. So, one last step…

type comparableFlexibleFishTank container[comparableFlexibleFish]

Ouch! Goland: interface includes constraint elements, can only be used in type parameters. Compiler: interface is (or embeds) comparable. I understand them about equally well. [Narrator: He’s equally baffled.]

I guess I am skating pretty far outside the lines here? But I think the intent of that comparable in the type declaration is perfectly clear. This thing implements the listed methods and promises to be comparable. So if I try to claim something is a comparableFlexibleFish and it’s implemented the right methods but isn’t comparable, the compiler can stop me with a helpful error.

Once again, maybe I shouldn’t want to do these things, but I do.

Take-aways · The performance was great, no detectable slowdown. [Note this is not always true and if you care, you should really follow that link. But get a large cup of coffee first.]

And I threw away a whole bunch of duplicative code, which made me happy.

When generics arrived in Java, I hated them. I thought the ratio of pain removed to complexity added was way too low. I don’t hate Go’s generics, which is actually pretty strong testimony given that I spent the best part of a couple of days fighting all the stuff described above.

But, my guess is the Go generics story is isn’t finished yet.

Contributions