Archive: Regarding the Go 2 Generics Draft

Pondering and explorations

Update: as generics are now a part of the Go language, and because this article is a review of a draft that does not reflect the final proposal that was adopted, this article should not be considered a source of particularly relevant information.

On August 27th the Go Blog announced Go 2 Draft Designs, marking exceptional progress in the formal design of selected portions of Go 2. Here, I will particularly explore and respond to the problem overview and contracts drafts of the generics design, authored by Ian Lance Taylor, Robert Griesemer, and Russ Cox.

To the draft authors: I am organizing this article into three sections: interesting implications and restrictions, as particularly requested in the feedback section of the overview; draft typos and clarification requests; and random explorations of the topic, including alternatives and enhancement ideas. I am also making some effort to not repeat the feedback that others linked in the wiki feedback page. To other respondents/bloggers: for posterity, please don’t remove feedback even if at some point it seems no-longer-applicable, since complex designs are a mesh of co-dependent considerations in which rejected design aspects can sometimes suddenly, transitively become a part of the draft again.

First, some general feedback: over the last several days, I have been equivocating between really liking the draft design, and being concerned that a number of details are hard to remember (e.g. when and when not to use a type keyword and what the inference rule restrictions are). Contracts are a very clever solution to many of the syntactical and semantic pitfalls that we have encountered in past designs, yet, as mentioned later in this document, contracts will likely be hard to statically analyze except in trivial cases (what the compiler needs to do is perhaps one of the more trivial cases, which is part of why the solution is so appealing). In general, at this time, I’m in favor of the broad direction the design draft is pointed toward.

A note on syntax: I initially found myself unpersuaded by the choice of parentheses to encapsulate type parameters. It quickly became clear though that generic functions are really a function that takes types and returns another function. In other words, generic functions are just first-class functions that operate on types. The draft-syntax for the following function…

func Sum(type T addable)([]T) T

… really behaves like:

func Sum(type T addable) func([]T) T

It would just be more painful in practice to use generic functions if they used such a syntax. The syntax proposed in the contracts draft is succinct for many uses, and is appropriate given the semantics.

Interesting Implications and Restrictions

Stealthy Variadics

The most straightforward notation for describing a call in a contract does very little to restrict that call, for better or worse, especially with respect to variadic parameters.

contract binaryop(f F, x T) {
    x = f(x, x)
}

This contract could be satisfied by math.Max, or func Sum(int, ...int) int, or func(int, int, ...Option) int, or even fmt.Sprintf (when A is a string)! In other words, this contract says deceptively little about the behavior of F.

It’s unclear if it’s good for the most convenient way to express a call in a contract to leave many potentially important details unspecified. In this regard, such contracts can be said to merely ensure that a square peg fits in a square hole, but does not establish any meaningful constraints on behavior (it doesn’t prevent the existence of unnoticed holes or arbitrary shape). Is the mere implementation of a loose contract sufficient license for the library importer to call a function without further consideration (“if it compiles, it’s probably correct”)? I can imagine that, in most cases the author of the such a contract would have implicitly intended to also have specified the constraint:

var _ func(T, T) T = f

Maybe their generic function is called AddMatrix, with clear assumptions about the behavior of the callback, such as commutativity of arguments. Maybe it’s just a type-preserving Reduce variant. In any case, perhaps go vet should attempt to determine when a contract is under-specified. Perhaps the compiler can reject contracts that make incomplete proofs about the signature of a call.

Generic interfaces

There is a strange intersection between interfaces and generic types in the form of generic interfaces. The purpose of an interface is to provide run-time polymorphic functionality (usually without sacrificing safety). Using the new terminology, we could say that interfaces provide a way of enforcing a run-time contract, while generics implement a compile-time contract.

Any given interface becomes more valuable as more types implement it, thus the decision to reduce the number of types that can implement an interface is usually undesirable. For this reason, generic interfaces seem to be less valuable compared interfaces that do not depend on generics. Let’s consider an example:

type ContainerLesser interface {
    Less(i, j int) bool
}
type ElemLesser(type T) interface {
    Less(T) bool
}

ContainerLesser is just a subset of sort.Interface, and is semantically sufficient for comparing any two indices in the same indexed container. ElemLesser is a bit different: the receiver value is directly compared to the call parameter; it is more flexible, and implementations can serve as the basis for a ContainerLesser. Ironically, though, ElemLesser is less generic: an ElemLesser(int) is an entirely unrelated to and incompatible with ElemLesser(string). The concrete method Less(string) is valuable only in its expressive convenience to the programmer, but ElemLesser itself is rather unlikely to be used to build meaningful algorithms. Put another way, an []ElemLesser(string) is going to have the same boxing overhead as any other slice of interface, but due to the over-specificity of the interface, has much less of an opportunity for multiple concrete types to share the same type.

I can imagine cases where parameterized interfaces could be used appropriately, such as an algorithm that works on slices of Valuer(int), slices of Valuer(string), etc. Valuer in this case would be:

type Valuer(type T) interface {
    Value() T
}

It is nicer to work with than []interface { Value() interface{} }, and it could result in heterogeneous slices, for example. Still, it seems equally likely to cause fragmentation as it does to result in better safety. Valuer is really a family of interfaces.

Non-method pseudo-interfaces

It is possible to define a contract that looks similar to an interface, except with the additional requirement that the specified calls cannot be method.

contract Reader(type R)(r R) {
    (func([]byte) (int, error))(r.Read)
    r.Read = nil
}

In this example, r.Read must be a field, since methods cannot be assigned over. While it’s not possible for a contract to directly define what a type cannot do, it is possible to constrain the possible kinds that can satisfy the contract. Ultimately, the intersection of properties define the kinds of types that can be used.

First-class generic functions

The Generics Draft defines the type-inference rules generic types, in particular that inference can only stem from input parameters. It’s unclear the inability to directly infer the types of return parameters is a mechanical limitation (“we can’t do it even if we wanted to”), a wait-and-see limitation (“we can do it, but it might not be a good idea”), or a deliberate design decision (“we can do it but we know it’s a bad idea”).

In any case, this design decision does lead to a few asymmetries. Consider this example:

func Set(type T)(t *T, v T) func() {
    return func() { *t = v }
}
func SetZero(type T)(t *T) func() {
    var zero T
    return Set(t, zero)
}
func main() {
    x := 5
    fmt.Println(x)     // prints 5
    SetZero(int)(&x)() // explicit type parameter
    SetZero(&x)()      // type-inference equivalent
    fmt.Println(x)     // prints 0
}

Now consider a similar example:

func AtIndex(type T)(i int) func([]T) T {
    return func(lst []T) T { return lst[i] }
}
func main() {
    x := AtIndex(1)([]int{9, 8, 7})      // NOT valid
    x := AtIndex(int)(1)([]int{9, 8, 7}) // valid
    fmt.Println(x)                       // prints 8
}

Container- or element-level generics?

The generics draft, as written, does allow many algorithms to be expressed as either a container-level algorithm (sort.Sort operates on the container level via ingenious use of interfaces, but is mostly used with slices), or the element level (the draft provides an example of a generic sort signature).

In general, container-level algorithms are more flexible, but not necessarily meaningfully so (range iteration over a channel is very different than single-assignment range iteration over a slice). We can demote a container-level contract into, effectively, an element-level contract fairly trivially:

contract sliceWithMethod(t T) {
    fmt.Stringer // T has a `String() string` method
    u := t[0]    // T is a slice, array, or map[numeric]anything
    append(t, u) // T is a slice
    io.Reader(u) // T's elements implement Reader, but T isn't
                 //     necessarily a []io.Reader
}

Strictly speaking, t[0] could have been used anywhere that u appeared, removing the need for the second line. For more complex, probably overly-draconian contracts, such as a slice of maps of value types that happen to have a “Name” field, assignment becomes useful.

The draft or community should provide a recommendation about when to use container- or element-level generics.

Matching maps

We can distinguish between a slice and a map using a “comma-ok” assignment:

contract mapOnly(t T, u U) {
    _, _ = t[u]
}

Single assignment would work for slices when u is an integer type, but dual assignment from an index expression is only supported by maps.

Generic slices.Copy supporting string

Normally, a generic function cannot be given a specialized implementation based on the actual types encountered, but with clever use of contracts, we may be able to achieve that result anyway:

contract copyable(t T, u U) {
    len(t)
    len(u)
    t[0] = u[0]
}
func Copy(type T, U copyable)(dst T, src U) int {
    l := len(dst)
    if len(src) < l {
        l = len(src)
    }
    i := 0
    for ; i < l; i++ {
        dst[i] = src[i]
    }
    return i
}

This implementation of Copy has a very loose contract, and relates two container types rather than expressing both arguments as being of the same type. This allows, among other things: a copy from string to []byte (both share the same element type), a copy from slice to map or map to slice, if the map’s key type is an integer and the element type of the slice is assignable to the value type of the map. It allows for copying from or to an array (though copying to an array is only meaningful if an array pointer is passed). This function also allows allows a copy from any of these into a []interface{} suitable for passing to fmt.Println.

With a little work, we could end up with a converting Copy (it’s essentially just a non-allocating Map), or an Append with similar properties.

Minimum array size

A contract can be used to specify a minimum requirements for an array, since the size of an array is part of its type.

contract atLeast5(x T) {
    x[5]   // matches map[numeric]T, array, *array, and slice
    x == x // out of the above, only matches array and *array with
           // "comparable" element type.
}

Any function that uses the atLeast5 contract would be able to access indices zero through five, inclusive. Consequently, T could be any array that has at least size 6. An [1000]bool would satisfy this contract, for example.

This does depend on the Go compiler considering an array index operation with a constant operand to be a “type check” since contracts only check types. Since the size of an array is part of its type, this seems reasonable to at least special-case.

Numeric constraints

Similarly to constraining arrays, numeric types can also be constrained according to a minimum range:

contract bits16plus(n N) {
    n = 256 // 256 is one higher than uint8 can represent
}

Here, bits16plus constrains to types that 256 does not overflow. This includes int16, uint16, int32, uint32, int64, uint64, int, uint, uintptr. It also includes float32, float64, complex64, and complex128, all of which are pretty hard to overflow since they use exponents internally and thus can have trade range for precision, and vice versa.

Let’s say we only want 32+ bit integers:

contract integers32plus(n N) {
    n = 1 << 16 // 32768 is one higher than uint16 can represent
    n ^ n       // xor is not defined on float or complex types
}

This is similar to the previous contract, but we have constrained the type further by using a bitwise operation (and bitwise operator or % will do). Now, only int32, uint32, int64, uint64, int, uint, uintptr can be represented.

What about allowing only signed integer types?

contract signed(n N) {
    n = -1 // -1 overflows unsigned types
    n ^ n
}

And only allowing unsigned integer types?

contract unsigned(n N) {
    1 << n // the right side of a shift must be unsigned
}

Complex numbers only?

contract complex(n N) {
    n + 0i // or real(n)
}

Floats only?

contract float(n N) {
    n + 0.1    // complex numbers also satisfy this
    float64(n) // complex numbers cannot be converted to floats
}

“Are interfaces just sugared contracts?”

DeedleFake asks if interfaces are now just more restrictive contracts. I’ll claim that interfaces are more powerful than contracts. Contracts don’t provide anything that code generation or writing near-duplicate code for a type could not achieve, since even with the proposal, Go doesn’t have first-class types (nor is it seeking to).

Interfaces provide something that contracts cannot: Axel Wagner pointed out that slices (or other structures) of interfaces behave very differently to slices of generic types, such that interfaces can have runtime-polymorphic behavior but generics cannot (unless the generic function is instantiated with an interface type).

Whether or not we provide generics, we cannot get rid of something like interfaces, or else the language will become less powerful. It would be beneficial to clarify the roles of interfaces and generics in a Go2 world, since it seems likely that generics will be used in places where interfaces are most appropriate, leading to some algorithms (such as worker pools) being much less useful.

Tooling support

