Wandering Thoughts archives

2018-11-29

Go 2 Generics: Interfaces are not the right model for type constraints

A significant and contentious part of the Go 2 draft generics design is its method of specifying constraints on the types that implementations of generic functions can be used with. There are excellent reasons for this; as an motivating example, I will quote the overview:

[...] In general an implementation may need to constrain the possible types that can be used. For example, we might want to define a Set(T), implemented as a list or map, in which case values of type T must be able to be compared for equality. [...]

The Go 2 generics proposal adopts a method called contracts, which are basically Go function bodies with somewhat restricted contents. From the beginning, one of the most proposed changes in generics is that type constraints should instead be represented through something like Go interfaces. I believe that this would be a mistake and that interfaces are fundamentally the wrong starting point for a model of type constraints.

First, let's observe that we can't really use stock interfaces as they stand as type constraints. This is because stock interfaces are too limited; they only let us say things about a single type and those things have fixed types (whether interfaces or concrete types). Pretty much every interface-based proposal that I've seen immediately expands generic-constraint interfaces to allow for multiple type variables that are substituted into the interface. Axel Wagner's proposal is typical:

type Graph(type Node, Edge) interface {
  Nodes(Edge) []Node
  Edges(Node) []Edge
}

However, I believe that this is still the wrong model. The fundamental issue is that interfaces are about methods, but many type constraints are about types.

An interface famously does not say things about the type itself; instead, it says things about the methods provided by the type. This provides implementations of interfaces with great freedom; in a well-known example, it's possible and even simple for functions to fulfill an interface. Providing interfaces with type variables and so on does not fundamentally change this. Instead it merely expands the range and flexibility of what one can say about methods.

However, a significant amount of what people want to do with generic functions is about the types themselves, and thus wants constraints on the types. The starting example of Set(T) is an obvious one. The implementation does not care about any methods on T; it simply wants to be able to compare T for equality. This is completely at odds with what interfaces want to talk about. Fundamentally, a significant number of generics want to operate on types themselves. There is not just Set(T), there are also often expressed desires like Max(T), Min(T), Contains(), Sort([]T), and so on.

A related issue is that interfaces are about a single type, while type constraints in generic functions are not infrequently going to be about constraints on the relationship between types. The Graph example from the overview is an example; it talks about two separate types, each of which is required to have a single method with a specific type signature:

contract Graph(n Node, e Edge) {
  var edges []Edge = n.Edges()
  var nodes []Node = e.Nodes()
}

In Axel Wagner's proposal, this is modified (as it has to be) into a single type that implements both methods. These two are not the same thing.

An example that combines both problems is the convertible contract from the draft design:

contract convertible(_ To, f From) {
  To(f)
}

This is expressing a constraint about the relationship between two types; From must be convertible into To. There is no single type and no methods in sight, and so expressing this in the interface model would require inventing both.

All of this is a sign that using interfaces to express type constraints is forcing a square peg into a round hole. It is not something that naturally fits the problem; it is simply something that Go already has. Interfaces would be a fine fit in a world where generics were about methods, but that is not the world that people really want; they want generics that go well beyond that. If Go 2 is to have generics, it should deliver that world and do so in a natural way that fits it.

Given my view that contracts are too clever in their current form, I'm not sure that contracts are right answer for type constraints for generics. But I'm convinced that starting from interfaces is definitely the wrong answer.

(This entry was sparked by a discussion with Axel Wagner on Reddit, where questions from him forced me to sit down and really think about this issue instead of relying on gut feelings and excessive hand waving.)

Sidebar: Interfaces and outside types

In their current form, interfaces are limited to applying to existing methods, for good reasons. But if type constraints must be expressed through methods, what do you do when you want to apply a type constraint to a type that does not already implement the method for that constraint? When it is your own package's type, you can add the method; however, when it is either a standard type or a type from another package, you can't.

