Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Go 2 Generics - Contract with methods

Contracts with methods

Abstract

This proposal is based on Lance Taylor and Robert Griesemer's proposal for Go 2 "generics" (Contracts — Draft Design). It is identical of the original regarding type parameters, but gives a different solution for contracts.

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.

The problem

Contracts are not easy to be read by an human. He or she must understand how the compiler makes the type checking. That makes Go code less readable and contract hard to be written.

This proposal

According the original proposal, a generic function with type parameters that does not use a contract , such as the Print example shown earlier, is a function is only permitted to use those type parameters in ways that any type may be used in Go. That is, operations like:

  1. Declare variables of those types.
  2. Assign other values of the same type to those variables.
  3. Pass those variables to functions or return them from functions.
  4. Take the address of those variables.
  5. Define and use other types that use those types, such as a slice of that type.

I am suggesting to add another permitted operation:

  1. Call methods of those type parameters. Those methods are defined inside contracts.

Contract with methods

A method in contract looks like a normal method of Go, but it is defined inside a contract block and can use types and variables defined in that contract. For function Stringify, the contract with methods is like:

contract stringer(x T) {
	func (T) String() string {
		return x.String()
	}
}

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

Above, the method String, defined in contract stringer, acts like an "interface" layer between the function Stringify and the type T. Once, the function Stringify is instantiated with a specific type, for example Stringify(int), the compiler can check the type int with the method String inside the contract stringer.

To compare, the original contract is a set lines in Go, syntactically correct, but without any semantic coherence besides be used for type checking. Here is the same example using the original contract model:

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

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

Operators

When a generic function needs to use operators like == or + with type parameters, those operators should be replaced by methods. In the below example, the method Equal replaces the operator ==.

Contract with methods

contract comparable(x T) {
	func (T) Equal(e T) bool {
		return x == e
	}
}

func Contains(type T comparable)(s []T, e T) bool {
	for _, v := range s {
		if v.Equal(e) {
			return true
		}
	}
	return false
}

Original contract

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

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

Contract embedding

A contract may embed another contract, this works very similar to contract embedding in original propose.

Contract with methods

contract stringer(x T) {
	func (T) String() string {
		return x.String()
	}
}

contract PrintStringer(x X) {
	stringer(X)
	func (X) Print() {
		x.Print()
	}
}

Original contract

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

contract PrintStringer(x X) {
	stringer(X)
	x.Print()
}

Some considerations

Contract with methods bring at least the same information of original contract. So, the compiler can:

  • Validate a set of type arguments.
  • Describe what is permitted to do with those type parameters.

Unlike the original contracts, the code in the methods could be called by a generic function. To avoid some performance penalty in that call, compiler could perform some inline expansion optimization.

Comparative examples

Those examples, from the original proposal, shows how would be the generic functions with contract with methods model and with original contract model.

Passing explicit types to a contract

Contract with methods

contract convertible(_ To, v From) {
	func (From) Convert() To {
		return(To(v))
	}
}

func FormatUnsigned(type T convertible(uint64, T))(v T) string {
	return strconv.FormatUint(v.Convert(), 10)
}
...

	s := FormatUnsigned(rune)('a')

Original contract

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

func FormatUnsigned(type T convertible(uint64, T))(v T) string {
	return strconv.FormatUint(uint64(v), 10)
}

...

	s := FormatUnsigned(rune)('a')

Multiple type parameters

Contract with methods

contract viaStrings(t To, f From) {
	func (From) String() string {
		return f.String()
	}

	func (To) Set(s string) {
		t.Set(s)
	}
}

func SetViaStrings(type To, From viaStrings)(s []From) []To {
	r := make([]To, len(s))
	for i, v := range s {
		r[i].Set(v.String())
	}
	return r
}

Original contract

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

func SetViaStrings(type To, From viaStrings)(s []From) []To {
	r := make([]To, len(s))
	for i, v := range s {
		r[i].Set(v.String())
	}
	return r
}

Using types that refer to themselves in contracts

Contract with methods

package comparable

contract equal(v T) {
	func (T) Equal(e T) bool {
		return v == e
	}
}

func Index(type T equal)(s []T, e T) int {
	for i, v := range s {
		if e.Equal(v) {
			return i
		}
	}
	return -1
}
import "comparable"

type EqualInt int

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

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

Original contract

package comparable

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

func Index(type T equal)(s []T, e T) int {
	for i, v := range s {
		if e.Equal(v) {
			return i
		}
	}
	return -1
}
import "comparable"

type EqualInt int

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

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

Type conversions

Contract with methods

package check

contract convert(t To, f From) {
	func (From) To() To {
		return To(f)
	}

	func (To) From() From {
		return From(t)
	}

	func (From) Equal(v From) bool {
		return f == v
	}
}


func Convert(type To, From convert)(from From) To {
	to := from.To()
	if !(to.From().Equal(from)) {
		panic("conversion out of range")
	}
	return to
}

Original contract

package check

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

func Convert(type To, From convert)(from From) To {
	to := To(from)
	if From(to) != from {
		panic("conversion out of range")
	}
	return to
}

Untyped constants

Contract with methods

contract add1K(x T) {
	func (T) Add1K() T {
		return (x + 1000)
	}
}