While is should be fairly inexpensive for types to be checked against a contract, the inverse may not be true: it will likely be very difficult to create an efficient query in guru (or an equivalent tool) to answer the question: “what list of types can satisfy this contract?” This is because an efficient answer would require deducing properties of types and limiting the selection of candidates, rather than trying every single permutation of known types. Similar questions around generic function type parameterization would be equivalently expensive. Users will want such a tool, having grown accustomed to asking (and receiving a quick enough answer to) the related question: “which types implement this interface?”

I do recommend that gofmt ship with contract simplifying support at time of generics launch: we should set the expectation that while the meaning of a contract is consistent, the possible equivalent representations are fluid, and thus there is a canonical representation that finds a balance between readability and simplicity. Roger Peppe discusses canonicalization of contracts more thoroughly.

Draft Typos and Clarification Requests

Call arity

In the contracts draft, there is one instance of the text:

check.Convert(int, interface{})(0, 0)

I believe it should instead be:

check.Convert(int, interface{})(0)

Alternatively, please provide an explanation as to why it the function should take two zeros instead of one.

Syntactical inconsistency

Looking at the signature of the Convert example from the contracts draft:

func Convert(type To, From convert)(from From) To

There is something peculiar about the type parameter syntax. Normal function parameter definitions look like: (var1, var2 typeA, var3 typeB). Here, var1 and var2 have type type while var3 has type typeB. Applying the same scheme to the above type parameter parenthetical, ignoring keywords, it looks like there is a variable called type of type To, and a variable called From of type convert.

Ignoring the type keyword, To, From convert does read like To and From both have type convert, which is a bit more regular, but since contracts are optional, type To, From would again look irregular.

Clearly type parameters don’t follow the same pattern as regular parameters, which makes their specific syntax, honestly, quite hard to remember.

Perhaps a different ordering would align more closely with regular parameter syntax:

func Convert(To, From type convert)(from From) To

This would read as: To and From are variables of [meta] type type. Even with the convert contract, the syntax is regular since To and From pair with type, and the presence or omission of a contract does not change that.

Visual similarity with chained calls

The explicit generic instantiation-and-call syntax is hard to distinguish from existing syntax for chained calls of first class functions. Consider:

// g is the simplest generic function
func g(type T)() {}
g(int)()
// No generics involved. This works today.
func f(x int) func() { return func() {} }
int := 5
f(int)()

Notice that if int is shadowed by a variable, the calls are indistinguishable until int is resolved into either a type or a variable.

Redundant contract parameters

It appears that contract type parameters can each be associated with multiple variables, for example:

contract add(a, b T) {
    a + b
}

This is unnecessary since a and b have the same type, and thus having two such variables cannot possibly be used to express any type-based constraints beyond what a single variable can express.

append

Should append be redefined as:

append(type T)(dst []T, src ...T)

And as a special case, accept calls as either append([]int(nil), 1, 2, 3) and append(int)(nil, 1, 2, 3)?

Sort

In the contracts draft, there is the example:

sort.OrderedSlice([]string{"a", "c", "b"})

Passing a slice literal to OrderedSlice (or any other sort function) would serve no purpose since the result would not be observable. Please clarify this as:

s := []string{"a", "c", "b"}
sort.OrderedSlice(s)

Context example

The contract draft provides a type-safe context values example. In the comment for the Key type is the following line:

Rather than calling Context.Value directly, use Key.Load

Key.Load is not defined. Perhaps the comment should refer to Key.Value?

“No generic methods?”

One consequence of the dual-implementation constraint is that we have not included support for type parameters in method declarations.

The above quote from the generics overview can be easily misinterpreted as indicating that generic methods are not supported at all. A reading of the contract draft does show that a method’s explicit arguments and return values can use indeed use type parameters listed in the receiver. Still, we should not expect everyone who reads the overview to read the contract draft (nor can we assume they will be read in quick succession). Therefore, I request for this part of the overview document to be clarified to indicate that some uses generics in methods are allowed.

Mutually referential type parameters

Because of the way that the contract is written, we could also use the non-pointer types Vertex and FromTo

