proposal: spec: generics: use type sets to remove type keyword in constraints

We propose clarifications for the semantics of constraint satisfaction in the generics proposal.  We also propose changing the syntax of type lists to remove the type keyword and to explicitly specify when type arguments should match on underlying types.
The changes this would make to the current generics proposal document can be seen in https://golang.org/cl/306689.
Background
The current generics proposal proposes a new syntax for type lists within interfaces.  A type list within an interface is the keyword type followed by a list of types separated by commas.  Type lists are only permitted in interface types that are used as type constraints.  For example:
// SignedInteger is a type constraint that permits any
// signed integer type.
type SignedInteger interface {
	type int, int8, int16, int32, int64
}

A type argument matches a constraint with a type list if

The type argument implements the interface ignoring the type list, and
either the type argument or its underlying type is identical to one of the types in the type list.

This rule was adopted in part to support permitting type lists in ordinary interface types, not only in constraints.  However, discussion has made clear that the rule is too subtle.  This suggests that it is too subtle not just for use in ordinary interface types, but also for use in constraints.
The behavior when embedding interfaces with type lists is also subtle.
We can do better.
Type sets
We start by defining a type set for all types.  We will define what it means for a type to implement an interface in terms of type sets, resulting in a behavior that is equivalent to the current definition based on method sets.
Every type has an associated type set.  The type set of an ordinary non-interface type T is simply the set {T} which contains just T itself.  The type set of an interface type (in this section we only discuss ordinary interface types, without type lists) is the set of all types that declare all the methods of the interface.
Note that the type set of an interface type is an infinite set.  For any given type T and interface type IT it's easy to tell whether T is in the type set of IT (by checking whether all methods of IT are declared by T), but there is no reasonable way to enumerate all the types in the type set of IT.  The type IT is a member of its own type set because an interface inherently declares all of its own methods.  The type set of the empty interface interface{} is the set of all possible types.
With this idea of type sets, we can restate what it means for a type T to implement an interface type IT: T implements IT if T is a member of the type set of IT.  Since the type set of IT is the set of all types that declare all the methods of the interface, T is a member of the type set of IT if and only if the method set of T is a (possibly improper) superset of the method set of IT, which is the standard definition of implementing an interface.
Now let's consider embedded interfaces.  For a case like type O1 interface{ E }, the type set of O1 is the same as the type set of E.  The case type O2 interface{ E1; E2 } is more interesting: the type set of O2 is the intersection of the type sets of E1 and E2.  To see this, observe that the type set of E1 is the set of all types that implement all the methods of E1, and similarly for E2.  What we want for the type set of O2 is the set of all types that implement all the methods of O2.  The methods of O2 are all of the methods of E1 combined with all of the methods of E2.  The set of types that implement all the methods of both E1 and E2 is the intersection of the type sets of E1 and E2.
Note that listing a method in an interface type definition in the usual way is, from a type set perspective, indistinguishable from embedding an interface that declares just that method.  Although a method by itself is not a type, for our purposes we can say that the type set for a method listed explicitly in an interface type definition is exactly the type set of an interface type with only that method: the set of all types that implement that method.  The advantage of doing this is that we can now say that the type set of an interface type is exactly the intersection of the type sets of each element listed in the interface.
We've now described type sets, and we've explained the meaning of implementing an interface in terms of type sets.  None of this changes the language in any way, but it serves as background and motivation for the next steps.
Proposal
We propose to replace type lists as defined by the generics proposal with three new, simpler, ideas.
An interface type that is used as a constraint, or that is embedded in a constraint, is permitted to embed some additional constructs that we will call interface elements.  An interface element can be:

Any type, not just an interface type.
A new syntactic construct called an approximation element.
A new syntactic construct called a union element.

With these new elements we will be able to state simply that a type argument A satisfies a constraint C exactly when A implements the interface type C, or, in terms of type sets, exactly when A is a member of the type set of C.
First, we propose that an interface type used as a constraint is permitted to embed a non-interface type.  For example: type Integer interface{ int }.  As discussed in the previous section, the type set of an interface type is the intersection of the type sets of the elements of the interface.  The type set of int is simply {int}.  This means that the type set of Integer is also {int}.
This constraint can be satisfied by any type that is a member of the set {int}.  There is exactly one such type: int.
Of course, that is useless by itself.  For constraint satisfaction, we want to be able to say not just int, but "any type whose underlying type is int."  To implement this, we propose a new syntactic construct, which may be embedded in an interface type used as a constraint.  This is an approximation element, written as ~T.  The type set of an approximation ~T is the set of all types whose underlying type is T.  An approximation ~T is only valid if the underlying type of T is itself T; this is discussed in more detail below.
For example: type AnyInt interface{ ~int }.  The type set of ~int, and therefore the type set of AnyInt, is the set of all types whose underlying type is int.  For example, if MyInt is defined as type MyInt int, then MyInt used as a type argument will satisfy the constraint AnyInt.
The final step is another new syntactic construct that may be embedded in an interface type used as a constraint: a union element.  A union element is written as a sequence of types or approximation elements separated by vertical bars (|).  For example: int | float32 or ~int8 | ~int16 | ~int32 | ~int64.  The type set of a union element is the union of the type sets of each element in the sequence.  The types and elements listed in a union must all be different: no two types may be identical, and no two approximation elements ~T1 and ~T2 may have T1 identical to T2.  For example:
type PredeclaredSignedInteger interface {
	int | int8 | int16 | int32 | int64
}

The type set of this union element is the set {int, int8, int16, int32, int64}.  Since the union is the only element of PredeclaredSignedInteger, that is also the type set of PredeclaredSignedInteger.  This constraint can be satisfied by any of those five types.
Here is an example using approximation elements:
type SignedInteger interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

The type set of this constraint is the set of all types whose underlying type is one of int, int8, int16, int32, or int64.
Any of those types will satisfy this constraint.  This is the equivalent of the notation used in the generics proposal
interface {
	type int, int8, int16, int32, int64
}

The use of explicit approximation elements clarifies when we are matching on underlying types, the use of | instead of , emphasizes that this is a union of elements, and the type keyword can be omitted by permitting constraints to embed non-interface elements.
The purpose of introducing type lists in the generics proposal was to specify the operations available to type parameters in parameterized functions.  This is easy to define based on the idea of type sets.  Given a type parameter P with a constraint C, a parameterized function is permitted to use an operation with a value of type P if the operation is permitted for every member of the type set of C.
That is the complete proposal: a conceptual change to use type sets, and three new syntax changes.  We will now mention some details and ramifications.
Approximation elements
The new ~T syntax will be the first use of ~ as a token in Go.
Since ~T means the set of all types whose underlying type is T, it will be an error to use ~T with a type T whose underlying type is not itself.  Types whose underlying types are themselves are:

Type literals, such as []byte or struct{ f int }.
Predeclared types, such as int or string.

We do not permit ~P where P is a type parameter.
The type set of ~T is an infinite set of types.
The ~ will bind more tightly than |.
~T1 | T2 means (~T1) | (T2), not ~(T1 | T2) (note that ~(T1 | T2) is not syntactically valid)..
The new syntax is
InterfaceType = "interface" "{" { ( MethodSpec | InterfaceTypeName | ConstraintElem ) ";" } "}" .
ConstraintElem = ConstraintTerm { "|" ConstraintTerm } .
ConstraintTerm = [ "~" ] Type .

Embedding constraints
A constraint can embed another constraint.  Union elements can include constraints.
// Signed is a constraint whose type set is any signed integer type.
type Signed interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

// Unsigned is a constraint whose type set is any unsigned integer type.
type Unsigned interface {
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

// Float is a constraint whose type set is any floating point type.
type Float interface {
	~float32 | ~float64
}

// Ordered is a constraint whose type set is any ordered type.
// That is, any type that supports the < operator.
type Ordered interface {
	Signed | Unsigned | Float | ~string
}

Interface types in union constraint elements
The type set of a union element is the union of the type sets of all elements in the union.  For most types T the type set of T is simply T itself.  For interface types (and approximation elements), however, this is not the case.
The type set of an interface type that does not embed a non-interface element is the set of all types that implement the interface, including the interface type itself.  Using such an interface type in a union element will add that type set to the union.  For example:
type Stringish interface {
	string | fmt.Stringer
}

The type set of Stringish will be the type string and all types that implement fmt.Stringer.  Any of those types (including fmt.Stringer itself) will be permitted as a type argument for this constraint.  No operations will be permitted for a value of a type parameter that uses Stringish as a constraint (other than operations supported by all types).  This is because fmt.Stringer is in the type set of Stringish, and fmt.Stringer, an interface type, does not support any type-specific operations.  The operations permitted by Stringish are those operations supported by all the types in the type set, including fmt.Stringer, so in this case there are no operations other than those supported by all types.  A parameterized function that uses this constraint will have to use type assertions or reflection in order to use the values.  Still, this may be useful in some cases for stronger static type checking.  The main point is that it follows directly from the definition of type sets and constraint satisfaction.
Combining embedded non-interfaces with methods
A constraint can embed a constraint element and also list methods.
type StringableSignedInteger interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
	String() string
}

The rules for type sets define what this means.  The type set of the union element is the set of all types whose underlying type is one of the predeclared signed integer types.  The type set of String() string is the set of all types that declare that method.  The type set of StringableSignedInteger is the intersection of those two type sets.  The result is the set of all types whose underlying type is one of the predeclared signed integer types and that declare the method String() string.  A function that uses  a parameterized type P that uses StringableSignedInteger as a constraint may use the operations permitted for any integer type (+, *, and so forth) on a value of type P.  It may also call the String method on a value of type P to get back a string.
Empty type sets
It is possible to write a constraint with an empty type set.  There is no type argument that will satisfy such a constraint.  The compiler should give an error whenever it detects such an unsatisfiable constraint.  However, in general a compiler may not be able to detect all such cases.  It is not feasible to detect all such cases, though they can't be used with any type argument.  It may be appropriate to have vet give an error for cases that it can detect.
// Unsatisfiable is an unsatisfiable constraint with an empty type set.
// No predeclared types have any methods.
// If this used ~int | ~float32 the type set would not be empty.
type Unsatisfiable interface {
	int | float32
	String() string
}

Method sets of constraint elements
Much as the type set of an interface type is the intersection of the type sets of the elements of the interface, the method set of an interface type can be defined as the union of the method sets of the elements of the interface.  In most cases, an embedded element will have no methods, and as such will not contribute any methods to the interface type.  That said, for completeness, we'll note that the method set of ~T is the method set of T.  The method set of a union element is the intersection of the method sets of the elements of the union.  These rules are implied by the definition of type sets, but they are not needed for understanding the behavior of constraints.
Possible future step: permitting constraints as ordinary interface types
We have proposed that constraints can embed some additional elements.  With this proposal, any interface type that embeds anything other than an interface type can only be used as a constraint or as an embedded element in another constraint.  A natural next step would be to permit using interface types that embed any type, or that embed these new elements, as an ordinary type, not just as a constraint.
We are not proposing that today.  But the rules for type sets and methods set above describe how they would behave.
Any type that is an element of the type set could be assigned to such an interface type.  A value of such an interface type would permit calling any member of the corresponding method set.
This would permit a version of what other languages call sum types or union types.  It would be a Go interface type to which only specific types could be assigned.  Such an interface type could still take the value nil, of course, so it would not be quite the same as a typical sum type.
In any case, this is something to consider in a future proposal, not this one.

At first glance, this seems okay to me. Some comments:

It makes me a bit sad that the default is exact-matching, with underlying-type-matching needing the ~ token, given that we introduce this for constraints only first and ~all usages in that context should probably use ~. It seems easy to accidentally use the unadorned types and then get locked into an unnecessarily restrictive constraint. I don't know a good alternative though - the obvious analogy would be to require =int for exact matching and it seems less clear that doesn't lead to parsing ambiguities.
There recently have been some questions about incomplete, implementation-defined validity checks: One example on Twitter and one example on golang-nuts. In both cases, the spec allows the compiler to reject certain programs, but doesn't require it. These questions convinced me that this is a bad idea to put into the spec. We don't want the validity of Go programs to be implementation-defined, IMO. If nothing else, it makes it very hard to change the used heuristic in the future. So, if we can't give a clear rule as to which unsatisfyable constraints to disallow (and I don't think we can, in general), I would personally advocate to simply allow them. I don't see a lot of disadvantages - after all, checking if a given type fulfills a constraint is still easy, so an impossibly constrained function can not be instantiated. So even the most basic test would surface the problem, it literally can't be called. And we can always do this as a vet check, which can use any heuristic it likes and can be progressively improved over time.
Even though you don't want to bind this to a future extension to sum types, I still think it's reasonable to consider how such an extension could happen - given that this change is prompted by that consideration. Most importantly, such an extension should allow to switch on the matched type. I don't know if you thought about this yet? My first impression is that it would be possible to allow type-assertions/switches of the form x.(~string), which would assert that xs underlying type is string and if so, evaluate to a string. It seems like a natural syntax which would allow everything we'd need and I don't see anything immediately wrong with it. So, ISTM that it's possible to do that extension somewhat naturally - but of course, I've only thought about it for two hours :)

