v2:
This started as a thought experiment after I read the Go generics and contracts proposal. The original proposal is powerful enough to specify precise type properties from the point of the generic implementor, however constraints such as "type T must support operator <" is over-specific in a language where < cannot be redefined. Such a constraints means "T must be numeric or string". So this exercise is an extension of the idea that contracts should be specified in terms of existing types, not in terms of type capabilities.
This is strictly about the contracts part of the generics proposal. It only describes a way to specify contracts using existing types, it does not add antyhing to the parameterized types discussion.
First, some context. The syntax and keywords are not really important in the following discussion:
This is a parameterized function:
func F(type T)(in T) T {
}
Structs and interfaces can also be parameterized:
type listNode(type T) struct {
payload T
}
type ListNode(type T) interface {
GetPayload() T
}
Here T is a type. The information about T is not sufficient to compile the func, struct, and interface because nothing is known about T when compiling the parameterized type. So we add contracts that specify constraints on T.
The official proposal uses a 'contract' construct that is similar to a function that asserts constraints on types. It is a powerful contstruct that can assert certain properties on types as well as mutual relationships between types. However, I believe contracts specified in terms of existing types is a more direct approach, it is more explicit, and it clearly represents the intent of the generic type implementor.
A type parameter can be constrained using a contract:
func F(type T C)() {...}
Here, T must be a type satisfying the contract C.
A contract is evaluated at two distinct points:
-
When compiling the generic type that is using the contract. Here, the generic type can be compiled by constructing a minimal concrete type satisfying the contract.
-
When the generic type is instantiated. At this point, a concrete type is checked if it satisfies the contract.
These are both compile-time checks. Contracts do not exist at runtime.
This is a contract that is specified using an interface:
contract stringer {
interface {
String() string
}
}
Type T satisfies stringer contract if it implements String() function. This contract is equivalent to an interface.
A contract can also be written in terms of a struct:
contract linkedListNode {
X struct {
next *X
}
}
Type T satisfies linkedListNode contract if it is a struct with a member named 'next' of type *T, such as:
type T struct {
next *T
}
The following is also valid, linked list node with payload:
contract linkedListNode(type P) {
X struct {
next *X
Payload P
}
}
More on contracts with type parameters later.
A contract can be defined in terms of primitive types:
contract C SignedNumber {
like(int16,int32,int64)
}
Type T satisfies SignedNumber contract if T is one of the types listed in the "like" clause, or if it is a type derived from one of those types. In the following:
func IsNegative(type T SignedNumber)(in T) bool {
return in<0
}
The following would work:
func f(i int) {
if IsNegative(i) {
...
}
because int is derived from int64 (or one of the other ints)
With this style of contract definition, the standard library can contain a library of common contracts such as integers, floats, unsigned, signed, etc.
One problem this cannot address is the == operator. This requires a built-in contract, something like "supportsEqual".
contract X {
supportsEqual
}
Here, if a type T satisfies contract X, then a == b must be well defined for a, b of type T.
Then we can also define:
contract MapKey {
supportsEqual
}
A contract can list multiple types. In that case, the concrete implementation must satisfy all types of the contract.
contract linkedListNode {
T struct {
next *T
}
interface {
GetNext() *T
}
}
This linkedListNode contract requires that the concrete type satisfying this contract must have a 'next' field pointing to the same struct type as well as a GetNext() T function returning a pointer to that same type. The above linked list node implementation allows implementing a linked list without a SetNext() method, because in the package it is instantiated, the list implementation will have access to the unexported 'next' field.
contract StringableNum {
like(int16,int32,int64)
interface {
String() string
}
}
The StringableNum contract requires an int-derivative that implements the String() string function.
Contracts can have type parameters:
contract linkedListNode(type P) {
X struct {
next *X
Payload P
}
interface {
GetPayload() P
}
}
This means that all types listed in the contract are parameterized types, and they inherit the contract type parameters:
type X struct(type P) {...}
type _ interface (type P) {...}
A side effect of this is that contract type parameters can be constrained by other contracts.
contract numLinkedListNode(type P StringableNum) {...}
Here numLinkedListNode is a contract that has StringableNum payloads.
When a parameterized contract is used to constrain a type parameter, the contract must be fully defined. That is:
contract linkedListNode(type P) {...}
func AddNode(type X,type N linkedListNode(X))(payload X) *N {...}
Here, the linkedListNode contract is used with type X. To compile AddNode, the compiler first processes the type parameters (X and N), and then does the contract processing. In this case, it deduces that N satisfies linkedListNode(X) contract.
Type inference cannot always be used for the above case:
myNode:=AddNode(myPayload)
Type of myPayload is known, but type of myNode is not know during compilation. Because of this, AddNode needs explicit instantiation:
myNode:=AddNode(MyPayloadType,MyNodeType)(myPayload)
Let's try to write the graph example from the official proposal. A graph has nodes and edges, and nodes must be associated with edges with correct types of nodes as endpoints. That is we want:
type SomeEdge interface {
Nodes() (SomeNode,SomeNode)
}
type SomeNode interface {
Edges() []SomeEdge
}
type Graph struct {
nodes []SomeNode
}
Above, Graph uses SomeNode, which implies it also uses SomeEdge.
contract Edge(type N) {
interface {
Nodes() (N, N)
}
}
contract Node(type E) {
interface {
Edges() []E
}
}
type Graph(type N Node(E), type E Edge(N)) struct {
nodes []N
}
A parameterized function can also be defined similarly:
func New(type N Node(E), type E Edge(N))(nodes []N) *Graph(N,E) {
}
The following is a valid use of the above contract:
type MyNode struct {
edges []*MyEdge
}
func (m MyNode) Edges() []*MyEdge {return m.edges}
type MyEdge struct {
from, to *MyNode
}
func (e MyEdge) Nodes() (*MyNode,*MyNode) {return e.from,e.to}
func f() {
var g:=graph.New([]MyNode{...})
}
An alternative contract specification using structs:
package graph
contract Node(type E Edge) {
struct {
edges []*E
}
interface {
GetEdges() []*E
}
}
contract Edge(type N Node) {
struct {
from,to *N
}
interface {
GetFrom() *N
GetTo() *N
}
}
contract Graph(type N Node(E),type E Edge(N)) {
struct {
nodes []*N
}
}
This example defines an ordered contract, and such a contract can also be included in the library of predefined contracts as:
contract Ordered {
like(numeric types, string, ...)
}
MapKey would be a predefined contract defined using the "supportsEqual" builtin
Contract comparable in this example is the same as supportsEqual builtin.
contract Metric1(type T MapKey) {
struct {
sync.Mutex
m map[T]int
}
}
func (m *M) Add(type ValueType,type M Metric1(ValueType))(v ValueType) {
m.Lock()
defer m.Unlock()
if m.m==nil {
m.m=make(map[T]int)
}
m[v]++
}
Above Metric1 is defined as a contract. Metric1 can also be defined as a parameterized struct, as done in the official proposal.
what is X?