I'm reading some slides of a class on object oriented programming languages and stepped into the type-subtype definition:
Barbara Liskov, “Data Abstraction and Hierarchy,” SIGPLAN Notices, 23,5 (May, 1988):
What is wanted here is something like the following substitution property: If for each object o_s of type S there is an object o_T of type T such that for all programs P
defined in terms of T, the behavior of P is unchanged when o_S is substituted for o_T then S is a subtype of T
Then it goes with an example:
Point = { x:Integer, y:Integer }
PositivePoint = { x:Positive, y:Positive }
where Positive = { k:Integer | k > 0 }Can we say that PositivePoint ≤ Point?
Yes, because an element of type PositivePoint may always replace an element of type Point in a program defined in Point terms!
Now... for me it seems it should be quite the opposite: Point ≤ PositivePoint because I couldn't use PositivePoint in a program that uses Point with negative coordinates, while I could to the opposite.
I doubted if the syntax was Type ≤ Sub-type
or Sub-Type ≤ Type
, but the statement seems more clear, what's wrong then?
Just to make things easier the question is:
Can you say that PositivePoint
is a subtype of Point
?
Why?
I report here what I wrote in a comment hoping it will make my problem clearer:
Suppose that the program has to draw a square map from
Point
(-100, -100) toPoint
(100, 100). What would happen if you use typePositivePoint
? Would the program's behavior be unchanged? It would not. This "unchanged behavior" is the only thing I don't get. If the definition of subtype was simplyinheriting and overriding
from an other type it would be ok, but it doesn't seem to be the case.
A subtype relationship connects an entity that defines the category and two or more additional entities that define each of the elements of the category. The parent entity of the category is considered the supertype and each child entity is considered a subtype.
For example, we say that water is a subtype of liquid because it is a specific type of liquid. The converse is that liquid is a supertype of water. In the context of natural language, a subtype is a hyponym and a supertype is a hypernym.
Subtypes and supertypes can have attributes. Attributes particular to individual subtypes are allocated to those subtypes; common attributes are allocated to the supertype. Subtypes and supertypes can participate in relationships.
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. The given type is called the type of the subtype. Similarly, the associated constraint is called the constraint of the subtype.
Liskov is correct, PositivePoint ≤ Point, because PositivePoint is a refinement of Point. Any code that uses Point must also be able to use PositivePoint, because there was always the possibility that Point's coordinates were positive anyway. The reverse is not true, because code using PositivePoint may act under the assumption that the coordinates are always positive, and replacing PositivePoint with Point would break that assumption.
Note that she's not saying that a PositivePoint can replace a Point, just that a PositivePoint can be used where a Point is needed.
You can model the type relationships through subsets.
PositivePoint ⊂ Point
holds for the same reason as PositiveInt ⊂ Int
does: Positive numbers are a subset of all possible numbers!
Every PositivePoint
belongs to the Point
s, but not other way round.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With