Part 3. of @Merovius's comment nicely addresses the issue in Identifying the matched predeclared type of the Type Parameters Proposal.

Since ~T means the set of all types whose underlying type is T, it will be an error to use ~T with a type T whose underlying type is not itself.

Does this mean that we can't define something like:
type Dictionary[K any, V any] interface {
    ~map[K]V
}

or
type GenChan[T any] interface {
    ~chan T
}

?

Thanks, @Merovius for the excellent initial feedback. Some comments to your points:

Ack. We've looked at = and other options, but, to turn the viewpoint around, it would also be somewhat sad to have to say =int when we exactly mean just int; and to have int mean something different that just int in the context of a constraint. But I'm sure you gathered as much as well. I suspect that we won't often write ~T elements in practice because many times we will just use constraints already declared elsewhere, e.g., constraints.Ordered or the like. Maybe that's a consolation.

It's an excellent point. One might also say that "implementation restrictions" are de-facto parts of the language, and perhaps we need to stop being a "chicken" (my apologies to chickens) and admit as much. With respect to unsatisfiable constraints, we've considered both, not reporting an error, or reporting an error. I agree that if there's no clear rule, we should probably not promise that the compiler reports an error. (Consider also parameterized constraints that may only become unsatisfiable upon instantiation.)

I'll let @iant chime in on this one as he's spent more time thinking about this.

@DmitriyMV No, to the contrary. Such constraints are explicitly permitted because the underlying type of map[K]V is itself (same for chan T).

Thanks! So what are those

T whose underlying type is not itself

types for example?

As I described in https://github.com/golang/go/issues/43651#issuecomment-774607611 and #44235, I think it creates a great pedagogical load to reuse the name "interface" for concepts that are not actually types. So, to me, the strength of this proposal is in addressing the concerns raised in #41716. I believe that the right decision is to leave as few releases as possible, ideally zero, between the release of generics and the "possible future step" of using this syntax (or another, if this is ultimately rejected) for sum types. The longer we go without being able to instantiate every type parameter with its own definition, the more tutorials, books, guidelines, and style documents will be written based on it being impossible.

@Merovius

It makes me a bit sad that the default is exact-matching, with underlying-type-matching needing the ~ token, given that we introduce this for constraints only first and ~all usages in that context should probably use ~. It seems easy to accidentally use the unadorned types and then get locked into an unnecessarily restrictive constraint. I don't know a good alternative though - the obvious analogy would be to require =int for exact matching and it seems less clear that doesn't lead to parsing ambiguities.

Conversely, I like that the default behavior here preserves Go's strong one-to-one relationship between names and types (aside from type aliases, which were introduced late and are usually discouraged). ~ being a new syntactic element meaning "approximately" leaves open a number of future options, including but not limited to type switches and assertions on underlying types as you mentioned.

@DmitriyMV Any defined type has an underlying type that is not itself. Look also for the definition of underlying types. For instance, myint declared as
type myint int

is a defined type whose underlying type is int. Writing ~myint is likely a programmer error because there's no type whose underlying type is myint, thus the type set of ~myint is empty. One could permit it, but that seems like an opportunity missed to catch a bug.
It's important to fully understand the notion of underlying type for this proposal.

@griesemer To be clear: I'm advocating not for "not promising to return an error", but for "promising not to return an error". That is, the compiler should consider an empty type-set valid, but vet might flag it :)

I'm wondering whether this proposal has any rough edges related to instantiation of constraints using interface types. Say I do something like below:
type I[T any] interface {
    T
}

Are either of the following valid:
func ToString[A fmt.Stringer, B I[A]](b B) string {
    return b.String()
}

func ToString[A I[fmt.Stringer]](a A) string {
     return b.String()
}

It's kind of a bias from other languages, but my first inclination is to read ~int as not int. I'm sure that I'd get used to it, though, and I agree that it's better than =int. I think it makes more sense for it to default to exact, rather than approximate, as it makes embedding a concrete type the same as embedding an interface, as every line just defines a type set and, as stated in the proposal, the type set of a concrete type can contain just itself. Switching that default requires there to be a difference between the two because it would conflict with existing usage outside of interfaces. As proposed, you can think of any usage as a type set, despite some being illegal under the current proposal, at least for now:
var Interface fmt.Stringer // Valid values limited to those in the set of fmt.Stringer.
var Concrete int // Valid values limited to those in the set of int.

The second would conflict with the embedding of types if ~int was replaced with =int, though, as int would have a different type set in different contexts.
Kind of makes me wonder about the potential legality in the future of var Underlying ~int or var Union ~int | ~float64. If they were allowed, interfaces would become exactly the same as a named type set, although something like type Signed ~int | ~int8 | ~int16 | ~int32 | ~int64 would also probably make sense at that point.
Disclaimer: I am not necessarily advocating for ~int being usable outside of interfaces.

Speaking as just a random developer who is pretty new to Go--so take this with a grain of salt--I can't help but feel like the whole constraint interfaces thing is just a complicated end run to avoid having to add operator overloading to the language.
If we had the ability to express that an interface includes specific operators (with whatever syntactic form makes it unambiguous), then we don't need type sets / constraint interfaces to enumerate types.
The generics proposal, with or without this type sets proposal, takes Go further away from structural typing.

Is there a practical use for having both T and ~T? If not, ~ can be dropped.

For numerical work you would like to implement float64 and float32 cases but probably not derived types (i.e. only interface{ float32 | float64 }), while if you wanted to implement an orderable container you would want all orderable types including their derivatives, so interface{ ~int | ~int8 | ... | ~string }.

For numerical work you would like to implement float64 and float32 cases but probably not derived types (i.e. only interface{ float32 | float64 })

I still can't see the benefit of excluding derived types from such an implementation. If a type has the underlying type of float64, is there a case where you don't want to treat it like one? I don't have much experience with numerical work, but I am thinking of a type Temperature float64 and can't see the benefit of excluding it from a generic function requiring float64 instead of ~float64.

Yeah, I can see your point.

It makes me a bit sad that the default is exact-matching, with underlying-type-matching needing the ~ token, given that we introduce this for constraints only first and ~all usages in that context should probably use ~. It seems easy to accidentally use the unadorned types and then get locked into an unnecessarily restrictive constraint.

Isn't it better to be accidentally too restricting and have the possibility to lift the restriction later than to be accidentally too permissive? Are there situations where changing T to ~T is a breaking change for the consumer of a parametrized type or function?

The case for including both T and ~T comes primarily from discussion on #41716 about sum types using the previous proposed type list syntax. Essentially, for generics, ~T is usually the correct choice, but for a sum type, T is usually better. It would be contrary to the philosophy of Go to use different syntaxes for a list of types as generic constraints and a list of types as union options, but having different semantics for the same syntax based on where that syntax appears is even more contrary. This proposal keeps the desirable behavior for generics without obstructing the eventual possibility of sum types by allowing users to choose the appropriate option for each respective use case.

At the risk of sounding +1, I would like to say that this seems to be a strong step forward, and that Ian and Robert have my thanks for their ongoing efforts to make generics a reality in a way that fits with Go’s ethos and that gophers can learn easily and use effectively.  No objections to the proposal, although I agree with @zephyrtronium that it would be ideal to narrow the gap between regular interfaces and constraint interfaces, hopefully to nothing, before generics are released, so I look forward to further iteration.

I'm curious whether it would be possible to allow approximations of structs to match not only the underlying type of a particular struct, but also to allow matches for structs that have at least the exact fields that are listed as the approximate struct element?

type Fooer interface {
    ~struct { Foo int; Bar string }
}

type MyFoo struct {
    Foo int
    Bar string
    Baz float64
}

In the above snippet, there is a potential for allowing types like MyFoo to satisfy the Fooer constraint. This could be quite useful,  as structs are the only class of types that vary wildly. I know of at least one other language that allows for a similar expression

@griesemer

Any defined type has an underlying type that is not itself.

Maybe this should be added to proposal in a form of explanation "aka having ~Type where Type is a defined type aka type MyType Type is invalid. Or something like that?

@bserdar AFAICT the main reason to have both is the possibility of expanding to sum types. Constraints almost always want to use ~T and sums almost always want to use T. Having both is a form of future-proofing (though as I said, it makes me a bit sad that if we don't do that expanding, we'll be stuck with extra ~ all over the place. But only a bit).
@fzipp I'm not sure. It might not be, especially if we only consider the proposal as-is with this change. Note that it's also possible to use constraints defined by other packages for your own function, so it's not just the consumers of a generic function that are affected, but also authors. A function that uses a constraint and type-asserts an argument would be an example of a breakage, when this constraint is relaxed. But this is shot from the hip - I have no idea how real/practically relevant this is. It becomes more relevant if we expand to sum types though.
@urandom It's definitely possible. I'm not sure it's a good idea though. It's a pretty significant change in the meaning of ~ based on the context.

@urandom I agree with @Merovius. I think that T1 which embeds T should have a different syntax.

Some questions / remarks:

Instead of prefix "~", what about suffix "+"?

type Floats interface {
	float32+ | float64+
}

This has the benefit of not introducing a new token and does not confuses to read as "not float32 or not float64". Also T- could at some point refer to the underlying type of T, which might be useful to express at some point.

Why a new list operater "|" instead of ","

Do this not work?
type Floats interface {
	float32+, float64+
}

What's the use case of mixin T~ with S in a single list?

Ie.
type Floats interface {
	int,~int32
}

When would you ever need that?
Instead, would it be possible / sensible to move the "~" to the parameter type side? I.e.
type Floats interface {float32, float64}
func Min[F ~Floats](a, b F) F 		// accept all floats, or all types with float as underlying type

Why ramming it into the interface construct?

Could something like this work to declare a type set/list?
type[] Floats {float32,float34}
type[] Strings  {string, fmt.Stringer}

To me, an interface is used when you care about functionality only (methods) and not about representation (actual type). So the word "interface" does not resonate very well to me with a type list (plus the interface concept of Go is already quite involved).

There's an interesting comment on r/golang, bringing up a parallel of this proposed syntax resembling the (also newline-based) boolean/set logic syntax of // +build directives, which was eventually found to be confusing and is expected to be replaced by a more "traditional" syntax for //go:build. Although this technically qualifies as 🚲 🏠 🖌 -ing, in light of the //go:build proposal I believe it might be worth calling out at least in passing a consideration of the currently proposed vs. more explicit syntax in the document.

@markusheukelom As for question 3: type Stringish interface { ~string | fmt.Stringer }.

April fools?:)

@scyth
I'm pretty sure that the [spaceship operator] (https://github.com/golang/go/issues/45319) proposal is the April Fool's one, though I'm not entirely sure...

@Merovius if having both T and ~T is preparation for sum-types, then maybe using only T to mean "all types derived from T" when specifying constraints, and finding a different way to specify sum types could be a clearer choice.

Is there a practical use for having both T and ~T? If not, ~ can be dropped.

I realize I did not express this correctly.
What I was suggesting was to use T to mean "all types derived from T", and drop the support for "type is T"

@Merovius

it would be possible to allow type-assertions/switches of the form x.(~string), which would assert that xs underlying type is string and if so, evaluate to a string. It seems like a natural syntax which would allow everything we'd need and I don't see anything immediately wrong with it.

I hope it will naturally come with implementation going. Possibly resolved at compile time.

@markusheukelom

Why a new list operater "|" instead of ","

There is a clear way to sum types, I think.

@bserdar

What I was suggesting was to use T to mean "all types derived from T", and drop the support for "type is T"

"type is T" is useful for "per type" optimizations. For example with new design it is possible to write generic abs function that supports both ints and floats and works correctly.

One thing this proposal doesn't seem to mention is the field set of constrained types. Say we have the following example:
type Foo struct {
    F int
}

type Bar struct {
    F int
}

