constraints: new package to define standard type parameter constraints

[ianlancetaylor]

Note: Discussion is now at #47319

This proposal is for use with #43651. The proposal document for that issue mentions adding a constraints package to define some standard useful constraints. Here we propose a specific API to define. If this proposal is accepted, the new package will be included with the first release of Go that implements #43651 (we currently expect that that will be Go 1.18).

This description below is focused on the API, not the implementation. In general the implementation will be straightforward.

The intent is that if we add any new predeclared types, such as int128 and uint128, those types will be supported by these constraints as appropriate based on the constraint descriptions. To make this work, code should follow these guidelines: 1) given a type parameter whose constraint is taken from the constraints package, don't use that type parameter to instantiate a type/function whose constraint is not any and is not taken from the constraints package; 2) don't write a type switch to handle all types when using a constraint taken from the constraints package. We can add vet checks to detect cases where these guidelines are not followed.

// Package constraints defines a set of useful constraints to be used with type parameters.
package constraints

// Signed is a constraint that permits any signed integer type.
type Signed interface { ... }

// Unsigned is a constraint that permits any unsigned integer type.
type Unsigned interface { ... }

// Integer is a constraint that permits any integer type.
type Integer interface { ... }

// Float is a constraint that permits any floating-point type.
type Float interface { ... }

// Complex is a constraint that permits any complex numeric type.
type Complex interface { ... }

// Ordered is a constraint that permits any ordered type: any type that supports the operators < <= >= >.
type Ordered interface { ... }

// Slice is a constraint that matches slices of any element type.
type Slice[Elem any] interface { ~[]Elem }

// Map is a constraint that matches maps of any element and value type.
type Map[Key comparable, Val any] interface { ~map[Key]Val }

// Chan is a constraint that matches channels of any element type.
type Chan[Elem any] interface { ~chan Elem }

[gudvinr]

I'd like to just quote this blogpost:

Avoid meaningless package names. Packages named util, common, or misc provide clients with no sense of what the package contains. This makes it harder for clients to use the package and makes it harder for maintainers to keep the package focused. Over time, they accumulate dependencies that can make compilation significantly and unnecessarily slower, especially in large programs. And since such package names are generic, they are more likely to collide with other packages imported by client code, forcing clients to invent names to distinguish them.
...
Don't use a single package for all your APIs. ...

[ianlancetaylor]

@gudvinr I don't think this proposal fails on either of those points. This package is named "constraints", and it contains type constraints. Nothing else. It doesn't contain a bunch of different APIs.

But I would be happy to hear an alternative suggestion. Thanks.

[smasher164]

Given that these constraints seem to be centered around describing builtin types, is there a reason something like comparable can't be declared here as well? I'm assuming the reason is something like "comparable requires a language spec change, while these constraints are just definitions." However the unsafe package is also described in the spec and is its own separate package.

[zephyrtronium]

What factors decide which constraints are defined in this package? E.g., why are there all of Signed, Unsigned, and Integer, but not, say, "types convertible to string" (string, []byte, []rune, rune) or "types appendable to []byte" (string, []byte)?

[ianlancetaylor]

@smasher164 Yes, as you say, comparable requires a language spec change. This proposed package isn't comparable to the unsafe package. The unsafe package exists only in the language spec. The source code found in the standard library is only documentation. The proposed constraints package would be an ordinary package like any other in the standard library.

@zephyrtronium I picked the constraints that seemed most likely to be useful. If you want to make the case for additional constraints to be defined by the package, this is the place to do it.

[zephyrtronium]

@ianlancetaylor

@zephyrtronium I picked the constraints that seemed most likely to be useful. If you want to make the case for additional constraints to be defined by the package, this is the place to do it.

I do think that the constraints I mentioned would be useful, but they might be better suited to living in packages strings and bytes. Similarly, I think the proposed Float, Complex, and Ordered might be more intuitive in math, math/cmplx, and sort, respectively, for reasons along the lines of @gudvinr's comment.

This would leave the integer constraints in an awkward spot. They'll certainly be useful, but were we to try to place these constraints in relevant standard library packages, there doesn't seem to be an existing home for them.

[smasher164]

@zephyrtronium
Given that math already holds information like MaxInt, I could see the integral constraints being placed there.

And I agree we should explore putting constraints in the stdlib differently from the way C++ provides generic algorithms and concepts in std::algorithms and <concepts>. Go is really good about putting definitions where they are most suitable.

Although one might distinguish types and metatypes as being on different levels of some hierarchy, a user might expect the constraint to be in a package with related types and operations. A type that implements sort.Interface's Less method and an Ordered type are conceptually similar.

[gudvinr]

This package is named "constraints", and it contains type constraints. Nothing else.
I picked the constraints that seemed most likely to be useful.

Your suggested interfaces only related to numeric types. So, when some developer will come up with another likely useful constraint for string manipulation he will probably put it into strings package.
But since it also likely useful and also constraint it might end up in constraints.

So it will either end up as ioutil with bunch of unrelated stuff or will contain only interfaces related to numeric types. But if it only contains numeric constrains maybe math and its subpackages is a better place for such constraints.

[komuw]

I think we should add Comparable to the constraints package even it is just a type alias to the builtin comparable.
This is so that you do not have to explain to newbies why they have to import some constraints from package constraints but they do not have to do the same for comparable

The same logic can be extended to the predeclared any constraint.

[DeedleFake]

@komuw
I feel like they'll become very annoying to use if the standard is to import it, especially from a package with a long name like constraints:

type Map[K comparable, V any] struct { ... }
// vs.
type Map[K constraints.Comparable, V constraints.Any] struct { ... }

I also think that it'll be more confusing for new people if you have to explain why both constraints.Comparable and comparable exist and are completely identical, not to mention they could run into some code that uses one and some that uses the other and if they've never seen it before they'll probably get confused trying to figure out the difference.

Edit: Since the new idea is to think of them as sets of types as per #45346, maybe it would make more sense to name it something type set related to try to get it shortened a bit? I'm not sure what to name it, though. sets seems too generic, especially if container/set ever winds up being a thing, and tsets is just not right.

[DeedleFake]

@gudvinr
As proposed it already contains non-numeric types. Ordered should have ~string in it.

[meling]

Having the constraints in one location promotes discoverability, but I agree with the other commenters that it feels more Go-like to keep them in relevant packages like math and strings etc.

[ianlancetaylor]

Personally I continue to think that it makes more sense for to have a single constraints package that contains common constraints. I think it is simpler to write

func F[T constraints.Integer]() { ... }

then to write

func F[T math.IntegerConstraint]() { ... }

I don't think it can just be math.Integer; that doesn't convey anything to the reader.

[meling]

Good point. I agree. But constraints is a bit long, especially with multiple constraints. I suspect many people will import them with . to avoid the long package name.

[gudvinr]

I don't think it can just be math.Integer; that doesn't convey anything to the reader.

Why though? You can only use constraints in type parameters. So it does convey that it is a constraint.

[meling]

I don't think it can just be math.Integer; that doesn't convey anything to the reader.

Why though? You can only use constraints in type parameters. So it does convey that it is a constraint.

Not when looking at the doc; there they are interfaces.

[gudvinr]

Not when looking at the doc; there they are interfaces.

Their location doesn't restrict you from using constraints.Integer as an interface if language allows it.
There's no package interfaces with common interfaces after all.

[zephyrtronium]

Their location doesn't restrict you from using constraints.Integer as an interface if language allows it.

Related to this, I think it is important to consider future language changes. If Go gets sum types that use type constraint syntax, then it no longer strictly makes sense to call the types in the proposed package just constraints. Contrarily, names like sort.TypeSet are future-proof in this sense.

[DeedleFake]

Maybe types makes more sense as a package name? It fits with the naming (types.Signed, types.Ordered, etc.), fits with the idea of type sets, and works with type set interfaces potentially becoming available as sum types later.

[cespare]

I think that if people are referring to constraints so frequently that typing constraints. becomes a hassle, there are other, deeper problems than the naming of the package.

We should expect that defining parameterized types and functions ought to be a lot less common than using them in real-world code that does useful things, and thus we need not optimize for code which excessively references the constraints package.

[tooolbox]

I don't support this proposal as given; my suggestion would be to revisit it some time after generics are added to the language. A couple of releases later, there may be enough constraints in the wild to analyze which are the most useful and canonicalize them by adding them to the stdlib. Conjecture about what people will use or not use seems premature, because once in the stdlib it can't change. Wait for 5 packages to have a Signed constraint before we standardize it.

[ianlancetaylor]

my suggestion would be to revisit it some time after generics are added to the language.

Certain kinds of generics are going to be annoying to write without this proposal. We can remove constraints if they don't seem useful, but I believe we at least need constraints.Ordered if nothing else.

[tooolbox]

Ordered looks like this, in the old syntax:

// Ordered is a type constraint that matches any ordered type.
// An ordered type is one that supports the <, <=, >, and >= operators.
type Ordered interface {
	type int, int8, int16, int32, int64,
		uint, uint8, uint16, uint32, uint64, uintptr,
		float32, float64,
		string
} 

That doesn’t seem atrocious to write in a package that needs it, does it? As an exercise, I’m curious generally how many functions you predict will need it? The example of Smallest is given in the proposal but you must be thinking of others.

[fzipp]

I once suggested the name is for a constraints package on the mailing list.

// Smallest returns the smallest element in a slice.
func Smallest[T is.Ordered](s []T) T

// Double returns a new slice that contains all the elements of s, doubled. 
func Double[E is.Number](s []E) []E

[fzipp]

I think that if people are referring to constraints so frequently that typing constraints. becomes a hassle, there are other, deeper problems than the naming of the package.

We should expect that defining parameterized types and functions ought to be a lot less common than using them in real-world code that does useful things, and thus we need not optimize for code which excessively references the constraints package.

To me it's about readability. The parameterized function signatures will be shown in the documentation. The typographic bulkiness of the word constraints might visually drown the rest of the signature and distract from the actual relevant parts.

[komuw]

I would be okay with an Ordered constraint that includes floats, if its behaviour when NaN's are involved is clearly documented on the docstring.

Analogous to the documented behaviour of NaN in sort.Float64 : https://golang.org/pkg/sort/#Float64s

[bcmills]

It's unfortunate that the current spec already uses the term “ordered” for types that support <=, but maybe that's enough of a reason to name the constraint Ordered.

I suppose that the built-in comparable constraint in the approved proposal is analogous: it includes interface types, which have the similar problem that == is defined for the type but may panic at run-time for certain values.

[benjaminjkraft]

Is adding types in the future going to cause compatibility problems? For example:

type MySigned interface { type int8, int16, int32, int64 }
func MyAbs[T MySigned](v T) T { ... }
func Abs[T constraints.Signed](v T) T { return MyAbs(v) }

(Of course presumably Abs is in some other package, and perhaps the type lists involved are more complex.) That compiles today, but not in a future Go version where constraints.Signed contains int128. It doesn't seem like this is enough to block the addition of constraints, and I don't see an obvious way to avoid it, but it's at least a bit awkward.

[Merovius]

@benjaminjkraft I don't think it's fully clear under what circumstances it will be allowed to instantiate a generic function using a type parameter. Especially if #45346 is accepted. I could well imagine that we'll have to allow your example, as long as int128 supports the same operators as the other int* do.

Either way, I think the ability to do this kind of extension seems important enough that we should make a stability exception in the form of a disclaimer for it. But it's definitely an interesting question.

[deanveloper]

I propose one more type to be added:

type Arithmetic interface { ... } // supports +, -, *, and /

This is useful for functions which can take integers, floats, and complex numbers as inputs, such as the quadratic formula:

func Quadratic[T constraints.Arithmetic](a, b, c T) (T, T) {
    return (-b + sqrt(b*b - 4*a*c)) / (2*a), (-b - sqrt(b*b - 4*a*c)) / (2*a)
}

(where sqrt has signature func sqrt[T constraints.Arithmetic](in T) T and does what you expect)

Another spelling could be Number, but I figured Arithmetic was less easily mistakable, one might assume that Number is orderable.

EDIT - quadratic formula is a bit of a bad example for integers because of strange interactions with division and square roots... some simple examples that work well with all 3 “kinds” of numbers may be Sum, Product, etc

[benjaminjkraft]

Either way, I think the ability to do this kind of extension seems important enough that we should make a stability exception in the form of a disclaimer for it. But it's definitely an interesting question.

Right, one question I have no sense of is how likely this is to come up in practice. Obviously my example is a bit contrived, and I had trouble coming up with something that I'd actually expect to write, even across several packages of a large codebase.

Another related example which seems much more likely to come up, especially if #45346 is accepted:

func Abs[T constraints.Float](v T) v {
  switch T {
  case ~float32:
    return math.Float32FromBits(math.Float32Bits(v) &^ (1 << 31))
  case ~float64:
    return math.Float64FromBits(math.Float64Bits(v) &^ (1 << 63)) // math.Abs
  default:
    panic("unknown type")
  }
}

(I'm using syntax proposed in #45380 here for brevity, but since T cannot be of interface type I believe this code can be expressed equally well without it, as switch any{v}.(type) + case interface{ ~float32 }. Without #45346 one could probably still write this as switch reflect.TypeOf(v).Kind(), although maybe at that point you're starting to tempt fate.) Right now this can never panic; if float128 is added it can, although at least it still compiles.

In general, I think the problem here is that experienced Go programmers know what it takes to make existing Go types backwards-compatible: for structs it's fine to add methods and fields (assuming no unkeyed literals); for interfaces may add methods only if they have an unexported method; for functions you just can't change them. But I, at least, don't know those rules for type lists yet -- these examples suggest that, more like interfaces, they can't be changed without some (in this case unknown) setup -- and I think we gotta figure them out to define the constraints package.

[rsc]

This is blocked pending type sets, but we haven't forgotten about it.
It won't proceed until the type sets proposal gets a decision.

[rsc]

Type sets have been accepted, so we are ready to finalize this. If you have any outstanding concerns, please post them not here but on this discussion: #47319. Thanks!

[ianlancetaylor]

I have added constraints.Slice, constraints.Map, and constraints.Chan.

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

[rsc]

There's a comment about chans in the discussion that we can work out in a separate issue.

Otherwise, this seems good to go.

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

[gopherbot]

Change https://golang.org/cl/349709 mentions this issue: constraints: new package

[robpike]

I don't understand the value of the Chan type here. What does it add in expressibility? Things like Signed and Unsigned are good, as they capture a wide range of types that are difficult to express. But what does Chan add?

Map too. And Slice. These three all seem to just provide an alternate way to express something that is already very easy to write.

[ianlancetaylor]

They become useful when using constraint type inference. See how the slices proposal at #45955 uses constraints.Slice.

[robpike]

I was worried that generic programming was going to spread throughout the library through these, which I suppose they still can (and probably will), but upon reflection I see what value these definitions add, which comes down to the difference between ~[]any and the bound single type Elem provided in the definition. In one case you can have a slice of any values of any type, while in the other you can have a slice of any single type.

That's what I was missing, and I know I'm not polymorphic front and center but I find that subtle. Important, but the subtlety is something to keep in mind when explaining these things. You're bringing these ideas to a community not all of whom might be facile with all the subtleties involved. I am in that infacile subgroup. And it helps me to see things explained. The original post at the top is little more than a blob of code. It warranted explanation and justification. Instead it spends times on the future (uint128 etc.) when it should probably also offer help to those living in the past.

[randall77]

constraints.Ordered is currently definable in this package. But some proposals, like making structs orderable, will mean that constraints.Ordered becomes like comparable, where it needs to be built-in. Do we have a way forward if a proposal like that happens?

[ianlancetaylor]

@randall77 We will introduce ordered as a new predeclared identifier similar to comparable, and we will make constraints.Ordered an alias for ordered.

[gopherbot]

Change https://golang.org/cl/351853 mentions this issue: cmd/compile: ignore generic packages when testing std lib

[gopherbot]

Change https://golang.org/cl/382535 mentions this issue: constraints: new package

[gopherbot]

Change https://golang.org/cl/382460 mentions this issue: constraints: remove package