Skip to content

Instantly share code, notes, and snippets.

@andybalholm
Last active October 30, 2019 19:42
Show Gist options
  • Save andybalholm/acecba3acf57bf1254142dadce928890 to your computer and use it in GitHub Desktop.
Save andybalholm/acecba3acf57bf1254142dadce928890 to your computer and use it in GitHub Desktop.
Contracts and Adaptors

Contracts and Adaptors

This is a proposal for an alternate syntax for contracts for generics in Go, along with adaptors for types that do not natively fulfill the contract. It takes a lot of inspiration from Pat Smith's Go Generics with Adaptors.

It is primarily motivated by the discussion about how to make a single generic function work both with builtin types that use operators and with user-defined types that use methods.

Contracts

In this proposal, a contract is a set of functions that encapsulates the type-specific operations that are needed to implement a generic algorithm. The functions’ bodies are unconstrained generic code; if they compile successfully with a given set of type parameters, those parameters fulfill the contract.

contract Adder(T) {
	Zero() T {
		return 0
	}
	Add(sum, n T) T {
		return sum + n
	}
}

A generic function that uses a contract calls the functions in the contract to perform operations on generic values. The names of the functions in the contract are in scope in the body of generic functions that use the contract, and in the bodies of methods on generic types that use the contract.

func SumSlice(type T Adder)(s []T) T {
	sum := Zero()
	for _, t := range s {
		sum = Add(sum, t)
	}
	return sum
}

Adaptors

If a type doesn’t fulfill the contract that a generic function or type was defined with, a compatible contract can be used as an adaptor.

contract BigIntAdder(T) {
	Zero() T {
		return big.NewInt(0)
	}
	Add(sum, n T) T {
		return sum.Add(sum, n)
	}
}

var bigints []*big.Int
fmt.Println(SumSlice(BigIntAdder)(bigints))

When a generic function or type has the name of a contract after it in parentheses, the result is another generic function or type, with its contract replaced by the new contract. The new contract must have the same number of type parameters as the original contract, and include all the functions that the original contract included, with the same signatures.

Where the original function or type called the functions from its contract, the new one calls the corresponding functions from its new contract.

Contracts on Multiple Types

A contract can have multiple type parameters; here is what the contract from the graph example in the draft design would look like:

contract G(Node, Edge) {
	Edges(n Node) []Edge {
		return n.Edges()
	}
	Nodes(e Edge) (from, to Node) [
		return e.Nodes()
	}
}

Permitted Operations

In the bodies of contract functions, any operation is permitted that might be valid with some type. Whether the functions typecheck successfully with a given set of type parameters determines whether those parameters fulfill the contract.

In a generic function or type with no contract, the only operations permitted on values of the unknown types are those that are permitted on all types (such as copying), plus type assertions and type switches.

If there is a contract, the generic function (or methods of the generic type) can also call the functions in the contract, or use a generic type or function that requires the same contract.

Map Keys

The runtime package defines the contract that map keys must fulfill:

contract MapKey(T) {
	hash(key T, seed uintptr) uintptr {
		// The body of this function is left as an exercise for the reader.
	}
	equal(a, b T) bool {
		return a == b
	}
}

Because the function names are lower case, they are private to the runtime package. Other packages can’t call them directly, or reimplement them with an adaptor. But they can use the contract as a whole:

type Set(type T runtime.MapKey) map[T]struct{}
@epbcricky
Copy link

Of the many variants presented this formulation of contracts is simple and readable. I hope the Go movers and shakers will consider it.

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