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.
The current document sketches a simple extension to that proposal, which would permit writing generic functions whose type parameters could be either built-in types or user-defined types deliberately designed to be similar to the built-in types.
Consider a generic function, say
func Sum(type T)(list []T) T // Returns the sum of the elements of list
Suppose the intent is that the type parameter T can be either a type built in to the language, say any numeric type, or a user-defined type with similar semantics, such as an arbitrary precision integer type defined as a wrapper around *big.Int from the math/big package.
type BigInt *big.Int
func (a BigInt) Add(b BigInt) BigInt {
return big.NewInt(0).Add(a, b)
}
// more methods
How can we write the body of Sum? One attempt might use type switches or type assertions, or some variation thereof.
type Adder(type T) interface {
Add(T) T
}
func Sum(type T)(list []T) T {
var sum T
if a, ok := sum.(Adder); ok {
for _, t := range list {
sum = sum.Add(t)
}
} else {
for _, t := range list {
sum += t
}
}
return sum
}
This has some difficulties. First, the version above requires that T be usable with the + operator, even if that branch will never be executed because T has an Add method. This might be avoidable using reflection, but the resulting Sum will not be typesafe; if called with an unusable type T, it will panic at run time instead of failing at compile time. Second, depending on how contracts work, it may be difficult or impossible to write a contract for this Sum.
Another way to write sum is to require the caller to pass an additional parameter encapsulating the behavior required of T. This is common with sorting functions, which often take a parameter describing how values are to be compared. We could write Sum as follows.
func Sum(type T)(list []T, add func(a, b T) T) T {
var T sum
for _, t := range list {
sum = add(sum, t)
}
return sum
}
This also works, but requires a fair bit of extra code. Many calls to generic functions will require one or more additional parameters, and many small adaptor functions will have to be written. Adding irritation, much of this extra code will be simple boilerplate, entirely predictable from the types involved.
In this document, we propose adding a new package operators to the standard library. This would contain many small generic functions corresponding to the built-in operators of Go. For example, there might be an Add function, which is defined as
func Add(type T)(a, b T) T { return a.Add(b) }
when T has a suitable Add method, and as
func Add(type T)(a, b T) T { return a + b }
otherwise. Using this Add, we can then write
func Sum(type T)(list []T) T {
var sum T
for _, t := range list {
sum = operators.Add(sum, t)
}
return sum
}
We are not proposing that the mechanisms for defining generic functions and their contracts be extended so that any programmer can write specialized versions of functions, such as Add above. Rather, we propose only that the compiler recognize the functions in the operators package and generate specialized instances for those functions, as required.
Here we assume generic types and functions have been implemented as in the contracts proposal, with or without the parts relating to contracts.
A new package operators will be added to the standard library. The exact name and placement is immaterial; generics/ops might be a suitable alternative, and would have the advantage of a short name.
Here we list generic functions to be provided in the operators package. For each function, we give a declaration for the function, followed by a list of possible bodies. The intent is that, for specific type arguments, the compiler will choose the first body which compiles successfully. If none of the bodies can be compiled, then the function cannot be used with those type arguments. There is an exception for array types; see below.
func Add(type T)(a, b T) T
return a.Add(b)return a + b
func Sub(type T)(a, b T) T
return a.Sub(b)return a - b
func Mul(type T)(a, b T) T
return a.Mul(b)return a * b
func Div(type T)(a, b T) T
return a.Div(b)return a / b
func Rem(type T)(a, b T) T
return a.Rem(b)return a % b
func BitAnd(type T)(a, b T) T
return a.BitAnd(b)return a & b
func BitOr(type T)(a, b T) T
return a.BitOr(b)return a | b
func BitXor(type T)(a, b T) T
return a.BitXor(b)return a ^ b
func BitClear(type T)(a, b T) T
return a.BitClear(b)return a &^ b
func ShiftLeft(type T)(a T, count uint) T
return a.ShiftLeft(count)return a << count
func ShiftRight(type T)(a T, count uint) T
return a.ShiftRight(count)return a >> count
func Minus(type T)(a T) T
return a.Minus()return -a
func BitComplement(type T)(a T) T
return a.BitComplement()return ^a
func Complex(type C, T)(r, i T) C
var c C; c.SetRealImag(r, i); return creturn complex(r, i)
func Real(type C, T)(c C) T
return c.Real()return real(c)
func Imag(type C, T)(c C) T
return c.Imag()return imag(c)
func Equal(type T, U)(t T, u U) bool
return t.Equal(u)return u.Equal(t)return t == u
func NotEqual(type T, U)(t T, u U) bool
return !Equal(t, u)
func Less(type T)(a, b T) bool
return a.Less(b)return a < b
func Greater(type T)(a, b T) bool
return b.Less(a)return a > b
func LessOrEqual(type T)(a, b T) bool
return !b.Less(a)return a <= b
func GreaterOrEqual(type T)(a, b T) bool
return !a.Less(b)return a >= b
func Len(type C)(c C) int
return c.Len()return len(c)
func Cap(type C)(c C) int
return c.Cap()return cap(c)
func At(type C, K, V)(collection C, key K) V
return collection.At(key)v, _ := collection.GetAt(key); return vreturn collection[key]
func GetAt(type C, K, V)(collection C, key K) (V, bool)
return collection.GetAt(key)v, ok := collection[key]; return v, ok
func PtrAt(type C, K, V)(collection C, key K) *V
return collection.PtrAt(key)return &collection[key]
func SetAt(type C, K, V)(collection C, key K, value V)
collection.SetAt(key, value)collection[key] = value
func Delete(type C, K)(collection C, key K)
collection.Delete(key)delete(collection, key)
func Slice(type S)(slice S, low, high int) S
return slice.Slice(low, high)return slice[low:high]
func SliceCap(type S)(slice S, low, high, max int) S
return slice.SliceCap(low, high, max)return slice[low:high:max]
func Append(type S, type T)(slice S, x ...T) S
return slice.AppendSlice(x...)return append(slice, x...)
func Make(type T)(n int) T
var t T; return t.Make(n)return make(T, n)
func MakeCap(type T)(n, m int) T
var t T; return t.Make(n, m)return make(T, n, m)
func Range(type C, K, V)(c C, func f(K, V)) (does not apply to channels)
c.Range(f)for k, v := range c { f(k, v) }
func Deref(type P, T)(p P) T
return p.Deref()return *p
func Receive(type C, T)(channel C) (T, bool)
t, ok := channel.Receive(); return t, okt, ok := <-channel; return t, ok
func Send(type C, T)(channel C, t T)
channel.Send(T)channel <- T
func Close(type C)(channel C)
channel.Close()close(channel)
Given an array type [n]T, the functions above which can apply to array types should be generated when the first type parameter is *[n]T, but not for [n]T itself. This is for efficiency, and so that functions which alter the container content will alter the caller's version of the array, not a copy local to the function.
This also implies that, given a generic function which calls functions from operators, when calling that function on an array, the & operator must be explicitly used. This is a good thing.
var array [100]int
Sort(array) // error
Sort(&array) // ok
How should the functions in operators behave with respect to user-defined types which inherit operators from built-in types? For example,
type Int int
Here, Int inherits the + operator from int. The programmer might or might not also define an Add method on Int.
Above, we assume that operators.Add(Int) will use the Int.Add method if it exists. If that method does not exist, the + operator inherited from int will be used. This is probably the best approach, as it allows for operators.Add(Int) to use the + operator with no additional code required, and also allows the programmer to override this choice when necessary.
Another viable rule would be that the inherited + operator is never used. A programmer who wishes to be able to use operators.Add(Int) must define the Int.Add method.
The Equal function as defined above is not entirely satisfactory. Given types T, U, and V, all of which are supposed to represent integers, we should be able to take a value a of type T and check whether it is equal to a value t of type T, a value u of type U, or a value v of type V. Our Equal probably does not do this unless T, U, and V all implement a common interface I which includes a method Equal(I).
However, it is not obvious how to implement a better Equal, and this one at least covers the important case in which the two type parameters T and U are the same type.
There are some minor differences between the functions above and the built-in operators they encapsulate. These differences should not present any significant problems.
The At, GetAt, PtrAt, and SetAt functions, when used with a user-defined collection type, will accept only values of the index type in the corresponding methods of the user-defined type. The built-in index expressions, when the collection is a slice or array, will accept indices of any integer type.
type Foo ...
func (f Foo) At(n uint) float64 { ... }
n := 2
var foo Foo
var x float64 = operators.At(foo, n) // Error: n is not a uint
The PtrAt function cannot be used on an unnamed map type, so as far as the built-in types are concerned, we could restrict the key type to be int. However, it may useful with user-defined collections to allow other key types.
Slice and SliceCap accept only int values as indices; built-in slice expressions accept any integer type.
ShiftLeft and ShiftRight accept only uint values as indices; the << and >> operators accept any unsigned integer type.
The comparison functions return a bool value; the built-in operators return an untyped boolean value.
type Bool bool
var b1 Bool = 5 < 7 // ok
var b2 Bool = operators.Less(5, 7) // Error: cannot assign bool to Bool
For convenience, the comparison functions have been written so that user-defined types need only provide Equal and Less methods. However, ordered comparisons on built-in types still use the corresponding operators. This is because comparisons involving floating point Nans are weird.
We might provide functions which combine a binary operation and an assignment, such as
func AddAssign(type T)(a *T, b T)
a.AddAssign(b)*a = (*a).Add(b)*a += b
This would be useful in cases where an AddAssign method can be implemented more efficiently than Add followed by assignment. Note that the first parameter should be a pointer.
We might consider allowing generic functions to use actual operators as syntactic sugar for calls to the corresponding functions in the operators package.
func Sum(type T)(list []T) T {
var sum T
for _, t := range list {
sum = sum + t
}
return sum
}
Here, sum + t would generate a call to operators.Add(sum, t). This is probably a really bad idea unless something about Sum, perhaps its contract, explicitly references operators.Sum(T). Even then, it's probably a bad idea.
For types that can undergo forms of addition and multiplication (for example, mathematical arrays), it might be useful to have functions that return the additive and multiplicative identities.
func Zero(type T)() T
var t T; return t.Zero()return 0
func One(type T)() T
var t T; return t.One()return 1
It might be common to have the zero value represented by Go's normal default initialization, in which case Zero might not be needed. But One might still be needed.
The operators package has no support for these. Actual type assertions and type switches should be used instead.
There is no support for building a value which can be called as if it were a function. Use a function literal or method value instead and call it normally.
There is no support for building a user-defined type similar to bool. If you need to do this, it should be sufficient to define a type based on bool, and the built-in operators can then be used.
type MyBool bool
Note also, that while we could trivially provide And, Or, and Not functions corresponding to the &&, ||, and ! operators, And and Or would always evaluate their second argument, unless we defined that argument to be a function returning bool.
There is no function corresponding to the unary & operator. This operator already applies to all types, and we should not add confusion.
There are no functions to do conversions. The contracts draft does not include methods with extra type parameters in addition to the type parameters of the receiver type. Without those, it is hard to see how to do conversions in the general case.
The unary + operator seems to be a no-op, so it has not been included.
Ordinary assignment statements work for values of any type. While a few types might benefit from having an Assign method that does something more semantically meaningful or more efficient than a simple assignment statement, it is likely that most writers of generic functions will use assignment statements rather an operators.Assign function, even if such were provided. So instead of providing this function, we should encourage writers of types similar to built-in types to ensure that their types work well with ordinary assignment functions.
There is no support for select statements. These will only be implemented for actual channel types, not user-defined imitations.
There is no function operators.New corresponding to the built-in new function. Instead of new(T), one may write var t T; &t.
The Range function above allows for iterating over the contents of a collection, using a function to describe the action to be taken for each element. For simplicity, there is no way to end the iteration early.
It would also be possible to allow Range to iterate over channels, by providing another possible body:
for v := range c { f(struct{}, v }
It is not clear whether this is desirable.
It is also desirable to provide a way to iterate over a collection with finer control, such as
var c C /* C is some collection type */
for r := operators.RangeStart(c); !operators.RangeDone(c, r); operators.RangeNext(c, &r) {
if !doSomethingWith(r.Key, r.Value) {
break
}
}
The return type of operators.RangeStart would depend on the collection type, as some collections may need more than just the current key and value in order to advance to the next position in the collection. In particular, it seems impossible to write suitable versions of RangeStart, RangeDone, and RangeNext as ordinary functions when the collection is a map[K]V.
Depending on what form contracts take, if they are added to the language, it might turn out to be impossible to write contracts for the functions in the operators package. This shouldn't be a major problem. The compiler will know what the requirements are, and those requirements can be included in the documentation for programmers to see. Furthermore, these are small, simple functions; future changes should be rare.
When writing a generic function F that calls one of these functions, directly or indirectly, one should include that fact in F's contract. That is, the contract for F should say that it calls operators.Add(T), instead of saying "either T has a method Add or the + operator works on values of type T". The latter is not possible under the current contracts draft.