proposal: spec: allow interface types to instantiate comparable type parameters

[zephyrtronium]

Background

Out of caution over backward compatibility of features introduced with generics, with little discussion with the community when changing a major proposal that had already been accepted, Go 1.18 defined the predeclared constraint comparable to be "the set of all non-interface types that are comparable." The majority of the conversation motivating the "non-interface" portion of that definition occurred in #50646 and #49587.

That interface types are comparable but not comparable is a significant pain point for a number of otherwise fine uses of generics: e.g., one cannot use x/exp/maps algorithms on map types which have reflect.Type as keys. #52474 (now retracted) was proposed to alleviate this problem, noting that the precise definition of comparable should include types like [1]reflect.Type, which is an array type supporting == rather than an interface type. A significant portion of the comments on that proposal noted that the entire motivation for the proposal is the inconsistency between "comparable" and comparable.

Proposal

The proposal here is to allow interface types to instantiate type parameters constrained by comparable. In essence, I propose to remove the term "non-interface" from the definition of comparable, so that "comparable" and comparable mean the same thing in every context in Go.

@atdiar points out that other language in the spec would produce contradictions following that simple change. This proposal would additionally require a change to the definition of type sets or the definition of implementing interfaces, likely splitting either or both into two senses for type parameters and otherwise.

A consequence of this proposal is that it becomes possible to write generic code using comparable which panics on comparison with non-comparable concrete types. That is an aspect of the type system which has existed since long before Go 1.0; in particular, see @nield's demonstration that the results are very similar to the situation we've always had. What we gain is the ability to write code generic over all comparable types, rather than most of them with no solution for the remainder.

For the concrete change to the Go specification that I propose to implement this, see #52509 (comment). It is not the only possible approach. @jimmyfrasche proposes #52509 (comment), and @Merovius proposes #52509 (comment) with an enumeration of examples at #52509 (comment).

Related Proposals

• proposal: spec: permit values to have type "comparable" #51338
• proposal: spec: add new constraint kind satisfied by types that support == (including interface types) #52531
• proposal: type parameters are comparable unless they exclude comparable types #52614
• proposal: spec: allow values of type comparable #52624
• proposal: spec: comparable as a case of a generalized definition of basic interfaces #53734

[beoran]

I agree with this proposal as it is simpler than the others. For code that would like to have a call comparable that cannot panick, we can add a strict_comparable (or the same with a better name) predefined interface.

[gopherbot]

Change https://go.dev/cl/401874 mentions this issue: spec: clarify type set and interface are different

[changkun]

I was prototyping a spec change, and it seems compatible with the goal of this proposal, although the implementation goes more into the detail of differentiating type sets and interfaces.

To advocate stopping those incomprehension discussions, we should clarify what exactly is the problem, and I think the problem is we are limiting ourselves to a mindset that type set and interfaces are the same things, which it turns out: they are different.

Again: Interface is just an approach to define a type set, and it can embed another type set, which may be an interface, comparable, or any other future possible predeclared type set.

Therefore, in CL 401874, I attempt to clarify this and remove comparable from a predeclared type to a predeclared type set.

