Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: spec: allow values of type comparable #52624

Open
bcmills opened this issue Apr 29, 2022 · 36 comments
Open

proposal: spec: allow values of type comparable #52624

bcmills opened this issue Apr 29, 2022 · 36 comments
Labels
generics Issue is related to generics Proposal Proposal-Hold
Milestone

Comments

@bcmills
Copy link
Member

bcmills commented Apr 29, 2022

Introduction

Since we're proposing comparable semantics, I'd like to throw this one into the ring.

This is a proposal for the approach mentioned in #51338 (comment). It is a possible alternative to proposals #52509 and #52614; please see those proposals for introduction and background.

Proposal

An interface type is comparable if its type-set includes at least one comparable type. Interfaces whose type-sets include only incomparable types — such as interface { func() | func() string } — are not comparable. (Comparability for all other types remains as it was defined in Go 1.18.)

Every comparable type implements the comparable interface. (Thus, comparable is itself comparable.) However, not every type that implements comparable is assignable to comparable interfaces (see below).

A variable of a parameter type is comparable only if all of the types that implement its constraint are comparable.

func eq1[T any](a, b T) bool {
	return a == b  // Compile error: type T is not necessarily comparable.
}

func eq2[T comparable](a, b T) bool {
	return a == b  // Ok, but may panic at run time if values are not comparable.
}

func eq3[T int | []byte](a, b T) bool {
	return a == b  // Compile error: type T is not necessarily comparable.
}

func eq4[T int | string](a, b T) bool {
	return a == b  // Ok; cannot panic at run time.
}

If T is an interface type that either is or embeds comparable, a variable of type T can hold only comparable run-time values.

  • An ordinary assignment of a value x to a variable of type T is allowed only if x is of a type whose values can always be compared without panicking, such as an integer type or an interface type that itself is or embeds comparable.

    • (Note: not every type in the type-set of T is necessarily assignable to T! Types that may panic — such as non-comparable interface types and structs with non-comparable interface fields — require a type-assertion instead.)
  • A type-assertion of a value x to a variable of type T is allowed if x is of any comparable type (even a concrete type). The type-assertion succeeds only if x == x would not panic.

That is:

	var i any = func() {}
	x, ok := i.(comparable)  // Compiles and does not panic: x == nil and ok == false.
	y := i.(comparable)  // Compiles, but panics at run-time because i is not comparable.
	var z comparable = i  // Does not compile: i is not necessarily comparable.
	var w comparable = math.NaN()  // Compiles: a float64 can always be compared without panicking.

Discussion

Like #52509 and #52614, this proposal allows comparable type parameters to be instantiated with ordinary interface types.

  • Unlike those proposals, this one also provides run-time semantics for the comparable interface.
  • Unlike #​52614, this proposal does not allow comparisons of type parameters whose type sets include incomparable types.

Like #51338, this proposal allows the use of comparable as an ordinary interface type.

  • Unlike that proposal, this one allows comparable type parameters to be instantiated with existing ordinary interface types.
  • Also unlike that proposal, under this proposal the == operator applied to two variables of comparable interface types cannot panic at run-time.
    • Note that, because today we have no way to constrain type parameters to be interface types, comparing variables of type parameters constrained by comparable interface types can panic at run-time.

Notably, this proposal allows panics from the == operator to be avoided (not just recovered!) using a simple type-assertion:

func Equal(a, b any) (eq bool, err error) {
	if _, ok := a.(comparable); !ok {
		return false, ErrIncomparable
	}
	if _, ok := b.(comparable); !ok {
		return false, ErrIncomparable
	}
	return a == b, nil
}

Examples

From #52509 (comment):

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

func F() {
    Eq(0, 0) // ok
    Eq([]int{}, []int{}) // compilation error: []int is not comparable
    Eq(any([]int{}), any([]int{})) // compiles OK, panics at run time. ('any' is comparable.)
    Eq[any]([]int{}, []int{}) // compiles OK, panics at run time
    Eq[any]([]int{}, 0) // compiles OK, runs OK, returns false
}

func G[T any](a, b T) {
    Eq(a, b) // compilation error: T is not guaranteed to be comparable
    Eq[any](a, b) // OK, may or may not panic at run time
}

From #52614, with further types added, as a variable:

interface                          comparable    may panic

any                                yes           yes
comparable                         yes           no
interface{ m() }                   yes           yes
interface{ m(); comparable }       yes           no
interface{ ~int }                  yes           no
interface{ ~struct{ f any } }      yes           yes
interface{ ~[]byte }               no
interface{ ~string | ~[]byte }     yes           yes

