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

spec: document definition of comparable #50791

Closed
griesemer opened this issue Jan 25, 2022 · 38 comments
Closed

spec: document definition of comparable #50791

griesemer opened this issue Jan 25, 2022 · 38 comments
Milestone

Comments

@griesemer
Copy link
Contributor

griesemer commented Jan 25, 2022

Title says it all. Reminder issue.

cc: @ianlancetaylor
cc: @findleyr
cc: @mdempsky

@griesemer griesemer added the NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. label Jan 25, 2022
@griesemer griesemer added this to the Go1.18 milestone Jan 25, 2022
@griesemer griesemer self-assigned this Jan 25, 2022
@rsc
Copy link
Contributor

rsc commented Jan 25, 2022

What would it be an alias of?

@griesemer
Copy link
Contributor Author

griesemer commented Jan 25, 2022

At the moment we have the equivalent of

type comparable <magic_comparable_interface_literal>

in the universe scope.
If it were an alias, it would be the same but as an alias declaration.

As it is now, there is an underlying type, which is that magic interface which doesn't have a name and can't be printed correctly.

I can't think of a way to make the distinction visible inside Go at the moment, but it's visible through the go/types API: This code prints the underlying type of comparable. Because there's no proper literal for it, it prints interface{} which is misleading at best. The actual underlying type behaves correctly (test).

If we make comparable an alias for this magic interface literal, the underlying type would be itself and could be printed as comparable.

Perhaps it should be a "basic" type like int, etc.

@rsc
Copy link
Contributor

rsc commented Jan 25, 2022

I'm confused about why making it an alias would change the underlying type, but perhaps my understanding that point that doesn't matter. Totally agree about it being its own underlying type. Calling it a 'basic' type would work too.

@findleyr
Copy link
Contributor

findleyr commented Jan 25, 2022

Agree about it being its own underlying type, which means it can't be a defined type. I think making it a basic type (like unsafe.Pointer) could be problematic. We'd have to introduce a new BasicKind, which behaves rather differently than all other basic kinds. This would require a updating a lot of code in tools.

Making comparable an alias for "the magic comparable interface" makes sense to me. Similar to any, we'd have special handling for formatting "the magic comparable interface" as comparable, but unlike any we don't have to implement this via pointer tracking: we have a bit on Interface that tells us if it is comparable.

@griesemer
Copy link
Contributor Author

griesemer commented Jan 25, 2022

Ok, we all agree that comparable's underlying type is itself.

Need to mention this in the spec in the section on underlying types, and need to adjust implementation accordingly.

See conclusion.

@griesemer griesemer added Documentation and removed NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. labels Jan 25, 2022
@griesemer griesemer changed the title spec: should comparable be an alias type (like any) spec: document that comparable is its own underlying type Jan 25, 2022
@gopherbot
Copy link

gopherbot commented Jan 25, 2022

Change https://golang.org/cl/380754 mentions this issue: go/types, types2: underlying type of comparable is itself

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Jan 25, 2022

If we ever permit variables to have type comparable, we'll have to explain what happens if you call reflect.TypeOf on a pointer to such a variable. Presumably the reflect.Kind will be Interface, because it is, after all, an interface type. For that reflect.Type, it seems to me that the Name method should return "comparable". That is what happens with the predeclared type error: the Name method returns "error". It is also what happens with the predeclared type int.

I think that implies that comparable is a defined type, defined in terms of a magic interface type, just as int is a defined type defined in terms of a magic integer type. I don't know what consequences that would have for the go/types package, and it's not necessarily essential that go/types and reflect act the same way.

@griesemer
Copy link
Contributor Author

griesemer commented Jan 25, 2022

The underlying type of error though is not error, it's the respective interface literal. This is different from other predeclared types such as int.

Making comparable a defined type like int is also a possibility, and perhaps the more correct choice. @findleyr is correct though that this will require some changes that will ripple through various packages' APIs because we'll add a new basic type. But that may be cleaner than using an alias to an interface which still needs some magic bit to indicate it is the comparable interface (this shows up in imports, for instance).

@findleyr
Copy link
Contributor

findleyr commented Jan 25, 2022

FWIW, when I wrote it my comment I didn't see much advantage to having comparable be a basic type. If we decide that is most correct, we should represent it accurately in go/types.

