spec: allow basic interface types to instantiate comparable type parameters #56548

griesemer · 2022-11-03T16:47:37Z

TL;DR

This is a restatement of proposal #52509 by @zephyrtronium. That issue has collected a lot of comments; starting anew will make it easier for readers to follow along again. The primary additional contributions in this issue are the formulation of the exact spec changes, a corresponding new API for go/types, and a discussion of these changes in the context of a future Go without the current implementation restrictions on interfaces. As a result, this issue is long, but the actually proposed change is small.

Background

The Go 1.18 release introduced the predeclared identifier comparable which denotes the set of all non-interface types that are comparable. More precisely, it is the set of (non-interface) types for which == and != are defined and for which these operations are guaranteed to not panic.

The types in the comparable type set do not correspond to the types of comparable operands: for instance, struct{ f any } is comparable but applying == on the field f may panic.

For clarity, in the following we use the term strictly comparable for the types in comparable, and spec-comparable for types of comparable operands. Strictly comparable types are spec-comparable, but not the other way around. Types that are not spec-comparable are simply not comparable.

Because in Go 1.18 and Go 1.19 constraint satisfaction means interface implementation, not all spec-comparable types satisfy the comparable constraint. The generic map type

type mymap[K comparable, V any] map[K]V

cannot be instantiated with struct{ f any } for K, but the built-in map type permits that. This is a major handicap for the design of generic data structures. See #51257 for another example.

Over the course of this year, many ideas have been proposed to address this problem, while trying to preserve the rule that constraint satisfaction and interface implementation remain the same. Here's a (possibly incomplete) list of proposals for reference: #51338, #52474, #52531, #52614, #52624, #53734.

If we want any to satisfy comparable, then constraint satisfaction can't be the same as interface implementation. A non-comparable type T (say []int) implements any, but T does not implement comparable (T is not in comparable's type set). Therefore any cannot possibly implement comparable (the implements relation is transitive - we cannot change that). So if we want any to satisfy the comparable constraint, then constraint satisfaction can't be the same as interface implementation.

A pre-Go1.18 implementation of the compiler did not treat interface implementation and constraint satisfaction the same, which led to initial confusion because of the resulting inconsistency (see #50646). Eventually the inconsistency was considered an implementation bug (in hindsight this was done without enough consideration of all the implications). With more experience it appears that this inconsistency made it easier to use generic Go with commonly used Go types.

@zephyrtronium's #52509 and this issue propose that we go back to this pre-Go1.18 implementation of constraint satisfaction.

Proposal

We change the spec to use a different rule for constraint satisfaction than for interface implementation: we want spec-comparable types to satisfy comparable; i.e., we want to be able to use any type for which == is defined even if it may not be strictly comparable.

Specifically, in the language spec section on Instantiations, we propose to change the 2nd rule from (old):

After substitution, each type argument must implement the constraint (instantiated, if necessary) of the corresponding type parameter. Otherwise instantiation fails.

to (new):

After substitution, each type argument must satisfy the constraint (instantiated, if necessary) of the corresponding type parameter. Otherwise instantiation fails.

We also add a new paragraph defining what "satisfy" means:

A type T satisfies a constraint interface C if

T implements C; or

C can be written in the form interface{ comparable; E }, where E is a basic interface and T is comparable and implements E.

With this change, constraint satisfaction matches interface implementation but also contains an exception for spec-comparable types. This exception permits the use of interfaces as type arguments which require strict comparability.

This is the entire proposal.

Observations

The proposed change expands the set of types that satisfy a constraint, therefore no existing programs are invalidated and the proposal is fully backward-compatible. See the section on Implementation below for when the feature becomes available.
The spec has various implementation restrictions: 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. Because of these restrictions, if the type argument T is a (non-type parameter) interface, it must be a basic interface. Thus, we can ignore the case of type-constrained interfaces (such as interface{ ~[]int }) which can only hold non-comparable types. For the same reason, if T is a non-interface type with an interface field (such as struct{ f F } where F is an interface), F must be a basic interface. In other words, we don't need to complicate the rules to explicitly disallow such types for T: any interface that is or appears in a (non-type parameter) type argument must be a basic interface and therefore is spec-comparable.
The spec has additional implementation restrictions in place: comparable and interfaces containing methods may not appear as terms in a union (with more than one term). Because of these restrictions, if comparable appears in an interface (or an embedded element), it can be "factored out to the top"; the same is true for methods. More precisely, constraint interfaces can always be written in one of two forms: interface{ comparable; E } or interface{ U; E }, where E stands for all the interface's methods (if any), and U denotes a union of non-interface types (if any). (An interface of the form interface{ comparable; U; E } can always be reduced to the form interface{ U'; E } by eliminating all non-strictly-comparable terms from U).
For interface{ U; E } constraints, constraint satisfaction is the same as interface implementation: nothing changes. For a type T to satisfy the constraint, it must be in the union and satisfy all the methods, if any.
For interface{ comparable; E } constraints, constraint satisfaction is looser: we still expect a type argument T to implement all the methods E, but we allow any T which is spec-comparable, even if it is not strictly comparable. This is not statically type-safe and must be remedied with a run-time check for ==.
Because the new rule invalidates static type safety, the definition of strictly comparable is not quite correct anymore: == on an operand of a strictly comparable type parameter type may in fact panic at run-time. To be able to separate the various kinds of comparability, strictly comparable now more precisely denotes the set of types for which == and != are defined and for which these operations won't panic if type safety was never broken through the instantiation of a (strictly) comparable type parameter with a spec-comparable type argument.
If a type parameter P is spec-comparable, it is always strictly comparable (but see the previous observation). Therefore, if a type parameter is used as a type argument for a constraint of the form interface{ comparable; E }, the rule that P must "only" be spec-comparable doesn't weaken any static type guarantees because P will be strictly comparable.
The pre-Go 1.18 implementation, before the inconsistency documented in spec: document/explain which interfaces implement comparable #50646 was reported, matched the proposed rules.