type FooBar interface {
    Foo | Bar
}

func GetF[T FooBar](t T) int {
    return t.F
}

Will the above code be valid?

Will the above code be valid?

I think it should be since both F are of the same type.

@bserdar

What I was suggesting was to use T to mean "all types derived from T", and drop the support for "type is T"

"type is T" is useful for "per type" optimizations. For example with new design it is possible to write generic abs function that supports both ints and floats and works correctly (remember about float Inf and NaN).
https://go2goplay.golang.org/p/aDv9ZmBKhbf

@DmitriyMV the same abs function still applies for ~int | ~float, right? Any type derived from float will still behave like float.

@bserdar Right, but with "type is T" aka int | float we can restrict and enforce this restriction AND can properly type assert it during execution. Unlike in previous design where you could pass type MyOwnFloat float and that would result in incorrectly working code.

This is a great step forward - thanks Ian! I very much like the fact that a type means exactly that type by default.
For those asking if there's a use for T over ~T, there's an important reason why the distinction might be helpful.
Suppose we add support for switching on the actual type of a type parameter. This might allow one to write code like the following to use a fast-path operator for some known types (bytes.Index uses some clever machine code under the hood):
func SplitAt[T comparable](x []T, at []T) ([]T, []T) {
    switch type T {
    case byte:
        if i := bytes.Index(x, at); i >= 0 {
            return x[:i], x[i:]
        }
        return x, nil
    default:
        for i := range x {
            if hasPrefix(x[i:], at) {
                 return x[:i], x[i:]
            }
        }
        return x, nil
}

It's awkward and error-prone to write the above code currently - you need to write unnecessary dynamic type coercions that could fail if you get them wrong.
Given such a type switch construct you'd have to decide what it should do when used on a type parameter with an embedded concrete type.
For example:
type AnyByte interface {
    byte, int
}

func f[T AnyByte]() {
    switch T {
    case byte:
        ...
    }
}

If ~ was the default behaviour, then we'd expect the above type switch to match when T has underlying type byte, because that's what you've explicitly mentioned in the type constraint, but that wouldn't be acceptable because then you'd be able to convert []B to []byte when the underlying type of B is byte, something that's forbidden by the usual language conversion rules.
With exact matching being the default behaviour, a type switch construct like the above becomes a viable and useful addition to the language. You'd still need to define the behaviour of such a type switch when presented with interface types though, which is a tricky issue, although you could just forbid that and it would still be useful, or re-use the ~ qualifier to ask for approximate matching of cases.

The changes this would make to the current generics proposal document can be seen in https://golangorg/cl/306689.
error in the link

@bsedar Yes. That was Point 1. here and it's addressed here.
@ajwerner Yes, that should be legal. The equivalent is legal under the proposal-as-accepted and this proposal only changes the syntax used to express it.
@DmitriyMV FTR, this proposal does not change a lot about whether or not you can specialize on type-arguments. In particular, as long as you use ~T, you have to use reflection to specialize. It does change insofar as that you can now express "exactly this type", which makes type-assertions/type-switches work. See also @rogpeppe's comment.
Come to think of it, I find this slightly concerning. It means people might be encouraged to use T, to gain speed in some cases (as it means they can forego reflection), even if ~T would be more general and just as correct.
I think it might be worth it to consider adding type-switches/assertions on type-arguments again. AFAIR they where taken out because of the ambiguity/confusion regarding underlying type matching. That argument has gone away, if we both add a way to be specific about what the constraint expects and add a way to type-switch/assert on the underlying type.

For anyone interested in type switch behavior, two related updated sections of the proposal CL are in the "Identifying the matched predeclared type" section, which includes:

One way to handle this would be to permit writing approximate types in
a type switch, as in case ~float32:.
Such a case would match any type whose underlying type is float32.
This would be meaningful, and potentially useful, even in type
switches outside of generic functions.

and later:

Another natural next step would be to permit approximation elements
and union elements in type switch cases.
That would make it easier to determine the contents of an interface
type that used those elements.
That said, approximation elements and union elements are not types,
and as such could not be used in type assertions.

In other words, the current proposal seems to hold that out as a future option.
It would be nice to include stronger support for type swtiches working with the underlying type in some way, or some flavor of using approximation elements in type switches.
Without that, we might see some people do:
type Float interface {
	~float32 | ~float64
}

but other people do something like:
type StrictFloat interface {
	float32 | float64
}

in order to get easier access to the type, which seems less desirable.
A separate question would be if something like case ~float32 is supported in a type switch (as sketched as possible future option in the proposal CL), what would the type of the parameter be within the case ~float32?

@thepudds My suggestion was that it would evaluate to a  float32. It seems very natural and the most useful way to go about it.

It might be nice sometimes to be able to express approximation of "anything that has the same underlying type as". So, if this were spelled ~~, then:
type MyType int
type Foo interface {
  ~~MyType
}

would be equivalent to using ~int in the type constraint. I don't know whether this is useful.
I think it'd be nice to be able to specify (1) "anything that can convert to T with a type conversion", and (2) "anything that can convert to T with a type conversion where the type conversion does not modify or change bits, only changes the type used to interpret them". So for instance, 1 would allow int64 to satify a request for float32 because you can do float32(int64value), but (2) wouldn't. (But would accept int for exactly one of int32 or int64, and would accept any pointer type for uintptr...)

Under this proposal, if you specify ~T, you don't need a type switch or type assertion to get to T, you just need a conversion. I think, at least, that any underlying-type conversion can be done with just the T(value) syntax?

For de/serialization code (which would continue to be non-parametric post-generics, AFAICT), it would be very convenient to be able to write:
func Serialize(v interface{}) []byte {
    if s, ok := v.(~string); ok {
        return encodeString(s)
    }
    // etc. handle numbers and so on
}

At that point, you would just need the reflect package to go through the fields of a struct, but otherwise could do almost everything else with just type assertions, I think.

@seebs If you know a type, you always know the underlying type. So you can always express that concept, but you wouldn't write ~~MyInt, but just ~int. On exception is to use a type-parameter (in which case you don't know the underlying type) but given that this proposal forbids even ~P in that case, there doesn't seem to be a use for that either.

Under this proposal, if you specify ~T, you don't need a type switch or type assertion to get to T, you just need a conversion. I think, at least, that any underlying-type conversion can be done with just the T(value) syntax?

Only if all possible type-arguments are convertible to that type. e.g. with type X interface { ~[]byte | ~int }, there is no way to check if the function was instantiated with a user-declared []byte or int type - you can't type-assert (as the type isn't exactly []byte or int) and you can't convert, as []byte is not convertible to int.

While you might always know the underlying type, you don't always want to encode that knowledge in every piece of code that refers to a thing if you don't have to, so reducing the number of times that you have to could be beneficial.

Robert Griesemer's 2020 GopherCon talk included this example, along with the title "We've arrived (mostly)", which I think was concluding form of that example (without being able to get down to a single unified Sort):
func BasicSort[Elem Ordered](list []Elem) {}

func Sort[Elem Lessor[Elem]](list []Elem) {}

type Lessor[Elem any] interface {
	Less(Elem) Elem
}

Would something like Combo below be supported under this proposal?
type Combo[Elem any] interface {
 	Ordered | Lessor[Elem]
}

And it seems the actual type switch here would not be supported under this current proposal, but would perhaps work under @rogpeppe's suggested extension above?
func ComboSort[Elem Combo[Elem]](list []Elem) {
	switch Elem {
	case Ordered:
		// sort using < operator
	case Lessor:
		// sort using Less method
	}
}

My guess is something like the following would be unlikely to be supported?
func ComboSort2[Elem Combo[Elem]](list []Elem) {
	switch (any)(list).(type) {
	case []Ordered:
		// sort using < operator
	case []Lessor:
		// sort using Less method
	}
}

Also, sorry if the answers are explained or implied by the Stringish example above or elsewhere, but trying to understand better with an additional example, as well as what the actual syntax would be...

Would something like Combo below be supported under this proposal?

Yes, you can write that, but no, you can't use that. There still is no way to specialize on the case matched, which would be necessary to use > or .Less based on what's available.

FWIW if we did support ~T in type-assertions/switches, it would become possible. Presumably, we'd have
package constraints

type Ordered interface {
    ~int | ~uint | ~int8 | … | ~string
}

and you could then do
type Lesser[T any] interface {
    Less(T) bool
}

type Lessable[T any] interface {
    constraints.Ordered | Lesser[T]
}

func Less[T Lessable[T]](a, b T) bool {
    switch v := a.(type) {
    case Lesser[T]:
        return a.Less(b)
    case ~int:
        return a < b.(~int)
    case ~int8:
        return a < b.(~int8)
    // …
    }
}

Not terribly convenient, but it could work.

@Merovius
I believe your type switch should actually look something like:
func Less[T Lessable[T]](a, b T) bool {
    switch T.(type) {
    case Lesser[T]:
        return a.Less(b)
    case Ordered[T]:
        return a < b
    }
}

We should be able to use any operation defined on the sum type.
Since a and b both have the same type, a true assertion on one should prove the same about the other.
I believe there was some part of a proposal that allowed assertions on the type: T.(type)

@Merovius

So, if we can't give a clear rule as to which unsatisfyable constraints to disallow (and I don't think we can, in general), I would personally advocate to simply allow them.

I agree.  Thanks.

My first impression is that it would be possible to allow type-assertions/switches of the form x.(~string), which would assert that xs underlying type is string and if so, evaluate to a string.

I also think that that seems like the natural approach.
@ajwerner

I'm wondering whether this proposal has any rough edges related to instantiation of constraints using interface types.

Those details got too complicated to put into this issue, but I've tried to address them in https://golang.org/cl/306689.  Look for "Type sets of embedded parameters".
@qualidafial

We just need a way to express that an interface includes certain operators.

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

I'm curious whether it would be possible to allow approximations of structs to match not only the underlying type of a particular struct, but also to allow matches for structs that have at least the exact fields that are listed as the approximate struct element?

Thanks, I think this is an idea for later, likely with a different syntax.  I don't think we want to overload the ~ syntax just for struct types.
@DmitriyMV

Maybe this should be added to proposal in a form of explanation....

In fairness the proposal does already explicitly say "Types whose underlying types are themselves are..." and then lists all those types.  Any type not listed there is a type whose underlying type is not itself.
@markusheukelom

Instead of prefix "~", what about suffix "+"?

I think it would work, but personally I think it's easier to see a prefix than a suffix.

Why a new list operater "|" instead of ","

I think that | more clearly expresses what the element means.  It's a union element, in that the type set is the union of the listed elements, and | expresses that.

Instead, would it be possible / sensible to move the "~" to the parameter type side?

I think that might be possible, but we would lose the reasonably elegant notion of type sets built up by combining elements.  So I don't see the advantage.

Why ramming it into the interface construct?

Interfaces already have method sets.  It feels like a natural extension to give them type sets as well, and it gives a good way of describing how they can be used to constrain type arguments.  We can't simply replace constraints with your suggested notation, because we also want to constrain type arguments on methods, and also on combinations of types and methods.
@akavel
Thanks for the pointer to the comment on r/golang.  The proposed syntax effectively lets us express an & operator of several elements, where each element can be an | operator.  That is, we can express (~int | ~float32) & (String() string).  What we can't express is any deeper expression.  We can't say ((~int & (String() string)) | ~float32).  Or, rather, in order to say that, we have to define a separate constraint as type StringableInt interface { ~int; String() string }  and then we can write StringableInt | ~float32.  So I think the situation is that complicated constraints are 1) possible; 2) really really weird.  So I don't think we are going to be pushed toward a simpler notation in this case.
@ajwerner

One thing this proposal doesn't seem to mention is the field set of constrained types.

This is mentioned in https://golang.org/cl/306689.  Basically the same guidelines as for the type list syntax.
@pickleslicesforall

error in the link

Thanks, fixed.

@extemporalgenome Note that it's not currently valid to type-assert on a type, so T.(type) first must be assigned a meaning. You also seem to assume that in the case, T gets assigned a new meaning in the case block.
All of that can be done (and AFAIK the design used to include this) but I believe it's different from what's suggested in the proposal as a possible extension, which is to allow type-assertions of interface-values to use approximations.

@urandom
type Fooer interface {
    ~struct { Foo int; Bar string }
}

That would be inconsistent with the proposed meaning of ~. I believe your code sample would be valid under Ian's proposal, but would mean "this exact struct or any named type with this exact struct as an underlying type."
I would also like to see first-class generics for structs, because reflect code in particular could still benefit from compile-time type verification (such as to require a pointer to a struct), which neither the accepted generics proposal, nor this followup, adequately address.
I believe syntax that would work well for that purpose would be:
type FieldsFooBar interface {
    struct { Foo int; Bar string; ... }
}

The ... is literal, meaning "and any other fields, and would further relax constraint validation to allow fields to appear in any other. Putting ~ in front of the type would allow derived named types as well.
@ianlancetaylor I didn't see anything in this proposal that addressed how struct fields interact with union/approximation types, but I imagine they could be compatible, such as in:
type FloatFieldX interface {
  struct { X float32 | float64 }
}

I realize this could be achieved by parameterizing the interface with the type of field X (thus solving this with two interfaces), but there will be cases in which we only care about the intersected operators, not the types themselves, and it would be quite convenient to allow nested unions.
I can see this becoming ambiguous if and when we allow "runtime" sum-typed values. At that point, does the above interface represent one of two types (one with a float32 field or another with a float64 field), or does it represent a single struct type with a field of runtime-type float32|float64 ?

@extemporalgenome This proposal does not permit people to write struct { X float32 | float64 }.  Constraint elements can only appear in constraints (interface types), not in struct types.  And, as you say, that notation would become ambiguous if we were to permit float32 | float64 to be used as an ordinary type (a sum type), so I don't think it would be a good idea to support that syntax now.

I think this is a great improvement to the existing proposal; it introduces more flexibility and eliminates unnecessary special-cases for the former 'type-lists'.

I have one syntax-bikeshed suggestion, which would be to consider a key (either prefix or postfix) like underlying to replace the ~ token:
type SignedInteger interface {
	underlying int | underlying int8 | underlying int16 | underlying int32 | underlying int64
}

Although fully reserving a new keyword would be a breaking change, currently there is nowhere in a type context that you're allowed to write an identifier like underlying followed by another type, so if it was only contextual then this should not be able to break existing programs.
I think a keyword may be a better choice than an operator for several reasons:

underlying is mostly self-documenting, and easier to Google, whereas ~ has no immediately-clear meaning
there are few operators, and it could be that a "better" use of ~ is discovered in the future (either for constraints or something else entirely!)
keywords allow future manipulations for typesets to be introduced more "symmetrically"; if keywords are used consistently, it's easier to grow a vocabulary than using operators

Although this does exacerbate the problem of "underlying is usually what you want, and it's more to type", I think since it will be relatively often that anyone actually writes new constraints with approximation elements that this cost is really not that big.

I also think that permitting semantics for ~(int | int8 | int16) could be useful and worthwhile; that is, "distribute" ~ over type-sets:
typeset(~S) = { ~T | T in typeset(S) }
where for a "primitive" type like int8 or map[K]V, ~T is just T.
This is a generalization of the current approach. For example, you'd be able to write
type PredeclaredSignedInteger interface {
	int | int8 | int16 | int32 | int64
}

type SignedInteger interface {
	~PredeclaredSignedInteger
}

since the type-set of PredeclaredSignedInteger is {int, int8, int16, int32, int64}, so the type-set of ~PredeclaredSignedInteger is any type whose representation is one of int, int8, int16, int32, or int64.
I think this is simpler than the existing approach (and more orthogonal) since it turns the ~ operator into an operator on type-sets, rather than making it a decoration for built-in types.
However, since (with current Go2 features) this doesn't really make the language that much more expressive, it could be better to just wait until it provides more power; right now, it just helps to abbreviate certain definitions for approximation lists. In the future (if the ability to manipulate/define type-sets expands) then it may be more useful.

Personally, I find ~ in approximately every type set constraint already more than verbose enough - making it an entire keyword is just too much.

I'm concerned about the learnability of this syntax. Even having read all the discussion here, i find it hard to predict the behavior of ~T vs T, type switching, casting etc. I think one of Go's greatest strengths is its simplicity, in terms of predictability and understandability, and I don't feel that ~T vs. T currently meets that bar. Further, I'm concerned about making a substantial change to the Generics proposal in support of a speculative and unapproved future language change (sum types).
Additionally, my outsider view is that a lot of Go's design wins have come from designing for specific and broad usecases, and I don't feel I've read a compelling explanation of the broad usecases for ~T vs. T.

FWIW, I'm in favor of this proposal even if we never allow sum types. Because I really think we'll eventually need a way to specialize code based on the actual type - be it for performance reasons or because we want to support generic functions that can use both operators or methods. We especially need that for sum types (they are basically useless otherwise), but we need it either way.
If, at that point, it is already explicit if we mean the specific type or the underlying type, we save ourselves some confusion at that point.

Maybe the proposal can be tweaked to mean "any type derived from T" with T, and "type=T" with another syntax, like =T

Allow me to illustrate my concerns. Given that the stated upside of having ~T and T is for type switches, it leaves me wondering how do you actually use ~T in a type switch? An example was given above:
func Less[T Lessable[T]](a, b T) bool {
    switch v := a.(type) {
    case Lesser[T]:
        return a.Less(b)
    case ~int:
        return a < b.(~int)
    case ~int8:
        return a < b.(~int8)
    // …
    }
}

As a user reading this, I immediately wonder, what is b.(~int)? What can I do with it? What functions can I pass a ~int to? Can I store it in maps? In lists? What is this new ~ syntax?
I feel that you might fairly view this as an addition of an entire new class of types to the language: approximate types. You could henceforth have variables that are specific var x int or vague var x ~int, and their interaction is unclear, as is the appropriateness of one declaration over the other.
In my mind, the fact that this proposal raises all of these questions classifies it as a major change to the language. I also think we should not accept this proposal until we have clear answers to all of them, which I dont feel I have yet reading the discussion here.
If the distinction between exact and derived types is only useful in a future situation, and we don't want to fully think through that future situation now, than I believe it would be imprudent to make changes in support of it at this time.
My interest here is in keeping the language easy to understand, and I fear that this change as its currently written is not easy to understand.

In my mind, the fact that this proposal raises all of these questions classifies it as a major change to the language.

Yes. It is part of the introduction of generics, which naturally is a pretty major change :)

I also think we should not accept this proposal until we have clear answers to all of them, which I dont feel I have yet reading the discussion here.

I don't understand this. FTR, the proposal as-is does not suggest adding type-switches or type-assertions for ~T. With that, most of the questions are moot.
Even if we would amend this proposal with type-switches and type-assertions, I feel like most of these questions have pretty clear answers

what is b.(~int) - A type-assertions, that b has underlying type int
What can I do with it? - same as with any other type-assertion; use an interface-type (or generic value) as an int
What functions can I pass a ~int to? Can I store it in maps? In lists? - none, no, no. ~int is not a type.
What is this new ~ syntax? an operator signifying "underlying type"

It is true that people will have to learn about this new syntax. But that's true of any language change. I don't feel this is harder to understand than generics in general. And I feel it's significantly easier to understand than the previous type-list semantics.

I think that explanation downplays the difficulty of understanding this syntax. Yes you can give answers to those questions, and that is easy to do when you are in the position of creating those answers, but when you are learning this syntax for the first time I don't think the answers you gave are necessarily obvious or guessable. In particular I think it is not clear that b.(~int) is the same as b.(int), in fact I think thats surprising.
Also, if we are saying we don't need type switches for this to stand on its own merit, then why don't we abandon ~T altogether and just have T include derived types? However I think this change actually requires type switches to be useful, and I think the ability to select a specific type from your interface sum type is important here, so I don't think you can just wave my concerns away so easily.

@thepudds
While I would definitely like some way of handling the SortCombo() case automatically, the best way to handle that situation that I've found so far with the currently proposed systems is to move more of the functionality specification to the call-site via higher-level functions:
type Lesser[T any] interface {
  Less(T) bool
}

func SortLess[T Lesser[T]](slice []T) {
  SortFunc(slice, func(v1, v2 T) bool {
    return v1.Less(v2)
  })
}

func SortOp[T constraints.Ordered](slice []T) {
  SortFunc(slice, func(v1, v2 T) bool {
    return v1 < v2
  })
}

func SortFunc[T any](slice []T, less func(v1, v2 T) bool) {
  // ...
}

Overall, I actually really like this approach, and think that it should probably be used wherever possible as it gives the most control to the call-site without requiring annoying repetition, but I'm kind of worried that it won't work particularly well for those situations where more functionality is required than can feasibly be handled by just a single function.
Oh, and, for the heck of it, here's an alternative implementation of the above that doesn't require three different sorting functions in the API:
func Sort[T any](slice []T, less func(v1, v2 T) bool) {
  // ...
}

func ByOperator[T constraints.Ordered](v1, v2 T) bool {
  return v1 < v2
}

func UsageExamples() {
  Sort(slice, CustomType.Less) // Sorts by method by taking advantage of method expressions.
  Sort(slice, ByOperator[int])
}

I prefer the first implementation, though, as it doesn't require repetition of the slice's element type when calling Sort().

but when you are learning this syntax for the first time I don't think the answers you gave are necessarily obvious or guessable.

They don't have to be obvious or guessable - they only have to be learnable and knowable.
FTR, I'm not trying to downplay how easy that is. But I genuinely don't believe this proposal makes anything harder to understand. With the proposal as accepted, interface { type int, string } constraints the type to have an underlying type string or int. With the proposal as accepted, interface { type MyInt, string } implyies that only MyInt or any type with underlying type string. I'm not saying ~ as a syntax must be learned, but I find interface { ~int | ~string } and interface { MyInt, ~string } far clearer - if nothing else, it at least gives you a hint that there is something happening here, instead of leaving the same confusing semantics implicit.
I don't believe it is reasonable to only allow language changes that do not require anyone to learn new things. As far as learning new things goes, this one seems fine to me.

In particular I think it is not clear that b.(~int) is the same as b.(int), in fact I think thats surprising.

It's also not true. One is an assertion that b has underlying type int, the other is an assertion that b has type exactly int. They are two different things.
And I want to repeat: This proposal is not about adding type-assertions or type-switches on ~T. That is only discussed as a possible future extension. This proposal is purely about replacing type-lists with type-sets/unions/approximate types.

I'm not arguing that we cannot require any new learning, but I think this syntax and its implications are harder to understand than the typical go feature, and I don't feel the value this syntax delivers (as explained so far) adequately justifies that cost. I also don't think the clarity of ~int vs int is worthwhile when it hasn't been firmly established that the distinction is worthwhile. I think actually thinking this feature through, which I think involves type switches, makes it clear that this has an unusually high learnability cost.
Yes we can make people learn new things, but not all learning is equivalent! And I acknowledge this proposal does not include type switches, but some of the justification I've read for the existence of ~T relies on type switches, so I don't think saying "its not in the proposal" is a sufficient counter argument.

To be clear, I don't think the justification for ~T relies on type switches.  The justification for ~T is that it permits us to clearly express whether a constraint should match exactly T or all types whose underlying type is T.  This is a subtle point in the currently published proposal (not including this proposal), because type int and type MyInt behave significantly differently.  type int accepts many different types.  type MyInt accepts a single type.
This difference is not a fatal problem with the currently published proposal.  After all, we did publish it.  But I think that difference is a small problem.  And I think that this proposal fixes that problem.
You are correct, of course, that people will have to learn about ~T.  It is obscure, and I'm not aware of any similar feature in other languages.  I think the main thing in its favor is that it clearly means something, and once you learn what it means it's fairly clear, and it shouldn't be hard for people to look it up when they encounter it.  And, for what it's worth (not much), this is not something that is going to appear at all in everyday Go code, so many people won't encounter it.

For those wondering about the potential use of ~ in type switch statements, here's one way that I think it could work:
Syntax:
switch type T {
case A1:
case A2:
   ...
}

The switched type (T above) must be the name of a type parameter. The type in a case arm can be any type, including constraint types.
Within an arm of the case statement, the type parameter that's being switched on becomes further restricted by the type selected, just as if it had originally been constrained by that type too (e.g. interface {T; A1}).
It would be a compile-time error if the type set of the type specified in the arm isn't a subset of the type parameter.
type Stringish interface {
	string | fmt.Stringer
}

func Concat[S Stringish](x []S) string {
    switch type S {
    case string:
        return strings.Join(x, "")
    case fmt.Stringer:
        var buf strings.Builder
        for _, s := range x {
             buf.WriteString(s.Stringer())
        }
        return buf.String()
    }
 }

The above assumes that the constraint:
interface {
     X | Y | Z
     X
}

