proposal: spec: add new constraint kind satisfied by types that support == (including interface types)

[atdiar]

Problem Statement

Currently, interface types and composites of interface types do not implement the comparable constraint interface.
Yet, the use of the comparison operators (== and !=) is allowed for interface types (and composites) in non-generic code.
We would like to be able to use those operators in generic code as well.

It should allow us to use interfaces such as reflect.Type or ast.Node in generic Set or Map datastructures by default.

Proposed Solution

We need a new constraint that is not an interface, for reasons we explain below.
This might well be a standalone unless there are other interesting operations available to interface types, that are shared only by some but not all members of the typesets they determine.
A quick, non-committing, idea would be to make it a predicate constraint e.g. HasComparisonOperators (too lenghty a name!!)
It should solve issue #52474 and permit the definition of generic Sets and Maps accepting interface types as type parameter values.

Explanation

For a summary of the issues at stake, skip to: #52624 (comment)

Go1.18 introduced constrained parametric polymorphism in the language.
The type constraints that can be written in 1.18 are under the form of interfaces.
Interfaces in Go denote set of types called type sets that can be defined as the set of non-interface types that implement said interface. Type set inclusion and interface implementation are in practice linked in an equivalence relation.

These type sets should mirror the subtyping relation of interfaces by being transitive sets meaning that:
Given three interfaces A , B, C such that A implements B and B implements C ,
we should be able to infer that typesetOf(A) ⊂ typesetOf(C) (equivalent to A implements C).
This was always the case for pre-1.18 Go when we only had Basic interfaces. This should extend quite naturally to all interfaces in Go 1.18

We posit that this property of typesets (transitivity), along with the equivalence relation between interface implementation and typeset inclusion , is very advantageous if not necessary for their accurate computation as well as the computation of the operation set and/or method sets, available to the members of typesets.

We also claim that the current issue of comparability/availability of comparison operators stems from the fact that it does not follow the subtyping relation.
If we take the simple example of the any interface, function types implement any as they are members of its typeset.
However they do not possess the comparison operators. Yet any, as an interface type, can still use the comparison operators.
It shows that an interface type having access to the comparison operators cannot be inferred from its typeset. The operations of interface types are independent from the operation set defined by the respective typesets.

So what now?

We need a new way of defining the permissible set of types that defines a type constraint.

This new kind of set should not be defined by an interface (so that it does not get embedded or it might interfere with the typeset computations). Such a set will be able to directly include interface types (and composites). Therefore, it won't have a type set.

As shown above, inducing operations of interface types from their type set is insufficient in the case of comparability. It only works for the current implementation of comparable and its embeddings.

Do we still need the comparable interface constraint or #51338 ?

We may not need it as much anymore but it may not hurt to have it either (see #49587 ).
Besides, comparable should belong to the set denoted by HasComparisonOperators by definition.

What about the interactions between two kinds of constraint?

Since HasComparisonOperators may only be used in generic code to constrain generic map key types for example, that's where we should place our focus.
An example of interaction is the case of nested functions where the inner function uses HasComparisonOperators and the outer function uses interfaces as constraints for a same type parameter.
It's presumed that HasComparisonOperators should apply further bounded quantification to the typesets accepted by the outer function.

Said more simply, the set of permissible types for the outer function has to be a subset of the set defined by HasComparisonOperators.

Shouldn't we be able to combine the two kinds of constraint?

A priori, there would be no need for it. So no need to create extra syntax.
We don't think that there are many cases where one wants a subset of all types satisfying HasComparisonOperators since, typically, the sole constraint on map key types is to have the comparison operators.
Maybe someone can come up with a rebuttal use-case though.
[edit] @Merovius found a rebuttal-case.

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 comparable fmt.Stringer](a, b T) bool { return Eq(a,b) // ok }
func Eq[T comparable](a, b T) bool {
    return a == b
}

// OR

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
}

Why not just change comparable?

[edit] we could by using the provision from the backward-compatibility promise.

"comparable" is a good name. But for the aforementioned reasons that changing comparable would interfere with typeset computations, we think that comparable should retain its current semantics.

