5 ms·

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)

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.

pcwalton 10y ago
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.
- catnaroek 10y ago
  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.
  - burntsushi 10y ago
    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.
    - computerex 10y ago
      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{}.
      - burntsushi 10y ago
        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{}`.
    - catnaroek 10y ago
      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.
      - burntsushi 10y ago
        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.
        catnaroek 10y ago
        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.)
        burntsushi 10y ago
        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.
  - pcwalton 10y ago
    > 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{}.
    - catnaroek 10y ago
      AFAICT, that only means that [] isn't covariant, which is only to be expected, since slices aren't immutable in Go.
- jzelinskie 10y ago
  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?
  - eddyb 10y ago
    The only document I can think of outside of Niko Matsakis' blog (http://smallcultfollowing.com/babysteps/ http://smallcultfollowing.com/babysteps/) would be https://github.com/rust-lang/rust/blob/master/src/librustc/infer/region_inference/README.md https://github.com/rust-lang/rust/blob/master/src/librustc/i...
  - stjepang 10y ago
    There is a chapter in Rustonomicon on subtyping and variance: https://doc.rust-lang.org/nomicon/subtyping.html https://doc.rust-lang.org/nomicon/subtyping.html

pcwalton 10y ago

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.

catnaroek 10y ago
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.
- burntsushi 10y ago
  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.
  - computerex 10y ago
    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{}.
    - burntsushi 10y ago
      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{}`.
  - catnaroek 10y ago
    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.
    - burntsushi 10y ago
      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.
      - catnaroek 10y ago
        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.)
        burntsushi 10y ago
        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.
- pcwalton 10y ago
  > 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{}.
  - catnaroek 10y ago
    AFAICT, that only means that [] isn't covariant, which is only to be expected, since slices aren't immutable in Go.
jzelinskie 10y ago
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?
- eddyb 10y ago
  The only document I can think of outside of Niko Matsakis' blog (http://smallcultfollowing.com/babysteps/ http://smallcultfollowing.com/babysteps/) would be https://github.com/rust-lang/rust/blob/master/src/librustc/infer/region_inference/README.md https://github.com/rust-lang/rust/blob/master/src/librustc/i...
- stjepang 10y ago
  There is a chapter in Rustonomicon on subtyping and variance: https://doc.rust-lang.org/nomicon/subtyping.html https://doc.rust-lang.org/nomicon/subtyping.html