@griesemer
Copy link
Contributor Author

griesemer commented Jan 25, 2022

cc: @danscales because this will also effect the representation of comparable in the compiler.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Jan 25, 2022

I don't feel strongly about any of this, but I think we need to answer a couple of questions.

If we ever permit variables of comparable type, how will the reflect package distinguish them from variables of interface{} type?

Why should comparable be an alias when error and int are not aliases? Why is comparable different?

I don't see why comparable should be a basic type as such (though perhaps I misunderstand what a basic type is). It seems to me that comparable is an interface type. So one approach for the reflect package would be to make comparable a defined type (like int) defined in terms of an interface type, and add some way to determine whether all comparable types implement that interface. In fact something like that would seem to be required to support using the reflect package with an interface type that embeds comparable.

@griesemer
Copy link
Contributor Author

griesemer commented Jan 25, 2022

If we agree that the underlying type of comparable is itself there are only two choices in the implementation: it's a basic type like int, or it's an alias to some magic interface literal: the underlying type of a basic type is that basic type, and the underlying type of a literal type is that literal type.

Because comparable is also an interface, it seemed to make sense to make it an alias for a magic interface type. Since we don't have a source code representation for that interface, we need to mark it somehow so we can recognize it. This matters for APIs and import/export. It may be an implementation "detail", but it's important to get it right lest we want to deal with special cases all over the place.

@griesemer
Copy link
Contributor Author

griesemer commented Jan 25, 2022

We do have some precedent: unsafe.Pointer is a defined/named type (like int) and implemented as a basic type. However it does behave like a pointer in some situations (for instance, it cannot be the underlying type of a receiver base type). We have special cases in the type-checker for this because unsafe.Pointer is not represented like other pointers.

@timothy-king
Copy link
Contributor

timothy-king commented Jan 25, 2022

Narrow question: for comparable, what does (go/types.Type).Underlying() return today? What would it return if this was adopted?

@griesemer
Copy link
Contributor Author

griesemer commented Jan 25, 2022

See #50791 (comment). It should always return itself.

@findleyr
Copy link
Contributor

findleyr commented Jan 25, 2022

Regarding the behavior of comparable in reflect, if we were to allow it outside of constraint position: how would we distinguish interfaces that embed comparable? Wouldn't we need a new API to answer that question, independent of whether comparable itself has a name?

@danscales
Copy link
Contributor

danscales commented Jan 25, 2022

I'm not sure why the underlying type of comparable has to be itself.

Since we can't represent the underlying type of comparable in terms of anything else (i.e. it has no methods, but is different from empty interface), we clearly need a magic bit or new basic kind to distinguish that fundamental interface type - call it C.

Then, it seems to me we can either do type comparable C or type comparable = C.

As Ian points out, given that error is a defined type, why shouldn't comparable stay as a defined type? I.e. comparable is a defined type whose underlying type is the magic interface C (so type comparable C)

Of course, we do still have to have a method of printing and distinguishing C when reflect, etc. wants to look at it. I'm not sure that there is a good way other than a new basic kind.

@griesemer
Copy link
Contributor Author

griesemer commented Jan 25, 2022

@danscales: see #50791 (comment) : What do we print for the underlying type of comparable if it's not itself? Note that the underlying type of a defined type is not itself, unless it's a basic type.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Jan 25, 2022

@findleyr

Regarding the behavior of comparable in reflect, if we were to allow it outside of constraint position: how would we distinguish interfaces that embed comparable? Wouldn't we need a new API to answer that question, independent of whether comparable itself has a name?

No, we wouldn't. The reflect package does not need to distinguish interfaces that are the result of embedding from interfaces that simply list the same sets of methods. The reflect package only describes the runtime behavior of types, not the way in which they were defined.

For that matter, aliases are completely invisible in the reflect package.

@findleyr
Copy link
Contributor

findleyr commented Jan 25, 2022

@ianlancetaylor

The reflect package only describes the runtime behavior of types, not the way in which they were defined.

That's exactly my point: how would we express the behavior that the interface pointed to by x can only hold comparable types?

type I interface { comparable }

var x *I

@danscales
Copy link
Contributor

danscales commented Jan 25, 2022