As written, the contracts draft seems to suggest that contracts may allow normal method-set rules/expectations to be violated in contracts that happen to look a lot like interfaces. I hope this is not the case.

Addressability needs to be handled in contracts in a safe way. Certainly if I define my type’s methods with pointer receivers, a variable of the value type can have pointer receivers called on it, as normal. Similarly, a non-pointer field of my type contained in a struct with its own pointer receivers is fine. But contracts should not permit the compiler to carelessly take the address of a copy, at least in any case where the compiler would reject similar behavior with interfaces.

Use of an unexported identifier

Consider the following contract:

package x
contract Unclear(t T) {
    t.name()
}

This could either require that T have a name method, or that T have a name field (that happens to be callable). What is the meaning of that contract when used in the package that defines it? Can only types that are defined in the same package implement that contract?

Since the contract is itself exported, what’s the meaning when used in generics defined in another package? Does any function defined in package y using that x.Unclear accept only types defined in package y? Or do those functions in package y only accept types from package x?

Relationship of len, cap, <-x, and x[y] to range iteration

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.

len and cap imply more than just that those specific builtin functions can be called on a given type. The documentation for len lists only those types which are also suitable for use in a range loop expression, thus at least the compiler could infer the ability to loop over any x which implements a contract containing len(x). Granted, channels have different loop semantics than everything else, and the most that can be inferred from len(x) with respect to iteration is single clause assignment.

A generally better approach would be to use other syntactical features shared with kinds that can be used in range loop expressions. For example, x[y] in the current language implies the ability to do one- or two-assignment range iteration (where the second variable assigned into is always the “value”). Similarly, <-x implies the ability to do single-assignment range iteration.

Were these potential avenues of inference specifically excluded? As I understand it, the particular grammar allowed in a contract, in particular, is still an open area of consideration. If only expressions and basic statements should be allowed, as suggested by Roger Peppe, it may be desirable to infer basic loop-ability rules defined by another means, such as those listed above.

It is certainly much less intuitive that, e.g. use of an index operator in a contract provides the ability to loop. Such contracts may indeed not be needed if such operations are not allowed to be generic, such that looping could only occur on []T1 or map[T2]T3 rather than a T3 that just happens to be a contract-proven container capable of looping. But given that contract grammar could change, it would be worth listing the motivation for why such inferences are disallowed (such as for clarity reasons), if they were considered and rejected.

Untyped constant intervals

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.

Can we not make reasonable inferences beyond what was stated in the draft? If we observe the single value -129, we can infer that we are able to at least utilize the range that corresponds to an int16: [-32768, 32767]. Further, we can infer that the following types can implement a contract: int16, int32, int64, float32, float64, complex64, complex128.

What is the rationale for restricting the allowed range to [min(observed…), max(observed…)]? Is there some plan for supporting numeric types with an application-bounded range?

Untyped boolean

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:

Wouldn’t !x or x && true be simpler equivalents to using conditionals in a contract?

Contract requiring variadic argument

There is no way to specify that a method takes variadic arguments.

I don’t believe that statement is true.

contract variadic(t T, u []U) {
    t.Method(u...)
}

Inference in generic types

Type parameter inference is defined for generic functions, but not for generic types. Consider the following generic type and constructor:

type X(type T) struct {
    Field T
}
func NewX(type T)() X(T) {
    return X{}
}

Is it necessary for the X returned from NewX to be qualified as X(T)? If there is exactly one type parameter in both a function and a type, could the signature of NewX just read as follows?

func NewX(type T)() X

Contract propagation

Can a generic function without restrictions call a generic function with restrictions?

// Map is defined as normal, and has normal semantics
func Map(type T, U)(fn func(T) U, lst []T) []U
contract multiply(t T) { t * t }
func Square(type T multiply)(t T) T { return t * t }
var squared = Map(Square, []int{1, 2, 3})

Would this compile? Can Map, which knows nothing about its type parameters except for the properties shared by all types, call the Square function, which requires a type that can be multiplied? Further, can using Square as a first-class value even infer its own type parameter from the []int during unification?

Is type parameter inference limiting future growth?