Eventually we may want to remove the existing implementation restrictions. This will also require a generalization of the rule for constraint satisfaction. To ensure backward compatibility, the proposed rule here should match a future, more general rule adjusted for the current implementation restrictions. But at the very least, the proposed rule should not permit more programs now than might be permitted with a more general rule for constraint satisfaction. See the appendix for an attempt at such a generalization.

Examples

Currently, any does not implement the comparable constraint. With the proposed change any will be permitted as type argument for comparable: comparable can be written as interface{ comparable; E } and thus the new rule applies, and any is spec-comparable and implements E (where E is the empty interface in this case).

Currently, the type parameter P in the type parameter list

[P interface{ comparable; fmt.Stringer }]

cannot be instantiated with the type S

type S struct {
	data any
}

func (S) String() string

because S is not strictly comparable. With the proposed change, S must only be spec-comparable (which it is) and implement fmt.Stringer (which it does).

More examples

type mymap[K comparable, V any] map[K]V

func _[P any, Q comparable]() {
	var (
		_ map[func()]string        // invalid with current and new rules: func() is not comparable
		_ map[struct{ f P }]string // invalid with current and new rules: P is not comparable
		_ map[struct{ f Q }]string // valid: key type is strictly comparable

		_ mymap[any, string]                // currently invalid, valid with new rules: any supports ==
		_ mymap[struct{ f any }, string]    // currently invalid, valid with new rules: type of f supports ==
		_ mymap[struct{ f func() }, string] // invalid with current and new rules: f is not comparable
		_ mymap[struct{ f int }, string]    // valid: key type is strictly comparable
		_ mymap[struct{ f P }, string]      // invalid with current and new rules: P is not comparable
		_ mymap[struct{ f Q }, string]      // valid: key type is strictly comparable
	)
}

Implementation

The proposal requires minor changes to the typechecker:

We have already implemented this alternative semantics at tip so that we can experiment. The new compiler flag -altcomparable enables the new behavior (disabled by default):

go tool compile -altcomparable <file.go>      // applied to a single file
go build -gcflags=-altcomparable <pkg path>   // applied to a package
etc.

If the proposal is accepted for Go version 1.nn, we will replace this flag with a version check that enables the new behavior starting with Go 1.nn.

Clients of go/types need to be able to check for constraint satisfaction, which is now slightly different from interface implementation. We cannot add a flag to the existing types.Implements function without breaking backward-compatibility. Instead, we propose to add the following exported function:

// Satisfies reports whether type V satisfies the constraint interface T.
//
// The behavior of Satisfies is unspecified if V is Typ[Invalid] or an uninstantiated
// generic type.
func Satisfies(V Type, T *Interface) bool

We may also want to provide a variant of types.Comparable that implements the notion of strict comparability. We can wait with this until a clear need arises.

All these changes are trivial (the internal implementations exist, they just need to be exported).

If this proposal is accepted in time, it could become effective with the Go 1.20 release.

Related spec issues

The current definition of the type set of the predeclared type comparable is incorrect in the spec. The definition is as follows:

The predeclared interface type comparable denotes the set of all non-interface types that are comparable. Specifically, a type T implements comparable if:

T is not an interface type and T supports the operations == and !=; or

T is an interface type and each type in T's type set implements comparable.

The first rule (T supports the operations == and !=) also includes types (such as structs) which may not be strictly comparable (see the structs used in the examples above). The rule needs to be amended to exclude types for which == may panic.

