In programming language perspective, what is mean by subtyping? I heard that "Inheritance is not Subtyping". Then what are the differences between inheritance and subtyping?
$\begingroup$
$\endgroup$
9
-
6$\begingroup$ I wonder if this question (and others like it) might be redirected to the new cs.SE site when it enters public beta ? $\endgroup$– Suresh VenkatMar 10, 2012 at 3:13
-
1$\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$– KavehMar 10, 2012 at 5:50
-
3$\begingroup$ @UdayReddy: No question was not trivial when first answered, but we should make a decision from the modern point of view. The same argument as yours would imply that the question about Dijkstra’s algorithm is on-topic because the first paper talks about it and nothing else. $\endgroup$– Tsuyoshi ItoMar 10, 2012 at 12:30
-
3$\begingroup$ @TsuyoshiIto The analogy is not appropriate because Dijkstra's first paper solved the problem whereas Cardelli's first paper here created the problem. Still, I take your point that we don't measure the state of the art based on the first paper. Let me assure you that the differences between inheritance and subtyping do not represent a solved problem, and I anticipate that the issue will be debated for another 20 years at least. The questioner might be advised to do some additional homework and edit the question to clarify the research-level issues. $\endgroup$– Uday ReddyMar 11, 2012 at 7:30
-
3$\begingroup$ In any case, it is easy enough to point the OP to Cook et al.'s paper of the same name: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.8635 $\endgroup$– Andreas RossbergMar 11, 2012 at 9:36
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
2
[I haven't thought deeply about the issues of object-oriented type systems, but I will say what I know to get the discussion going.]
We say that $A$ is a subtype of $B$ if all $A$-typed values can be used in every context where $B$-typed values are expected. Or, to put another way, $A$-typed values can "masquerade" as $B$-typed values.
If such masquerading poses no issues with type checking, i.e., plugging in $A$-typed values where $B$-typed values are needed continues to type check, we call it "structural subtyping". If it cause no issues with behaviour, i.e., such plugging does not alter the behaviour expected, then we call it "behavioural subtyping". (The "behaviour expected" will have to be formalised separately and many notions of behaviour are possible.)
Structural subtyping does not ensure behavioural subtyping because the structure of a type might match for accidental reasons. However, defining the behaviour expected is not easy. So, many programming languages use an intermediate point, where the user has to declare which type is a subtype of which. This is referred to as "nominal subtyping". See the question on Implicit vs explicit subtyping for a discussion of this issue. The idea is that the programmer has to ensure behavioural subtyping for all declared subtypes using his own ingenuity. The language cannot offer any help. However, all declared subtypes must be at least structural subtypes. Otherwise, the program would fail to type check. The language can help ensure this. (Some programming languages don't have good enough type systems to ensure this at compile-time. If so, the type failure would be detected at run-time, or perhaps wrong results might be produced. Such type holes are obviously undesirable.)
When one defines subclasses in object oriented programs, one typically adds publicly visible fields (or methods). In most programming languages, such subclasses are regarded as nominal subtypes. The question is whether they are also structural subtypes. If they are not, i.e., the programming language allows one to declare nominal subtypes that are not structural subtypes, then there would be type holes in the programming language.
In simple cases, adding fields works fine. The type of the superclass expects fewer fields than the type of the subclass. So, if you plug in an instance of a subclass where an instance of the sueprclass is expected, the program will just ignore the additional fields provided and nothing goes wrong.
However, if the superclass or subclass has methods that take arguments of the same type as itself, or return results of the same type as itself, then problems arise. Then the interface type of the subclass is not a structural subtype of that of the superclass. Widely used type-safe programming languages such as Java do not allow such subclasses. So, they restrict the language to obtain type safety. The programming language Eiffel is said to have sacrificed type-safety to obtain flexibility instead. If one designs a strong type system that retains flexibility, one must give up the principle that subclasses give rise to subtypes. Hence the title of the paper "Inheritance is not subtyping". The authors propose a different notion of higher-order subtyping which works instead. Kim Bruce also has a closely related proposal called "matching" that achieves the same effect. See this presentation. Also helpful is a position paper of Andrew Black.
The semantics community is probably at fault for largely ignoring the problem. We have traditionally regarded it as a practical type-system engineering issue that is of little theoretical interest. If that is not the case and there is indeed some semantics work in the area, I hope the other people will mention them.
-
1$\begingroup$ It is perhaps also worth mentioning that there are actual languages out there that have successfully decoupled subtyping from inheritance, e.g. Ocaml in its object system. $\endgroup$ Mar 11, 2012 at 21:12
-
$\begingroup$ @AndreasRossberg Indeed, OCaml wasn't in my frame when I wrote that answer. I suppose OCaml doesn't have nominal subtyping at all. So, some of these issues wouldn't arise. But there is the possibility that types might match accidentally even if the behaviour doesn't, and the type system won't be able to help catch mistakes of that kind. $\endgroup$ Mar 12, 2012 at 11:16