would allow all operations allowed on X, but I believe that's true under the current proposal.

Thanks for the explanations. It does make me feel better that we anticipate this being an obscure feature (though I'm surprised that ~ is only for user-defined types, I must've overlooked that). I suppose my main contention is that I don't really understand the usefulness of restricting types to just be exact match. All the usecases I can imagine I would want to use the ~ pattern, so the distinction feels unnecessary to me.
Would something like this be valid?
type Numish interface {
	int64 | float64
}

func Sign[S Numish](x S) int {
    switch type S {
    case float64:
        return math.Float64Sign(float64(x))
    case fmt.Stringer:
        return math.Int64Sign(int64(x))
    }
 }

Basically I'm trying to understand how, if you accept a type-or-derived-type in a function, you can unwrap to the root type.

Would something like this be valid?
func Sign[S Numish](x S) int {
switch type S {
...
case fmt.Stringer:

According to my suggestion above, no, that wouldn't be valid because the type set of fmt.Stringer isn't a subset of the type set of Numish, so the constraint could never apply.
But I suspect you might have been trying to write this:
func Sign[S Numish](x S) int {
    switch type S {
    case float64:
        return math.Float64Sign(x)
    case int64:
        return math.Int64Sign(x)
    }
 }

which would be fine according to my switch type suggestion (note: no type conversions needed).

Oh haha, you're right, that was a sillly mistake. Why is not type conversion needed? This is just statically checked to be valid? What if a derived type is passed in, aren't you required to convert it to the underlying type before passing it into a function that takes the underlying type?

Would ~func (SomeInterface) allow you to match functions that take interfaces that are structural identical but declared separately? I’m guessing not, but I’m not sure how it would interact with functions. For other interfaces, it’s just forbidden, but a way to smooth out the difference between structurally equivalent interfaces would be nice.

Is the approximation being applied here is a form of subtyping (notated :> or <:)?
If we consider the subtype relation to be S <: T if T is the underlying type of S, then ~T means "every type S such that S <: T".
It might also be worth it to borrow the notation (without the :?), so instead of ~T, you'd see T> or <T.

@rogpeppe

According to my suggestion above, no, that wouldn't be valid because the type set of fmt.Stringer isn't a subset of the type set of Numish, so the constraint could never apply.
But I suspect you might have been trying to write this:
func Sign[S Numish](x S) int {
    switch type S {
    case float64:
        return math.Float64Sign(x)
    case int64:
        return math.Int64Sign(x)
    }
 }

which would be fine according to my switch type suggestion (note: no type conversions needed).

There is one question tho - how does type parameter switch work when you have several arguments of the same type aka
func Min[T any](a T, b T) T {
...
}

And how does it work when you have different types:
func Something[T any, T2 any](a T, b T2) {
...
}

@carlmjohnson

Would ~func (SomeInterface) allow you to match functions that take interfaces that are structural identical but declared separately?

No. func (SomeOtherInterface) has itself as an underlying type and that type is different from func (SomeInterface).
@smasher164

Is the approximation being applied here is a form of subtyping (notated :> or <:)? If we consider the subtype relation to be S <: T if T is the underlying type of S,

No. "Underlying type" has no relation to subtyping. Subtyping requires you to be able to use a term of the subtype whenever a term of the supertype is valid. That's not the case with underlying types, you can't pass an int to a function which expects a MyInt, you need to explicitly convert.

@hherman1

It does make me feel better that we anticipate this being an obscure feature.

To the contrary I think this (~ aka "underlying" operator) being a much needed clarification that restores, at least partially, readability of the Go w/generics source.
In current iteration of the generics proposal the unadorned type identifier has different meanings re context. Now - with the help of an unary operator ~ this confusion vanished. This clear disambiguation stands alone high to the all other future possibilities that "underlying" operator and set operations on types both promise.

@hherman1

Why isn't type conversion needed? This is just statically checked to be valid? What if a derived type is passed in, aren't you required to convert it to the underlying type before passing it into a function that takes the underlying type?

Type conversion wouldn't be needed in that case, because float64 (a.k.a. interface {float64} a.k.a. interface {int64 | float64; float64} a.k.a. interface { Numish; float64}) has a type set with exactly one member (float64 itself) which, by the definition of type sets, allows any operation that that member allows.
If you'd done:
case interface{~float64}:

then you would have needed the type conversion, because all types with underlying type float64 can be explicitly type-converted to float64.
@DmitriyMV

There is one question tho - how does type parameter switch work when you have several arguments of the same type

From my suggestion:

Within an arm of the case statement, the type parameter that's being switched on becomes further restricted by the type selected, just as if it had originally been constrained by that type too

Suppose we take your example and want to special-case on float64 so that we can use math.Min:
func Min[T Ordered](a T, b T) T {
     switch type T {
     case float64:
          return math.Min(a, b)
      }
      if a < b {
          return a
      }
      return b
}

That example would be OK because within the float64 arm of the type switch,
it's as if the Min function was declared like this:
func Min[T interface { Ordered; float64 }](a T, b T) T {

and since interface { Ordered; float64 } has exactly one member in its type set (float64), it means that T effectively is a float64 within that arm, so we can treat both a and b and the return type as exactly floa64.

And how does it work when you have different types:

Only the switched-on type parameter would be affected. But you could always nest:
func Something[T any, T2 any](a T, b T2) {
    switch type T {
    case float64:
         switch type T2 {
         case string:
              // Here T is float64 and T2 is string
         }
     }
}

You could also use this type switch to check whether two argument types are identical; for example:
func Something[T any, T2 any](a T, b T2) {
    switch type T {
    case T2:
        x := []T{a, b}
        ...
    }
}

I'm not sure how useful that particular capability would be in practice though, but it falls out naturally.

More tangential possibilities: here are some thoughts about how "using constraint types as ordinary interface values" might actually work:
An interface type is allowed as an ordinary interface value if one of the following apply:

it consists only of method constraints
it has a finite type set that includes, but is not limited tonil.

The first case covers all existing interface types. The second allows what have been referred to elsewhere as "sum types".
The nil type is defined to be a type which allows every operation, and will panic if that operation is used. This corresponds to the existing behaviour of nil with respect to interface values.
An operation on an interface type is allowed if one of:

it has an infinite type set and the operation is a method call to a method that's explicitly mentioned in the interface.
it has a finite type set and the operation is unary

A unary operation is an operation that uses the type as an argument at most once.
All interface-typed values can be compared against the literal nil, and nil is the zero value for all interface types.
For example:
type Float interface {
	float64 | float32 | nil
}

var f Float		// f is now nil.
f = 3.14		// OK; f now has dynamic type float64
f = -f			// unary minus is OK
g := f
f += g		// Not allowed because it's equivalent to f = f + g, and + isn't unary.
f += 2		// Could be allowed if we consider +constant to be a unary operation.
switch f := f.(type) {
case float64:
case float32:
case nil:
}

It would be nice to allow interface types that don't have nil as a possible value, but that would require some way to mark one of the union elements as "preferred" for the zero value. Using nil seems to fit better with the way that interfaces work currently in Go.

FWIW, I feel like this discussion is straying further and further away from the actual proposal.

@Merovius

"Underlying type" has no relation to subtyping. Subtyping requires you to be able to use a term of the subtype whenever a term of the supertype is valid.

Gotcha, thanks for clarifying. So it would be inaccurate to say MyInt is a subtype of int, but accurate to say that MyInt is a subtype of interface{~int}?

@Merovius

FWIW, I feel like this discussion is straying further and further away from the actual proposal.

I agree, but I think so many people talking about specialization shows that we are ready to include a specification for it. That might be more appropriate for a separate proposal if this one is accepted, or including it in this proposal might help it to be accepted.
@smasher164

Gotcha, thanks for clarifying. So it would be inaccurate to say MyInt is a subtype of int, but accurate to say that MyInt is a subtype of interface{~int}?

I believe this is also not quite correct. interface{~int} is not a type per se, only a constraint. There are no values with type interface{~int}. So, there still is not exactly a subtype relationship. (We seem to be trying hard to avoid the word "metatype.")

FWIW, I feel like this discussion is straying further and further away from the actual proposal.

You are right of course, and I accept some blame, except that I do think that it's good to show how the elegantly uniform model proposed can make it straightforward to add some other significant features to the language. I think that speaks very well for the "rightness" of this new change.

I'm confused by the use of the term "intersection" in the proposal. In the PP starting with

Now let's consider embedded interfaces.

it says:

The set of types that implement all the methods of both E1 and E2 is the intersection of the type sets of E1 and E2.

Does "intersection" in this paragraph mean a proper set intersection E1 ∩ E2 (E1 & E2) or a set union E1 ∪ E2 (E1 | E2)? It seems to use the term for one but describes the other.  What am I missing?

I'm confused by the use of the term "intersection" in the proposal. In the PP starting with

Now let's consider embedded interfaces.

it says:

The set of types that implement all the methods of both E1 and E2 is the intersection of the type sets of E1 and E2.

Does "intersection" in this paragraph mean a proper set intersection E1 ∩ E2 (E1 & E2) or a set union E1 ∪ E2 (E1 | E2)? It seems to use the term for one but describes the other. What am I missing?

It means E1 ∩ E2. Example:
type E1 interface { Foo() }
type E2 interface { Bar() }

type A struct{}
func (a A) Foo() {}

type B struct{}
func (b B) Bar() {}

type C struct{}
func (c C) Foo() {}
func (c C) Bar() {}

The type set of E1 is {A, C}, and the type set of E2 is {B, C}.
The set of types that implement all the methods of both E1 and E2 is {C}, which is {A, C} ∩ {B, C}.

I think the confusion is that the union of the interface definitions is implemented by the intersection of the sets of types implementing the interfaces. So you can think of the combined interface as the union (of the interface definitions) or the intersection (of the sets of things implementing the interfaces), which might be counterintuitive because you describe "all of the methods of E1 and E2", which sounds like "union of E1 and E2", and then call it an "intersection". The phrase "the type sets of" is load-bearing in this distinction. The type set of the union of the interface definitions of E1 and E2 is the intersection of the type sets of E1 and E2, where "the type set of E1" means "the set of all types which implement the interface definition of E1".
I figure I've either made the confusion better or worse here.

@smasher164 Only if interface{~int} was a type - as proposed for now, it's not (only a constraint, you can't use it as the type of a variable). But yes, interface satisfaction is a subtype relationship.

@rogpeppe I mingled a bit with your SplitAt snippet - and I think that even without type switch on type parameters we can have some sort of optimizations. Provided we use it correctly of course.
https://go2goplay.golang.org/p/11tacA0ojGW

@DmitriyMV You can achieve many goals by using unsafe or reflect. The goal of a good generics implementation should be to make them unnecessary.

@Merovius I'm not disputing that - I would prefer to not use unsafe and/or reflect. I'm just saying that we can delay "type switch on type parameters" and write reasonably effective code for now.

To add a bit to @seebs point:

The type set of E1 is {A, C}, and the type set of E2 is {B, C}.

That description makes it sound like the type set of E1 and E2 are finite, but they're not - the type set of E1, for example, is the infinite set of all types that implement a method Foo with no argument or return parameters.

Hi @rogpeppe, under the possible future type switch extension you proposed above, do you think something like this would be supported?
type Lesser[T any] interface {
	Less(T) bool
}

type Ordered interface {
	~int | ~int8 | ... | ~string
}

type Lessable[T any] interface {
	Ordered | Lesser[T]
}

func Sort[T Lessable[T]](list []T) {
	var less func(a, b T) bool
	switch type T {
	case Ordered:
		less = func(a, b T) bool { return a < b }
	case Lesser:
		less = func(a, b T) bool { return a.Less(b) }
	}

	// sort using less
}

If so, that seems reasonably nice.
(One could even argue it provides some of the benefits people look for regarding operator overloading, but is more explicit and avoids some of the costs that come with the implicitness of actual operator overloading).

Could someone help me understand what are some example situations where having an exact match, and excluding derived types, would be useful?
I imagine that 90% of the time supporting derived types is the right choice for a constraint, so it seems like backwards UX to me that exact match is the default and derived types are a special case.
also, while forming this distinction may bring some technical expressivity to the proposal, I still don’t really understand why this new expressivity is useful, and this I continue to feel that this new complexity isn’t carrying its own weight.
Also, I recognize that I seem to be one of the few with these concerns, so although it is frustrating to me, I understand if it’s easier to ignore my complaints.

@thepudds

Hi @rogpeppe, under the possible future type switch extension you proposed above, do you think something like this would be supported?

Yes, that would work as you'd expect.

@hherman1

Could someone help me understand what are some example situations where having an exact match, and excluding derived types, would be useful?

One example, alluded to by @kortschak earlier, is when you're using floating point numbers in matrix or vector operations. Go does not allow converting []T to []float64 even when the underlying type of T is float64, so specifying interface{float64 | float32} means you'll always be able to convert matrices and vectors into a known form, amenable to machine optimised fast paths, without resorting to unsafe.
Another scenario is when you might wish to restrict an argument to a known set of locally defined types. Allowing only exact matches means you can be sure that if you put the argument into a regular interface{} value (for example to add it to a global cache), you'll always be able to retrieve it with a type switch, because the number of possible types is known.

Ok, thanks I think I understand those examples. My impression is that those are niche use cases, (they come up when you’re dealing with very specific external restrictions) so it reinforces my belief that the default case in this syntax is backwards. I’m a big fan of “make the common path easy”. Is my impression mistaken?
Further: I think it would be useful for the decision to promote support for exact matching constraints to language syntax to be grounded in some analysis of the expected need for this feature. I think it is harder to justify making this feature, rather than providing an escape hatch through reflection or something like it, if the feature is only going to be used in <1% of code. And, if it is the case that <1% of code is going to use this, it seems more likely that this feature will cause confusion when it’s encountered.
Basically I’m trying to argue that we should consider the net benefit of maintaining the distinction between derived and exact match types. I think the case has been made that there is some benefit: niche use cases will have more first class support. I believe the downside is that there is a new language feature, and that it will confuse many people over the course of its lifetime. For me personally the question of “should this feature be added” comes down to weighing the established pros against the cost.
I don’t think I am experienced enough to accurately predict how many people fall into the “will get value” camp, versus the “will be confused/offput” camp. My intuition is that the second group is much larger than the first, but I’m hoping that others here will both find my perspective compelling and have some insight into either the size of these two groups or why we don’t need to worry about it.

@hherman1 To be clear: I shared your concerns (though I've now changed my mind), which is why I brought this up as the first point in the first comment in this thread. And after it got brought up @griesemer addressed it. So, the reason I haven't continued to discuss it, is that I don't think there is a need. It has been seen and I don't think any significant new arguments have come to the table since then. That doesn't mean the concerns are invalid or unimportant. But it's also obviously not productive to just repeat the same things over and over again.

Yes, I read those comments, and I sympathized with your point, and I do find it somewhat compelling to make int mean int, though I think this concern needs to be put in context. There is something nice about the straightforwardness of int is exact match int, but how many people will get value out of that? And how many people will instead be more so disserviced by this change? I don’t feel this question was explored, and I think it’s essential in order to settle this point. I think it is both true that this feature provides utility in some situations and confusion for people, but I think it’s hard to pick between these cross cutting concerns without a consideration of what in practice is at stake here.
Maybe to make my position more clear, there are two issues I’m concerned about:

Should the default be ~ or =
Do enough people need support for = to justify including it in the spec

i think you and @griesemer made excellent points about 1, though for me the question of what is going to have the better net affect on users isn’t yet settled.
I don’t think 2 has been addressed yet, though it’s possible I missed a comment where it was.

Also, FWIW, the cases @rogpeppe mentioned are not the only arguments in the "pro" column. The arguments, AFAICT, are

It is also confusing to have int mean something different from int
It is also confusing to have to write =int (or something) to mean int
There are cases where it is useful to specify exact types
Even though we are not proposing adding type-switches or type-assertions on underlying types today, we might want to in the future and this proposal means we are not painting ourselves into a corner for that - and in fact give ourselves a nice, natural syntax to express it.
Even though we are not proposing to make it possible to use constraint-interfaces as types today, we might want to in the future and this proposal means we are not painting ourselves into a corner for that
While it might be confusing or something new to learn, it is ultimately not that hard to understand or learn - and it might in fact even be easier than the proposal-as-accepted, because it at least makes a potentially confusing new way to match types explicit, instead of implicit.

So we don't think that the cases where it is useful to match on exact types justify the cost - we think that all of these benefits together justify the cost.
Clearly you disagree with some of the specific arguments and clearly you disagree with the overall conclusion. And that's fine. I'm also not 100% sold on them. But I don't see how we can convince you. The things have been said, they are mainly a matter of opinion now - unless someone wants to go through the effort of finding a reliable way to collect data on this. It seems to be mainly a matter of opinion to me, and it's impossible to argue about opinions.

I think the switch type T idea should be put aside.  It's basically a compile-time switch like #if typeof(A) == T masquerading as a run-time control structure, which seems ugly to me.
What I think the examples above are trying to express is specialization of a generic function, which can already be done explicitly:
func SortOrdered[T Ordered](list []T) {
	// sort using "a < b"
}

func SortLesser[T Lesser[T]](list []T) {
	// sort using a.Less(b)
}

In principle, another way to achieve the specialization would be allow them both to be called "Sort" and have the compiler pick the matching implementation:
func Sort[T Ordered](list []T) {
	// sort using "a < b"
}

func Sort[T Lesser[T]](list []T) {
	// sort using a.Less(b)
}

There would be problems with resolving ambiguities (first match in package wins??)
Doing it this way gives another orthogonal feature: the user being able to define specialized versions of a function with different argument types.  This is pretty much what generics are anyway, but currently allowing only one template to generate an unlimited number of specialized versions.

I think the switch type T idea should be put aside. It's basically a compile-time switch like #if typeof(A) == T masquerading as a run-time control structure, which seems ugly to me.

Whether it's strictly compile-time or not depends somewhat on the implementation details, I think - an implementation may well choose to do an actual runtime check rather than expanding out the code for the different possibilities. That decision is similar to the decision as to whether to expand out (monomorphise) generic functions for every type they're instantiated with.
To me, the type switch on type parameters would fit nicely into Go as a dual to the type switching you can currently do on interface values. The two features seem to be closely related.

What I think the examples above are trying to express is specialization of a generic function, which can already be done explicitly:
func SortOrdered[T Ordered](list []T) {
	// sort using "a < b"
}

func SortLesser[T Lesser[T]](list []T) {
	// sort using a.Less(b)
}

Yes, and perhaps for the Lesser | Ordered case this would perhaps be preferable. But I see a lot of the potential use case for this feature to be optimisations within the implementation details of a feature.
If I've got a generic function that takes a []T, I don't necessarily want to add a specialised entry point when T is byte so that I can take advantage of efficient functions in the bytes package, because I want the API to look the same regardless (this is somewhat similar to how io.Copy makes use of type switching under the hood to optimise data transfer).

In principle, another way to achieve the specialization would be allow them both to be called "Sort" and have the compiler pick the matching implementation:
func Sort[T Ordered](list []T) {
	// sort using "a < b"
}

func Sort[T Lesser[T]](list []T) {
	// sort using a.Less(b)
}

There would be problems with resolving ambiguities (first match in package wins??)

Yes, there are a bunch of issues with that approach - Go has always eschewed overloading function names by type, and I believe that's a Good Thing. In Go, if you know a name, you can always find where that's defined without having to know the types of its argument or return parameters and how they might match against a load of possible implementations.
Let's not go in that direction, please.

Doing it this way gives another orthogonal feature: the user being able to define specialized versions of a function with different argument types. This is pretty much what generics are anyway, but currently allowing only one template to generate an unlimited number of specialized versions.

Another way to look at it is that even in the proposal as it currently is, you can already do this kind of specialisation by converting a value to interface{} and type switching on that. Adding an explicit switch type statement avoids the need for the awkwardness we see in that example without dramatically changing the feel of any of the rest of the language.
But as @Merovius pointed out, this is verging on off-topic. Maybe it should be another proposal.

I think the switch type T idea should be put aside. It's basically a compile-time switch like #if typeof(A) == T masquerading as a run-time control structure, which seems ugly to me.

Whether it's strictly compile-time or not depends somewhat on the implementation details, I think - an implementation may well choose to do an actual runtime check rather than expanding out the code for the different possibilities.

I'm not sure. Taking the example given earlier by @thepudds:
func Sort[T Lessable[T]](list []T) {
	var less func(a, b T) bool
	switch type T {
	case Ordered:
		less = func(a, b T) bool { return a < b }
	case Lesser:
		less = func(a, b T) bool { return a.Less(b) }
	}

	// sort using less
}

I can't see how the two branches of the "switch" can be compiled in the same function instance.  For a given T, only one branch or the other is semantically valid.
There is also some performance expectation around generics (although maybe it's not justified yet?)  For example, if I define a List[T] then I'd expect functions taking List[int32] and List[int64] to generate different implementations.  If under the hood it's just a List[interface{}] where every element is boxed, then the performance benefit of generics is lost.
You do of course still gain valuable type checking.

Given that it's threatening to derail the discussion here, I've created https://github.com/golang/go/issues/45380 to talk about the type switch proposal specifically.

Another idea to solve ~T: a "special" package of interfaces, e.g:
package underlying

type Uint32 interface {
    // Implemented by types with underlying uint32.
}

type Chan[T any] interface {
    // Implemented by types with underlying chan T.
}

Interface underlying.Uint32 is implemented by all types that have underlying uint32. This could be used instead of a syntactical ~uint32.

@thwd I think relying on a package of "magic" interfaces like that has already been considered (and rejected) for the original proposal. What's more, there is a boundless set of such types that are needed - we can list the underlying pre-declared types, but what about []byte? It's not pre-declared, but still very useful. And what about function/channel/interface/struct types?
Lastly, I also feel that it's too verbose.

Given a type parameter P with a constraint C, a parameterized function is permitted to use an operation with a value of type P if the operation is permitted for every member of the type set of C.

One thing I haven't seen in the generics proposal so far is any kind of more concrete definition of what "operation" means. Is an operation considered to be allowed for a type P if, when P is substituted for the type, the code compiles?
Or is it considered to be allowed when the code is reduced to some kind of abstract form and the operations implicit in that abstract form type check OK?
Here's a problematic case that got me wondering about this: is this OK or not? If not, why not?
type C interface {
	type map[int]string, []string, [2]string, struct{b1, b2 string}
}

var b1, b2 = 1, 2

func f[A C]() A {
	return A{
		b1: "a",
		b2: "b",
	}
}

One thing I haven't seen in the generics proposal so far is any kind of more concrete definition of what "operation" means.

I'm starting to feel that constraints over non-interface types will be used less in practice. If I'm writing a generic container or algorithms package, the easiest way to ensure that the type I'm parameterizing over meets my requirement is to enforce that the user implements an interface. It asserts for expected behavior as opposed to expected representation. Sure it's more verbose, just like sort.Interface, but it's more predictable for both parties.
On the other hand, union elements in constraints (and potentially sum types) open up an array of possibilities, even if they were just restricted to interface types.

@rogpeppe

Is an operation considered to be allowed for a type P if, when P is substituted for the type, the code compiles?

Yes.  Or, more precisely, if P is the type parameter in question, the operation is permitted if the code compiles for every member of P's type set (or, before this proposal, for every element in P's type list).
But you definitely have an interesting test case.  I don't know whether a composite literal should count as an operation.  I'm inclined to think not.  But can you open a separate issue for that?  It's independent of this proposal.  Thanks.

@fzipp

It means E1 ∩ E2. Example:
type E1 interface { Foo() }
type E2 interface { Bar() }

type A struct{}
func (a A) Foo() {}

type B struct{}
func (b B) Bar() {}

type C struct{}
func (c C) Foo() {}
func (c C) Bar() {}

The type set of E1 is {A, C}, and the type set of E2 is {B, C}.
The set of types that implement all the methods of both E1 and E2 is {C}, which is {A, C} ∩ {B, C}.

Note that method-based interfaces are included in their own type sets: your type E1 includes every type that has a Foo() method, and E1 itself has a Foo() method so it is included.
(Strictly speaking, the type set of E1 in your example is {A, C, E1}, and the type set of E2 is {B, C, E2}, but their intersection is still just {C}.)

@ianlancetaylor

But you definitely have an interesting test case. I don't know whether a composite literal should count as an operation. I'm inclined to think not. But can you open a separate issue for that? It's independent of this proposal. Thanks.

done: https://github.com/golang/go/issues/45396
One more thought from the proposal:

It is possible to write a constraint with an empty type set. There is no type argument that will satisfy such a constraint.  It is not possible to detect all such cases.

Could you provide an example of a case where the type set is empty but it's not possible to detect that?
Does this mean that type sets are non-computable in general?

@rogpeppe Determining whether a type set is empty is trivially equivalent to solving SAT. So it's always possible, but it's not always feasible. We definitely shouldn't require a SAT solver to compile Go :)

Type sets are computable but computing an entire type set is not necessarily trivial.
Whether this constraint has an empty type set depends on the set of types defined in the current package.  This is locally computable but do we really want to do it?
type MaybeEmpty1 interface {
    ~struct{ f int }
    M()
}

I shouldn't have written that it's not possible.  It would be better to say that it's not feasible.

@merovious Remember that {union, intersection} is not functionally complete
over sets. We're missing the complement operator for that. (Or is there a
proposed one?)
On Mon, Apr 5, 2021, 20:42 Axel Wagner @.***> wrote:

@rogpeppe https://github.com/rogpeppe Determining whether a type set is
empty is trivially equivalent to solving SAT. So it's always possible,
but it's not always feasible. We definitely shouldn't require a SAT
solver to compile Go :)
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/golang/go/issues/45346#issuecomment-813568305, or
unsubscribe
https://github.com/notifications/unsubscribe-auth/ACLH7DAWLO7BQZP6PXQ2GODTHIAC7ANCNFSM42H5HFIQ
.

For the Approximation Elements section, CL 306689 (which updates the design doc for this proposal) currently includes a third case (emphasis added) for “[t]ypes whose underlying types are themselves”:

Since ~T means the set of all types whose underlying type is T, it
will be an error to use ~T with a type T whose underlying type is
not itself.
Types whose underlying types are themselves are:

Type literals, such as []byte or struct{ f int }.
Most predeclared types, such as int or string.
Type parameters (but see below).

I think that third case is a mistake. As far as I can tell, the underlying type of a type parameter P should itself be an (anonymous) type parameter. (I may at some point file a proposal for a predeclared generic type Underlying[T], which would be defined as an alias for the underlying type of T, so for the purpose of this discussion I will call the anonymous type parameter Underlying[P].)
As far as I can tell, the reason to have a well-defined underlying type for each type in a Go program is so that we can compute convertibility, which has a couple of cases that depend on whether two types are “identical”, ignoring struct tags. However, I think we can compute the “identical” judgment for type parameters using type sets rather than unique types.
The anonymous parameter (Underlying[P]) is constrained to the union of the underlying types in the type-set of P. Two type parameters P1 and P2 have an identical underlying type only if Underlying[P1] and Underlying[P2] are constrained to singleton sets containing an identical type. (The type in that set may itself be the underlying type of some type parameter; the underlying type of Underlying[P] is Underlying[P] itself, by definition, so I believe that the type-set computation is guaranteed to reach a fixed point.)

@thwd Yes, I realized that after, see my edit.

Type sets are computable but computing an entire type set is not necessarily trivial.
Whether this constraint has an empty type set depends on the set of types defined in the current package. This is locally computable but do we really want to do it?

Ah, that's very interesting! You seem to be thinking of the actual type set of the constraint when applied to a complete program so that you know the entire set of types. If no types match, then the type set is empty for that program.
I was thinking of it a bit differently: ignoring the actual set of types for a given program, what's the full, sometimes infinite, type set for any given constraint? How computable is that (obviously using some abstraction to stand in for the unbounded part)?
Would it not be reasonable to suggest that when that set is known to be empty, the compiler should give an error?
Or maybe that set's harder to compute than it seems on the surface. I'd like to see proof of the SAT-equivalence that @Merovius suggests that it might have.

@rogpeppe, bear in mind that the type-set of a generic type may depend on its type parameters.
The declaration:
type I[T1 any, T2 any] interface {
	T1
	T2
}

could be unsatisfiable if T1 and T2 are instantiated with mutually-incompatible interfaces. But it seems clearer to attribute that problem to the point of use (where we can say U does not implement T1; missing method Foo) rather than to the interface declaration itself.
Actually, come to think of it, perhaps we should relax the existing restriction on interfaces with conflicting methods, for the same reason:
https://go2goplay.golang.org/p/iApKMqybnMv
Or perhaps we should always flag errors for impossible non-generic interfaces, and always defer error-reporting for impossible generic interfaces until they are actually instantiated.

@rogpeppe We want all compilers to implement the same language, so if we want the compiler to give an error when the type set is known to be empty, we need to define precisely when the type set is known to be empty.

I believe that dropping the ~ and defining it as "the set of all types whose underlying type is" is the best way to go. This is because to me the interface is already similar to a constraint and as such "The type must have underlying type x" makes just as much sense as "The type must have function x". This also means for that for me there is no issue in different behavior to sum types because it's the interface that makes it a constraint and not the type set.
As for the cases where exact types are useful, I would love to see more examples. The most prominent example I have seen here is type switches. I would suggest simply using type assertions instead:
if f, ok := x.(interface{float32}); ok {
	return float32(f)
}

I would also like to avoid littering the code with ~ everywhere just because a few special cases need different handling. The approximation operator would make Go code harder to read and more complex. Even if it is easy to learn it is yet another thing you have to know. I believe that keeping Go as simple as possible is important and because of that I would even consider simply not supporting those few special cases.
What I would strongly recommend: Just try it
Try both variants on the go2go playground and see what those that will use it think.

@2767mr I think that in effect we have already tried it.  In the currently published proposal, not including this proposal, type lists do not use ~.  Instead, matching is done on underlying types.  But these means that there is a subtle difference between type int and type MyInt, which can be confusing.  This proposal aims to eliminate that subtle difference.

@bcmills Do you have an opinion on whether we should permit ~P for a type parameter P if we drop the wording saying that the underlying type of a type parameter is itself?  That is, we could just say that ~P is also permitted for type parameters.
Also CC @griesemer on this general question.

@rogpeppe, bear in mind that the type-set of a generic type may depend on its type parameters.
The declaration:
type I[T1 any, T2 any] interface {
	T1
	T2
}

could be unsatisfiable if T1 and T2 are instantiated with mutually-incompatible interfaces. But it seems clearer to attribute that problem to the point of use (where we can say U does not implement T1; missing method Foo) rather than to the interface declaration itself.

Indeed. But at the point of use, it should still be possible to do some checking, because of the nature of type sets (they can be restricted but never extended). So the type set of the above interface is infinite/unknown, but if someone unified it with an impossible combination (reducing the infinity to zero), we could still give an error.

Or perhaps we should always flag errors for impossible non-generic interfaces, and always defer error-reporting for impossible generic interfaces until they are actually instantiated.

As author of a generic package, if I use a generic interface that's known to have an empty type set, I think it should be an error.
@ianlancetaylor

We want all compilers to implement the same language, so if we want the compiler to give an error when the type set is known to be empty, we need to define precisely when the type set is known to be empty.

In order for all compilers to implement the same language, the standard will need to precisely define how the type set is calculated, and given that, I feel like it might be a relatively small amount of extra effort to define criteria for when a type set is known to be empty.

@rogpeppe I'm not an expert. But here's my attempt.
Assume we can decide if a type set is empty or not. We use this to solve SAT for CNF (AIUI this is sufficient. I don't think it's needed either way). Assume we are given a CNF formula in variables A…Z (e.g. (A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ C ∨ D)). We write the program
type A = interface {
    A()
}

type NotA = interface {
    A() int
}

// …

type Z = interface {
    Z()
}

type NotZ = interface {
    NotZ() int
}

// the example formula
type Formula interface {
    A | NotB | NotC
    NotA | C | D
}

Assume a type Solution is in the type set Formula. Then, one of these three things must be true:

Solution has a method A(). In this case, assign true to the variable A.
Solution has a method A() int. In this case, assign false to the variable A.
Solution has no method A, or the method has a different signature. In this case, it doesn't matter for the solution whether you set A to true or false.

Do this for B…Z. This gives you an assignment to the variables which satisfies the formula. So, if the type set is not empty, the formula has a solution.
Likewise, if we have an assignment to the variables which satisfies the formula, we can add methods to a type Solution and add methods to it:

If A is true, add a method A()
If A is false, add a method A() int

Do the same for B…Z. This type now is in the type set. So, if the formula has a solution, the type set is not empty.
Thus, the type set is not empty if and only if the formula has a solution.

@ianlancetaylor, I can think of three options there:

Reject ~P unconditionally.
Permit ~P only when the type-set of P's constraint contains only valid underlying types. (That is: permit ~P when P is guaranteed to be a valid underlying type, even if we don't know what that specific type is.)
Permit ~P unconditionally, but have it decay to just P if P is instantiated with a non-underlying type.
Permit ~P unconditionallly, but have it decay to the empty type-set if P is instantiated with a non-underlying type.

I think (1) and (2) are clearly ok, and we could reasonably choose either of those. I would be inclined to start with (1), because we can easily relax (1) to (2), whereas tightening (2) to (1) would be an incompatible change. (If we reject ~P at compile time, then no program that successfully compiles can rely on that fact.)
I think (3) and (4) are too subtle, and regardless it would be easy to relax from (1) or (2) to either (3) or (4). So I'm not sure whether we could adopt one of those options over the long term, but I don't think that (3) or (4) is a good starting point.

@rogpeppe Hm, I think I'm wrong, that proof doesn't fully work. A type can be neither in A nor in NotA, so we don't have Tertium Non Datur and that affects the solveability. I'll have to think about it some more.

@bcmills in CL 306689 I outline how to handle ~P in the "Type sets of embedded parameters" section.
Basically, for embedded parameters in general you have to think in terms of two different type sets.  The first is the type set defined by the parameter's constraint.  This is used when deciding what operations are permitted in a generic function/type body.  The second is the type set defined by the type argument at instantiation time.  This is used when deciding what type arguments are permitted.
So I think from that perspective it's 5) permit ~P unconditionally, but at instantiation time reject instantiating it with a type argument which is not its own underlying type.
If that is too subtle then I think we have to reject ~P.

In order for all compilers to implement the same language, the standard will need to precisely define how the type set is calculated, and given that, I feel like it might be a relatively small amount of extra effort to define criteria for when a type set is known to be empty.