Creating a new kind of constraint might add a bit more complexity to the backend. But the advantage is that it would not interfere with typeset computations, leaving us with some leeway to use all interfaces as types later.
This could be a crucial point in the discussion about sum/union types for instance.
The alternative* could more easily preclude us from entertaining using interfaces as union types (#19412), should we see a need for it (because typeset calculation would not be precise). It might be better to leave the design space open, just in case.

(*) the alternative as proposed by some would be to change the comparable interface. It would still be an interface constraint :
As such it would be embeddable but reifying it into a type would not be possible.
It would create two subcategories of interface constraints : those that embed comparable and would not be reifiable into types and the rest that would be reifiable.

Other naming ideas?

• weakcomparable
• comparable-maypanic
• comparable-unsafe
• ...

We could also change the implementation of comparable so that it is equivalent to our HasComparisonOperators
In which case we would take advantage of the provision in the backward-compatibility promise.

Changes to the Specification

Just a few notes, leaving that part to the more experienced.

• A constraint C would be said to be satisfied by a type T if(f?) T belongs to the set of permissible type arguments defined by C.
• interface implementation would be equivalent to typeset inclusion. Note: that does not mean that if I implements A, I is in the typeset of A. It means set inclusion of the corresponding typesets.
• the definition of a type being comparable should be adjusted for the semantics of the current implementation of comparable
• there would be effectively two ways to define a type constraint: interface constraints and predicate constraints. Both defining a set of permissible types.
• type parameters for generic map keys could use the predicate constraint HasComparisonOperators or be more restrictive by using the interface constraint comparable. The choice would be left to the programmer.

References

Alain Frisch, Giuseppe Castagna, Véronique Benzaken (2008) Semantic subtyping: Dealing set-theoretically with function, union, intersection, and negation types

G. Castagna, T. Petrucciani, and K. Nguyen (2016) Set-theoretic types for polymorphic variants

Transitive set. Wikipedia

Jech, Thomas J., et al. Set theory. Vol. 14. Berlin: Springer, 2003.

[atdiar]

cc @griesemer @ianlancetaylor

[beoran]

Ah, now I see what is the problem. It is still allowed to use == on any types, for nil comparison, so the subset relationship would not hold if we change comparable. In that case, indeed it is better to keep comparable as it is, and have a different name for this.

We need a better name than HasComparisonOperators, though. Perhaps commensurable?

[atdiar]

Ah, now I see what is the problem. It is still allowed to use == on any types, for nil comparison, so the subset relationship would not hold if we change comparable. In that case, indeed it is better to keep comparable as it is, and have a different name for this.

We need a better name than HasComparisonOperators, though. Perhaps commensurable?

That's a great point that you raise.
comparison to nil also falls into that category/problem because struct types, array types and some basic types are not comparable to nil while interfaces are.
Perhaps it would require its own non-interface constraint too? It's a bit less certain that it would be needed as a first-class constraint though.

Regarding the name, I have no idea. Doesn't commensurable mean "measurable" though?

[Merovius]

We don't think that there are many cases where one wants a subset of all types satisfying HasComparisonOperators since, typically, the sole constraint on map key types is to have the comparison operators.
Maybe someone can come up with a rebuttal use-case though.

A generic map, which allows both a) O(1) access to elements and b) allows iteration in sorted key order. For example, it might use a binary tree as storage, alongside a map[K]*treeNode for O(1) access to elements.

I think as soon as you require to be able to mix these, the entire case for this seems to fall down. If we need to be able to combine them, whatever solution to whatever problem you come up to do that, can just as well be applied to what we call "constraint interfaces" (of which comparable is an example) instead. As you say yourself, the entire argument for not making comparable work however we think it should is

(*) the alternative as proposed by some would be to change the comparable interface. It would still be an interface constraint : As such it would be embeddable but reifying it into a type would not be possible.

i.e. the sole advantage of your HasComparisonOperator seems to be, that it can't be mixed with other constraints.

On a general level, having two different notions for a constraint for equality operators, which behaves subtly differently, seems like a very confusing idea. It certainly violates the goals of orthogonal language features.

[Merovius]

@beoran

It is still allowed to use == on any types, for nil comparison

Most types are not comparable to the predeclared identifier nil and as best as I know there is no way to write a constraint which allows it for interface types. So, I don't understand what you are saying here.

[atdiar]

We don't think that there are many cases where one wants a subset of all types satisfying HasComparisonOperators since, typically, the sole constraint on map key types is to have the comparison operators.
Maybe someone can come up with a rebuttal use-case though.

A generic map, which allows both a) O(1) access to elements and b) allows iteration in sorted key order. For example, it might use a binary tree as storage, alongside a map[K]*treeNode for O(1) access to elements.

Sorry, I'm not sure I understand. What does it change for the map key types? What additional constraint should be used to constrain the type parameter of such generic map?
edit: some kind of ordered constraint?

I think as soon as you require to be able to mix these, the entire case for this seems to fall down. If we need to be able to combine them, whatever solution to whatever problem you come up to do that, can just as well be applied to what we call "constraint interfaces" (of which comparable is an example) instead. As you say yourself, the entire argument for not making comparable work however we think it should is

Not sure I understand either. The issue of being able to combine them is a bit orthogonal as it would only appear in generic code. But it does mean creating some kind of syntax (for example similar to boolean connectives) and I'm not so sure that we want that. But the arguments about typeset computations would remain.

(*) the alternative as proposed by some would be to change the comparable interface. It would still be an interface constraint : As such it would be embeddable but reifying it into a type would not be possible.

i.e. the sole advantage of your HasComparisonOperator seems to be, that it can't be mixed with other constraints.

