Go 2 Generics: Interfaces are not the right model for type constraints

November 29, 2018

A significant and contentious part of the Go 2 draft generics design is its method of specifying constraints on the types that implementations of generic functions can be used with. There are excellent reasons for this; as an motivating example, I will quote the overview:

[...] In general an implementation may need to constrain the possible types that can be used. For example, we might want to define a Set(T), implemented as a list or map, in which case values of type T must be able to be compared for equality. [...]

The Go 2 generics proposal adopts a method called contracts, which are basically Go function bodies with somewhat restricted contents. From the beginning, one of the most proposed changes in generics is that type constraints should instead be represented through something like Go interfaces. I believe that this would be a mistake and that interfaces are fundamentally the wrong starting point for a model of type constraints.

First, let's observe that we can't really use stock interfaces as they stand as type constraints. This is because stock interfaces are too limited; they only let us say things about a single type and those things have fixed types (whether interfaces or concrete types). Pretty much every interface-based proposal that I've seen immediately expands generic-constraint interfaces to allow for multiple type variables that are substituted into the interface. Axel Wagner's proposal is typical:

type Graph(type Node, Edge) interface {
  Nodes(Edge) []Node
  Edges(Node) []Edge
}

However, I believe that this is still the wrong model. The fundamental issue is that interfaces are about methods, but many type constraints are about types.

An interface famously does not say things about the type itself; instead, it says things about the methods provided by the type. This provides implementations of interfaces with great freedom; in a well-known example, it's possible and even simple for functions to fulfill an interface. Providing interfaces with type variables and so on does not fundamentally change this. Instead it merely expands the range and flexibility of what one can say about methods.

However, a significant amount of what people want to do with generic functions is about the types themselves, and thus wants constraints on the types. The starting example of Set(T) is an obvious one. The implementation does not care about any methods on T; it simply wants to be able to compare T for equality. This is completely at odds with what interfaces want to talk about. Fundamentally, a significant number of generics want to operate on types themselves. There is not just Set(T), there are also often expressed desires like Max(T), Min(T), Contains(), Sort([]T), and so on.

A related issue is that interfaces are about a single type, while type constraints in generic functions are not infrequently going to be about constraints on the relationship between types. The Graph example from the overview is an example; it talks about two separate types, each of which is required to have a single method with a specific type signature:

contract Graph(n Node, e Edge) {
  var edges []Edge = n.Edges()
  var nodes []Node = e.Nodes()
}

In Axel Wagner's proposal, this is modified (as it has to be) into a single type that implements both methods. These two are not the same thing.

An example that combines both problems is the convertible contract from the draft design:

contract convertible(_ To, f From) {
  To(f)
}

This is expressing a constraint about the relationship between two types; From must be convertible into To. There is no single type and no methods in sight, and so expressing this in the interface model would require inventing both.

All of this is a sign that using interfaces to express type constraints is forcing a square peg into a round hole. It is not something that naturally fits the problem; it is simply something that Go already has. Interfaces would be a fine fit in a world where generics were about methods, but that is not the world that people really want; they want generics that go well beyond that. If Go 2 is to have generics, it should deliver that world and do so in a natural way that fits it.

Given my view that contracts are too clever in their current form, I'm not sure that contracts are right answer for type constraints for generics. But I'm convinced that starting from interfaces is definitely the wrong answer.

(This entry was sparked by a discussion with Axel Wagner on Reddit, where questions from him forced me to sit down and really think about this issue instead of relying on gut feelings and excessive hand waving.)

Sidebar: Interfaces and outside types

In their current form, interfaces are limited to applying to existing methods, for good reasons. But if type constraints must be expressed through methods, what do you do when you want to apply a type constraint to a type that does not already implement the method for that constraint? When it is your own package's type, you can add the method; however, when it is either a standard type or a type from another package, you can't.

I think it's clear that you should be able to apply generic functions to types you obtain from the outside world, for example from calling other package's functions or methods. You might reasonably wish to find the unique items from a bunch of slices that you've been given, for example, where the element type of these slices is not one your types but comes from another package or is a standard type such as int.

(It would be rather absurd to be unable to apply Max() to int values from elsewhere, and a significant departure from current Go for the language to magically add methods to int so that it could match type constraints in interfaces.)

Written on 29 November 2018.
« Go 2 Generics: A way to make contracts more readable for people (if not programs)
I've learned that sometimes the right way to show information is a simple one »

Page tools: View Source, Add Comment.
Search:
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Thu Nov 29 01:02:56 2018
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.