But, as a constraint:

constraint                         comparable    may panic

any                                no
interface{ m() }                   no
interface{ ~int }                  yes           no
interface{ ~struct{ f any } }      yes           yes
interface{ ~[]byte }               no
interface{ ~string | ~[]byte }     no
@gopherbot gopherbot added this to the Proposal milestone Apr 29, 2022
@Merovius
Copy link
Contributor

Merovius commented Apr 29, 2022

Would this compile?

type X[T any] interface {
    *T
    M()
}

func F[T comparable, P X[T]](v T) {
    P(&v).M()
    fmt.Println(v == v)
}

type S struct { A any }

func (s *S) M() { s.A = func() {} }

func main() {
    F(S{})
}

I don't see why it would be forbidden. It would then probably panic. Correct?

[edit] Ah, I see, this falls under

Note that, because today we have no way to constrain type parameters to be interface types, comparing variables of type parameters constrained by comparable interface types can panic at run-time.

TBH I feel that's a downside compared to #51338. In general, I feel that #51338 provides overall better semantics - the semantics described there are much closer to what I would intuit comparable to mean. YMMV, of course.

[edit2] to clarify: By "what I would intuit comparable to mean", I mean when used as an interface type, as well as when used as a constraint.

@bcmills
Copy link
Member Author

bcmills commented Apr 29, 2022