I think that this is a major point, yes. It also leaves us with the possibility of reifying any interface constraint. At least, it does not preclude it from the get-go.

On a general level, having two different notions for a constraint for equality operators, which behaves subtly differently, seems like a very confusing idea. It certainly violates the goals of orthogonal language features.

As I've said, the current comparable would not be an absolute requirement.
So there is also the possibility to change the current one, but I'd argue that it still shouldn't be an interface constraint if we want to avoid closing the route toward interface constraints as types. Otherwise, we would also end up having two different kinds of interface constraints (reifiable and non-reifiable).

[Merovius]

Sorry, I'm not sure I understand. What does it change for the map key types? What additional constraint should be used to constrain the type parameter of such generic map?
edit: some kind of ordered constraint?

Yes.

Otherwise, we would also end up having two different kinds of interface constraints (reifiable and non-reifiable).

Yes, that's the situation where are in, currently. Though I'm not sure "reifiable" is the right word.

[zephyrtronium]

We need a new constraint that is not an interface, for reasons we explain below. This might well be a standalone unless there are other operations available to interface types, that are shared only by some but not all members of the typesets they determine. A quick, non-committing, idea would be to make it a predicate constraint e.g. HasComparisonOperators (too lenghty a name!!) It should solve issue #52474 and permit the definition of generic Sets and Maps accepting interface types as type parameter values.

I am overwhelmingly opposed to adding a new identifier which means very close to the same thing as comparable but differs in a single detail. I agree with @Merovius that it violates orthogonality, and it makes more for new Go programmers to learn, for what I believe is very little benefit.

We posit that this property of typesets (transitivity), along with the equivalence relation between interface implementation and typeset inclusion, is very advantageous if not necessary for their accurate computation as well as the computation of the operation set and/or method sets, available to the members of typesets.

I find this claim irrelevant, if not dubious. We check whether a type satisfies a constraint by verifying that the type satisfies all of the constraint's intersection elements. Aside from methods which are listed explicitly, we find what operations are in the operation set of the constraint by the intersection of the types listed in its union terms. Neither of these things depend on transitivity. I don't think there is any context in an implementation of Go where it is useful to compute an entire type set.

We don't think that there are many cases where one wants a subset of all types satisfying HasComparisonOperators

What if I want to constrain a type parameter to any comparable type with a method String() string?

[atdiar]

I am overwhelmingly opposed to adding a new identifier which means very close to the same thing as comparable but differs in a single detail. I agree with @Merovius that it violates orthogonality, and it makes more for new Go programmers to learn, for what I believe is very little benefit.

It does not create much to learn, conceptually.
Besides, currently the spec has in effect two definitions for interface implementation:
One for the comparable interface and the other for the rest of Go's interfaces.
It would make everything behave and consistent. So I kindly beg to differ.

I would also add that most beginners would probably not start creating generic code and what I propose would almost only affect generic code. So I think that this argument might be a bit overblown.

We posit that this property of typesets (transitivity), along with the equivalence relation between interface implementation and typeset inclusion, is very advantageous if not necessary for their accurate computation as well as the computation of the operation set and/or method sets, available to the members of typesets.

I find this claim irrelevant, if not dubious. We check whether a type satisfies a constraint by verifying that the type satisfies all of the constraint's intersection elements. Aside from methods which are listed explicitly, we find what operations are in the operation set of the constraint by the intersection of the types listed in its union terms. Neither of these things depend on transitivity. I don't think there is any context in an implementation of Go where it is useful to compute an entire type set.

All this is possible by virtue of typesets being transitive sets. Transitivity in that case is stable wrt set union and set intersection.
That's the formal reason why we can infer method sets and operations in my understanding.
So there are theoretic underpinnings. In other terms, proper bounding requires some level of accuracy.
They should have been somewhat apparent when considering interface embedding.
If you are curious, I think that it might stem from downward absoluteness and upward absoluteness.

The main issue with interface types being included in typesets is that I think it messes with the accuracy of the typeset computation. It can be proven easily (I explained why in another issue).

As far as computing an entire typeset is concerned, that probably depends on whether we are talking extensionally or intensionally.
Regardless, (I think both might occur), I might be mistaken but... your argument seems to be in contradiction with the implementation https://github.com/golang/go/blob/master/src/go/types/typeset.go
We do check for typeset inclusion so typeset computation has to be somewhat precise.

What if I want to constrain a type parameter to any comparable type with a method String() string?

If you happen to read the discussion with @Merovius, who gave a great example, we could decide to add some syntax to be able to combine both kinds of constraint.
I gave an example that can be found in the theory (boolean connectives), but we could perhaps find a much simplified solution to make sure that our legibility goals are met. (I sure am a huge opponent of adding too many sigils in a language and the budget is already a bit spent for interface elements).
The goal here is (at the very least) to let a type parameter be constrained by multiple constraints. (the full list of boolean connectives would allow perhaps more but not sure it is needed at all)

