This is an experimental rewrite of https://go.googlesource.com/proposal/+/master/design/go2draft-contracts.md to evaulate if type parameterized types as described in the contracts proposal could be implemented on top of the feature described in golang/go#33818. This to help evaluate weather the featuere could make sense for Go in the longer term, or if there is any issues with it.
This is not mean as an actual proposal.
This text assumes type parameterized interface default methods as described in golang/go#33818 have already been added to the language.
To facilitate this exercise, let's assume it was implemented with the following syntax/clarification:
type Equaler interface {
Equal(other interface{}) bool
}
func (e $E Equaler) Equal(other interface{}) bool {
o, ok := other.($E)
return ok && o == e
}The declaration line has three parts in the receiver clauses:
- The receiver value variable (
e). - The receiver type variable (
$E), where the$prefix is by convention only. - The receiver interface, which is analogious to a reciever type in other type methods.
The receiver value variable can be ommmited if not used.
If the receiver type variable is not be used, the name can be set to _.
The name can be set to any other valid variable name, but by convention it's
either the same as in the type declaration or it's underscore.
It is valid to define an interface default method with a pointer receiver type variable:
type Setter interface{
Set(v interface{}) error
}
// This is OK.
func (e *$E Setter) Set(v interface{}) error {
t, ok := v.($E)
if !ok {
return erros.New("incompatible type")
}
*e = t
return nil
}It is not valid to define a interface default method with an interface pointer receiver:
type Setter interface{
Set(v interface{}) error
}
// Pointer reviever interface is INVALID.
func (e $E *Setter) Set(v interface{}) error {
...
}This syntax is chocen because it's illustrative and simplem, and because it is sufficeint to illustrate what we will do next.
The exercise is to try to rewrite parts of the contracts draft proposal on top of this feature, without contracts. More specifically, we will rewrite type parameterized types.
Type parameterized functions have been omitted, as they are not strictly
necessary; we can do almost the same things through just having type
parameterized types, and removing the feature allows the type parameterization
syntax to be simplified (ommiting the type prefix).
Starting now:
We suggest extending the Go language to add optional type parameters to types.
Type parameters must specify either an interface to satisfy, or a built-in kind that the (underlying) type must implement.
This is an experimental alteration of the current contracts draft proposal to see if it can reasonably be implemented without contracts on top of the type parameterized interface default methods proposal.
We will describe the complete design in stages based on examples.
Kinds and interfaces are the key concepts we will use to allow type parameterization. You can think of a kind as a hard-coded interface. Unlike interfaces, all kinds are statically defined in the language, and can only be used as type parameters.
Kinds are essentially defined as groups of types that share certain properties
that are hard to explain through normal interfaces. E.g. hashable (can be used
as map keys) or rangable (can be ranged over).
There are also kinds defined for numeric and comparable.
These types can in princial be described through something called
type parameterized interfaces, but using kinds restrict the
allowed underlying types and allows direct access to operators
withot going through interface methods.
E.g. access a < b over a.LessThan(b) or a + b over a.Add(b).
(Note: the border between kind and interfaces should be defined better).
How kind implementation is handled, may vary from case to case. E.g. a numeric value is comparable, but a struct of numeric types is ont. However, a struct consisting of only hashable types, is still hashable.
Generic code is code that is written using types that will be specified later. Each unspecified type is called a type parameter. A type parameter must either implement a given interface (after considering interface default method implementations), or be of a specified kind. When running the generic code, the type parameter will be set to a type argument.
We want generic types. We suggest that types be extended to take type parameters.
type Vector($E interface{}) []$EThe $ type parameter name prefix is by convention only.
Within the type definition, the type parameters may be used like any other type.
To use a parameterized type, you must supply type arguments. This looks like a function call, except that the function in this case is actually a type. This is called instantiation.
var v Vector(int)Parameterized types can have methods. The receiver type of a method must list the type parameters. They are listed without the type parameter interface or kind.
func (v *Vector($E)) Push(x $E) { *v = append(*v, x) }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, listed in the same order. This restriction prevents infinite recursion of type instantiation.
// This is OK.
type List($E interface{}) struct {
next *List($E)
val Element
}
// This type is INVALID.
type P($E1, $E2 interface{}) struct {
F *P($E1, $E2) // INVALID; must be (Element1, Element2)
}(Note: with more understanding of how people want to write code, it may be possible to relax this rule to permit some cases that use different type arguments.)
A short-hand of self-reference is also allowed:
// This is OK and equivilent to example above.
type $L List($E interface{}) struct {
next *$L
val Element
}
// This is OK.
type $P P($E1, $E2 interface{}) struct {
F *$P
}The type parameter of a parameterized type may use any relevant interface:
type StringableVector($E fmt.Stringer) []$E
func (s StringableVector($E)) 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()
}Remember that the Stringer interface could also have a default interface implementation causing it to be implemented by many different types.
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 of the type parameter, not the name of the type argument.
type Lockable($T interface{}) struct {
$T
mu sync.Mutex
}
func (l *Lockable($T)) Get() T {
l.mu.Lock()
defer l.mu.Unlock()
return l.$T
}Type aliases may not have type parameters. Type aliases may refer to instantiated types.
type VectorInt = Vector(int)If a type alias refers to a parameterized type, it must provide type arguments.
Top-level functions can not take type arguments. To define a function that can take type parameters, we need to do it as methods on a parameterized type. This restrictions exists to simplify syntax and limit the (precieved) complexity of the solution.
Although methods of a parameterized type may use the type's parameters, methods may not themselves have additional type parameters.
Parameterized function types can be declared just as any other type.
// A parameterized function type can be defined just like any other
/// parameterized type.
type PrinterFunc($I interface{}) func($I)
var PrintStrings = PrinterFunc(string)Kinds can be used instead of interfaces when suitable. E.g.:
type Record($V numeric) struct {
Time time.Time
Value $V
}
type Timeseries($V numeric) []Record($V)Although the examples we've seen so far use only a single type parameter, types may have multiple type parameters.
type SyncMap($K hashable, $V interface{}) struct {
m map[$K]$V
l sync.RWMutex
}
func (sm *SyncMap($K, $V)) Get(k $K) ($V, bool) {
l.RLock()
v, ok := sm.m[k]
l.RUnlock()
return v, ok
}
func (sm *SyncMap($K, $V)) Set(k $K, v $V) {
l.Lock()
sm.m[k] := v
l.Unlock()
}Kinds can not be embedded for now. However, if it turns out there are good use case for it, we could potentially allow embedding of kinds into interfaces. A seprate proposal should be formed to investage this idea, if relevant.
Yes, you heard me correctly; interfaces are also types, and can be parameterized.
package compare
// Equaler is a type parameterized interface that describes types that have an
// Equal method with an argument of the same type as the receiver type.
type Equaler($I interface{}) interface{
Equal($I) bool
}
// Equal default implementation.
func (e _ Equaler($I)) Equal(o $I) bool {
return e == o // only compiles of e is comparable to o.
}
type Indexer($I interface{}) struct{}
// Index returns the index of e in s, or -1.
func (Indexer($I)) Index(s []Equaler($I), e Equaler($I)) int {
for i, v := range s {
// Both e and v are type Equaler($I), so it's OK to call e.Equal(v).
if e.Equal(v) {
return i
}
}
return -1
}The Indexer type can be used with any type that has an Equal method
whose single parameter type is the same as the receiver type.
Due to the specified interface default method implementations, it can also be
used for any type that is comparable through the double equality sign.
Example usage:
import "compare"
type (
// Initalizes an Indexer accepting Equaler(int).
IndexerInt = compare.Indexer(int)
)
func main() {
i1 := IndexerInt.Index([]int{1, 2, 3}, 2)
fmt.Println(i1)
// output: 1
}In this example, when we pass int to compare.Index on intiation, which again
triggers initation of the interface compare.Equaler with $I set to int.
The type int does note supply an Equal metohod, so we replace $I with
int in the declaration of the Equaler.Equal method.
The (e _) Equal(int) bool method compiles succesfully, and all is well.
import "compare"
type EqualStruct struct
// The Equal method lets EqualStruct satisfy the compare.Equaler interface.
func (a EqualStruct) Equal(b EqualStruct) bool { return a == b }
func Index(s []EqualStruct, e EqualStruct) int {
return compare.Indexer(EqualStruct).Index(s, e)
}However, we can do it slightly more elegant by adding one more feature.
(Note: not completely sound)
A self-refrencing interface, is a special-case of a type parameterized interface that specify a receiver type as part of the declaration. Such interfaces are initated by passing the receiver as the first argument, which menas that a initated interface can only be implemented by a single type. While this doesn't immidelatly sound useful, it can in fact be used for several things:
- Wrap a compatible type to provide additional methods based on default implementations.
- Static type cheking.
- Define inline as part of type parameterized type.
Let's first rewrite the example from the previous section to use self-reference:
package compare
// Equaler is a type parameterized interface that describes types that have an
// Equal method with an argument of the same type as the receiver type.
type $E Equaler() interface{
Equal($E) bool
}
// Equal default implementation.
func (e $E Equaler) Equal(o $E) bool {
return e == o // only compiles of e is comparable to o.
}The definition and usage of compare.Indexer remain the same.
(Note: may be initally ommited)
Self-referencing interfaces can also be used to define mutually referencing type parameters.
For example, consider a generic graph package that contains generic
algorithms that work with graphs.
The algorithms use two types, Node and Edge.
Node is expected to have a method Edges() []Edge.
Edge is expected to have a method Nodes() (Node, Node).
A graph can be represented as a []Node.
This representation is enough to implement graph algorithms like finding the shortest path.
package graph
type $N Node() interface{
Edges() []Edge($N)
}
type $E Edge() interface{
Nodes() (from, to Node($E))
}
type Factory($N Node($N), $E Edge($E)) struct{}
func ($F Factory($N, $E)) New(nodes $N) *Graph($N, $E) { ... }
type Graph($N Node($N), $E Edge($E)) struct { ... }
func (g *Graph($N, $E)) ShortestPath(from, to $N) []$E { ... }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.
For example, consider these type definitions in some other package:
type Vertex struct { ... }
func (v *Vertex) Edges() []*FromTo { ... }
type FromTo struct { ... }
func (ft *FromTo) Nodes() (*Vertex, *Vertex) { ... }There are no interface types here, but we can instantiate
graph.Graph using the type arguments *Vertex and *FromTo:
var g = graph.New(*Vertex, *FromTo)([]*Vertex{ ... })*Vertex and *FromTo are not interface types, but when used
together they define methods that implement the contract graph.G.
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.
type NodeInterface interface { Edges() []EdgeInterface }
type EdgeInterface interface { Nodes() (NodeInterface, NodeInterface) }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
permitted.
This ability for type parameters to refer to other type parameters illustrates an important point: it should be a requirement for any attempt to add generics to Go that it be possible to instantiate generic code with multiple type arguments that refer to each other in ways that the compiler can check.