go2draft-contracts.md: update to new contracts draft design
The design of contracts is simplified significantly.
Change-Id: I16aba65fa09d7e7fee3e2aeeabe1e76c7c8c75af
Reviewed-on: https://go-review.googlesource.com/c/proposal/+/187740
Reviewed-by: Robert Griesemer <gri@golang.org>
diff --git a/design/go2draft-contracts.md b/design/go2draft-contracts.md
index cdc0450..10fd074 100644
--- a/design/go2draft-contracts.md
+++ b/design/go2draft-contracts.md
@@ -2,55 +2,56 @@
Ian Lance Taylor\
Robert Griesemer\
-August 27, 2018
+July 25, 2019
## Abstract
We suggest extending the Go language to add optional type parameters
to types and functions.
Type parameters may be constrained by contracts: they may be used as
-ordinary types that only support the operations described by the
+ordinary types that only support the operations permitted by the
contracts.
Type inference via a unification algorithm is supported to permit
omitting type arguments from function calls in many cases.
Depending on a detail, the design can be fully backward compatible
with Go 1.
-For more context, see the [generics problem overview](go2draft-generics-overview.md).
-
## Background
+This version of the design draft is similar to the one presented on
+August 27, 2018, except that the syntax of contracts is completely
+different.
+
There have been many [requests to add additional support for generic
-programming](https://golang.org/wiki/ExperienceReports#generics)
+programming](https://github.com/golang/go/wiki/ExperienceReports#generics)
in Go.
-There has been extensive discussion on
-[the issue tracker](https://golang.org/issue/15292) and on
-[a living document](https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4/view).
+There has been extensive discussion on [the issue tracker]
+(https://golang.org/issue/15292) and on [a living document]
+(https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4/view).
There have been several proposals for adding type parameters, which
-can be found by looking through the links above.
+can be found through the links above.
Many of the ideas presented here have appeared before.
The main new features described here are the syntax and the careful
examination of contracts.
-This draft design suggests extending the Go language to add a form of
+This design draft suggests extending the Go language to add a form of
parametric polymorphism, where the type parameters are bounded not by
a subtyping relationship but by explicitly defined structural
constraints.
-Among other languages that support parametric polymorphism this
-design is perhaps most similar to CLU or Ada, although the syntax is
+Among other languages that support parameteric polymorphism this
+design is perhaps most similar to Ada, although the syntax is
completely different.
-Contracts also somewhat resemble C++ concepts.
This design does not support template metaprogramming or any other
-form of compile-time programming.
+form of compile time programming.
As the term _generic_ is widely used in the Go community, we will
use it below as a shorthand to mean a function or type that takes type
parameters.
-Don’t confuse the term generic as used in this design with the same
+Don't confuse the term generic as used in this design with the same
term in other languages like C++, C#, Java, or Rust; they have
-similarities but are not always the same.
+similarities but are not the same.
## Design
@@ -61,7 +62,8 @@
Generic code is code that is written using types that will be
specified later.
Each unspecified type is called a _type parameter_.
-When the code is used the type parameter is set to a _type argument_.
+When running the generic code, the type parameter will be set to a
+_type argument_.
Here is a function that prints out each element of a slice, where the
element type of the slice, here called `T`, is unknown.
@@ -78,7 +80,7 @@
}
```
-As you can see, the first decision to make is: how should the type
+With this approach, the first decision to make is: how should the type
parameter `T` be declared?
In a language like Go, we expect every identifier to be declared in
some way.
@@ -87,11 +89,12 @@
ordinary non-type function parameters, and as such should be listed
along with other parameters.
However, type parameters are not the same as non-type parameters, so
-although they appear in the parameters we want to distinguish them.
+although they appear in the list of parameters we want to distinguish
+them.
That leads to our next design decision: we define an additional,
optional, parameter list, describing type parameters.
This parameter list appears before the regular parameters.
-It starts with the keyword `type` and lists type parameters.
+It starts with the keyword `type`, and lists type parameters.
```Go
func Print(type T)(s []T) {
@@ -107,7 +110,7 @@
type argument.
Type arguments are passed much like type parameters are declared: as a
separate list of arguments.
-At the call site, the `type` keyword is not used.
+At the call site, the `type` keyword is not required.
```Go
Print(int)([]int{1, 2, 3})
@@ -115,11 +118,12 @@
### Type contracts
-Let’s make our example slightly more complicated.
-Let’s turn it into a function that converts a slice of any type into a
+Let's make our example slightly more complicated.
+Let's turn it into a function that converts a slice of any type into a
`[]string` by calling a `String` method on each element.
```Go
+// This function is INVALID.
func Stringify(type T)(s []T) (ret []string) {
for _, v := range s {
ret = append(ret, v.String()) // INVALID
@@ -129,9 +133,9 @@
```
This might seem OK at first glance, but in this example, `v` has type
-`T`, and we don’t know anything about `T`.
-In particular, we don’t know that `T` has a `String` method.
-So the call `v.String()` is invalid.
+`T`, and we don't know anything about `T`.
+In particular, we don't know that `T` has a `String` method.
+So the call to `v.String()` is invalid.
Naturally, the same issue arises in other languages that support
generic programming.
@@ -146,7 +150,7 @@
The C++ approach would be a poor choice for Go.
One reason is the style of the language.
-In Go we don’t refer to names, such as, in this case, `String`, and
+In Go we don't refer to names, such as, in this case, `String`, and
hope that they exist.
Go resolves all names to their declarations when they are seen.
@@ -155,17 +159,17 @@
We must consider the case in which the generic function definition
(`Stringify`, above) and the call to the generic function (not shown,
but perhaps in some other package) are far apart.
-In general, all generic code has a contract that type arguments need
-to implement.
+In general, all generic code implies a contract that type arguments
+need to implement.
In this case, the contract is pretty obvious: the type has to have a
`String() string` method.
In other cases it may be much less obvious.
-We don’t want to derive the contract from whatever `Stringify` happens
+We don't want to derive the contract from whatever `Stringify` happens
to do.
If we did, a minor change to `Stringify` might change the contract.
That would mean that a minor change could cause code far away, that
calls the function, to unexpectedly break.
-It’s fine for `Stringify` to deliberately change its contract, and
+It's fine for `Stringify` to deliberately change its contract, and
force users to change.
What we want to avoid is `Stringify` changing its contract
accidentally.
@@ -174,26 +178,31 @@
to define generic programming in Go: there should be an explicit
contract between the generic code and calling code.
-### Contract syntax
+### Contract introduction
-In this design, a contract has the same general form as a function.
-The function body is never executed.
-Instead, it describes, by example, a set of types.
+In this design, a contract describes the requirements of a set of
+types.
+We'll discuss contracts further later, but for now we'll just say that
+one of the things that a contract can do is specify that a type
+argument must implement a particular method.
For the `Stringify` example, we need to write a contract that says
-that the type has a `String` method that takes no arguments and
-returns a value of type `string`.
-Here is one way to write that:
+that the single type parameter has a `String` method that takes no
+arguments and returns a value of type `string`.
+We write that like this:
```Go
-contract stringer(x T) {
- var s string = x.String()
+contract stringer(T) {
+ T String() string
}
```
-A contract is introduced with a new keyword `contract`.
-The definition of a contract looks like the definition of a function,
-except that the parameter types must be simple identifiers.
+A contract is introduced with a new keyword `contract`, followed by a
+name and a list of identifiers.
+The identifiers name the types that the contract will specify.
+Specifying a required method looks like defining a method in an
+interface type, except that the receiver type must be explicitly
+provided.
### Using a contract to verify type arguments
@@ -203,26 +212,13 @@
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.
+If the type arguments don't satisfy the requirements specified by the
+contract, the compiler will report a type error: the call is using
+types that the function's contract does not permit.
-To validate the type arguments, each of the contract’s parameter types
-is replaced with the corresponding type argument (there must be
-exactly as many type arguments as there are parameter types; contracts
-may not be variadic).
-The body of the contract is then type checked as though it were an
-ordinary function.
-If the type checking succeeds, the type arguments are valid.
-
-In the example of the `stringer` contract seen earlier, we can see
-that the type argument used for `T` must have a `String` method (or it
-must be a struct with a `String` field of function type).
-The `String` method must not take any arguments, and it must return a
-value of a type that is assignable to `string`. (As it happens, the
-only type assignable to `string` is, in fact, `string`.)
-If any of those statements about the type argument are not true, the
-contract body will fail when it is type checked.
+The `stringer` contract seen earlier requires that the type argument
+used for `T` has a `String` method that takes no arguments and
+returns a value of type `string`.
### The party of the second part
@@ -244,23 +240,17 @@
that type
If the function wants to take any more specific action with the type
-parameter, or a value of the type parameter, the contract must permit
-it.
-Basically, if the contract body uses a type in a certain way, the
-actual function is permitted to use the type in the same way.
-This is described in more detail later.
-For now, look at the `stringer` contract example above.
-The single statement in the contract body shows that given a value of
-type `T`, the function using the `stringer` contract is permitted to
-call a method of type `String`, passing no arguments, to get a value
-of type `string`.
+parameter, or a value of the type parameter, the contract must
+explicitly support that action.
+In the `stringer` example seen earlier, the contract provides the
+ability to call a method `String` on a value of the type parameter.
That is, naturally, exactly the operation that the `Stringify`
function needs.
### Using a contract
-We’ve seen how the `stringer` contract can be used to verify that a
-type argument is suitable for the `Stringify` function, and we’ve seen
+We've seen how the `stringer` contract can be used to verify that a
+type argument is suitable for the `Stringify` function, and we've seen
how the contract permits the `Stringify` function to call the `String`
method that it needs.
The final step is showing how the `Stringify` function uses the
@@ -277,131 +267,19 @@
}
```
-The list of type parameters (in this case, a list of one element) is
-followed by an optional contract name.
-The contract must have the same number of parameters as the function
-has type parameters; when validating the contract, the type parameters
-are passed to the function in the order in which they appear in the
-function definition.
-
-### Contract syntactic details
-
-Before we continue, let’s cover a few details of the contract syntax.
-
-#### Passing explicit types to a contract
-
-Although the normal case is for a function to validate the contract
-with its exact list of type parameters, the contract can also be used
-with a different set of types.
-
-For example, this simple contract says that a value of type `From` may
-be converted to the type `To`.
-
-```Go
-contract convertible(_ To, f From) {
- To(f)
-}
-```
-
-Note that this contract body is quite simple.
-It is a single statement expression that consists of a conversion
-expression.
-Since the contract body is never executed, it doesn’t matter that the
-result of the conversion is not assigned to anything.
-All that matters is whether the conversion expressed can be type
-checked.
-
-For example, this contract would permit the type arguments `(int64,
-int32)` but would forbid the type arguments `([]int, complex64)`.
-
-Given this contract, we can write this function, which may be invoked
-with any type that can be converted to `uint64`.
-
-```Go
-func FormatUnsigned(type T convertible(uint64, T))(v T) string {
- return strconv.FormatUint(uint64(v), 10)
-}
-```
-
-This could be called as, for example,
-
-```Go
- s := FormatUnsigned(rune)('a')
-```
-
-This isn’t too useful with what we’ve described so far, but it will be
-a bit more convenient when we get to type inference.
-
-#### Restrictions on contract bodies
-
-Although a contract looks like a function body, contracts may not
-themselves have type parameters.
-Contracts may also not have result parameters, and it follows that
-they may not use a `return` statement to return values.
-
-The body of a contract may not refer to any name defined in the
-current package.
-This rule is intended to make it harder to accidentally change the
-meaning of a contract.
-As a compromise, a contract is permitted to refer to names imported
-from other packages, permitting a contract to easily say things like
-"this type must support the `io.Reader` interface:"
-
-```Go
-contract Readable(r T) {
- io.Reader(r)
-}
-```
-
-It is likely that this rule will have to be adjusted as we gain more
-experience with this design.
-For example, perhaps we should permit contracts to refer to exported
-names defined in the same package, but not unexported names.
-Or maybe we should have no such restriction and just rely on
-correct programming supported by tooling.
-
-As contract bodies are not executed, there are no restrictions about
-unreachable statements, or `goto` statements across declarations, or
-anything along those lines.
-
-Of course, it is completely pointless to use a `goto` statement, or a
-`break`, `continue`, or `fallthrough` statement, in a contract body,
-as these statements do not say anything about the type arguments.
-
-#### The contract keyword
-
-Contracts may only appear at the top level of a package.
-
-While contracts could be defined to work within the body of a
-function, it’s hard to think of realistic examples in which they would
-be useful.
-We see this as similar to the way that methods can not be defined
-within the body of a function.
-A minor point is that only permitting contracts at the top level
-permits the design to be Go 1 compatible.
-
-There are a few ways to handle the syntax:
-
-* We could make `contract` be a keyword only at the start of a
- top-level declaration, and otherwise be a normal identifier.
-* We could declare that if you use `contract` at the start of a
- top-level declaration, then it becomes a keyword for the duration of
- that package.
-* We could make `contract` always be a keyword, albeit one that can
- only appear in one place, in which case this design is not Go 1
- compatible.
-
-#### Exported contracts
-
-Like other top level declarations, a contract is exported if its name
-starts with an upper-case letter.
-An exported contract may be used by functions, types, or contracts in other
-packages.
+The list of type parameters (in this case, a list with the single
+element `T`) is followed by an optional contract name.
+When just the contract name is listed, as above, the contract must
+have the same number of parameters as the function has type
+parameters; when validating the contract, the type parameters are
+passed to the contract in the order in which they appear in the
+function signature.
+Later we'll discuss passing explicit type parameters to the contract.
### Multiple type parameters
-Although the examples shown so far only use a single type parameter,
-naturally functions may have multiple type parameters.
+Although the examples we've seen so far use only a single type
+parameter, functions may have multiple type parameters.
```Go
func Print2(type T1, T2)(s1 []T1, s2 []T2) { ... }
@@ -421,9 +299,9 @@
have a single contract.
```Go
-contract viaStrings(t To, f From) {
- var x string = f.String()
- t.Set(string("")) // could also use t.Set(x)
+contract viaStrings(To, From) {
+ To Set(string)
+ From String() string
}
func SetViaStrings(type To, From viaStrings)(s []From) []To {
@@ -444,7 +322,7 @@
type Vector(type Element) []Element
```
-A type’s parameters are just like a function’s type parameters.
+A type's parameters are just like a function's type parameters.
Within the type definition, the type parameters may be used like any
other type.
@@ -468,8 +346,8 @@
A parameterized type can refer to itself in cases where a type can
ordinarily refer to itself, but when it does so the type arguments
-must be the type parameters.
-This restriction avoids an infinite recursion of type instantiation.
+must be the type parameters, listed in the same order.
+This restriction prevents infinite recursion of type instantiation.
```Go
// This is OK.
@@ -478,15 +356,34 @@
val Element
}
-// This is INVALID.
+// This type is INVALID.
type P(type Element1, Element2) struct {
F *P(Element2, Element1) // INVALID; must be (Element1, Element2)
}
```
(Note: with more understanding of how people want to write code, it
-may be possible to relax the reference rule to permit some cases that
-use different type arguments.)
+may be possible to relax this rule to permit some cases that use
+different type arguments.)
+
+The type parameter of a parameterized type may have contracts.
+
+```Go
+type StringableVector(type T stringer) []T
+
+func (s StringableVector(T)) String() string {
+ var sb strings.Builder
+ sb.WriteString("[")
+ for i, v := range s {
+ if i > 0 {
+ sb.WriteString(", ")
+ }
+ sb.WriteString(v.String())
+ }
+ sb.WriteString("]")
+ return sb.String()
+}
+```
When a parameterized type is a struct, and the type parameter is
embedded as a field in the struct, the name of the field is the name
@@ -505,26 +402,11 @@
}
```
-(Note: this works poorly if you write `Lockable(X)` in the method
-declaration: should the method return `l.T` or `l.X`?
-Perhaps we should simply ban embedding a type parameter in a struct.)
-
### Parameterized type aliases
-Type aliases may have parameters.
-
-```Go
-type Ptr(type Target) = *Target
-```
-
-Type aliases may refer to parameterized types, in which case any uses
-of the type alias (other than in another type alias declaration) must
-provide type arguments.
-
-```Go
-type V = Vector
-var v2 V(int)
-```
+Type aliases may not have parameters.
+This restriction exists because it is unclear how to handle a type
+alias with type parameters that have a contract.
Type aliases may refer to instantiated types.
@@ -532,16 +414,19 @@
type VectorInt = Vector(int)
```
+If a type alias refers to a parameterized type, it must provide type
+arguments.
+
### Methods may not take additional type arguments
-Although methods of a parameterized type may use the type’s
-parameters, methods may not themselves have (additional) type
+Although methods of a parameterized type may use the type's
+parameters, methods may not themselves have additional type
parameters.
Where it would be useful to add type arguments to a method, people
-will have to write a top-level function.
+will have to write a suitably parameterized top-level function.
-Making this decision avoids having to specify the details of exactly
-when a method with type arguments implements an interface.
+This restriction avoids having to specify the details of exactly when
+a method with type arguments implements an interface.
(This is a feature that can perhaps be added later if it proves
necessary.)
@@ -549,56 +434,50 @@
A contract may embed another contract, by listing it in the
contract body with type arguments.
-This will look like a function call in the contract body, but since
-the call is to a contract it is handled as if the called contract’s
-body were embedded in the calling contract, with the called contract’s
-type parameters replaced by the type arguments provided in the
-contract call.
+This will look a bit like a method definition in the contract body,
+but it will be different because there will be no receiver type.
+It is handled as if the embedded contract's body were placed into the
+calling contract, with the embedded contract's type parameters
+replaced by the embedded type arguments.
This contract embeds the contract `stringer` defined earlier.
```Go
-contract PrintStringer(x X) {
+contract PrintStringer(X) {
stringer(X)
- x.Print()
+ X Print()
}
```
-This is roughly equivalent to
+This is equivalent to
```Go
-contract PrintStringer(x X) {
- var s string = x.String()
- x.Print()
+contract PrintStringer(X) {
+ X string() string
+ X Print()
}
```
-It’s not exactly equivalent: the contract can’t refer to the variable
-`s` after embedding `stringer(X)`.
-
### Using types that refer to themselves in contracts
-Although this is implied by what has already been discussed, it’s
+Although this is implied by what has already been discussed, it's
worth pointing out explicitly that a contract may require a method to
-have an argument whose type is one of the contract’s type parameters.
+have an argument whose type is the same as the method's receiver
+type.
```Go
-package comparable
+package compare
-// The equal contract describes types that have an Equal method for
-// the same type.
-contract equal(v T) {
- // All that matters is type checking, so reusing v as the argument
- // means that the type argument must have a Equal method such that
- // the type argument itself is assignable to the Equal method’s
- // parameter type.
- var x bool = v.Equal(v)
+// The equal contract describes types that have an Equal method with
+// an argument of the same type as the receiver type.
+contract equal(T) {
+ T Equal(T) bool
}
// Index returns the index of e in s, or -1.
func Index(type T equal)(s []T, e T) int {
for i, v := range s {
- // Both e and v are type T, so it’s OK to call e.Equal(v).
+ // Both e and v are type T, so it's OK to call e.Equal(v).
if e.Equal(v) {
return i
}
@@ -608,32 +487,33 @@
```
This function can be used with any type that has an `Equal` method
-whose single parameter type is the type itself.
+whose single parameter type is the same as the receiver type.
```Go
-import "comparable"
+import "compare"
type EqualInt int
-// The Equal method lets EqualInt implement the comparable.equal contract.
+// The Equal method lets EqualInt satisfy the compare.equal contract.
func (a EqualInt) Equal(b EqualInt) bool { return a == b }
func Index(s []EqualInt, e EqualInt) int {
- return comparable.Index(EqualInt)(s, e)
+ return compare.Index(EqualInt)(s, e)
}
```
-In this example, when we pass `EqualInt` to `comparable.Index`, we
-check whether `EqualInt` satisfies the contract `comparable.equal`.
-We replace `T` in the body of `comparable.equal` with `EqualInt`, and
-see whether the result type checks.
+In this example, when we pass `EqualInt` to `compare.Index`, we
+check whether `EqualInt` satisfies the contract `compare.equal`.
+We replace `T` with `EqualInt` in the declaration of the `Equal`
+method in the `equal` contract, and see whether `EqualInt` has a
+matching method.
`EqualInt` has a method `Equal` that accepts a parameter of type
`EqualInt`, so all is well, and the compilation succeeds.
-### Mutually referential type parameters
+### Mutually referencing type parameters
-Within a contract body, expressions may arbitrarily combine values of
-any type parameter.
+Within a contract, methods may refer to any of the contract's type
+parameters.
For example, consider a generic graph package that contains generic
algorithms that work with graphs.
@@ -648,23 +528,22 @@
```Go
package graph
-contract G(n Node, e Edge) {
- var _ []Edge = n.Edges()
- var from, to Node = e.Nodes()
+contract G(Node, Edge) {
+ Node Edges() []Edge
+ Edge Nodes() (from Node, to Node)
}
type Graph(type Node, Edge G) struct { ... }
func New(type Node, Edge G)(nodes []Node) *Graph(Node, Edge) { ... }
-func (*Graph(Node, Edge)) ShortestPath(from, to Node) []Edge { ... }
+func (g *Graph(Node, Edge)) ShortestPath(from, to Node) []Edge { ... }
```
-At first glance it might be hard to see how this differs from similar
-code using interface types.
-The difference is that although `Node` and `Edge` have specific
-methods, they are not interface types.
+While at first glance this may look like a typical use of interface
+types, `Node` and `Edge` are non-interface types with specific
+methods.
In order to use `graph.Graph`, the type arguments used for `Node` and
`Edge` have to define methods that follow a certain pattern, but they
-don’t have to actually use interface types to do so.
+don't have to actually use interface types to do so.
For example, consider these type definitions in some other package:
@@ -684,10 +563,8 @@
`*Vertex` and `*FromTo` are not interface types, but when used
together they define methods that implement the contract `graph.G`.
-Because of the way that the contract is written, we could also use the
-non-pointer types `Vertex` and `FromTo`; the contract implies that the
-function body will always be able to take the address of the argument
-if necessary, and so will always be able to call the pointer method.
+Note that we couldn't use plain `Vertex` or `FromTo`, since the
+required methods are pointer methods, not value methods.
Although `Node` and `Edge` do not have to be instantiated with
interface types, it is also OK to use interface types if you like.
@@ -699,7 +576,7 @@
We could instantiate `graph.Graph` with the types `NodeInterface` and
`EdgeInterface`, since they implement the `graph.G` contract.
-There isn’t much reason to instantiate a type this way, but it is
+There isn't much reason to instantiate a type this way, but it is
permitted.
This ability for type parameters to refer to other type parameters
@@ -708,6 +585,63 @@
generic code with multiple type arguments that refer to each other in
ways that the compiler can check.
+As it is a common observation that contracts share some
+characteristics of interface types, it's worth stressing that this
+capability is one that contracts provide but interface types do not.
+
+### Passing parameters to a contract
+
+As mentioned earlier, by default the type parameters are passed to the
+contract in the order in which they appear in the function signature.
+It is also possible to explicitly pass type parameters to a contract
+as though they were arguments.
+This is useful if the contract and the generic function take type
+parameters in a different order, or if only some parameters need a
+contract.
+
+In this example the type parameter `E` can be any type, but the type
+parameter `M` must implement the `String` method.
+The function passes just `M` to the `stringer` contract, leaving `E`
+as though it had no constraints.
+
+```Go
+func MapAndPrint(type E, M stringer(M))(s []E, f(E) M) []string {
+ r := make([]string, len(s))
+ for i, v := range s {
+ r[i] = f(v).String()
+ }
+ return r
+}
+```
+
+### Contract syntactic details
+
+Contracts may only appear at the top level of a package.
+
+While contracts could be defined to work within the body of a
+function, it's hard to think of realistic examples in which they would
+be useful.
+We see this as similar to the way that methods can not be defined
+within the body of a function.
+A minor point is that only permitting contracts at the top level
+permits the design to be Go 1 compatible.
+
+There are a few ways to handle the syntax:
+
+* We could make `contract` be a keyword only at the start of a
+ top-level declaration, and otherwise be a normal identifier.
+* We could declare that if you use `contract` at the start of a
+ top-level declaration, then it becomes a keyword for the entire
+ package.
+* We could make `contract` always be a keyword, albeit one that can
+ only appear in one place, in which case this design is not Go 1
+ compatible.
+
+Like other top level declarations, a contract is exported if its name
+starts with an uppercase letter.
+If exported it may be used by functions, types, or contracts in other
+packages.
+
### Values of type parameters are not boxed
In the current implementations of Go, interface values always hold
@@ -717,16 +651,16 @@
That means that the actual value is stored somewhere else, on the heap
or stack, and the interface value holds a pointer to that location.
-In contrast to interface values, values of instantiated polymorphic types are not boxed.
-For example, let’s consider a function that works for any type `T`
+In this design, values of generic types are not boxed.
+For example, let's consider a function that works for any type `T`
with a `Set(string)` method that initializes the value based on a
string, and uses it to convert a slice of `string` to a slice of `T`.
```Go
package from
-contract setter(x T) {
- var _ error = x.Set(string)
+contract setter(T) {
+ T Set(string) error
}
func Strings(type T setter)(s []string) ([]T, error) {
@@ -740,7 +674,7 @@
}
```
-Now let’s see some code in a different package.
+Now let's see some code in a different package.
```Go
type Settable int
@@ -753,6 +687,7 @@
func F() {
// The type of nums is []Settable.
nums, err := from.Strings(Settable)([]string{"1", "2"})
+ if err != nil { ... }
// Settable can be converted directly to int.
// This will set first to 1.
first := int(nums[0])
@@ -768,7 +703,7 @@
set by a generic function.
Similarly, when a parameterized type is instantiated it will have the
-expected types as fields.
+expected types as components.
```Go
package pair
@@ -799,31 +734,31 @@
The type argument `int` in the function call can be inferred from the
type of the non-type argument.
-This can only be done when all the function’s type parameters are used
-for the types of the function’s (non-type) input parameters.
+This can only be done when all the function's type parameters are used
+for the types of the function's (non-type) input parameters.
If there are some type parameters that are used only for the
-function’s result parameter types, or only in the body of the
+function's result parameter types, or only in the body of the
function, then it is not possible to infer the type arguments for the
-function.
+function, since there is no value from which to infer the types.
For example, when calling `from.Strings` as defined earlier, the type
-parameters cannot be inferred because the function’s type parameter
+parameters cannot be inferred because the function's type parameter
`T` is not used for an input parameter, only for a result.
-When the function’s type arguments can be inferred, the language uses
+When the function's type arguments can be inferred, the language uses
type unification.
On the caller side we have the list of types of the actual (non-type)
arguments, which for the `Print` example here is simply `[]int`.
-On the function side is the list of the types of the function’s
+On the function side is the list of the types of the function's
non-type parameters, which here is `[]T`.
-In the lists, we discard arguments for which the function side does
-not use a type parameter.
+In the lists, we discard respective arguments for which the function
+side does not use a type parameter.
We must then unify the remaining argument types.
Type unification is a two pass algorithm.
-In the first pass, untyped constants on the caller side, and their
-corresponding types in the function definition, are ignored.
+In the first pass, we ignore untyped constants on the caller side and
+their corresponding types in the function definition.
-Corresponding types in the lists are compared.
+We compare corresponding types in the lists.
Their structure must be identical, except that type parameters on the
function side match the type that appears on the caller side at the
point where the type parameter occurs.
@@ -832,16 +767,17 @@
Those caller types must be identical, or type unification fails, and
we report an error.
-After the first pass, check any untyped constants on the caller side.
+After the first pass, we check any untyped constants on the caller
+side.
If there are no untyped constants, or if the type parameters in the
corresponding function types have matched other input types, then
type unification is complete.
Otherwise, for the second pass, for any untyped constants whose
-corresponding function types are not yet set, determine the default
+corresponding function types are not yet set, we determine the default
type of the untyped constant in [the usual
way](https://golang.org/ref/spec#Constants).
-Then run the type unification algorithm again, this time with no
+Then we run the type unification algorithm again, this time with no
untyped constants.
In this example
@@ -882,8 +818,8 @@
with `func(From) To`, matching `From` with `int` and `To` with
`string`.
`From` is matched twice, both times with `int`.
-Unification succeeds, changing the call from `transform.Slice` to
-`transform.Slice(int, string)`.
+Unification succeeds, so the call written as `transform.Slice` is a
+call of `transform.Slice(int, string)`.
To see the untyped constant rule in effect, consider
@@ -929,19 +865,19 @@
functionality to the design, only convenience in using it.
It would be possible to omit it from the initial implementation, and
see whether it seems to be needed.
-That said, this feature doesn’t require additional syntax, and is
+That said, this feature doesn't require additional syntax, and is
likely to significantly reduce the stutter of repeated type arguments
in code.)
-(Note: We could also consider supporting type inference in composite
-literals.
+(Note: We could also consider supporting type inference for
+composite literals of parameterized types.
```Go
type Pair(type T) struct { f1, f2 T }
var V = Pair{1, 2} // inferred as Pair(int){1, 2}
```
-It’s not clear how often this will arise in real code.)
+It's not clear how often this will arise in real code.)
### Instantiating a function
@@ -954,7 +890,7 @@
This will produce an ordinary function value with no type parameters.
```Go
-// PrintInts will have type func([]int).
+// PrintInts will be type func([]int).
var PrintInts = Print(int)
```
@@ -962,30 +898,28 @@
A useful function with type parameters will support any type argument
that implements the contract.
-Sometimes, though, it’s possible to use a more efficient
-implementation for some type arguments.
+Sometimes, though, it's possible to use a more efficient
+function implementation for some type arguments.
The language already has mechanisms for code to find out what type it
is working with: type assertions and type switches.
Those are normally only permitted with interface types.
In this design, functions are also permitted to use them with values
-whose types are type parameters, or based on type parameters.
+whose types are type parameters, or are based on type parameters.
-This doesn’t add any functionality, as the function could get the same
+This doesn't add any functionality, as the function could get the same
information using the reflect package.
-It’s merely occasionally convenient, and it may result in more
+It's merely occasionally convenient, and it may result in more
efficient code.
For example, this code is permitted even if it is called with a type
argument that is not an interface type.
```Go
-contract byteReader(x T) {
- // This expression says that x is convertible to io.Reader, or,
- // in other words, that x has a method Read([]byte) (int, error).
- io.Reader(x)
+contract reader(T) {
+ T Read([]byte) (int, error)
}
-func ReadByte(type T byteReader)(r T) (byte, error) {
+func ReadByte(type T reader)(r T) (byte, error) {
if br, ok := r.(io.ByteReader); ok {
return br.ReadByte()
}
@@ -1010,22 +944,46 @@
The second case is a composite literal of type `[]T(v2)`, where `T` is
a parameterized type that we are instantiating with the type argument
`v2`.
-The ambiguity is at the point where we see the parenthesis: at that
-point the parser doesn’t know whether it is seeing a type conversion
-or something like a composite literal.
+The ambiguity is at the point where we see the open parenthesis: at
+that point the parser doesn't know whether it is seeing a type
+conversion or something like a composite literal.
To avoid this ambiguity, we require that type instantiations at the
end of a type literal be parenthesized.
-In other words, we always parse `[]T(v1)` as a type conversion, not as
-a potential instantiation of `T`.
To write a type literal that is a slice of a type instantiation, you
must write `[](T(v1))`.
+Without those parentheses, `[]T(x)` is parsed as `([]T)(x)`, not as
+`[](T(x))`.
This only applies to slice, array, map, chan, and func type literals
ending in a type name.
Of course it is always possible to use a separate type declaration to
give a name to the instantiated type, and to use that.
This is only an issue when the type is instantiated in place.
+### Using parameterized types as unnamed function parameter types
+
+When parsing a parameterized type as an unnamed function parameter
+type, there is a parsing ambiguity.
+
+```Go
+var f func(x(T))
+```
+
+In this example we don't know whether the function has a single
+unnamed parameter of the parameterized type `x(T)`, or whether this is
+a named parameter `x` of the type `(T)` (written with parentheses).
+
+For backward compatibility, we treat this as the latter case: `x(T)`
+is a parameter `x` of type `(T)`.
+In order to describe a function with a single unnamed parameter of
+type `x(T)`, either the parameter must be named, or extra parentheses
+must be used.
+
+```Go
+var f1 func(_ x(T))
+var f2 func((x(T)))
+```
+
### Reflection
We do not propose to change the reflect package in any way.
@@ -1035,201 +993,454 @@
will return the name with the type arguments in parentheses.
For example, `List(int)`.
-It’s impossible for non-generic code to refer to generic code without
+It's impossible for non-generic code to refer to generic code without
instantiating it, so there is no reflection information for
uninstantiated generic types or functions.
### Contracts details
-Let’s take a deeper look at contracts.
+Let's take a deeper look at contracts.
Operations on values whose type is a type parameter must be permitted
-by the type parameter’s contract.
+by the type parameter's contract.
This means that the power of generic functions is tied precisely to
the interpretation of the contract body.
It also means that the language requires a precise definition of the
operations that are permitted by a given contract.
-The general guideline is straightforward: if a statement appears in a
-contract, then that same statement may appear in a function using that
-contract.
-However, that guideline is clearly too limiting; it essentially
-requires that the function body be copied into the contract body,
-which makes the contract pointless.
-Therefore, what needs to be clearly spelled out is the ways in which a
-statement in a contract body can permit other kinds of expressions or
-statements in the function body.
-We don’t need to explain the meaning of every statement that can
-appear in a contract body, only the ones that permit operations other
-than an exact copy of the statement.
-
#### Methods
-All the contracts we’ve seen so far show only method calls and type
-conversions in the contract body.
+All the contracts we've seen so far show only method calls in the
+contract body.
If a method call appears in the contract body, that method may be
-called on an addressable value in any statement or expression in the
-function body.
-It will take argument and result types as shown in the contract body.
+called on a value in any statement or expression in the function
+body.
+It will take argument and result types as specified in the contract
+body.
-The examples above use `var` declarations to specify the types of the
-result parameters.
-While it is valid to use a short declaration like `s := x.String()` in
-a contract body, such a declaration says nothing about the result
-type.
-This would match a type argument with a `String` method that returns a
-single result of any type.
-It would not permit the function using the contract to use the result
-of `x.String()`, since the type would not be known.
+In order to avoid worrying about the distinction between value methods
+and pointer methods, in a generic function body all method calls will
+be pointer method calls.
+If necessary, the function body will insert temporary variables,
+not seen by the user, in order to get an addressable variable to use
+to call the method.
-There are a few aspects to a method call that can not be shown in a
-simple assignment statement like the ones shown above.
-
-* There is no way to specify that a method does not return any
- values.
-* There is no way to specify that a method takes variadic arguments.
-* There is no way to distinguish a method call from a call of a struct
- field with function type.
-
-When a contract needs to describe one of these cases, it can use a
-type conversion to an interface type.
-The interface type permits the method to be precisely described.
-If the conversion to the interface type passes the type checker, then
-the type argument must have a method of that exact type.
-
-An explicit method call, or a conversion to an interface type, can not
-be used to distinguish a pointer method from a value method.
-When the function body calls a method on an addressable value, this
-doesn’t matter; since all value methods are part of the pointer type’s
-method set, an addressable value can call either pointer methods or
-value methods.
-
-However, it is possible to write a function body that can only call
-a value method, not a pointer method. For example:
+For example, this code is valid, even though `LookupAsString` calls
+`String` in a context that requires a value method, and `MyInt` only
+has a pointer method.
```Go
-contract adjustable(x T) {
- var _ T = x.Adjust()
- x.Apply()
+func LookupAsString(type T stringer)(m map[int]T, k int) string {
+ return m[k].String() // Note: calls method on value of type T
}
-func Apply(type T adjustable)(v T) {
- v.Adjust().Apply() // INVALID
+type MyInt int
+func (p *MyInt) String() { return strconv.Itoa(int(*p)) }
+func F(m map[int]MyInt) string {
+ return LookupAsString(MyInt)(m, 0)
}
```
-In this example, the `Apply` method is not called on an addressable
-value.
-This can only work if the `Apply` method is a value method.
-But writing `x.Apply()` in the contract permits a pointer method.
-
-In order to use a value method in the function body, the contract must
-express that the type has a value method rather than a pointer
-method.
-That can be done like this:
-
-```Go
-contract adjustable(x T) {
- var _ T = x.Adjust()
- var f func() T
- f().Apply()
-}
-```
-
-The rule is that if the contract body contains a method call on a
-non-addressable value, then the function body may call the method on a
-non-addressable value.
+This makes it easier to understand which types satisfy a contract, and
+how a contract may be used.
+It has the drawback that in some cases a pointer method that modifies
+the value to which the receiver points may be called on a temporary
+variable that is discarded after the method completes.
+It may be possible to add a vet warning for a case where a generic
+function uses a temporary variable for a method call and the function
+is instantiated with a type that has only a pointer method, not a
+value method.
#### Operators
Method calls are not sufficient for everything we want to express.
-Consider this simple function that reports whether a parameterized
-slice contains an element.
+Consider this simple function that returns the smallest element of a
+slice of values, where the slice is assumed to be non-empty.
```Go
-func Contains(type T)(s []T, e T) bool {
- for _, v := range s {
- if v == e { // INVALID
- return true
+// This function is INVALID.
+func Smallest(type T)(s []T) T {
+ r := s[0] // panics if slice is empty
+ for _, v := range s[1:] {
+ if v < r { // INVALID
+ r = v
}
}
- return false
+ return r
}
```
Any reasonable generics implementation should let you write this
function.
-The problem is the expression `v == e`.
-That assumes that `T` supports the `==` operator, but there is no
+The problem is the expression `v < r`.
+This assumes that `T` supports the `<` operator, but there is no
contract requiring that.
Without a contract the function body can only use operations that are
-available for all types, but not all Go types support `==` (you can
-not use `==` to compare values of slice, map, or function type).
+available for all types, but not all Go types support `<`.
-This is easy to address using a contract.
+It follows that we need a way to write a contract that accepts only
+types that support `<`.
+In order to do that, we observe that, aside from two exceptions that
+we will discuss later, all the arithmetic, comparison, and logical
+operators defined by the language may only be used with types that are
+predeclared by the language, or with defined types whose underlying
+type is one of those predeclared types.
+That is, the operator `<` can only be used with a predeclared type
+such as `int` or `float64`, or a defined type whose underlying type is
+one of those types.
+Go does not permit using `<` with an aggregate type or with an
+arbitrary defined type.
+
+This means that rather than try to write a contract for `<`, we can
+approach this the other way around: instead of saying which operators
+a contract should support, we can say which (underlying) types a
+contract should accept.
+
+#### Types in contracts
+
+A contract may list explicit types that may be used as type
+arguments.
+These are expressed in the form `type-parameter-name type, type...`.
+The `type` must be a predeclared type, such as `int`, or an aggregate
+as discussed below.
+For example,
```Go
-contract comparable(x T) {
- x == x
-}
-
-func Contains(type T comparable)(s []T, e T) bool {
- for _, v := range s {
- if v == e { // now valid
- return true
- }
- }
- return false
+constract SignedInteger(T) {
+ T int, int8, int16, int32, int64
}
```
-In general, using an operator in the contract body permits using the
-same operator with the same types anywhere in the function body.
+This contract specifies that the type argument must be one of the
+listed types (`int`, `int8`, and so forth), or it must be a defined
+type whose underlying type is one of the listed types.
-For convenience, some operators also permit additional operations.
+When a parameterized function using this contract has a value of type
+`T`, it may use any operation that is permitted by all of the listed
+types.
+This can be an operation like `<`, or for aggregate types an operation
+like `range` or `<-`.
+If the function can be compiled successfully using each type listed in
+the contract, then the operation is permitted.
-Using a binary operator in the contract body permits not only using
-that operator by itself, but also the assignment version with `=`
-appended if that exists.
-That is, an expression like `x * x` in a contract body means that
-generic code, given variables `a` and `b` of the type of `x`, may
-write `a * b` and may also write `a *= b`.
+For the `Smallest` example shown earlier, we could use a contract like
+this:
-Using the `==` operator with values of some type as both the left and
-right operands means that the type must be comparable, and implies
-that both `==` and `!=` may be used with values of that type.
-Similarly, `!=` permits `==`.
+```Go
+contract Ordered(T) {
+ T int, int8, int16, int32, int64,
+ uint, uint8, uint16, uint32, uint64, uintptr
+ float32, float64,
+ string
+}
+```
-Using the `<` operator with values of some type as both the left and
-right operators means that the type must ordered, and implies that all
-of `==`, `!=`, `<`, `<=`, `>=`, and `>` may be used with values of
-that type.
-Similarly for `<=`, `>=`, and `>`.
+(In practice this contract would likely be defined and exported in a
+new standard library package, `contracts`, so that it could be used by
+function and type and contract definitions.)
-These additional operations permit a little more freedom when writing
-the body of a function with type parameters: one can convert from `a =
-a * b` to `a *= b`, or make the other changes listed above, without
-having to modify the contract.
+Given that contract, we can write this function, now valid:
+
+```Go
+func Smallest(type T Ordered)(s []T) T {
+ r := s[0] // panics if slice is empty
+ for _, v := range s[1:] {
+ if v < r {
+ r = v
+ }
+ }
+ return r
+}
+```
+
+#### Conjunction and disjunction in contracts
+
+The use of comma to separate types is a general mechanism.
+A contract can be considered as a set of constraints, where the
+constraints are either methods or types.
+Separating constraints by a semicolon or newline means that the
+constraints are a conjunction: each constraint must be satisfied.
+Separating constraints by a comma means that the constraints are a
+disjunction: at least one of the constraints must be satisified.
+
+With a conjunction of constraints in a contract, a generic function
+may use any operation permitted by at least one of the constraints.
+With a disjunction, a generic function may use any operation permitted
+by all of the constraints.
+
+Syntactically, the type parameter being constrained must be listed for
+each individual conjunction constraint, but only once for the
+disjunction constraints.
+
+Normally methods will be listed as a conjunction, separated by a
+semicolon or newline.
+
+```Go
+// PrintStringer1 and PrintStringer2 are equivalent.
+contract PrintStringer1(T) {
+ T String() string
+ T Print()
+}
+
+contract PrintStringer2(T) {
+ T String() string; T Print()
+}
+```
+
+Normally builtin types will be listed as a disjunction, separated by
+commas.
+
+```Go
+contract Float(T) {
+ T float32, float64
+}
+```
+
+However, this is not required.
+For example:
+
+```Go
+contract IOCloser(S) {
+ S Read([]byte) (int, error), // note trailing comma
+ Write([]byte) (int, error)
+ S Close() error
+}
+```
+
+This contract accepts any type that has a `Close` method and also has
+either a `Read` or a `Write` method (or both).
+To put it another way, it accepts any type that implements either
+`io.ReadCloser` or `io.WriteCloser` (or both).
+In a generic function using this contract permits calling the
+`Close` method, but calling the `Read` or `Write` method requires a
+type assertion to an interface type.
+It's not clear whether this is useful, but it is valid.
+
+Another, pedantic, example:
+
+```Go
+contract unsatisfiable(T) {
+ T int
+ T uint
+}
+```
+
+This contract permits any type that is both `int` and `uint`.
+Since there is no such type, the contract does not permit any type.
+This is valid but useless.
+
+#### Both types and methods in contracts
+
+A contract may list both builtin types and methods, typically using
+conjunctions and disjunctions as follows:
+
+```Go
+contract StringableSignedInteger(T) {
+ T int, int8, int16, int32, int64
+ T String() string
+}
+```
+
+This contract permits any type defined as one of the listed types,
+provided it also has a `String() string` method.
+Although the `StringableSignedInteger` contract explicitly lists
+`int`, the type `int` is not permitted as a type argument, since `int`
+does not have a `String` method.
+An example of a type argument that would be permitted is `MyInt`,
+defined as:
+
+```Go
+type MyInt int
+func (mi MyInt) String() string {
+ return fmt.Sprintf("MyInt(%d)", mi)
+}
+```
+
+#### Aggregate types in contracts
+
+A type in a contract need not be a predeclared type; it can be a type
+literal composed of predeclared types.
+
+```Go
+contract byteseq(T) {
+ T string, []byte
+}
+```
+
+The same rules apply.
+The type argument for this contract may be `string` or `[]byte` or a
+type whose underlying type is one of those.
+A parameterized function with this contract may use any operation
+permitted by both `string` and `[]byte`.
+
+Given these definitions
+
+```Go
+type MyByte byte
+type MyByteAlias = byte
+```
+
+the `byteseq` contract is satisfied by any of `string`, `[]byte`,
+`[]MyByte`, `[]MyByteAlias`.
+
+The `byteseq` contract permits writing generic functions that work
+for either `string` or `[]byte` types.
+
+```Go
+func Join(type T byteseq)(a []T, sep T) (ret T) {
+ if len(a) == 0 {
+ // Use the result parameter as a zero value;
+ // see discussion of zero value below.
+ return ret
+ }
+ if len(a) == 1 {
+ return T(append([]byte(nil), a[0]...))
+ }
+ n := len(sep) * (len(a) - 1)
+ for i := 0; i < len(a); i++ {
+ n += len(a[i]) // len works for both string and []byte
+ }
+
+ b := make([]byte, n)
+ bp := copy(b, a[0])
+ for _, s := range a[1:] {
+ bp += copy(b[bp:], sep)
+ bp += copy(b[bp:], s)
+ }
+ return T(b)
+}
+```
+
+#### Aggregates of type parameters in contract
+
+A type literal in a contract can refer not only to predeclared types,
+but also to type parameters.
+In this example, the `Slice` contract takes two parameters.
+The first type parameter is required to be a slice of the second.
+There are no constraints on the second type parameter.
+
+```Go
+contract Slice(S, Element) {
+ S []Element
+}
+```
+
+We can use the `Slice` contract to define a function that takes an
+argument of a slice type and returns a result of that same type.
+
+```Go
+func Map(type S, Element)(s S, f func(Element) Element) S {
+ r := make(S, len(s))
+ for i, v := range s {
+ r[i] = f(s)
+ }
+ return r
+}
+
+type MySlice []int
+
+func DoubleMySlice(s MySlice) MySlice {
+ v := Map(MySlice, int)(s, func(e int) int { return 2 * e })
+ // Here v has type MySlice, not type []int.
+ return v
+}
+```
+
+(Note: the type inference rules described above do not permit
+inferring both `MySlice` and `int` when `DoubleMySlice` calls `Map`.
+It may be worth extending them, to make it easier to use functions
+that are careful to return the same result type as input type.
+Similarly, we would consider extending the type inference rules to
+permit inferring the type `Edge` from the type `Node` in the
+`graph.New` example shown earlier.)
+
+#### Comparable types in contracts
+
+Earlier we mentioned that there are two exceptions to the rule that
+operators may only be used with types that are predeclared by the
+language.
+The exceptions are `==` and `!=`, which are permitted for struct,
+array, and interface types.
+These are useful enough that we want to be able to write a contract
+that accepts any comparable type.
+
+To do this we introduce a new predeclared contract: `comparable`.
+The `comparable` contract takes a single type parameter.
+It accepts as a type argument any comparable type.
+It permits in a parameterized function the use of `==` and `!=` with
+values of that type parameter.
+
+As a predeclared contract, `comparable` may be used in a function or
+type definition, or it may be embedded in another contract.
+
+For example, this function may be instantiated with any comparable
+type:
+
+```Go
+func Index(type T comparable)(s []T, x T) int {
+ for i, v := range s {
+ if v == x {
+ return i
+ }
+ }
+ return -1
+}
+```
+
+#### Observations on types in contracts
+
+It may seem awkward to explicitly list types in a contract, but it is
+clear both as to which type arguments are permitted at the call site,
+and which operations are permitted by the parameterized function.
+
+If the language later changes to support operator methods (there are
+no such plans at present), then contracts will handle them as they do
+any other kind of method.
+
+There will always be a limited number of predeclared types, and a
+limited number of operators that those types support.
+Future language changes will not fundamentally change those facts, so
+this approach will continue to be useful.
+
+This approach does not attempt to handle every possible operator.
+For example, there is no way to usefully express the struct field
+reference `.` or the general index operator `[]`.
+The expectation is that those will be handled using aggregate types in
+a parameterized function definition, rather than requiring aggregate
+types as a type argument.
+For example, we expect functions that want to index into a slice to be
+parameterized on the slice element type `T`, and to use parameters or
+variables of type `[]T`.
+
+As shown in the `DoubleMySlice` example above, this approach makes it
+awkward to write generic functions that accept and return an aggregate
+type and want to return the same result type as their argument type.
+Defined aggregate types are not common, but they do arise.
+This awkwardness is a weakness of this approach.
#### Type conversions
-As already shown, the contract body may contain type conversions.
-A type conversion in the contract body means that the function body
-may use the same type conversion in any expression.
+In a function with two type parameters `From` and `To`, a value of
+type `From` may be converted to a value of type `To` if all the
+types accepted by `From`'s contract can be converted to all the
+types accepted by `To`'s contract.
+If either type parameter does not accept types, then type conversions
+are not permitted.
-Here is an example that implements a checked conversion between
-numeric types:
+For example:
```Go
-package check
-
-contract convert(t To, f From) {
- To(f)
- From(t)
- f == f
+contract integer(T) {
+ T int, int8, int16, int32, int64,
+ uint, uint8, uint16, uint32, uint64, uintptr
}
-func Convert(type To, From convert)(from From) To {
+contract integer2(T1, T2) {
+ integer(T1)
+ integer(T2)
+}
+
+func Convert(type To, From integer2)(from From) To {
to := To(from)
if From(to) != from {
panic("conversion out of range")
@@ -1238,183 +1449,36 @@
}
```
-Note that the contract needs to explicitly permit both converting `To`
-to `From` and converting `From` to `To`.
-The ability to convert one way doesn’t necessarily imply being able to
-convert the other way; consider `check.Convert(int, interface{})(0, 0)`.
+The type conversions in `Convert` are permitted because Go permits
+every integer type to be converted to every other integer type.
#### Untyped constants
-Some functions are most naturally written using untyped constants.
-The contract body needs ways to say that it is possible to convert an
-untyped constant to some type.
-This is most naturally written as an assignment from an untyped
-constant.
+Some functions use untyped constants.
+An untyped constant is permitted with a value of some type parameter
+if it is permitted with every type accepted by the type parameter's
+contract.
```Go
-contract untyped(x T) {
- x = 0
-}
-```
-
-A contract of this form must be used in order to write code like `var
-v T = 0`.
-
-If a contract body has assignments with string (`x = ""`) or bool (`x
-= false`) untyped constants, the function body is permitted to use any
-untyped `string` or `bool` constant, respectively, with values of the
-type.
-
-For numeric types, the use of a single untyped constant only permits
-using the exact specified value.
-Using two untyped constant assignments for a type permits using those
-constants and any value in between.
-For complex untyped constants, the real and imaginary values may vary
-to any values between the two constants.
-
-Here is an example that adds 1000 to each element of a slice.
-If the contract did not say `x = 1000`, the expression `v + 1000` would be
-invalid.
-
-```Go
-contract add1K(x T) {
- x = 1000
- x + x
+contract integer(T) {
+ T int, int8, int16, int32, int64,
+ uint, uint8, uint16, uint32, uint64, uintptr
}
-func Add1K(type T add1K)(s []T) {
+func Add10(type T integer)(s []T) {
for i, v := range s {
- s[i] = v + 1000
+ s[i] = v + 10 // OK: 10 can convert to any integer type
+ }
+}
+
+// This function is INVALID.
+func Add1024(type T integer)(s []T) {
+ for i, v := range s {
+ s[i] = v + 1024 // INVALID: 1024 not permitted by int8/uint8
}
}
```
-These untyped constant rules are not strictly required.
-A type conversion expression such as `T(int)` permits converting any
-`int` value to the type `T`, so it would permit code like `var x T =
-T(1000)`.
-What the untyped constant expressions permit is `var x T = 1000`,
-without the explicit type conversion.
-(Note that `int8` satisfies the `untyped` contract but not `add1K`,
-since 1000 is out of range for `int8`.)
-
-#### Booleans
-
-In order to use a value of a type parameter as a condition in an `if`
-or `for` statement, write an `if` or `for` statement in the contract
-body: `if T {}` or `for T {}`.
-This is only useful to instantiate a type parameter with a named
-boolean type, and as such is unlikely to arise much in practice.
-
-#### Sequences
-
-Some simple operations in the contract body make it easier for the
-function body to work on various sorts of sequences.
-
-Using an index expression `x[y]` in a contract body permits using an
-index expression with those types anywhere in the function body.
-For anything other than a map type, the type of `y` will normally be
-`int`; that case may also be written as `x[0]`.
-Naturally, `z = x[y]` permits an index expression yielding the
-specified type.
-
-A statement like `x[y] = z` in the contract body permits the function
-body to assign to an index element using the given types.
-Again `x[0] = z` permits assignment using any `int` index.
-
-A statement like `for x, y = range z {}` in the contract body permits
-using either a one-element or a two-element `range` clause in a `for`
-statement in the function body.
-
-Using an expression like `len(x)` or `cap(x)` in the contract body
-permits those builtin functions to be used with values of that type
-anywhere in the function body.
-
-Using contracts of this sort can permit operations on generic sequence
-types.
-For example, here is a version of `Join` that may be instantiated with
-either `[]byte` or `string`.
-This example is imperfect in that in the `string` case it will do some
-unnecessary conversions to `[]byte` in order to call `append` and
-`copy`, but perhaps the compiler can eliminate those.
-
-```Go
-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 {
- // Use the result parameter as a zero value;
- // see discussion of zero value below.
- 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
-
-Using `x.f` in a contract body permits referring to the field in any
-expression in the function body.
-The contract body can use `var y = x.f` to describe the field’s type.
-
-```Go
-package move
-
-contract counter(x T) {
- var _ int = x.Count
-}
-
-contract counters(T1, T2) { // as with a func, parameter names may be omitted.
- // Use contract embedding to say that both types must have a
- // Count field of type int.
- counter(T1)
- counter(T2)
-}
-
-func Corresponding(type T1, T2 counters)(p1 *T1, p2 *T2) {
- p1.Count = p2.Count
-}
-```
-
-The function `move.Corresponding` will copy the `Count` field from one
-struct to the other.
-The structs may be entirely different types, as long as they both have
-a `Count` field with type `int`.
-
-A field reference in a contract body also permits using a keyed
-composite literal in the function body, as in `T1{Count: 0}`.
-
-#### Impossible contracts
-
-It is possible to write a contract body that cannot be implemented by
-any Go type.
-This is not forbidden.
-An error will be reported not when the contract or function or type is
-compiled, but on any attempt to instantiate it.
-This eliminates the need for the language spec to provide an
-exhaustive set of rules describing when a contract body cannot be
-satisfied.
-
-It may be appropriate to add a vet check for this, if possible.
-
### Implementation
Russ Cox [famously observed](https://research.swtch.com/generic) that
@@ -1435,14 +1499,16 @@
### Summary
-While this design is long and detailed, it reduces to a few major
-points.
+While this document is long and detailed, the actual design reduces to
+a few major points.
* Functions and types can have type parameters, which are defined
using optional contracts.
-* Contracts describe the operations permitted for a type parameter
- and required for a type argument.
-* Type inference can sometimes permit omitting type arguments when
+* Contracts describe the methods required and the builtin types
+ permitted for a type argument.
+* Contracts describe the methods and operations permitted for a type
+ parameter.
+* Type inference will often permit omitting type arguments when
calling functions with type parameters.
This design is completely backward compatible, in that any valid Go 1
@@ -1450,11 +1516,11 @@
`contract` is treated as a pseudo-keyword that is only meaningful at
top level).
-We believe that this design addresses people’s needs for generic
+We believe that this design addresses people's needs for generic
programming in Go, without making the language any more complex than
necessary.
-We can’t truly know the impact on the language without years of
+We can't truly know the impact on the language without years of
experience with this design.
That said, here are some speculations.
@@ -1463,8 +1529,8 @@
One of the great aspects of Go is its simplicity.
Clearly this design makes the language more complex.
-We believe that the increased complexity is minor for people reading
-generic code, rather than writing it.
+We believe that the increased complexity is small for people reading
+well written generic code, rather than writing it.
Naturally people must learn the new syntax for declaring type
parameters.
The code within a generic function reads like ordinary Go code, as can
@@ -1492,14 +1558,6 @@
The only change is passing arguments to types rather than only to
functions.
-For the minority of people writing generic packages, we expect that
-the most complicated part will be writing correct contract bodies.
-Good compiler error messages will be essential, and they seem entirely
-feasible.
-We can’t deny the additional complexity here, but we believe that the
-design avoids confusing cases and provides the facilities that
-people need to write whatever generic code is desired.
-
In general, we have tried to avoid surprises in the design.
Only time will tell whether we succeeded.
@@ -1513,6 +1571,9 @@
are currently duplicated for each element type.
A `set` package may be added.
+A new `contracts` packages will provide standard embeddable contracts,
+such as contracts that permit all integer types or all numeric types.
+
Packages like `container/list` and `container/ring`, and types like
`sync.Map`, will be updated to be compile-time type-safe.
@@ -1547,12 +1608,12 @@
Generic functions, rather than generic types, can probably be compiled
using an interface-based approach.
That will optimize compile time, in that the package is only compiled
-once, but there will be some run-time cost.
+once, but there will be some run time cost.
Generic types may most naturally be compiled multiple times for each
set of type arguments.
-This will clearly carry a compile time cost, but there shouldn’t be
-any run-time cost.
+This will clearly carry a compile time cost, but there shouldn't be
+any run time cost.
Compilers can also choose to implement generic types similarly to
interface types, using special purpose methods to access each element
that depends on a type parameter.
@@ -1573,11 +1634,15 @@
* No metaprogramming.
There is no way to write code that is executed at compile time to
generate code to be executed at run time.
-* No higher-level abstraction.
+* No higher level abstraction.
There is no way to speak about a function with type arguments other
than to call it or instantiate it.
There is no way to speak about a parameterized type other than to
instantiate it.
+* No general type description.
+ For operator support contracts use specific types, rather than
+ describing the characteristics that a type must have.
+ This is easy to understand but may be limiting at times.
* No covariance or contravariance.
* No operator methods.
You can write a generic container that is compile-time type-safe,
@@ -1592,8 +1657,8 @@
There is no way for a contract to define adaptors that could be used
to support type arguments that do not already satisfy the contract,
such as, for example, defining an `==` operator in terms of an
- `Equal` method.
-* No parameterization on non-type values.
+ `Equal` method, or vice-versa.
+* No parameterization on non-type values such as constants
This arises most obviously for arrays, where it might sometimes be
convenient to write `type Matrix(type n int) [n][n]float64`.
It might also sometimes be useful to specify significant values for
@@ -1603,14 +1668,14 @@
There are some issues with this design that deserve a more detailed
discussion.
-We think these issues are relatively minor compared with the design
-as a whole, but they still deserve a complete hearing and discussion.
+We think these issues are relatively minor compared to the design as a
+whole, but they still deserve a complete hearing and discussion.
##### The zero value
This design has no simple expression for the zero value of a type
parameter.
-For example, consider this implementation of optional values by using
+For example, consider this implementation of optional values that uses
pointers:
```Go
@@ -1629,15 +1694,19 @@
In the case where `o.p == nil`, we want to return the zero value of
`T`, but we have no way to write that.
-It would be nice to be able to write `return nil`, but that wouldn’t
+It would be nice to be able to write `return nil`, but that wouldn't
work if `T` is, say, `int`; in that case we would have to write
`return 0`.
+And, of course, there is no contract to support either `return nil` or
+`return 0`.
Some approaches to this are:
* Use `var zero T`, as above, which works with the existing design
but requires an extra statement.
* Use `*new(T)`, which is ugly but works with the existing design.
+* For results only, name the result parameter `_`, and use a naked
+ `return` statement to return the zero value.
* Extend the design to permit using `nil` as the zero value of any
generic type (but see [issue 22729](https://golang.org/issue/22729)).
* Extend the design to permit using `T{}`, where `T` is a type
@@ -1662,56 +1731,121 @@
We experimented with other syntaxes, such as using a colon to separate
the type arguments from the regular arguments.
-The current design seems to be the best, but perhaps something
+The current design seems to be the nicest, but perhaps something
better is possible.
-##### What does := mean in a contract body?
-
-If a contract body uses a short declaration, such as
-
-```Go
- s := x.String()
-```
-
-this does not provide any information about the result parameter of
-the `String` method.
-This contract body would match any type with a `String` method that
-returns a single result of any type.
-It’s less clear what it permits in the function using this contract.
-For example, does it permit the function to call the `String` method
-and assign the result to a variable of empty interface type?
-
##### Pointer vs. value methods in contracts
-It seems that the natural ways to write a contract calling for certain
-methods to exist will accept either a pointer method or a value
-method.
-That may be confusing, in that it will prevent writing a function body
-that requires a value method.
+Contracts do not provide a way to distinguish between pointer and
+value methods, so types that provide either will satisfy a contract.
+This in turn requires that parameterized functions always permit
+either kind of method.
+This may be confusing, in that a parameterized function may invoke a
+pointer method on a temporary value; if the pointer method changes the
+value to which the receiver points, those changes will be lost.
We will have to judge from experience how much this confuses people in
practice.
-##### Copying the function body into the contract body
+##### Defined aggregate types
-The simplest way to ensure that a function only performs the
-operations permitted by its contract is to simply copy the function
-body into the contract body.
-In other words, to make the function body be its own contract, much as
-C++ does.
-If people take this path, then this design in effect creates a lot of
-additional complexity for no benefit.
+As discussed above, an extra type parameter is required for a function
+to take, as an argument, a defined type whose underlying type is an
+aggregate type, and to return the same defined type as a result.
-We think this is unlikely because we believe that most people will not
-write generic function, and we believe that most generic functions
-will have only non-existent or trivial requirements on their type
-parameters.
-More experience will be needed to see whether this is a problem.
+For example, this function will map a function across a slice.
+
+```Go
+func Map(type Element)(s []Element, f func(Element) Element) []Element {
+ r := make([]Element, len(s))
+ for i, v := range s {
+ r[i] = f(v)
+ }
+ return r
+}
+```
+
+However, when called on a defined type, it will return a slice of the
+element type of that type, rather than the defined type itself.
+
+```Go
+type MySlice []int
+
+func DoubleMySlice(s MySlice) MySlice {
+ s2 := Map(s, func(e int) int { return 2 * e })
+ // Here s2 is type []int, not type MySlice.
+ return MySlice(s2)
+}
+```
+
+As discussed above with an example, this can be avoided by using an
+extra type parameter for `Map`, and using a contract that describes
+the required relationship between the slice and element types.
+This works but is awkward.
+
+##### Identifying the matched predeclared type
+
+In this design we suggest permitting type assertions and type switches
+on values whose types are based on type parameters, but those type
+assertions and switches would always test the actual type argument.
+The design doesn't provide any way to test the contract type matched
+by the type argument.
+
+Here is an example that shows the difference.
+
+```Go
+contract Float(F) {
+ F float32, float64
+}
+
+func NewtonSqrt(type F Float)(v F) F {
+ var iterations int
+ switch v.(type) {
+ case float32:
+ iterations = 4
+ case float64:
+ iterations = 5
+ default:
+ panic(fmt.Sprintf("unexpected type %T", v))
+ }
+ // Code omitted.
+}
+
+type MyFloat float32
+
+var G = NewtonSqrt(MyFloat(64))
+```
+
+This code will panic when initializing `G`, because the type of `v` in
+the `NewtonSqrt` function will be `MyFloat`, not `float32` or
+`float64`.
+What this function actually wants to test is not the type of `v`, but
+the type that `v` matched in the contract.
+
+One way to handle this would be to permit type switches on the type
+`F`, rather than the value `v`, with the proviso that the type `F`
+would always match a type defined in the contract.
+This kind of type switch would only be permitted if the contract does
+list explicit types, and only types listed in the contract would be
+permitted as cases.
+
+If we took this approach, we would stop permitting type assertions and
+switches on values whose type is based on a type parameter.
+Those assertions and switches can always be done by first converting
+the value to the empty interface type.
+
+A different approach would be that if a contract specifies any types
+for a type parameter, then let type switches and assertions on values
+whose type is, or is based on, that type parameter to match only the
+types listed in the type parameter's contract.
+It is still possible to match the value's actual type by first
+converting it to the `interface{}` type and then doing the type
+assertion or switch.
#### Discarded ideas
This design is not perfect, and it will be changed as we gain
experience with it.
-That said, there are many ideas that we’ve already considered in
+That said, there are many ideas that we've already considered in
detail.
This section lists some of those ideas in the hopes that it will help
to reduce repetitive discussion.
@@ -1720,8 +1854,10 @@
##### Why not use interfaces instead of contracts?
_The interface method syntax is familiar._
-_Writing contract bodies with `x + x` is ordinary Go syntax, but it_
-_is stylized, repetitive, and looks weird._
+_Why introduce another way to write methods?_
+
+Contracts, unlike interfaces, support multiple types, including
+describing ways that the types refer to each other.
It is unclear how to represent operators using interface methods.
We considered syntaxes like `+(T, T) T`, but that is confusing and
@@ -1735,37 +1871,102 @@
the cost of some repetition.
These are not fatal problems, but they are difficulties.
+More seriously, a contract is a relationship between the definition of
+a generic function and the callers of that function.
+To put it another way, it is a relationship between a set of type
+parameters and a set of type arguments.
+The contract defines how values of the type parameters may be used,
+and defines the requirements on the type arguments.
+That is why it is called a contract: because it defines the behavior
+on both sides.
+
+An interface is a type, not a relationship between function
+definitions and callers.
+A program can have a value of an interface type, but it makes no sense
+to speak of a value of a contract type.
+A value of interface type has both a static type (the interface type)
+and a dynamic type (some non-interface type), but there is no similar
+concept for contracts.
+
+In other words, contracts are not extensions of interface types.
+There are things you can do with a contract that you cannot do with an
+interface type, and there are things you can do with an interace type
+that you cannot do with a contract.
+
+It is true that a contract that has a single type parameter and that
+lists only methods, not builtin types, for that type parameter, looks
+similar to an interface type.
+But all the similarity amounts to is that both provide a list of
+methods.
+We could consider permitting using an interface type as a contract
+with a single type parameter that lists only methods.
+But that should not mislead us into thinking that contracts are
+interfaces.
+
+##### Why not permit contracts to describe a type?
+
+_In order to use operators contracts have to explicitly and tediously_
+_list types._
+_Why not permit them to describe a type?_
+
+There are many different ways that a Go type can be used.
+While it is possible to invent notation to describe the various
+operations in a contract, it leads to a proliferation of additional
+syntactic constructs, making contracts complicated and hard to read.
+The approach used in this design is simpler and relies on only a few
+new syntactic constructs and names.
+
##### Why not put type parameters on packages?
We investigated this extensively.
It becomes problematic when you want to write a `list` package, and
you want that package to include a `Transform` function that converts
a `List` of one element type to a `List` of another element type.
-It’s very awkward for a function in one instantiation of a package to
+It's very awkward for a function in one instantiation of a package to
return a type that requires a different instantiation of the package.
It also confuses package boundaries with type definitions.
There is no particular reason to think that the uses of parameterized
types will break down neatly into packages.
-Sometimes they will, sometimes they won’t.
+Sometimes they will, sometimes they won't.
-##### Why not use `F<T>` like C++ and Java?
+##### Why not use the syntax `F<T>` like C++ and Java?
When parsing code within a function, such as `v := F<T>`, at the point
-of seeing the `<` it’s ambiguous whether we are seeing a type
+of seeing the `<` it's ambiguous whether we are seeing a type
instantiation or an expression using the `<` operator.
Resolving that requires effectively unbounded lookahead.
In general we strive to keep the Go parser simple.
-##### Why not use `F[T]`?
+##### Why not use the syntax `F[T]`?
-When parsing a type declaration `type A [T] int` it’s ambiguous
+When parsing a type declaration `type A [T] int` it's ambiguous
whether this is a parameterized type defined (uselessly) as `int` or
whether it is an array type with `T` elements.
+However, this would be addressed by requiring `type A [type T] int`
+for a parameterized type.
+
+Parsing declarations like `func f(A[T]int)` (a single parameter of
+type `[T]int`) and `func f(A[T], int)` (two parameters, one of type
+`A[T]` and one of type `int`) show that some additional parsing
+lookahead is required.
+This is solvable but adds parsing complexity.
+
+The language generally permits a trailing comma in a comma-separated
+list, so `A[T,]` should be permitted if `A` is a parameterized type,
+but normally would not be permitted for an index expression.
+However, the parser can't know whether `A` is a parameterized type or
+a value of slice, array, or map type, so this parse error can not be
+reported until after type checking is complete.
+Again, solvable but complicated.
+
+More generally, we felt that the square brackets were too intrusive on
+the page and that parentheses were more Go like.
+We will reevaluate this decision as we gain more experience.
##### Why not use `F«T»`?
-We considered it but we couldn’t bring ourselves to require
+We considered it but we couldn't bring ourselves to require
non-ASCII.
##### Why not define contracts in a standard package?
@@ -1776,9 +1977,10 @@
Listing all the possible combinations of types gets rather lengthy.
It also introduces a new set of names that not only the writer of
generic code, but, more importantly, the reader, must remember.
-One of the driving goals of this design is to not introduce new
-names.
-Instead we introduce one new keyword and some new syntax.
+One of the driving goals of this design is to introduce as few new
+names as possible.
+In this design we introduce one new keyword and one new predefined
+name.
We expect that if people find such names useful, we can introduce a
package `contracts` that defines the useful names in the form of
@@ -1811,34 +2013,32 @@
ordinary programming done at compile time using a syntax that is
completely different than that of non-template C++.
This design has no similar feature.
-This saves considerable complexity while losing some power and
-run-time efficiency.
+This saves considerable complexity while losing some power and run
+time efficiency.
### Examples
The following sections are examples of how this design could be used.
This is intended to address specific areas where people have created
-user experience reports concerned with Go’s lack of generics.
+user experience reports concerned with Go's lack of generics.
-#### sort
+#### Sort
Before the introduction of `sort.Slice`, a common complaint was the
need for boilerplate definitions in order to use `sort.Sort`.
With this design, we can add to the sort package as follows:
```Go
-contract ordered(e Ele) { e < e }
+type orderedSlice(type Elem comparable) []Elem
-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 (s orderedSlice(Elem)) Len() int { return len(s) }
+func (s orderedSlice(Elem)) Less(i, j int) bool { return s[i] < s[j] }
+func (s orderedSlice(Elem)) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
// OrderedSlice sorts the slice s in ascending order.
// The elements of s must be ordered using the < operator.
-func OrderedSlice(type Ele ordered)(s []Ele) {
- sort.Sort(orderedSlice(Ele)(s))
+func OrderedSlice(type Elem comparable)(s []Elem) {
+ sort.Sort(orderedSlice(Elem)(s))
}
```
@@ -1859,18 +2059,18 @@
to take values rather than slice indexes.
```Go
-type sliceFn(type Ele) struct {
- s []Ele
- f func(Ele, Ele) bool
+type sliceFn(type Elem) struct {
+ s []Elem
+ f func(Elem, Elem) bool
}
-func (s sliceFn(Ele)) Len() int { return len(s.s) }
-func (s sliceFn(Ele)) Less(i, j int) bool { return s.f(s.s[i], s.s[j]) }
-func (s sliceFn(Ele)) Swap(i, j int) { s.s[i], s.s[j] = s.s[j], s.s[i] }
+func (s sliceFn(Elem)) Len() int { return len(s.s) }
+func (s sliceFn(Elem)) Less(i, j int) bool { return s.f(s.s[i], s.s[j]) }
+func (s sliceFn(Elem)) Swap(i, j int) { s.s[i], s.s[j] = s.s[j], s.s[i] }
// SliceFn sorts the slice s according to the function f.
-func SliceFn(type Ele)(s []Ele, f func(Ele, Ele) bool) {
- Sort(sliceFn(Ele){s, f})
+func SliceFn(type Elem)(s []Elem, f func(Elem, Elem) bool) {
+ Sort(sliceFn(Elem){s, f})
}
```
@@ -1882,16 +2082,16 @@
sort.SliceFn(s, func(p1, p2 *Person) bool { return p1.Name < p2.Name })
```
-#### map keys
+#### Map keys
Here is how to get a slice of the keys of any map.
```Go
package maps
-contract mappable(k K, _ V) { k == k }
-
-func Keys(type K, V mappable)(m map[K]V) []K {
+// Keys returns the keys of the map m.
+// Note that map keys (here called type K) must be comparable.
+func Keys(type K, V comparable(K))(m map[K]V) []K {
r := make([]K, 0, len(m))
for k := range m {
r = append(r, k)
@@ -1906,7 +2106,7 @@
k := maps.Keys(map[int]int{1:2, 2:4}) // sets k to []int{1, 2} (or {2, 1})
```
-#### map/reduce/filter
+#### Map/Reduce/Filter
Here is an example of how to write map, reduce, and filter functions
for slices.
@@ -1956,9 +2156,9 @@
evens := slices.Filter(s, func(i int) bool { return i%2 == 0 })
```
-#### sets
+#### Sets
-Many people have asked for Go’s builtin map type to be extended, or
+Many people have asked for Go's builtin map type to be extended, or
rather reduced, to support a set type.
Here is a type-safe implementation of a set type, albeit one that uses
methods rather than operators like `[]`.
@@ -1967,32 +2167,30 @@
// Package set implements sets of any type.
package set
-contract comparable(Ele) { Ele == Ele }
+type Set(type Elem comparable) map[Elem]struct{}
-type Set(type Ele comparable) map[Ele]struct{}
-
-func Make(type Ele comparable)() Set(Ele) {
- return make(Set(Ele))
+func Make(type Elem comparable)() Set(Elem) {
+ return make(Set(Elem))
}
-func (s Set(Ele)) Add(v Ele) {
+func (s Set(Elem)) Add(v Elem) {
s[v] = struct{}{}
}
-func (s Set(Ele)) Delete(v Ele) {
+func (s Set(Elem)) Delete(v Elem) {
delete(s, v)
}
-func (s Set(Ele)) Contains(v Ele) bool {
+func (s Set(Elem)) Contains(v Elem) bool {
_, ok := s[v]
return ok
}
-func (s Set(Ele)) Len() int {
+func (s Set(Elem)) Len() int {
return len(s)
}
-func (s Set(Ele)) Iterate(f func(Ele)) {
+func (s Set(Elem)) Iterate(f func(Elem)) {
for v := range s {
f(v)
}
@@ -2007,11 +2205,11 @@
if s.Contains(2) { panic("unexpected 2") }
```
-This example, like the sort examples above, shows how to use this
+This example, like the sort examples above, show how to use this
design to provide a compile-time type-safe wrapper around an
existing API.
-#### channels
+#### Channels
Many simple general purpose channel functions are never written,
because they must be written using reflection and the caller must type
@@ -2036,7 +2234,7 @@
d := make(chan bool)
s := &Sender(T){values: c, done: d}
r := &Receiver(T){values: c, done: d}
- runtime.SetFinalizer(r, (*Receiver(T)).finalize)
+ runtime.SetFinalizer(r, r.finalize)
return s, r
}
@@ -2046,7 +2244,7 @@
done <-chan bool
}
-// Send sends a value to the receiver. It reports whether any more
+// Send sends a value to the receiver. It returns whether any more
// values may be sent; if it returns false the value was not sent.
func (s *Sender(T)) Send(v T) bool {
select {
@@ -2085,12 +2283,12 @@
There is an example of using this function in the next section.
-#### containers
+#### Containers
One of the frequent requests for generics in Go is the ability to
write compile-time type-safe containers.
This design makes it easy to write a compile-time type-safe wrapper
-around an existing container; we won’t write out an example for that.
+around an existing container; we won't write out an example for that.
This design also makes it easy to write a compile-time type-safe
container that does not use boxing.
@@ -2226,7 +2424,7 @@
}
```
-#### append
+#### Append
The predeclared `append` function exists to replace the boilerplate
otherwise required to grow a slice.
@@ -2264,7 +2462,7 @@
}
```
-That example uses the predeclared `copy` function, but that’s OK, we
+That example uses the predeclared `copy` function, but that's OK, we
can write that one too:
```Go
@@ -2286,14 +2484,14 @@
slices.Copy(s[3:], []int{7, 8, 9})
```
-This code doesn’t implement the special case of appending or copying a
-`string` to a `[]byte`, and it’s unlikely to be as efficient as the
+This code doesn't implement the special case of appending or copying a
+`string` to a `[]byte`, and it's unlikely to be as efficient as the
implementation of the predeclared function.
Still, this example shows that using this design would permit append
and copy to be written generically, once, without requiring any
additional special language features.
-#### metrics
+#### Metrics
In a [Go experience
report](https://medium.com/@sameer_74231/go-experience-report-for-generics-google-metrics-api-b019d597aaa4)
@@ -2324,15 +2522,7 @@
import "sync"
-contract comparable(v T) {
- v == v
-}
-
-contract cmp1(T) {
- comparable(T) // contract embedding
-}
-
-type Metric1(type T cmp1) struct {
+type Metric1(type T comparable) struct {
mu sync.Mutex
m map[T]int
}
@@ -2411,11 +2601,11 @@
}
```
-This package implementation does have a certain amount of repetition
-due to the lack of support for variadic package type parameters.
+This package implementation has a certain amount of repetition due to
+the lack of support for variadic package type parameters.
Using the package, though, is easy and type safe.
-#### list transform
+#### List transform
While slices are efficient and easy to use, there are occasional cases
where a linked list is appropriate.
@@ -2459,7 +2649,7 @@
}
// Next advances the iterator.
-// It reports whether there are more elements.
+// It returns whether there are more elements.
func (it *Iterator(T)) Next() bool {
if *it.next == nil {
return false
@@ -2478,7 +2668,7 @@
return (*it.next).val, true
}
-// Transform runs a transform function on a list, returning a new list.
+// Transform runs a transform function on a list returning a new list.
func Transform(type T1, T2)(lst *List(T1), f func(T1) T2) *List(T2) {
ret := &List(T2){}
it := lst.Range()
@@ -2492,7 +2682,7 @@
}
```
-#### context
+#### Context
The standard "context" package provides a `Context.Value` method to
fetch a value from a context.
@@ -2535,7 +2725,7 @@
}
```
-To see how this might be used, consider the net/http package’s
+To see how this might be used, consider the net/http package's
`ServerContextKey`:
```Go
@@ -2559,3 +2749,134 @@
Code that uses `Key.WithValue` and `Key.Value` instead of
`context.WithValue` and `context.Value` does not need any type
assertions and is compile-time type-safe.
+
+#### Dot product
+
+A generic dot product implementation that works for slices of any
+numeric type.
+
+```Go
+// Numeric is a contract that matches any numeric type.
+// It would likely be in a contracts package in the standard library.
+contract Numeric(T) {
+ T int, int8, int16, int32, int64,
+ uint, uint8, uint16, uint32, uint64, uintptr,
+ float32, float64,
+ complex64, complex128
+}
+
+func DotProduct(type T Numeric)(s1, s2 []T) T {
+ if len(s1) != len(s2) {
+ panic("DotProduct: slices of unequal length")
+ }
+ var r T
+ for i := range s1 {
+ r += s1[i] * s2[i]
+ }
+ return r
+}
+```
+
+#### Absolute difference
+
+Compute the absolute difference between two numeric values, by using
+an `Abs` method.
+This uses the same `Numeric` contract defined in the last example.
+
+This example uses more machinery than is appropriate for the simple
+case of computing the absolute difference.
+It is intended to show how the common part of algorithms can be
+factored into code that uses methods, where the exact definition of
+the methods can very based on the kind of type being used.
+
+```Go
+// NumericAbs matches numeric types with an Abs method.
+contract NumericAbs(T) {
+ Numeric(T)
+ T Abs() T
+}
+
+// AbsDifference computes the absolute value of the difference of
+// a and b, where the absolute value is determined by the Abs method.
+func AbsDifference(type T NumericAbs)(a, b T) T {
+ d := a - b
+ return d.Abs()
+}
+```
+
+We can define an `Abs` method appropriate for different numeric types.
+
+```Go
+// OrderedNumeric matches numeric types that support the < operator.
+contract OrderedNumeric(T) {
+ T int, int8, int16, int32, int64,
+ uint, uint8, uint16, uint32, uint64, uintptr,
+ float32, float64
+}
+
+// Complex matches the two complex types, which do not have a < operator.
+contract Complex(T) {
+ T complex64, complex128
+}
+
+// OrderedAbs is a helper type that defines an Abs method for
+// ordered numeric types.
+type OrderedAbs(type T OrderedNumeric) T
+
+func (a OrderedAbs(T)) Abs() T {
+ if a < 0 {
+ return -a
+ }
+ return a
+}
+
+// ComplexAbs is a helper type that defines an Abs method for
+// complex types.
+type ComplexAbs(type T Complex) T
+
+func (a ComplexAbs(T)) Abs() T {
+ r := float64(real(a))
+ i := float64(imag(a))
+ d := math.Sqrt(r * r + i * i)
+ return T(complex(d, 0))
+}
+```
+
+We can then define functions that do the work for the caller by
+converting to and from the types we just defined.
+
+```Go
+func OrderedAbsDifference(type T OrderedNumeric)(a, b T) T {
+ return T(AbsDifference(OrderedAbs(T)(a), OrderedAbs(T)(b)))
+}
+
+func ComplexAbsDifference(type T Complex)(a, b T) T {
+ return T(AbsDifference(ComplexAbs(T)(a), ComplexAbs(T)(b)))
+}
+```
+
+It's worth noting that this design is not powerful enough to write
+code like the following:
+
+```Go
+// This function is INVALID.
+func GeneralAbsDifference(type T Numeric)(a, b T) T {
+ switch a.(type) {
+ case int, int8, int16, int32, int64,
+ uint, uint8, uint16, uint32, uint64, uintptr,
+ float32, float64:
+ return OrderedAbsDifference(a, b) // INVALID
+ case complex64, complex128:
+ return ComplexAbsDifference(a, b) // INVALID
+ }
+}
+```
+
+The calls to `OrderedAbsDifference` and `ComplexAbsDifference` are
+invalid, because not all the types that satisfy the `Numeric` contract
+can satisfy the `OrderedNumeric` or `Complex` contracts.
+Although the type switch means that this code would conceptually work
+at run time, there is no support for writing this code at compile
+time.
+This another of way of expressing one of the omissions listed above:
+this design does not provide for specialization.