The definition of comparable operands in the spec is missing a dedicated rule for operands of type parameter type. Without it, type parameters (whose underlying types are their constraint interfaces) fall into the category of spec-comparable interface values. This is incorrect. A type parameter-specific rule needs to be added to this section.

Both these spec corrections should be made irrespective of whether this proposal is accepted or not.

Appendix

In a hypothetical future version of Go ("FutureGo") where generalized interfaces may be used as ordinary types, the constraint satisfaction rules must be suitably extended and expressed in terms of type sets. @ianlancetaylor proposes the following FutureGo rules:

Given a (constraint) interface C, we define two type sets S1 and S2 as follows:

S1 is the type set of C computed in the usual way, except that wherever comparable appears in C
it is treated as the set of all (spec-)comparable types (not just the strictly comparable types); and

S2 is the type set of C computed in the usual way, except that wherever comparable appears in C
it is treated as the set of all types, any.

Given these special type sets S1 and S2, we can define general constraint satisfaction as follows:

A type T satisfies a constraint interface C if

T is not an interface type, and T is an element of type set S1; or

T is a (non-type parameter) interface type, the type set of T is a subset of the type set S2,
and the intersection of the type set of T with the type set S1 is not empty; or

T is a type parameter and T implements C.

(The case for type parameters can be folded into the case of non-interface types, but for the following discussion it is clearer to handle it separately.)

If T is not an interface (or type parameter) type, it is not hard to see why the respective sub-rule makes sense: instead of only accepting strictly comparable types for comparable, the use of the type set S1 permits any spec-comparable type.

If T is an interface type, we also want to accept it as a type argument for comparable: more precisely, any interface type, irrespective of its type set, supports == and thus is spec-comparable (we could say that non-basic interfaces don't support == by default, but that's an separate discussion). Effectively this means that comparable is the same as any in this case, hence the type set S2. However, we (probably) want to exclude interface types with type sets for which we can prove that == can't possibly succeed. For instance, interface{ ~[]int } is spec-comparable (all interfaces support ==, but see the comment on that above), but its type set only contains non-comparable types: comparing operands of type interface{ ~[]int } will always panic. The intersection of the type set of such interfaces with the type set S1 will be empty (if it were not empty, the interface would contain at least one spec-comparable type and so == might always happen to succeed in a concrete application). This explains the second part of the rule for interfaces.

Finally, if T is a type parameter, nothing changes and we can simply ignore this case below.

To make sure we remain forward-compatible with FutureGo, i.e., that these generalized constraint satisfaction rules do not restrict our current, limited proposal, we need to show that our current proposal doesn't permit more types for a constraint than the FutureGo rules.

We can do this by applying the current implementation restrictions to the FutureGo constraint satisfaction rules. With those restrictions in place, from the Observations section we know that constraint interfaces can appear in only two (canonical) forms:

a) interface{ comparable; E }; or
b) interface{ U; E }

where E stands for all the methods in the constraint (if any), and U denotes a union of non-interface types (if any). Therefore, the respective type set S1 is either

S1a which is the type set of interface{ comparable; E } with comparable denoting all spec-comparable types; or
S1b which is the type set of interface{ U; E } (unchanged).

Similarly, the type set S2 is either

S2a which is the type set of interface{ E }; or
S2b which is the type set of interface{ U; E } (unchanged).

Now we can look at the type argument T and how the generalized rules apply:

If T is not an interface type, per the generalized rules, T must be an element of S1. Therefore, T must either be an element of S1a, or S1b. If the former is true, T must be spec-comparable and implement the methods E - this corresponds to the our proposed exception for interface satisfaction. If the latter is true, T is simply an element of the type set of the constraint, which means T implements the constraint. This corresponds to the non-exceptional part of the proposed rule for constraint satisfaction.

If T is a (non-type parameter) interface type, with the implementation restrictions in place, T must be a basic interface. Per the generalized rules, the type set of T must be a subset of S2a and the intersection of T's type set and S1a must not be empty, or the type set of T must be a subset of S2b and the intersection of T's type set and S1b must not be empty. If the former is true, T implements the methods E, and because T is a basic interface it is also spec-comparable. This corresponds to the proposed exception for constraint satisfaction. If the latter is true, T simply implements the constraint, which again corresponds to the non-exceptional part of the proposed rule for constraint satisfaction.

In summary, if we apply the current implementation restrictions to FutureGo, the FutureFo constraint satisfaction rules reduce to the rules proposed in this issue. This provides some insurance that the proposed rules won't cause problems in FutureGo.

The text was updated successfully, but these errors were encountered:

zephyrtronium · 2022-11-03T18:03:31Z

A type T satisfies a constraint interface C if

T implements C; or