A quick idea could be to put the list of constraints between parens, comma-delimited

package main

import "fmt"

type Map[T (HasComparisonOperators, interface{String()}), V any] map[T]V

func main() {
	fmt.Println(Map[fmt.Stringer,any]{})
}

Or we could lose the parens, use the ampersand symbol & instead of a comma, which may conform a bit more to set-theory and predicate logic.
These are just quick examples, btw, no need to really bikeshed on this. This is not very important at this stage of the discussion.
Also, I've never dealt much with parsing yet, so....

Obviously, I know that for interface constraints, the way to do it is via embedding. In practice, I don't expect things to get too confusing. But that's my impression and I would defer to the potential implementers here.

Out of sheer curiosity, do you have any example of such constraint that would occur in real code?

[ianlancetaylor]

I have to agree with earlier comments that given

func F1[T comparable](a, b T) bool
func F2[T HasComparisonOperators](a, b T) bool

then the difference between F1 and F2 is quite subtle.

Also it's hard to define the idea of a non-interface constraint, because of one generic function instantiating another.

func F1[T comparable](a, b T) bool { return a == b }
func F2[T HasComparisonOperator](a, b T) bool {
    F1(a, b) // OK?
    F1[T](a, b) // OK?
    F1[any](a, b) // not OK
}

[atdiar]

I have to agree with earlier comments that given

func F1[T comparable](a, b T) bool
func F2[T HasComparisonOperators](a, b T) bool

then the difference between F1 and F2 is quite subtle.

There is some overlap. Maybe it is because I've been thinking about it lately but the difference between the two constraints doesn't strike me as something too difficult to understand.
Perhaps that naming things appropriately could also help here.

Also it's hard to define the idea of a non-interface constraint, because of one generic function instantiating another.

func F1[T comparable](a, b T) bool { return a == b }
func F2[T HasComparisonOperator](a, b T) bool {
    F1(a, b) // OK?
    F1[T](a, b) // OK?
    F1[any](a, b) // not OK
}

I think that none of those cases should compile actually because the bounds for the type parameter T defined in F2 are too wide for usage by F1.
The reverse situation where F1 uses an instantiation of F2 should be fine however.

edit: to try and be clearer, comparable satisfies HasComparisonOperator but the opposite is not true; the cause being: most interface types have the comparison operators but are not comparable?

[jlouis]

Some pointers from someone who does little to no proposal work:

Equality operators in programming languages are hard. Exceedingly hard. I claim that it's because we (Programming Language Designers / Type Theorists / Computer Scientists) don't really have a good grasp of what equality means. We want some kind of sameness, but judging a bit:

• In practical terms, 40 years of language developement has told us that no-one implements equality in exactly the same way. In fact, many languages pose several comparison operators with different rules. We want a certain level of strictness and/or weakness and we propose an operator for our use case. Contrast with the exeuction semantics of an if..then..else block, for instance. It's far more agreed upon what such an expression/statement should reduce to.

• In theory, the last 10 years of work in Homotopy Type Theory suggest that the world of sameness isn't as clear cut as we think. In fact, it suggests that most of our (naive) definitions of equality are wrong for a lot of the things we want to do with a programming language.

Interface equality

The key point about interface equality is that it is heterogenous. We can compare interfaces of different type. Whereas comparison on ground types are homogenous in that the type must be the same type on both sides of the operator. At a first glance, comparable allows homogenous type comparison, but rejects heterogenous ditto. But the == operator is defined such that it "picks up" the heterogenous aspect when working on interfaces, or between a "concrete" type and an interface type.

It's one of those places where we---suddenly---take a giant leap of faith, bundle another kind of equality onto our == operator because it is ... correct ... somehow?

Some part of me thinks we are happy with Frankenstein Monsters. We even allow the Frankenstein Monster to panic our program.

This is the basis for my claim that we don't really understand sameness too well.

Problem Statement

Heterogenous-Equal (HEQ) can be nice to have, but I'd like to see a more fleshed out problem statement, as I think it goes for a solution a bit too early. In particular, try to find examples where the current situation is inadequate, and where the examples point in "different directions" in the sense that they shouldn't be reiterations of the same idea, posed in new ways. Then, when a solution is proposed ("Add HEQ"), it can be shown that it's "right" by the fact that it covers all of the examples. It also gives rise to alternatives. Maybe some of the examples can be solved in different ways. Maybe there's a different equality definition which fits better with the goals of Go. Perhaps a generalization is possible, etc.

To squeeze out examples, find issues or places in existing code where the proposal will help. This informs the cost/benefit analysis: core functionality imposes a cost in implementation, but that's just a constant factor. Much more important is that the cost scales linearly with users of the language since they all have to learn about the functionality. In turn, the benefit needs to be more than just an abstract theory. There must be some real value, and it also has to have a certain weight. For instance, I like the analysis Russ Cox did for strings.Cut.