I'm not sure I agree.  For this code I think it's pretty easy to define the type set of I2 but I don't think it's all that obvious that the type set is empty.
type I1 interface {
    M() int
}

type I2 interface {
    ~I1
    M() string
}

@ianlancetaylor  I would not consider
type MaybeEmpty1 interface {
    ~struct{ f int }
    M()
}

an error even if there did not happen to be a type that satisfies MaybeEmpty1 because it's still possible for such a type to exist.
I would assume that errors would be restricted to constraints like
interface {
  string
  fmt.Stringer
}

where no type could ever be created to satisfy the constraint (without changing the language spec).
The type set happening to be empty and the type set always being empty by construction are different.
Your example does raise a question though. If the package defining MaybeEmpty1 defines type E struct { f int } without a method M and I embed E in a struct in a different package and give that a method M does that satisfy the constraint?

@rogpeppe Just thought of a simple fix for the problem I've been having :) So here's my stab at a proof.

Checking if a type set is empty reduces to solving SAT for CNF.
Proof: Assume we have an algorithm to determine if any type set is empty. Assume we are given a boolean formula in variables A…Z, in CNF (for example, say (A∨¬B∨¬C) ∧ (¬A∨C∨D)). We write the following program (which can be done in linear time):
type A = interface {
    a()
}

type NotA = interface {
    a() int
}

// similar for B…Z

type TertiumNonDatur interface {
    A | NotA
    // …
    Z | NotZ
}

// example formula
type Formula interface {
    A | NotB | NotC
    NotA | B | C
    TertiumNonDatur
}

That is, we write two, mutually exclusive interface types per variable. We write a special type TertiumNonDatur, which includes one line A | NotA for each variable. We then write a type Formula, containing one line per disjunction clause in the formula, consisting of a union of the appropriate types for the individual literals in the clause. We also embed TertiumNonDatur in Formula.
Now, if there is an assignment to the variables that satisfies the formula, we can write a type
type Solution struct{}

func (Solution) a() {} // if A is true in the assignment
func (Solution) a() int {} // if A is false in the assignment

// The same for B…Z

This type now inhabits Formula. It has a method a() or a method a() int for every variable, so implements either A or NotA. The same for all the variables. So Solution is in TertiumNonDatur. Also, as each individual clause in the formula is true with this assignment, and Solution is in A exactly if A is assigned true and it's in NotA exactly if A is assigned false, it must be in all the individual union elements in Formula. And thus inhabits Formula, as it inhabits all embedded type sets.
So we've shown that if the formula has a solution, Formula is not empty.
Similarly, say Formula is not empty. Say Solution is a type in Formula. We construct an assignment by

