Skip to content

Instantly share code, notes, and snippets.

@gbitten
Last active March 6, 2019 10:10
Show Gist options
  • Save gbitten/9faf20886728d3750e106e352c31f0e9 to your computer and use it in GitHub Desktop.
Save gbitten/9faf20886728d3750e106e352c31f0e9 to your computer and use it in GitHub Desktop.
go2draft-proposal-II.md

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))
}
@griesemer
Copy link

From your examples it is not clear to me how you call a generic function, especially if a generic function argument type is parametrized via two types. For instance, how do I call SetViaStrings? At some point I will need to provide the respective type parameters to that call, don't I (and then I would need some parentheses for that)? Your examples might work with type inference (for parameter types), but type inference is not sufficient if only a function result is parametrized. What am I missing?

The problem with the draft design on contracts which we presented last year is really not the extra "silly parentheses" - that syntax we can work on if need be (though we're not unhappy with it). The problem is really in the contracts specification themselves; i.e., how does the compiler extract the relevant information from a contract's code body, how can we make that easily human-readable, and how does one specify that in the spec. We were pretty clear in the design draft that this was the weak spot in the design.

So this (contract specification) is what we're trying to improve at the moment. We have made some progress I believe, but we're not quite ready to talk about it (it needs a bit more work); but we hope to do so later this year.

@gbitten
Copy link
Author

gbitten commented Mar 6, 2019

From your examples it is not clear to me how you call a generic function, especially if a generic function argument type is parametrized via two types. For instance, how do I call SetViaStrings? At some point I will need to provide the respective type parameters to that call, don't I (and then I would need some parentheses for that)?

You are right, the syntax of my propose is incomplete, so I just updated it. Now, the viaStrings example is like:

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
}

The type arguments of ElemFrom and ElemTo are now explicitly declared in function viaStrings. I am not sure if it is a good solution, but is the only one I can see.

Your examples might work with type inference (for parameter types), but type inference is not sufficient if only a function result is parametrized. What am I missing?

You are right again. The propose doesn't address functions which only the result is parameterized.

The problem with the draft design on contracts which we presented last year is really not the extra "silly parentheses" - that syntax we can work on if need be (though we're not unhappy with it). The problem is really in the contracts specification themselves; i.e., how does the compiler extract the relevant information from a contract's code body, how can we make that easily human-readable, and how does one specify that in the spec. We were pretty clear in the design draft that this was the weak spot in the design.

So this (contract specification) is what we're trying to improve at the moment. We have made some progress I believe, but we're not quite ready to talk about it (it needs a bit more work); but we hope to do so later this year.

Totally agree if you, I really hope you succeed.

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