C can be written in the form interface{ comparable; E }, where E is a basic interface and T is comparable and implements E.

With this change, constraint satisfaction matches interface implementation but also contains an exception for spec-comparable types. This exception permits the use of interfaces as type arguments which require strict comparability.

This seems like a small and clever rule with intentionally broad consequences. I'm not sure why this approach is preferable to, in particular, #52509 (comment) by @Merovius. Adding the "satisfies" relation seems to be helpful for the go/types API, but we can do that and also have a list of small explicit rules rather than a very big implicit one. Perhaps that's just my reading.

griesemer · 2022-11-03T18:38:23Z

The approach suggested by @Merovius changes the meaning of type sets to include interfaces, which seems like a pretty big change. The end result may still be the same, but I haven't tried to prove that in any way.

If we want an interface, say any to satisfy comparable - which the comparable issues are all about - constraint satisfaction simply cannot be the same as interface implementation. Thus, the simplest change I can think of is to separate the two and introduce an exception for exactly the cases which we want to cover. Unless I'm overlooking something (which is entirely possible), it seems that the proposed rule does exactly what developers want: to be able to use a spec-comparable type where we request a comparable type argument, similar to what we always could do with map keys.

nightlyone · 2022-11-03T20:11:35Z

Since after implementing this comparable is equivalent to any since any will satisfy the comparable constraint, I don't understand why comparable is needed. What can we model with a comparable that will include any that we can't model with any alone?

There may be advantages when stenciling out the actual usages, but type safety is not improved over just using any.

Also when following this proposal one again cannot model comparable types without special support for equality that comparable enables right now. I don't see a plan for regaining this capability in in the proposal.

griesemer · 2022-11-03T20:38:02Z

comparable is not the same as any with this proposal nor do we state that anywhere. It's not possible to use a non-comparable type (such as []int) as type argument for a type parameter constrained by comparable - yet if the constraint were any, it would be possible. What this proposal does is carving out just the right (I think) exception to permit types that in Go are considered comparable as type arguments constrained by comparable, even if those types are not strictly comparable (== may panic). We retain all the static safety elsewhere. Static type safety is definitely stronger than with any.

I do not understand what you mean by your second paragraph. Can you provide an example of the capability you're missing?

Finally, you may want to try and play with the actual implementation of this feature which is available to you at tip (see the Implementation section of the proposal). Perhaps that helps clarifying the impact this would have on your code.

apparentlymart · 2022-11-04T00:27:40Z

Thanks for sharing this proposal. It broadly makes sense to me and I believe it will allow me to write the programs I described wanting to write in some of the previous proposal discussions (which I will not repeat here).

I do have a clarifying question, though:

The proposed text constrains E in interface{ comparable; E } to be a Basic interface. The spec currently defines that as an interface whose body consists only of methods.

The following section of the specification defines "Embedded interfaces" without describing the interaction between "Basic interface" and "Embedded interface". Is it true to say that an interface which embeds a basic interface is itself a basic interface as long as it otherwise meets the definition of a basic interface?

Concretely, is B in the following example a "basic interface" for the sake of satisfying the proposed new rule?

type A interface {
    Foo()
}

type B interface {
    A
    Bar()
}

griesemer · 2022-11-04T00:36:45Z

Yes, B in your example would be basic interface. Per the spec:

Interfaces whose type sets can be defined entirely by a list of methods are called basic interfaces.