This is a bit of a stretch, but… If Go hypothetically ever gets true first class types, would type parameter inference, as described in the contracts draft, make use of those first class types semantically ambiguous? Should, for example, ellipsis be allowed as a way to make inference explicit, as in:

Sum(...)([]int{1,2,3}) // equivalent to Sum([]int{1,2,3})

First class types would allow a function to return another function of as-yet-undetermined type, thus, a hypothetical Sum could take a []int and choose to return a function or a non-function depending on its input values, types, or both. Languages like Idris have such capabilities, but do not allow what amount to calls to be elided, as in the case with type parameter inference.

Miscellaneous Thoughts

These are likely not ideas worth adopting, but what follows is a compendium of thoughts, counter proposals and proposal extensions. Hopefully they’ll highlight some more of the gaps in the existing contracts draft, or provide a basis for discussing possible enhancements.

Blank Types

Note: there has been a generics-like proposal in the past called “Blank Types.” This section is a hypothetical expansion of the Contracts Draft.

In the contracts draft is the following example:

s := []int{1, 2, 3}
floats := slices.Map(s, func(i int) float64 { return float64(i) })

The blank identifier could be used for types similarly to how it’s used for variables: anywhere that a type can be inferred, _ could be used as a stand-in type. In this case, the above example could look like:

s := []int{1, 2, 3}
floats := slices.Map(s, func(i _) _ { return float64(i) })

That could be interpreted as an equivalent to:

s := []int{1, 2, 3}
floats := slices.Map(s, func(type T, U)(i T) U {
    return float64(i)
})

A similar syntax could be:

func floats = slices.Map(_, int)

This has the benefit of using blank types to define partially concrete package-scoped functions, but without needing to resort to a wrapping function, and without using a global variable. This syntax is reminiscent of the rejected “function aliases” portion of the “type aliases” proposal that, after revisions, had been included in Go.

This also enables the not-very-convincing:

func Map(T, U type mycontract, fn func(T) U, lst []T) []U {
    // ...
}
// func(func(int) float64, []int) []float64
func IntsToFloat64s = Map(int, float64, _, _)
var TheList = []int{1, 2, 3}
// func(U type mycontract(int, U), func(int) U) []U
func TheListToXs = Map(int, _, _, TheList)

Partial Application

Following the implications of blank types, we can also extend this concept to provide partial application of normal functions:

joinComma := strings.Join(_, ",")

This function would be semantically equivalent to the following:

joinComma := func(s []string) string { return strings.Join(s, ",") }

For efficiency and sanity, a variadic parameter itself cannot be partially applied. If any value is applied, then the entire underlying slice is applied and can accept no additional parameters. If exactly one blank identifier stands in for the entire variadic parameter list, the entire variadic is unapplied (and can be filled in later with subsequent parameter application). If no value or blank identifier is supplied for the variadic, the parameter is considered applied with a nil slice. Any other combination of variadic values is rejected by the compiler.

Tuple conversion

Often there will be an annoying limitation of generic type inference: returned parameters cannot be inferred unless they have the same parameter name as an input type. Consider the following toy example, which both swaps inputs and converts the values to destination types at the same time:

contract convert(t T, _ U) { U(t) }
contract convertSwap(A, B, Y, X) {
    convert(A, X)
    convert(B, Y)
}
func ConvertSwap(type A, B, Y, X convertSwap)(a A, b B) (Y, X) {
    return Y(b), X(a)
}

Normally this would need to be called with explicit parameters:

a, b := 5, "pqr"
c, d := ConvertSwap(int, string, []byte, float32)(a, b)
fmt.Printf("var c %T = %[1]v\n", c) // var c []byte = [112 113 114]
fmt.Printf("var d %T = %[1]v\n", d) // var d float32 = 5

By introducing tuple conversion, we could provide the explicit means for inferring the types of return values in addition to the input parameters:

a, b := 5, "pqr"
c, d := ([]byte, float32)(ConvertSwap(a, b))
fmt.Printf("var c %T = %[1]v\n", c) // var c []byte = [112 113 114]
fmt.Printf("var d %T = %[1]v\n", d) // var d float32 = 5