As a side effect, comparable is now aligned with the original type parameter proposal, that: The predeclared identifier comparable is a type set that denotes the set of all types that are comparable (this "comparable" refers to the Go 1's definition of types that are comparable). For the differences between any and comparable, simply just: depending on how they are used:

func f[T any](x T) {}         // any as type set
func g[T comparable](x T) {}
func h(x any){}               // any as function parameter

var (
    x func() = func() {}
    _ = f(x) // OK, T is infered as func(), and f is instantiated as f(x func())
    _ = g(x) // Invalid, type func() is not comparable.
    _ = h(x) // OK, h accepts anything
)

Also, this behavior remains the same as expected:

var (
	anyType        = types.Universe.Lookup("any").Type()
	comparableType = types.Universe.Lookup("comparable").Type()
)
fmt.Println(types.AssignableTo(comparableType, anyType)) // true
fmt.Println(types.AssignableTo(anyType, comparableType)) // false

[Merovius]

@changkun FWIW I disagree that the core issue is one of how to word things. I believe the core issue is what behavior we want, i.e. a) do we want comparable to be usable as a type (#51338), b) do we want interface types to implement the comparable constraint (this proposal) and c) do we maybe want to do other changes to solve other problems associated with either (e.g. #52474, which tries to address a problem with #51338). Once we decided on the behavior we want, finding the right words to put into the spec should be easy. But we should really focus on the actual technical language changes we want, first.

[changkun]

@Merovius I think the wording address what we might want explicitly:

• a) we disallow comparable to be used as a type (as they are not today)
• b) interfaces are comparable and satisfy comparable type set (as they are in Go 1)
• c) the problems are not valid if type set is just a type set. (as the generics design doesn't permit using interface to be Turing complete for defining all kinds of type sets)

[Merovius]

@changkun What you are not doing is talking about what kind of code we want to be able to write and what that code should or should not do. #51338 and this proposal both try to address a specific problem: There is no way to instantiate e.g. type Set[K comparable] … using interface-types. They do that using concrete technical changes, which have their own, technical drawbacks, namely "comparable becomes viral" in the case of #51338 and "comparisons in generic functions might panic" in the case of this proposal. If we want to enable people to use code like Set[reflect.Type], we have to address and/or weigh these drawbacks.

None of these technical questions changes based on whether we call comparable a "constraint", a "type set" or a "type" (though TBF, we use "comparable is a type" as a short-cut for #51338). It doesn't help to demonstrate that a particular answer can be worded in the spec. We need arguments as to why a particular answer is better than the others.

IMHO one reason these discussions have become so long and convoluted is because people try to interpret what "comparable" means and/or trying to come up with new definitions of that term, instead of talking about the concrete technical questions which are on the table. Namely, what code do we want to be able to write and what should that code do.

[atdiar]

So would interface types be included in comparable's typeset?

What would it entail?

[Merovius]

@atdiar

So would interface types be included in comparable's typeset?

Yes.

What would it entail?

I don't understand the question.

[atdiar]

So now how would you define interface implementation in terms of typeset?

[Merovius]

@atdiar I don't think we should worry about how to word the change, before we have decided what the change is we want to make. It doesn't seem particularly hard to word this, to me.

[atdiar]

It's not just about wording. It affects how we understand, compute and use typesets.
So I will rephrase because it is important.

Currently the spec defines an interface T implementing another interface I as:

T is an interface and the type set of T is a subset of the type set of I.

How would you change it?

[Merovius]

If you have questions about how a specific piece of code would behave under this proposal, or how a specific piece of code could be written, I feel more confident that I could answer. Personally, as I said, I think it detracts from the discussion to talk about wording (but, if someone else thinks differently, they might well try to take a stab at it, of course).

[changkun]

you are not doing is talking about what kind of code we want to be able to write and what that code should or should not do. #51338 and this proposal both try to address a specific problem: There is no way to instantiate e.g. type Set[K comparable] … using interface-types.

I am not because people are mixing the objectives and concepts here.

Of course I understand there is no way to instantiate a vague conceptual "comparable" type set type Set[K comparable] …. But it has no association with the existing comparable identifier, the issue is: how such a type set looks like, and what should be the name of such a type set.

The language had a definition of "comparable" types, and comparable is the set of types that are comparable.

They do that using concrete technical changes, which have their own, technical drawbacks, namely "comparable becomes viral" in the case of #51338 and "comparisons in generic functions might panic" in the case of this proposal. If we want to enable people to use code like Set[reflect.Type], we have to address and/or weigh these drawbacks.

Is it a problem with "what we want to write", or "what people would actually do"?
If we use type set comparable:

func eq[T comparable](x, y T) bool { return x == y }

and people erase the type information using any:

var _ = eq(any(func(){}), any(func(){})) // eq(any, any)

Is the panic a language issue or a usage issue?

None of these technical questions changes based on whether we call comparable a "constraint", a "type set" or a "type" (though TBF, we use "comparable is a type" as a short-cut for #51338). It doesn't help to demonstrate that a particular answer can be worded in the spec. We need arguments as to why a particular answer is better than the others.

No. I think all of these questions arise because people start to talk about a solution without defining the scope or understanding what it exactly means. Again, the problem would be framed completely differently if the concepts are clarified. The problem would be: proposal: spec: add new predeclared type set X, Y, Z

IMHO one reason these discussions have become so long and convoluted is because people try to interpret what "comparable" means and/or trying to come up with new definitions of that term instead of talking about the concrete technical questions which are on the table.

Exactly! But how do all these questions is strong associating with the identifier comparable then?

[Merovius]

@changkun

I think all of these questions arise because people start to talk about a solution without defining the scope or understanding what it exactly means.

"We want to be able to instantiate type Set[K comparable] … using reflect.Type" is a precise and unambiguous problem-statement. It stands in for a wider range of problems, e.g. "we want to be able to write a maps.Keys function usable with a map[reflect.Type]T". It is not a solution, it is a problem. Specifically, a problem about particular pieces of code, which are currently impossible to write.

That particular problem is addressed by #51338 (after embedding comparable in reflect.Type) and it's addressed by this proposal, by allowing type parameters interface types to implement comparable. There might be other solutions as well, feel free to bring one up.

But the problem statement is very clear: We want to write specific generic functions, which are currently impossible to write.

[changkun]

"We want to be able to instantiate type Set[K comparable] … using reflect.Type" is a precise and unambiguous problem-statement. It stands in for a wider range of problems, e.g. "we want to be able to write a maps.Keys function usable with a map[reflect.Type]T". It is not a solution, it is a problem. Specifically, a problem about particular pieces of code, which are currently impossible to write.

That particular problem is addressed by #51338 (after embedding comparable in reflect.Type) and it's addressed by this proposal, by allowing type parameters interface types to implement comparable. There might be other solutions as well, feel free to bring one up.

Still, I have the feeling that you maintained in the mindset that type set and interfaces are the same. As the CL attempt to clarify: interface can be used to define a type set. But there are type set that cannot be written or implemented using interface, such as comparable.

If we want to solve a particular problem to instantiate type Set[K comparable] … using reflect.Type, it is better to clarify that the problem is:

proposal: spec: add a predeclared type set magicset

so that we can type Set[K magicset] ... and reflect.Type is an element of the type set magicset.

But the problem statement is very clear: We want to write specific generic functions, which are currently impossible to write.

Of course there are so many generic function we want to write and currently impossible to write. But why mix up with the comparable?

[atdiar]

If you have questions about how a specific piece of code would behave under this proposal, or how a specific piece of code could be written, I feel more confident that I could answer. Personally, as I said, I think it detracts from the discussion to talk about wording (but, if someone else thinks differently, they might well try to take a stab at it, of course).

I'm still asking because without proper definitions, we don't know what we are talking about.

So under the proposed, updated, comparable,

type M struct{
   Name string
   Map map[string] interface{}
} 
type Set[T comparable]... 

How is it decided that M cannot be a value for the type argument?

Do we still use typeset inclusion?

[changkun]

This is a joke: maybe we should revisit the previous abandoned contract design. Now we know that there is a clear difference between what is a contract and what is an interface. Because interface can implement a contract, but a contract is a contract.

[Merovius]

If we want to solve a particular problem to instantiate type Set[K comparable] … using reflect.Type, it is better to clarify that the problem is:

proposal: spec: add a predeclared type set magicset

That might be a solution to the problem. Feel free to file such a proposal. I disagree that it is better to say that is the problem. The problem is "we can't instantiate type Set[K comparable] … using reflect.Type" as an example of a broader problem of using interface types in generic code which needs to do comparisons.

[Merovius]

@atdiar

How is it decided that M cannot be a value for the type argument?

The spec defines which types are comparable. Map types are categorically not comparible, so neither are struct types with map fields. This proposal only suggests changing whether or not interface types do or do not implement comparable, it does not talk about map types. So your example seems irrelevant to this discussion.

[changkun]

I disagree that it is better to say that is the problem. The problem is "we can't instantiate type Set[K comparable] … using reflect.Type" as an example of a broader problem of using interface types in generic code which needs to do comparisons.

Maybe. But that's not a strong enough argument to complicate the definition comparable type set. Again, the problem is:

"we can't instantiate type Set[K someconstraint] … using reflect.Type, someconstraint maybe named as comparable or different. If named as comparable, then we have to change comparable"

not

"we can't instantiate type Set[K comparable] … using reflect.Type"

[atdiar]

@atdiar

How is it decided that M cannot be a value for the type argument?

The spec defines which types are comparable. Map types are categorically not comparible, so neither are struct types with map fields. This proposal only suggests changing whether or not interface types do or do not implement comparable, it does not talk about map types. So your example seems irrelevant to this discussion.

Just follow me for now. By the spec definition, M also implements comparable since it implements any and any is implementing comparableso what gives?

Should we use typeset inclusion to constrain type parameters or is there now something else we use?

[Merovius]

@atdiar FWIW the proposal is to strike the "non-interface" and "is not an interface type" from the section about comparable. I disagree that with that change, M would implement comparable, as it is not an interface type and does not support == and !=.

But again, that doesn't matter right now. We need to decide if we want to do this. We can always figure out how to word it, after we decided that. We can always fix ambiguities and conflicts, once we actually know how we want the language to behave. We can find words to describe whatever semantics we want. We are doing that all the time. It's just not a problem.

[beoran]

@changkun I think the spec changes you propose contain some unneeded changes as well. We came from contracts to interfaces to interfaces as type sets, I don't think we can go back now easily. The only change we need is this one:

The predeclared identifier comparable is a type set that denotes the set of all types that are comparable (this "comparable" refers to the Go 1's definition of types that are comparable).

[beoran]

@Merovius , @atdiar what are you going on about? You can agree with this proposal or oppose it but it seems besides the point. This proposal is to make the generic comparable and the pre generic comparable identical, for simplicity. It will have the benefit of making generics much easier to reason about.

[atdiar]

@atdiar FWIW the proposal is to strike the "non-interface" and "is not an interface type" from the section about comparable. I disagree that with that change, M would implement comparable, as it is not an interface type and does not support == and !=.

But again, that doesn't matter right now. We need to decide if we want to do this. We can always figure out how to word it, after we decided that. We can always fix ambiguities and conflicts, once we actually know how we want the language to behave. We can find words to describe whatever semantics we want. We are doing that all the time. It's just not a problem.

I disagree. We can't sweep everything under a rug. There are moving pieces and changing one of them may impact everything else.

You asserted that this change would also mean that interface types are part of comparable typeset.
That's problematic.

The spec clearly says that:

Implementing an interface
A type T implements an interface I if

T is not an interface and is an element of the type set of I; or
T is an interface and the type set of T is a subset of the type set of I.
A value of type T implements an interface if T implements the interface.

With the proposed change, M would therefore be a member of comparable typeset. (while also not being comparable by the spec definition)
So typesets would not be constraining anymore. That would be a failure of typeset as way toward bounded quantification.

I am merely asking, how do you propose to resolve this incongruency?

I have an idea that I have already mentioned in other issues. But that seems to have flown over people's head too.
In short, the proposed change can't work if comparable is an interface. We would need to extend the concept of constraint to be a superset of constraint interfaces.

So we either keep comparable as it is and we add something else, or we change comparable but it requires more than just what is in this proposal.

@beoran there is an issue with this proposal and I am trying to explain why I think so. The end goal may still be legible.

[Merovius]

@beoran I understand that. FWIW it was my first suggestion when the problem came up as well.

[DmitriyMV]

@Merovius

any (as a type argument) can instantiate comparable (rule v, observation 1)

Can you provide a code sample to describe this? I'm not sure I understand it correctly.

[griesemer]

@Merovius Right now we say that an operation (say +) on a type parameter is permitted if all types in the type parameter's type set support the operation. But if a type set of a type parameter contains an interface, the type parameter cannot have any operations because ordinary interfaces don't have operations (ignoring ==). I assume this is why you say "basic interfaces would always be in their own type set, whereas interfaces with type elements generally would not"?

Do I understand that correctly?

[jimmyfrasche]

Doesn't that fall out of X not being in typeset(X) given something like type X interface { A | B }?

[griesemer]

Here's an attempt at a summary, slightly more compact, written down for my own understanding:

1. Terminology
   a) uppercase T, I, P stand for a concrete, interface, or type parameter type respectively
   b) lowercase t, i, p stand for variables of type T, I, P respectively

2. Typesets
   a) typeset(T) = {T}
   b) typeset(I): defined like in the Go spec but if I is a basic interface (no type elements), then typeset(I) also contains all interface types that implement I (i.e., have at least the same methods as I) [corrected].
   c) typeset(P) = typeset(I) with P declared as [P I]
   d) typeset(x) = typeset(type(x)) with x one of t, i, p

3. Assignment
   a) x is assignable to i if typeset(x) ⊆ typeset(i)

4. Instantiation
   a) T instantiates P if T ∈ typeset(P)
   b) I instantiates P if I ∈ typeset(P)
   c) P1 instantiates P2 if typeset(P1) ⊆ typeset(P2)

The differences between this and what we have now are:

• the typeset of basic interfaces also contain all interfaces implementing those basic interfaces
• instantiation with a non-type parameter uses type inclusion, not typeset inclusion

Do I have this correctly?

[griesemer]

@jimmyfrasche

Doesn't that fall out of X not being in typeset(X) given something like type X interface { A | B }?

I suppose so, but I didn't see this written down. Is it written down somewhere (besides in the summary I just wrote)?

[Merovius]

@griesemer

Here's an attempt at a summary, slightly more compact, written down for my own understanding: […] Do I have this correctly?

Yes, I think so.

I suppose so, but I didn't see this written down. Is it written down somewhere (besides in the summary I just wrote)?

As part of the discussion, e.g. this comment. I wasn't explicit about it, but it's a consequence of the typeSet definition, which would AFAICT be the same we already use (with the exception of the "non-interface" parts).

[bcmills]

@griesemer

b) typeset(I): defined like in the Go spec but if I is a basic interface (no type elements), then typeset(I) also contains I