Opinion statement

My hunch/intuition is that it's too early to tell. People have only had generics in the language for a very short time span. Go 1.0 came out in March 2012. Go 1.18 in March 2022. That's 120 months, we've had Go with a stability guarantee. But only 1 month we've had generics. So I'm going to claim we don't really understand how generics will settle in the language and what is possible. This is why I think one should round up some examples of what's not currently possible for a while. It makes a possible proposal far stronger because it can claim to solve a number of these pain points people have, where nobody found a good way to work around them.

Another hunch: a subtyping relation should always pose the following questions:

• How do we deal with contravariance?
• How do we deal with bounded polymorphism? (In the case where you mix in generics)

Because it is very likely to show up at some point. Discharging it might be possible, but my spider sense always tingles if subtyping is mentioned without these two items. The usual question to get the ball rolling is: "how does thing thing work when we start passing functions around?" and "we want to pass a generic parameter in a covariant and contravariant position. How?" Go usually gets around this question because interface embedding isn't a subtype relation.

[atdiar]

Indeed, I should have added more context. This proposal was initiated as a kind of counter proposal so I forgot to add the background details.
Agreed, we need a fair amount of motivating examples. I have none myself but it had been reported in other issues that people would like to use ast.Node or reflect.Type as values for type arguments constrained by comparable. This is currently not possible unless we embed comparable retroactively.
It could be done by "reifying" the comparable constraint into a proper interface type and embedding it but this is still limiting for library authors who define interfaces that have apparently no reason to be coercively comparable.

I will link these cases in the problem statement. It will be clearer.

Another hunch: a subtyping relation should always pose the following questions:

How do we deal with contravariance?
How do we deal with bounded polymorphism? (In the case where you mix in generics)

I think I might have an answer to the first question. I think that we have a subsumption rule if we restrict ourselves to the domain of interface types. However type constructors in Go are invariant so co/contra/variance does not matter too much in practice.

Regarding the second question, I am not too sure of what you mean by dealing with bounded polymorphism.
If I attempt an answer nonetheless, it would be that, to my knowledge, interfaces have a set interpretation that defines bounds on a range of non-interface types. But for interface types themselves, there is no such bounding (at least not yet).
So if we want to be able to use operations that target interface types ( == and != for instance i.e. HEQ) we probably need to create a superset of that set interpretation.
That's what this proposal attempts to do by using a predicate, and offer ideas about a syntax #52531 (comment) if we need to combine constraints.

(HEQ is nicely put! I wasn't really thinking about it this way)

[Merovius]

However type constructors in Go are invariant so co/contra/variance does not matter too much in practice.

I think even though variance doesn't matter directly, it still guides questions in that you have to ask the question of what happens when you call one from the other. i.e. what happens when you call func F[T compatable]() from func G[T HasComparisonOperators]() passing T as a type-argument and vice-versa. Even without actually variant type constructors, you can still gain some insight from that POV.

I think that's relevant here, because I think it exposes the main issue with this proposal. Either a) both directions work, in which case they really describes the same set of types and we don't need two names, or b) at least one direction doesn't work, in which case it seems likely that you run into situations where it's not clear which to use - or one of them is just always better, in which case you also don't need two names.

I don't understand well enough what you are proposing to actually apply this argument. But it might help you to make your case or understand the concerns people have.

[atdiar]

However type constructors in Go are invariant so co/contra/variance does not matter too much in practice.

I think even though variance doesn't matter directly, it still guides questions in that you have to ask the question of what happens when you call one from the other. i.e. what happens when you call func F[T compatable]() from func G[T HasComparisonOperators]() passing T as a type-argument and vice-versa. Even without actually variant type constructors, you can still gain some insight from that POV.

This still would not really be a variance issue but a consequence of the subsumption rule.
Constraints having a set interpretation, it should be easy to see that a type satisfying comparable has the comparison operators, but not every type that has the comparison operators satisfies comparable. Easiest example of the latter would be any. This is the exact same rule we have with interface constraints. Nothing really changes.

Where you are right is that interface implementation and constraint satisfaction look really similar and it does look similar to a variance issue.
Which is why I am a bit dubious about a proposal which would rule that interfaces implement comparable but can't satisfy comparable.

I think that's relevant here, because I think it exposes the main issue with this proposal. Either a) both directions work, in which case they really describes the same set of types and we don't need two names, or b) at least one direction doesn't work, in which case it seems likely that you run into situations where it's not clear which to use - or one of them is just always better, in which case you also don't need two names.

It should be clear because it uses the same kind of set inclusion check we use for interface constraints. It's really just an extension of the same logic, just including interface types. A bit like a superset of typesets.
HasComparisonOperator (or however we name it), as a predicate, would create a set of types. It is essentially an indicator function.

