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: type parameters are comparable unless they exclude comparable types #52614

Closed
griesemer opened this issue Apr 29, 2022 · 102 comments
Closed
Labels
generics Issue is related to generics Proposal
Milestone

Comments

@griesemer
Copy link
Contributor

griesemer commented Apr 29, 2022

Introduction

The predeclared type constraint comparable, introduced with Go 1.18, is a (magic) interface describing the set of types for which == is expected to work without panic. The introduction of comparable led to considerable discussion (see background in #52474 for details). It also led to confusion because the set of types described by comparable does not match the types that are considered comparable per the Go spec.

Here's the current list of issues related to this discussion:

The goal of these proposals is to address the perceived shortcomings of comparable by changing its definition or by separating the notion of interfaces and type sets.

So far none of these proposals (if still open) have gained significant traction, and none of them directly address the core of the comparable problem: in Go ordinary interfaces are always comparable, i.e., they support == and != independently of whether the dynamic type of the interface is comparable. We cannot change this without breaking backward-compatibility.

Instead we propose to embrace this property of interfaces.

Proposal

The underlying type of a type parameter is its type constraint interface; i.e., a type parameter is an interface (albeit with a "fixed" dynamic type which is given when the type parameter is instantiated). Because type parameters are interfaces, we propose:

Type parameters are comparable unless the type parameter's type set contains only non-comparable types.

This is the entire proposal.

Discussion

The reason for having comparable in the first place is to be able to statically express that == is expected to work and that it won't panic. If this proposal is accepted, == will be supported on type parameters unless the type set contains only non-comparable types. We will also lose the guarantee that == won't panic (if == is supported in the first place). We may still keep comparable, but more on that below.

This proposal hinges on the premise that losing the static "no-panic" guarantee is not as severe a loss as it might appear at first. We believe this could be true for the following reasons:

  • We are well-accustomed to the fact that == on ordinary interface types might panic. In code, we tend to address the comparability requirement through documentation; we suggest that we continue to use documentation for this.

  • If a type parameter is instantiated with a non-comparable type and == is expected to work, upon invocation the generic code is likely to panic right away. This contrasts favorably to the situation with ordinary interfaces where a panic may occur for some of the dynamic values but not all of them. In other words, making a comparability mistake in generic code would be detected quickly, probably in the first test run.

  • Better yet, we don't have to rely entirely on dynamic type safety: it should be straight-forward to introduce a vet check that reports when a type parameter for which we expect == to work is instantiated with a type that is not comparable. Such a check would provide the equivalent of a static compile-time check, and virtually eliminate the risk of ==-related panics.

With this proposal unfortunate restrictions caused by the use of comparable can be avoided. The == operator will simply be available to all type parameters unless their type sets contain only non-comparable types (it makes sense to exclude such type sets because we know with certainty that == will always panic for such type parameters). Examples:

interface                          comparable    may panic

any                                yes           yes
interface{ m() }                   yes           yes
interface{ ~int }                  yes           no
interface{ ~struct{ f any } }      yes           yes
interface{ ~[]byte }               no            n/a
interface{ ~string | ~[]byte }     yes           yes

This proposal also opens the door to more flexible (if perhaps esoteric) generic code that relies on == to work for some type instantiations but not for others, something that can be readily expressed through control flow but which is much harder (or impossible) to encode through types.

We still have the option to keep comparable as the "umbrella" set of types which are comparable without panic. Or we could decide to remove it because using it may preclude some uses of generic code (e.g., see #51338 (comment)). Keeping it will also require a programmer to always make the decision whether or not to use it. To remove it we could make use of the provision in the Go 1 compatibility guarantee:

If it becomes necessary to address an inconsistency or incompleteness in the specification, resolving the issue could affect the meaning or legality of existing programs. We reserve the right to address such issues, including updating the implementations.

Eliminating comparable would simplify the language and probably eliminate some confusion. The decision whether to keep or remove it is independent of this proposal.

History and credits

We briefly toyed with a simpler form of this idea (type parameters should always be comparable) as a potential solution to the comparable problem shortly before the 1.18 release. At that time we dismissed making all type parameters comparable (and eliminating the predeclared type comparable) as too radical. The resulting loss of static type safety around == in generic code seemed unacceptable.

We are aware of at least one other person, Conrad Irwin, who independently suggested that all type parameters should be comparable in #52509 (comment).

@hherman1
Copy link

hherman1 commented Apr 29, 2022

Sorry I must be misunderstanding something, but if you were to instantiate a generic function with a concrete non comparable type (e.g a slice) wouldn’t you consider the type parameter to not be an interface? The point that type parameters are interfaces is confusing to me.

Also couldn’t this cause weird action at a distance? A deeply nested generic function requires comparable type parameters and you don’t realize it?

I realize I’m not fully read up on this issue and there’s a lot of history here, but the proposed behavior feels weird and surprising as a dumb user, which is concerning me.

@griesemer
Copy link
Contributor Author

griesemer commented Apr 29, 2022

@hherman1 The view of a type parameter as an interface mostly affects type checking: for instance, in a generic function, the type of a type parameter is unknown when that function is type-checked (consider a generic exported library function were one knows nothing about clients - still we want to fully type-check that function). For type-checking we therefore treat the type parameter (more precisely, a variable of type parameter type) as an interface in the sense that we have to consider all possible types in its type set (we know a bit more than that, for instance we know that the type of such a variable, even if unknown, doesn't change for the duration of that generic function, which is why these are somewhat special interface types). It's also this type set we care about when that type parameter is used to instantiate yet another generic function.

We already have "weird action at a distance" with non-generic Go: a function operating on ordinary (non-type parameter) interfaces may hold a dynamic type that doesn't support comparison yet that function may try to compare the interface (all ordinary interfaces support ==). A point this proposal is trying to make is that this might not be as bad as it might seem: we're used to it and we could have a vet check fairly easily. The other point this proposal is making is that the apparent inconsistencies with respect to type sets (and comparable) disappear if we use the proposed approach.

@atdiar
Copy link

atdiar commented Apr 29, 2022

I think it could work. It still feels like we are admitting defeat on having full static checking.

If we can use the provision, why not just make type parameters able to take a list of constraints?
Something like

type Set[T (any, comparable), V any]map[T]V

?
With comparable just filtering the set of types that implement any?

@go101
Copy link

go101 commented Apr 29, 2022

Does this proposal mean the following code will become valid?

func foo[T any](x T) {
	_ = x == x
}

... Eliminating comparable would simplify the language and probably eliminate some confusion ...

Is there still a plan to use comparable as value type?

@magical
Copy link
Contributor

magical commented Apr 29, 2022

Just to be clear, this program

func eq[T any](a, b T) bool { return a == b }

func main() {
     var s []int
     eq[[]int](s, s)
}

would be defined to always panic at runtime, right? Not a compile error even though it's statically obvious that it can't succeed? If the compiler decides to stencil eq[[]int] it would have to compile it down to, essentially,

func(a, b []int) bool { panic("[]int cannot be compared") }

since there is no way to implement the comparison.


How does this interact with comparisons to nil (or other constants)? I assume

func isnil[T any](a T) bool { return a == nil }

would still be invalid, since nil is not convertible to every type in T.

@griesemer
Copy link
Contributor Author

griesemer commented Apr 29, 2022

@atdiar I don't understand what you're asking about with the "list of constraints" (any, comparable). It doesn't seem directly relevant to this proposal.

@go101 Yes, the foo function

func foo[T any](x T) {
	_ = x == x
}

would become valid since the type set of any includes all non-interface types, comparable and incomparable ones. Whether comparable would remain, and whether it should become a value type are questions that don't directly depend on this proposal: we could keep comparable as is for the static type safety that we don't have with this proposal, at the cost of less flexibility. If we keep it, we probably want to also allow it as a value type. But again these decisions are not directly tied to this proposal. On the flip side, if we accept this proposal we do have an opportunity to remove comparable which would simplify the language slightly.

@magical Correct, your example calling eq[[]int](s, s) would compile successfully and panic at run-time. Whether the eq function is fully stenciled and == replaced with a panic call or not is an implementation question. isnil would continue to be invalid code as is the case now. Note that in the case of eq, go vet could easily detect that == is used on operands of type T and report an error if T is instantiated with a non-comparable type like []int.

@atdiar
Copy link

atdiar commented Apr 29, 2022

@griesemer
If an interface used as a constraint defines the set of permissible types, what keeps us from selecting the comparable subset? (i.e. The set of types that are comparable according to the spec)

It's relevant to that proposal in the sense that it would avoid the use of a static tool.

If it's really too off-topic I will disengage but I am curious.

@go101
Copy link

go101 commented Apr 29, 2022

I wonder how feasible to remove comparable. Will it be declared as an alias of any to keep compatibility?

@Merovius
Copy link
Contributor

Merovius commented Apr 29, 2022

To me, this throws the baby out with the bathwater. It seems to have ~all of the downsides of #52509 except that it converts some compile time errors into run time panics. I assume the argument is that it is confusing to have compiler errors for some bugs of this class of, but not all - but IMO that is completely fine and not a good argument to not have compiler errors for any bugs of this class.

I still believe both #51338 and #52509 are acceptable solutions. And the more we talk about it, the more I become entrenched into my view that they are the best ones (either of them). They have downside, but it's fine to accept downsides sometimes.

We still have the option to keep comparable as the "umbrella" set of types which are comparable without panic. Or we could decide to remove it because using it may preclude some uses of generic code

IMO, if we do this, we should absolutely remove comparable. It wouldn't allow the author of a generic function to do anything new, it would only prevent the user of a generic function from using it. That just feels like the current situation, but worse.

In other words, one of the flagship use cases for comparable is Set[T comparable]. The discussion is caused by Set[reflect.Type] currently being impossible. With this proposal, the recommendation would thus be to write Set[T any] instead. At that point, this flagship use case for comparable goes away. Similarly for at least most other obvious use-cases. So ISTM that with this proposal, the general guidance on comparable would be "don't use it, it unduly restricts the user of your function/type", in which case it should just go away.

@changkun
Copy link
Member

changkun commented Apr 29, 2022

Type parameters are comparable unless the type parameter's type set contains only non-comparable types.

How does this definition differ from "Types that supports == or !="? Specifically, what's the differentiation between this proposal and #52509?

@ConradIrwin
Copy link
Contributor

ConradIrwin commented Apr 29, 2022

@griesemer thanks for taking the time to write this up more concretely, I still think this would be a very good simplification for the language as a whole (and agree with @Merovius that assuming this proposal is accepted, deprecating comparable would be the obvious next step).

To the point around bathwater... I do agree that it reduces some compiler completeness; but I don't think the programmer error of "passing something not comparable where comparability is needed" is a very common one in my experience (compared to say, just a logic bug). As pointed out in the proposal, it would still be found by cursory testing. So I think the trade-off of "a very confusing keyword" vs "a slightly longer turn around time to identify specific classes of bug in your code" is well worth it overall.

@changkun That proposal still leaves comparable as a required keyword to use the == operator; this proposal would eliminate the need for that to be specified explicitly; which would avoid the problems around "virality" or "coloring" discussed in the other issues (and reduce the number of things for new go programmers to learn about).

@changkun
Copy link
Member

changkun commented Apr 29, 2022

this proposal would eliminate the need for that to be specified explicitly

Thanks for clarifying this. The goal here is radical as we already have comparable in the language. Despite the interpretation of the Go 1 compatibility promise may differ, it remains a significant historical remark if this actually happens.

Take a step back, and I think the suggested wording in CL 401874 that separates the notion of interface and type set may balance this better. As noted in the CL commit message:

Defining "a type parameter is an interface", "may reflect a simplification, but it is also cumbersome for the predeclared identifier comparable because

  1. comparable cannot be easily defined using an interface and implemented
    using compiler magic;
  2. comparable is very confusing to use"

This observation points to the key challenge of the current generics design: Type constraints are limited by the expressiveness of an interface, there are (more than one possible) type sets cannot be defined using an interface. comparable is already a good example to show this limitation, and the known limitation noted in the 1.18 release note also confirms more examples, such as interface { string | fmt.Stringer }. A theoretical proof may be more supportive in favor of this observation.

This should arise the reflect: As previous discussions revealed the need of multiple differently defined comparable definitions (in real world), it might worth to do the separation between interfaces and type sets.

@Merovius
Copy link
Contributor

Merovius commented Apr 29, 2022

The == operator will simply be available to all type parameters unless their type sets contain only non-comparable types (it makes sense to exclude such type sets because we know with certainty that == will always panic for such type parameters).

I don't think it poses a problem, but if we ever make all interfaces into full types, this restriction would fully go away, as you could always instantiate a generic function using its constraint. i.e. the set of types a constraint would allow will always include a comparable type - the constraint itself.

It's not a problem, because it will be a relaxation of a restriction (i.e. it will only allow more programs to compile, not prevent previously compiling programs to stop compiling). It might hint at a bit of strangeness about this rule though.

@ConradIrwin

I do agree that it reduces some compiler completeness; but I don't think the programmer error of "passing something not comparable where comparability is needed" is a very common one in my experience (compared to say, just a logic bug). As pointed out in the proposal, it would still be found by cursory testing. So I think the trade-off of "a very confusing keyword" vs "a slightly longer turn around time to identify specific classes of bug in your code" is well worth it overall.

I don't think #52509 leaves us with "a very confusing keyword" (nit: predeclared identifier) at all. So I disagree that this is a tradeoff we are making. In particular, anything that would still be confusing about comparable would only happen in exactly the same situation where we get runtime panics with this proposal. So if you discount that, because it's not a very common mistake to make, it seems only fair to also discount the confusion this mistake would cause about comparable.

IMO #52509 even makes the better tradeoff - because when that happens, there is at least a very clear indication in the API, that the values are supposed to be comparable. That's not something we even have here. That is, with #52509, if you get a panic by instantiating a generic function using an interface type and then get a panic in the comparison, you can at least look at the signature and say "oh, it says the value needs to be comparable, makes sense", whereas here, you end at "well, the signature says any, so…".

@atdiar
Copy link

atdiar commented Apr 29, 2022

Just leaving that as a note but I agree with @changkun #52614 (comment)

The problem with comparable was that we decided to have only one way to build the set of permissible types for a type parameter: an interface.

That's the reason behind #52531: to be able to introduce a refinement so that we can select the comparable (in its spec sense) subset of a set of types. Although it might be more complex in implementation, I don't know why it was deemed as not addressing the issue.
(the only difference was the name, that was different for backward-compatibility reasons)

Also a little nit, it seems to me that the set of permissible types is not always a type set. For instance, basic interfaces are included in the set of permissible types, not in their own type set.

@Merovius
Copy link
Contributor

Merovius commented Apr 29, 2022

That's the reason behind #52531: to be able to introduce a refinement so that we can select the comparable (in its spec sense) subset of a set of types. Although it might be more complex in implementation, I don't know why it was deemed as not addressing the issue.

I wouldn't say that it doesn't address the issue. I would say that it's either a) the same as #49587 (in its original phrasing) or b) the same as #52509 (with your latest comment, after removing the second comparison constraint). It is phrased more complicatedly, but in terms of what code it allows to write and how that code is written, it does the same.

Both of those proposals do address the issue. Both have other downsides. But that doesn't mean we can't accept them anyways. I wouldn't say there has been a final decision made on any of these proposals.

@atdiar
Copy link

atdiar commented Apr 29, 2022

Well if you leave the part about comparable not being an interface anymore, they might look similar I guess (it would be equivalent to having both).

But yes, on the topic of the current proposal, it feels like we are dropping the ball perhaps too early. Although it could be seen as an engineering tradeoff, I'm not too sure about it. 😕

@Merovius
Copy link
Contributor

Merovius commented Apr 29, 2022

Well if you leave the part about comparable not being an interface anymore

I think the only practical difference this makes, is that it doesn't allow mixing comparable with other constraints. Which is a problem with the design that would need to be addressed. At that point, any practical difference vanishes.

@atdiar
Copy link

atdiar commented Apr 29, 2022

Well if you leave the part about comparable not being an interface anymore

I think the only practical difference this makes, is that it doesn't allow mixing comparable with other constraints. Which is a problem with the design that would need to be addressed. At that point, any practical difference vanishes.

I don't want to hijack this issue much more but there is still a practical difference. comparable would not define a type set any longer. Only a set of permissible types which would also include all interface types and well-defined composites.
That's an important distinction.
The issue of mixing comparable with interfaces is acknowledged.
But it's really too off-topic now. Let's talk about it on #52531.

@aarzilli
Copy link
Contributor

aarzilli commented Apr 29, 2022

What happens to derived map types?

func F[K any]() map[K]bool { return nil }

does this become valid? Is instantiating it with a non-comparable type a typechecker error or a runtime panic? Or can you actually get a map[[]int]bool that doesn't work?

@carlmjohnson
Copy link
Contributor

carlmjohnson commented Apr 29, 2022

func F[K any]() map[K]bool { return nil }

IIUC, that would panic when run.

Here is another tough case. This does not compile:

func f(a []byte) {
	var b []byte = nil
	_ = a == b
}

But presumably this will compile and panic at runtime?

func f[T *any|[]byte](a T) {
	var b T = nil
	_ = a == b
}

f[[]byte](nil)

It's confusing because you can compare []byte to nil, but only against a constant nil, not against a variable that happens to have nil in it.

@zephyrtronium
Copy link
Contributor

zephyrtronium commented Apr 29, 2022

@Merovius

The == operator will simply be available to all type parameters unless their type sets contain only non-comparable types (it makes sense to exclude such type sets because we know with certainty that == will always panic for such type parameters).

I don't think it poses a problem, but if we ever make all interfaces into full types, this restriction would fully go away, as you could always instantiate a generic function using its constraint. i.e. the set of types a constraint would allow will always include a comparable type - the constraint itself.

An alternative here is to adjust the meaning of "comparable" to specifically exclude interfaces that have no comparable types. At least to me, that rule seems at first like it is a bit too subtle, but we already have precedent with struct and array types that the comparability of a type can depend on the contents of the type definition. It is a straightforward rule which also seems reasonable to include in the spec change for this proposal.

@apparentlymart
Copy link

apparentlymart commented Apr 29, 2022

I said this in more words in one of the previous proposals, but it seems more relevant here and so I'll state it again more concisely this time:

My general assumption is that whenever I use interface types (by which I mean: the pre-type-parameters mechanism for opting in to dynamic dispatch based on an interface) I am opting in to the possibility of panics at runtime in return for the flexibility of choosing a concrete type at runtime.

Therefore I expect to be able to choose to place an interface type in a type parameter and have the compiler defer to runtime any checks that depend on the final concrete type. This is under control of the caller of the generic function/type and so their own risk to take; the author of the callee only needs to specify that they require a comparable type, without regard to whether a caller will satisfy that constraint statically (by using a concrete type that the compiler can prove is comparable) or dynamically (by using an interface type where comparability is known only at runtime, and might therefore panic).

Constraining use of interface types because we don't know what concrete type they will contain at runtime rather seems to defeat the benefit of having them in the language. Callers are still free to use concrete types if they want the additional static guarantee of no panics at runtime.

This proposal seems to be a compromise within that mental model and so it seems favorable to me.

@rogpeppe
Copy link
Contributor

rogpeppe commented Apr 29, 2022

@griesemer

If a type parameter is instantiated with a non-comparable type and == is expected to work, upon invocation the generic code is likely to panic right away

That's interesting. Why is that?

Specifically, would the following code panic? (one could replace false with any unlikely or non-test-covered condition)

func F[T any](a, b T) {
    if false {
       _ = a == b
    }
}

@griesemer
Copy link
Contributor Author

griesemer commented May 5, 2022

@atdiar As you correctly state, all type parameters P implement interface{ ~string | ~int }

func f[P interface{ ~string | ~int }]() { f[P]() }
func g[P interface{ ~string }]()        { f[P]() }
func h[P interface{ string | int }]()   { f[P]() }

and yes, these interfaces can be used as type arguments.

I assume you're hinting at the fact that @neild just mentioned, which is that we can instantiate f with an interface T that implements f's type parameter constraint, but the interface type T is not in that type parameter's type set.

We have to be careful to not confuse type checking with the specifics of an implementation:

The type checking rules ensure that a correct generic function f with type parameter P can be instantiated with any type that implements P and f will still be correct. This is reasonably obvious from the existing rules: if f type-checks for all types in P (i.e., any concrete type in the type set of the constraint for P) then obviously f is correct for any concrete type T that implements P because T must be in P's type set. If T is an interface, and T implements P, then for any possible dynamic (concrete!) type in T, f will type-check because the type set of T must be a subset of the type set of P (otherwise it wouldn't implement it).

A valid implementation is to implement instantiation of f through stenciling (replacing the type parameter with the type argument throughout). So if we instantiate f with an interface T, the implementation produces a new f' where the type parameter is implemented as (replaced with) the interface T. So it would appear that f should have access to == on operands of type T because an ordinary Go interface supports ==. But it doesn't. The fact that the implementation used stenciling is an implementation choice. There may be other choices. Instantiating a generic function f with an interface type T doesn't mean we have access to the general functionality of interface types inside f, we only have access to the operations supported by all concrete types that implement T.

The fact that (for historic reasons) all ordinary Go interfaces supports == is a property of Go interfaces, not of their type sets. The == is "added" to an interface by virtue of it being an interface, whether or not we store a comparable type in a variable of interface type. This may well be the "original sin" in this context.

This proposal is trying to make == accessible to type parameters by doing the same that Go did for ordinary interfaces: it simply states that == is available, independent of the interfaces type set. And maybe we should not perpetuate the original sin and find another approach. Any such other approach will require that we explicitly indicate whether an interface is comparable or not, either by choice of explicit type set, or by using comparable as a marker in some way. Otherwise we have no way to know whether == is available or not in a generic function.

This proposal has disadvantages (some loss of static typing) and implementations problems (see the map issue further up). But it does seem consistent with what we have.

@griesemer
Copy link
Contributor Author

griesemer commented May 5, 2022

@jimmyfrasche We currently don't have a mechanism to describe type sets that include interfaces. Interfaces are type sets and cannot themselves contain interfaces. So comparable cannot contain all the types that are currently comparable in Go because that would include interfaces. See also my previous comment.

With respect to the line that would change in the examples: the call to f[any] would change and be newly permitted: the desire is to be able to instantiate comparable with any because an interface implements ==.

There is at least one other proposal (#52509) that suggests that we separate the notion of interfaces and type sets such that a type set can also contain interfaces. It may be possible but I admit I do not understand the repercussions quite yet.

@magical
Copy link
Contributor

magical commented May 5, 2022

The fact that (for historic reasons) all ordinary Go interfaces supports == is a property of Go interfaces, not of their type sets. The == is "added" to an interface by virtue of it being an interface, whether or not we store a comparable type in a variable of interface type. This may well be the "original sin" in this context.
[...] And maybe we should not perpetuate the original sin and find another approach.

I disagree with this framing. The fact that interfaces support == is not an accident, it is a deliberate, pragmatic choice. We should not sweep it under the rug simply because it is inconvenient.

@griesemer
Copy link
Contributor Author

griesemer commented May 5, 2022

@magical Sure. And this proposal is attempting to push this deliberate choice to the logical conclusion. But it seems that people are not happy with this much loss of static type checking in the context of generics. So this original decision has become a liability in this context. In other words, had we decided that comparable interfaces needed to be marked somehow as such from the start of Go, then we couldn't have this discussion at all. We'd be done.

@atdiar
Copy link

atdiar commented May 5, 2022

@atdiar As you correctly state, all type parameters P implement interface{ ~string | ~int }

func f[P interface{ ~string | ~int }]() { f[P]() }
func g[P interface{ ~string }]()        { f[P]() }
func h[P interface{ string | int }]()   { f[P]() }

and yes, these interfaces can be used as type arguments.

@griesemer I see. I am a bit confused actually.
In our example, what is the type of P for f, g, h? And its dynamic type if it applies?

I initially thought that P was simply assuming the role of a constrained type variable/parameter.

@griesemer
Copy link
Contributor Author

griesemer commented May 5, 2022

@atdiar P is a type parameter and its constraint is the respective interface, in all cases. A type parameter is a type like any other and can be used to instantiate another type parameter. The usual interface implementation rules apply because constraints are just interfaces and the underlying type of a type parameter is its constraint interface. (That's really the beauty of Go's generics type rules and why it all works out. And why it's difficult to adjust it in inconsistent ways.)

P doesn't have a "dynamic type" in the trad. interface sense. I've been saying earlier that a type parameter could be viewed as an interface with a "fixed" dynamic type, which is its concrete instantiation type, if we know it. But here we instantiate with P inside these functions, and we don't know its instantiation type outside of these functions. (The notion of "fixed" dynamic type is at best a thinking assistance and at worst misleading, so maybe it's best to ignore it. It's not needed to understand what's going on.)

@aarzilli
Copy link
Contributor

aarzilli commented May 5, 2022

One way to get around the problem with derived map types is to only allow a type parameter T to appear as the key to a map type if it appears as the key to a map type in the type parameter list.

For example func F[T any]() map[T]bool {...} would not be allowed and have to be written as func F[T any, _ map[T]any]() map[T]bool {...}.
Then F[any] is a valid instantiation, because interface{map[any]any} contains one type, but F[[]byte] is not a valid instantiation, because interface{map[[]byte]any} has an empty type set.

This would allow comparability to be written as a constraint without having the weird paradoxical comparable interface.

As for the equality operator func eq[T any, _ map[T]any](x, y T) bool { return x == y } could not be instantiated with a type that is always guaranteed to panic (like []byte or func()), but could be instantiated with an interface type (which could panic sometimes, but that's fine because that's how the equality operator works on interfaces).

And func eq[T any](x, y T) bool { return x == y } could either be allowed, or not. If it was allowed it could be instantiated with types that are not comparable and panic every time it's called.

There are a few problems with this:

  • the predeclared identifier comparable would have to be removed from the language, it's continued presence would only serve as a trap
  • approximately all code written for 1.18 that manipulates map generically will not compile anymore
  • it's one step farther away from allowing extra type parameters on methods.

@atdiar
Copy link

atdiar commented May 5, 2022

@griesemer

[edit] I think we understand the issue differently. From my understanding of your explanation, P is a variable of type interface{~string | ~int} which can hold a value that is either int or string. It is also assignable once, at instantiation.
This is fine.

What does not seem to work is that traditionally, for interface variables, the values that can be assigned to it are any value that implements the interface. This is not always the case for type parameters. interface{string|int} being one example here.

That's why the definition of interface implementation does not exactly match here: it's a necessary but not sufficient condition. (not an equivalence)

@ConradIrwin
Copy link
Contributor

ConradIrwin commented May 5, 2022

The map edge-case really comes down to ‘when’ it should fail.

I think the clearest answer is that it should fail as though the map had been instantiated with the key type of any - I.e. when you try and set a key and not before.

These two snippets should both compile and both fail with a runtime error when setting a key (assuming the runtime type of ‘c’ is not comparable).

func ag[T any](c T) {
  x := map[T]int{}
  x[c] = 1 // panic
}

func ai(c any) {
  x := map[any]int{}
  x[c] = 1 // panic
}

// all panic equivalently
ag(func () {})
ag[any](func () {})
ai(func () {})

Although it would be possible to panic when creating an instance of such a map, it seems better that these two functions fail equivalently instead of introducing a new failure mode to the language.

The simplification this gives you (in terms of programmer mental model) is that the behavior of code that compiles successfully depends only on the runtime type of values; you don’t have to think about separate failure modes for different compile time type arguments.

@Merovius
Copy link
Contributor

Merovius commented May 5, 2022

I think the clearest answer is that it should fail as though the map had been instantiated with the key type of any - I.e. when you try and set a key and not before.

Let me repeat this clarifying question, then. And would you agree, that the logical conclusion of this is that we should abandon the concept of static comparability altogether and allow == to be applied to any type and panic, if the type is inappropriate (just as if all values where wrapped in any)?

@atdiar
Copy link

atdiar commented May 5, 2022

func ag[T any](c T) {
x := map[T]int{}
x[c] = 1 // panic
}

That panic will only occur in a determinate manner if we do not have any branching in the body of the function or in the functions that call it.
Not sure it is tractable for a static tool to evaluate all branches.

@DmitriyMV
Copy link

DmitriyMV commented May 5, 2022

I think the clearest answer is that it should fail as though the map had been instantiated with the key type of any - I.e. when you try and set a key and not before.

The problem with map[K]V maps where K is func() for example is that it is incorrect type for all situations, unlike map[any]any. Basically with map[any]any you can add both variables of comparable types and it will behave properly, and variables of non-comparabable types and it will panic. With map[K]V where K is non-comparabable, every operation will fail, making it an incorrect type from the start. I'm also not sure how well reflect will play with incorrect types.

@Merovius
Copy link
Contributor

Merovius commented May 5, 2022

FWIW I think it would absolutely be possible to accept that all comparisons are valid and comparisons (and usage as a map key) of any func, slice or map type would panic when you operate on it. I don't like doing that, but it would be a consistent language.

I don't see a lot of middle ground though. I don't think we can allow comparisons and usage as map key for all type-parameters, while not also allowing them in non-generic code - because once we admit that these types can exist in some circumstances, carving out room so they don't exist in all circumstances seems complicated and confusing.

Another strange program, BTW:

func F[T any]() func(T, T) bool {
    return func(a, b T) bool { return a == b }
}

func main() {
    a := []byte{}
    f := F[[]byte]
    f(a, a) // panic, presumably
}

I think it would be very strange to adopt this proposal while not extending comparability to all types in general.

@griesemer
Copy link
Contributor Author

griesemer commented May 5, 2022

@atdiar

From my understanding of your explanation, the type of P is not interface{~string | ~int}.
This is fine.

In the example, the type of P in f is a type parameter with underlying (constraint) type interface{~string | ~int}. That's what the example says. And the type interface{string | int} definitely implements P and therefore could be used as type argument for P. But we do not allow this per the spec:

Interfaces that are not basic may only be used as type constraints, or as elements of other interfaces used as constraints. They cannot be the types of values or variables, or components of other, non-interface types.

In other words, the fact that interface{string | int} (currently) cannot be used to instantiate P has nothing to do with the rules for instantiation, it's because we do not allow such (variable) interface types. But we do allow type parameters with such interface types (constraints) and it all works as expected: in this example, g calls f with a type parameter of the desired type.

To repeat: Interface implementation is constraint satisfaction.

I think that seeing P as an interface is confusing. I find it clearer to see it as a bounded variable ranging over a set of types (variable for which there is no way to reassign a new type value).

Sure. All I am saying is that for purposes of type rules (and thus type checking), P's underlying type is an interface.

It's probably much clearer if we accept that an interface may define a constraint but a constraint is not an interface. Equating the two causes issues.

I couldn't disagree more. The fact that a constraint is an interface is what makes it all work. It's the insight that got us from a vague notion of "constraints" in 2018 to a thorough understanding of what a constraint is in 2021 and propelled the generics effort forward. It's the crux behind the type theory of Go generics.

The problem we're dealing with is not that constraints are modeled as interfaces or that constraint satisfaction is interface implementation. The problem is that ordinary Go interfaces have an == operator even if they can hold concrete dynamic types that are not comparable, which is and never has been statically type safe (hence the run-time panics); and that we are trying to make this work somehow with the rules for generics which are strictly enforcing static type safety. The generic type rules are correct. It's that Go programmers are used to having == on interfaces even though we have no guarantee that it will work without panic but now we want that guarantee when using == in generic code. That is the problem.

@Merovius
Copy link
Contributor

Merovius commented May 5, 2022

@griesemer

The problem we're dealing with is not that constraints are modeled as interfaces or that constraint satisfaction is interface implementation. The problem is that ordinary Go interfaces have an == operator even if they can hold concrete dynamic types that are not comparable, which is and never has been statically type safe (hence the run-time panics); and that we are trying to make this work somehow with the rules for generics which are strictly enforcing static type safety. The generic type rules are correct. It's that Go programmers are used to having == on interfaces even though we have no guarantee that it will work without panic but now we want that guarantee when using == in generic code. That is the problem.

It sounds like if we had comparable since Go 1, had made it a type from the beginning and only allowed == on interfaces embedding comparable, there wouldn't be a problem today, right?

Which seems like a case that we should accept #51338 and a vet check, if == is used with a non-comparable interface, which would get us most of the way into that problem-free world, right?

Are there any fundamental problem with that, apart from the virality-concerns of comparable?

@griesemer
Copy link
Contributor Author

griesemer commented May 5, 2022

@Merovius Exactly. See also the last paragraph in #50646 (comment).

I think you are probably correct that if we accept this proposal, we have to make == available to all types, similar to how we can use assignment with all types. Then there's no need to track comparability through constraints anymore, comparable becomes meaningless and should go away, and the problem is solved.

But it comes with a loss of static type safety that we may not be willing to accept for generic code. (The compiler could probably still complain if we directly compare concrete slice or function types, but that's beside the point.)

If we want static type safety for == we need to tell whether an interface/constraint supports ==. Which is what we do with comparable.

I think there's no middle ground here: we either a) make == universally available, or b) strictly track availability of ==. We cannot simply "adjust" the constraint satisfaction rules a little bit. Everything will come crashing down.

I also agree that accepting #51338 is probably the only viable alternative, the flip side of this coin. (The vet check would be icing on the cake in this case, wouldn't it?)

At the moment I also don't see any problems with #51338 besides the virality concerns.

@ConradIrwin
Copy link
Contributor

ConradIrwin commented May 5, 2022

@Merovius re: "And would you agree, that the logical conclusion of this is that we should abandon the concept of static comparability altogether and allow == to be applied to any type and panic, if the type is inappropriate (just as if all values where wrapped in any)?"

Not at all. I do think having fewer non-comparable values would be good for Go; but that is a separate discussion.

The way I think about it, is that there are three different "time"s at which an error can be caught:

  • Compile time when code is written
    // author of code writes:
    func Eq[T any](a, b T) bool { return a == b } //compiles
    func EqF[T func()](a, b T) bool { return a == b } // doesn't compile
    
  • Compile time when code is used
    func Eq([]byte{'a'}, []byte{'a'}) //compiles
    func Eq("a", "a"). // compiles
    
  • Run time (when the code is run).

I would suggest that an important property to preserve is that the "compile time when code is used" behavior depends only on the type-signature of the function, not on its implementation. (I think that is the case today, and under #52509, and under this proposal). I don't think we need to go so far as to say "any code that uses == should compile".

An emergent property of that (in combination with any is comparable) which is maybe surprising, but is perfectly consistent, is that you could use generic code to create a useless (but well-defined) instance of a map for the sole-purpose of deferring the type-check to runtime.

The other emergent property (that I really like) is that you can "inline" any method set type parameter to get a specialized function with the same behavior.

func Eq[T any](a, b T) { ... }
func Eq(a, b any) { ... }

For #52509 the emergent property is that you need to specify comparable everywhere, despite it not really adding any additional safety.

// under #52509 
func Eq[T comparable](a, b T) bool {
  return a == b
}

f := func (w http.ResponseWriter, r *http.Request) { }
h := http.HandlerFunc(f)
Eq(f, f) // compile time error
Eq(h, h) // runtime error

I think this is not really adding any safety because (in my experience) you are most often in the "runtime error" camp anyway; and so having two ways to fail what would otherwise be very similar pieces of code seems unnecessary to me.

#51338 does also have the emergent specialization feature

func Eq[T comparable](a, b T) { ... }
func Eq(a, b comparable) { ... }

which is nice; but continues to fail to compile programs that would run just fine, and it's not obvious how to fix them.

Eq(context.TODO(), context.TODO()) // compile time error
context.TODO() == context.TODO() // => true

This is (I think) a matter of taste, more than anything else. I really enjoy that go generics re-use interfaces, and I think that was a great insight to simplify things and avoid adding new concepts. I also really enjoy a language that doesn't require too much ceremony, and statically declaring comparable or not seems (to me) like too much ceremony.

@atdiar
Copy link

atdiar commented May 5, 2022

@griesemer

The way I see it, we risk complicating either interfaces or constraints or both.
Beginners will expect that the constraint interface{string | int} denotes an option between string or int. Not string or int or any interface type that implements it.

I think I see what you mean by a type parameter's underlying type is an interface but I still don't see how P could be instantiated by interface{string | int} even if it was allowed.
An interface has no "+" operator for instance. (and if we decide that it has, what should it do on unmatching dynamic types?)

If we accept that a constraint defines the set of permissible type arguments, I don't understand why the only way to construct such a set has to be an interface.
comparable could just be a constraint. There is no real need to make it an interface? (it would solve the issues with type sets and virality just as well if not better)

Anyway, that's my view, I guess we will see, but I find it quite a pity that all constraints have to be an interface. This is too inflexible imho. That interfaces can be constraints is fine. This is just a way to denote a set of types.

@DmitriyMV
Copy link

DmitriyMV commented May 5, 2022

@ConradIrwin

The way I think about it, is that there are three different "time"s at which an error can be caught:
Compile time when code is written

This is the current strategy for (almost?) all generics implementations except C++. It is also current Go strategy for every non-generic code. You can't call do stuff on type which it does not support explicitly.

Compile time when code is used

This is C++ strategy and it's very bad if you have layers of generic code, because it produces error messages deep down the line. In Go case vet check will only catch very simple errors, because traversing entire tree is unpractical.

The other emergent property (that I really like) is that you can "inline" any method set type parameter to get a specialized function with the same behavior.

I'm not sure what you mean.Eq[int] for example and traditional Eq(a, b any) are not interchangeable under this proposal. That is - you can't use one in place of another (unlike Java where subclassing allows you that). If we are talking about Eq[any] - yes, you could, but I don't see much benefit to using generics if you rely on dynamic behavior in the first place. YMMY.

@apparentlymart
Copy link

apparentlymart commented May 5, 2022

The discussion about whether interfaces and constraints are exactly the same thing or whether one is a subset of the other etc is an interesting way to draw out the details of how exactly this could work.

The main way I've been thinkiing about these proposals focused on comparable is that it feels to me like it would help understanding and orthogonality of the language if there were a way to define map types in the spec as if they were made of type parameters, rather than them being special (other than syntax). Hypothetically changing the spec say in effect that a map type is map[K comparable](V any) with just some special syntax -- changing comparable to make that comparison correct -- was the way I was originally approaching it, but I'm sure that's not the only way.

I bring this up because I see the discussion shifting to the idea of comparable being a new kind of thing called a constraint, rather than it being exactly an interface, and I wonder what a type-parameters-oriented explanation of map types would look like in that view of the world. At first glance it feels like it would end up needing to just stay as effectively map[K any](V any) with a prose description of the special case for when K is an interface type, and maybe that's the best compromise in the end, but it does mean that any generic collection type which wraps a map risks being overconstrained by its author as comparable because the treatment of K in map types feels like "comparable" even though it isn't exactly that. A caller of that type would not be empowered to override that decision to select something that is dynamically comparable even though it's not statically provable.

@Merovius
Copy link
Contributor

Merovius commented May 5, 2022

@ConradIrwin

The other emergent property (that I really like) is that you can "inline" any method set type parameter to get a specialized function with the same behavior.

I'm not sure. You obviously can't unless the constraint is a basic interface. But I also don't think it's strictly true even if it is. Here's a dumb example:

func F[T any](v T) { fmt.Printf("%T\n", &v) }
func G(v any) { fmt.Printf("%T\n", &v) }

func main() {
    F(42) // prints "*int"
    G(42) // prints "*interface{}"
}

Maybe I'm picking nits. But it also also definitely would be not true for writing out a specific instantiation, which I think is similarly important.

For #52509 the emergent property is that you need to specify comparable everywhere, despite it not really adding any additional safety.

// under #52509 
func Eq[T comparable](a, b T) bool {
  return a == b
}

f := func (w http.ResponseWriter, r *http.Request) { }
h := http.HandlerFunc(f)
Eq(f, f) // compile time error
Eq(h, h) // runtime error

No, the second one would be a compile time error as well. The compiler would infer http.HandlerFunc, which is not comparable. You'd have to write h := http.Handler(http.HandlerFunc(f)) or write Eq[http.Handler](h, h) for this to become a runtime error. Which is why I kind of think this problem with #52509 is overstated. I'm not saying it never happens that you accidentally instantiate a generic function/type using interfaces, but it is surprisingly hard.

But no matter. #52509 has other problems as well.

which is nice; but continues to fail to compile programs that would run just fine, and it's not obvious how to fix them.

Over the long term, hopefully, by being deliberate about embedding comparable or not. It will definitely be a transition and it might be a painful one.

FTR your specific example is, IMO, a bad one. I don't think context.Context should be comparable, so the fact that it is and does not panic is arguably a mistake.

I also really enjoy a language that doesn't require too much ceremony, and statically declaring comparable or not seems (to me) like too much ceremony.

I think comparable is in no way different from declaring that a type should have a Read method. It's just another operation you can do on a type. In many languages, it is the same, as they use operator overloading. I think if comparable feels like ceremony, the only reason is that you didn't used to have to.

@griesemer
Copy link
Contributor Author

griesemer commented May 5, 2022

@atdiar

The way I see it, we risk complicating either interfaces or constraints or both.

We definitely risk complicating interfaces or constraints or both if we separate constraints from interfaces as you seem to hint at. Which is why we don't.

Beginners will expect that interface{string | int} denotes an option between string or int. Not string or int or any interface type that implements it.

It does exactly denote an option between string or int. And of course any interface that implements it which again could only contain string or int. Seems pretty consistent. Rather similar to a bool variable which can be assigned the value true or false, and any bool variable which again could only hold a true or false value.

An interface has no "+" operator for instance. (and if we decide that it has, what should it do on unmatching dynamic types?)

A type parameter constrained by interface{string | int} definitely has a "+" operator. And if we were to allow such interfaces as ordinary variable types we could make the "+" operator work by dynamically checking that the dynamic types match (and panic otherwise). That seems consistent with the dynamic dispatch we do for methods. And it matches exactly the dynamic check we do for == already. Again we must not confuse the implementation or operational behavior of interfaces with the type(s) they represent.

If we accept that a constraint defines the set of permissible type arguments, I don't understand why the only way to construct such a set has to be an interface.

So you're suggesting a separate language construct which is a type set, used as a constraint, and which somehow is different from an interface. This is similar to what others have suggested in #52509. But such a type set would have to interoperate with concrete and interface types somehow. Specifically, we'd need to explain how an interface implements a type set (constraint) and how a type set implements an interface (when a type parameter is assigned to an interface); maybe even the same interface. See also #52509 (comment) which I believe addresses the same question. I'd love to see the exact rules of how interfaces and such hypothetical constraint type sets interoperate. But it's hard to imagine that this would be simpler (and more flexible) than what we have now.

comparable could just be a constraint. There is no real need to make it an interface? (it would solve the issues with type sets and virality just as well if not better)

The beauty is that comparable is a constraint, because interfaces and constraints are the same. Besides, how would it solve the issue with type sets and virality "just as well"? See again the previous paragraph on how constraints and interfaces must work together.

but I find it quite a pity that all constraints have to be an interface. This is too inflexible imho

See the previous paragraph and also my previous reply (last paragraph).

@atdiar
Copy link

atdiar commented May 5, 2022

Not really suggesting a type set because type sets do not include interface types.
I'm suggesting another way to denote the set of permissible type arguments. Which is rarely if ever just the type set.

The explanation about unions is a complication of interfaces imho. That they might inherit possibly panicking operators from their type sets is more complex. But fair enough.

That interface{string | int} does not really mean either string or int is also another thing to explain. If I got confused, it's possible that someone else will.

Differentiating comparable from interfaces would help the question of virality because, even though usable as a constraint, it would not be necessary or even possible to embed it in interfaces. Interface types would satisfy comparable by default.
It's not free (requires syntax) but it would make the generic implementation consistent with the non-generic language.

Also because comparable would not be an interface, interface types would not have to implement it.
Which solves the following problem:
If a function f implements an interface A that implements an interface B, then we can intuit that f also implements B.

But if all interfaces have to implement comparable now, then the function f implements comparable?!

We can see this problem because f is in the typeset of any for instance.

comparable being an interface adds unnecessary complexity.

We just need to check that types have the comparison operators to satisfy the constraint. This is not something that looks difficult to do, unless I am mistaken.

@carlmjohnson
Copy link
Contributor

carlmjohnson commented May 15, 2022

Experience report: Here is a blog post where Tim Bray (ex-AWS) is confused about comparable and interface map keys.

@griesemer
Copy link
Contributor Author

griesemer commented May 17, 2022

It seems pretty clear at this point that this proposal, at least in the current form, is not providing the kinds of static guarantees that people would like to ensure.

Retracted.

@rsc rsc moved this from Incoming to Declined in Proposals (old) May 25, 2022
@rsc
Copy link
Contributor

rsc commented May 25, 2022

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
generics Issue is related to generics Proposal
Projects
Status: Declined
Development

No branches or pull requests