Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: spec: generics: type parameters on aliases #46477

Open
mdempsky opened this issue Jun 1, 2021 · 18 comments
Open

proposal: spec: generics: type parameters on aliases #46477

mdempsky opened this issue Jun 1, 2021 · 18 comments

Comments

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Jun 1, 2021

The generics proposal says "A type alias may refer to a generic type, but the type alias may not have its own parameters. This restriction exists because it is unclear how to handle a type alias with type parameters that have constraints."

I propose this should be relaxed and type aliases allowed to have their own type parameters. I think there's a clear way to handle type aliases with constrained type parameters: uses of the type alias need to satisfy the constraints, and within the underlying type expression those parameters can be used to instantiate other generic types that they satisfy.

I think it's fine to continue allowing type VectorAlias = Vector as in the proposal, but this should be considered short-hand for type VectorAlias[T any] = Vector[T]. More generally, for generic type B with type parameters [T1 C1, T2 C2, ..., Tn Cn], then type A = B would be the same as type A[T1 C1, T2 C2, ..., Tn Cn] = B[T1, T2, ..., Tn].

In particular, something like this would be an error:

type A[T comparable] int
type B[U any] = A[U]   // ERROR: U does not satisfy comparable
type C B[int]

As justification for this, analogous code in the value domain would give an error:

func F(x int) {}
func G(y interface{}) { F(y) }  // ERROR: cannot use y (type interface{}) as int
func H() { G(42) }

I suspect if TParams is moved from Named to TypeName and type instantiation is similarly changed to start from the TypeName instead of the Type, then this should work okay.

/cc @griesemer @ianlancetaylor @findleyr @bcmills

@mdempsky mdempsky added this to the Go1.18 milestone Jun 1, 2021
@findleyr
Copy link
Contributor

@findleyr findleyr commented Jun 1, 2021

If this proposal were accepted, would the following code be valid?

type A[T any] int
type B[U comparable] = A[U]

I.e. would it be possible to define an alias which tightens the constraints of the aliased type?

IMO the example in the value domain is more analogous to defining a new named type, which already behaves as expected:

type A[T comparable] int
type B[U any] A[U] // ERROR: U does not satisfy comparable

Aliasing seems more analogous to function value assignment, for which we don't redeclare parameters:

func F(x int) {}
var G = F

I think you're right about how this could be implemented, but I wonder if it is conceptually coherent. Specifically, I wonder about whether we should think of the declaration as parameterizing the type, or as defining a parameterized type, and whether it still makes sense to call the example with additional restrictions above an alias.

I'll also note that as you point out, our decisions with respect to the go/types API have real consequences for how easy it would be to relax this restriction on aliases in the future, so it is good to talk about this now. Thanks for raising this issue!

@mdempsky
Copy link
Member Author

@mdempsky mdempsky commented Jun 1, 2021

I.e. would it be possible to define an alias which tightens the constraints of the aliased type?

Yes. U (type parameter with bound comparable) satisfies the constraint any, so that's a valid type declaration in my mind. But similarly, trying to instantiate B[[]int] would be invalid, because []int does not satisfy comparable, even though it satisfies the underlying any.

I would expect that the type checker would see B[[]int], resolve B to the TypeName and check it against the type parameters, and then reject it as invalid, before proceeding to instantiating/substituting its Type with the type argument []int.

Aliasing seems more analogous to function value assignment, for which we don't redeclare parameters:

Note that var G = F is really shorthand there for var G func(int) = F. You're not allowed to write var G func(interface{}) = F, for example, even if you only ever call G with int arguments.

But this is also why I suggest still allowing type A = B as shorthand for explicitly writing out type parameters for the alias declaration.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jun 1, 2021

There is a reason why we didn't do this in the first place.

I don't have any principal objections to this proposal. If we accept this, I wonder whether we should still permit the type A = B form as it does deviate from the current design which requires that every use of a generic type requires an instantiation.

I'm inclined to proceed in one of two ways:
1) Disallow (not implement) the form type A = B for Go1.17. It's not crucial and we can always add it later.
2) Implement this proposal instead of permitting type A = B.

@bcmills
Copy link
Member

@bcmills bcmills commented Jun 1, 2021

I seem to recall @rogpeppe raising a similar point in various conversations.

@bcmills
Copy link
Member

@bcmills bcmills commented Jun 1, 2021

@findleyr

Aliasing seems more analogous to function value assignment, for which we don't redeclare parameters:

