Lecture Notes on Object-Oriented Programming

The Quality of Classes and OO Design

This collection of notes on OOP was never meant to stand alone. It also represents a view of OO circa early to mid 1990s. Some people still find them useful, so here they are, caveat emptor. Special thanks to Gilbert Benabou for taking to time to compile the first printable version of this document and inspiring us to provide it.
[PDF]
Printable Version

Polymorphic: from the Greek for "many forms."

When something (function argument, variable, etc) can be of more than one type.

Not limited to OO languages.

Seen in nearly every language in the form of operator overloading. For example in C, we have operators like +, -, *, etc, which operate for all primitive types. In other words we don't have separate "+ int", "+ float", "+ char" etc, operators for each type. The arguments to the + operator may be of a variety of types (the set of primitives). We can say that the + operator is polymorphic.

For OO languages polymorphism is tied up with substitutability. We design methods and we write client code that can operate on a set of types. What is common about these types is that they are substitutable for each other.

Advantages

In short, reusability of higher level abstractions. The higher we can push reuse, the better (more reliable) and cheaper (faster, greater reuse) our projects will be.

Traditional procedural languages and structured development allow for the reuse of lower level abstractions like data structures and algorithms for manipulating them. Budd uses the example of an algorithm for computing the length of a list. Written generically (at a high level, in other words) as a recursive algorithm in pseudo-C we have:

int length( list l) {
 if( l.link == NULL )
 return 1;
 else
 return 1 + length( l.link );
}

If you wanted to implement this in real C, you'd have to have a specific data structure. It would be something like this, for a list of integers:

struct listst {
 int value;
 struct listst *link;
};
int length( struct listst *lp) {
 if( lp->link == NULL)
 return 1;
 else
 return 1 + length(lp->link);
}

So the question is now, what can you use in your next project? The answer is:

  • the high level recursive algorithm design
  • the actual code, if you happen to be dealing with a linked list of integers

If you have a linked list of widgets in your next project, you'll have to re-write the length() function.

The goal of a language that supports polymorphism is to let us specify and reuse our algorithms or design.

Polymorphism is necessary for the sort of higher level reuse which is the goal of design patterns and frameworks.

There are several flavors of polymorphism in OO. All of them require that variables can be polymorphic. How a language supports polymorphic variables depends on whether it is statically or dynamically bound.

Binding

When is the method that is invoked by a message determined? If it is at compile-time (static binding) then you lose a lot of flexibility. If it is at run-time (dynamic binding) then you have polymorphism, or the ability for each object to react differently to the same message.

An object-oriented language may provide either form of typing (static or dynamic) and either form of binding (static or dynamic), which makes four possibilities to consider. Traditionally, non-OO high level languages use static typing and static binding. Pure OO languages use dynamic typing and dynamic binding.

C++ implements a limited form of polymorphism (dynamic binding) with virtual methods.

Statically bound languages differentiate between the static and the dynamic type of a variable. The compile-time checking is done against the static type. The dynamic type may be one of the subtypes (subclasses) of the static type.

Dynamically bound languages can be very loose, including a completely generic reference type that can refer to any sort of object. These languages push typing errors in to run-time.

Example

Accumulate the total cost of items in inventory.

float cost = 0.0;
 for( all objects obj in inventory ){
 typeOfObject = obj.type();
 switch( typeOfObject ){
 case bolts: cost += obj.boltCost();
 break;
 case nuts: cost += obj.nutCost();
 break;
 case screws: cost += obj.screwCost();
 break;
 }
}

Each object must be sent a message unique to its type, so we have one line of code for each object class or type. With polymorphism we don't have the same restriction:

float cost = 0.0;
for( all objects obj in inventory ){
 cost += obj.ost();
}

The advantage is really obvious when you add washers to your inventory.

Example: Edit->Cut, Copy, Paste

Incorporating a single Edit menu item into your application lets the user perform the same operation (push a button) to cut a character, word, sound, graphic, etc, even though the button push results in very different objects being sent the "cut" message. At compile-time all you know is that the "cut" message will be sent to a selected object; you don't know the class of that object. At run-time the actual code that is executed is determined by the type of the selected object.

Without dynamic binding, the alternative would be to have Cut_Sound, Cut_Word, Cut_Graphic... Or you would need a large case statement in your controller (where the code for the Edit menu is) that sent a message which depended on the type of object currently selected. In either case, you must change the controller's code if you ever add another data type.

With dynamic binding you never need to change your controller since all it knows is that it will send a "cut" message to some object. The class of that object may not even exist when the controller is created.

There are several "flavors" of polymorphism if you look broadly at computer languages in general.

  1. Pure polymorphism - when a single function (think of a piece of client code) can be applied to objects of many types.
  2. Overriding - inheritance of specialization and extension
  3. Deferred methods - inheritance of specification
  4. Generics - parameterizing the data types of a class so that common behavior can be applied to various types
  5. Overloading or ad-hoc polymorphism - when multiple functions have the same name but are distinguished by their parameters

Pure polymorphism

As used by Budd, and other authors, "pure" polymorphism refers to a function which can take parameters of many types. This ocurrs as a natural result of the isa relationship. Subclasses which are subtypes are substitutable for their base classes. Clients can't tell the difference and don't care. A piece of code can be written in terms of what is common to all the objects (i.e. the interface of the base class).

An example would be the Edit menu of a GUI application. The functions, or behavior, that is being coded is to let users

  • select, cut, copy, and paste

The objects which these actions apply to may be of a variety of classes (text, audio, image, video, etc). Without polymorphism, you'd have to code this as follows:

void cut(selected_object) {
 switch( type of selected_object ) {
 case text:
 selected_object.cutText();
 break;
 case audio:
 break;
 // etc
}

Every time you added a data type you'd have to re-write the above function. With polymorphism we can write out cut function abstractly and have it work with a variety of types, including those not yet dreamed of.

Overriding

This sort of polymorphism supports the inheritance of specialization and extension. A subclass implements a different version, or extends the existing version, of a base class method. The method name is the same, but subtypes implement it differently.

This is distinct from overloading because of the type relationship between the overriding classes.

Deferred methods

This sort of polymorphism supports the inheritance of specification. A method may have no implementation - it could be just an interface specification. Subclasses are required to implement such methods, but in the meantime, clients can be written in terms of the abstract method without worrying about how each subclass implements the method.

Generics

Container classes provide the best example of the use of generics, or parameterized classes.

The behavior common to container classes representing common data structures (queues, stacks, lists, etc) is completely independent (at the high level) of the particular data type being stored in the container.

One solution is to build a very generic container that will hold objects of any type. But what you lose with this approach is the safety of having the compiler type check your code.

What you want are type-safe containers, where the container is code is written in terms of a generic type, but the container class can be created with a specific type and the compiler will check with this specific type.

Overloading

The name of the function is polymorphic. The compiler uses the type (and possibly the number) of parameters to distinguish between multiple functions with the same name.

Basic operators for primitives support overloading.

An overloaded operator or function is not required to have any particular relationship to the class hierarchy. The function being overloaded may be in completely unrelated classes. So, for example, the draw() method works for Artists, Shapes, and CardDealers.

No semantic similarity is implied by overloading. Overloading of function names is likely if you're using good names, since there is redundancy and multiple meaning in human languages.