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

proposal: spec: built-in functions for generic type constraints #44235

Open
zephyrtronium opened this issue Feb 12, 2021 · 15 comments
Open

proposal: spec: built-in functions for generic type constraints #44235

zephyrtronium opened this issue Feb 12, 2021 · 15 comments

Comments

@zephyrtronium
Copy link
Contributor

@zephyrtronium zephyrtronium commented Feb 12, 2021

Now that #43651 has been accepted, I propose changing the spelling of type constraints to use the new names any and comparable as built-in functions that produce type constraints. Accompanying these built-in functions in this proposal is the addition of type constraints as a fully independent concept in the language and type system, rather than reusing interface types. Furthermore, the type list syntax proposed in the type parameters draft would be removed.

Motivation

This proposal addresses concerns from @bcmills (here) and I (here) raised in #43651, as well as many others who discussed type lists at length.

Keeping type constraints and interfaces distinct removes many caveats and special cases, simplifying the mental model required to understand generics. In the type parameters draft, interface types may also serve as type constraints. This makes the meanings of "interface" and "type" much more intricate, or at least requires a variety of caveats to distinguish the two different uses. By constructing type constraints from interfaces, the distinction becomes much clearer.

Giving an explicit name to type constraints in code as well as in the specification makes it much easier for experienced Go programmers to learn generics and for new programmers to learn Go with generics. Arguably, interfaces are already the subtlest concept in the language. The type parameters draft further increases their subtlety by creating situations where they are no longer types, at least in the current sense in the context of Go. The concept of interfaces in Go almost becomes reminiscent of the many meanings of static in C++. By separating type constraints from interface types in code, learners can acquire one concept at a time.

It is possibly clearer where to modify the Go specification to add built-in functions than to add type lists to interface types. Admittedly, this benefits very few people. Still, an important aspect of Go is that its specification is easy to read. Generics will add a significant amount of text to that document, so it is crucial that these additions be as straightforward and readable as possible. The spec already contains a section on built-in functions, which begins:

Built-in functions are predeclared. They are called like any other function but some of them accept a type instead of an expression as the first argument.

The built-in functions do not have standard Go types, so they can only appear in call expressions; they cannot be used as function values.

These paragraphs would require only minimal modifications to describe the properties of the new built-in functions here proposed.

Lastly, this proposal reduces the number of special cases added with type parameters, at least insofar as every existing built-in function already being some special case. The type parameters draft introduces a special predeclared identifier any that is defined as "equivalent to interface{}," but with the unusual exception that it can be used only as a type constraint. Similarly, comparable is an interface containing every comparable type in a type list, which is not normally possible to express in Go code. By using these names for built-in functions instead, their definitions are more consistent with the language, and their special properties follow from the usual traits of built-in functions.

Proposal

Let I denote some interface type and T1, T2, ..., Tn be a non-empty list of types. Then the any built-in function would accept the following forms:¹

  • any() constructs a type constraint with which any type may unify. (This matches the current draft behavior of any.)
  • any(I) constructs a type constraint requiring a type to implement I to unify with the constraint. (This matches the current draft behavior of supplying an interface without a type list as a constraint.)
  • any(I, T1, T2, ..., Tn) constructs a type constraint requiring a type to implement I and to either be a member of the list T1, ..., Tn or to be a defined type whose underlying type is a member of the same list to unify with the constraint. (An example spelling might be any(interface{}, float32, float64). This matches the current draft behavior of type lists.)

The comparable built-in function accepts the same forms as any and adds the requirement that a type must be comparable to unify with the constraint it produces. It is an error during type checking if any type in the type list given to comparable after the first argument is not comparable.

The result of all forms of any and comparable is a type constraint. Type constraints are new citizens of the type system that may appear in exactly two contexts:

  • In the type parameter list of a generic type or function declaration, specifying a constraint on a type parameter.
  • In a type declaration², as in type C any(...) or type C = any(...) (or comparable).

Defined type constraints may additionally be parameterized as if they were types.³ So, for example, if I is

type I[A any()] interface {
	...
}

then type C[B any()] any(I[B]) defines a constraint requiring a type to implement I[B].

Examples

Comparing declarations under this proposal to those of the type parameters draft document:

func Print2[T1, T2 any](s1 []T1, s2 []T2)
func ConcatTo[S Stringer, P Plusser](s []S, p []P) []string
type Ordered interface {
	type int, int8, int16, int32, int64,
		uint, uint8, uint16, uint32, uint64, uintptr,
		float32, float64,
		string
}
type ComparableHasher interface {
	comparable
	Hash() uintptr
}

become

func Print2[T1, T2 any()](s1 []T1, s2 []T2)
func ConcatTo[S any(Stringer), P any(Plusser)](s []S, p []P) []string
type Ordered any(interface{},
	int, int8, int16, int32, int64,
	uint, uint8, uint16, uint32, uint64, uintptr,
	float32, float64,
	string,
)
type ComparableHasher comparable(interface {
	Hash() uintptr
})

And the more involved, mutually dependent parameterized type definition in the draft:

type NodeConstraint[Edge any] interface {
	Edges() []Edge
}
type EdgeConstraint[Node any] interface {
	Nodes() (from, to Node)
}
type Graph[Node NodeConstraint[Edge], Edge EdgeConstraint[Node]] struct { ... }

becomes

type NodeConstraint[Edge any()] any(interface {
	Edges() []Edge
})
type EdgeConstraint[Node any()] any(interface {
	Nodes() (from, to Node)
})
type Graph[Node NodeConstraint[Edge], Edge EdgeConstraint[Node]] struct { ... } // no change

For constraints that previously were only any or comparable, the only change is the addition of parentheses. On the other hand, for constraints containing only type lists, this proposal requires the addition of interface{}.⁴ So, some generic declarations become more verbose, and others stay close to the same length or are unchanged.


¹ Another form for any and comparable which might be desirable would be any(I, C...) to produce a constraint with the union of the method sets of I and the interface used to construct C and that reuses the type list of C. I generally find nested constraints in any proposal unintuitive, so I do not propose that at this time.

² Type constraints are not types, in the sense that there are no values of type any(...). Still, of the existing declaration keywords, type seems the most appropriate to define a type constraint.

³ A consideration is whether any and comparable should accept type parameters directly, as in any[K any()](I[K]). I think this makes declarations excessively noisy.

⁴ I considered proposing untyped nil in place of interface{} as the first argument when creating a type list, but I'm not confident that's a sensible, intelligible decision.


  • Would you consider yourself a novice, intermediate, or experienced Go programmer?
    Experienced.
  • What other languages do you have experience with?
    C, Java, Python, C++, various assembly languages
  • Would this change make Go easier or harder to learn, and why?
    This change will make it significantly easier to learn generics in Go, because the existing concept of interfaces are no longer gaining a new, subtle meaning.
  • Has this idea, or one like it, been proposed before?
    To my knowledge, only syntactic approaches have been proposed for type constraints. This proposal instead adds new identifiers to the universe scope.
  • Who does this proposal help, and why?
    This proposal helps people who teach Go, because we no longer have to explain many new caveats on interfaces, which are already one of the subtlest concepts in Go. Transitively, it helps people to learn Go, whether those people are new to Go or new to programming, because distinct concepts remain distinct.
  • Is this change backward compatible?
    Yes. The only changes are the addition of predeclared identifiers in the universe scope.
  • What is the cost of this proposal? (Every language change has a cost).
    I am given to understand that some work has already been put into implementing the type parameters draft, including the current meanings of any and comparable, the current syntax for type lists, and the idea of interface types as constraints. This might reverse some of that work. Additionally, this proposal may or may not require greater separation between interface types and type constraints in cmd/compile. Otherwise, there should be no difference between this proposal and the current draft for external tools, compile-time costs, or run-time costs.
@gopherbot gopherbot added this to the Proposal milestone Feb 12, 2021
@gazerro
Copy link
Contributor

@gazerro gazerro commented Feb 12, 2021

When are any and comparable builtins called? Is their return value required at compile time but are they called at runtime?

@zephyrtronium
Copy link
Contributor Author

@zephyrtronium zephyrtronium commented Feb 12, 2021

When are any and comparable builtins called? Is their return value required at compile time but are they called at runtime?