I think it's clear that you should be able to apply generic functions to types you obtain from the outside world, for example from calling other package's functions or methods. You might reasonably wish to find the unique items from a bunch of slices that you've been given, for example, where the element type of these slices is not one your types but comes from another package or is a standard type such as int.

(It would be rather absurd to be unable to apply Max() to int values from elsewhere, and a significant departure from current Go for the language to magically add methods to int so that it could match type constraints in interfaces.)

Go2GenericsNotWithInterfaces written at 01:02:56; Add Comment

2018-11-28

Go 2 Generics: A way to make contracts more readable for people (if not programs)

In the Go 2 generics draft design, my only real issue with contracts is their readability; contracts today are too clever. Contracts have been carefully set up to cover the type constraints that people will want to express for generics, and I think that something like contracts is a better approach to type constraints for generics than something like interfaces (but that's another entry). Can we make contracts more readable without significantly changing the current Go generics proposal? I believe we can, through use of social convention and contract embedding.

For being read and written by people, the problem with contracts today is that they do not always clearly say what they mean. Instead they say it indirectly, through inferences and implicit type restrictions. To make contracts more readable, we need to provide a way to say tricky things directly. One obvious way to do this is with a standard set of embeddable contracts that would be provided in a package in the standard library. Let's call this package generic/require (because there probably will be a standard generic package of useful generic functions and so on).

The require package would contain contracts for standard and broadly useful properties of types, such as require.Orderable(), require.String(), and require.Unsigned(). When writing contract bodies it would be standard practice to use the require versions instead of writing things out by hand yourself. For example:

contract Something(t T) {
  require.Unsigned(t)
  // instead of: 1 << t
}

Similarly, you would use 'require.Integer(t)' instead of any of the various operations that implicitly restrict t to being an integer (signed or unsigned), and require.Numeric if you just needed a number type, and so on. Of course, contracts from the require package could be used on more than direct type parameters of your contract; they could be used for return values from methods, for example.

The obvious advantage of this for the reader is that you have directly expressed what you require in a clear way. For cases like require.Integer, where there are multiple ways of implementing the same restriction, you've also made it so that people don't have to wonder if there's some reason that you picked one over the other.

It's likely that not everything in contracts would be written using things from the require package. Some restrictions on types would be considered obvious (comparability is one possible case), and we would probably find that require contracts don't make other cases any easier to read or write. One obvious set of candidates for require contracts are cases where there are multiple ways of creating the same type restriction.

(In the process the Go developers might find that there were gaps in the type restrictions that you could express easily, as exposed by it being difficult or impossible to write a require contract for the restriction. For example, I don't think there's currently any easy way to say that a type must be a signed integer type.)

Use of the require package would be as optional as the use of Go's standard formatting style, and it would be encouraged in much the same way, by the tacit social push of tools. For instance, 'gofmt -s' could rewrite your contracts to use require things instead of hand-rolled alternatives, and golint or even vet could complain about 'you should use require.<X> instead of ...'. Faced with this push towards a standard and easy way of expressing type restrictions, I believe that most people would follow it, much as how gomft has been accepted and become essentially universal.

An open question is if this would add enough more readability to significantly improve contracts as they stand. I'm not sure that a number of the trickier restrictions in the full draft design could be implemented in this sort of reusable contract restriction in a way that both is usable and is amenable to a good, clear name. People may also disagree over the relative readability of, say:

contract stringer(x T) {
   var s string = x.String()
   // equivalent:
   require.String(x.String())
   // or perhaps:
   require.Returns(x.String, string)
}

At a certain point it feels like one would basically be spelling out phrases and sentences in the form of require package contracts. I'm not sure that's a real improvement, or if a more fundamental change to how contracts specify requirements is needed for true readability improvements.

Sidebar: Augmenting the language through the back door

The require package would also provide a place to insert special handling of type restrictions that can't be expressed in normal Go, in much the way that the unsafe package is built in to the compiler (along with various other things). People might find this too awkward for some sorts of restrictions, though, since using require has to at least look like normal Go and even then, certain sorts of potentially implementable things might be too magical.

Go2ContractsMoreReadable written at 02:01:13; Add Comment

2018-11-16

Go 2 Generics: Contracts are too clever

The biggest and most contentious thing in the Go 2 Draft Designs is its proposal for generics. Part of the proposal is a way to specify things about the types that generic functions can be used on, in the form of contracts. Let me quote from the overview:

[...] In general an implementation may need to constrain the possible types that can be used. For example, we might want to define a Set(T), implemented as a list or map, in which case values of type T must be able to be compared for equality. To express that, the draft design introduces the idea of a named contract. A contract is like a function body illustrating the operations the type must support. For example, to declare that values of type T must be comparable:

contract Equal(t T) {
    t == t
}

This is a clever trick (among other things it basically avoids adding any new syntax to Go to define contracts), but my view is that it is in fact too clever. Using function bodies with operations in them to define the valid types is essentially prioritizing minimal additions to the language and the compiler over everything else. The result is easy for the compiler to use (it just runs types through contract bodies in a regular typechecking process) but provides generally bad to terrible ergonomics for everything else.

In practice, contracts will be consumed and used by far more than the compiler. People will read contracts to understand error messages about 'your type doesn't satisfy this contract', to understand what they need to do to create types that can be used with generic functions they're interested in, to see how to specify something for their own generic functions, to try to understand mistakes that they made in their own contracts, and to understand what a contract actually requires (as opposed to what the code comments claim it requires, because we all know about what happens to code comments eventually). IDE systems will read contracts so they can figure out what types can be suggested as type parameters for generic functions. Code analysis will read contracts for all sorts of reasons, including spotting unnecessarily requirements that the implementation doesn't actually need.

All of these parties and all of these purposes are badly served by contracts which require you to understand the language and its subtle implications at a deep level. For instance, take this contract:

contract Example(t T) {
    t.Fetch()[:5]
    t.AThing().Len()
}

The implications of both lines are reasonably subtle; the first featured in a quiz by Dave Cheney, and the second requires certain sorts of return values and what the .Len() method is on, as covered as part of addressable values in Go. I would maintain that neither are obvious to a person (certainly they aren't to me without careful research), and they might or might not be easily understood by code (certainly they're the kind of corner cases that code could easily be wrong on).

Part of the bad ergonomics of contracts here is that they look simple and straightforward while hiding subtle traps in the fine details. I've illustrated one version of that here, and the detailed draft design actually shows several other examples. I could go on with more examples (consider the wildly assorted type requirements of various arithmetic operators, for example).

Go contracts do not seem designed to be read by anything but the compiler. This is a mistake; computer languages are in large part about communicating with other people, including your future self, not with the computer. If we're in doubt, we should bias language design toward being clearly and easily read by people, not toward the compiler. Go generally has this bias, preferring clean communication over excessive cleverness. The current version of contracts seem quite at odds with this.

(This is especially striking because other parts of the Go 2 Draft Designs are about making Go clearer for people. The error handling proposal, for example, is all about making Go code read better by hiding repetitive patterns.)

PS: The Go team may have the view that only a few people will ever create generics and thus contracts, and mostly everyone else will read the excellent documentation that these very few people have carefully written. I think that the Go team is quite wrong here; I expect to see generics sprout like mushrooms across Go codebases, at least for the first few years. In general I would argue that if generics are successful, we can expect to see them widely used, which means that many generics and contracts will not be written or read by people who are deep experts with Go. A necessary consequence of this wide use will be that some amount of it will be with contracts and code created partly through superstition in various forms.

Go2ContractsTooClever written at 01:04:00; Add Comment


Page tools: See As Normal.
Search:
Login: Password:
Atom Syndication: Recent Pages, Recent Comments.

This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.