proposal: type parameters are comparable unless they exclude comparable types

[griesemer]

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:

• 50646

• 51257

• 51338

• 52474

• 52509

• 52531

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 https://github.com/golang/go/issues/51338#issuecomment-1057735177). 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 https://github.com/golang/go/issues/52509#issuecomment-1109359139.

[Merovius]

@griesemer Yes, @neild's response is similarly effective, without relying on a change to generics.

I appreciate the concern about lack of static type checking here; I do worry about it myself. But it's not the only concern, yet most feedback so far (in this and the other related proposals) seems to only worry about that. What about: […]

I, for one, think I didn't fully understand all the implications of this yet, which is why I haven't commented about it so far. Which is saying something in and off itself, maybe.

I do find "type parameters are interfaces" a very surprising explanation, I must say. It's not how I conceptualize them. To me, func F[T any]() is not "a function using any type", but "a collection of functions, indexed by a type". F itself has no identity to me and consequently neither has T. So, I wouldn't really expect var x T in a generic function to behave like an interface type - I would expect it to behave "like whatever T ends up being instantiated". I don't know, it's hard to talk about, but it's what makes this proposal hard to find simple, for me.

I also think this is an exceedingly good question, which AFAICT has not been answered yet? I don't have a good answer to what this should do.

One answer was "it panics", but, at what point? Like, if I do var x = F[[]byte](), what's the type of x as reported by go/types for example? Does the instantiation itself panic, or could I pass F[[]byte] to reflect.TypeOf to get access to a reflect.Type representing map[[]byte]struct{}? If the former, instantiations seem to conceptually happen at compile time, to me (that was one of the appeals of the design), does that mean the program just compiles to a panic? What happens if I write type X[T any] map[T]struct{}; type Y X[[]byte]?

Or should we just allow writing map[A]B for any A after all, maybe? And have that panic whenever something is assigned? That seems only consequential, if we allow it for any type parameter.

[atdiar]

@ianlancetaylor

Unless mistaken,

• fmt.Stringer : implements itself and is in the set permissible of type arguments it defines. These are strict supersets of the typeset.
• interface{ ~string | ~int} : implements itself but is not in the set of permissible type arguments it defines. interface{ ~string} also implements it?

The third point was about comparable, in general, the set of permissible type arguments is even larger. It is still true with this proposal but comparableis not first-class anymore.

The easiest way I've found is reasoning in terms of set of permissble type arguments. Which is the way the spec defines a type constraint, so this is good.

[ianlancetaylor]

The question about maps of a non-comparable type is a great one. Sorry I missed it.

I think the simplest answer is that it panics on a call to make, or, given a nil value, a map lookup or a call to delete (or the equivalent reflection functions).

But, yes, that is troubling.

[ianlancetaylor]

@atdiar OK, I see what you mean. You can't use interface { ~string | ~int } as a type argument, so the issue you are describing doesn't seem to arise today.

[jonbodner]

@ianlancetaylor This gets back to my question about compile-time checks. Can the compiler tell that there's (a) a type parameter being used as a map key and (b) that the concrete type that's supplied for an instantiation isn't comparable? This feels like something that can be detected at compile-time in the vast majority (all?) cases. It wouldn't be explicit in the function/method signature, but that seems OK to me if the compile-time error explains the problem.

You can substitute "==", "== nil", and whatever other operator you'd like for "map key" in the sentence above.

It is slightly coloring a function, I guess, but it does prevent a run-time panic.

[ianlancetaylor]

One goal we want to retain is that if the type parameters don't change, the code that instantiates the generic function/type will continue to compile. We don't want it to be the case that a change to the body of a generic function/type can cause other instantiating code far away to stop compiling.

[ianlancetaylor]

(That was, of course, the point behind adding comparable in the first place.)

[jonbodner]

I appreciate the concern, but in my preference hierarchy, I'd rather have code far away stop compiling than have code panic at runtime. I guess it's a matter of how frequently we can expect these sorts of changes to happen.

[Merovius]

I think the simplest answer is that it panics on a call to make, or, given a nil value, a map lookup or a call to delete (or the equivalent reflection functions).

To clarify: Are you suggesting we remove the restrictions on valid map keys in general? That is, would m := make(map[[]byte]struct{}) become a valid program, which panics at runtime?

Otherwise, ISTM this would still require us to remove the restriction on map-keys (as the types can exist, as a result of short variable declarations), but also add some new special-casing to disallow their use in type literals.

[Merovius]

@ianlancetaylor Actually, I don't feel lifting restrictions on map keys alone is enough. We (specifically, me and @bcmills) brought up a couple of times that manually expanding instantiations of generic functions should be valid and vice-versa. That is, given

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

