Contracts — Draft Design presents a draft proposal for adding generic types and functions to the Go programming language, using contracts to specify the behavior required of type parameters.
This document discusses two topics.
First, suppose generic types and functions are added to Go as in the contracts proposal, but without contracts. When a generic function f has a type parameter T, the only operations f can perform on values of type T are the operations that are available on all types. Is there a reasonable way to write generic code in these circumstances, with no other additions to the language? The answer seems to be
- Yes, this is quite doable.
- And it works well with both built-in and user-defined types.
- But it is verbose.
- And it is likely slower than code generated under the contracts proposal.
Second, can we extend Go in ways that improve the code from the first topic, making it less verbose and more efficient?
We assume that Go is extended to allow generic types and functions, as discussed in the contracts proposal, but without contracts. There are two additional rules.
If an instantiation of a generic type or function creates an illegal type, then that instantiation is not allowed. Under the contracts proposal, the type or function's contract would prevent such instantiations, but we are not using contracts, so we need this rule.
type Set(type T) map[T]struct{}
var s1 Set(int) // ok
var s2 Set([]int) // illegal
func Unique(type T)(list []T) []T {
var m := make(map[T]bool)
for _, t := range list {
m[t] = true
}
var result []T
for t := range m {
result = append(result, t)
}
return result
}
fmt.Println(Unique(make([]int, 5))) // ok; can make map[int]bool
fmt.Println(Unique(make([][]int, 5))) // illegal; can't make map[[]int]boolWhen a generic function manipulates a value of unknown type, it may only use operations that are applicable to all types.
func Min(type T)(a, b T) T {
if a < b { // illegal; T might not have the < operator
return a
}
return b
}
func Min(type T)(a, b T, less func(T, T) bool) T {
if less(a, b) { // this is ok
return a
}
return b
}Suppose we want a function to add the elements of a slice. We can't write the obvious
func SumSlice(type T)(s []T) T {
var sum T
for _, t := range s {
sum += t // illegal; T might not have the + operator
}
return sum
}One traditional way to do this uses an adaptor function passed as an additional parameter.
func SumSlice(type T)(s []T, add func(T, T) T) T {
var sum T
for _, t := range s {
sum = add(sum, t)
}
return sum
}This approach works, but can be quite verbose. If a generic function needs five operations on its type parameters, then each call to the function will have to supply five additional function arguments. And all those adaptor functions have to be written somewhere and organized appropriately.
We suggest instead using interfaces to express the operations needed.
type Adder(type T) interface {
Zero() T
Add(T, T) T
}
func SumSlice(type T)(s []T, a Adder(T)) T {
sum := a.Zero()
for _, t := range s {
sum = a.Add(sum, t)
}
return sum
}
type IntAdder struct {}
func (IntAdder) Zero() int { return 0 }
func (IntAdder) Add(a, b int) int { return a + b }
var ints []int
fmt.Println(SumSlice(ints, IntAdder{}))
type BigIntAdder struct {}
func (BigIntAdder) Zero() *big.Int { return nil }
func (BigIntAdder) Add(a, b *big.Int) *big.Int { return big.NewInt(0).Add(a, b) }
var bigints []*big.Int
fmt.Println(SumSlice(bigints, BigIntAdder{}))Unlike many other proposals, it is not expected that the type T should implement the interface Adder(T). Instead, T is used only in the parameter and result types of the Adder(T) methods. This allows us to create an Adder(T) when T is a built-in type. For example, IntAdder above implements Adder(int).
When a type XAdder implements Adder(X), it will usually be true that the methods of XAdder do not use the content of the XAdder receiver, so XAdder can be defined as struct{}, as in the examples above. However, there can be cases in which other definitions are useful.
type ModularAdder uint
func (ModularAdder) Zero() uint { return 0 }
func (m ModularAdder) Add(a, b uint) uint { return (a + b) % uint(m) }
var modints []uint
fmt.Println(SumSlice(modints, ModularAdder(49999)))We can also create adaptor types and objects that describe the behaviors of the types we use with generic functions.
type Float64Adaptor struct{}
func (Float64Adaptor) Zero() float64 { return 0.0 }
func (Float64Adaptor) One() float64 { return 1.0 }
func (Float64Adaptor) Add(a, b float64) float64 { return a + b }
func (Float64Adaptor) Sub(a, b float64) float64 { return a - b }
func (Float64Adaptor) Mul(a, b float64) float64 { return a * b }
func (Float64Adaptor) Div(a, b float64) float64 { return a / b }
func (Float64Adaptor) AddAssign(a *float64, b float64) { *a += b }
func (Float64Adaptor) SubAssign(a *float64, b float64) { *a -= b }
func (Float64Adaptor) MulAssign(a *float64, b float64) { *a *= b }
func (Float64Adaptor) DivAssign(a *float64, b float64) { *a /= b }
func (Float64Adaptor) Equal(a, b float64) bool { return a == b }
func (Float64Adaptor) NotEqual(a, b float64) bool { return a != b }
func (Float64Adaptor) Less(a, b float64) bool { return a < b }
func (Float64Adaptor) LessOrEqual(a, b float64) bool { return a <= b }
func (Float64Adaptor) Greater(a, b float64) bool { return a > b }
func (Float64Adaptor) GreaterOrEqual(a, b float64) bool { return a >= b }
// And the same again, with 64 everywhere replaced by 32Now we can use these adaptors to call SumSlice without having to create helper types for the calls:
var f32 []float32
var f64 []float64
fmt.Println(SumSlice(f32, Float32Adaptor{}))
fmt.Println(SumSlice(f64, Float64Adaptor{}))This is the main advantage of this programming style: we don't need helper types for each possible call. Instead, each type parameter of a generic function uses an interface to express the operations required on that type parameter, and each concrete type uses a separate adaptor type to express the operations it provides.
type Order(type T) interface {
Less(T, T) bool
}
func Min(type T)(o Order(T), first T, rest ...T) T {
min := first
for _, x := range rest {
if o.Less(x, min) {
min = x
}
}
return min
}
func Max(type T)(o Order(T), first T, rest ...T) T {
max := first
for _, x := range rest {
if o.Less(max, x) {
max = x
}
}
return max
}
fmt.Println(Min(Float64Adaptor, 1.5, 3, -17))type Coefficient(type C) interface {
Adder(C) // Embedding
Mul(C, C) C
}
type Polynomial(type C) []C
func (p Polynomial(C)) Eval(x C, c Coefficient(C)) C {
y := c.Zero()
for n := len(p) - 1; n >= 0; n-- {
y = c.Add(p[n], c.Mul(x, y))
}
return y
}
func (p Polynomial(C)) Add(q Polynomial(C), c Coefficient(C)) Polynomial(C) {
r := make(Polynomial(C), Max(IntAdaptor{}, len(p), len(q)))
for n := 0; n < len(p) && n < len(q); n++ {
r[n] = c.Add(p[n], q[n])
}
if len(p) < len(q) {
copy(r[len(p):], q[len(p):])
} else {
copy(r[len(q):], p[len(q):])
}
return r
}
func (p Polynomial(C)) Mul(q Polynomial(C), c Coefficient(C)) Polynomial(C) {
if len(p) == 0 || len(q) == 0 {
return nil
}
r := make(Polynomial(C), len(p) + len(q) - 1)
for n := range r {
r[n] = c.Zero()
}
for i, pi := range p {
for j, qj := range q {
c.AddAssign(&r[i+j], c.Mul(pi, qj))
}
}
return r
}And we can create polynomials whose coefficients are themselves polynomials. This shows the construction of an adaptor for a user-defined type.
type PolynomialAdaptor(type C) struct{}
func (PolynomialAdaptor(C)) Zero() Polynomial(C) { return nil }
func (PolynomialAdaptor(C)) Eval(p Polynomial(C), x C, c Coefficient(C)) C {
return p.Eval(x, c)
}
func (PolynomialAdaptor(C)) Add(p, q Polynomial(C), c Coefficient(C)) Polynomial(C) {
return p.Add(q, c)
}
func (PolynomialAdaptor(C)) Mul(p, q Polynomial(C), c Coefficient(C)) Polynomial(C) {
return p.Mul(q, c)
}
var pp Polynomial(Polynomial(float64))
var px Polynomial(float64)
fmt.Println(pp.Eval(px, Float64Adaptor{}))type SliceAdaptor(type T) struct{}
func (SliceAdaptor(T)) Len(s []T) int { return len(s) }
func (SliceAdaptor(T)) At(s []T, n int) T { return s[n] }
func (SliceAdaptor(T)) SetAt(s []T, n int, t T) { s[n] = t }
func (SliceAdaptor(T)) PtrAt(s []T, n int) *T { return &s[n] }
func (SliceAdaptor(T)) Slice(s []T, low, high int) []T { return s[low:high] }
func (SliceAdaptor(T)) CapSlice(s []T, low, high, cap int) []T { return s[low:high:cap] }
func (SliceAdaptor(T)) Make(n int) []T { return make([]T, n) }
func (SliceAdaptor(T)) MakeCap(n, m int) []T { return make([]T, n, m) }
func (SliceAdaptor(T)) Range(s []T, f func(int, T)) { for n, t := range s { f(n, t) } }
func (SliceAdaptor(T)) BreakableRange(s []T, f func(int, T) bool) {
for n, t := range s {
if !f(n, t) { break }
}
}See also the example in the contracts proposal.
type ConstList(type L, T) interface {
Len(L) int
At(L, int) T
}
type List(type L, T) interface {
ConstList(L, T) // embedding
SetAt(L, int, T)
}
func SortSlowly(type L, T)(list L, l List(L, T), o Order(T)) {
for i := l.Len(list) - 1; i > 0; i-- {
for j := 0; j < i; j++ {
lj := l.At(list, j)
lj1 := l.At(list, j + 1)
if o.Less(lj1, lj) {
l.SetAt(list, j, lj1)
l.SetAt(list, j + 1, lj)
}
}
}
}
type StdSorter(type L, T) struct {
list L
l List(L, T)
o Order(T)
}
func (ss StdSorter(L, T)) Len() int { return ss.l.Len(ss.list) }
func (ss StdSorter(L, T)) Less(i, j int) bool {
return ss.o.Less(ss.l.At(ss.list, i), ss.l.At(ss.list, j))
}
func (ss StdSorter(L, T)) Swap(i, j int) {
li, lj := ss.At(ss.list, i), ss.At(ss.list, j)
ss.l.SetAt(ss.list, i, lj)
ss.l.SetAt(ss.list, j, li)
}
func StdSort(type L, T)(list L, l List(L, T), o Order(T)) {
sort.Sort(StdSorter{ list, l, o })
}
func SortSlice(type T)(s []T, o Order(T)) {
StdSort(s, SliceAdaptor(T){}, o)
}
type LessAdaptor(type T) struct {
Less func(T, T) bool
}
func (l LessAdaptor(T)) Less(a, b T) bool { return l.Less(a, b) }
func SortSliceBy(type T)(s []T, less func(T, T) bool) {
SortSlice(s, LessAdaptor{ less })
}Note the difference between StdSorter here and Polynomial above. StdSorter includes the adaptor objects it needs; Polynomial assumes each function call will provide a suitable adaptor, and that the same adaptor will be provided in each call. Which strategy is best will depend on the circumstances.
See the example in the contracts document.
type MapAdaptor(type K, V) struct{}
func (MapAdaptor(K, V)) Len(m map[K]V) int { return len(m) }
func (MapAdaptor(K, V)) At(m map[K]V, k K) V { return m[k] }
func (MapAdaptor(K, V)) GetAt(m map[K]V, k K) (V, bool) {
v, have := m[k]
return v, have
}
func (MapAdaptor(K, V)) SetAt(m map[K]V, k K, v V) { m[k] = v }
func (MapAdaptor(K, V)) Range(m map[K]V, f func(K, V)) { for k, v := range m { f(k, v) } }
func (MapAdaptor(K, V)) BreakableRange(m map[K]V, f func(K, V) bool) {
for k, v := range m {
if !f(k, v) { break }
}
}
type Ranger(M, K, V) interface {
Len(M) int
Range(M, f func(K, V))
}
func Keys(type M, K, V)(m M, r Ranger(M, K, V)) []K {
list := make([]K, 0, r.Len(m))
r.Range(m, func(k K, v V) {
list = append(list, k)
})
return list
}
var m map[int]string
fmt.Println(Keys(m, MapAdaptor(int, string){}))Suppose we want to add the elements of a slice, but the element type might be large enough to hold the sum, so we need to use a different type for the sum.
func SumSlice2(type T, S)(slice []T, convert func(T) S, a Adder(S)) S {
sum := a.Zero()
for _, t := range slice {
sum = a.Add(sum, convert(t))
}
return sum
}
var bytes []byte
fmt.Println(SumSlice2(bytes, func(b byte) int { return int(b) }, IntAdaptor{})This illustrates that conversion between types is best handled through a separate function. We can't expect the ByteAdaptor type to include a method to convert a byte to an int.
Code using this approach will be quite a bit more verbose than corresponding code using contracts.
- Each concrete type needs an adaptor written.
- Each call to a generic function requires additional arguments.
- The body of a generic function, instead of directly using methods and operators, must call methods of the adaptor interfaces.
Also, adaptor interfaces must be written to express what each generic function requires from its type parameters. These should be roughly equivalent to contracts, so do not make this code more verbose than code using contracts.
In exchange for this verbosity, we are easily able to write generic functions operating on both built-in and user-defined types.
This section is pure speculation.
There are probably two main alternatives for compiling a generic function when using contracts.
- Compile a single version applicable to all combinations of type parameters.
- Compile a separate version for each unique combination of type parameters.
For the adaptor programming style described here, there seem to be three alternatives.
- Compile a single version applicable to all combinations of type parameters.
- For each unique combination of type parameters, compile a version of the function that works with any adaptors for those type parameters.
- For each unique combination of type parameters and adaptors, compile a version of the function.
Contracts alternative 1 and adaptors alternative 1 seem roughly equivalent, using function pointers or interfaces to specify how to perform operations. Adaptors have an additional, unused, value: the adaptor itself. So adaptors might be marginally slower.
Contracts alternative 2 and adaptors alternative 3 also seem equivalent, with operations going directly to built-in operators or type parameter method calls. However, it is unreasonable to expect the compiler to implement adaptors alternative 3.
Adaptors alternative 2 retains a significant amount of indirection, so will probably be slower than contracts alternative 2.
The use of adaptors described above is a programming style, not an extension to the language. So even if contracts are implemented, these adaptors can still be used. It is not clear what programmers would choose to do in this event.
Most operations in Go involve one type that constrains which types are valid for the other operands. For example,
- in an index operation, the slice, array, or map being indexed
- the receiver type in a method call
- either operand type from an arithmetic operation
These operations can be properly handled by type adaptors as described above.
However, some operations can involve two types in such a way that neither type clearly constrains the other type. These are
- conversions
- type assertions
- equality comparisons
These operations are probably best handled with simple adaptor functions, as in Adding slice elements, take 2.
Equality comparisons are a special case. The adaptor for a type T can include a method Equal(T, T), but a separate adaptor function should be used when comparing values of two different types.
What would we do if we were willing to extend the language in order to support this programming style? (Yes, a large assumption, but just suppose...).
The first target should be the default adaptor types. These are almost entirely predictable from the base types, so let's have the compiler generate them. For the purposes of this dicussion, given a type X, we will assume the syntax adaptortype(X) for the adaptor type of X, and adaptor(X) for an object of this type. adaptortype(X) will always be defined as struct{}, so adaptor(X) is just shorthand for adaptortype(X){}.
With this, we can use SumSlice from above this way:
var ints []int
fmt.Println(SumSlice(ints, adaptor(int)))This is essentially the same as before, but now we don't have to write the IntAdaptor type and its methods.
Here we suggest rules for the compiler to use in generating a type adaptor for a type X. These fall into two categories, rules pertaining to methods, and rules pertaining to operators.
adaptortype(X) should have one method for each method of X or *X, with the corresponding type X or *X prepended to the argument list. This will call the original method.
If X is an interface type, then *X has no methods, so only the methods of X are considered.
type X interface {
Foo(int)
}
// Pseudo-code generated by the compiler
type adaptortype(X) struct{}
func (adaptortype(X)) Foo(x X, i int) { x.Foo(i) }Otherwise, methods of both X and *X are considered.
type X int
func (X) Foo(float64, int) uint { ... }
func (*X) Bar() string { ... }
func (X) Add(X) X { ... }
// Pseudo-code generated by the compiler
type adaptortype(X) struct{}
func (adaptortype(X)) Foo(x X, f float64, i int) uint { return x.Foo(f, i) }
func (adaptortype(X)) Bar(x *X) string { return x.Bar() }
func (adaptortype(X)) Add(x, y X) X { return x.Add(y) }
// The methods of this X are also methods of *X; but **X has no methods
type adaptortype(*X) struct{}
func (adaptortype(*X)) Foo(x *X, f float64, i int) uint { return x.Foo(f, i) }
func (adaptortype(*X)) Bar(x *X) string { return x.Bar() }
func (adaptortype(*X)) Add(x *X, y X) X { return x.Add(y) }There are special rules corresponding to the built-in operations. For example, if X has the + operator, then adaptortype(X) has a method
func (adaptortype(X)) Add(a, b X) X { return a + b }However, the method rules take priority; if X also has a method named Add, that is used to generate adaptortype(X).Add.
Here are some more examples of methods that could be generated.
// type X int
func (adaptortype(X)) AddAssign(a *X, b ) { a += b }
func (adaptortype(X)) Equal(a, b X) bool { return a == b }
// type M map[string]int
func (adaptortype(M)) At(m M, s string) int { return m[s] }
func (adaptortype(M)) Range(m M, f func(string, int)) {
for k, v := range m { f(k, v) }
}It might be useful to have adaptors include some methods other than those corresponding to the methods and operations of the base type. For example, Float64Adaptor above included Zero and One methods. An adaptor for an integer type might usefully have MinValue and MaxValue methods. But the rules above won't create these methods; what can we do?
For user-defined types, we can simply give the type a method whose receiver is not used.
type MyUint uint
func (MyUint) MinValue() MyUint { return 0 }There will now be an adaptortype(MyUint).MinValue method. This construction is not possible for the built-in types, but there could be a few standard methods the compiler generates in adaptors for built-in types.
Another option is to use type embedding to create a new adaptor type with additional methods.
type MinUintAdaptorType {
adaptortype(uint)
}
func (MinUintAdaptorType) MinValue() uint { return 0 }
var MinUintAdaptor MinUintAdaptorType{}Yet another option is to simply not have these additional methods; workarounds surely exist.
If the compiler can generate default adaptor types as discussed above, then we have the option of extending the syntax for generic functions to indicate that adaptor arguments are optional. For example, we might put a semi-colon in the argument list, indicating that the following arguments are optional.
func Sort(type L, T)(list L; o Order(T), l List(L, T)) { ... }
var ints []int
// The following three calls are equivalent
Sort(ints; adaptor(int), adaptor([]int))
Sort(ints; adaptor(int))
Sort(ints)
type CustomAdaptor struct{}
func (CustomAdaptor) Less(a, b int) bool { return fmt.Sprint(a) < fmt.Sprint(b) }
// The following two calls are equivalent
Sort(ints; CustomAdaptor{}, adaptor([]int))
Sort(ints; CustomAdaptor{})The rule would be that each argument type after the semi-colon must be an instantiation of a generic interface type; the default value for that argument is the default adaptor for the first type argument of the interface type. Also, when one generic function calls another, it must explicitly pass the adaptors required by the called function.
func Foo(type L, T)(list L; o Order(T), l List(L, T)) {
Sort(list; o, l)
// Sort(list) would be illegal,
// because adaptortype(L) and adaptortype(T) have no methods
}This syntax clearly marks off the function parameters which are expected to be adaptor types. So it might now be reasonable for the compiler to produce a separate version of the function for each combination of type arguments, using the default adaptors for those types. This should yield similar runtime speed to that which could be obtained with contracts.
As a variant on this, we might want to rule that when there is a default value for an adaptor interface, then only that default may be used. The default may not be overridden with a custom adaptor. In that case, a more suitable syntax might be to put the adaptors with the type parameters, separated by a colon.
func Sort(type L, T : o Order(T), l List(L, T))(list L) { ... }
var ints []int
// Now there's only one way to do this call.
// It implicitly uses o = adaptor(int) and l = adaptor([]int).
Sort(ints)
// I lied. You can also do this. But it doesn't gain you anything here.
Sort([]int, int)(ints)But we would need additional logic to specify what adaptor to use when one generic function calls another.
We might try to make the bodies of generic functions a little bit shorter and clearer by allowing methods of the adaptor interfaces to be called through what appear to be calls of methods on the parameter types. For example,
func SumSlice(type T)(s []T, a Adder(T)) T {
sum := a.Zero()
for _, t := range s {
sum = sum.Add(t) // Equivalent to sum = a.Add(sum, t)
}
}Any method of Adder(T) whose first parameter type is T can be used as if were a method of T; methods of Adder(T) with first parameter type *T can be called as if they were methods of *T. Of course, this only works if the choice of adaptor interface to use is unambiguous or somehow indicated by syntax.
I don't recommend this. The improvement seems too small.
The important point here is that very basic generics, without contracts, provide us a great deal of flexibility in writing code, even if the code is verbose. Furthermore, the amount of code required scales as the sum of the number of generic functions and the number of types (and their methods) that might be passed to those functions, not as the product of those two numbers.
This suggests that those very basic generics, without contracts, might be useful as a first step in implementing generics, so that people may experiment before deciding on the next steps.
This also sets up minimal expectations for generics. Any approach to be considered should either provide more flexibility than the adaptors discussed in this document or yield shorter and clearer code.
- 2018/10/16: Initial version.
- 2018/10/16: Bug fix in Float64(32)Adaptor: can't assign 0.0 or 1.0 to a variable whose type is a type parameter.