@danscales: see #50791 (comment) : What do we print for the underlying type of comparable if it's not itself? Note that the underlying type of a defined type is not itself, unless it's a basic type.

Yes, I agree that we still have to have something to print out for C and possible a new kind or magic bit for C. (I had already edited my previous comment to say something like that, but should have made a new comment.)

I think we could print out <underlyingComparable> or something like that for the underlying type of comparable. My point is that we don't have to make the underlying type of comparable be itself. We can make comparable similar to error - a defined type. But I realize it may be uglier in some ways (which are not usually seen).

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Jan 25, 2022

@findleyr Ah, sorry for misunderstanding. Yes, as I mentioned earlier, we would have to add some way to determine whether all comparable types implement that interface. As far as I can see this would have to be a new method on reflect.Type. I don't see any other approach that could work. In particular it would not work to introduce a new reflect.Kind.

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Jan 25, 2022

I guess my main concern about making comparable an alias is that this would be the only case in which we have an alias for a type that can not be expressed in any other way. It may still be the right choice, but it seems weird.

@findleyr
Copy link
Contributor

findleyr commented Jan 25, 2022

@ianlancetaylor

Yes, as I mentioned earlier, we would have to add some way to determine whether all comparable types implement that interface

Apologies, I missed that you had mentioned that explicitly in your second comment. I was still thinking about your original comment :)

I think the fact that a new API would be required in any case makes it less important that the universe comparable type has a name.

@griesemer
Copy link
Contributor Author

griesemer commented Jan 26, 2022

Per discussion with @ianlancetaylor . Here are implementation options for go/types, types2:

  1. Introduce a new basic types.BasicKind value, similar to types.UnsafePointer.
  2. Make comparable an alias for a magic interface literal.
  3. Make comparable a defined type whose underlying type is itself, as in: type comparable comparable.
  4. Make comparable a defined type whose underlying type is an interface, as in: type comparable interface{comparable}.

Discussion:

  1. Would make comparable a built-in basic type which count as defined/named types and their underlying types are themselves. However, it would require the introduction of the new BasicKind value throughout various packages (incl. importers) and, in a future where we permit var v comparable, would require a new reflect.Kind.
  2. Seems simple (CL 380754) but probably requires (minor) adjustments to importers to work correctly. The underlying type of a literal type is itself.
  3. Likely doesn't require any adjustments but it violates the invariant that the underlying type of types.Named (defined types) is not a defined type.
  4. Doesn't violate the invariant for defined types but then the underlying type of comparable is not itself.

@gopherbot
Copy link

gopherbot commented Jan 26, 2022

Change https://golang.org/cl/380854 mentions this issue: spec: document the underlying type of comparable

gopherbot pushed a commit that referenced this issue Jan 26, 2022
For #50791.

Change-Id: I7f135bb6626128a3cee9fd71c57535c1fc83ac7f
Reviewed-on: https://go-review.googlesource.com/c/go/+/380854
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
@virtuald

This comment has been minimized.

@griesemer
Copy link
Contributor Author

griesemer commented Jan 26, 2022

Per further discussions with @ianlancetaylor and @findleyr:

The updated spec already says that all predeclared types are named types. comparable can only be a named type if it's a defined type (like error), or a predeclared basic type (like int). For reasons outlined above, the latter is not a good option. Thus we need a defined type. Unless we break the language-wide invariant that the underlying type of a defined type cannot be a defined type, comparable as a defined type cannot be its own underlying type, after all. It can also not be an alias to a magic interface as that would not be a defined type.

Thus, we can define it as:

type comparable interface{ /* magically marked as comparable */ }

which is what we already have in the implementation. When printing the underlying type of comparable, we can print interface{comparable} which is a valid Go type.

In short: The underlying type of comparable is not itself. Instead we define comparable similar to error, as a defined type with a magic underlying type that still can be printed as valid Go.

@griesemer griesemer changed the title spec: document that comparable is its own underlying type spec: document definition of comparable Jan 26, 2022
@gopherbot
Copy link

gopherbot commented Jan 26, 2022

Change https://golang.org/cl/381094 mentions this issue: go/types, types2: clean up the set up of error, comparable

@gopherbot
Copy link

gopherbot commented Jan 26, 2022

Change https://golang.org/cl/381076 mentions this issue: Revert "spec: document the underlying type of comparable"

