Skip to content

Instantly share code, notes, and snippets.

Last active September 29, 2020 22:32
Show Gist options
  • Save zenhack/ad508d08c72fce6df945a49945ad826d to your computer and use it in GitHub Desktop.
Save zenhack/ad508d08c72fce6df945a49945ad826d to your computer and use it in GitHub Desktop.
Go Generics: A Concrete Proposal Re: Using Interfaces Instead Of Contracts.


About a month and a half ago, the Go team released draft designs for changes in Go 2. One of these discusses adding parametric polymorphism ("generics") to Go. Many people have pointed out (and I agree) that the new "contracts" concept has several problems, including:

  1. It does not not encouraging expressing intent, as a contract is just a snippet of code that must type check. I and others worry that this will lead to a lot of under-specified APIs in the wild.
  2. It does not provide a good way to write generic code that works with e.g. both built-in types that are "ordered" (i.e. support < and friends), and user-defined types.
  3. It has too much overlap with interfaces.

Per (3), many people have suggested that we should be using interfaces, instead of adding a new non-orthogonal construct to the language. This document outlines a concrete design for doing just that. It is meant as a starting point for further discussion. A few questions are left unanswered; in particular it also does not provide a solution to problem (2). I will make a brief argument that punting on this is actually better than what the draft design proposes, but it is still unsatisfying.

The Proposal Proper

I'll start with an example:

type Any interface{}