Note that we do allow function value assignment to strengthen (but not weaken) a type via assignability, which IMO is analogous to strengthening type constraints on a type declaration.

Consider this program:

package main

import "context"

func cancel() {}

type thunk func()

var f = cancel
var g context.CancelFunc = cancel

In that program, var f = cancel is shorthand for var f func() = cancel.

The declaration var g context.CancelFunc = cancel refers to the exact same function value, but with a stronger type (one that is not assignable to thunk).

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Jun 1, 2021

It looks like it could fall out of the definition but, to be explicit, partial application would also be useful:

type Named[T any] = Map[string, T]
@mdempsky
Copy link
Member Author

@mdempsky mdempsky commented Jun 1, 2021

@griesemer If we proceed with this proposal, I think it could be a nice convenience to keep type A = B as short-hand. But as it's not essential, I'd similarly be fine with just removing it altogether. We can always re-add it in the future if appropriate.

And yes, the deviating from the norm of requiring instantiation is what threw me off. I had written some code that was working under the assumption that if I only started from non-generic declarations, then I would never see a non-instantiated type. But that doesn't hold for the type A = B form. (Fortunately though, it's not hard to special case this one instance either.)

@findleyr
Copy link
Contributor

@findleyr findleyr commented Jun 1, 2021

@bcmills

Note that we do allow function value assignment to strengthen (but not weaken) a type via assignability, which IMO is analogous to strengthening type constraints on a type declaration.

The example from #46477 (comment) made the analogy of function parameters with type parameters (which makes sense). In that analogy, we don't allow changing function parameter types when assigning [example], i.e. we don't support covariant function assignment.

@bcmills
Copy link
Member

@bcmills bcmills commented Jun 1, 2021

In that analogy … we don't support covariant function assignment.

Sure, but pretty much the entire point of type parameters is to support variance in types. 😉

@neild
Copy link
Contributor

@neild neild commented Jun 2, 2021

What is the use case for permitting parameters on type aliases?

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jun 2, 2021

@neild The same reason for which type aliases were introduced in the first place, which is to make refactoring across package boundaries easier (or possible, depending on use case).

I misread this comment. See below.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jun 2, 2021

Going through my notes I remember now why we didn't go this route in the first place: Note that an alias is just an alternative name for a type, it's not a new type. Introducing a smaller set of type arguments (as suggested above), or providing stronger type constraints seems counter that idea. Such changes arguably define a new type and then one should do that: declare a new defined type, i.e., leave the = away. I note that @findleyr pointed out just that in the 2nd comment on this proposal.
This would mean that the respective methods also have to be redefined (likely as forwarders) but that seems sensible if the type constraints are narrowed or partially instantiated.

In summary, I am not convinced anymore that this is such a good idea. We have explored the generics design space for the greater part of two years and the devil really is in the details. At this point we should not introduce new mechanisms until we have collected some concrete experience.

I suggest we put this on hold for the time being.

@neild
Copy link
Contributor

@neild neild commented Jun 2, 2021

@griesemer I don't see what the refactoring case is for changing the constraints of a type. As you say, an alias is just an alternative name for a type, but an alternative name with altered constraints is a subtler concept that I struggle to see the use for.

I may be missing something. A concrete example of when you'd use this would be useful.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Jun 2, 2021

@neild Agreed - I misread your comment as "what is the use of allowing alias types for generic types" - my bad. See my comment just before your reply.

@mdempsky
Copy link
Member Author

@mdempsky mdempsky commented Jun 2, 2021

I don't see what the refactoring case is for changing the constraints of a type.

Under this proposal, you can do more with parameterized type aliases than just change the constraints. E.g., see #46477 (comment) for using type parameters to provide default arguments to other generic types. I called out the constraint change to clarify the semantics, not because I expect that's something people are likely to do in practice.

I anticipate analogous to how we added type aliases to facilitate large-scale refactorings while maintaining type identity, we're going to face situations where generic types need to be refactored to add, remove, or change parameters while also maintaining type identity. Having parameterized type aliases would facilitate that. I think if just "declaring a new defined type" was always an adequate solution, we could have skipped adding type aliases too.

I think it's fine though if Go 1.18 doesn't have parameterized type aliases. But I at least think we should try to ensure the go/types APIs are forward compatible with adding parameterized type aliases.

@findleyr
Copy link
Contributor

@findleyr findleyr commented Jun 2, 2021

@bcmills

Sure, but pretty much the entire point of type parameters is to support variance in types. 😉

FWIW, I don't follow this argument. We still support variance in types no matter what we decide about this proposal, just like we allow variance in function arguments whether or not we allow covariant assignment of function values. I think we're dipping in and out of the 'meta' realm. The point I was trying to make is that if we're trying to argue by analogy with the value domain, wrapping a function is more like defining a new named type (or perhaps more correctly like struct embedding), and aliasing is more like assignment. Since we don't allow covariant assignment for functions, it's arguably a bit inconsistent to allow covariant assignment for "meta functions" (if that's how we think about generic declarations).

@griesemer

This would mean that the respective methods also have to be redefined (likely as forwarders) but that seems sensible if the type constraints are narrowed or partially instantiated.

Or use embedding, which might be more analogous to wrapping a function in the value domain.

I suggest we put this on hold for the time being.

Independent of whether we relax the restriction on aliases, this proposal indirectly makes the point that it matters whether we think of the "type" as generic or the "declaration" as generic, both in the current APIs and for future extensions of the language. For example, thinking of the type declaration as generic allows relaxing this restriction on aliases. Thinking of the function type as generic allows for generic interface methods and generic function literals. If we put this proposal on hold, we will still need to make API decisions that affect its feasibility.

@mdempsky
Copy link
Member Author

@mdempsky mdempsky commented Jun 2, 2021

[re: value vs type domain analogies]

I want to clarify that I made this analogy initially to help explain how I intuit the relationships here. Go's values and types operate sufficiently distinctly and irregularly that I think trying to read too far into the analogy is going to hit rough edges and become more philosophical than actionable. E.g., the value domain has no analog to defined types and type identity, because it's impossible to create a copy of a Go value that's distinguishable from the original. (Emphasis: I'm talking specifically about values here, not variables.)

Certainly we should revisit these discussions when it comes time to add dependent types to Go 3 though. :)

@rogpeppe
Copy link
Contributor

@rogpeppe rogpeppe commented Jun 11, 2021

Note that an alias is just an alternative name for a type, it's not a new type.

I'm not sure that this is entirely true. What about this, which is currently allowed?

type S1[V any] struct { .... }

type S2 = S1[int]

S2 neither an alternative name for an existing type nor an entirely new type. More of a composite type, perhaps. Also, it does have some identity of its own (its name is used when it's embedded)

Introducing a smaller set of type arguments (as suggested above), or providing stronger type constraints seems counter that idea. Such changes arguably define a new type and then one should do that: declare a new defined type, i.e., leave the = away

Sometimes defining a new type isn't possible. For example, if a type is specifically mentioned in a type signature, it's not possible to use a new type - you have to use the same type as the original. Also, the fact that all methods are lost when you define a new type is a real problem and embedding doesn't always work either.

For non-generic code, it might usually be possible to define a fully-qualified type alias like S2 above, but in generic code that's often not possible because a type parameter might be free.

An example:

Say some package defines an OrderedMap container that allows an arbitrary comparison operation for keys:

package orderedmap

type Map[K any, V any, Cmp Comparer[K]] struct {
    ...
}

func (m *Map[K, V, Cmp]) Clone() *Map[K, V, Cmp]

func (m *Map[K, V, Cmp]) Get(k K) (V, bool)

type Comparer[K any] interface {
    Cmp(k1, k2 K) int
}

I want to implement a higher level container in terms of orderedmap.Map. In my implementation, only the value type is generic:

package foo

type Container[V any] struct {
}

func NewContainer[V any]() *Container[V] {
    ...
   var m *orderedmap.Map[internalKey, V, keyComparer]
}

type internalKey struct {
    ...
}

type keyComparer struct{}

func (keyComparer) Cmp(k1, k2 internalKey) int {
    ...
}

In the above code, whenever I wish to pass around the orderedmap.Map[internalKey, V, keyComparer] type, I have to do so explicitly in full. This could end up very tedious (and annoying to change when refactoring the code). It would be nice to be able to do:

type internalMap[V any] = orderedmap.Map[internalKey, V, keyComparer]

Then we can avoid duplicating the type parameters everywhere.

Defining a new type wouldn't be great here - you'd either have to explicitly forward all the methods (if you did type internalMap[V any] orderedmap.Map[...]) or reimplement some of the methods (if you did type internalMap[V any] struct {orderedmap.Map[...]}).

In short, I'm fairly sure that generic type aliases are going to be a much requested feature when people start using generics in seriousness, and that they're definitely worth considering now even if they're not implemented, so that the type checker isn't implemented in a way that makes it hard to add them later.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
8 participants