any and comparable take only types as arguments and return only type constraints, which cannot be used outside of type and function declarations. There is nothing for them to evaluate while the program runs. Depending on the compiler's implementation of type constraints, it may be the case that any references to them are removed after type checking.

@gazerro
Copy link
Contributor

@gazerro gazerro commented Feb 12, 2021

There is nothing for them to evaluate while the program runs.

So are they a special kind of function that are not called and cannot be called? What is the advantage of introducing a new special kind of function in Go (and I don't mean two special functions but a new kind of function), compared to introducing two new keywords?

@DeedleFake
Copy link

@DeedleFake DeedleFake commented Feb 12, 2021

It seems to me that calling any() and comparable() 'built-in functions' might be slightly misleading, though. They seem more like special types that behave like functions only syntactically. It might make more sense to give them a more type-like syntax:

type SignedInt any {
  int; int8; int16; int32; int64
}

If you want to add an interface as well, you can just add it as type parameter:

// Type list in {} is optional.
type GenericStringer any[Stringer]

Then your example becomes the following:

func Print2[T1, T2 any](s1 []T1, s2 []T2)
func ConcatTo[S any[Stringer], P any[Plusser]](s []S, p []P) []string
type Ordered any {
	int; int8; int16; int32; int64
	uint; uint8; uint16; uint32; uint64; uintptr
	float32; float64
	string
}
type ComparableHasher comparable[interface {
	Hash() uintptr
}]

The downside to this particular syntax is that it requires any and comparable to be keywords, rather than just predefined identifiers, but it might be possible to come up with a syntax that doesn't require that and still makes it clear that they're fundamental types and not functions.

All of that being said, this proposal feels somewhat unnecessary to me, though. It still doesn't solve the primary problem of type lists. It just fixes the dichotomy caused by the difference between normal interfaces and interfaces with type lists in terms of non-generic usage. The main problem that needs fixing, in my opinion, is the lack of usability of type list interfaces with user-defined types due to the lack of operator overloading and/or operator methods, resulting in the requirement of two implementations for anything that uses operators and also wants to support user-defined types. That's the primary reason that type list interfaces exist in the first place and the main reason that they can't be used as normal interfaces, so I think that fixing that will probably automatically fix this issue, too.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Feb 12, 2021

@ianlancetaylor ianlancetaylor added this to Incoming in Proposals Feb 12, 2021
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Feb 12, 2021

Am I correct in thinking that this is a purely syntactic change? The semantics are the same as in the current generics proposal, it's just that type constraints are written differently?

As @DeedleFake suggests, in this proposal any and comparable are not functions. They are type constructors. This proposal seems to introduce a new kind of type, a constraint, that has no literal representation but can only be created by calling one of the type constructors any or comparable. Go currently does not have any type constructors, and currently does not have any types that do not have a literal representation. That seems like a pretty significant stylistic change.

@bcmills
Copy link
Member

@bcmills bcmills commented Feb 12, 2021

FWIW, any and comparable as presented in the original Type Parameters design are well-defined and well-behaved as interface types.

If any is an interface type equivalent to interface{}, then, because the type any has no methods and no type-specific operations:

  • A value of a type that implements any can be used wherever a value of type any is needed.
  • The type any supports all of operations that the constraint any allows. (Namely, assignment to a variable of its own type.)

If comparable is an interface type implemented by all types for which == and != are well-defined:

  • A value of a type that implements comparable can be used wherever a value of type comparable is needed.
  • Because comparable is an interface type, it also has well-defined == and != operations.
  • If T is a type that implements comparable, and two values x and y are of type T, then either:
    • x == y and comparable(x) == comparable(y), or
    • x != y and comparable(x) != comparable(y).

So I don't actually think that any change is needed to any and comparable per se — they are already coherent if defined as “predeclared interface types”.

@bcmills
Copy link
Member

@bcmills bcmills commented Feb 12, 2021

The novel part of this proposal seems to be the any(I, T1, T2, ..., Tn) form, which I think is intended to replace type-lists.

However, that form is less expressive than type-lists: type-lists allow both disjunction (using comma-separated entries as in type T1, …, Tn) and intersection (embedding two type-lists in a higher-level constraint), whereas any as proposed here seems to allow only disjunction.

It isn't obvious to me whether the loss of the “intersection” operation is significant, but I suspect that it may be.

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Feb 12, 2021

I don't think the intersection property of embedding type lists will ever be useful in practice. It falls out of the design, it's not a goal or even a useful feature.

@zephyrtronium
Copy link
Contributor Author

@zephyrtronium zephyrtronium commented Feb 12, 2021

@DeedleFake

All of that being said, this proposal feels somewhat unnecessary to me, though. It still doesn't solve the primary problem of type lists. It just fixes the dichotomy caused by the difference between normal interfaces and interfaces with type lists in terms of non-generic usage.

To me, type lists are orthogonal to that dichotomy. It is really between interface types and type constraints. I think it is a mistake, especially for explaining the idea to programmers new to Go, to make those into one concept. Even without type lists, they're incompatible things.

This proposal is not about solving any problems related to type lists.


@ianlancetaylor

Am I correct in thinking that this is a purely syntactic change? The semantics are the same as in the current generics proposal, it's just that type constraints are written differently?

That is the goal, yes. Any behavior that is possible with the current draft should be possible with this proposal.

Apparently, I completely missed the section on type lists in embedded constraints, however. My assumption was that it would be illegal to embed an interface when it would cause there to be more than one type list in the interface definition. So, this proposal has no way to express intersection of type lists. As you and @bcmills discussed, I can't think of a way in which that is a useful operation.

As @DeedleFake suggests, in this proposal any and comparable are not functions. They are type constructors. This proposal seems to introduce a new kind of type, a constraint, that has no literal representation but can only be created by calling one of the type constructors any or comparable. Go currently does not have any type constructors, and currently does not have any types that do not have a literal representation. That seems like a pretty significant stylistic change.

I agree with @DeedleFake that any and comparable are not functions in the usual sense. I chose the name "built-in functions" as one that already exists in the language and generally serves to capture behaviors that can't normally be expressed in Go code.

More precisely, I believe these would be metatype constructors. I want to avoid talking about metatypes in the proposal; even if accurate, I'm not trying to suggest anything about adding metatype programming to Go.

However, unless my definition of "type constructor" is incorrect, these are precisely what generics adds. type T[C any] struct {...} is not a type, but T[int] is a type constructed from it. So, if there is a time to add more type constructors, it would be now.


@bcmills

If any is an interface type equivalent to interface{}, then, because the type any has no methods and no type-specific operations:

More precisely, any would have to be an interface with a type list containing all types, because any is not allowed outside of type constraints. Still, both any and comparable are consistent, as you say, if not expressible in Go code. That is not a part of the draft that particularly concerns me, though – they're easy to explain because they only apply in type parameters. The same is not true of interfaces as type constraints.

@zephyrtronium
Copy link
Contributor Author

@zephyrtronium zephyrtronium commented Feb 12, 2021

@gazerro

What is the advantage of introducing a new special kind of function in Go (and I don't mean two special functions but a new kind of function), compared to introducing two new keywords?

New keywords would violate the Go 1 compatibility promise. New predeclared identifiers do not.

@griesemer
Copy link
Contributor

@griesemer griesemer commented Feb 16, 2021

I think it is a mistake to introduce a new language concept such as a constraint just to separate the different use cases for interfaces, at least if we ignore type lists. And ignoring type lists for a moment (as you state "This proposal is not about solving any problems related to type lists."), interfaces seem exactly the correct mechanism to describe constraints. From the perspective of a caller of a generic function, a type argument satisfies a constraint if it implements the constraint interface. From the perspective inside of a generic function, the type parameter constraint is exactly the interface of the type parameter. These concepts are well understood.

But here's a concrete technical argument as to why introducing a new concept such as constraint seems unwise. For example, let's say we've got a simple generic List type (you can replace this with any other suitable type or generic function):

type List[T any] struct {
   next *List[T]
   elem T
}

It makes perfect sense to instantiate such a generic type with its own constraint:

type PolymorphicList List[any]

Now we've gone from a generic (parameter polymorphic) list with a fixed element type to a non-generic list with a polymorphic element type. Here the constraint is just any, but in general this works for other constraints as well. But the point is, if constraints were a new concept, we couldn't satisfy them without yet some additional rules. In fact, introducing the notion of a constraint would make interfaces less orthogonal than they actually are.

Type lists complicate matters. The final word has not been spoken yet; and we may well end up with some additional mechanism besides just interfaces.

@KevinCathcart
Copy link

@KevinCathcart KevinCathcart commented Feb 17, 2021

Just to be clear, there are a LOT of people concerned about type lists in interfaces creating a sort of "interface that cannot be used in most ways a normal interface can". Besides people who are completely opposed to generics in the first place, I think people concerned about these "special case interfaces" are the next biggest opposition to the current (accepted) version of the generics proposal.

If the sum-types proposal is unable to re-use the type list semantics, then we would likely be stuck with the implied "(except if the interface contains a type list)" in most discussions of interfaces when not used as constraints, and this probably needs to not just be implied but explicitly stated in some beginner oriented materials, which is really unfortunate.

This proposal is just one of likely many attempts to find a way around this unfortunate limitation. A separate constraint concept is one possible solution.

My own reservations about generics are: a) this second class interfaces issue and b) the extra type-parameter that gets auto-inferred approach to solving the only the pointer implements desired interface concern. (With the latter, I'm concerned that if a cleaner solution is added later, existing generics in the standard library would need to still use the old approach indefinitely, since some callers may have explicitly specified the second type argument since they can).

@griesemer
Copy link
Contributor

@griesemer griesemer commented Feb 17, 2021

@KevinCathcart Thanks, Kevin. Let me assure you that we are very aware of the problems with type lists in interfaces and that such "interfaces cannot be used in most ways a normal interface can". We (Go team) are actively working on it, with @bcmills involved in the discussion, and we have some promising ideas that very much are taking into account many of the observations made by the community.

But I still hope that ordinary interfaces (no type lists) can remain usable as constraints directly. The problem are type lists, and their inclusion into ordinary interfaces which muddles the latter. I updated (edited) my comment to be clearer about that, but perhaps not clear enough. I do think it would be fairly sad if we could not instantiate a generic function or type with its own constraint if that constraint is an ordinary Go interface.

This proposal is recognizing that type lists are a problem as well and addresses this by introducing a new mechanism (constraints) using built-in functions. What I have reservations with is that even if the constraint is an ordinary interface, one has to wrap it first with a built-in function call. Also, using a built-in call rather than syntax seems a bit of a deviation from how we construct types (and type-like things such as constraints) in Go. This proposal could avoid the former by simply allowing ordinary interfaces to be used as constraints as well.

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

@zephyrtronium
Copy link
Contributor Author

@zephyrtronium zephyrtronium commented Feb 17, 2021

What I have reservations with is that even if the constraint is an ordinary interface, one has to wrap it first with a built-in function call.

I received feedback elsewhere that allowing I in place of any(I) should be allowed as a shortcut in my proposal. My response at the time was that the point of this proposal is to reduce the ambiguity between interfaces, which are dynamically typed, and type constraints, which are purely static, and such a shortcut is counterproductive to that goal. I don't think that ambiguity is harmless; I've already had to answer questions about why this (old) attempt to borrow Rust's Result<T> doesn't work, and I've seen this incorrect conclusion from a core Rust dev lead a few very experienced Go programmers astray. (Maybe Rust is really what is to blame here. 😏)

As you point out, though, type constraints as an independent concept would not be orthogonal to interfaces. I still believe that interfaces as constraints makes them no longer unitary, to continue the linear algebra terminology. However, considering my original motivation for proposing this – that being the fact that I expect to answer many questions about why people's generic code doesn't work how interfaces lead them to expect – I think it would be enough of a solution to be able to instantiate a generic type or function with its own constraint in every case. That would at least make it easier to illustrate how type parameters and interfaces are different.

So, contrary to what I said before, this proposal may indeed defer to a better approach to type lists (or perhaps sum types). In particular, I agree with everything in the last paragraph of your previous comment.

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

Successfully merging a pull request may close this issue.

None yet
9 participants