I think typeset(I) needs to include all of the interface types that implement I, not just I itself.
(That is: if a type parameter P is bounded by error, then it should be possible to instantiate P with the interface type net.Error, and thus net.Error should be in the typeset of error.)

Otherwise the instantiation rule doesn't work out.

[Merovius]

Good point. This is BTW an issue with the spec right now:

The type set of a method specification is the set of types whose method sets include that method.

This would include interfaces in type sets, which we tried to leave out by construction. So, currently there should be a "non-interface" added here. i.e. making that work seems to be a pretty natural consequence of defining type sets based on their elements - it has to be actively excluded, not to be the case.

[griesemer]

This was fixed several weeks ago. You're not looking at the spec at tip:

The type set of a method specification is the set of all non-interface types whose method sets include that method.

[bcmills]

@griesemer

I've been thinking about the rules in #52509 (comment) through the lens of #52624.

If we treat comparable as a run-time interface type, then we also need to define its semantics for type-assertions.

For this proposal, I believe the rule is (roughly):

5. Assertability
   a) x asserts to i if type(x) ⊆ typeset(i)

That is, in the program:

type SemiComparable struct { N int, I interface{} }
…
	s := SemiComparable{ N: 42, I: func() {} }
	var a any = s
	c, ok := a.(comparable)  // c = s; ok = true
	_ = c == s