In other words, we mean all interfaces that can be written in the form interface{ comparable; M1; M2; ... } (where the Mi's are methods) after "inlining" or "flattening" of any embeddings.

apparentlymart · 2022-11-04T01:12:40Z

Ahh yes, thank you for clarifying that. I clumsily read "can be defined entirely by" as "are defined entirely by".

atdiar · 2022-11-04T14:14:32Z

Thank you for the detailed proposal.
Sorry in advance for the long-winded comment. I think this proposal is a step toward a solution although there are a few things that I think differ from the conclusions of #52509 and #53734 and these differences may be important.
(also, note that #53734 and its predecessor suggests to differentiate between interface implementation and constraint satisfaction)

To be honest, I've found some of the explanations a bit hard to follow personally (which might be from my own limitations).
I think that the issue is that:

we have two definitions for comparability : spec comparable and strictly comparable (I have myself changed my mind on this and think it could be an unnecessary distinction)
constraint satisfaction seems to depend partially on interface implementation (a bit confusing to me, I believe that should be the opposite if anything)
comparable still seems to be treated as a special interface (which seems to be confusing others apparently)
FutureGo would require two kinds of type sets? (maybe I misunderstood)
maps in regular code and in generic code do not behave the same wrt acceptable map key types

(5) is about struct types whose fields may be interfaces. https://go.dev/play/p/JkAcqvXlirF
In current Go, these types are accepted as map keys even though they might trigger a runtime panic. So they can be used in Set datastructures that are built upon maps. I think this was one use-case that was mentioned by people.
They are indeed satisfying the comparable constraint if we define such constraint as the proposition: has the comparison operators == and !=.

That however does not mean that these types would implement a potential future comparable interface. Admittedly, that part has been underdiscussed but seems that any composite type would implement comparable if and only if every part of that type implements comparable.
For a struct, that would be every field. For an array, the type argument to the array constructor should implement comparable.

Following this, we would not require a distinction between spec and strictly comparable. That takes care of issue 1 and issue 5 as the distinction would merely be between implementing and satisfying.

But now, what about 2,3,4 ? What is even implementing an interface and satisfying a constraint, why does it differ? How to build a simple mental model?

That's where I think there has been attempts to establish the (long) list of requirements for each in the spec but I think it shows that the mental model may need to be clarified so that it is made simpler and more obvious.
If we take a step back and think about it (I will probably be paraphrasing #53734):

A. An interface type defines the set of constraints that allow to group types together. It defines thus a set called a type set.
B. Any non-interface type is also an interface (conceptually) and defines a type set that is a singleton.
C. comparable is just an interface defined by the set of constraints { has == and != operators}
D. A type U satisfies a constraint interface V iff U belongs to the type set of V by definition
E. An interface I implements an interface J iff we can show that all types that satisfy I satisfy J. (i.e. the type set defined by I is a subset of the type set defined by J i.e. the set of constraints defining J is a subset of the set of constraints defining I)

So as can be seen (in A,D,E), the definition of constraint satisfaction is the basis for a definition of interface implementation instead of the reverse.
We have only one kind of type sets and one kind of comparability. That's simpler.

Also because assignment to an interface value must be true for all satisfying typed values, it is by definition using interface implementation as a requirement. In the case of comparable, it would correspond to what is defined as strict comparability in the current proposal.

Constraint statisfaction is what is used by type parameters, so

struct{ 
  int
  ast.Node
}

should still be able to instantiate generic map keys, just like in normal Go code, since it has the comparison operators.

Now on the question of whether interface types belong to type sets or not?

... it depends.
We just need to apply the constraint rules rulesto interface types.
Obviously that means that interface types may belong to type sets. Sometimes they would not, depending on the type set. e.g. interface{ int | string}
Just like regular types.

Another question is whether all interface types should satisfy comparable ?

As mentioned in this proposal, it might seem less clear for interface{ ~[]int} .
I would still tend to say yes but it is perhaps not mandatory. Having these operators doesn't seem to rely on type sets as seen with any. Quite the opposite, the availability of these operators determine the type set instead.
In any case, it should be evident that it does not implement comparable, however. There is a difference between a type and the elements of the set it denotes.

griesemer · 2022-11-04T16:07:04Z

I believe the mental model needed here remains very simple: Constraint satisfaction is the same as interface implementation (nothing changes), but we introduce an exception so that Go's (spec-) comparable types can also be used where (strictly) comparable type arguments are required.

That is all, and that is exactly what users are asking for. The reason we need this is that historically, Go was not statically type-safe with respect to ==: the operation can panic in some cases. But when writing generic code, we want to preserve type-safety as much as possible (which is why comparable is not the same as spec-comparable), this is simply something users don't want to give up. These two goals are conflicting, and the only way to bridge the gap is through an exception. Which is what we propose.

Now, to answer your questions:

We have always had (spec-)comparable and we cannot change that or it would break backward-compatibility. With Go 1.18 we introduced comparable which stands for strictly comparable types. We could make comparable the same as spec-comparable (a sort of late fix for a "bug" in the generics design), one could even get rid of comparable (make it mean any), see e.g. proposal: type parameters are comparable unless they exclude comparable types #52614. But this and similar ideas were vehemently rejected repeatedly. People want comparable to provide some guarantees, which is what we have now. Therefore comparable must be different from spec-comparable.
Constraint satisfaction depends mostly (not partially!) on interface implementation because we want to keep it that way. We just added an exception for spec-comparable types. That is the whole point of this proposal.
comparable is a special interface: it is predeclared because we don't have another mechanism in the language to denote strictly comparable types (and we don't want to invent one either, a predeclared identifier works fine). Again, if we accept 1), comparable must be different from spec-comparable.
FutureGo is a thought experiment. We want to make sure that this proposal holds up even if we were to remove the current implementation restrictions. Or, looking the other way, we want to make sure that we can remove the current implementation restrictions and not run into problems because of this proposal. To that effect, @ianlancetaylor has proposed a set of (plausible) rules for constraint satisfaction that we believe would work with such a future Go, and then we show that this proposal doesn't conflict with those hypothetical future rules. It is possible that these future rules can be expressed more clearly and concisely. All this is relevant here only insofar that it gives us some confidence that this proposal is reasonable. If it feels confusing to you, just ignore the appendix.
The built-in go map type behaves exactly the same in all cases: the key type must be spec-comparable. If you define your own generic map type with a key type parameter that is comparable, it also accepts spec-comparable types. With this proposal, your example type

struct{ 
  int
  ast.Node
}

can be used to instantiate a generic map key. Again, that is the goal of this proposal.

I very much agree with you that it would all be much simpler if there was only one type of comparability - and we have tried that before (again see #52614 and perhaps others). But users want stronger guarantees.

To summarize:

users want to express in generic code that comparable really means strictly comparable (but see the next point)
users still want to use any for a strictly comparable type parameter (and any is not strictly comparable)
this is an inherent conflict and requires an exception in the constraint satisfaction rules
this proposal provides exactly that exception without changing anything else

(Regarding your last two questions: a) should interfaces be parts of type sets, and b) should all interfaces satisfy comparable. For a): probably not - but we don't need to answer this question for this proposal. For b) the type interface{ ~[]int } cannot be used as an ordinary type, so the question is moot for that case. A type parameter constrained by this interface is and will not be (strictly) comparable, nor is it spec-comparable. This won't change and is I think what you'd expect.)

