9 ms·
You Need Subtyping
- SomeoneOnTheWeb 2y agoI disagree with this article. Subtyping is what we have in TypeScript and it creates a lot of problems due to covariance.
- loup-vaillant 2y agoWait, if I recall correctly, covariance has long been established as a mistake. I would guess that if TypeScript had adopted contravariance the problems you mention would go away. We could then argue that TypeScript does need subtyping (like everyone else), as long as it’s contravariant. My point is, we can’t say TypeScript doesn’t need subtyping just because they botched it. As such, it may not be a good counter example of the article’s thesis.
- paldepind2 2y ago> Wait, if I recall correctly, covariance has long been established as a mistake. Perhaps you're just missing some words here, but, just for clarity: it doesn't make any sense to say that covariance is a mistake. Covariance applied in specific places, like Java's mutable covariant arrays which leads to unsoundness, can be a mistake, but covariance itself in fine and essential in languages with subtyping. Function parameters should be covariant, function returns should be contravariant, mutable data structures should be invariant, etc.
- pansa2 2y ago> function returns should be contravariant I'm not very familiar with these relations, but shouldn't function returns be covariant? `String => Cat` is a subtype of `String => Animal`? > Function parameters should be covariant For function parameters, doesn't it depend on how the parameter is used?
- paldepind2 2y ago> I'm not very familiar with these relations, but shouldn't function returns be covariant? `String => Cat` is a subtype of `String => Animal`? You're right :) I mixed up covariance and contravariance for function parameters and return value in my comment. > For function parameters, doesn't it depend on how the parameter is used? I don't think so, but maybe there's specific circumstances I don't know of? Function parameter types is a constraint on _input_ to the function. Changing that to a subtype amounts to the function receiving arguments that satisfies a stronger constraint. That seems that something that would hold no matter how the parameter is used?
- pansa2 2y ago> > For function parameters, doesn't it depend on how the parameter is used? > I don't think so, but maybe there's specific circumstances I don't know of? I don't know specific circumstances either, but I presume they exist because of things like Dart's `covariant` keyword [0], which makes function parameters covariant instead of contravariant. [0] https://dart.dev/language/type-system#covariant-keyword https://dart.dev/language/type-system#covariant-keyword
- kragen 2y agoMaybe this is intentionally introducing logical unsoundness into Dart's type system for pragmatic purposes, perhaps supplemented with some implicit dynamic checks?
- sparkie 2y agoThe use case would be where the arguments are expected to be filled in by the function - ie, as additional return types. Consider if we have `A <= B <= C`, and a function: int Copy([out] Array<B> dest, [in] Array<B> src); Given some potential inputs: Buffer<A> asrc = ... Buffer<B> bsrc = ... Buffer<C> csrc = ... Buffer<A> adest = allocate(...) Buffer<B> bdest = allocate(...) Buffer<C> cdest = allocate(...) The following should be true: Copy(adest, asrc); // No! - How would Copy know how to copy `A` values when it only knows about `B`? Copy(adest, bsrc); // No! - src argument is OK, but how can it downcast them to `A`? Copy(adest, csrc); // No! - Same as above, and src elements must be at least `B`s`. Copy(bdest, asrc); // Ok. - Any `A` in the src are interpreted as `B`s. Copy(bdest, bsrc); // Ok, - all values are interpreted as `B`s. Copy(bdest, csrc); // No! - Argument elements must be at least `B`s`. Copy(cdest, asrc); // Ok - values are interpreted as `B`s in src, and as `C`s in dest. Copy(cdest, bsrc); // Ok Copy(cdest, csrc); // No! Argument elements must be at least `B`s`. If the `dest` argument were contravariant, it would permit invalid copies and forbid valid ones. Copy(adest, asrc); // pass (wrong) Copy(adest, bsrc); // pass (wrong) Copy(adest, csrc); // fail Copy(bdest, asrc); // pass Copy(bdest, bsrc); // pass Copy(bdest, csrc); // fail Copy(cdest, asrc); // fail (wrong) Copy(cdest, bsrc); // fail (wrong) Copy(cdest, csrc); // fail In a purely functional setting, you should not need a covariant parameter type because all writes would end up in the return type. copy : Array<B> -> Array<B>
- jyounker 2y agoCorrect solution: Contravariance for arguments, Covariance for return types. Another way to put it, if I create a subtype, then the subtype's functions are allowed to be more general in what they accept, and more specific in what they return. This implies that there is no subtype relation between X[Supertype] and X[Subtype].
- kragen 2y agoOthers have pointed out that "covariance is a mistake" is nonsense, because, if you have subtyping, it's perfectly correct to make function types covariant on return types and contravariant on argument types. And it's useful. To switch up the examples a bit, Natural is a subtype of Integer, so it's perfectly valid to make Natural => Natural (the type of IntegerSqrt) a subtype of Natural => Integer (the type of functions returning integers given a natural-number argument, such as n => (-2)**n), and to make Integer => Natural (the type of IntegerAbs) a subtype of Natural => Natural. If someone is expecting a Natural => Natural function, no surprises will result if you secretly smuggle them IntegerAbs. They just won't happen to call it with a negative argument. And others have pointed out that covariance and contravariance are both logically unsound for mutable container types like arrays. In particular, covariance would allow you to infer Vector<Natural> is a subtype of Vector<Integer>, which, together with the function subtyping rules above, lets you pass a Vector<Natural> to a function like a => a[0] := -1. That will store a negative number into the Vector<Natural>, and down the line, that -1 will be incorrectly used in Natural calculations, possibly producing incorrect results. Contravariance is no better, because then functions like a => IntegerSqrt(a[0]) fall down go boom. What I haven't seen anyone mention yet is that covariance is perfectly sound for immutable container types. If you have an immutable List container type supporting Car, Cdr, Cons, and IsEmpty functions, no surprises will result from passing a List<Natural> to a function expecting a List<Integer>. It can add -1 to the List with Cons(-1, xs) but that doesn't mutate the original List; it returns a new, longer List, which is already statically typed as a List<Integer>. This is far from an original observation, so I was surprised not to see it mentioned. Nothing obliges you to add function or immutable-container subtyping to your language just because you have subtyping of some kind. You could require implicit or explicit adaptors to be inserted in cases like the above, perhaps eliding those adaptors as a compilation optimization. Logically, that's a perfectly sound thing to do. I don't know why you would want to. It seems inconvenient. But maybe you do.
- josephg 2y agoCan you give some examples? How does this cause problems in typescript?
- rocqua 2y agoPresumably tye issue lies with mutable collections. If you have a type Animal, with subtypes Dog and Cat, then covariance means a list of Cat is a subtype of a list of Animal. The problem is that appending a Dog is a legal action for a list of Animals, but not a legal action for a list of Cats.
- btown 2y agoTo expand on this, you could be maintaining a list of Cats, call a function which accepts a list of Animals, and that function could append a Dog without causing a type error. https://github.com/python/mypy/issues/4976 https://github.com/python/mypy/issues/4976 is an interesting discussion on this in Python: should a TypedDict be allowed where a dict argument is accepted? The basic consensus is no, because then one could modify the dict, adding keys that wouldn't be allowed in the specific TypedDict. But this means that often you have to do cast(dict, my_typed_dict) to be able to interop with third party libraries that (quite naturally) believed that by typing their arguments as accepting a dict, they'd be accepting all dict-like things.
- rocqua 2y agoThe solution is to encode mutability. So that you can say: Const list<cat> is a subtype of Const list<animal>. But that does get complicated because. The difference between a mutable container of immutable elements and an immutable container of mutable elements is hard to get your head around, and verbose to capture in syntad.
- debugnik 2y agoYou're confusing covariance itself with having covariant mutable collections. The former is a great feature, the latter a design mistake that makes the type system unsound.
- stephantul 2y agoWhat is the meaning of the word “boxed” in this article? Bit confused about it.
- masklinn 2y agoUsually it's used for saying something is heap allocated. In this case it doesn't seem very relevant, it looks like the article just assumes boxed records are dynamically or structurally typed, even though that's completely unrelated.
- mostlylurks 2y agoNot represented directly in memory in its raw form right where the value is placed, but rather stored somewhere else (usually the heap) / in an opaque manner and accessed via an indirection, such as a pointer / reference. Often involved in making things polymorphic, because different types usually have different representations in memory even if they implement the same interface, so they need to be boxed.
- tialaramex 2y agoIf you're familiar with Rust it's what's different about Box<T> compared to T, if you know Java, all their "objects" are boxed it's the difference between Integer and the primitive int type. In C++ it's approximately std::unique_ptr<T> in a lot of the high level languages (indeed Java I mentioned above fits this if you're not familiar with the details) boxing is silently done for you and you are unaware of it unless you care about fine details. Think of an arbitrary type Goose, where "is" the Goose? Assume for a moment there's data associated so the Goose does need to be stored somewhere, the two usual candidates are "the stack" and "the heap". If you've no idea what those are then I'm afraid you need a bit more CS to really engage with this conversation. Boxing puts things on the heap, typically with just a pointer to that box kept on the stack.
- DeathArrow 2y agoBoxing means transforming a variable of a value type into a variable of reference type. //boxing var a = 5; //int, value type string b = (string)a; //string, reference type Unboxing is the reverse process of transforming variables of reference types to value types. A value type variable holds the value directly, while a reference type variable holds a reference that points to a memory address where the actual value is found.
- masklinn 2y ago> If a function accepts a value that can be String or null, it is ok to pass it a value that is guaranteed to be a String and not null. Or in other words, String is a subtype of String?! That's... not true? The language can just have an implicit conversion rule for convenience. > properties like nullability that don’t affect memory layout That's not true either? It might not affect memory layout because all your objects are boxed or you have niche value optimisation you can use to tag nulls, but make an unboxed integer nullable and you'll definitely see your memory layout be affected.
- zarakshR 2y ago> The language can just have an implicit conversion rule for convenience the presence of an implicit conversion rule `T -> T?` amounts to the observation that `T <: T?`, where <: is the subtyping relation > make an unboxed integer nullable ... I don't think any language allows this, in any case disallowing nullability for unboxed types amounts to the observation that `P !<: P?`, where !<: is "does not subtype" I believe (unless I have misunderstood you) that both your examples are subsumed (heh) by subtyping
- lmm 2y ago> the presence of an implicit conversion rule `T -> T?` amounts to the observation that `T <: T?`, where <: is the subtyping relation Not necessarily, because you might consider it acceptable for the implicit conversion to change the memory layout in this sense. > I don't think any languages allow this Plenty do, e.g. Rust's Option works that way. > in any case disallowing nullability for unboxed types amounts to the observation that `P !<: P?`, where !<: is "does not subtype" Saying the same thing with fancier words doesn't explain anything. The point is you can't simply treat non-nullable as a subtype of nullable in general, because this case exists.
- zarakshR 2y ago> The point is you can't simply treat non-nullable as a subtype of nullable in general, because this case exists. But surely, you can still use subtyping in other cases -- when it is already unboxed -- right? Like so: `T <: T?` for all boxed `T`.
- a3w 2y agoAfter reading the article, I propose this gist / title: "In high level programmming languages, you expect subtyping as a given", since we expect a lot of features to work as if subtyping was the way it was implemented?
- psychoslave 2y agoSo is that basically duck typing?
- djtango 2y agoThe example using an open record is an implementation of safe duck typing Checking type unions and inferring information about conditional branching isn't really duck typing
- pansa2 2y ago> existing programming languages have little or no subtyping [...] If you remember the fad for Object Oriented Programming I was under the impression that even today, most code is written in an object-oriented style (or at least, written in languages that support OOP). Therefore, most languages support subtyping via inheritance. Is that not true?
- josephg 2y ago> I was under the impression that even today, most code is written in an object-oriented style (or at least, written in languages that support OOP). Whoa there - those are very different claims! Most modern languages are multi-paradigm. You can write Python in an OO way, or a data oriented way, or a functional way, or whatever you like. The same is true of JavaScript/typescript. And modern Java. And lots of languages. Just because the language has the class keyword doesn’t mean everything can be subtyped. If you have an entity-component system, you can’t necessarily inherit from your Entity type. Likewise I can’t inherit from a react component, just because JavaScript has classes. (At least not using modern react)
- kllrnohj 2y ago> Most modern languages are multi-paradigm. [..] And modern Java. Modern Java is still very definitely OOP and not multi-paradigm. Other JVM languages, like Scala or Kotlin, add more multi-paradigm features to that ecosystem, but modern Java doesn't.
- diroussel 2y agoIt tries to be OOP, but you can still implement a program with int, int[] and static methods. And you can’t subtype those. Other JVM languages, like scala, are more OO than Java.
- tkcranny 2y agoJava has made some big strides here to catch up with the functional and data-oriented features other languages are all adding. I was pretty surprised and impressed to see a modern example lately. There’s Record data types, stronger type inference with `var`, pretty great structural pattern matching, switch expressions (that return a value), stream apis for map, filter, and reduce etc. All of these move it further away from strictly OOP. And separate but still cool is a pretty neat virtual thread system too. Java has definitely had a bit of a glow up since I learned it in uni.
- smackeyacky 2y ago[flagged]
- dang 2y agoCan you please not post like this to HN, regardless of how wrong someone is or you feel they are? We're trying for something else here. If you wouldn't mind reviewing https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html and taking the intended spirit of the site more to heart, we'd be grateful.
- smackeyacky 2y agoMy bad, suitably chastened.
- deleted 2y ago[deleted]
- continuational 2y agoThis would be a lot more convincing if served with an example of a language where subtyping doesn't lead to more rough edges.
- jyounker 2y agoDude seems to be coming from a strange place if he thinks that subtyping is uncommon in programming languages. Java, Kotlin, Scala, C++, Python, Go, and C# all have subtyping of one sort or another, and that covers at least 80% of the code being written today.
- jolux 2y agoSeems like "Why You Need Algebraic Subtyping" might be a better title for this post.
- ivanjermakov 2y agoI think more common name for this is structured typing, so it's not confused with subtyping which is a kind of polymorphism.
- Rusky 2y agoAlgebraic subtyping and structured typing are not the same thing. Algebraic subtyping is a specific approach to type inference and checking of subtyping, which may or may not be used with structural types.
- smitty1e 2y ago> In this case, {x: int, y: int, z: int} is a subtype of {x: int, y: int} It seems like the former should be a supertype?
- almostgotcaught 2y agoGeneral -> specific Animal -> Dog (and a Dog will have more fields than an animal)
- smitty1e 2y agoAh, so. That helps. Thank you.
- jraph 2y agoNo, because all {x, y, z}s are {x, y}s, but the opposite is not true. Said differently, any function that applies to the general {x, y} also applies to the more specific {x, y, z} (it will just not use the z part) but a function that requires a {x, y, z} specifically will not work with all {x, y}s.
- yxhuvud 2y agoIn any case, it is clearly not following from his definitions of what a subtype is, since as soon as something depends on memory size the interopability is lost.
- kragen 2y agoNot necessarily? Usually the only operation that depends on memory size is constructing a new object of a type. With respect to memory size, operations on existing objects only depend on the memory size being at least big enough, other than maybe things like .clone().
- gugagore 2y agoSubtyping is one form of type polymorphism. Others include: - parametric polymorphism (generics, templates, ...) - ad hoc polymorphism (type classes are the nicest example) - https://en.wikipedia.org/wiki/Row_polymorphism https://en.wikipedia.org/wiki/Row_polymorphism I think this one is the most relevant for the record discussion.
- curtisszmania 2y ago[dead]
- ijustlovemath 2y agoI hear what the author is saying, but I think if composability is your goal, you should look no further than traits/interfaces. Accomplishes the same goals but actually far more general (which, according to the author, is a good thing)
- kragen 2y agoTrait and interface systems use a subtyping relation; they aren't alternatives to a subtyping relation.
- smadge 2y agoI think subtyping is the general concept in the programming language / type literature and interfaces / traits are an example of subtyping. If A implements interface B, A is a subtype of B.
- ijustlovemath 2y agothanks for clarifying that!
- pyjarrett 2y ago> However, existing programming languages have little or no subtyping Every "type" you use in Ada is actually a subtype. In Ada, "A subtype of a given type is a combination of the type, a constraint on values of the type, and certain attributes specific to the subtype". You don't ever refer to actual types in Ada, since creating a type with "type" actually creates an anonymous type and the name refers to the first subtype.[1] type Token_Kind is ( Identifier, String_Literal, -- many more ... -- These are character symbols and will be part of Token_Character_Symbol. Ampersand, -- ... Vertical_Bar, ); -- A subtype with a compile-time checked predicate. subtype Subprogram_Kind is Token_Kind with Static_Predicate => Subprogram_Kind in RW_Function | RW_Procedure; subtype Token_Character_Symbol is Token_Kind range Ampersand .. Vertical_Bar; > If you have a pointer with more permissions, it should still be usable in a place that only requires a pointer with fewer permissions This is exactly how "accessibility" of access types works in Ada[2]. If you have a pointer ("access type") to something on the heap, you can use it wherever an anonymous access type can be used. You can also create subtypes of access types which have the constraint of a "null exclusion". [1]: https://ada-lang.io/docs/arm/AA-3/AA-3.2#p1_3.2.1 https://ada-lang.io/docs/arm/AA-3/AA-3.2#p1_3.2.1 [2]: https://ada-lang.io/docs/arm/AA-3/AA-3.10 https://ada-lang.io/docs/arm/AA-3/AA-3.10
- RKFADU_UOFCCLEL 2y agoOkay, I can pass {x:int,y:int,z:int} to a function of type {x:int,y:int}, so what? Where is the argument for ditching nominal typing in the first place?
- hackburg 2y ago[dead]
- deleted 2y ago[deleted]