Gregory M. Kapfhammer

Associate Professor of Computer Science

http://www.cs.allegheny.edu/~gkapfham/

  
View  Edit  Uploads  History  Top  Changes  Search

Chapter Seven: Type Hierarchy

  • Liskov asserts that a compiler may not be able to determine what code to run when a method is called. Give an example to demonstrate that this is actually true. Furthermore, discuss a solution that will enable the dispatch to the desired method.


Suppose we have two classes- CubeShape and CylinderShape, both subclasses of Shape. All three classes have a method, calcVolume(Shape s). When this method is compiled, the compiler does not know whether the actual type of s refers to CubeShape or CylinderShape. But it must know which class' method to use because each shape's volume is calculated differently.

The compiler does the following:
  • "The compiler deduces an apparent type for each object by using the information in variable and method declarations."
  • "Each object has ana ctual type that it receives when it is created: this is the type defined by the class that constructs it."
  • "The compiler ensures the apparent type it deduces for an object is always a supertpe of the actual type of the object."
  • "The compiler determines what calls are legal based on the object's apparent type."
  • "Dispatching causes method calls to go to the objects actual code- that is the code provided by its class."
"There are several ways to implement dispatching. One approach is to have objects contain, in addition to their instance variables, a pointer to a dispatch vector, which contains pointers to the implementations of the object's methods." How this works- "Code to call a method, code retrieves the dispatch vector from the object, retrieves the address of the method's code from the appropriate slot of the dispatch vector, and then branches to that address." So to in order to dispatch to the correct method, the compiler essentially examines the dispatch vector of the object passed to the method, and based on the contents of the dispatch vector, calls the proper method. So if calcVolume(Shape s) was called on a CubeShape, the compiler would examine the dispatch vector of s and then call the calcVolume method of CubeShape.

Dan Fiedler

An example is that suppose you have a supertype class of sportTeams and subtype classes hockeyTeam and footballTeam. All three classes have a method called surface(sportsTeam t) that returns the type of surface each team plays on (Hockey = Ice, Football = Grass). To figure out what method to use, the compiler does:

1) The compiler deduces an apparent type for each object by using the information in variable and method declarations.
2) Each object has ana ctual type that it receives when it is created: this is the type defined by the class that constructs it.
3) The compiler ensures the apparent type it deduces for an object is always a supertpe of the actual type of the object.
4) The compiler determines what calls are legal based on the object's apparent type.
5) Dispatching causes method calls to go to the objects actual code- that is the code provided by its class.

A solution is code to call a method that retrieves the dispatch vector from the object and then retrieves the address of the method's code from the appropriate slot of the dispatch vector, and then branch to that address which would be the correct method. Such as in my previous example, if surface(sportsTeam t) was called for hockeyTeam, the compiler would retrieve the dispatch vector, and then choose the appropriate address for the surface method in hockeyTeam.

John Pacino
  • The Java programming language provides the notion of an abstract class and an interface. Provide some guidelines that might enable us to chose between these two constructs.


An abstract class is a partial implementation of a class (type). It has regular methods, with code, and abstract methods, without code (only the method declaration and parameters,) and may have instance variables. An interface defines a class (type). It has only nonstatic, abstract, public methods.

Abstract - instance variables, regular methods and abstract methods
Interface- only abstract methods

Dan Fiedler

Can an interface have fields inside of it? Greg

In a word, no. Interfaces do not contain any data, only methods to be defined by later implementations of that interface. Dan Fiedler

An abstract class provides only a partial implementation of a type. It may have one or more constructors with instance variables. Since the abstract class has no objects, the constructors can not be called by users but can be used by the subclasses to initialize. An abstract class contains both abstract methods and regular methods.

An interface is a class used to define a type. It also gives either a complete or partial implementation. An interface also only has abstract methods.

John Pacino

I assume that you meant to type that an abstract class is used to define a type and that it can have either a complete or partial implementation. Is this the case? Is it possible for an interface to have fields inside of it? You did not clearly state your view on this issue. Greg

  • Clearly describe the Liskov substitution principle. Make sure that your response includes a review of the three rules that must be supported. What is the main purpose of this principle? What insight does this principle on an inheritance hierarchy?

Liskov Substitution Principle-
Users can write and reason about subtypes, using the same rules and reasoning that apply to the supertypes. Code written in a subtype must behave just as if it used the supertype.
  • Signature Rule - "The subtype objects must have all the methods of the supertype, and the signatures of the subtype methods must be compatible with the signature of the corresponding supertype methods."
("The supertype's definition is also type correct for the subtype.")
  • Methods Rule - "Calls of these subtype methods must "behave like" calls to the corresponding supertype methods.
  • Properties Rule - "The subtype must preserve all properties that can be proved about supertype objects."
("Subtype objects behave enough like supertype objects that code written in terms of the supertype won't notice the difference.")

This principle allows code to be written that deals with as much abstraction/detail as it needs to. Some methods only needs the basics of an object (they use the supertype) , other methods need more detail (they use the subtype), but if one of the former methods used a subtype it would still work correctly.

The question "What insight does this principle on an inheritance hiearchy?" does not make any sense, I think we need another word or two in there. (And hierarchy was spelled incorrectly, I fixed it)

Dan Fiedler

Substitution rules:
1) Signature Rule - The subtype objects must have all the methods of the supertype, and the signatures of the supertype methods must be compatible with the signatures of the corresponding supertype methods.
2) Methods Rule - Calls of these subtypes methods must behave like calls to the corresponding supertype methods.
3) Properties Rule - The subtype must preserve all properties that can be proved about supertype objects.

The main purpose of the principle is that so the users can write and reason about code just using the supertype specification.

Some insight that this principle might have on inheritance hierarchy is when you are building a hierarchy your supertypes and subtypes are going to fall under one of these rules.

John Pacino

A comment for you both: it seems that the LSP indicates that inheritance hierarchies should be based upon behavior. That is, even though Square ISA Rectangle makes sense when we see it at first glance, this is not an appropriate inheritance hierarchy! Greg

  • Briefly summarize the benefits that are normally associated with type hierarchies in object-oriented programming languages.
  • "Hierarchy can be used to define the relationship among a group of types, making it easier to understand the group as a whole."
  • "Hierarchy allows code to be written in terms of a supertype, yet work for many types- all the subtypes of that supertype."
  • "Hierarchy provides the extensibility: code can be written in terms of a supertype, yet continue to work when subtypes are defined later."
  • "All of these benefits can be obtained only if subtypes obey the substitution principle."

In essence, as I said before, Hierarchies allow code to be written that deals with as much abstraction/detail as a class, method, or object needs to. But these Hierarchies are dependant upon the correct use of the Substition Principle.

Dan Fiedler

Some benefits of type hierarchies are:
1) Hierarchy can be used to define the relationship among a group of types, making it easier to understand the group as a whole.
2) Hierarchy allows code to be written in terms of a supertype, yet work for many types - all the subtypes of that supertype.
3) Hierarchy provides extensibility: code can be written in terms of a supertype, yet continue to work when a subtypes are defined later
4) All of these benefits can be obtained only if subtypes obey the substitution principle.

John Pacino

Link to this Page

  • Software Design last edited on 14 October 2004 at 2:29 pm by aldenv28.allegheny.edu