the program would compile successfully, the type-assertion would succeed, and the comparison would fail at run-time.

[Merovius]

I think the rule is "x.(I) succeeds if x is not nil and T∈typeSet(I), where T is the dynamic type of x". Maybe you meant type(x) to be the dynamic type of x and meant typeSet(type(x)) ⊆ typeSet(I) in which case that means the same. But just to be explicit.

[Merovius]

@DmitriyMV

any (as a type argument) can instantiate comparable (rule v, observation 1)

Can you provide a code sample to describe this? I'm not sure I understand it correctly.

It means this compiles and works (which is good, as that's the reason for this proposal):

type Set[K comparable] map[K]struct{}

func main() {
    s := make(Set[any]) // instantiate `Set` using `any`. any ∈ typeSet(comparable), so this is allowed by rule v.
}

[gopherbot]

Change https://go.dev/cl/444635 mentions this issue: go/types, types2: implement alternative comparable semantics

[gopherbot]

Change https://go.dev/cl/444636 mentions this issue: cmd/compile: add support for alternative comparable semantics

[griesemer]

The 2 CLs above essentially get us back to before #50646 was addressed (by strictly implementing the typeset rules), and re-introduce the "inconsistency" that existed at that time. Specifically, an ordinary interface satisfies the comparable constraint. I believe that's the essence of this proposal.

The CLs allow us to experiment with this approach.

[griesemer]

I just posted #56548 which in essence is this proposal, but also includes the precise spec change and a discussion. @zephyrtronium, please comment as you see fit (and/or perhaps close this proposal, if you're so inclined). Thanks.

[zephyrtronium]

I'll close this in favor of #56548. If that proposal doesn't work out, this one can be reopened.

[zephyrtronium]

A note for future reference. I started sketching a proof that #52509 (comment) and the current language of #56548 allow for the same assignments and instantiations, and I found a surprise.

After some simplification, the rule for assignability of values x of concrete type T to variables of parameter type P reads as "for all types U in the type set of P, x is assignable to U." Say P is constrained by the interface I. By @Merovius's rules, the type set of P contains not only I but every interface with at least the methods of I, which means in particular that the type set of P contains mutually exclusive interfaces. For any given interface type U in P, T must be a member of the type set of U for x to be assignable to U. Since the type set of P contains mutually exclusive interfaces, there can be no T assignable to all types in the type set of P. So, it seems we cannot assign any value of any concrete type to any variable of parameter type.

It seems like what #52509 (comment) wants for type parameters is something like the assignable closure. A concrete type T needs to be a member of cl(P), an interface type I needs to be a subset of cl(P) (which is a contradiction, since I contains interface types! But that is what we want anyway, otherwise we could write func Foo[P any](x any) { _ P = x }), and a type parameter P2 needs to have cl(P2) a subset of cl(P). I believe cl(P) comes out to "the set of all non-interface types assignable to P." Seems like we've come full circle.

Similar to one of the notes in #52509 (comment), I do believe that defining the assignable closure for concrete types means that assignability is always exactly the subset relation between closures. That might make it easier to formalize the rules for unnamed types, directional channels, and so on.

[Merovius]

the rule for assignability of values x of concrete type T to variables of parameter type P

I don't think I wrote down a rule for that. It also seems a rule of dubious utility. I think that's what you essentially showed. We might be able to write a rule allowing this, but it would require P to mention a list of concrete types, which makes the rest of your argument collapse.

There is a rule for a concrete type instantiating a type parameter, but that rule uses ∈ and again doesn't seem to fit your argument.

What am I missing? What specific rule are you referring to (they are numbered)?

[zephyrtronium]

That's true. I was so focused on resolving the contradiction that I didn't think about whether it's correct to do so, and indeed, we would be able to write func Foo[P any]() { _ P = struct{}{} } if so. Funny that I noticed that for interface assignments, but not for concrete types. 🙂