Skip to content

Instantly share code, notes, and snippets.

@bserdar
Last active November 22, 2018 04:12
Show Gist options
  • Save bserdar/8f583d6e8df2bbec145912b66a8874b3 to your computer and use it in GitHub Desktop.
Save bserdar/8f583d6e8df2bbec145912b66a8874b3 to your computer and use it in GitHub Desktop.
Types are contracts

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.

Types are contracts

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)

Primitive type contracts in standard library

With this style of contract definition, the standard library can contain a library of common contracts such as integers, floats, unsigned, signed, etc.

Special case for == operator

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 as a List of Types

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 with Type Parameters

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)

Mutually referential type parameters

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
  }
}

Examples from the proposal

Sort

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, ...)
}

Map keys

MapKey would be a predefined contract defined using the "supportsEqual" builtin

Sets

Contract comparable in this example is the same as supportsEqual builtin.

Metrics

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.

@komuw
Copy link

komuw commented Nov 20, 2018

A contract can also be written in terms of a struct:

contract linkedListNode {
  X struct {
    next *X
  }
}

what is X?

@mlevieux
Copy link

mlevieux commented Nov 20, 2018

I guess X is the type that is represented by the struct, the meaning being : "the type X is a struct that contains a field that is a pointer to a value of the same type".

EDIT : I think the "next" word, which is here the name of the field, can even be omitted. The relevant information here is to know the type X contains a field of type *X, whether this field is named "next" or "child" or anything else does not break the viability of the expression.

@mandolyte
Copy link

Contract comparable in this example is the same this as supportsEqual builtin.
Should omit second "this"? Contract comparable in this example is the same as supportsEqual builtin.

@bserdar
Copy link
Author

bserdar commented Nov 22, 2018

Contract comparable in this example is the same this as supportsEqual builtin.
Should omit second "this"? Contract comparable in this example is the same as supportsEqual builtin.

Fixed that, thanks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment