Contracts only for Generic Types

Abstract

This is my second proposal based on Lance Taylor and Robert Griesemer's proposal for Go 2 "generics" (Contracts — Draft Design). Although they are very similar, it is a simplification of the original but keeps its capabilities.

Original proposal

Generic functions

According the Contracts proposal, "generic code is code that is written using types that will be specified later". To achieve that, it defines generic functions using an unspecified type called type parameter. When the code is used, the type parameter is set to a type argument.

package main

import (
	"fmt"
)

func Print(type T)(s []T) {
	for _, v := range s {
		fmt.Println(v)
	}
}

func main() {
	Print(int)([]int{1, 2, 3})
}

Above, the Print function is defined with a type paramenter (type T). That definition states that the Print function could receive a slice of any type. In the main function, Print is called with a type argument (int). So, the compiler "instantiates" a Print function that accept a slice of integer ([]int) as its argument.

Generic types

Besides the generic functions, the Contracts proposal also defines generic types using type parameter and type argument.

type Vector(type Element) []Element

var v Vector(int)

Above, Vector is a type that defines a slice of any type. Therefore, the variavle v is an instance of the type Vector and a slice of integer ([]int).

Contracts

Contracts are structures used to constrain generic functions to maintain strict type rules at compile-time. This is an example from the Contracts proposal ⇗, the Stringify function converts a slice of some type into a slice of strings ([]string) by calling a String method on each element.

func Stringify(type T stringer)(s []T) (ret []string) {
	for _, v := range s {
		ret = append(ret, v.String())
	}
	return ret
}

The Stringify function will work if type T has a String method. But if doesn't, it will fail. The contract stringer (see the below code) allow the compiler to verify the contrainsts of type T to work with Stringify.

contract stringer(x T) {
	var s string = x.String()
}

The code inside a contract will never run, it is only used by compiler to:

1. Validate a set of type arguments. When a function with type parameters is called, it will be called with a set of type arguments. When the compiler sees the function call, it will use the contract to validate the type arguments. If the type arguments are invalid, the compiler will report a type error: the call is using types that the function’s contract does not permit.
2. Describe what the function with type parameters, is permitted to do with those type parameters.

So, contract intend to be used for type checking of generic functions.

This proposal

Using the type argument in the generic functions causes a complex syntax with a "lots of irritating silly parentheses". Therefore, this propose support to use type argument ONLY with generic types. Thereby, the contracts would be used for type checking of variables with generic type, instead checking generic functions. Following are the earlier examples written with generic types.

package main

import (
	"fmt"
)

type Vector(type T) []T

func Print(s Vector) {
	for _, v := range s {
		fmt.Println(v)
	}
}

func main() {
	Print(Vector(int){1, 2, 3})
}

contract stringer(x T) {
	var s string = x.String()
}

type Vector(type T stringer) []T

func Stringify (s Vector) (ret []string) {
	for _, v := range s {
		ret = append(ret, v.String())
	}
	return ret
}

Variables

Variables are instatiations of a generic type. Bellow, the Elem is a generic type that can be incremented, then variable v is a slice of Elem instatiated as an integer.

contract incrementable(x T) {
	var _ T = x + 1
}

type Elem(type T incrementable) T

func Increment(s []Elem(t)) (ret []Elem(t)) {
	for _, v := range s {
		ret = append(ret, v + 1)
	}
	return ret
}
...
	v := []Elem(int){1, 2, 3}
	v = Increment(v)

Some examples

Operators

contract comparable(x T) {
	x == x
}

type Elem(type T comparable) T

func Contains(s []Elem, e Elem) bool {
	for _, v := range s {
		if v == e {
			return true
		}
	}
	return false
}

Passing explicit types to a contract

contract convertible(_ To, f From)  {
	To(f)
}

type Value(type T convertible(uint64, T)) T

func FormatUnsigned(v Value) string {
	return strconv.FormatUint(uint64(v), 10)
}
...

	s := FormatUnsigned('a')

Multiple type parameters

contract viaStrings(t To, f From) {
	var x string = f.String()
	t.Set(string(""))
}

type ElemTo(type To, From viaStrings) To

type ElemFrom(type To, From viaStrings) From

func SetViaStrings(s []ElemFrom(t,f)) []ElemTo(t,f) {
	r := make([]ElemTo(t,f), len(s))
	for i, v := range s {
		r[i].Set(v.String())
	}
	return r
}

Using types that refer to themselves in contracts

package comparable

contract equal(v T) {
	var x bool = v.Equal(v)
}

type Elem(type T equal) T

func Index(s []Elem, e Elem) int {
	for i, v := range s {
		if e.Equal(v) {
			return i
		}
	}
	return -1
}

import "comparable"

type EqualInt comparable.Elem(int)

func (a EqualInt) Equal(b EqualInt) bool { return a == b }

func Index(s []EqualInt, e EqualInt) int {
	return comparable.Index(s, e)
}

Type conversions

package check

contract convert(t To, f From) {
	To(f)
	From(t)
	f == f
}

type ElemTo(type To, From convert) To

type ElemFrom(type To, From convert) From

func Convert(from ElemFrom(t,f)) ElemTo(t,f) {
	to := ElemTo(t,f)(from)
	if ElemFrom(t,f)(to) != from {
		panic("conversion out of range")
	}
	return to
}

Untyped constants

contract add1K(x T) {
	x = 1000
	x + x
}

type Elem(type T add1K) T

func Add1K(s []Elem) {
	for i, v := range s {
		s[i] = v + 1000
	}
}

Sequences

contract strseq(x T) {
	[]byte(x)
	T([]byte{})
	len(x)
}

type Elem(type T strseq) T

func Join(a []Elem(t), sep Elem(t)) (ret Elem(t)) {
	if len(a) == 0 {
		return ret
	}
	if len(a) == 1 {
		return Elem(t)(append([]byte(nil), []byte(a[0])...))
	}
	n := len(sep) * (len(a) - 1)
	for i := 0; i < len(a); i++ {
		n += len(a[i])
	}

	b := make([]byte, n)
	bp := copy(b, []byte(a[0]))
	for _, s := range a[1:] {
		bp += copy(b[bp:], []byte(sep))
		bp += copy(b[bp:], []byte(s))
	}
	return Elem(t)(b)
}

Fields

package move

contract counter(x T) {
	var _ int = x.Count
}

type Cont(type T counter) T

func Corresponding(p1 *Cont, p2 *Cont) {
	p1.Count = p2.Count
}

Sort

contract ordered(e Ele) { e < e }

type orderedSlice(type T ordered) []T

func (s orderedSlice) Len() int {
	return len(s)
}

func (s orderedSlice) Less(i, j int) bool {
	return s[i] < s[j]
}

func (s orderedSlice) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func OrderedSlice(s orderedSlice) {
	sort.Sort(orderedSlice(orderedSlice))
}