@Merovius, I think the P(v).M() line is always a compile error today, regardless of comparability (https://go.dev/play/p/wkSDX6EATJu). But that's orthogonal to this proposal. 😅

@Merovius
Copy link
Contributor

Merovius commented Apr 29, 2022

Whoops. Edited sneakily.

@bcmills
Copy link
Member Author

bcmills commented Apr 29, 2022

Ok, then here we go!

type X[T any] interface {
    *T // Since the type set of X[T] is always a pointer type, a type constrained by X[T] is comparable.
    M()
}

func F[T comparable, P X[T]](v T) {
    P(&v).M()
    fmt.Println(v == v)  // This is allowed (because T is comparable), but may panic at run-time.
                         // (And that fact is completely independent of both P and X.)
}

// S is comparable: it is a struct type whose fields are comparable.
// (Field A is comparable because the type-set of 'any' includes at least one comparable type.)
type S struct { A any }

func (s *S) M() { s.A = func() {} }

func main() {
    F(S{})  // This panics at run-time.
    // (The call to M() causes the resulting value to become incomparable, and then it is compared.)
}

Note that the equivalent non-generic code also compiles successfully and panics at run-time: https://go.dev/play/p/WZtngo905Xj

In my opinion that is a good thing, because it allows one to reason about generic code by thinking through (and experimenting with) non-generic equivalents. (Compare #52614 (comment).)

@ianlancetaylor ianlancetaylor added this to Incoming in Proposals (old) Apr 29, 2022
@neild
Copy link
Contributor

neild commented Apr 29, 2022

The type set of the comparable interface includes all comparable types. (Thus, comparable is itself comparable.)

This may seem like a nitpick, but it's significant:

Currently, an interface's type set never contains an interface type. I think what you want to say is that all comparable types implement the comparable interface, not that they are in its type set.

"A is in the type set of B" means that B can store an A, including A's type. "A implements B" is a weaker assertion.

@bcmills
Copy link
Member Author

bcmills commented Apr 29, 2022

Currently, an interface's type set never contains an interface type. I think what you want to say is that all comparable types implement the comparable interface, not that they are in its type set.

Indeed. I think my understanding of type sets and “implements” is still a bit of a holdover from earlier discussions in which those two concepts were identical. I don't fully understand why they're not. 😅

@bcmills
Copy link
Member Author

bcmills commented Apr 29, 2022

@neild, updated with more precise language based on the current spec.

@bcmills
Copy link
Member Author

bcmills commented Apr 29, 2022

(On further reading I think the current spec is more-or-less incoherent with the interpretation of union terms as run-time interface types — but that's orthogonal to this proposal.)

@neild
Copy link
Contributor

neild commented Apr 29, 2022

Indeed. I think my understanding of type sets and “implements” is still a bit of a holdover from earlier discussions in which those two concepts were identical. I don't fully understand why they're not. sweat_smile

A variable of interface type can store a value of any type that is in the type set of the interface.

A variable of interface type can't store a value of interface type.

var a any
var b any = int(0)

// This stores the value stored in b (type int), not b (type any).
a = b

Therefore error (for example) is not in the type set of any, because you can't store a value of type error in a variable of type any.

You can, however, assign a value of type error to a variable of type any, because error implements any.

@griesemer
Copy link
Contributor

griesemer commented Apr 29, 2022

So in this example given above

func G[T any](a, b T) {
    Eq(a, b) // compilation error: T is not guaranteed to be comparable
    Eq[any](a, b) // OK, may or may not panic at run time
}

the two calls of Eq are Eq[T](a, b) and Eq[any](a, b) (after type inference). The type set of T is the type set of its constraint which is any. So the instantiation of Eq[T] is not permitted (while Eq[any] is) because T is a type parameter and not an ordinary interface (even though the type sets seem identical)? Do I have that right?

@bcmills
Copy link
Member Author

bcmills commented Apr 29, 2022

The type set of T is the type set of its constraint which is any.

I honestly no longer have a coherent understanding of type-sets. (Something changed in between the initial proposal and the wording in the current spec and it doesn't click at all for me any more.)

From @neild's explanation above, though, I would expect that the type set of T is indeed equal to the type set of any.

the instantiation of Eq[T] is not permitted (while Eq[any] is) because T is a type parameter and not an ordinary interface (even though the type sets seem identical)? Do I have that right?

More or less, yes: a type parameter is not necessarily an interface type.
(Eq[T] is not permitted because T is not guaranteed to implement comparableT and its constraint are two different entities!)

I note that the spec currently says that “[f]or a type parameter [the parameter's underlying type] is the underlying type of its type constraint, which is always an interface.” I think that sentence is erroneous: the underlying type of a type parameter cannot be an interface type, because nothing constrains the parameter to be instantiated with an interface type.

(It is not obvious to me whether the actual implementation in Go 1.18 contains the same error.)

@griesemer
Copy link
Contributor

griesemer commented Apr 29, 2022

Note that we're careful to talk about "non-type parameter interfaces" in the spec. A type parameter is an interface with a "fixed" dynamic type if you will, which is why it has special properties.

@bcmills
Copy link
Member Author

bcmills commented Apr 29, 2022

I haven't been keeping up with the spec changes, but that seems to weaken the notion of “interface types” to be nearly meaningless.

A type parameter does not behave at all like an interface type with a fixed dynamic type: its zero-value is not the nil interface value, it doesn't present as an interface value when observed with reflect, and it supports operators that are not defined for interface values in general.

@atdiar
Copy link

atdiar commented Apr 29, 2022

So in this example given above

func G[T any](a, b T) {
    Eq(a, b) // compilation error: T is not guaranteed to be comparable
    Eq[any](a, b) // OK, may or may not panic at run time
}

the two calls of Eq are Eq[T](a, b) and Eq[any](a, b) (after type inference). The type set of T is the type set of its constraint which is any. So the instantiation of Eq[T] is not permitted (while Eq[any] is) because T is a type parameter and not an ordinary interface (even though the type sets seem identical)? Do I have that right?

I think that the way to grok this for me is to come back to the spec.
For G, any is a type constraint: it defines the set of permissible types for the type parameter T.
T is essentially a bounded variable.

This set of permissible values is much larger that the one defined by comparable. That' s why Eq[T] can't compile. T could go out of the range of types defined by comparable.

However any as an interface type belongs to the set of permissible values defined by the type constraint comparable (in this proposal)
So it can instantiate Eq although it may panic at runtime just like any interface comparison in traditional Go code.

type sets do not directly matter here. They do not even include interface types (for good reasons).

@griesemer
Copy link
Contributor

griesemer commented Apr 29, 2022

Assignment to an interface actually changes type sets and we are ignoring that. Given

var f func()
var x any = f

the comparison x == x is permitted (but will panic) even though f is not comparable. Go effectively provides a (panicking) == operator for f upon assignment to x. This means that the type set of the interface any is really the set of all types which implement == (and not simply the set of all types). We can assign f to it even though f is not in the type set of interface any because the assignment makes f part of the type set. When we take f out again from x (through a type assertion), we remove the == operator again. (It's almost as if we can use == on x if we don't look too closely, but as soon as we want to know exactly what type we're operating on we can't do it anymore...)

On the other hand, when we talk about the constraint (type parameter type) any we really mean the set of all types, comparable or not.

If we now define comparable as the set of types which support the (possibly panicking) == operator we can perhaps say:

  • The ordinary interface any implements comparable: the type set of the interface any is the same as the type set of comparable. This any may be used to instantiate comparable.
  • The constraint interface any is the set of all types and does not implement comparable. This any cannot be used to instantiate comparable.

Again, the type sets for the two forms of any are different because the ordinary (non-type parameter) interface accepts non-comparable types (which are made comparable upon assignment) but the type constraint any does not: instantiation does not change the type set.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Apr 30, 2022

I think I may understand that comment after reading it a couple of times, but I find the whole set of ideas rather confusing.

I would like to believe that any as a type parameter constraint and any as an ordinary type mean the same thing.

If I understand this proposal correctly (I may not) whether a type argument satisfies the type parameter constraint comparable is different from whether a value of that type may be assigned to a variable of type comparable. For example, the type argument any satisfies the type parameter constraint comparable, but a value of type any may not be assigned to a variable of type comparable.

(Separately, this proposal says "unlike [#51338], under this proposal the == operator applied to two variables of comparable interface types cannot panic at run-time." Just a note that the same is true for #51338: it does not permit a panic when using == to compare values of type comparable.)

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Apr 30, 2022

We could imagine that we have two different equality operators. One is == which can only be used with comparable non-interface types. It never panics. The other is =i= which can only be used when comparing interface types, including comparing interface types to non-interface types. It may panic. (There is also != and !i= which behave in the obvious fashion.) The map keyword permits only comparable non-interface types as the key type. The new mapi keyword permits only interface types as the key type.

This seems straightforward for non-generic Go code. Various instances of == must be mechanically converted to =i=. Various instances of map must be mechanically converted to mapi.

In a generic function, a constraint with a type set of only comparable types permits the use of ==. The predefined type comparable is such a constraint. A constraint that explicitly mentions a non-comparable type (such as interface { []byte | string} does not permit the use of either == or =i=. A constraint that may be instantiated with an interface type (this is a constraint that only lists methods, including any) and is not comparable (and does not embed comparable) does not permit == but does permit =i=. Types that permit == may be used as the key type of a map. Types that permit =i= may be used as the key type of a mapi.

This leads us to the following:

type Set[T comparable] map[T]bool // OK; map uses ==
type Set[T any] map[T]bool // Does not compile
type Set[T any] mapi[T] bool // OK; mapi uses =i=
func Eq1[T comparable](a, b T) bool { return a == b } // OK
func Eq2[T any](a, b T) bool { return a == b } // Does not compile
func Eq3[T any](a, b T) bool { return a =i= b } // OK

Back in reality, we can't change existing Go code to use =i= or mapi. We could theoretically change generic code to use those new names, but not in practice.

But something we could do is to change the constraint. The constraint comparable means that the type argument must support ==. We could have a different constraint that means that the type argument must support either == or =i=. If we use that different constraint we will permit the type parameter to be used as the key type of a map. The type set of this different constraint is the type set of all types (even non-comparable types), as otherwise we could not us a type argument of any. However, we might perhaps as a special case reject instantiating this constraint with a non-comparable type.

Once we do that we can go back to writing =i= as == and mapi as map. The choice is implicitly made by the type parameter constraint.

Then we just need a name for that constraint. I guess this gives us something similar to #52531.

@griesemer
Copy link
Contributor

griesemer commented Apr 30, 2022

I would like to believe that any as a type parameter constraint and any as an ordinary type mean the same thing.

Likewise. But we do have the odd situation that == is permitted on a variable of (ordinary) interface type but not a type parameter constrained by say any. It is exactly this behavior that seems to imply that any should implement comparable. My comment #52624 (comment) was an attempt at trying to make that work out in terms of type sets. (As an aside, the outcome is slightly different for some cases than what is proposed by this proposal, but not in important ways.)

The alternative view is what we have now. == on interfaces is simply an operation that is provided on (ordinary) interfaces, independent of type sets, and therefore shouldn't be taken into account for type sets. Which means that any does not implement comparable. #52614 is bolting == onto most type parameters, simply because they are interfaces, too, irrespective of whether they define comparable type sets or not.

If we believe comparable defines a type set at all, I think we need to make things consistent with type sets. And I think the implements relationship needs to be explained in terms of type sets or we are having bigger problems: for instance the theory behind Go generics relies on this property.

There's another approach: comparable is not defining a type set or interface at all. It's simply a special marker (a flag) on an interface. This happens to be written like an embedded type, but that's just for convenience. In this view, comparable means that == is available, nothing else. It's mostly independent of type sets. An interface that is marked as comparable can only be assigned (concrete) values that are in fact comparable. An interface that is marked comparable can only be implemented by interfaces that implement == (irrespective of type set). Maybe this is closest to this proposal because the implements relation is not just type set inclusion, it also needs to respect the comparable bit (possibly with repercussions for the type theory behind it).

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Apr 30, 2022

Another approach we could take (which I suspect that someone has already suggested) is to introduce a notation specific to constraints that means "this constraint may only be instantiated by an interface type". We permit == on type parameters with that constraint, with the understanding that == really means =i=, the version of == that can panic.

In fact there is any easy way to write such a constraint: interface not followed by {.

Then we can write

type Set[T interface | comparable] map[T]bool

I don't really like this idea but semantically I think it addresses all problems.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Apr 30, 2022

But we do have the odd situation that == is permitted on a variable of (ordinary) interface type but not a type parameter constrained by say any.

Sure, but really the type parameter constraint any only permits =i=, not ==. #52614 is basically saying that in a generic function == is always =i=. Note that this is not true in a non-generic function, where the type of the value determines whether we are using == or =i=. So the objection is to #52614 is basically that when I write == I don't expect to get =i= unless I've explicitly said that I want it.

@neild
Copy link
Contributor

neild commented Apr 30, 2022

If we believe comparable defines a type set at all, I think we need to make things consistent with type sets. And I think the implements relationship needs to be explained in terms of type sets or we are having bigger problems: for instance the theory behind Go generics relies on this property.

I don't follow what you mean by the implements relationship being explained in terms of type sets.

Under the current language of the spec, a "type set" is the set of types that can be stored in a variable of interface type. This explicitly excludes other interface types, because an interface variable cannot store an interface value. any is not in the type set of any, even though any obviously implements any.

The implements relationship seems distinct from type sets.

@atdiar
Copy link

atdiar commented Apr 30, 2022

Assignment to an interface actually changes type sets and we are ignoring that. Given

var f func()
var x any = f

the comparison x == x is permitted (but will panic) even though f is not comparable. Go effectively provides a (panicking) == operator for f upon assignment to x. This means that the type set of the interface any is really the set of all types which implement == (and not simply the set of all types). We can assign f to it even though f is not in the type set of interface any because the assignment makes f part of the type set. When we take f out again from x (through a type assertion), we remove the == operator again. (It's almost as if we can use == on x if we don't look too closely, but as soon as we want to know exactly what type we're operating on we can't do it anymore...)

Oh I see! Yes if we look at comparison in a fine-grained way. We could also look at it coarsely as a part of an operation specific to interface types. (Let me try to mirror you with this other perspective to see where it leads)
In this case, the type set of any would be the set of all non-interface types, still. But the interface type any itself would have that one operation specific to interface types that allows comparison of all values.

On the other hand, when we talk about the constraint (type parameter type) any we really mean the set of all types, comparable or not.

Yes. The set of permissible type arguments; which in this case, can be any type.
We know that not every type in this set has "==". interface types do have the possibly panicking kind of "==".

If we now define comparable as the set of types which support the (possibly panicking) == operator we can perhaps say:

  • The ordinary interface any implements comparable: the type set of the interface any is the same as the type set of comparable. This any may be used to instantiate comparable.

Here I think our perspectives would diverge slightly. Per spec, we don't know if any implements comparable. Even if we ruled that it did, we wouldn't know anything more about its type set.
Realistically, we only know that any (the interface type) has some version of "==" and so it is in the set defined by the type constraint comparable. (that's why I make it a predicate derived set in #52531 instead of interface-derived, more about that below)

If we said that any and comparable have the same type sets, shouldn't this compile?

package main

import "fmt"

func G[T comparable](a T) T {
	return a
}

func main() {
	fmt.Println(G[func()](nil))
}
  • The constraint interface any is the set of all types and does not implement comparable. This any cannot be used to instantiate comparable.

Since type constraints define sets, we could also express that in terms of set non-inclusion.

Again, the type sets for the two forms of any are different because the ordinary (non-type parameter) interface accepts non-comparable types (which are made comparable upon assignment) but the type constraint any does not: instantiation does not change the type set.

Well, we defined above the type constraint any as "...the set of all types, comparable or not."
Since we can't determine that every type in that set has "==", we just can't use this operation. We would need to add information for the type parameter.

So any may also not implement comparable while still being comparable. Perhaps we can make comparable be something other than an interface?
I got rid of comparable as an interface in #52531 because I wanted to keep type set inclusion transitive so as to follow interface implementation. It does not work with a spec-compliant comparable interface because all interfaces are comparable regardless of their type set.
If it wasn't for the comparable interface, I think we could provide a definition for interface implementation such that:
an interface A implements an interface B **iff** typesetOf(A) is included in typesetOf(B)
Bonus: if every type in typesetOf(B) supports an operation, every type in typesetOf(A) does.

That would perhaps allow us an additional rule such that "a type is in the set of permissible types defined by an interface constraint iff it implements it (i.e. type set inclusion)." I don't know if that rule would hold. So far, I had been reasoning in terms of sets of permissible types only.

@bcmills
Copy link
Member Author

bcmills commented Apr 30, 2022

@griesemer

Go effectively provides a (panicking) == operator for f upon assignment to x. This means that the type set of the interface any is really the set of all types which implement == (and not simply the set of all types).

I find that interpretation extremely confusing — it is defining type sets in terms of operators instead of the other way around.

The mistake, I think, is in treating interface types as merely “sets of types” rather than types in and of themselves. But they cannot be merely sets of types: I can have, say, a type that is a pointer to an interface type (*any), but “a pointer to a set of types” would be a categorical error.

When we acknowledge that interface types are types, then we can also see that the == operator on a variable of an interface type is, as @ianlancetaylor describes, semantically different from the == operator (if any) on the concrete value. (For example, it compares values as unequal if they are of different types, which the == operator for other types cannot do.)

So I see a serious problem that I see with the current formulation of type sets, which is that they explicitly fail to include an entire subset of the types in the language (namely, the interface types). (I thought some more about the implications of this problem, and filed #52628 for one of its ramifications.)

We see that in the current definition of “implements”: it is not one uniform rule about types sets (as I would expect it to be), but rather a pair of rules — one for type sets, and a different one for interface types.

A more uniform rule would include interface types in type sets, with two properties:

  1. A type “implements” an interface if it is in the type set of that interface.
  2. An interface type is a member of its own type set.

But, I think this is all basically a digression: it is relevant here only in the sense that it shows that type parameters should not be treated as just fancy interface types.

@bcmills
Copy link
Member Author

bcmills commented Apr 30, 2022

@ianlancetaylor

(Separately, this proposal says "unlike [#51338], under this proposal the == operator applied to two variables of comparable interface types cannot panic at run-time." Just a note that the same is true for #51338: it does not permit a panic when using == to compare values of type comparable.)

I do not think that holds. In that proposal:

Any comparable non-interface type could be assigned to a variable of type comparable.

The type SemiComparable is a “comparable non-interface type”, according to the general language notion of “comparable”.
However, comparing a SemiComparable value to itself may panic (https://go.dev/play/p/-OXyZ3bdgHS).

type SemiComparable struct {
	X interface{}
}

I do not see anything in proposal #51338 that prevents that panic.

In contrast, the special case for assignability in this proposal prevents a value of type SemiComparable from being assigned to a variable of type comparable: the SemiComparable value would have to be type-asserted to comparable, and that type-assertion (not the subsequent comparison!) is what would fail.

@bcmills
Copy link
Member Author

bcmills commented Apr 30, 2022

(Without the special case for assignability, this proposal decays to essentially #52509. So if we don't like that special case, I suggest that we adopt #52509 instead.)

@bcmills
Copy link
Member Author

bcmills commented Apr 30, 2022

@griesemer

If we believe comparable defines a type set at all, I think we need to make things consistent with type sets.

I agree. As far as I can tell, this proposal does keep comparable consistent with type sets: the set of concrete types that may be stored in the comparable interface is exactly the set for which == is defined.

And I think the implements relationship needs to be explained in terms of type sets or we are having bigger problems: for instance the theory behind Go generics relies on this property.

Again I agree. And as far as I can tell this proposal does keep ”implements” as consistent with type sets as it is today. However, since interface types for some reason are not included in their own type sets today, I think “implements” is already wildly divergent from type sets. (FWIW, I think that could be corrected by expanding the type set for interface types to include all interface types that implement it, but we would need to take care to avoid a circular definition.)

At any rate: the main point of flexion in this proposal is assignability, not “implements” or type sets. Under this proposal, the set of types that implement the comparable interface is exactly the set of types that have a defined comparison operator. However, run-time values can only be assigned to the comparable interface if that operator does not panic.

That is: this proposal breaks the relationship between “implements” and “is assignable to”, not the relationship between “implements” and type-sets.

@griesemer
Copy link
Contributor

griesemer commented Apr 30, 2022

@neild On implementing an interface the spec says:

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.

That is, the "implements" relation is very much defined in terms of type sets.

@Merovius
Copy link
Contributor

Merovius commented Apr 30, 2022

@bcmills

However, comparing a SemiComparable value to itself may panic (https://go.dev/play/p/-OXyZ3bdgHS). […] I do not see anything in proposal #51338 that prevents that panic.

We can't prevent that panic in and off itself, as the current language allows it and we can't break backwards compatibility. But with #51338, generic code constrained on comparable could never panic, because you could not instantiate it with SemiComparable. Because while it might be comparable as per spec, it does not implement comparable as suggested in the proposal. It also doesn't according to the current rules, so we are free to maintain that limit.

At least as I understand it. I don't think it is made explicit in the proposal text, but my understanding is, that a struct type would implement comparable if all its fields implement comparable (and similar for an array type). At least that's the assumption I made in the comment that sparked a lot of this debate and so far no one has contradicted that.

You say

Also unlike [#51338], under this proposal the == operator applied to two variables of comparable interface types cannot panic at run-time.

I don't think you that is unlike #51338 at all. I don't think == applied to an interface embedding (or being) comparable according to that proposal can panic at all.

@atdiar
Copy link

atdiar commented Apr 30, 2022

@bcmills
I'm not sure that type sets fail to include interface types.
The type sets of interface types are taken into account instead of the interface types themselves.
There is an indirection.
It's just that this indirection does not hold for "==" that may panic because the presence of this operator is not derived from the type sets but a property only available to interface types, by default.

The problem lies with comparable as an interface. I don't think it should be defined as an interface. It does not have the properties shared by interface types.

@griesemer
Copy link
Contributor

griesemer commented Apr 30, 2022

@bcmills Regarding your #52624 (comment) on interfaces as type sets:

Interfaces are types in the language, there's no question about that. But an interface variable never stores an interface, only concrete types. Thus, viewing an interface as a set of concrete types is fitting and as far as we have seen consistent (ignoring the debate around comparable for the moment). The fact that an interface cannot be in an interface's type set is not hurting this view in any way.

Your *any example is simply misleading: this is a pointer to an interface type, a concrete pointer type which clearly can be an element of a type set; and there's no reason to assume that this should be viewed as a pointer to a type set.

Regarding comparability: The correct answer may well be that for comparability of (variable) interfaces we don't look at the type set but the interface type itself. This is the "other approach" I have mentioned in #52624 (comment).

For instance, for any it's the interface type that provides the ==, not the types in its type set. That is, (variable) interfaces always have the operation ==, the "comparable bit". Constraint interfaces only have it when the "comparable bit" is explicitly set somehow. Which is why the variable interface any could implement the constraint comparable, but the constraint any would not implement the constraint comparable.

Unless I am mistaken, all proposals so far have either come up with a precise mechanism but fallen short of what we want to express in code, or outlined everything we want to express in code but failed to explain the precise mechanism.

@atdiar
Copy link

atdiar commented Apr 30, 2022

I think that most proposals would need to consider the following issues:

If we define comparable as the set of all types that have "==" and "!="

comparable interface breaks subtyping

More precisely, for a function F and 2 interfaces A and B such that:

  • F implements A
  • A implements B

We generally can deduce that F implements B.

If we apply this with A==any and B==comparable, it breaks. A function type does not have the comparison operators.

Also, for any interface besides comparable, interface implementation implies type set inclusion. Since the reverse is true according to the current spec, perhaps that it should be an equivalence for interfaces.

For comparable, we want to say that any interface type implements it but then the type sets are not always included.

Not sure that comparable can ever be turned into a proper interface type

comparable as currently implemented (non-spec compliant) should be usable as a type. We could rename it and keep it.

A comparable that would be spec-compliant could not be turned into a type: it would not work with the assignment rules because of the type set issues.
We should probably just keep it as a constraint.

comparable if embedded could make an interface unusable as a type

For the same reasons stated above, because comparable is deemed an interface, it should be embeddable. Which could be necessary to select the subset of permissible types that have "==" and "!=".
Best if that could be avoided so that all interfaces are usable as types later if we want to.

Potential solution?

Not make comparable an interface constraint.
Also that means that we need to find another way equivalent to interface embedding to combine constraints.
That should be easy enough.
A type parameter definition could accept a list of constraints. For instance:

  • space separated constraints for a type parameter would create the conjunction of constraints i.e. the intersection of the set of permissible typês for each constraint
  • Or we could use boolean connectives to make the conjunction more apparent (more future-proof perhaps)
  • ... other ideas ?

that could look like this:

func F1[T fmt.Stringer comparable](a, b T) bool { return Eq(a,b) // ok }
func Eq[T comparable](a, b T) bool {
    return a == b
}

Other questions that have not been adressed by any proposal so far...?

  • If two type parameters are constrained by comparable, can they be compared?
func Compare[T comparable & fmt.Stringer, U comparable](a T, b U) bool { return a == b} // Is it OK?

The problem is that I think it is allowed for interfaces...

  • How to determine the set of permissible type arguments defined by a constraint?

    1. For a basic interface, it is any type that implements the interface. This is a superset of the type set. It includes interface types that have the method set.

    2. For an interface type such as interface{~[]byte}, per spec. definition the interface implements itself but it is obviously not in the set of permissible type arguments.

    3. For comparable, we just need to check the availability of "==" and "!=". So any type that is not func, map, slice or a composite of any of those types.

Seems like we have to deal with 3 sets of types for an interface:

  • its type set
  • the set of types that implements the interface (may be a strict superset of the type set)
  • the set of permissible type arguments it defines

@bcmills
Copy link
Member Author

bcmills commented May 5, 2022

@atdiar, that's a very good point about subtyping. I think there is something of an analogy with union interface types.

Today, “implements” is the basis of type-parameter instantiation. Per https://go.dev/ref/spec#Instantiations:

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


#45346 suggested “permitting constraints as ordinary interface types” as a next step, and the various proposals about comparable are similar: they are all considering what happens when we take a type that is today allowed as only a type constraint, and interpret it as a type proper.

So, consider this program, which is valid in Go 1.18:

type Plusser interface {
	~int | ~string
}

func Add[T Plusser](a, b T) T { return a + b }

If Plusser were allowed as an interface type at run-time, then it would be important that callers not be allowed to instantiate Add[Plusser]. Although all of the types in Plusser's type-set support the + operator, Plusser itself (the interface type) does not, so Plusser must not implement itself.

Note that an ordinary interface type must implement itself. This program surely must be valid:

func Println[T fmt.Stringer](x T) {
	fmt.Println(x.String())
}

func main() {
	buf := new(strings.Builder)
	buf.WriteString("Hello, world!")

	var s fmt.Stringer = buf
	Println(s)
}

As it turns out, comparable has exactly the opposite problem. comparable necessarily does implement itself, because all interface types support == and comparable is an interface type — and also because the whole point of comparable is to represent things that support ==. 😅 But also, other interface types ought to implement comparable, because interface types in general (including any) support the == operator today.

So, indeed, we do have the case that “F implements any” and “any implements comparable”, but F does not implement (and is not a subtype of) comparable. And that is definitely awkward, because in some sense it breaks substitution. I'll have to think about that some more.

@jimmyfrasche
Copy link
Member

jimmyfrasche commented May 5, 2022

It's awkward looking written as that but it looks less awkward if you write it as

  • F∈typeset(any)
  • any∈typeset(comparable)
  • F∉typeset(comparable)

as it makes it clear that the type and the typeset it generates are different kinds of things

It also makes it clearer why interface { A | B }∉typeset(interface { A | B })={A, B}.

@bcmills
Copy link
Member Author

bcmills commented May 6, 2022

Yeah. On further consideration, I think the fact that this would break subtyping isn't actually that big a deal in and of itself, considering that Go already doesn't have a formal concept of subtypes (compare https://github.com/bcmills/go2go/blob/master/subtypes.md).

The thing that Go uses in place of subtypes is assignability, and there we already have some kind of analogous cases: a named type is assignable to the corresponding literal type, and a value of a literal type is assignable to any corresponding named type, but named types are not assignable to each other. Substitute comparable for the “a literal type” in that sentence, and you have a perfect analogy (https://go.dev/play/p/a0NmWliZNyG):

	var f F  // type F struct{}
	var a A  // type A = struct{}
	var b B  // type B struct{}

	a = f // F is assignable to A
	b = a // A is assignable to B
	b = f // F is not assignable to B

But, it's true that this would break the existing relationship between “implements” and “assignable to”, and it would break the existing correspondence between “is or implements” and subtyping. So probably we need a different approach.

@bcmills
Copy link
Member Author

bcmills commented May 6, 2022

Looking at this proposal through the lens of #52509 (comment), I think we could use almost exactly those rules to describe this proposal.

The difference would be in the assignability rule. #52509 allows:

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

but this proposal would have an additional caveat:

  1. Assignment
    a) x is assignable to i if typeset(x) ⊆ typeset(i) and either every value in type(x) is comparable or i does not embed comparable

In addition, I think both proposals need an explicit rule for type-assertions. For this one:

  1. Assertability
    a) x.(I) succeeds if T ⊆ typeset(I) (where T is the dynamic type of x) and either the value of x is comparable or I does not embed comparable

@rsc rsc changed the title proposal: the comparable interface represents the comparable subset of run-time values proposal: spec: allow values of type comparable Aug 10, 2022
@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Nov 4, 2022

We have proposed #56548 as an alternative to this approach. If we adopt #56548 we will not be adopting this proposal. Putting this one on hold pending a decision on #56548.

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

No branches or pull requests

8 participants