type Ordered(type T Any) interface {
    Less(other T) bool

func Sort(type T Ordered(T))(slice []T) {
    // Code to sort the slice. To compare elements, it calls the Less()
    // method.

To describe the proposal in detail:

  • Syntactically, type parameter lists are identical to value parameter lists, except that (a) they still start with the type keyword, and (b) as with the current draft design, they do not allow variadic arguments.
  • The types specified in the type parameter lists must be interfaces.
  • A generic function may only be called with concrete types which satisfy the interfaces specified for those type parameters.
  • Similarly, a generic type may only be instantiated with concrete types which satisfy the specified interfaces.
  • When type-checking the body of a function whose type parameter list is e.g. (type T1 I1, T2 I2), T1 and T2 are treated as defined types, whose underlying types are themselves (i.e. T1's underlying type is T1 and T2's underlying type is T2), and whose method sets are those of I1 and I2, respectively.
  • Because it will be common to have type parameters with no constraints, a type alias like Any above will be useful; it may make sense to make this a pre-declared identifier.

Note that inside the body, type parameters are not interfaces; they are defined types with a method set specified by an interface. They are guaranteed to implement that interface by construction, but their static type is not that interface. This is a subtle but important point.

Note also that while it is possible for a type T to implement Ordered(T2) for a different type T2, The Sort function is still able to constrain its type parameter T to only implement Ordered(T).

In other respects the proposal is mostly unchanged from the draft design. The remainder of this document explores implications.



First, I'll address the major hole in my proposal that I find unsatisfying: operators. My proposal does not make it possible to abstract over built-in operators like +, *, <, == etc. It would be nice to complement this proposal with something that addresses this issue. However, having delved into the problem I will say that it is more subtle than it first appears, so I will leave it as future work. I hope to write up my thoughts in the future.

Note that, as the draft mentions, it is still possible (although again, unsatisfying) to abstract over e.g. ordering for both primitive integers and user defined types by doing something like:

type Ordered(type T Any) interface {
    Less(other T)

// We define a wrapper type around int, so that we can define methods
// on it:
type OrderedInt int

// The Less method causes OrderedInt to implement the Ordered
// interface.
func (a OrderedInt) Less(b OrderedInt) bool { return a < b }

...and then in generic functions, call .Less() instead of using <.

Contracts as specified in the draft design allow users to write generic functions which abstract over built-in operators like < directly, but then these functions are unable to operate on user-defined types.

There are a few ways I can think of to cope with these consequences of the draft design:

  1. Write each generic function twice, once for the built-in operator and once for the method.
  2. Only write the method based version, and require users to wrap basic types, like the above example.
  3. Only write the operator version, and sacrifice extensibility.

There are trade-offs between each of these, but I worry that having several incompatible approaches to library interfaces with no clear "winner" will make for lots of inconsistencies in our ecosystem.

By contrast, my proposal only enables option (2). While still unsatisfying, it at least does not risk fragmenting the ecosystem.

A common package with wrapper types for each of the built-ins would go some way towards making this more pleasant.


This section explores what a large number of the examples in the draft design would look like given the modifications I have described.

Mutually Referential Type Parameters

The draft design discusses using contracts to capture constraints involving more than one type. There is an example using graphs. It may not be immediately obvious that interfaces can deal with this, or how, so let me sketch how that example might look in the context of my proposal:

// Together, the Node and Edge interfaces capture the `G` contract
// in the draft.

// The node interface is parametrized over the type of its edges:
type Node(type E) interface {
    Edges() []E

// Dually, the edge interface is parametrized over the type of its
// nodes:
type Edge(type N) interface {
    Nodes() (N, N)

// Thi graph's type ties nodes and edges together.
type Graph(type N Node(E), E Edge(N)) struct {

The encoding is slightly non-obvious, but interfaces are sufficient to capture this apparently-tricky case.

Other Examples

There is a laundry list of examples at the end of the draft; In this section I compare each of these to how it might look in the context of my own proposal.

The minimal changes required to capture this example:

// Change 1: The contract `ordered` is replaced with the interface:
type Ordered(type T Any) interface {
    Less(other T)

type orderedSlice(type Ele Ordered(Ele)) []Ele

func (s orderedSlice(Ele)) Len() int           { return len(s) }
// Change 2: less calls the `Less` method, rather than using the `<` operator.
func (s orderedSlice(Ele)) Less(i, j int) bool { return s[i].Less(s[j]) }
func (s orderedSlice(Ele)) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func OrderedSlice(type Ele Ordered(Ele))(s []Ele) {

Note also that sort.Slice can now have the signature:

func Slice(type T Ordered(T))(slice []T) the orderedSlice type is unnecessary, though it may still make sense to have sort.Interface for types that are not actually slices.

How this example might look with interfaces:

package maps

// Equatable captures the notion of equality. Its semantics are similar
// to the notion of "comparable" types in the language specification.
type Equatable(type T) interface {
    Equal(other T) bool

// Replaces the `mappable` contract; our keys will have to implement
// this interface. Note that the `mappable` contract must include the
// `V` type parameter, even though it does not involve the type of
// values at all. it is unnecessarily tightly coupled with the `Keys`
// function. The Mappable interface does not have this problem.
// It likely makes sense to change the name of this interface, as it
// is not tightly bound to maps, and could easily be used in sets, other
// data structures etc.
type Mappable(type T Any) interface {

    // Hash the value. The reason this appears here and not in the
    // contract based design is that the `==` operator is
    // serendipitously defined on the same set of built-in types
    // that can be hashed, so it is possible to gloss over the fact
    // that you can't implement a hash table without a hash function.
    // A binary search tree implementation of maps might require
    // `Orderded` instead.

func Keys(type K Mappable(K), V Any)(m map[K]V) []K {
    // Body of `Keys` is unchanged. Note that we don't actually use the
    // `Mappable` interface's methods here, except in that maps require
    // their keys to be `Mappable`.
Open question: pointer equality and maps

Note that the above translation ignores some subtle details of how built-in maps work in Go today. In particular, it is possible to have:

type Foo struct {
    // ...

type Bar struct {
    // ...

var (
    structMap map[Foo]Bar
    ptrMap map[*Foo]Bar

In this case, structMap and ptrMap do not agree on the equality of keys; structMap compares the Foo structs, while ptrMap compares their addresses. It is not possible to capture this difference in an interface, because it is illegal for both Foo and *Foo to implement a method with the same name.

For a newly defined hash table type, this concern does not come up, but this kind of subtlety is why I have for now punted on trying to fully unify built-in operators with interfaces, though I believe there is value in doing so.

One possible solution which may make sense in a fully clean-slate environment is to make pointers non-comparable, and map[*Foo]Bar equivalent to map[Foo]Bar in terms of notions of equality. This matches the usual rule of being able to call a method of Foo on a value of type *Foo. Note that reference equality can be captured like so:

type EqPtr(type T Any) *T

func (p EqPtr(T)) Equal(other EqPtr(T)) bool {
    return uintptr(unsafe.Pointer(p)) == uintptr(unsafe.Pointer(other))

And then we can use map[EqPtr(Foo)]Bar to capture the original uses of map[*Foo]Bar. However, I worry the upgrade path to this design for code that uses maps with pointer keys is too subtle and error prone. I consider this an open problem.

These examples are unaffected by the modifications to the proposal suggested in this document, except that the type parameter lists need to add Any at the correct locations.

This example is the same, except that instead of the contract comparable, we can use exactly the same interface Mappable as used by the Keys function in a previous example. Note that we cannot do this with the mappable contract.

Similarly to the map/reduce/filter examples, the channel examples are unaffected by the proposal except for the syntactic change.

The containers example can be translated as-is, with the same minor syntactic alterations as for channels and map/reduce/filter. However, it is also possible to use the Ordered interface defined above, as mentioned. It is not clear to me why this was not done with contracts in the example.

Unchanged, except for the minor syntactic changes required as described in examples above.

First, I wish to note that even with the existing draft, defining keyN, cmpN, and MetricN for each size desired is unnecessary; rather than passing multiple arguments, one for each field, we can just have what is now Metric1, call it Metric, and pass it a struct. This example does not feel very well thought out.

Here is the updated example, per the modifications in this document and the use of structs:

package metrics

import "sync"

// We remove the comparable contract, and use Mappable as defined
// above. cmp1 is unnecessary, as we will just use structs (though
// this is orthogonal to the use of contracts vs. interfaces).

type Metric(type T Mappable(T)) struct {
	mu sync.Mutex
	m  map[T]int

func (m *Metric(T)) Add(v T) {
	if m.m == nil {
		m.m = make(map[T]int)

Using the package looks like:

import "metrics"

type Value struct {
    str string
    num int

func (v Value) Equal(other Value) bool {
    return v == other

func (v Value) HashInto(h hash.Hash) {
    // ...

var m = metrics.Metric(Value){}

func F(value Value)
	m.Add(v) // this call is type checked at compile time

This example is unchanged, modulo the usual syntax stuff.


Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment