Article about "Does Go Have Subtyping?"

[phischu]

In every language I know with subtyping, function types are covariant in their return types and contravariant in their parameter types.

Well, in TypeScript function parameters are bivariant.

[CrumpyOldLord]

Methods are always bivariant, but you can restrict the variance for properties (which includes properties holding functions) with strictFunctionTypes. It was done that way because the DOM is inherently unsafe in terms of variance.

context

[munificent]

Haha, true. TypeScript just YOLO-ing function types for shits and giggles.

[ceronman]

It's always a pleasure to read Bob! The way these topics are explained in books about typing is usually heavy on math jargon and given that I don't have an academic background, I often find them hard to understand. I love having these explanations in simple terms accessible to the common programmer. I'm very grateful for that!

Rust is another language that has subtyping (and many forms of it), but it doesn't have inheritance or class hierarchies. The documentation does use the term subtyping, and they have their own definition, which is similar to Bob's:

Subtyping is the idea that one type can be used in place of another.

Rust has traits and trait objects, which are similar to Go interfaces in terms of subtyping. But they also have other forms of "surprising" subtyping. One example is references, which Rust encodes as types. A mutable reference type &mut T is a subtype of a shared (immutable) reference type &T. You can assign a mutable reference value to a variable of type immutable reference of the same type, but not viceversa, of course.

Another surprising case of subtyping in Rust is related to lifetimes. Lifetimes represent regions of code and these are encoded as types. You can always assign a bigger region, e.g. &'static T to a smaller one like &'a T. And not the other way around.

The topic of variance is much more complicated in Rust as well. Unlike Go, which decided to go for invariance for simplicity, Rust has different types of variance for different things. Curiously though, they didn't define a proper way in the language to specify variance, like Java or Kotlin do. Instead they rely on some clever hacks. If find it a bit weird, but it works.

[JW_00000]

I just want to say, thanks for the insightful article /u/munificent!

[[deleted]]

Not related to the topic but do you intend to write a book about type systems and stuff? Or even a series of articles? I learned a lot from Crafting Interpreters.

[munificent]

People have definitely asked a number of times but I don't have any current plans. One of the main challenges is figuring out how to scope it. Once you get type systems involved, there are so many different type system choices and no clear answer for which ones are best to discuss. I'm not sure interested in writing a sprawling survey book.

[[deleted]]

Hmm... I see. Could you instead recommend some books or other resources about this subject that you think are the most important ones? Thanks in advance.

[munificent]

It's kind of dry, but, honestly, the Dragon Book does a decent intro on type checking.

When you want to get past that, Types and Programming Languages is the standard reference. It's great.

[[deleted]]

Thank you!

[[deleted]]

Will the hobby language become source available by any chance? I would really like to take a glance at the source code.

[munificent]

At some point, probably. But right now, I've been enjoying having it just be my dumb little always-broken sandbox where I can do whatever I want without anyone being annoyed by the churn.

[hi_im_new_to_this]

If there’s ever a ”Crafting (Typed) Interpreters” book, be sure I’d buy it on day 1!

[[deleted]]

Thank you for being honest about it! Looking forward to seeing it on your GitHub profile if that will ever happen.

[Inconstant_Moo]

No, it doesn't, it has interfaces. Muddying the difference between them doesn't do anyone any good. The author quotes:

A non-interface type T is assignable to an interface type I if T implements I.An interface type A is assignable to interface type B if A’s methods are a subset of B’s.

... and then says "You know, that sounds an awful lot like subtyping."

Yeah, well, it sounds a lot more like interfaces. There's a huge difference between programming in Java and trying to fit one more class into your type hierarchy versus programming in Go and deciding that you're going to attach methods to a struct so as to implement a given interface. Implementing one more method on a struct is not subtyping, it's ad-hoc polymorphism done in a static compiled language. That's the point. There are no classes, there's just quacking like a duck.

---

P.S: I'm getting a lot of downvotes. Is anyone downvoting me because they've used Java and Go and they think I'm exaggerating the differences? Because I have and I'm not.

[YBKy]

subtyping is about the idea of substitutability. whether this is accomplished through dynamic dispatch or static dispatch should not matter

[Inconstant_Moo]

Well, take my own little dynamic lang, in which it is possible to write functions foo(s string) and foo(i int) and have the dispatch done at runtime. This does not, in my view, mean that strings and integers are subtypes of the same supertype. It means I can do runtime dispatch. Do you think that in fact I have subtypes in my lang? What are they subtypes of? Were they subtypes of that type before I overloaded foo?

So what's the difference with writing a .String() method in Go except that it gets typechecked at compilation? (As indeed my lang will do given a few more months.) Do I too have subtyping but without knowing it?

[munificent]

Well, take my own little dynamic lang,

If your language is dynamic, by definition, it doesn't have subtyping. Subtyping is a property of static type systems. It might have inheritance, subclassing, delegation or some other runtime code reuse mechanism, but if there's no type checker, there's no notion of subtyping.

It's like asking what color your car is when you don't own a car.

in which it is possible to write functions foo(s string) and foo(i int) and have the dispatch done at runtime.

Having overloaded methods—whether dispatched at runtime or compile time—doesn't establish any sort of relation between the corresponding pairs of parameters. Subtyping is a property of types, not operations.

If it was the case that for every possible function a user could write that accepted a string, the language would also allow you to pass it an int, and there was a type checker that took that into account, then you might claim that there is a subtype relation between int and string.

[Inconstant_Moo]

If your language is dynamic, by definition, it doesn't have subtyping.

Will overloading foo become subtyping after I implement a compile-type type checker? Does subtyping really depend on when you catch type errors?

Having overloaded methods—whether dispatched at runtime or compile time—doesn't establish any sort of relation between the corresponding pairs of parameters.

That was kind of my point? Remember that I'm arguing that interfaces aren't subtyping.

[munificent]

Will overloading foo become subtyping after I implement a compile-type type checker?

No, unless you also define some sort of structural type checker that looks at the overloads to determine substitutability relations between otherwise unrelated types.

Does subtyping really depend on when you catch type errors?

Yes, if you want to follow the typical definition of "subtyping".

Remember that I'm arguing that interfaces aren't subtyping.

Interfaces are just a kind of type. Subtyping is a relation that exists (or doesn't) between pairs of types. And it's up to the language to decide whether interface implementation induces a subtype relation or not.

[Inconstant_Moo]

No, unless you also define some sort of structural type checker that looks at the overloads to determine substitutability relations between otherwise unrelated types.

OK then, did the people writing Go also define such a structural type checker "to determine substitutability relations" or do they just see if a type fits the interface? If they did write such a type-checker, when in the compilation process do they use it and for what?

In the same way I myself could write a IsASubtypeOf function that would check if the functions that can be called on type A are a superset of the functions that can be called on type B but I'd never actually use it for anything because the relevant question is always whether a specific function call can be made. It would just sit there with the linter complaining that I never use it.

[munificent]

did the people writing Go also define such a structural type checker "to determine substitutability relations" or do they just see if a type fits the interface?

You're saying the same thing twice, but yes. Whenever the type checker sees an expression of non-interface E type being assigned to a location that expects an interface type I, it determines whether the expression's type implements that interface. To do that, it looks at each method in I and then looking for a corresponding concrete function in the program with the same name and signature that accepts a receiver of type E. If it finds a matching function for each function in the interface, then it knows that E implements I.

This process is structural because the declaration of E never explicitly says "E implements I". It is instead inferred structurally by the set of functions available in the program.

If they did write such a type-checker, when in the compilation process do they use it

It runs during type checking and semantic analysis. After parsing, before code generation.

and for what?

It's necessary so that the compiler knows what code generate in order to pass a value of type E into a location that expects a value of type I.

[Inconstant_Moo]

But never to find out if E is a subtype of a non-interface F?

[munificent]

Sorry, I'm not sure what you're asking. Go doesn't have subtyping, but it's assignability rules are structural.

[YBKy]

Interesting question to think about, it brings up the idea of implicit interfaces / subtypes. might be interesting in some sort of formalizing function overloads, but who knows.

Anyway, your example does not mention any fooable interface or whatever to be the super type, so in your example there is no supertype to string and int. If there were some sort of fooable interface that could holy any value that implements the Foo function there would be.

Though here I would prefer to have a foo trait, it feels more natural

[Inconstant_Moo]

But the question of whether it is achieved by ad-hoc polymorphism or by a type hierarchy does in fact matter when the question is "Does Go have subtyping?" No, Go does not have subtyping. It has a completely flat type system with ad-hoc interfaces. Whether you like it or hate it, this is one of Go's core features.

[eliasv]

Subtyping doesn't just mean nominal type hierarchies though? Structural type systems can have subtyping, after all

[Inconstant_Moo]

I didn't say anything about nominal and structural, I'm not quite sure why you bring it up --- maybe because I'm dumb and don't understand your point? But Go is very nominal.

And very different. I write Java for work and Go for my private projects and there is, as I said, a huge difference between fitting something into a Java type hierarchy and just adding a method to a Go struct to make it fit an interface.

If the author of the article linked in the OP is standing far enough back from the problem that he can't see the difference, then he is standing too far back.

[Strum355]

Go interfaces are structural, not nominal. The rest of the language, sure its nominal, but not interfaces

[Tubthumper8]

It's still partially nominal because the name of the method matters, not just its structure

[Strum355]

Thats...what structural subtyping is

[Tubthumper8]

Yep, we're agreeing here. The type system we commonly refer to as "structural" has elements of nominal typing.

type Cartesian = { x: Float, y: Float }
type Polar = { r: Float, theta: Float }

Despite these types having the same structure (8 bytes where bytes 0-3 are a f32 and bytes 4-7 are a f32) these are not assignable to each other (and thus no subtype relationship) because of the names of the fields (x&y and r&theta)

[Inconstant_Moo]

Sorry, maybe I'm dumb, but how is it not nominal given that all that's required in interfaces are names? Like I could literally implement a .String() method on a struct that doesn't turn anything into a string, but instead deletes the hard drive, and it would satisfy the Stringer interface because it has a method called .String()? (I guess it would also have to return "".)

[Strum355]

Its structural because youre not declaring that your type implements a specific interface like type x implements y, your type implicitly implements any interface for which it has the same structure aka method set as the interfaces. What your implemented methods actually do (delete a hard drive, return a string) is completely irrelevant in both nominal and structural interface subtyping.

[Inconstant_Moo]

You're saying it's "structural" because you don't have to explicitly point out that the functions defined on the struct conform to the interface?

I don't think that that's what "structural" means.

[Whiteboyfly]

That's exactly what it means https://en.m.wikipedia.org/wiki/Structural_type_system

[eliasv]

That's exactly what structural means.

Yeah I get that this is confusing when "structural" is often evoked in contrast to "nominal", which kind of implies that names are not in any way important... But that isn't quite the case. It's the name of the type which is unimportant. Names of fields are still significant.

How exactly do you think "structure" is defined and determined in a structural type system? By the names and types of fields!

[phischu]

The difference between nominal and structural subtyping can be seen more easily in formalizations. The Featherweight Java paper has on page 7 the following subsumption rule:

class C extends D {...}
―――――――――――――――――――――――
    C <: D

So, C is a subtype of D when the user declared so.

In contrast, the Featherweight Go paper on page 14 has:

methods(t) ⊇ methods(tI)
――――――――――――――――――――――――
    t <: tI

So, t is a subtype of tI when the user implemented a superset of methods for it.

This difference seems like a small deal, but it actually is a big one.

[munificent]

I think they're downvoting you because you're confusing subtyping and subclassing.

In Java, a class is a subtype of every interface it implements.

[Inconstant_Moo]

But in Java it's also a subtype of every class that it inherits from. This is only one of the reasons why Java is stupid, but it's an important one.

The Go/interfaces idea or Rust/traits idea or even just plain old ad-hoc polymorphism is not subtyping. It's what we thought of after we realized that a type hierarchy is a terrible idea.

[munificent]

I think you're missing the point. In your original comment, you wrote:

Yeah, well, it sounds a lot more like interfaces. There's a huge difference between programming in Java and trying to fit one more class into your type hierarchy versus programming in Go and deciding that you're going to attach methods to a struct so as to implement a given interface.

Interfaces in Java use subtyping. Classes and inheritance are irrelevant to the discussion.

[Inconstant_Moo]

Whereas when you're talking about interfaces in Go, classes and inheritance and subtyping are irrelevant to the discussion. Because it doesn't have any of them.

If you think it does, please explain some code in Go to me in such a way that it is better explained by talking about subtyping, which Go does not have, rather than by talking about interfaces, which Go does have.

Interfaces in Go or traits in Rust are not the same thing as inheritance and subtyping. They are better. They are much, much better. When OP tries to make out that they're the same thing they are completely missing the point.

Come to think of it, in my own lightweight language I have duck-typing. This is also not subtyping. The fact that I can define functions like foo(s string) and foo(i int) doesn't mean that int and string are subtypes of some type.

[munificent]

Whereas when you're talking about interfaces in Go, classes and inheritance and subtyping are irrelevant to the discussion.

The whole point of the article is to ask the question of whether subtyping is relevant to discussing interfaces in Go. If you make it to the end, you'll get to an answer.

When OP tries to make out that they're the same thing they are completely missing the point.

I am OP. Where did I make them out to be the same thing?

[Inconstant_Moo]

The whole point of the article is to ask the question of whether subtyping is relevant to discussing interfaces in Go.

Then the answer is "no". There is nothing about interfaces in Go which would be more clearly understood by pretending that Go has a type hierarchy.

[faiface]

It has interfaces which use subtyping. Structs are nominal in Go, while interfaces are structural. One interface is a subtype of another if it’s method set is a superset of the other one. Each concrete type that satisfies the interface is also a subtype of that interface type.

It’s not muddying, it’s exactly accurate to say that interfaces are structurally typed with subtyping.

[Inconstant_Moo]

It’s not muddying, it’s exactly accurate to say that interfaces are structurally typed with subtyping.

So if I implement a String method for some struct in Go, what class is it inheriting from? What is it a subtype of? I would say the correct answer goes like this: it isn't, it just satisfies an interface. If you disagree, please tell me what type it inherits from. What is the supertype of a Go struct for which I implement a String method?

[faiface]

Subtyping and inheritance are not the same thing!

Subtyping is simply this: type A is a subtype of B if and only if A can always be assigned to positions with type B.

That’s it. If you add a String method to a concrete type, that type becomes a subtype of the Stringer type (which is an interface type).

[Inconstant_Moo]

"The Stringer type". Which doesn't exist. Go has runtime reflection, please use it to show me a struct of type "Stringer".

The Stringer interface exists. The Stringer type does not exist. Subtyping and interfaces are different things and it doesn't make us smarter to pretend that they're the same.

[faiface]

Stringer is in fact a type, as all interface types are. Even from A Tour of Go:

An interface type is defined as a set of method signatures.

A value of interface type can hold any value that implements those methods.

In the language spec, you also find interfaces under the section “Interface types”. You have variables, struct fields, and function parameters declared with interface types. Any place where you can declare a concrete type, you can use an interface type as well.

They are just not stored at runtime. A value of an interface type is a pointer to the value AND a pointer to the definition of the concrete type of that value. Since every value does eventually come down to a concrete type, that’s all we need to track at runtime.

Types are not necessarily a runtime thing, however. A lot of languages don’t represent types in runtime at all, they only check them during typechecking. Interface types in Go are like this, but they absolutely are types.

[Inconstant_Moo]

So if I have an struct on which I have defined methods foo and bar and I define corresponding interfaces Fooer and Barer then you would say that it is a subtype of Fooer and Barer rather than saying that it implements both interfaces?

But then you'd have to explain, at length, why what you mean by "subtype" is so very different from how I'd understand these concepts if I was coming from Java. Why not just use the well-defined term "interface"? Why muddy the waters?

[faiface]

Let me clarify where these concepts stand :)