func Add1K(type T add1K)(s []T) {
	for i, v := range s {
		s[i] = v.Add1k()
	}
}

Original contract

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

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

Sequences

Contract with methods

contract strseq(x T) {
	func (T) Len() int {
		return len(x)
	}

	func (T) ByteSlice() []byte {
		return []byte(x)
	}

	func (T) New(b []byte)) T {
		return T(b)
	}
}

func Join(type T strseq)(a []T, sep T) (ret T) {
	if len(a) == 0 {
		return ret
	}
	if len(a) == 1 {
		return T.New(append([]byte(nil), a[0].ByteSlice()...))
	}
	n := sep.Len() * (len(a) - 1)
	for i := 0; i < len(a); i++ {
		n += a[i].Len()
	}

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

Original contract

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

func Join(type T strseq)(a []T, sep T) (ret T) {
	if len(a) == 0 {
		return ret
	}
	if len(a) == 1 {
		return 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 T(b)
}

Fields

Contract with methods

package move

contract counter(x T) {	
	func (T) Count() int {
		return x.Count
	}

	func (T) SetCount(i int)  {
		x.Count = i
	}
}

contract counters(T1, T2) {
	counter(T1)
	counter(T2)
}

func Corresponding(type T1, T2 counters)(p1 *T1, p2 *T2) {
	p1.SetCount(p2.Count())
}

Original contract

package move

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

contract counters(T1, T2) {
	counter(T1)
	counter(T2)
}

func Corresponding(type T1, T2 counters)(p1 *T1, p2 *T2) {
	p1.Count = p2.Count
}

Sort

Contract with methods

contract ordered(e Ele) {
	func (Ele) LessThan(v Ele) bool {
		return e < v
	}
}

type orderedSlice(type Ele ordered) []Ele

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

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

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

func OrderedSlice(type Ele ordered)(s []Ele) {
	sort.Sort(orderedSlice(Ele)(s))
}

Original contract

contract ordered(e Ele) { e < e }

type orderedSlice(type Ele ordered) []Ele

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

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

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

func OrderedSlice(type Ele ordered)(s []Ele) {
	sort.Sort(orderedSlice(Ele)(s))
}
@sean-cfa

This comment has been minimized.

Copy link

commented Feb 28, 2019

Explicit Contracts

I think you're on to something. Here is a compromise variation that has the following rules:

  • contract declaration can only have types as arguments (no variable).
  • var can NOT be used in a contract.

Function types

Function Types

contract stringer(T) {
	func (T) String() string
}

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

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

Comparison

Comparison

Explicit Contracts

contract comparable(T) {
    T == T
}

Original contract

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

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

Contract embedding

A contract may embed another contract, this works very similar to contract embedding in original propose.

Explicit Contracts

contract stringer(T) {
	func (T) String() string
}

contract PrintStringer(X) {
	stringer(X)
	func (X) Print()
}

Original contract

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

contract PrintStringer(x X) {
	stringer(X)
	x.Print()
}

Conversions

Conversions

Explicit Contracts

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

Original contract

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

func FormatUnsigned(type T convertible(uint64, T))(v T) string {
	return strconv.FormatUint(uint64(v), 10)
}

...

	s := FormatUnsigned(rune)('a')

Multiple type parameters

Explicit Contracts

contract viaStrings(To, From) {
	func (From) String() string
	func (To) Set(string)
}

Original contract

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

func SetViaStrings(type To, From viaStrings)(s []From) []To {
	r := make([]To, len(s))
	for i, v := range s {
		r[i].Set(v.String())
	}
	return r
}

Using types that refer to themselves in contracts

Explicit Contracts

package comparable

contract equal(v T) {
	func (T) Equal(T) bool
}

Original contract

package comparable

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

func Index(type T equal)(s []T, e T) int {
	for i, v := range s {
		if e.Equal(v) {
			return i
		}
	}
	return -1
}
import "comparable"

type EqualInt int

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

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

Type conversions

Explicit Contracts

package check

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

Original contract

package check

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

func Convert(type To, From convert)(from From) To {
	to := To(from)
	if From(to) != from {
		panic("conversion out of range")
	}
	return to
}

Untyped constants

Explicit Contracts

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

func Add1K(type T add1K)(s []T) {
	for i, v := range s {
		s[i] = v.Add1k()
	}
}

Original contract

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

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

Sequences

Explicit Contracts

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

Original contract

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

func Join(type T strseq)(a []T, sep T) (ret T) {
	if len(a) == 0 {
		return ret
	}
	if len(a) == 1 {
		return 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 T(b)
}

Fields

Explicit Contracts

package move

contract counter(T) {	
	struct T {Count int}
}

contract counters(T1, T2) {
	counter(T1)
	counter(T2)
}

Original contract

package move

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

contract counters(T1, T2) {
	counter(T1)
	counter(T2)
}

func Corresponding(type T1, T2 counters)(p1 *T1, p2 *T2) {
	p1.Count = p2.Count
}

Sort

Explicit Contracts

contract ordered(E) { E < E }

Original contract

contract ordered(e Ele) { e < e }

type orderedSlice(type Ele ordered) []Ele

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

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

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

func OrderedSlice(type Ele ordered)(s []Ele) {
	sort.Sort(orderedSlice(Ele)(s))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.