commit | a2c03b640cb6c87aaaff70a178f5492937d30667 | [log] [tgz] |
---|---|---|

author | Ian Lance Taylor <iant@golang.org> | Fri Aug 07 16:57:55 2020 -0700 |

committer | Ian Lance Taylor <iant@golang.org> | Thu Aug 13 02:29:21 2020 +0000 |

tree | a7d2067bca40470db15c8fa7145548635049136d | |

parent | 572fea69936c3f25a99860fce22aeb23a3263ca3 [diff] |

design: type parameters: add constraint type inference Change-Id: Ifefbaf79cd5ca7bcde4a5fc00f26aad5813ffc40 Reviewed-on: https://go-review.googlesource.com/c/proposal/+/247518 Reviewed-by: Robert Griesemer <gri@golang.org>

diff --git a/design/go2draft-type-parameters.md b/design/go2draft-type-parameters.md index a215340..47b0ae5 100644 --- a/design/go2draft-type-parameters.md +++ b/design/go2draft-type-parameters.md

@@ -2,7 +2,7 @@ Ian Lance Taylor\ Robert Griesemer\ -June 16, 2020 +August 12, 2020 ## Abstract @@ -745,219 +745,6 @@ types rather than on underlying types; perhaps `type ==`. For now, this is not permitted. -### Function argument type inference - -In many cases, when calling a function with type parameters, we can -use type inference to avoid having to explicitly write out the type -arguments. - -Go back to [the example](#Type-parameters) of a call to the simple -`Print` function: - -```Go - Print(int)([]int{1, 2, 3}) -``` - -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. -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, then our algorithm does not infer the type arguments for the -function, since there is no value from which to infer the types. - -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 is simply `[]int`. -On the function side is the list of the types of the function's -non-type parameters, which for `Print` is `[]T`. -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, we ignore untyped constants on the caller side and -their corresponding types in the function definition. - -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. -If the same type parameter appears more than once on the function -side, it will match multiple argument types on the caller side. -Those caller types must be identical, or type unification fails, and -we report an error. - -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, we determine the default -type of the untyped constant in [the usual -way](https://golang.org/ref/spec#Constants). -Then we run the type unification algorithm again, this time with no -untyped constants. - -In this example - -```Go - s1 := []int{1, 2, 3} - Print(s1) -``` - -we compare `[]int` with `[]T`, match `T` with `int`, and we are done. -The single type parameter `T` is `int`, so we infer that the call to -`Print` is really a call to `Print(int)`. - -For a more complex example, consider - -```Go -// Map calls the function f on every element of the slice s, -// returning a new slice of the results. -func Map(type F, T)(s []F, f func(F) T) []T { - r := make([]T, len(s)) - for i, v := range s { - r[i] = f(v) - } - return r -} -``` - -The two type parameters `F` and `T` are both used for input -parameters, so type inference is possible. -In the call - -```Go - strs := Map([]int{1, 2, 3}, strconv.Itoa) -``` - -we unify `[]int` with `[]F`, matching `F` with `int`. -We unify the type of `strconv.Itoa`, which is `func(int) string`, -with `func(F) T`, matching `F` with `int` and `T` with `string`. -The type parameter `F` is matched twice, both times with `int`. -Unification succeeds, so the call written as `Map` is a call of -`Map(int, string)`. - -To see the untyped constant rule in effect, consider: - -```Go -// NewPair returns a pair of values of the same type. -func NewPair(type F)(f1, f2 F) *Pair(F) { ... } -``` - -In the call `NewPair(1, 2)` both arguments are untyped constants, so -both are ignored in the first pass. -There is nothing to unify. -We still have two untyped constants after the first pass. -Both are set to their default type, `int`. -The second run of the type unification pass unifies `F` with -`int`, so the final call is `NewPair(int)(1, 2)`. - -In the call `NewPair(1, int64(2))` the first argument is an untyped -constant, so we ignore it in the first pass. -We then unify `int64` with `F`. -At this point the type parameter corresponding to the untyped constant -is fully determined, so the final call is `NewPair(int64)(1, -int64(2))`. - -In the call `NewPair(1, 2.5)` both arguments are untyped constants, -so we move on the second pass. -This time we set the first constant to `int` and the second to -`float64`. -We then try to unify `F` with both `int` and `float64`, so unification -fails, and we report a compilation error. - -Note that type inference is done without regard to constraints. -First we use type inference to determine the type arguments to use for -the function, and then, if that succeeds, we check whether those type -arguments implement the constraints (if any). - -Note that after successful type inference, the compiler must still -check that the arguments can be assigned to the parameters, as for any -function call. - -(Note: type inference is a convenience feature. -Although we think it is an important feature, it does not add any -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 -produces more readable code.) - -### Using types that refer to themselves in constraints - -It can be useful for a generic function to require a type argument -with a method whose argument is the type itself. -For example, this arises naturally in comparison methods. -(Note that we are talking about methods here, not operators.) -Suppose we want to write an `Index` method that uses an `Equal` method -to check whether it has found the desired value. -We would like to write that like this: - -```Go -// Index returns the index of e in s, or -1 if not found. -func Index(type T Equaler)(s []T, e T) int { - for i, v := range s { - if e.Equal(v) { - return i - } - } - return -1 -} -``` - -In order to write the `Equaler` constraint, we have to write a -constraint that can refer to the type argument being passed in. -There is no way to do that directly, but what we can do is write an -interface type that use a type parameter. - -```Go -// Equaler is a type constraint for types with an Equal method. -type Equaler(type T) interface { - Equal(T) bool -} -``` - -To make this work, `Index` will pass `T` as the type argument to -`Equaler`. -The rule is that if a type contraint has a single type parameter, and -it is used in a function's type parameter list without an explicit -type argument, then the type argument is the type parameter being -constrained. -In other words, in the definition of `Index` above, the constraint -`Equaler` is treated as `Equaler(T)`. - -This version of `Index` would be used with a type like `equalInt` -defined here: - -```Go -// equalInt is a version of int that implements Equaler. -type equalInt int - -// The Equal method lets equalInt implement the Equaler constraint. -func (a equalInt) Equal(b equalInt) bool { return a == b } - -// indexEqualInts returns the index of e in s, or -1 if not found. -func indexEqualInt(s []equalInt, e equalInt) int { - return Index(equalInt)(s, e) -} -``` - -In this example, when we pass `equalInt` to `Index`, we check whether -`equalInt` implements the constraint `Equaler`. -Since `Equaler` has a type parameter, we pass the type argument of -`Index`, which is `equalInt`, as the type argument to `Equaler`. -The constraint is, then, `Equaler(equalInt)`, which is satisfied -by any type with a method `Equal(equalInt) bool`. -The `equalInt` type has a method `Equal` that accepts a parameter of -type `equalInt`, so all is well, and the compilation succeeds. - ### Mutually referencing type parameters Within a single type parameter list, constraints may refer to any of @@ -1094,15 +881,410 @@ generic code with multiple type arguments that refer to each other in ways that the compiler can check. -### Pointer methods +### Type inference -There are cases where a generic function will only work as expected if -a type argument `A` has methods defined on the pointer type `*A`. -This happens when writing a generic function that expects to call a -method that modifies a value. +In many cases we can use type inference to avoid having to explicitly +write out some or all of the type arguments. +We can use _function argument type inference_ for a function call to +deduce type arguments from the types of the non-type arguments. +We can use _contraint type inference_ to deduce unknown type arguments +from known type arguments. + +In the examples above, when instantiating a generic function or type, +we always specified type arguments for all the type parameters. +We also permit specifying just some of the type arguments, or omitting +the type arguments entirely, when the missing type arguments can be +inferred. +When only some type arguments are passed, they are the arguments for +the first type parameters in the list. + +For example, a function like this: + +```Go +func Map(type F, T)(s []F, f func(F) T) []T +``` + +can be called in these ways. (We'll explain below how type inference +works in detail; this example is to show how an incomplete list of +type arguments is handled.) + +```Go + var s []int + f := func(i int) int64 { return int64(i) } + var r []int64 + // Specify both type arguments explicitly. + r = Map(int, int64)(s, f) + // Specify just the first type argument, for F, + // and let T be inferred. + r = Map(int)(s, f) + // Don't specify any type arguments, and let both be inferred. + r = Map(s, f) +``` + +If a generic function or type is used without specifying all the type +arguments, it is an error if any of the unspecified type arguments +cannot be inferred. + +(Note: type inference is a convenience feature. +Although we think it is an important feature, it does not add any +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 +produces more readable code.) + +#### Type unification + +Type inference is based on _type unification_. +Type unification applies to two types, either or both of which may be +or contain type parameters. + +Type unification works by comparing the structure of the types. +Their structure disregarding type parameters must be identical, and +types other than type parameters must be equivalent. +A type parameter in one type may match any complete subtype in the +other type. +If the structure differs, or types other than type parameters are not +equivalent, then type unification fails. +A successful type unification provides a list of associations of type +parameters with other types (which may themselves be or contain type +parameters). + +For type unification, two types that don't contain any type parameters +are equivalent if they are identical, or if they are channel types +that are identical ignoring channel direction, or if their underlying +types are equivalent. +It's OK to permit types to not be identical during type inference, +because we will still check the constraints if inference succeeds. + +For example, if `T1` and `T2` are type parameters, `[]map[int]bool` +can be unified with any of the following: + * `[]map[int]bool` + * `T1` (`T1` matches `[]map[int]bool`) + * `[]T1` (`T1` matches `map[int]bool`) + * `[]map[T1]T2` (`T1` matches `int`, `T2` matches `bool`) +(This is not an exclusive list, there are other possible successful +unifications.) + +On the other hand, `[]map[int]bool` cannot be unified with any of + * `int` + * `struct{}` + * `[]struct{}` + * `[]map[T1]string` +(This list is of course also not exclusive; there are an infinite +number of types that cannot be successfully unified.) + +In general we can also have type parameters on both sides, so in some +cases we might associate `T1` with, for example, `T2`, or `[]T2`. + +#### Function argument type inference + +Function argument type inference is used with a function call to infer +type arguments from non-type arguments. +Function argument type inference is not used when a type is +instantiated, and it is not used when a function is instantiated but +not called. + +To see how it works, let's go back to [the example](#Type-parameters) +of a call to the simple `Print` function: + +```Go + Print(int)([]int{1, 2, 3}) +``` + +The type argument `int` in the function call can be inferred from the +type of the non-type argument. + +The only type arguments that can be inferred are those that 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, then those type arguments cannot be inferred using function +argument type inference. + +When the function's type arguments can be inferred, we unify the +caller's argument types with the function's parameter types. +On the caller side we have the list of types of the actual (non-type) +arguments, which for the `Print` example is simply `[]int`. +On the function side is the list of the types of the function's +non-type parameters, which for `Print` is `[]T`. +In the lists, we discard respective arguments for which the function +side does not use a type parameter. +We must then apply type unification to the remaining argument types. + +Function argument type inference is a two-pass algorithm. +In the first pass, we ignore untyped constants on the caller side and +their corresponding types in the function definition. +We use two passes so that in some cases later arguments can determine +the type of an untyped constant. + +We unify corresponding types in the lists. +This will give us an association of type parameters on the function +side to types on the caller side. +If the same type parameter appears more than once on the function +side, it will match multiple argument types on the caller side. +If those caller types are not identical, we report an error. + +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, we determine the default +type of the untyped constant in [the usual +way](https://golang.org/ref/spec#Constants). +Then we unify the types again, this time with no untyped constants. + +In this example + +```Go + s1 := []int{1, 2, 3} + Print(s1) +``` + +we compare `[]int` with `[]T`, match `T` with `int`, and we are done. +The single type parameter `T` is `int`, so we infer that the call to +`Print` is really a call to `Print(int)`. + +For a more complex example, consider + +```Go +// Map calls the function f on every element of the slice s, +// returning a new slice of the results. +func Map(type F, T)(s []F, f func(F) T) []T { + r := make([]T, len(s)) + for i, v := range s { + r[i] = f(v) + } + return r +} +``` + +The two type parameters `F` and `T` are both used for input +parameters, so function argument type inference is possible. +In the call + +```Go + strs := Map([]int{1, 2, 3}, strconv.Itoa) +``` + +we unify `[]int` with `[]F`, matching `F` with `int`. +We unify the type of `strconv.Itoa`, which is `func(int) string`, +with `func(F) T`, matching `F` with `int` and `T` with `string`. +The type parameter `F` is matched twice, both times with `int`. +Unification succeeds, so the call written as `Map` is a call of +`Map(int, string)`. + +To see the untyped constant rule in effect, consider: + +```Go +// NewPair returns a pair of values of the same type. +func NewPair(type F)(f1, f2 F) *Pair(F) { ... } +``` + +In the call `NewPair(1, 2)` both arguments are untyped constants, so +both are ignored in the first pass. +There is nothing to unify. +We still have two untyped constants after the first pass. +Both are set to their default type, `int`. +The second run of the type unification pass unifies `F` with +`int`, so the final call is `NewPair(int)(1, 2)`. + +In the call `NewPair(1, int64(2))` the first argument is an untyped +constant, so we ignore it in the first pass. +We then unify `int64` with `F`. +At this point the type parameter corresponding to the untyped constant +is fully determined, so the final call is `NewPair(int64)(1, +int64(2))`. + +In the call `NewPair(1, 2.5)` both arguments are untyped constants, +so we move on the second pass. +This time we set the first constant to `int` and the second to +`float64`. +We then try to unify `F` with both `int` and `float64`, so unification +fails, and we report a compilation error. + +Note that function argument type inference is done without regard to +constraints. +First we use function argument type inference to determine type +arguments to use for the function, and then, if that succeeds, we +check whether those type arguments implement the constraints (if +any). + +Note that after successful function argument type inference, the +compiler must still check that the arguments can be assigned to the +parameters, as for any function call. + +#### Constraint type inference + +Constraint type inference permits inferring a type argument from +another type argument, based on type parameter constraints. +Constraint type inference is useful when a function wants to have a +type name for an element of some other type parameter, or when a +function wants to apply a constraint to a type that is based on some +other type parameter. + +Constraint type inference can only infer types if some type parameter +has a constraint that has a type list with exactly one type in it. +We call such a constraint a _structural constraint_, as the type list +describes the structure of the type. +A structural constraint may also have methods in addition to the type +list, but the methods are ignored by constraint type inference. +For constraint type inference to be useful, the constraint type will +normally refer to one or more type parameters. + +Constraint type inference is applied after function argument type +inference. +It is only tried if there is at least one type parameter whose type +argument is not yet known. + +We start by creating a mapping from type parameters to type arguments. +We initialize the mapping with all type parameters whose type +arguments are already known, if any. + +For each type parameter with a structural constraint, we unify the +type parameter with the single type in the constraint's type list. +This will have the effect of associating the type parameter with its +constraint. +We add the result into the mapping we are maintaining. +If unification finds any associations of type parameters, we add those +to the mapping as well. +When we find multiple associations of any one type parameter, we unify +each such association to produce a single mapping entry. +If a type parameter is associated directly with another type +parameter, meaning that they must both be matched with the same type, +we unify the associations of each parameter together. +If any of these various unifications fail, then constraint type +inference fails. + +After merging all type parameters with structural constraints, we have +a mapping of various type parameters to types (which may be or contain +other type parameters). +We continue by looking for a type parameter `T` that is mapped to a +fully known type argument `A`, one that does not contain any type +parameters. +Anywhere that `T` appears in a type argument in the mapping, we +replace `T` with `A`. +We repeat this process until we have replaced every type parameter. + +##### Element constraint example + +For an example of where constraint type inference is useful, let's +consider a function that takes a defined type that is a slice of +numbers, and returns an instance of that same defined type in which +each number is doubled. + +Using type lists, it's easy to write this function if we don't care +about [defined types](https://golang.org/ref/spec#Type_definitions). + +```Go +// Double returns a new slice that contains all the elements of s, doubled. +func Double(type E constraints.Number)(s []E) []E { + r := make([]E, len(s)) + for i, v := range s { + r[i] = v + v + } + return r +} +``` + +However, with that definition, if we call the function with a defined +slice type, the result will not be that defined type. + +```Go +// MySlice is a slice of ints. +type MySlice []int + +// The type of V1 will be []int, not MySlice. +// Here we are using function argument type inference, +// but not constraint type inference. +var V1 = Double(MySlice{1}) +``` + +We can do what we want by introducing a new type parameter. + +```Go +// SC constraints a type to be a slice of some type E. +type SC(type E) interface { + type []E +} + +// DoubleDefined returns a new slice that contains the elements of s, +// doubled, and also has the same type as s. +func DoubleDefined(type S SC(E), E constraints.Number)(s S) S { + // Note that here we pass S to make, where above we passed []E. + r := make(S, len(s)) + for i, v := range s { + r[i] = v + v + } + return r +} +``` + +Now if we use explicit type arguments, we can get the right type. + +```Go +// The type of V2 will be MySlice. +var V2 = DoubleDefined(MySlice, int)(MySlice{1}) +``` + +Function argument type inference by itself is not enough to infer the +type arguments here, because the type parameter E is not used for any +input parameter. +But a combination of function argument type inference and constraint +type inference works. + +```Go +// The type of V3 will be MySlice. +var V3 = DoubleDefined(MySlice{1}) +``` + +First we apply function argument type inference. +We see that the type of the argument is `MySlice`. +Function argument type inference ignores constraints. +It matches the type parameter `S` with `MySlice. + +We then move on to constraint type inference. +We know one type argument, `S`. +We see that a type argument, `S` again, has a structural type +constraint. + +We create a mapping of known type arguments: + +``` +{S -> MySlice} +``` + +We then unify each type parameter with a structural constraint with +the single type listed by that constraint. +In this case the structural constraint is `SC(E)` which has the single +type `[]E`, so we unify `S` with `[]E`. +Since we already have a mapping for `S`, we then unify `[]E` with +`MySlice`. +As `MySlice` is defined as `[]int`, that associates `E` with `int`. +We now have: + +``` +{S -> MySlice, E -> int} +``` + +We then substitute `E` with `int`, which changes nothing, and we are +done. +The type arguments for this call to `DoubleDefined` are `(MySlice, +int)`. + +This example shows how we can use constraint type inference to set a +type name for an element of some other type parameter. +In this case we can name the element type of `S` as `E`, and we can +then apply further constraints to `E`, in this case requiring that it +be a number. + +##### Pointer method example Consider this example of a function that expects a type `T` that has a -`Set(string)` method that initializes the value based on a string. +`Set(string)` method that initializes a value based on a string. ```Go // Setter is a type constraint that requires that the type @@ -1115,8 +1297,8 @@ // calling the Set method to set each returned value. // // Note that because T is only used for a result parameter, -// type inference does not work when calling this function. -// The type argument must be passed explicitly at the call site. +// function argument type inference does not work when calling +// this function. // // This example compiles but is unlikely to work as desired. func FromStrings(type T Setter)(s []string) []T { @@ -1128,11 +1310,10 @@ } ``` -Now let's see some code in a different package (this example is -invalid). +Now let's see some calling code (this example is invalid). ```Go -// Settable is a integer type that can be set from a string. +// Settable is an integer type that can be set from a string. type Settable int // Set sets the value of *p from a string. @@ -1173,24 +1354,21 @@ The problem is that `FromStrings` creates a slice of type `[]T`. When instantiated with `*Settable`, that means a slice of type `[]*Settable`. -When `FromStrings` calls `result[i].Set(v)`, that passes the pointer -stored in `result[i]` to the `Set` method. +When `FromStrings` calls `result[i].Set(v)`, that invokes the `Set` +method on the pointer stored in `result[i]`. That pointer is `nil`. -The `Settable.Set` method will be invoked with a `nil` receiver, -and will raise a panic due to a `nil` dereference error. +The `Settable.Set` method will be invoked with a `nil` receiver, and +will raise a panic due to a `nil` dereference error. -What we need is a way to write `FromStrings` such that it can take -the type `Settable` as an argument but invoke a pointer method. +What we need is a way to write `FromStrings` such that it can take the +type `Settable` as an argument but invoke a pointer method. To repeat, we can't use `Settable` because it doesn't have a `Set` method, and we can't use `*Settable` because then we can't create a slice of type `Settable`. -One approach that could work would be to use two different type -parameters: both `Settable` and `*Settable`. +What we can do is pass both types. ```Go -package from - // Setter2 is a type constraint that requires that the type // implement a Set method that sets the value from a string, // and also requires that the type be a pointer to its type parameter. @@ -1203,7 +1381,7 @@ // calling the Set method to set each returned value. // // We use two different type parameters so that we can return -// a slice of type T but call methods on *T. +// a slice of type T but call methods on *T aka PT. // The Setter2 constraint ensures that PT is a pointer to T. func FromStrings2(type T interface{}, PT Setter2(T))(s []string) []T { result := make([]T, len(s)) @@ -1218,7 +1396,7 @@ } ``` -We would call `FromStrings2` like this: +We can then call `FromStrings2` like this: ```Go func F2() { @@ -1231,121 +1409,164 @@ } ``` -This approach works as expected, but it is awkward. -It forces `F2` to work around a problem in `FromStrings2` by passing -two type arguments. -The second type argument is required to be a pointer to the first type -argument. -This is a complex requirement for what seems like it ought to be a -reasonably simple case. - -Another approach would be to pass in a function rather than calling a -method. - -```Go -// FromStrings3 takes a slice of strings and returns a slice of T, -// calling the set function to set each returned value. -func FromStrings3(type T)(s []string, set func(*T, string)) []T { - results := make([]T, len(s)) - for i, v := range s { - set(&results[i], v) - } - return results -} -``` - -We would call `Strings3` like this: +This approach works as expected, but it is awkward to have to repeat +`Settable` in the type arguments. +Fortunately, constraint type inference makes it less awkward. +Using constraint type inference we can write ```Go func F3() { - // FromStrings3 takes a function to set the value. - // Settable is as above. - nums := FromStrings3(Settable)([]string{"1", "2"}, - func(p *Settable, s string) { p.Set(s) }) + // Here we just pass one type argument. + nums := FromStrings2(Settable)([]string{"1", "2"}) // Now nums is []Settable{1, 2}. -} -``` - -This approach also works as expected, but it is also awkward. -The caller has to pass in a function just to call the `Set` method. -This is the kind of boilerplate code that we would hope to avoid when -using generics. - -Although these approaches are awkward, they do work. -That said, we suggest another feature to address this kind of issue: a -way to express constraints on the pointer to the type parameter, -rather than on the type parameter itself. -The way to do this is to write the type parameter as though it were a -pointer type: `(type *T Constraint)`. - -Writing `*T` instead of `T` in a type parameter list changes two -things. -Let's assume that the type argument at the call site is `A`, and the -constraint is `Constraint` (this syntax may be used without a -constraint, but there is no reason to do so). - -The first thing that changes is that `Constraint` is applied to `*A` -rather than `A`. -That is, `*A` must implement `Constraint`. -It's OK if `A` implements `Constraint`, but the requirement is that -`*A` implement it. -Note that if `Constraint` has any methods, this implies that `A` must -not be a pointer type: if `A` is a pointer type, then `*A` is a -pointer to a pointer, and such types never have any methods. - -The second thing that changes is that within the body of the function, -any methods in `Constraint` are treated as though they were pointer -methods. -They may only be invoked on values of type `*T` or addressable values -of type `T`. - -```Go -// FromStrings takes a slice of strings and returns a slice of T, -// calling the Set method to set each returned value. -// -// We write *T, meaning that given a type argument A, -// the pointer type *A must implement Setter. -// -// Note that because T is only used for a result parameter, -// type inference does not work when calling this function. -// The type argument must be passed explicitly at the call site. -func FromStrings(type *T Setter)(s []string) []T { - result := make([]T, len(s)) - for i, v := range s { - // result[i] is an addressable value of type T, - // so it's OK to call Set. - result[i].Set(v) - } - return result -} -``` - -Again, using `*T` here means that given a type argument `A`, the type -`*A` must implement the constraint `Setter`. -In this case, `Set` must be in the method set of `*A`. -Within `FromStrings`, using `*T` means that the `Set` method may only -be called on an addressable value of type `T`. - -We can now use this as - -```Go -func F() { - // With the rewritten FromStrings, this is now OK. - // *Settable implements Setter. - nums := from.Strings(Settable)([]string{"1", "2"}) - // Here nums is []Settable{1, 2}. ... } ``` -To be clear, using `type *T Setter` does not mean that the `Set` -method must only be a pointer method. -`Set` could still be a value method. -That would be OK because all value methods are also in the pointer -type's method set. -In this example that only makes sense if `Set` can be written as a -value method, which might be the case when defining the method on a -struct that contains pointer fields. +There is no way to avoid passing the type argument `Settable`. +But given that type argument, constraint type inference can infer the +type argument `*Settable` for the type parameter `PT`. + +As before, we create a mapping of known type arguments: + +``` +{T -> Settable} +``` + +We then unify each type parameter with a structural constraint. +In this case, we unify `PT` with the single type of `Setter2(T)`, +which is `*T`. +The mapping is now + +``` +{T -> Settable, PT -> *T} +``` + +We then replace `T` with `Settable` throughout, giving us: + +``` +{T -> Settable, PT -> *Settable} +``` + +After this nothing changes, and we are done. +Both type arguments are known. + +This example shows how we can use constraint type inference to apply a +constraint to a type that is based on some other type parameter. +In this case we are saying that `PT`, which is `*T`, must have a `Set` +method. +We can do this without requiring the caller to explicitly mention +`*T`. + +##### Constraints apply even after constraint type inference + +Even when constraint type inference is used to infer type arguments +based on constraints, we must still check the constraints after the +type arguments are determined. + +In the `FromStrings2` example above, we were able to deduce the type +argument for `PT` based on the `Setter2` constraint. +But in doing so we only looked at the type list, we didn't look at the +methods. +We still have to verify that the method is there, satisfying the +constraint, even if constraint type inference succeeds. + +For example, consider this invalid code: + +```Go +// Unsettable is a type that does not have a Set method. +type Unsettable int + +func F4() { + // This call is INVALID. + nums := FromString2(Unsettable)([]string{"1", "2"}) + ... +} +``` + +When this call is made, we will apply constraint type inference just +as before. +It will succeed, just as before, and infer that the type arguments are +`(Unsettable, *Unsettable)`. +Only after constraint type inference is complete will we check whether +`*Unsettable` implements the constraint `Setter2(Unsettable)`. +Since `*Unsettable` does not have a `Set` method, constraint checking +will fail, and this code will not compile. + +### Using types that refer to themselves in constraints + +It can be useful for a generic function to require a type argument +with a method whose argument is the type itself. +For example, this arises naturally in comparison methods. +(Note that we are talking about methods here, not operators.) +Suppose we want to write an `Index` method that uses an `Equal` method +to check whether it has found the desired value. +We would like to write that like this: + +```Go +// Index returns the index of e in s, or -1 if not found. +func Index(type T Equaler)(s []T, e T) int { + for i, v := range s { + if e.Equal(v) { + return i + } + } + return -1 +} +``` + +In order to write the `Equaler` constraint, we have to write a +constraint that can refer to the type argument being passed in. +There is no way to do that directly, but what we can do is write an +interface type that use a type parameter. + +```Go +// Equaler is a type constraint for types with an Equal method. +type Equaler(type T) interface { + Equal(T) bool +} +``` + +To make this work, `Index` will pass `T` as the type argument to +`Equaler`. +The rule is that if a type contraint has a single type parameter, and +it is used in a function's type parameter list without an explicit +type argument, then the type argument is the type parameter being +constrained. +In other words, in the definition of `Index` above, the constraint +`Equaler` is treated as `Equaler(T)`. + +This version of `Index` would be used with a type like `equalInt` +defined here: + +```Go +// equalInt is a version of int that implements Equaler. +type equalInt int + +// The Equal method lets equalInt implement the Equaler constraint. +func (a equalInt) Equal(b equalInt) bool { return a == b } + +// indexEqualInts returns the index of e in s, or -1 if not found. +func indexEqualInt(s []equalInt, e equalInt) int { + return Index(equalInt)(s, e) +} +``` + +In this example, when we pass `equalInt` to `Index`, we check whether +`equalInt` implements the constraint `Equaler`. +Since `Equaler` has a type parameter, we pass the type argument of +`Index`, which is `equalInt`, as the type argument to `Equaler`. +The constraint is, then, `Equaler(equalInt)`, which is satisfied +by any type with a method `Equal(equalInt) bool`. +The `equalInt` type has a method `Equal` that accepts a parameter of +type `equalInt`, so all is well, and the compilation succeeds. + +(Note: using the type parameter as the default argument for its +constraint is a convenience feature. +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 +produces more readable code.) ### Using generic types as unnamed function parameter types @@ -1391,7 +1612,7 @@ In this design, values of generic types are not boxed. For example, let's look back at our earlier example of -`from.Strings`. +`FromStrings2`. When it is instantiated with type `Settable`, it returns a value of type `[]Settable`. For example, we can write @@ -1401,14 +1622,13 @@ type Settable int // Set sets the value of *p from a string. -func (p *Settable) Set(s string) (err error) { +func (p *Settable) Set(s string) { // same as above } func F() { // The type of nums is []Settable. - nums, err := from.Strings(Settable)([]string{"1", "2"}) - if err != nil { ... } + nums := FromStrings2(Settable)([]string{"1", "2"}) // Settable can be converted directly to int. // This will set first to 1. first := int(nums[0]) @@ -1416,8 +1636,8 @@ } ``` -When we call `from.Strings` with the type `Settable` we get back a -`[]Settable` (and an error). +When we call `FromStrings2` with the type `Settable` we get back a +`[]Settable`. The elements of that slice will be `Settable` values, which is to say, they will be integers. They will not be boxed, even though they were created and set by a @@ -2013,49 +2233,6 @@ The current design seems to us to be the nicest, but perhaps something better is possible. -##### Defined composite types - -As [discussed above](#Type-parameters-in-type-lists), an extra type -parameter is required for a function to take, as an argument, a -defined type whose underlying type is a composite type, and to return -the same defined type as a result. - -For example, this function will map a function across a slice. - -```Go -// Map applies f to each element of s, returning a new slice -// holding the results. -func Map(type T)(s []T, f func(T) T) []T { - r := make([]T, 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 -// MySlice is a defined type. -type MySlice []int - -// DoubleMySlice returns a new MySlice whose elements are twice -// that of the corresponding elements of s. -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](#Type-parameters-in-type-lists), this can be -avoided by using an extra type parameter for `Map`, and using -constraints that describe the required relationship between the slice -and element types. -This works but is awkward. - ##### Identifying the matched predeclared type The design doesn't provide any way to test the underlying type matched