I don't understand well enough what you are proposing to actually apply this argument. But it might help you to make your case or understand the concerns people have.

I hope I was able to make things clearer. The main point is that although this proposal adds the concept of non-interface constraint, it allows to simplify the relation between interface implementation and interface constraint satisfaction.
And it should also solve the issue of using interface types as value for type parameters of map keys etc. Without requiring for interfaces to embed comparable.

Remains the issue of naming those constraints.

[Merovius]

@atdiar FTR I still do not understand what exactly the semantics are you have in mind both for how comparable works and how HasComparisonOperator works under your proposal. And I think it would be extremely helpful if you could provide a bunch of code-examples of which of them could/would be used in what circumstances and how they interact.

I find your abstract arguments about type set inclusions and constraints/interfaces/constraint kinds/reification impossible to understand. A set of "this piece of code currently does not compile/compiles and does X and would, under this proposal not compile/compile and do Y" is significantly easier to understand and IMO the best practical way to evaluate proposals. As it stands, the only thing I, personally, can go by for evaluating this is "I don't even understand what you are proposing, so it's obviously too confusing to explain to people".

[atdiar]

• comparable corresponds to the current implementation. As written in the proposal, we don't change anything.

• HasComparisonOperator denotes the set of types which have ( == and !=). It's a superset of comparable's typeset. It includes interface types and some composites of interface types. It can because HasComparisonOperator is not an interface. Just a pure type constraint.

For an example of how it would work, see @ianlancetaylor 's question #52531 (comment) and my answer #52531 (comment)

Instead of using comparable to constrain a generic map key type, we would use HasComparisonOperator which allows all interface types and all possible composites of interface types to be used as key types just like in regular Go.

[ianlancetaylor]

See #52614 for another take on this problem.

[atdiar]

See #52614 for another take on this problem.

@ianlancetaylor
Ok. Will take a look.

Also taking advantage of this to say that, concerning the current proposal, if we used the provision from the backward-compatibility promise, HasComparisonOperators could be renamed comparable.
Then the old version of comparable would have to be renamed or could even be removed.

[Merovius]

In response to

comparable would not define a type set any longer. Only a set of permissible types which would include all interface types and well-defined composites.

Sorry for being glib, but "one is a type set, the other is a set of types" is as close as you can get to "not a practical difference".

I've asked a couple of times now, but I'll ask again, if need be: Can you provide some code this allows you to write, which the other proposals don't? Or vice-versa? Until that happens, we're left with trying to interpret this proposal as best as we can. And my interpretation is "it doesn't have any practical differences to either #49587 or #52509, depending on which version of your proposal we look at".

[atdiar]

In response to

comparable would not define a type set any longer. Only a set of permissible types which would include all interface types and well-defined composites.

Sorry for being glib, but "one is a type set, the other is a set of types" is as close as you can get to "not a practical difference".

I've asked a couple of times now, but I'll ask again, if need be: Can you provide some code this allows you to write, which the other proposals don't? Or vice-versa? Until that happens, we're left with trying to interpret this proposal as best as we can. And my interpretation is "it doesn't have any practical differences to either #49587 or #52509, depending on which version of your proposal we look at".

With the current restrictions on union element interfaces you're right. But if we wanted to lift those restrictions at some point we would then be stuck.
For instance, to be able to define

type CompString interface{
   ~string | fmt.Stringer
   comparable
}

And I know there are limitations now and it is not allowed but we have to take into account that it is the very first iteration. Again, just future-proofing.
The whole point about the little details is to be able to be future-proof.

Edit: now that I think about it again, maybe it is ok. As long as we keep the type set and the set of permissible types different.🤔

[Merovius]

If I understand you correctly, you are hinting at some hypothetical problems in the future, if we ever lift this restriction:

Implementation restriction: A union (with more than one term) cannot contain the predeclared identifier comparable or interfaces that specify methods, or embed comparable or interfaces that specify methods.

First, I don't think, currently, we ever can lift that restriction. No matter what happens to comparable. It is in place for a reason. We would, at least, have to change some other aspects of the design (e.g. forbid to have multiple union elements, as we did with type lists originally).

Second, I don't think that constraint is any harder to handle than, say

type C interface{
   ~string | fmt.Stringer
   M()
}

It might be easier, but it certainly is not harder. Neither in spec, nor in implementation. Unless you can make a very good case for why that would make difficulties, I'm certain that is not a problem.

Third, there isn't actually a difference between those proposals in how they would handle this. They only differ in what types fulfill the comparable constraint - namely whether or not interface types satisfy it. That changes absolutely nothing about how hard it is to calculate that set.

I'm not just handwaving here. As you know, I discovered the difficulty of calculating type sets in the first place. And I spent a lot of time thinking about it and writing proofs. If I would see any issue related to that, I'd be the first to speak up. It's just not relevant here. And TBH, I find it a bit frustrating to see a problem which I spent quite a bit of time and care laying out invoked in such a haphazardly and unrelated manner.

