This is not a proposal, rather outlining a different approach to achieve “generics” in Go. I see a problem with the existing proposal in that it duplicates Go interfaces to some extent. It’s a shame in my opinion, as so far Go has been very careful to be a language with orthogonal (i.e. non-overlapping) features. I am trying to address this problem by adding generics to the language using interfaces.

A “generic” graph package with interfaces

The first non-trivial example of the Go Contract proposal is a graph contract so I am using a similar example. Say we have a graph package defining the following:

package graph

type N interface {
    Edges() []E
}

type E interface {
    Nodes() (N, N)
}

type Graph struct {
    nodes []N
}

func NewGraph(nodes []N) *Graph {
    return &Graph{nodes: nodes}
}

func Neighbors(n N) []N {
    var neighbors []N
    for _, e := range n.Edges() {
        n1, n2 := e.Nodes()
        if n1 != n {
            neighbors = append(neighbors, n1)
        }
        if n2 != n {
            neighbors = append(neighbors, n2)
        }
    }
    return neighbors
}

It is “generic” insofar as it doesn’t rely on a particular implementation of the node N interface and the edge E interface, but of course as Go currently stands it suffers from all the problems that the Go generics proposals are trying to solve. To define these problems more precisely, let’s try to use the package above.

Issues with the graph package

Say we have another package mygraph in which we want to implement a graph using the graph.Graph type but with a specialized type for N and E:

package mygraph

type Node struct {
    edges []*Edge
}

func (n *Node) Edges []*Edge {
    return n.edges
}

type Edge struct {
    n1, n2 *Node
}

func (e *Edge) Nodes (*Node, *Node) {
    return e.n1, e.n2
}

If we want to make use of the graph.Graph type and the graph.Neighbors functions, several problems arise.

  • Type safety. The compiler cannot ensure that only instances of *Node will be in our graph instance, as any type that implements graph.N will satisfy the type constraints.
  • Performance. All our instances of *Node and *Edge will be wrapped in an interface, which will incur a small performance penalty. It also follows from this that there will be no opportunity for the compiler to optimise the code in the graph package for the particular *Node and *Edge implementations of the graph.N and graph.E interfaces.
  • Boilerplate. it will be necessary to convert between interface and concrete type continually in the code using graph, and also between slice types, e.g. []*Node and []graph.N.

Specialization as a means to remedy these issues

We introduce the idea of specialization. A specialization can be seen as a mapping from Go package-level identifiers to compile-time defined values (e.g. types, functions, constants). The new keyword spec will allow us to defined specializations.

// in package mygraph

spec GraphSpec {
    type N = *Node // The identifier N maps to the *Node type
    type E = *Edge // The identifier E maps to the *Edge type
}

This defines the GraphSpec specialization. This specialization can then be applied to package level types, functions, or even whole packages. A specialization is applied by replacing the definitions of the identifiers named in it with the value they are defined as in the target package. Here are some examples, all supposed to be defined in the mygraph package.

// import "graph"

type Graph = GraphSpec(graph.Graph)

This is equivalent to defining

type Graph struct {
    nodes []*Node
}

Or:

func Neighbors = GraphSpec(graph.Neighbors)

This is equivalent to defining

func Neighbors(n *Node) []*Node {
    var neighbors []*Node
    for _, e := range n.Edges() {
        n1, n2 := e.Nodes()
        if n1 != n {
            neighbors = append(neighbors, n1)
        }
        if n2 != n {
            neighbors = append(neighbors, n2)
        }
    }
    return neighbors
}

Or even perhaps

GraphSpec(graph)

This would be equivalent to “reimplementing” the whole of the graph package in he current mygraph package, so we would have the following defined in the mygraph package:

type Graph struct {
    nodes []Node
}

func NewGraph(nodes []*Node) *Graph {
    // ...
}

func Neighbors(n *Node) []*Node {
    // ...
}

To be continued!

I’m hoping to have some time to think this trough at some point! If you think this is a promising idea, please get in touch with me.