proposal: type parameter lists - extended syntax for relationships/defaults amongst type parameters

[AndrewHarrisSPU]

Proposal

Introduce a type judgement syntax used in type parameters lists. The goal is providing an affordance for some cases where correctly expressing intent requires some awkward elaborations. In contrast, judgement can afford a more direct declaration of relationships between types, given inside of a type parameter list, and in a way that comports with how unification is currently implemented.

The type judgement syntax for a type parameter X.(T) would be, to a degree, congruent with existing syntax for type assertions x.(T) or type switches x.(type).

Example 1: A relationship between an element type T, and a slice-of-element type ST

	[ST.([]T constraints.Number)]

Example 2: A relationship between an element type T, and a pointer-to-element type PT

	[PT.(*T constraints.Number)]

Example 3: A default for a type parameter T

	[T.(float64) constraints.Number]

Example 4: Flexibility to unify T as a particular implementer of an interface, or as the interface itself:

	[T.(io.Reader)]

1. Conceptual continuity between type assertions, type switches, and type judgements

A passage from the Go language specification on type assertions is worth examining:

In other words, even though the dynamic type of x is known only at run time, the type of x.(T) is known to be T in a correct program.

The particular phrasing "known to be T in a correct program" is especially useful. Type assertions and type switches come in the following forms, with associated notions of program correctness:

• type assertion (single type, compile time): Given n := x.(*foo), the program is correct if there is evidence in scope that x is of type *foo.
• type assertion (single type, run time): Given n, ok := x.(*foo), the program is correct if, at run time, usage of n is limited by conditionally branching on ok.
• type switch (multiple types, run time): Given switch i := x.(type), the program is correct if a case *foo branch of the switch is taken.
• type switch (default, run time): Given switch i := x.(type), the program is correct if a default branch of the switch is taken.

Before generics, a similar construct for multiple types at compile time would be non-sensical. With generics, it isn't. Following the pattern:

• type judgement (mutliple types, compile time): Given X.(T), the program is correct for any X and T such that unification succeeds.
• type judgement (default, compile time): Given T.(foo), the program is correct when T is foo. (Correctness is not limted to this case, but does include it).

Abstractly, where type assertions and switches assume the existence of a compiler or a runtime environment, the type judgement syntax assumes the existence of a unification solver. The phrasing "known to be T in a correct program" meshes well with the notion of declaring a predicate, and leaning on a solver to compute further. While a more centrally declarative langauge or system can get a bit involved in the details, here we might say the 'predicates' and 'solver' are known to be type sets and unification. Then, because type judgement can be handled when transforming from type parameter lists to type sets, we can leave predicate/solver machinery as is.

2. Arguments on current and proposed syntax