and given that Eq[[]byte] would become valid, it would be confusing for

func Eq(a, b []byte) bool { return a == b }

to not be valid. The only way to resolve that confusion would be to allow comparison on any type (panicing at runtime for inappropriate types).

Of course "manual instantiation doesn't work" is a weaker problem than "you can create maps with non-comparable keys, whether we want or not". But it doesn't feel good to me nevertheless.

[jimmyfrasche]

I think the restriction would have to be removed

func F[T any]() reflect.Type {
  var m map[T]struct{}
  return reflect.TypeOf(m)
}
var _ = F[func()]

I do not like this proposal

[earthboundkid]

I think the problem with this proposal is that it goes back on the decision that it's worthwhile having some form of comparable. ISTM that whatever the original reasoning was that led to comparable, it's a bit late to revisit it unless there turns out to be something deeply unworkable about it. For that reason, I prefer BC Mill's proposal to this one at the moment.

[atdiar]

@atdiar OK, I see what you mean. You can't use interface { ~string | ~int } as a type argument, so the issue you are describing doesn't seem to arise today.

@ianlancetaylor Well the original statement is still true whether interface { ~string | ~int } can be used as a type argument or not today, I believe.

We still have multiple sets to think about.

[griesemer]

@Merovius Regarding "type parameters are interfaces": I agree that this looks surprising. It all boils down to the question of what the underlying type of a type parameter is for type-checking purposes. Each type parameter is a new type, very much like each defined type is a new type, by virtue of their name. Similarly to how we talk about an array whether it has a name given by a type definition or not, we can talk about the interface of a type parameter given by the type parameter declaration. (We sometimes say "constraint" for emphasis, but "constraint" per se is not a new kind of type in the language, it's the use of an interface in constraint position.) A type parameter's properties are exactly defined by its (constraint) interface and the type set defined by that interface. Specifically, we can invoke the same methods as if it were an ordinary interface. (In turn, we could imagine that operators that are permitted on type parameters could be permitted on ordinary interfaces if they were allowed to be type-constrained - though we probably would never go there as it would require run-time checks.) The primary difference between type parameters and interfaces, relevant for type checking, is that the "dynamic type" of a type parameter interface is fixed at instantiation time and cannot be changed. Which makes for some adjustments to the usual interface rules. And which allows us to apply operators without some dynamic run-time checks. But in any other respect, type parameters behave like interfaces for type-checking purposes. Specifically, treating them as such (while keeping the fixed "dynamic type" in mind) answers many type checking questions directly (such as does a pointer to a type parameter have methods, and others). As an aside, the Featherweight Generic Go authors also subscribe to this view when they explicitly model the underlying type of a type parameter explicitly.

The more general point here is that == is an operator of ordinary Go interfaces that has (from the start) been independent of the dynamic type of the interface; it's always provided whether the dynamic type can do == or not. As long "implementing an interface" and "satisfying a type parameter constraint" mean the same thing (which is a significant point of simplification) it seems to me that == needs to be available on type parameters (at least the ones constrained by ordinary interfaces) or we run into inconsistencies (see #50646).

But I agree that maps of non-comparable map types are troubling; I also missed that question. :-(

[griesemer]

Ironically, our early implementation did allow the assignment of a variable of type any to an interface comparable (#50646), including the instantiation of a comparable type parameter with any before we fixed that inconsistency, which led to the current, consistent, but restrictive, definition of comparable.

[neild]

which is a significant point of simplification

I'm no longer convinced that this is a point of simplification.

We have three separate concepts:

1. Types which can be boxed by a variable of interface type T (the type set of T).
2. Types which can be assigned to a variable of interface type T.
3. Types which can satisfy a constraint of type T.

Combining cases 2 and 3 under "types that implement T" reduces the number of concepts in the language, but is a source of ongoing confusion because assignment is concerned with the value boxed by an interface value, while constraint satisfaction is concerned with the interface value itself.

This keeps going in circles because we're trying to stretch the single concept of "implements" to cover two different cases, and one or the other refuses to fit.

Given that this is difficult/impossible to change at this point, however, what breaks if we add a clause to the "implementing an interface" rules: "A type T implements an interface I if T is an interface and I is comparable"? It's an ugly special case, but a small one for a demonstrably complicated edge case. This does permit assigning any to comparable, which is irrelevant so long as we don't permit comparable as a regular type.

[jimmyfrasche]

@griesemer This seems to be the (hidden by default) comment in that issue you are referring to: https://github.com/golang/go/issues/50646#issuecomment-1022890421

I don't see anything inconsistent or contradictory in there. Not obvious, perhaps, but it seems correct and logical.

[jimmyfrasche]

@neild I think just splitting out the "X is in the type set of I" is sufficient, specwise, see my comment here https://github.com/golang/go/issues/52509#issuecomment-1114059140

[neild]

what breaks if we add a clause to the "implementing an interface" rules: "A type T implements an interface I if T is an interface and I is comparable"?

Answering my own question, this breaks:

func F1[T comparable](T) {}

func F2[T any]() {
  // If any implements comparable, then the following instantiation is valid.
  // But if F1[func()] is invalid, then the following instantiation cannot be valid (because func() is in F2's type set).
  F1[T]()
}

[jimmyfrasche]

Oh I see. In:

func f[P comparable]() {}
func g[P any]() {
  f[P]
}

You're using implements to see if f can be called from g instead of subset. Is checking typeSetOf(any) subset typeSetOf(comparable) incomputable in general or something horrific like that?

[atdiar]

@griesemer

As long "implementing an interface" and "satisfying a type parameter constraint" mean the same thing (which is a significant point of simplification)

That's actually the point that I was trying to make. That simplification does not hold even if we remove comparablefrom the mix. Implementing interface{~string | ~int} is not equivalent to satisfying the corresponding type parameter constraint. (I also thought it could be equivalent initially because I was focused on basic interfaces)

Whether we can use interface{~string | ~int} as a type argument today or not is a bit irrelevant, as it is not and will never be possible anyway.

So an interesting question would be: how to determine the set of permissible type arguments? If we already have different cases, why not add a specific bullet-point for comparable.

[griesemer]

@atdiar

Implementing interface{~string | ~int} is not equivalent to satisfying the corresponding type parameter constraint. (I thought it could be equivalent initially because I was focused on basic interfaces)

I'd love to hear why that is. The spec says so, and the implementation does so. What am I missing? (And note, we can use a type parameter constrained by interface{~string | ~int} as type argument today.)

[atdiar]

@griesemer

• interface{~string | ~int}
• interface{~string}
• interface {string | int} -...

All implement interface{~string | ~int} but are not in the set of permissible types it defines, by construction, if I'm not confused somewhere.

And even if these interfaces could be used as type argument, they would still not belong to the set of permissible type arguments for that constraint even though we have interface implementation.

[griesemer]

@jimmyfrasche In your example f cannot be called from g (at the moment) since P does not implement comparable because the type set of P (which is the type set of any) is not a subset of the type set of comparable: the empty interface is the set of all types which includes types that are not in the type set of the comparable types.

The implements relationship is doing a subset test (do not be confused by the actual implementation which is making use of the various implementation restrictions at the moment).

The whole point of the discussion is that we somehow want any to implement comparable because we can use == on variables of interface type (even if their dynamic types are not comparable in the least). Which then leads to odd situations like:

func f[P comparable]() {
   _ = f[P] // ok
   _ = g[P] // ok
   _ = f[any] // currently not ok but we'd like it be ok even though typeset(any) is not a subset of typeset(comparable)
}

func g[P any]() {
   _ = g[P] // ok
   _ = f[P] // not ok because typeset(P) == typeset(any) is not a subset of typeset(comparable)
   _ = g[any] // ok
}

But I may not understand what you're asking.

[neild]

What breaks if any (and all other interface types) is in the type set of comparable?

That violates the rule that no interface type has an interface type in its type set, and I suspect it breaks something even if we don't allow variables of type comparable, but I can't figure out what.

[jimmyfrasche]

So, if everything were the same as today except that the type set of comparable were defined to be all types that satisfy the definition of comparable in https://go.dev/ref/spec#Comparison_operators , then

func f[P comparable]() {
   _ = f[P] // ok
   _ = g[P] // ok <- this is the only line that changes from your last post
   _ = f[any] // ok
}

func g[P any]() {
   _ = g[P] // ok
   _ = f[P] // not ok because typeset(P) == typeset(any) is not a subset of typeset(comparable)
   _ = g[any] // ok
}

Is that correct? I feel like I'm missing something because that seems like everything there is how it should work while still allowing you to statically require an == operator.

[griesemer]

@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]

@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]

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]

@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]

@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]

@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]

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]

@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 intor 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]

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]

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]

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]

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]

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]

@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]

@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]

@Merovius Exactly. See also the last paragraph in https://github.com/golang/go/issues/50646#issuecomment-1023706545.

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]

@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]

@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. comparablecould 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]

@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]

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]

@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]

@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 https://github.com/golang/go/issues/52509#issuecomment-1118148009 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]

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.

[earthboundkid]

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