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:
- 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.
- 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. - 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.
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
typekeyword, 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),T1andT2are treated as defined types, whose underlying types are themselves (i.e.T1's underlying type isT1andT2's underlying type isT2), and whose method sets are those ofI1andI2, respectively. - Because it will be common to have type parameters with no constraints,
a type alias like
Anyabove 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:
- Write each generic function twice, once for the built-in operator and once for the method.
- Only write the method based version, and require users to wrap basic types, like the above example.
- 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.
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.
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) {
sort.Sort(orderedSlice(Ele)(s))
}Note also that sort.Slice can now have the signature:
func Slice(type T Ordered(T))(slice []T)...so 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 {
Equatable(T)
// 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.
HashInto(hash.Hash)
}
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`.
}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.
map/reduce/filter (https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md#map_reduce_filter)
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) {
m.mu.Lock()
defer m.mu.Unlock()
if m.m == nil {
m.m = make(map[T]int)
}
m[v]++
}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
}list transform (https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md#list-transform)
This example is unchanged, modulo the usual syntax stuff.
Unchanged.