Feel free to write a proof showing that I'm wrong and these problems might exist. Until then, I really feel you should drop that claim.

[atdiar]

Yes, that would be the restriction in question.
For the recall, the initial claim was that an equivalence between interface implementation and type set inclusion made things easier.
I still think that's true.

But my example is a little bit of a red herring.
If we made fmt.Stringer implement comparable,
it wasn't clear to me what would be the type set of

type CompStringer interface{
   fmt.Stringer
   comparable
} 

And how it would compare to fmt.Stringer
I think it is a subtle detail and perhaps that it was obvious to you.

So the answer seems to be that making interfaces implement comparable changes the set of permissible types for comparable but not the type set of these interfaces.

Contrast this with your claim that interface types would be included in type sets. Maybe it is not obvious for anybody...

[Merovius]

You are, again, moving into abstract arguments about type sets and inclusions, instead of talking about actual Go programs and how your proposal would change their behavior. I don't see the point in arguing anymore, it just adds more noise and goes in circles.

As far as I'm concerned, a language change proposal - in particular one, which tries to solve our current problems with comparable - should be motivated by a desirable change in behavior of real Go programs. Until you can write down some Go programs and describe how your proposal changes their behaviors, as opposed to other proposals (or the current implementation), I'm out.

[atdiar]

I think people (especially beginners) will have to understand those concept of set inclusion to reason about the below:

func F1[T fmt.Stringer](a, b T) bool { return Eq(a,b) // ok? don't think so... }
func Eq[T comparable](a, b T) bool {
    return a == b
}

Even if fmt.Stringer implements comparable, people should know that it barely impacts the logic in terms of permissible set of types.
It does not even impact the type set.

That's why what I was proposing would instead simply allow to adjust the set of permissible type arguments for a type parameter.

The current proposal as written would allow:

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
}

where fmt.Stringer & comparable denotes the set of types that implements fmt.Stringer and are comparable(includes fmt.Stringer itself).

The difference with other proposals is that this set would be formed from a conjunction of constraints, one of which would not be an interface. So it would prevent the creation of new interfaces that could not be turned into types.

Compared to being able to define this:

type CompStringer interface{
   fmt.Stringer
   comparable 
} 

where it is not obvious to me which set of permissible types it denotes. Does fmt.Stringer implement CompStringer? How do the respective type sets relate? Can CompStringer ever be an interface type? If so, would a value of type fmt.Stringer be assignable to a variable of type CompStringer?

Sorry for being confused if those are truly the same proposals but I think not.

[Merovius]

func F1[T fmt.Stringer](a, b T) bool { return Eq(a,b) // ok? don't think so... }

Not under any of the proposals currently discussed, I think.

The current proposal as written would allow: […]

Comparing that to

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

Which is allowed under the current rules, there doesn't seem to be any difference. Except that you allow fmt.Stringer as well, which is exactly #52509. So, it seems your proposal is equivalent to that one.

[atdiar]

My point, that I kept repeating, is that it's different because this proposal does not allow the creation of interfaces that could not be turned into types.

That's why we were disagreeing on the names for the comparable constraint. I simply had to deal with this in the current proposal for backward compatibility by naming it HasComparisonOperators so that I could also make it a non-interface.

Hope it's clearer now.

[Merovius]

it's different because I propose to disallow the creation of interfaces that could not be turned into types.

I don't think your proposal is different in that way either. HasComparisonOperators could be turned into a type just as easily as comparable could be. And if we don't want to turn comparable (or any other interface) into a full type, all we have to do is not do it.

If we adopt #52509, everything that speaks in favor of making comparable a type, also speaks in favor of making HasComparisonOperators a type. And everything that speaks against making comparable a type, also speaks against making HasComparisonOperators a type. They are on exactly equal footing - they both are a constraint, which is not a type. Whether we call them "an interface" or "a non-interface new constraint kind". As long as they behave exactly the same, one of them doesn't magically become more or less suited to become a type at some point.

[atdiar]

I don't get it. How would you embed in an interface something that is not an interface?

If you keep comparable an interface, you have the right to embed it. With this proposal, you just can't.
So no viral creation of interface constraints that can't be turned into types. Seems straightforward to me.

#52209 does not make this distinction.

Now what is possible is to have an interface denoting the set of types that allow panic-free comparison (which correspond to the current implementation of comparable although it would have a different name). That would not be an issue to turn this into a type.

These are truly different proposals.

[Merovius]

Okay. I believe it is a bad idea to introduce a new system to express constraints, which needs to carry all the same complexities to achieve its expressiveness (i.e. you still need the same ways to be able to express conjunctions and disjunctions and methods and type sets), but behaves subtly different than an existing one. To me, that seems an obvious non-starter, so I was trying to reconcile it into something workable, by extracting the core ideas. Apologies for the noise.

[atdiar]

Well, no worries. At least, you hopefully understand exactly what is being proposed.
We'll have to agree to disagree because I think this proposal can be totally workable (as I've said, the case of comparable might well be a standalone. We would just need conjunction.).