I recommend you play with the implementation available at tip. Setting the compiler flag -altcomparable will give you the proposed behavior. Thanks.

atdiar · 2022-11-04T16:23:47Z

@griesemer thanks for the reply. I realize that I misread the examples and made a mistake. As you correctly state, the struct example works. So that's one less issue.

Regarding comparable however, if we distinguish between interface implementation and constraint satisfaction, do we really still need to have two notions of comparability?
We should be able to keep compile-time safety (strict comparability) since it uses interface implementation and interface types would still satisfy the comparable constraint. Just not implement it.

Basically instantiation requires constraint satisfaction. Assignability requires interface implementation (which forces strict comparability) ?
Interface implementation being constraint satisfaction of the members of the type set of a type instead of constraint satisfaction of the type itself.

griesemer · 2022-11-04T17:58:17Z

We still need to be able to talk about the different kinds of comparability. What you are suggesting is that comparable types be the new "comparable" types. And then we have some other types (such as interfaces) for which == is defined.

I suppose we could talk about "types that support ==" instead of types that are comparable in the spec. That change would not be difficult. But it would require that we teach that "comparable types" now means types in the type set of comparable. Not to mention all the related documentation, books, API entry point names, etc. that would be affected but often cannot be changed.

It seems to me that might be even more confusing. In the spec and documentation it might be clearer to talk about "strictly comparable" types instead and leave established terminology alone.

We made a similar terminology change in the past: we used to refer to types declared in a type declaration as "named types". When we introduced alias declarations, the notion of a "named type" didn't make 100% sense anymore, because an alias declaration (e.g. type S = struct{}) introduces a name (such as S) for a type yet the type denoted by that name (struct{}) may not be a "named type". So "defined types" became the term for types formerly called "named types". We're still not fully recovered from that terminology change. With Go 1.18, we re-introduced the notion of a "named type" which is getting us mostly back to where we were. The lesson learned here is that we should not make changes to established terminology if there's other ways around it.

atdiar · 2022-11-04T21:11:37Z

Almost but not quite the change I had in mind. Perhaps I'm thinking wrongly though.

I would define comparable as comparable i.e. the constraint would determine the set of types that have the comparison operators.

Quoting the current spec on Comparison operators, The equality operators == and != apply to operands that are comparable.
So nothing would change here?

Interface types could be said to be comparable since they can be compared.(just means that interface types satisfy the comparable interface.)

The difference would simply be that not every comparable type would implement comparable.
Which has to be understood in terms of interface.
Interface implementation is basically: can every type that fits into one interface also fit into another interface?
It's a comparison of constraining power and as such, it becomes obvious that any does not implement comparable for instance.

With non-basic interfaces we have the opposite, interface{string | int} would implement itself as it denotes the same constraining power but the interface type does not satisfy the constraint it represents.

I think these are nuances that we might want to make clearer. constraint satisfaction seems really different from interface implementation.

That might even allow to future proof a potential FutureGo if all constraint interfaces are to be used as types.

griesemer · 2022-11-04T23:05:45Z

I think the proposal establishes that interface implementation and constraint satisfaction should be different. We can consider this part of the discussion as settled.

You are saying we should turn things 180 degrees around: let comparable be the set of all spec-comparable types, and then make sure that not every comparable type implements comparable.

I don't know how that can work. You state yourself, that "Interface implementation is basically: can every type that fits into one interface also fit into another interface?". That is set inclusion: An interface A implements an interface B if every type in A is also in B. Thus every type in comparable implements comparable.

Similarly, you say that any does not implement comparable - it would only satisfy comparable. Yet any is clearly comparable (== is defined) and therefore any is in the set of all comparable types. So it must implement comparable.

The only potential way I see how this could work is by changing the definition of interface implementation - it could not be based on set inclusion anymore, or the notion of type sets for interfaces would need to be adjusted. If it's possible I'd love to see that. Without a precise definition of the "nuance" you're alluding to it's difficult to assess your idea. There's not enough here to make progress.

atdiar · 2022-11-04T23:20:18Z

I think the proposal establishes that interface implementation and constraint satisfaction should be different. We can consider this part of the discussion as settled.

Yes!

You are saying we should turn things 180 degrees around: let comparable be the set of all spec-comparable types, and then make sure that not every comparable type implements comparable.

Yes, I think that many interfaces are comparable themselves as a type but the types that implement these interfaces are not necessarily comparable as well. In terms of type set inclusion i.e. interface implementation, we can just take the example of any.

I don't know how that can work. You state yourself, that "Interface implementation is basically: can every type that fits into one interface also fit into another interface?". That is set inclusion: An interface A implements an interface B if every type in A is also in B. Thus every type in comparable implements comparable.

Set inclusion would be set membership of every type in A. That is satisfaction of the constraints of B for each type in A.
Every type in comparable satisfies comparable rather.

Similarly, you say that any does not implement comparable - it would only satisfy comparable. Yet any is clearly comparable (== is defined) and therefore any is in the set of all comparable types.

I think:

Type set membership of a type would be constraint satisfaction.
Set inclusion of the type set of a given type would be interface implementation. (note set inclusion of the type set, not set inclusion of the type itself)

griesemer · 2022-11-05T00:11:42Z

Type set membership of a type would be constraint satisfaction.

Let me spell this out: A type T satisfies a constraint C if the type T is a member of the type set of C.

Set inclusion of the type set of a given type would be interface implementation.

An interface T implements an interface C if the type set of T is a subset (set inclusion) of the type set of C.

Is that what you are saying? If so, that would require that interfaces (e.g. any) be part of type sets (so that any can satisfy the constraint comparable). #52509 (comment) comes to mind but this sounds a bit different.

Is comparable (the type) in the type set of comparable? I think it would have to be because a comparable type should satisfy comparable:

func f[P comparable]() {
   f[P] // this should be legal
}

I need to think about this some more, but I am going to disengage from this specific conversation for now because it doesn't directly discuss the pros and cons of the proposal at hand (which suggests a very small localized change). It sounds like you are proposing a different idea altogether, which changes how type sets are computed, and that should be discussed elsewhere. Feel free to open a new proposal explaining in detail how your idea would work. Thanks.

atdiar · 2022-11-05T00:31:49Z

Yes, you got it right, interface types could/would now belong to type sets (as mentioned in #52509)

The advantage would be only one notion of comparability, comparable would be somewhat less magic an interface, and for a potential FutureGo, only one kind of type sets would need to be considered.
Would probably explain why constraint interfaces can in theory be used as regular interfaces as well, implementation-pending

No problem I will amend #53734 to try and specify things more accurately.

Thanks.

griesemer · 2022-11-05T00:44:46Z

Just one last comment: I'm not sure things would be less magic. Right now, an interface is never in a type set. Type sets exactly represent the very real concrete types that can be stored in an interface variable, the types in a type set correspond to the possible dynamic types at run-time. If interfaces become parts of type sets, type sets become an essentially mathematical construct with no direct correspondence to run-time types. Just something to keep in mind. Thanks.

rsc · 2022-11-09T19:15:17Z

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

atdiar · 2022-11-11T01:40:31Z

I have updated #53734 for a different take on this issue.

nobishino · 2022-11-14T13:24:22Z

Thank you for the detailed proposal. It seems very reasonable to have separate meanings for "implement" and "satisfy" a type constraint, given that we want any to satisfy the comparable constraint.

I have a question: it is not very clear to me when type-parameter type satisfies a constraint.

https://go.dev/play/p/RJQcw75YVnf

type mymap[T comparable] map[T]struct{}

func f[T comparable]() {
	_ = mymap[T]{}
}

For example, the above program successfully compiles in Go1.19, so this should successfully compile in this proposal.
How this should be explained in the new spec? Why does the type parameter type T satisfies comparable in the above code?

According to the description of the proposal,

A type T satisfies a constraint interface C if

T implements C; or

C can be written in the form interface{ comparable; E }, where E is a basic interface and T is comparable and implements E.

In Go1.18, we could assume that (after instantiation) the argument T implements C.
But I think that we can no longer assume that in this proposal.
So I'm wondering "When a type-parameter type T satisfies type constraint C?"

My guess is something like follows. Excuse me if this question is too detailed to discuss now.

type parameter T satisfies constraint C if and only if all types that satisfy T's constraint also satisfy C.

Merovius · 2022-11-14T13:54:37Z

@nobishino The second bullet point:

C can be written in the form interface{ comparable; E }, where E is a basic interface and T is comparable and implements E.

In your example, C can be written as interface{ comparable; any } and T is comparable and implements any.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

spec: allow basic interface types to instantiate comparable type parameters #56548

spec: allow basic interface types to instantiate comparable type parameters #56548

griesemer commented Nov 3, 2022

zephyrtronium commented Nov 3, 2022

griesemer commented Nov 3, 2022

nightlyone commented Nov 3, 2022

griesemer commented Nov 3, 2022 •

edited

apparentlymart commented Nov 4, 2022

griesemer commented Nov 4, 2022 •

edited

apparentlymart commented Nov 4, 2022

atdiar commented Nov 4, 2022 •

edited

griesemer commented Nov 4, 2022 •

edited

atdiar commented Nov 4, 2022 •

edited

griesemer commented Nov 4, 2022

atdiar commented Nov 4, 2022 •

edited

griesemer commented Nov 4, 2022

atdiar commented Nov 4, 2022 •

edited

griesemer commented Nov 5, 2022

atdiar commented Nov 5, 2022 •

edited

griesemer commented Nov 5, 2022

rsc commented Nov 9, 2022

atdiar commented Nov 11, 2022

nobishino commented Nov 14, 2022

Merovius commented Nov 14, 2022 •

edited

gopherbot commented Nov 30, 2022

gopherbot commented Dec 1, 2022

gopherbot commented Dec 1, 2022

go101 commented Dec 8, 2022 •

edited

atdiar commented Dec 8, 2022 •

edited

go101 commented Dec 8, 2022

ianlancetaylor commented Dec 9, 2022

gopherbot commented Dec 13, 2022

gopherbot commented Dec 13, 2022

griesemer commented Dec 14, 2022

spec: allow basic interface types to instantiate comparable type parameters #56548

spec: allow basic interface types to instantiate comparable type parameters #56548

Comments

griesemer commented Nov 3, 2022

TL;DR

Background

Proposal

Observations

Examples

More examples

Implementation

Related spec issues

Appendix

zephyrtronium commented Nov 3, 2022

griesemer commented Nov 3, 2022

nightlyone commented Nov 3, 2022

griesemer commented Nov 3, 2022 • edited

apparentlymart commented Nov 4, 2022

griesemer commented Nov 4, 2022 • edited

apparentlymart commented Nov 4, 2022

atdiar commented Nov 4, 2022 • edited

But now, what about 2,3,4 ? What is even implementing an interface and satisfying a constraint, why does it differ? How to build a simple mental model?

Now on the question of whether interface types belong to type sets or not?

Another question is whether all interface types should satisfy comparable ?

griesemer commented Nov 4, 2022 • edited

atdiar commented Nov 4, 2022 • edited

griesemer commented Nov 4, 2022

atdiar commented Nov 4, 2022 • edited

griesemer commented Nov 4, 2022

atdiar commented Nov 4, 2022 • edited

griesemer commented Nov 5, 2022

atdiar commented Nov 5, 2022 • edited

griesemer commented Nov 5, 2022

rsc commented Nov 9, 2022

atdiar commented Nov 11, 2022

nobishino commented Nov 14, 2022

Merovius commented Nov 14, 2022 • edited

gopherbot commented Nov 30, 2022

gopherbot commented Dec 1, 2022

gopherbot commented Dec 1, 2022

go101 commented Dec 8, 2022 • edited

atdiar commented Dec 8, 2022 • edited

go101 commented Dec 8, 2022

ianlancetaylor commented Dec 9, 2022

gopherbot commented Dec 13, 2022

gopherbot commented Dec 13, 2022

griesemer commented Dec 14, 2022

griesemer commented Nov 3, 2022 •

edited

griesemer commented Nov 4, 2022 •

edited

atdiar commented Nov 4, 2022 •

edited

griesemer commented Nov 4, 2022 •

edited

atdiar commented Nov 4, 2022 •

edited

atdiar commented Nov 4, 2022 •

edited

atdiar commented Nov 4, 2022 •

edited

atdiar commented Nov 5, 2022 •

edited

Merovius commented Nov 14, 2022 •

edited

go101 commented Dec 8, 2022 •

edited

atdiar commented Dec 8, 2022 •

edited