proposal: type parameters are comparable unless they exclude comparable types

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:

spec: document/explain which interfaces implement comparable #50646
spec: any no longer implements comparable #51257
proposal: spec: permit values to have type "comparable" #51338
proposal: spec: permit non-interface types that support == to satisfy the comparable constraint #52474
proposal: spec: allow interface types to instantiate comparable type parameters #52509
proposal: spec: add new constraint kind satisfied by types that support == (including interface types) #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 #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).

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.

@hherman1

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

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?

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?

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.

@atdiar

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

@griesemer

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

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

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.

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?

@griesemer

@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).

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

comparable cannot be easily defined using an interface and implemented
using compiler magic;
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.

@griesemer

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

@ConradIrwin

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

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.

@ConradIrwin

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

@atdiar

@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).

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.

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

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.

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

Navigation Menu

Repository navigation

proposal: type parameters are comparable unless they exclude comparable types #52614

Introduction

Proposal

Discussion

History and credits

81 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

proposal: type parameters are comparable unless they exclude comparable types #52614

Description

Introduction

Proposal

Discussion

History and credits

Activity

hherman1 commented on Apr 29, 2022

griesemer commented on Apr 29, 2022

atdiar commented on Apr 29, 2022

zigo101 commented on Apr 29, 2022

magical commented on Apr 29, 2022

griesemer commented on Apr 29, 2022

atdiar commented on Apr 29, 2022

zigo101 commented on Apr 29, 2022

Merovius commented on Apr 29, 2022

changkun commented on Apr 29, 2022

ConradIrwin commented on Apr 29, 2022

changkun commented on Apr 29, 2022

81 remaining items

atdiar commented on May 5, 2022

DmitriyMV commented on May 5, 2022

apparentlymart commented on May 5, 2022

Merovius commented on May 5, 2022

griesemer commented on May 5, 2022

atdiar commented on May 5, 2022

earthboundkid commented on May 15, 2022

griesemer commented on May 17, 2022

rsc commented on May 25, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions