Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

constraints: new package to define standard type parameter constraints #45458

Closed
ianlancetaylor opened this issue Apr 8, 2021 · 64 comments
Closed

Comments

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 8, 2021

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 }
@ianlancetaylor ianlancetaylor added this to the Proposal milestone Apr 8, 2021
@ianlancetaylor ianlancetaylor added this to Incoming in Proposals Apr 8, 2021
@gudvinr
Copy link

@gudvinr gudvinr commented Apr 8, 2021

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. ...

Loading

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Apr 9, 2021

@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.

Loading

@smasher164
Copy link
Member

@smasher164 smasher164 commented Apr 9, 2021

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.

Loading

@zephyrtronium
Copy link
Contributor

@zephyrtronium zephyrtronium commented Apr 9, 2021

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)?

Loading

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Apr 9, 2021

@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.

Loading

@zephyrtronium
Copy link
Contributor

@zephyrtronium zephyrtronium commented Apr 9, 2021

@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.

Loading

@smasher164
Copy link
Member

@smasher164 smasher164 commented Apr 9, 2021

@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.

Loading

@gudvinr
Copy link

@gudvinr gudvinr commented Apr 9, 2021

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.

Loading

@komuw
Copy link
Contributor

@komuw komuw commented Apr 9, 2021

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.

Loading

@DeedleFake
Copy link

@DeedleFake DeedleFake commented Apr 9, 2021

@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.

Loading

@DeedleFake
Copy link

@DeedleFake DeedleFake commented Apr 9, 2021

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

Loading

@meling
Copy link

@meling meling commented Apr 9, 2021

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.

Loading

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Apr 9, 2021

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.

Loading

@meling
Copy link

@meling meling commented Apr 9, 2021

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.

Loading

@gudvinr
Copy link

@gudvinr gudvinr commented Apr 9, 2021

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.

Loading

@meling
Copy link

@meling meling commented Apr 9, 2021

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.

Loading

@gudvinr
Copy link

@gudvinr gudvinr commented Apr 9, 2021

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.

Loading

@zephyrtronium
Copy link
Contributor

@zephyrtronium zephyrtronium commented Apr 9, 2021

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.

Loading

@DeedleFake
Copy link

@DeedleFake DeedleFake commented Apr 9, 2021

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.

Loading

@cespare
Copy link
Contributor

@cespare cespare commented Apr 9, 2021

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.

Loading

@tooolbox
Copy link

@tooolbox tooolbox commented Apr 10, 2021

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.

Loading

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Apr 10, 2021

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.

Loading

@tooolbox
Copy link

@tooolbox tooolbox commented Apr 10, 2021

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.

Loading

@fzipp
Copy link
Contributor

@fzipp fzipp commented Apr 10, 2021

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

Loading

@fzipp
Copy link
Contributor

@fzipp fzipp commented Apr 10, 2021

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.

Loading

@twmb
Copy link
Contributor

@twmb twmb commented Apr 28, 2021

For prior art, Rust has PartialOrd, which I've been partial to, rather than OrderedOrNaN.

Rust implements PartialOrd for f64 by returning None if left <= right and left >= right both return false.

Loading

@Merovius
Copy link

@Merovius Merovius commented Apr 28, 2021

float64 is not a partial order though. Partial orders are still reflexive.

Loading

@komuw
Copy link
Contributor

@komuw komuw commented Apr 28, 2021

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

Loading

@bcmills
Copy link
Member

@bcmills bcmills commented Apr 28, 2021

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.

Loading

@benjaminjkraft
Copy link

@benjaminjkraft benjaminjkraft commented Apr 29, 2021

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.

Loading

@Merovius
Copy link

@Merovius Merovius commented Apr 29, 2021

@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.

Loading

@deanveloper
Copy link

@deanveloper deanveloper commented May 5, 2021

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

Loading

@benjaminjkraft
Copy link

@benjaminjkraft benjaminjkraft commented May 6, 2021

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.

Loading

@rsc
Copy link
Contributor

@rsc rsc commented May 19, 2021

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.

Loading

@rsc
Copy link
Contributor

@rsc rsc commented Jul 21, 2021

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!

Loading

@golang golang locked and limited conversation to collaborators Jul 21, 2021
@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Aug 11, 2021

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

Loading

@rsc
Copy link
Contributor

@rsc rsc commented Aug 11, 2021

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

Loading

@rsc rsc moved this from Active to Likely Accept in Proposals Aug 11, 2021
@rsc
Copy link
Contributor

@rsc rsc commented Aug 18, 2021

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

Otherwise, this seems good to go.

Loading

@rsc rsc moved this from Likely Accept to Accepted in Proposals Aug 18, 2021
@rsc
Copy link
Contributor

@rsc rsc commented Aug 18, 2021

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

Loading

@rsc rsc changed the title proposal: constraints: new package to define standard type parameter constraints constraints: new package to define standard type parameter constraints Aug 18, 2021
@rsc rsc removed this from the Proposal milestone Aug 18, 2021
@rsc rsc added this to the Backlog milestone Aug 18, 2021
@gopherbot
Copy link

@gopherbot gopherbot commented Sep 13, 2021

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

Loading

@robpike
Copy link
Contributor

@robpike robpike commented Sep 14, 2021

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.

Loading

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Sep 14, 2021

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

Loading

@robpike
Copy link
Contributor

@robpike robpike commented Sep 14, 2021

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.

Loading

@randall77
Copy link
Contributor

@randall77 randall77 commented Sep 23, 2021

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?

Loading

@ianlancetaylor
Copy link
Contributor Author

@ianlancetaylor ianlancetaylor commented Sep 23, 2021

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

Loading

@gopherbot gopherbot closed this in 4dd5f09 Sep 24, 2021
@gopherbot
Copy link

@gopherbot gopherbot commented Sep 24, 2021

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

Loading

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
Proposals
Accepted
Linked pull requests

Successfully merging a pull request may close this issue.

None yet