And I am not the only one thinking that it could be done.
@griesemer seems to have intuited that it wasn't 100% sure we would only have interface constraints.
#44235 (comment)

Anyway, happy it's clear now.

Then again, I would be happy if someone has an even better solution.

[Merovius]

And I am not the only one thinking that it could be done. @griesemer seems to have intuited that it wasn't 100% sure we would only have interface constraints.

Yes, the "something else" from that comment is what we call type elements today. It's not something on top of what we call interfaces today, but it's something on top of what we called interfaces then. You should pay attention to the historical context that comment was made in. I assume the "active work" he is referencing is #45346 (note the dates).

The non-starter is adding a different constraint system to what we have today.

[atdiar]

Not necessarily..

Thinking out loud, one way of looking at it is that "to satisfy a constraint" doesn't necessarily have to mean "to implement an interface" as is the case in the current generics proposal. It could mean "to implement the interface if the constraint is an interface", and "to do something else if the constraint is something else". And then a constraint could be two different things, or a combination of two different things (such as a type list and an interface); very much like we don't just have one kind of type, we have many kinds of types.And then ordinary interfaces are not "polluted" by type lists, they remain exactly as they always were, but they now can also be used as type constraints. And in addition we have another mechanism, call it type lists, which are different from interfaces, and which may also be used as constraints. And then we need to figure out how to tie it all together nicely, both syntactically and semantically.

(emphasis mine)

Where does it say that it has to be type elements? That's your interpretation.
What he is talking about is exactly applicable to this proposal.
And I do not propose a different constraint system, I propose to extend it such as is deemed possible in the above quote.

[atdiar]

Note As I am thinking about this again:

Implementing an interface does not (should not?) necessarily mean satisfying the constraint it denotes:

• An interface type implements itself. It works well with assignability. But it may not satisfy the constraint it denotes. For example: non-basic interfaces.

• Furthermore, there would be a little bit of friction if all constraints were deemed to be interface types.
  An interface type I satisfying a constraint C would still not necessarily mean that I implements C. If it did, we would have assignability of I to C. As seen concretely with comparability/having comparison operators, it does not seem to work (because constraint satisfaction is independent of type set inclusion: e.g. interface{func()} should not be assignable to comparable where interface types satisfy comparable and comparable is reified into a type)

From this, we can wonder if:

1. type set inclusion and interface implementation shouldn't become a full-fledged equivalence relation since it is needed for assignability purposes. (currently, type set inclusion is just a sufficient condition for interface implementation but not a necessary one)
2. all interface types define constraints, but perhaps, not all constraints should define (interface) types.

Note that this second point does not mean that constraints cannot be turned into types. Just that they might not all be turned into interface types. Mostly because interfaces determine set membership differently.
That's just to say that it does not conflict with propositions as types.
(the same way, a set of numbers is not itself a member of a set of numbers, an interface does not necessarily belong to the set it denotes).

In a nutshell, this proposal attempts to:

1. leave assignability definition unchanged (for interface types, it relies on interface implementation)
2. simplify interface implementation by making it equivalent to type set inclusion
3. specify constraint satisfaction as a different kind of set membership. (already defined as the set of permissible type arguments in the spec)

In doing so, we also retain one current interesting property: assignability test being true means that we have statically determined that operations such as a comparison will not panic.

[atdiar]

Actually, I think it could be simplified:

There are essentially two ways that type sets can be defined:

1. One or several predicates (basic interfaces, comparable)
2. A list of types (non-basic interfaces)

Then the difference between interface implementation and constraint satisfaction is that:

• interface implementation tests for type set inclusion
• constraint satisfaction tests for type set membership, where the type parameter can range over a domain

Even if the type parameter value is an interface type, we do not rely on its type set inclusion but on whether the interface belongs to the type set.

In terms of theory, I believe that it means that a type parameter is a variable urelement.

As such, there shouldn't even be a need to introduce much change.
Just that:

• a type set can be defined by two kinds of set membership rule (and therefore interface types can now belong to type sets if they satisfy a set membership rule)
• interface implementation is equivalent to type set inclusion
• constraint satisfaction is equivalent to set membership

I think it is leading me to the same result as in #52509 (comment)

So rescinding what I wrote earlier, we can perhaps generalize slightly the concept of a basic interface to accomodate for comparable.

The only thing is to be careful about any predicates that are in relation to each other, when checking type set inclusion, I guess. Most often, there shouldn't be any issue. Might involve De Morgans laws in some other cases (e.g. conflicting methods?).

[atdiar]

Yes well, might as well close this issue. Might not be necessary but I will open a new one just for the sake of clarity.