The overall scheme of generics in Go involves a chain of reasoning from method or constraint interfaces, to type parameter lists, to type sets, to unification. This proposal embeds an opinion that some affordances could be useful along the way. It addresses some situations the Type Paramter Proposal describes as 'awkward'. Fundamentally, the 'awkward' cases arise when an element type parameter or default type, as well as a related type parameter, must both occur in a type parameter list. (Further, if it's fair to say Go thinks about memory more like C, and less like Lisp, some awkwardness is bound to show up somewhere; relevant aspects of memory layouts are codified in the type system.)

Examples 1 and 2 (slice-of-element and pointer-to-element):

The examples ([ST.([]T constraints.Number)], [PT.(*T constraints.Number)]) mirror examples in the Type Paramter Proposal:

• Element constraint example
• Pointer method example

In these cases, the current solutions involve defining new constraints (SC or Setter2) parameterizing on or embedding interfaces (constraints.Number or Setter) on a slice or pointer type. In other words, expressing the intended relationships occurs in disjoint places. Generally in similar situations, there are two options:

1. abandoning the methods-only interface by adding constraint terms
2. maintaining two (or more) similar interfaces

Argument:

• Option 1 precludes use of the interface in some cases, e.g. as a function argument type.
• Option 1 isn't possible when the interface can't be modified.
• Option 2 clutters code. A significant subset of constraining interfaces seem likely to be one-off, developed only for a particular and narrow use. But when examining a constraining interface like Setter2 in isolation, it may not be immediately clear where the constraint will be used.
• In contrast, the proposed syntax conserves element-type and method-only interfaces. It also lives inside the type parameter lists where it applies.
• To be clear, I agree where the current proposal suggests calling generic code is minimally awkward. The proposed benefit here would only be an affordance for reading, writing, and maintaining the called code.

Example 3 (defaults for type parameters):

Some equivalent suggestions for type parameter defaults are given in a discussion how to update APIs for generics:

1. [T any (= someDefaultType)]
2. type Pool[T any] ...; type Pool = Pool[interface{}]
3. default Pool Pool[interface{}]

Argument:

• T.(someDefaultType) would integrate default type parameters with other language components conceptually and syntactically.
• Under some options, defaults may become distant from type parameter lists where they are significant; less so under the proposal.

Example 4 (interfaces as default types):

I haven't worked out an equivalent solution for example 4 [T.(io.Reader) with current syntax. Two similar things are straightforward (and often reasonable):

1. A type parameter that unifies to a specific implementer of an interface (faster, monomorphized execution)
2. Elide generics and stick with interfaces (more flexible; necessary to collect multiple implementers in one data structure)

Argument:

• The proposal allows one passage of code to encompass both possibilities. This helps avoid APIs becoming colored as either 'generics' or 'interfaces as we've known them'.
• The difference between an interface as a type and as a type parameter can feel subtle in practice. This syntax can be less subtle.

Related issues/proposals

Beyond these examples, some of the underlying issues appear in some other issues and proposals. It's hard to say where the ball is going to bounce next sometimes, but this proposal could help resolve or clarify things.

• spec: typeparams: clarify whether method calls are allowed to implicitly dereference pointer-to-TypeParams
• generics: Confusion between interfaces and constraints
• proposal: spec: generics: type switch on parametric types

3. EBNF and additional nuances

A loose depiction of EBNF for current and proposed syntax follows. More things could make sense here, but this just sketches the examples in order to suggest soundness. Hopefully, in not too crude a fashion...

Type Parameters Proposal(e.g. [T any]):

	TypeParam = "TypeName" "Constraint" .

how to update APIs for generics(e.g. [T constraints.Number (= float64)]):

	TypeParam = "TypeName" "Constraint" [ "(=" "Type" ")" ] .

Proposed here:

	Judgement = ( "[]" "TypeName" "Constraint" ) | ( "*" "TypeName" "Constraint" ) | ( "Type" [ "Constraint" ] ) | "Interface" .
	TypeParam = ( "TypeName" "Constraint" ) | ( "TypeName" ".(" "Judgement" ")" [ "Constraint" ] ) .

Some nuances less naturally expressed in EBNF:

1. Where type assertions and switches fully imply the underlying type T satisfies an interface, type judgment similarly requires some constraint that T must satisfy.

   • [X.(*Y)], [X.([]Y)], [X.(float64)]: Invalid: no constraints.
   • [X.(io.Reader): Valid: io.Reader is valid both as a type (an interface at run time) and a constraint
   • [T any, ST.([]T)], [PT.(*T), T any]: Valid: a constraint for T is found elsewhere in the type parameter list

2. The most permissive scheme could allow a bit of looseness on where constraints appear:

   • [ST.([]T) constraints.Number]
   • [ST.([]T constraints.Number)]
   • [PT.(*T) io.Writer)]
   • [PT.(*T io.Writer)]
   • [T.(float64 constraints.Number)]
   • [T.(float64) constraints.Number]
   • [R.(io.Reader)]
     In the same order, matching pattern -> rules for constructing a TypeParam:

	"TypeName" ".(" "[]" "TypeName" ")" "Constraint" ->
		propagate constraint to the inner "TypeName"; don't propagate constraint to the outer "TypeName"

	"TypeName" ".(" "[]" "TypeName" "Constraint" ")" ->
		don't propagate constraint to outer "TypeName"

	"TypeName" ".(" "*" "TypeName" ")" "Constraint" ->
		propagate constraint to the inner "TypeName"

	"TypeName" ".(" "*" "TypeName" "Constraint" ")" ->
		propagate constraint to the outer "TypeName"

	"TypeName" ".(" "Type" "Constraint" ")" ->
		fail unless "Type" satisfies the constraint; propagate the constraint to "TypeName"; "Type" becomes a default "Type" for "TypeName"

	"TypeName" ".(" "Type" ")" "Constraint" ->
		fail unless "Type" satisfies the constraint; propagate the constraint to "TypeName"; "Type" becomes a default "Type" for "TypeName"

	"TypeName" ".(" "Interface" ")" ->
		"Interface" becomes a default "Type" for and constraint on "TypeName"

4. Viability of implementation

Implementing the core functionality could just entail:

• additional parsing to recognize type judgment and its cases
• logic for constructing a type parameter resulting from a type judgement

The result of parsing a type parameter list should still be the synthesis of TypeName/Constraint pairs, not different from current implementation (with the exception of defaults for type parameters).

Some foreseeable problems can be ruled out by disallowing productions that are challenging to parse, without unduly diminishing expressive power:

1. Disallow nested judgements:

   • [X.(*Y.([]Z constraint))]: invalid
   • [X.(*Y), Y.([]Z constraint)]: valid

2. Disallow repeated or superfluous TypeNames in a judgement

   • T.(*T): invalid
   • [T.(T float64) constraints.Number]: invalid
   • T2.(T1 float64) constraints.Number]: possible to parse but invalid.
   • PT.(*T any), V any, map[T,V]: valid

Conclusion

In summary, the thesis of this proposal:

1. Some affordances could be useful inside of type parameter lists for some cases
2. There is a natural way to extend type assertion / type switch syntax inside of type parameter lists for those cases
3. It'd be feasible to implement the syntax

Subjective aspects to these points:

1. It's syntax sugar. It doesn't feel to me like too much - maybe similar to how Go affords a.Foo() (not *a.Foo(), or a->Foo(), etc.) for value, pointer, or interface types of a. But, it is a question of taste.
2. The type assertion / switch / judgement feels tangible and intuitively robust, to me ... it feels fun, even.
3. There are a lot of ideas to further smooth and polish generics in Go, this is just one. The big picture requires balancing a lot of things well and not implementing every idea.

Thanks for looking! I have tried to address points mentioned in Go 2 language change template. (note: I think this proposal is constrained to things that aren't baked into the language or still emerging, so I wasn't sure if that was the best template to follow.)

[ianlancetaylor]

CC @griesemer

[ianlancetaylor]

Just a note that one of the nice features of the current syntax is that type parameters lists use the same syntax as ordinary parameter lists (except that they use square brackets and do not permit just listing types).

[rsc]

If this were a clear improvement over the current syntax, then we would certainly consider it.
But it doesn't seem to be, and we are focused on getting generics working and shipped.
And we are not going to redesign this after shipping generics.
It's possible that this is wonderfully better and we just don't understand that,
but what we have seems like it is working very well, so we should probably stick with that.

[rsc]

Declining as infeasible.

[rsc]

This proposal has been declined as infeasible.
— rsc for the proposal review group