Description
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 typeT
if(f?)T
belongs to the set of permissible type arguments defined byC
. - 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 constraintcomparable
. The choice would be left to the programmer.
References
G. Castagna, T. Petrucciani, and K. Nguyen (2016) Set-theoretic types for polymorphic variants
Jech, Thomas J., et al. Set theory. Vol. 14. Berlin: Springer, 2003.
Activity
atdiar commentedon Apr 24, 2022
cc @griesemer @ianlancetaylor
beoran commentedon Apr 25, 2022
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 commentedon Apr 25, 2022
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 commentedon Apr 25, 2022
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 makingcomparable
work however we think it should isi.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 commentedon Apr 25, 2022
@beoran
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 commentedon Apr 25, 2022
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?
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.
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.
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 commentedon Apr 25, 2022
Yes.
Yes, that's the situation where are in, currently. Though I'm not sure "reifiable" is the right word.
zephyrtronium commentedon Apr 25, 2022
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.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.
What if I want to constrain a type parameter to any comparable type with a method
String() string
?atdiar commentedon Apr 25, 2022
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.
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.
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
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 commentedon Apr 26, 2022
I have to agree with earlier comments that given
then the difference between
F1
andF2
is quite subtle.Also it's hard to define the idea of a non-interface constraint, because of one generic function instantiating another.
atdiar commentedon Apr 26, 2022
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.
I think that none of those cases should compile actually because the bounds for the type parameter
T
defined inF2
are too wide for usage byF1
.The reverse situation where
F1
uses an instantiation ofF2
should be fine however.edit: to try and be clearer,
comparable
satisfiesHasComparisonOperator
but the opposite is not true; the cause being: most interface types have the comparison operators but are notcomparable
?33 remaining items