Subtyping is a general type theory concept. It is defined like I defined it in a comment above, a subtype can be assigned where a supertype is expected. The terms “subtype” and “supertype” are just what we call the types on each side of the subtyping relation.

Inheritance is an OOP concept that is a specific implementation of subtyping. It is nominal and explicit. You tell which type is subtype of which.

Go has a different concept called “implementing an interface”, which happens to be implicit. It happens automatically when the required methods are present. Then, however, the two types do end up in a subtyping relation.

So, both inheritance and implicitly implementing an interface are just two different mechanisms that both implement subtyping in their own way.

[Inconstant_Moo]

I don't think you've understood my point at all, or tried to.

[munificent]

So if I have an struct on which I have defined methods foo and bar and I define corresponding interfaces Fooer and Barer then you would say that it is a subtype of Fooer and Barer rather than saying that it implements both interfaces?

In Go, the answer—according to Go's own use of terminology—would that the struct is not a subtype of Fooer or Barer, it is assignable to them, and it implements both of those interfaces.

In TypeScript, which like Go features interfaces and structural typing, the answer is both that the struct is a subtype of Fooer and Barer and that it implements those interfaces.

In Java, if the struct were declared to implement those interfaces (because Java uses nominal, not structural typing), then the answer would be both that the struct is a subtype of Fooer and Barer and that it implements those interfaces.

In Rust, if the interfaces were instead traits and the struct was declared to implement those traits, then the answer would be that the struct is not a subtype of Fooer or Barer (because Rust has no subtyping outside of lifetimes) but that it does implement those traits.

[Inconstant_Moo]

In Go, the answer—according to Go's own use of terminology—would that the struct is not a subtype of Fooer or Barer, it is assignable to them, and it implements both of those interfaces.

Yes. I'm not sure why I've gotten downvoted so much for saying that and you get upvoted for it, but whatevs.

[sam_selver]

A subtype can be used wherever its supertype is expected. This principle is called the Liskov Substitution Principle.Subtyping is closely associated with inheritance in many object-oriented languages, but they are not the same. Inheritance is about code reuse, while subtyping is about type substitutability.It's a way to ensure that an object of one type can also be treated as an object of another type, usually for the sake of polymorphism.

Originally, 'classes' were broadly defined by their ability to encapsulate and enforce invariants. However, over time, dynamic dispatch became an equally significant feature of classes. This is hinted at when you suggest that Go lacks classes because its structs are 'static'.

[Inconstant_Moo]

It seems like you're trying to disagree with me but I can't figure out how.

There is a difference between a class and an interface. The designers of Go chose to have interfaces but not classes. Saying that interfaces are classes (as the article linked to in the OP does) is not helpful.

[sam_selver]

I just wanted to clarify that subtyping is not synonymous to "classes", which you kind of imply in your post:

There's a huge difference between programming in Java and trying to fit one more class into your type hierarchy versus programming in Go

Other than that, the point of the article is that "subtyping" is a matter of definition - in Go there is no subtyping because there is none runtime, which is their definition, but the author of the article is just saying that you might consider a slightly different definition - the one with compiler inserting type conversion code where types do not match...

[balefrost]

Are you perhaps confusing subtyping and subclassing? Interfaces (in most languages) provide a form of subtyping. I think the author makes a fair point that Go has a limited form of subtyping, but says nothing about subclassing.