Assign "true" to A, if Solution has a method A()
Assign "false" to A, if Solution has a method A() int
It must have one or the other, as it is in TertiumNonDatur, thus it must be in A | NotA.

This assignment now makes the formula true.
Thus we've shown that if Formula is not empty, the formula has a solution, concluding the proof.

@ianlancetaylor

So I think from that perspective it's 5) permit ~P unconditionally, but at instantiation time reject instantiating it with a type argument which is not its own underlying type.

I think that's probably reasonable in isolation, but it seems inconsistent with the rest of the Type Parameters design, which otherwise seems very careful to ensure that a use of a generic function or type cannot fail due to a problem in a distant declaration.
Consider something like:
type I1[T any] interface {
	~T
}

type I2[T any] interface {
	M1(I1[T]) T
}

type I3[T any] interface {
	M2() I2[T]
}

type MyInt int

var x I3[MyInt]

For that example, the error would be detected at instantiation of I3, but the need for the parameter to be its own underlying type is not explicit in the declarations of I3 or I2 (their constraints are just any), so the diagnostic would need to display an error stack all the way up to I1.

@ianlancetaylor

So I thinink from that perspective it's 5) permit ~P unconditionally, but at instantiation time reject instantiating it with a type argument which is not its own underlying type.

I think that's probably reasonable in isolation, but it seems inconsistent with the rest of the Type Parameters design, which otherwise seems very careful to ensure that a use of a generic function or type cannot fail due to a problem in a distant declaration.
Consider something like:
type I1[T any] interface {
	~T
}

type I2[T any] interface {
	M1(I1[T]) T

I don't understand how that example would be allowed. You're using a interface type with an approximation element as a method argument, not in the only place it's allowed: a type parameter constraint.
I'd find it helpful if you could include a bit more exposition.

@bcmills To me, this is similar to how we allow duplicate fields/methods in embedded struct fields, as long as they are never referenced (or converted into a relevant interface). That is,
package somepkg

type A struct {
    X int
}

type B struct {
   X string
}

type C struct {
    A
    B
}

---
package someotherpkg

func main() {
    var c somepkg.C
    c.A = 42 // error: ambiguous field
}

In this case, too, the cause of the error is hidden behind layers of indirection. So there is precedent.

FWIW, in the question of "should the compiler reject empty type sets", I'm still strongly advocating against that (I know that my points where already acknowledged by @ianlancetaylor and @griesemer, so this is just for the benefit of other people still pushing for it :) ):

It's tempting to look at simple examples and say that the compiler should clearly recognize that. And it's not feasible in general, so we are in any case limited to give very simple rules for what to reject. In fact, the proposal does contain one such rule: ~T is only allowed if T is its own underlying type, as otherwise the type set ~T is empty. But the more of these rules we add, the more the question becomes where to stop (especially given that this ruleseet is effectively frozen after first publishing - we can only relax it after that).
It's trivial to test for an empty type set. In fact any form of test (it doesn't even have to be a good test or a unit test - even a manual "I wonder if this code is doing what I expect it to, let's do a quick check" is fine) must necessarily instantiate the generic function or type, so any such test will necessarily either proof that the type set is not empty, or surface the problem. So, unless you really are a "it compiles, ship it" person, this problem will not go unnoticed.
Even if you happen to publish code using an empty type set as a constraint, given that no user of your package can actually reference or use it, it would be a backwards-compatible change to simply remove the generic function/type using it. That is, the actual damage of if this mistake happens is pretty small, in the end. Of course, the damage is higher when you modify an existing constraint and accidentally make it empty. But, again, you hopefully have tests for that and changing constraints is likely a backwards incompatible change anyway.
Lastly, even if we allow them in the language doesn't mean we can't detect them in tooling. A tool like go vet can use any heuristic it pleases, up to and including a SAT solver. It can also start with simple rules and then detect more and more cases as we find more common mistakes people make - something we can't do, if we reject them in the compiler, because of compatibility.

So really, I feel quite strongly that the problem is a lot harder and the benefit is a lot smaller than people might believe at first glance. :) We still can help people, by putting checks in vet - but we don't have to decide what these are yet :)

I like that in this proposal we can explicitly specify either an exact type or all types which have a certain underlying type, which wouldn't have been possible with the previous proposal.
However the concept of type sets seems to be rather complex, with difficulties as described above, for example with detecting empty type sets. Since type sets are potentially infinite, I fear they might be inadvertently Turing complete as well.
Therefore I wonder if we could keep the type lists, but enhanced so ~type is also available for them and type simply means an exact match?

However the concept of type sets seems to be rather complex

I think it is simpler than it might appear from this discussion. For example, we already have method sets in the language and they are, at least conceptually, less clean, in the way they deal with pointer methods. This proposal is IMO rather simple - you construct sets out of primitives like "the set of this type", "the set of all types having this as an underlying type" and "the set having this method" and operators for union and intersection. I may be biased, because I'm already quite familiar with how sets work - but this seems to compose very well into individually understood parts and a very natural way to describe constraints.

Since type sets are potentially infinite, I fear they might be inadvertently Turing complete as well.

There is no reason to believe this. On the contrary. Since the only computation you can trigger is "is a type in a type set" and that is guaranteed to be possible in linear time, I feel there is pretty strong reason to believe them not to be.
Note that interfaces already have infinite type sets and that doesn't cause any problems.

Therefore I wonder if we could keep the type lists, but enhanced so ~type is also available for them and type simply means an exact match?

I don't think this proposal does much more (if anything) than introducing ~T and then renaming some concepts and changing the syntax slightly to more closely resemble the actual logic. We already had type sets, we just called them "constraints" or "interfaces". We already had union elements, we just called them "type lists" and wrote them with a type keyword and , instead of |. The only thing we are really adding is the approximation element.
In particular, given that you reference the difficulty of determining if a type set is empty: The same applies to determining if a constraint is unfulfillable in the proposal as accepted. The reduction to SAT does not use approximation elements, so you can replace all occurrences of x | y with type x, y and get to exactly the same conclusion.

Just to entertain the scenario where the compiler does reject empty type sets:
Although type-set fulfillment may reduce to SAT, how likely are people to encounter pathological behavior in practice? You can narrow down the set of checked types to the ones passed into function calls or type instantiations for definitions that actually use that constraint. I can't imagine an encoded formula being large enough to significantly slow down the compiler. It would have to be a core piece of functionality used across many modules, with an extremely large number of embedded constraints.

Although type-set fulfillment may reduce to SAT, how likely are people to encounter pathological behavior in practice?

Even if people don't run into it by accident, they might run into it intentionally. Currently, you can be certain that if you compile a Go program, it doesn't have any side effects and it runs quickly. If the compiler would have to solve SAT, you couldn't be sure anymore.

You can narrow down the set of checked types to the ones passed into function calls or type instantiations for definitions that actually use that constraint.

I don't understand. If an instantiation actually uses that constraint, it is by definition not an empty type set - it must be possible to instantiate it. That's why I said "the benefit is smaller than you realize". Any usage of a constraint implies that it is not empty.
Note that even though it is infeasible to check if a type set is empty, it is trivial to check if a specific type is in it - otherwise the entire concept would be useless :)

I can't imagine an encoded formula being large enough to significantly slow down the compiler.

Sorry for being blunt, but then you underestimate exponential growth.

@Merovius thanks for detailing that.
And, if I understand correctly, implementing a SAT solver is an NP-complete problem, so that is why we should avoid implementing an empty type set checker for this proposal.

I don't like the approximation ~T thing. Approximation should be the default behavior. interface{int} should be applicable to both int and type T int. Is there any use case where we need to differentiate int from type T int? We declare type T int so that we can use the int-related operations. For instance, given type Money int, we can now add, subtract, multiply, divide our Money type. So why should type T int be excluded from interface{int}?
In general, I feel this generic proposal is way more complicated than it needs to be. We are overthinking the corner cases.

@beoran Correct.

@henryas

... Is there any use case where we need to differentiate int from type T int
type Money int, we can now add, subtract, multiply, divide our Money type ...

Money and int are distinct types and for good reason;
type Money int

func pay(m Money) {}

func main() {
	var salary Money = 34
	pay(salary)

	var countOfElephants int = 10
	pay(countOfElephants) // cannot use countOfElephants (type int) as type Money in argument to pay
}

@henryas

... Is there any use case where we need to differentiate int from type T int
type Money int, we can now add, subtract, multiply, divide our Money type ...

Money and int are distinct types and for good reason;
type Money int

func pay(m Money) {}

func main() {
	var salary Money = 34
	pay(salary)

	var countOfElephants int = 10
	pay(countOfElephants) // cannot use countOfElephants (type int) as type Money in argument to pay
}

Is there any use case of a generic function that should apply to int but shouldn't apply to Money?

@henryas Please take into account the discussion so far. [I've collected some of the main arguments in favor of having ~ in this comment and @rogpeppe has mentioned two cases of where identical type matching is preferable a couple comments before that.

@beoran

However the concept of type sets seems to be rather complex, with difficulties as described above, for example with detecting empty type sets. Since type sets are potentially infinite, I fear they might be inadvertently Turing complete as well.

The good news is, most of type theory is already infinite sets of types, so we're in very good company.
FWIW, I don't think type sets are Turing-complete. They don't provide a way to enumerate or iterate over the types in a type set.

@henryas Please take into account the discussion so far. I've collected some of the main arguments in favor of having ~ in this comment and @rogpeppe has mentioned two cases of where identical type matching is preferable a couple comments before that.

My point is that approximation should be the default behavior. There is no need for an extra ~ keyword. I can't think of any realistic use cases where approximation as the default behavior would cause any harm.
If the purpose of this thread is to collect arguments in favor of having ~, instead of judging the merits of the new ~ keyword and whether it is a worthy inclusion into the language, then I suppose there is no place for me here.
I am not against approximation. I am against adding unnecessary new keywords into the language. Throwing more wrenches does not fix the car.

I don't understand. If an instantiation actually uses that constraint, it is by definition not an empty type set - it must be possible to instantiate it. That's why I said "the benefit is smaller than you realize". Any usage of a constrained function/type implies that the constraint is not empty.

I mean usage in a definition, not an instantiation. Like
type A[T SomeConstraint] struct {
 ...
}

Note that even though it is infeasible to check if a type set is empty, it is trivial to check if a specific type is in it - otherwise the entire concept would be useless :)

I think I misunderstood the problem. Checking that a type set is empty about checking that the constraint is fundamentally unsatisfiable, not about checking that there's at least one type in the current program that satisfies it. I see now that checking emptiness is not all that useful.

Sorry for being blunt, but then you underestimate exponential growth.

Sure, but note that there are other compilers that solve "intractable" problems during type-checking, namely Swift and C#. I'm not saying the problems are equivalent, but people don't seem to run into bad behavior in practice.

@henryas

My point is that approximation should be the default behavior. There is no need for an extra ~ keyword. I can't think of any realistic use cases where approximation as the default behavior would cause any harm.

Then please refer to the comments I linked to. They provided such examples.

If the purpose of this thread is to collect arguments in favor of having ~, instead of judging the merits of the new ~ keyword and whether it is a worthy inclusion into the language, then I suppose there is no place for me here.

The point is to discuss the merits of ~. But it has to be a discussion. You asked for examples, where matching on identical types is useful, so I referred you to parts of the discussion where some where given. And you said you think ~ is unnecessary, but you didn't respond to the arguments as to why we think it is.
"I don't want to add ~" is a perfectly reasonable opinion to hold, but as an argument in the discussion it has already been mentioned and taken into consideration. And to make progress, we need new arguments and new reasoning, or evidence that the existing one is flawed.

I am not against approximation. I am against adding unnecessary new keywords into the language. Throwing more wrenches does not fix the car.

This is a fine opinion to hold, but again, we've talked about why we think it is a necessary (or at least beneficial) addition. Do you have anything to add to those arguments?

I mean usage in a definition, not an instantiation.

That doesn't help limit the computational complexity of checking if the type set is empty though.

Sure, but note that there are other compilers that solve "intractable" problems during type-checking, namely Swift and C#.

I'm not sure they do, but even if, that's certainly their prerogative. It's not how Go tends to work though. Safe execution of the compiler is a design goal for the language.

@Merovius

To me, this is similar to how we allow duplicate fields/methods in embedded struct fields, as long as they are never referenced (or converted into a relevant interface).