Hacker News Reader

Comment by catnaroek | Hacker News Reader

Parametric polymorphism alone is a simple yet very powerful feature, but this assessment changes drastically as soon as subtyping (which both Go and Java have) enters the picture. The combination of parametric polymorphism and subtyping creates the pesky issue of determining whether Foo<T> should be a subtype of Bar<U>.

Java-style generics are a lot of things (notably “bolted on”), but “simple” certainly isn't one of them. Wildcards are complex. F-bounded polymorphism is complex. Non-denotable types are complex.

View on HN

Go doesn't have subtyping. It has coercions, which are not the same thing, and they do not lead to issues around variance.

Variance is straightforward anyway. A lot of things in Go, like the semantics of "nil" and zero values, are more complex than variance. And, as a designer, if you're worried about the complexity, just make all type parameters invariant, like C++ does. It's a bad excuse to not have generics at all.

Rust works exactly the same way as Go (coercions, no subtyping), except that there is subtyping in Rust via the region system. But Go doesn't have that. No region system, no subtyping.

What distinction between coercion and subtyping are you making? Aren't Go structs subtypes of every interface they conform to?

And I don't think making all type parameters invariant eliminates any complexity. It just pushes it onto the user.

It would be the other way around. It is intuitive to say that interface{} is a subtype of all other types, but it is easy to show a contradiction. Assume that interface{} is a subtype of int, which means interface{} can be used in place of int in any type. So define a function with type func(xs []int). If you pass a []interface{} to this function you will get a type error. More concretely, []int and []interface{} have different in memory representations.

Can you explain why the empty interface would be a subtype of [] int and not the other way around? Intuitively, I think it's the other way around, as every type implements interface{}.

I guess neither direction is especially intuitive because structural typing makes the relationship a bit strange. In both cases, it's easy to show a contradiction. `interface{}` can't substitute `int` in `[]int` and `int` can't substitute `interface{}` in `[]interface{}`.

I'm not sure how you concluded that I said interface{} is a subtype of all other types. Perhaps you meant supertype?

Also, from “Foo <: Bar”, you can't automatically conclude that “[]Foo <: []Bar”. That requires the additional assumption that [] is a covariant type constructor, which in Go it isn't.

I didn't conclude that at all. It is trivial to produce a contradiction if you assume A <: B because Go will not let you substitute A in place of B for every type in which B occurs. Therefore A is not a subtype of B. This has nothing to do with []A <: []B.

But that's not at all what subtyping means! It doesn't mean that you can substitute every occurence of “A” with “B” in the program text. It means that every term of type “A” also has type “B”. (Source: I have TaPL p. 182 right in front of me.)

OK, I see where I was wrong now. You are right to emphasize the word "term" because that's precisely the detail I was missing. I can no longer come up with a contradiction.

The next obvious step is getting an answer to "what is the meaning of saying Go doesn't have subtyping?", which is essentially what you asked above:

> What distinction between coercion and subtyping are you making?

But this is a question for pcwalton, not you. :-) However, I have some thoughts on the matter.

While exploring the extent of my wrongness, I found it very interesting that the Go language spec doesn't mention the words "subtype" or "polymorphism" or "structural" at all. The FAQ mentions "subtype" and "covariance," but doesn't lead to anything conclusive. What I think this means is that the language designers of Go probably don't think of interfaces as being tied to the formal notion of subtype, but rather that of assignability or coercions. This just takes us in a circle though, which leads me to guess that this is a simple matter of two groups of people having different names for the same thing.

The litmus test for “typeness” is to ask whether it makes sense to ask whether a term has the type in question. For example, it makes sense to ask whether 2 has type string, and the answer is “no”. But it doesn't make sense to ask whether 2 has type 3 - the closest thing to an answer is “what the hell I don't even?” Then:

(0) Structs and interfaces are unarguably types.

(1) If a struct S has all the methods required by an interface I, then every term of type S also has type I.

As for coercions, they are one possible implementation of subtyping. Another possible implementation is guaranteeing that, whenever “Foo <: Bar”, then “Foo” and “Bar” have a common in-memory representation.

But languages shall never be conflated with their implementation details!

Yes, I think pcwalton saying that Go doesn't have subtyping is very confusing. What I think he was trying to say was that Go's subtyping is strange because everything is invariant, and that the use of coercions makes the questions you initially raised perhaps not so interesting.

For example, if you start with some base assumptions about which type constructors in Go are invariant, e.g., pointers, slices, arrays, etc., then you could feasibly come up with a rule like this: If T <: U, then Foo<T> <: Foo<U> if Foo's type parameter doesn't appear within an invariant type constructor in the definition of Foo. If a rule like that is all you need (and those types of rules have precedence in Go, like whether a type permits equality comparisons or not), then I think that more or less backs up pcwalton's point that subtyping isn't necessarily the thing you have to worry about when adding parametric polymorphism to Go. It's the other stuff, like the mentioned zero values and presence of `nil`.

The concern I initially raised is just that retrofitting parametric polymorphism into a statically typed language with subtype polymorphism and a sizeable codebase worth not breaking... has a history of not going so well.

Although zero values are inelegant, I don't see why they would interact so badly with parametric polymorphism. In Rust terms, it's as if every type implicitly implemented the Default trait. (EDIT: You're right, steveklabnik. It's closer to Default than to Zero. Thanks!)

As for nil, I'd rather not comment, since I'm not familiar with the specifics of how it works in Go. (But a previous conversation with pcwalton made it perfectly clear that it doesn't work the same as in Java or .NET.)

(I think it's closer to Default than Zero, personally.)

> Aren't Go structs subtypes of every interface they conform to?

No. There's a defined coercion between values and interface types, which is not the same thing as subtyping. This affects the semantics: for example, you can't pass a value of type []MyStruct to a function taking []interface{}.

AFAICT, that only means that [] isn't covariant, which is only to be expected, since slices aren't immutable in Go.

I googled for a bit and didn't find anything current about Rust's region system from an implementation perspective. Is there a good place to read more in depth about design decisions, but containing less process than the RFCs and PRs?

The only document I can think of outside of Niko Matsakis' blog (http://smallcultfollowing.com/babysteps/) would be https://github.com/rust-lang/rust/blob/master/src/librustc/i...

There is a chapter in Rustonomicon on subtyping and variance: https://doc.rust-lang.org/nomicon/subtyping.html

Reply on news.ycombinator.com