Tuple conversion would be conceptually related to multiple-assignment, and have syntax similar to those cases when wrapping parentheses are needed to disambiguate a conversion, such as when converting to an unnamed pointer type.

Conversion Functions

Using the same example from the contract draft, we could also make it more concise by stating that all types are also generic functions with an implicit contract defined by Go’s existing conversion rules. Thus, float64 is both a type, and a generic function with the signature:

func(t T convertibleToFloat64)(T) float64

Thus, the original Map example could become:

s := []int{1, 2, 3}
floats := slices.Map(s, float64)

Other types, such as []byte would also be functions without a name. All of this does create several problems, however:

fn := float64(int) // fn is a func(int) float64
int := 0
v := float64(int)  // v is 0.0 of type float64

And ambiguities arise:

func MapToInt(type T)(fn func(T) int) func([]T) []int {
    return func(in []T) []int {
        out := make([]int, len(in))
        for i := range in {
            out[i] = fn(in[i])
        }
        return out
    }
}
func main() {
    // func(func(float64) int) func([]float64) []int
    float64sToIntsBuilder := MapToInt(float64)
    // func([]float64) []int
    float64sToInts := float64sToIntsBuilder(int)
    // same, but float64 is as a type and int is a func
    float64sToInts = MapToInt(float64)(int)
    // is int treated as a type, or is it treated as a _value_
    // via generics inference?
    unclear := MapToInt(int)
    // ...
}

Derived types

Note: looking at other responses, this looks very similar to Steven Blenkinsop’s Auxiliary Types proposal. I haven’t read his work sufficiently yet to know if this just an unrefined rephrasing of his work, or if it merely shares motivations and some syntactic choices/trade-offs.

In a contract, as shown earlier, we can describe a lot about an element type from a type parameter that describes properties of a container, but does not restrict the kind of container. However, there are some aspects of the element type that cannot be described without an explicit, somewhat redundant type parameter.

contract convertCopy(x X, y Y, _ XVal) {
    for k, v := range y {
        x[k] = XVal(v)
    }
}
func Copy(type X, Y, XVal)(dst X, src Y) {
    for k, v := range src {
        dst[k] = XVal(v)
    }
}
func main() {
    dst := make(map[int]uint64)
    Copy(map[int]uint64, string, uint64)(dst, "abc")
    fmt.Println(dst) // map[0:97 2:99 1:98]
}

There were two unnecessary details here. First, the contract had no way of relating an unknown container kind to its element type: we had to be explicit about this. Second, since the XVal type parameter is not used in the function signature, we cannot use inference to avoid the explicit instantiation.

This could be made easier by providing a way to infer the type of an expression:

contract convertCopy(x X, y Y) (XKey, XVal) {
    var xk XKey
    var xv XVal
    // inference of XKey and XVal happens here
    for xk, xv = range x {}
    for yk, yv := range y {
        x[XKey(yk)] = XVal(yv)
    }
}
func Copy(type X, Y convertCopy)(dst X, src Y) {
    type XKey, XVal = convertCopy(X, Y) // syntax TBD
    for k, v := range src {
        dst[XKey(k)] = XVal(v)
    }
}
func main() {
    dst := make(map[int]uint64)
    Copy(dst, "abc")
    fmt.Println(dst) // map[2:99 0:97 1:98]
}

The first thing to note is that a contract can return evaluated types (essentially a contract would just be a function that accepts types and returns other types). The returned types must be derived from the inputs, and each returned type may only be unified to a single type in a single invocation of the contract, thus contracts are pure functions.

Second, Copy is able to retrieve the evaluated types from the instantiated contract. Since these types can also be used for conversions (the contract required that they be usable in that way), we can use them in the Copy implementation to convert both key and value, which is more flexible than what we achieved in the original example. Finally, since XKey and XVal were derived, they don’t need to be specified in the function’s list of type parameters, and we’re able to use the shorthand inference-based call to Copy now.

Some of these needs could also be solved by allowing type X = type(expr) inside a contract. type, when used as a conversion function, would evaluate to the type of the provided expression.