gopherbot pushed a commit that referenced this issue Jan 26, 2022
…omparable}"

For #50791.

Change-Id: Ib12009d2895146e55ec3a51aa8ceafe58dfd82a5
Reviewed-on: https://go-review.googlesource.com/c/go/+/380754
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
gopherbot pushed a commit that referenced this issue Jan 26, 2022
Follow-up on CL 380754.

For #50791.

Change-Id: Ia2f8f9785c2f02647525e7ee4168991fd4066dd3
Reviewed-on: https://go-review.googlesource.com/c/go/+/381094
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
gopherbot pushed a commit that referenced this issue Jan 26, 2022
This reverts CL 380854.

Per the conluding discussions on #50791. A follow-up will
document `comparable` more thoroughly.

For #50791.

Change-Id: I15db9051784a012f713e28d725c3b8bbfeb40569
Reviewed-on: https://go-review.googlesource.com/c/go/+/381076
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
@beoran
Copy link

beoran commented Jan 27, 2022

Just bike shedding but maybe interface {==} could be the magical one?

@changkun
Copy link
Member

changkun commented Jan 27, 2022

Isn't it going to be easier if we have operator method? No magic anymore:

type comparable[T any] interface {
    ==(t T) bool // == is the operator but also the name of the method
}

@griesemer
Copy link
Contributor Author

griesemer commented Jan 27, 2022

Just bike shedding but maybe interface {==} could be the magical one?

It could but why introduce a new notation for something we'll never need? We have the name comparable.

Isn't it going to be easier if we have operator method? No magic anymore:

We've tried operator methods repeatedly over the course of developing generics. They have their own (numerous) problems. That ship has sailed (and sunk) a long long time ago.

Except for documentation, I think this issue is resolved. Thanks.

@changkun
Copy link
Member

changkun commented Jan 27, 2022

It would be an interesting story to hear about the failure due to the proposal doc have only two places mentioning operator method but none of them mentioned about the sunk of that approach and only says "unplanned".

@griesemer
Copy link
Contributor Author

griesemer commented Jan 27, 2022

It would be an interesting story to hear about the failure due to the proposal doc have only two places mentioning operator method but none of them mentioned about the sunk of that approach and only says "unplanned".

There's only so much time in one's life to write down every single path taken which ended in a dead end. Sometimes it's just two short mentions... :-)

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Jan 27, 2022

@changkun https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md#why-not-use-methods-instead-of-type-sets

@gopherbot
Copy link

gopherbot commented Jan 29, 2022

Change https://golang.org/cl/381896 mentions this issue: spec: add section on comparable constraint

@fzipp
Copy link
Contributor

fzipp commented Feb 7, 2022

When printing the underlying type of comparable, we can print interface{comparable} which is a valid Go type.

In short: The underlying type of comparable is not itself. Instead we define comparable similar to error, as a defined type with a magic underlying type that still can be printed as valid Go.

I think this should be reflected by the declaration of comparable in the builtin documentation package:

https://github.com/golang/go/blob/master/src/builtin/builtin.go#L102

-type comparable comparable
+type comparable interface{ comparable }

Code-Hex added a commit to Code-Hex/go-generics-cache that referenced this issue Feb 11, 2022
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
For golang#50791.

Change-Id: I7f135bb6626128a3cee9fd71c57535c1fc83ac7f
Reviewed-on: https://go-review.googlesource.com/c/go/+/380854
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
…omparable}"

For golang#50791.

Change-Id: Ib12009d2895146e55ec3a51aa8ceafe58dfd82a5
Reviewed-on: https://go-review.googlesource.com/c/go/+/380754
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
Follow-up on CL 380754.

For golang#50791.

Change-Id: Ia2f8f9785c2f02647525e7ee4168991fd4066dd3
Reviewed-on: https://go-review.googlesource.com/c/go/+/381094
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
jproberts pushed a commit to jproberts/go that referenced this issue Jun 21, 2022
This reverts CL 380854.

Per the conluding discussions on golang#50791. A follow-up will
document `comparable` more thoroughly.

For golang#50791.

Change-Id: I15db9051784a012f713e28d725c3b8bbfeb40569
Reviewed-on: https://go-review.googlesource.com/c/go/+/381076
Trust: Robert Griesemer <gri@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests