<p>[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.]</p>

<p>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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Structural_subtyping" rel="nofollow noreferrer">"structural subtyping"</a>.  If it cause no issues with behaviour, i.e., such plugging does not alter the behaviour expected, then we call it <a href="http://en.wikipedia.org/wiki/Behavioral_subtyping" rel="nofollow noreferrer">"behavioural subtyping"</a>.  (The "behaviour expected" will have to be formalised separately and many notions of behaviour are possible.)</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Nominative_type_system" rel="nofollow noreferrer">"nominal subtyping"</a>.  See the question on <a href="https://cstheory.stackexchange.com/questions/3991/implicit-vs-explicit-subtyping">Implicit vs explicit subtyping</a> 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.)</p>

<p>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 <em>nominal</em> subtypes.  The question is whether they are also <em>structural</em> 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.</p>

<p>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.</p>

<p>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 <em>not</em> a structural subtype of that of the superclass.  Widely used type-safe programming languages such as Java do not allow such subclasses.  So, they <em>restrict</em> the language to obtain type safety.  The programming language Eiffel is said to have sacrificed type-safety to obtain <em>flexibility</em> 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 <a href="http://www.cs.utexas.edu/~wcook/papers/InheritanceSubtyping90/CookPOPL90.pdf" rel="nofollow noreferrer">"Inheritance is not subtyping"</a>.  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 <a href="http://www.cs.williams.edu/~kim/Talks/NEPLS2-04.pdf" rel="nofollow noreferrer">presentation</a>.  Also helpful is a <a href="http://web.cecs.pdx.edu/~black/publications/pp.pdf" rel="nofollow noreferrer">position paper</a> of Andrew Black.</p>

<p>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.</p>

CC BY-SA 3.0
2012-03-11T21:12:13.040Z
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.
Andreas Rossberg
CC BY-SA 3.0
2012-03-12T11:16:55.127Z
@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.
Uday Reddy
CC BY-SA 3.0
2012-03-11T11:15:59.470Z
2012-03-11T13:08:48.330Z
2017-04-13T12:32:28.080Z
Uday Reddy
<p>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?</p>

CC BY-SA 3.0
2012-03-10T03:13:28.830Z
I wonder if this question (and others like it) might be redirected to the new cs.SE site when it enters public beta ?
Suresh Venkat
CC BY-SA 3.0
2012-03-10T05:50:00.307Z
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.
Kaveh
CC BY-SA 3.0
2012-03-10T07:47:35.017Z
This question is off topic. Read about subtyping in textbooks, such as John Reynold's [Theories of Programming Languages](http://books.google.si/books?id=2OwlTC4SOccC&pg=PA349&lpg=PA349&dq=reynolds+subtyping&source=bl&ots=lJjX3eNNdV&sig=G8AchzuULxhl7Xz5bUsrLdXrjOM&hl=en&sa=X&ei=0QZbT8iqEJHO4QS9hrSbDw&ved=0CBwQ6AEwAA#v=onepage&q=reynolds%20subtyping&f=false)
Andrej Bauer
CC BY-SA 3.0
2012-03-10T09:39:45.543Z
I am sympathetic to the question, and would like to see the answer(s).  Recall that the first paper on the subject, called [Semantics of Multiple Inheritance](http://lucacardelli.name/Papers/Inheritance.pdf), talks about subtyping and nothing else.  So the question is not as trivial as it is being made out to be.
Uday Reddy
CC BY-SA 3.0
2012-03-10T12:30:28.070Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-10T22:17:42.367Z
Oops, in the first sentence of my previous comment, I meant “No question was trivial when first answered….”
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-11T07:30:49.673Z
@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.
Uday Reddy
CC BY-SA 3.0
2012-03-11T09:36:25.633Z
In any case, it is easy enough to point the OP to Cook et al.'s paper of the same name: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.8635
Andreas Rossberg
CC BY-SA 3.0
2012-03-11T18:37:21.890Z
@Uday Reddy: Thank you for understanding my point.  After reading your answer, I agree that this question is not trivial.  I (virtually) take back my close vote.
Tsuyoshi Ito
<pl.programming-languages><type-theory><type-systems><object-oriented>
How does inheritance differ from subtyping?
RoboAlex
# How does inheritance differ from subtyping?

(Asked by: username_0 on 2012-03-10)

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?

**Tags:** pl.programming-languages, type-theory, type-systems, object-oriented

> **Comments:**
> **username_1**: I wonder if this question (and others like it) might be redirected to the new cs.SE site when it enters public beta ?  
> **username_2**: 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.  
> **username_3**: This question is off topic. Read about subtyping in textbooks, such as John Reynold's [Theories of Programming Languages](http://books.google.si/books?id=2OwlTC4SOccC&pg=PA349&lpg=PA349&dq=reynolds+subtyping&source=bl&ots=lJjX3eNNdV&sig=G8AchzuULxhl7Xz5bUsrLdXrjOM&hl=en&sa=X&ei=0QZbT8iqEJHO4QS9hrSbDw&ved=0CBwQ6AEwAA#v=onepage&q=reynolds%20subtyping&f=false)  
> **username_4**: I am sympathetic to the question, and would like to see the answer(s).  Recall that the first paper on the subject, called [Semantics of Multiple Inheritance](http://lucacardelli.name/Papers/Inheritance.pdf), talks about subtyping and nothing else.  So the question is not as trivial as it is being made out to be.  
> **username_5**: @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.  
> **username_5**: Oops, in the first sentence of my previous comment, I meant “No question was trivial when first answered….”  
> **username_4**: @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.  
> **username_6**: In any case, it is easy enough to point the OP to Cook et al.'s paper of the same name: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.8635  
> **username_5**: @username_4: Thank you for understanding my point.  After reading your answer, I agree that this question is not trivial.  I (virtually) take back my close vote.  

---

## 1 answers

### Answer by username_4 on 2012-03-11. Score: 19 | Accepted answer

[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"](http://en.wikipedia.org/wiki/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"](http://en.wikipedia.org/wiki/Behavioral_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"](http://en.wikipedia.org/wiki/Nominative_type_system). See the question on [Implicit vs explicit subtyping](https://cstheory.stackexchange.com/questions/3991/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"](http://www.cs.utexas.edu/~wcook/papers/InheritanceSubtyping90/CookPOPL90.pdf). 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](http://www.cs.williams.edu/~kim/Talks/NEPLS2-04.pdf). Also helpful is a [position paper](http://web.cecs.pdx.edu/~black/publications/pp.pdf) 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.

> **Comments:**
> **username_6**: 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.  
> **username_4**: @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.  

---

