[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [CSci202] / polymorphism
[Text Version] [Syllabus] [Schedule] [Glossary] [Resources] [Grading] [Contact] [Question] [Search ]
Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
Labs: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10]
Wed Apr 13 13:41:46 PDT 2011

Contents


    Polymorphism

      The word comes from Latin or Greek: "poly" means "many" and "morph" means "shape".

      In programming Polymorphism means that we can write the special code for many different "shapes" of data and the computer figures out which special programming to use.

      This is good for programmers. Whenever the computer's power does some of the work for us, we don't have to work as hard. However, learning how it works takes a little time. Thus, polymorphism is a power-tool: it saves human work when you use it. But, it takes a little extra investment to make or buy the tool.

      For example, operator "+" has many meanings and the compiler figures out which to use. This "overloading" is the simplest from of polymorphism. In object-oriented programs and the UML objects of different classes automatically select the methods belonging to their own classes as the program runs. This is a more complex form of polymorphism the uses Late Binding.

      Polymorphism comes in several forms:

      Purists will tell you that only the last one above is really polymorphism.

      Polymorphism by Overloading

      You have already met the idea that "+" is polymorphic: it can add two integers, two floats, two doubles, two chars, .... Each time the code at the machine's level is different but the C++ symbol is the same. A symbol that has multiple meanings is said to be overloaded. The C++ compiler looks at the context of the symbol to determine what you mean by it. You should remember that
       		1/2
      is 0 but
       		1.0/2
      has the value 0.5.

      You can also overload functions - one name with different arguments.

      You can even add further meanings to the operators in C++. We don't have time to do this but it is not as hard as you might think.

      Polymorphism by Overriding

      If a Base class called B has a function 'f()' that outputs 'BB' and a derived class D has a function with the same name that outputs 'DD' then the D version can override the B version depending on the type of the object that f is applied to. If b is a B and d is a D then b.f() executes the B version of f and d.f() executes the D version. For example:
       	#include <iostream>
       	using namespace std;
       	class B          { public: void f(){cout <<"BB"; } };
       	class D: public B{ public: void f(){cout <<"DD"; } };
      
      
       	main(){
       		B b; D d;
       		b.f(); d.f(); d.B::f();
       	}//end main
      outputs 'BBDDBB'. (Please down load this code [ poly1.cpp ] and test it).

      So the effect of f on an object fits that object's type.

      The compiler sorts this kind of polymorphism out, before the program starts running. The program (once running) has no decision to make. It has been told which function is which.

      This works when there are several different derived classes.

       	#include <iostream>
       	using namespace std;
       	class B           { public: void f(){cout <<"BB"; } };
       	class D1: public B{ public: void f(){cout <<"D1"; } };
       	class D2: public B{ public: void f(){cout <<"D2"; } };
       	main(){
       		B b;   D1 d1;   D2 d2;
       		b.f(); d1.f();  d1.B::f();
       		       d2.f();  d2.B::f();
       	}//end main
      outputs: "BBD1BBD2BB". (Try [ poly2.cpp ] )

      But not quite polymorphic enough!

      However if you replace the above main program by this:
       	main(){
       		B* p;
                p = new D1; p->f(); p->B::f();
                p = new D2; p->f(); p->B::f();
       	}//end main
      [ poly3.cpp ] (Recall that p->f() means the same thing as (*p).f(), namely, to call the f operation/function of the object that p points to)

      The above will compile because the address of a D1 (new D1 for example) is also the address of a B - because each D1 object starts with a B object. Similarly new D2 is also an address of a B. Thus the pointer p is polymorphic in the sense that it can point at objects of three different types: B, D1, and D2. It can even extract public data from the B part of objects of these three types.

      We get a surprise when we run the above code however because the indirect access to functions is not polymorphic here. We don't get "D1BBD2BB". Instead we get "BBBBBBBB".

      The compiler compiles 'p->f()' without trying to find the previous assignment to 'p'. The compiler looks at p->f() and sees (*p).f() plus the declaration B *p;. Now the declaration says that *p is a B, and so the compile uses B's version of f.

      In the above case you can figure out what p points to at different times but the compiler can not. There is no way for the compiler to predict the complete run without running the program.

      Worse even intelligent human beings can not always predict whether a p is pointing at a B, a D1, or a D2. A simple example of this is:

       		if(user_input.indicates_d1()) p=new D1; else p=new D2;
      So the compiler always uses the declared type of p (B*) and deduces that this is pointing at a B, and gives us B's function.

      Arrays and Vectors of Items of different type

      We could program round the above. But suppose we have an array of items each either being a D1 or D2. We might send a pointer down the array or an iterator across a vector - and we would like it to treat each item as itself not a BB! The same thing happens if the D1s and D2s are in a List, Stack or Queue, or any other data structure.

      Notice that a vector (and other container) can only be used to collect together objects of the same size. You should not expect subscripts, pointer arithmetic, and iterators to work with vectors or arrays of B's. A D1 and a D2 will take up more space than a B, but p++ moves on p from one B to the next B, even if p is actually pointing at a D1 or D2. This means that we can't have an array of B's and try to make some of them D1s!

      We get round this blockage by having arrays of pointers to the different objects.... because all pointers take up the same space, however much data they are pointing at. Thus to organize a collection of B's, D1s, and D2's into a vector we would use

       		vector < B* > v;
      because pointers to D1 and D2 also point to B.

      You can also use pointers in other containers as well.

       		B* (a [10] );
       		list < B* > l;

      Polymorphism by Ignorance

      Since all pointers look alike, whatever they point at (think of a finger pointing at an ant, an elephant, and a castle... the finger still fits in the same glove...). There is even a notation for the idea of a pointer to an object of unknown type. These are called void pointers and in C and C++ they are declared like this:
       		void * p;
      [ Warning ] However the compiler has no idea what can be done with these pointers so '*p' can not be accessed (its size is unknown) or added (it may not be a number or a string), etc. Neither can we write 'p++' or '++p' because the compiler does not know where the next item is. Neither will (*p).f or p->f compile because the compiler does not know whether p is pointing at a class with member f at all!

      Writing code to handle these is time consuming and difficult. As a result void* is deprecated. Instead we group similar classes under a common parent and use a pointer to the parent.

      In programming, ignorance is not bliss!

      Polymorphism by Late Binding

      The story so far:
      1. We can use the compiler to sort out the correct functions to be used with a function whenever the object's type is obvious to the compiler.
      2. If we wish to store a collection of objects that have different behaviors in a common data structure then need to store pointers to the different objects.
      3. This is OK when the objects are all derived from a common base class.
      4. The problem is that the compiler can only see the base class and so we always get operations for that class!

      5. Similarly we may need a single variable to point at different types of objects at different times, and for the behavior of the pointed at object to be executed, rather than the base object.

      Object Oriented languages need a simple way to handle this indirect polymorphism. The simplest words describing what we want is "late binding". We don't want the compiler to choose (or bind) the meaning of the function. We want to delay the choice (binding) until the program is running. So we want the compiler to generate code that makes the right decision, on the fly, automatically. In other words, full polymorphism requires that member functions are resolved as the program executes, rather than when the compiler scans the code.

    1. late_binding::=delaying the choice of the meaning of something until the program is executing.

      Virtual Functions

      In other languages (Smalltalk and Java) late binding is assumed. Similarly in UML inheritance(generalization) implies late binding.

      C++ uses a particular but quite efficient trick to get late binding. It is still not be as fast as making the compiler do the resolution of course. And because C++ programmers traditionally prefer fast code it arrived late on the C scene and is not the default.

      The C++ syntax is rather weird for its purpose. It uses the word virtual. Here are three classes you saw previously but with a simple change: the f function is now virtual.

       	#include <iostream>
       	using namespace std;
       	class BV{             public: virtual void f(){cout <<"BB"; } };
       	class D1V: public BV{ public: void f(){cout <<"D1"; } };
       	class D2V: public BV{ public: void f(){cout <<"D2"; } };
       	main(){
       	        BV* p;
       	        p = new D1V; p->f(); p->BV::f();
       	        p = new D2V; p->f(); p->BV::f();
       	}//end main
      [ poly4.cpp ]

      The code outputs "D1BBD2BB" as you probably expected. Notice that the code for D1V is almost exactly the same as that of D1. Only the base class (BV) has the word virtual in it.

    2. virtual_function::=a member function that is resolved when the program is running, rather than when the compiler is running.

      Here is an example of a vector of BV pointers some of which are refer to D1Vs and some to D2Vs:

       	#include <iostream>
       	#include <vector>
       	using namespace std;
       	class BV            { public: virtual void f(){cout <<"BB"; } };
       	class D1V: public BV{ public: void f(){cout <<"D1"; } };
       	class D2V: public BV{ public: void f(){cout <<"D2"; } };
      
      
       	int main(){
       	        vector <BV*> a;
       	        a.push_back(new D1V);
       	        a.push_back(new D2V);
       	        a.push_back(new D2V);
       	        a.push_back(new D1V);
       	      for( int i = 0; i < a.size(); ++i)
       	              a[i] -> f();
       	}//end main
      [ poly5.cpp ]

      The following example show how we can have an array of objects of different types, and each one knows how to behave without a single case or if. This array is effectively a mixture of D1s and D2s with each automatically doing its own thing.

       	#include <iostream>
       	using namespace std;
       	class BV{             public: virtual void f(){cout <<"BB"; } };
       	class D1V: public BV{ public: void f(){cout <<"D1"; } };
       	class D2V: public BV{ public: void f(){cout <<"D2"; } };
       	main(){
       		BV *a[]={ new D1V, new D2V, new D2V, new D1V};
       		for( int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
       			a[i] -> f();
       	}//end main
      By the way, notice these other techniques in the code above:
      Net
      1. You can create an array of objects with explicit initialization.
      2. You can find out the length of an array by using sizeof(array)/sizeof(item)

      (End of Net)

      Testing Virtual Functions

      Notice that to show that a function is virtual you must access it by using a pointer to the base class that is attached to different derived objects. Suppose that class X is derived from Y, that Y has a virtual function v() that is over-ridden in X:
       	class Y{public: virtual void v(){...} ... };
       	class X: public Y{ ... public: void v(){...} ... };
      then the smallest test that v is working includes statements like these:
       		Y* p = new X;
       		p->v();
      and
       		p=new Y;
       		p->v();
      If there is no pointer and indirect access the 'virtual' has no effect.

      No Virtual Data

      The ability for a pointer to an object to lead to the function associated with the object (rather than the type of pointer) does not happen with data. Data references are always handled by the compiler -- in jargon: "statically". Here is an example where I declare two data items -- with the same name in a base and a derived class.
       class B            { public: string s; };
       class D : public B { public: string s; };
      
      
       main()
       {	B b;  b.s="B"; cout << "b.s = "<< b.s << endl;
       	D d;  d.s="D"; d.B::s="B::D";
       	cout <<"d.s =" << d.s << endl;
       	cout << "d.B::s =" << d.B::s << endl;
       	B* p;
       	p=&b; cout << "p->s =" << p->s << endl;
       	p=&d; cout << "p->s =" << p->s << endl;
       }
      [ dataNotPoly.cpp ]

      If you compile and run this you will see that "p->s" picks up the "s" inside "B" not in "D" even when "p" points at a "D".

      Review Example

      Here are three attempts at writing a program that has an array of Students, some of which are Undergraduates, and some are Graduates. Look at the code of the three versions and see if you can predict what each will do:
      1. vector <Student> [ polystud.cpp ]
      2. vector <Student*> [ polystud2.cpp ]
      3. Success [ polystud3.cpp ]

        You should be able to figure it out without testing them!


      Key Point: Polymorphic Pointers Rule

      To make C++ objects work the way most people feel they should work we need two things
      1. The functions in the classes must be virtual.
      2. We must not copy them into objects of the base class.

      The second point leads to these rules
      • Store pointers to objects in data structures, not copies of objects.
      • Pass parameters/arguments by reference or as pointers, not via copying the value.

      This is wise for another reason: If our Student data has 1,024 bytes of data, we would be wasteful copying and storing these when we can copy and store a 4 byte pointer!

      Polymorphism in UML

      In the UML it is assumed that if an operation is applied to an object and there are several alternative classes that have the operation defined then the object to which the operation is applied always determines the operation that is executed. This is even true if the access to the object is via a pointer in C++ using syntax like this:
       		pointer->function(arguments)
      The UML remains
       		pointer.function(arguments)

      For example if there is a base class name Base with a function f() and a derived class called Derived that overides f() then an object in the Derived class wil execute Derived's f, and an object in the Base class executes the Base f. This is true even if the access is via a pointer to the object and if the variable holding the pointer is declared to be of the Base type.

      UML diagram of pointer to general class

      When you code a design drawn in the UML into C++ you should initially assume that all member functions are virtual and only remove th word 'virtual' if you are sure that polymorphism is not needed.

      A Good Example

      Paul Tonning found a delightful example of this in a text book when he was a graduate student and technician here. It suggested that you could model a bowl of cereal as an array of crispies... each one either going "Snap", "Crackle", or "Pop" as defined. Applying a function to each crisp in turn gets the correct sound. Please try this. Low fat, no calories... [ rice.cc ]

      Snap Cracle Pop are special Crispies

      A Zoo Simulation of Animals

      You might like to think about visitting a the zoo. Each animal has a different number of legs and its own name.

      UML diagram of zoo

      Simplest doesn't work: [ animal.cpp ] [ animal2.cpp ] [ animal3.cpp ] [ animal4.cpp ] [ animal5.cpp ] [ animal6.cpp ] [ animal7.cpp ]

      More Examples of virtual functions

      Here are a two examples of how virtual functions differ from non-virtual functions: [ vf.cc ] [ virtual_fun.cc ]

      Here are two simple examples of objects that know their own type at run time, as they change.

      RunTime Type Identification(RTTI): [ rtti.cc ]

      Source Code Control - classes that identify their version in the compiled code using a standard formatted char* called a sccsid(Source Code Control System Identifier): [ vn.cpp ]

      Polymorphism simplifies coding

      Using this kind of polymorphism - where a base class has more than one derived class and the variations are in virtual functions - means you don't have to write so many 'if()...else...' and 'switch(...)...' statements in your code.

      This makes C++ code smaller than C code in many cases. However see the [ Code Bloat Warning ] below

      Family tree example

      This is an extended example where a set of classes have been created and model the development of a family. Notice how the gender of a person is modeled by their class. Notice how this means that it not easy for a person to change their gender - variables are fixed to their declared type throughout their life. Gender does not appear as an item of data about a Person but a const function that reports (automatically) the gender of that class of person.

      This is also an example of a moderately complex linked data structure.

      Exercise: The main program records the marriage of a couple and the subsequent birth of twins. Suppose they have now had a boy - add commands to record suitable invented data and then test to see if it has been stored correctly.

    . . . . . . . . . ( end of section Polymorphism) <<Contents | End>>

    Next

    See Abstraction [ abstraction.html ]

    Glossary

  1. automagically::jargon=something that is automatic and so neat that it does precisely what you wanted as if it was magic.

  2. inheritance::= See http://cse.csusb.edu/dick/samples/glossary.html#inheritance

  3. polymorphism::= See http://cse.csusb.edu/dick/samples/glossary.html#polymorphism

  4. UML::= See http://cse.csusb.edu/dick/samples/uml.html

    Warning

    Do not confuse 'void*' with the use of 'void' in a function specification or header. C/C++ uses the same word in two different ways. In void* it means "unknown data", and in a function spec 'void name(...)' it means "No useful data".

    The designers of C and C++ preferred to keep the number of reserved words as small as possible, even if it is confusing when you first meet them.

    Code Bloat Warning

    However in some early projects, people found their compiled programs were much bigger than they expected. They found that their compiler was not using an efficient implementation of their virtual functions. Here each object stored within it the addresses of its virtual functions. Each virtual function need at least 16 bits in every object that had that function as a virtual member. The compiler produced code that told the program to call the function whose address was in the object (this is simple and fast...). However if your program had a thousand objects, each with 10 virtual functions then your data needed 20,000 more bytes than you had expected on from the data members in the object. This was called code bloat.

    This may not be a big problem with later compilers. These compilers construct a single table of function addresses for each class of object rather than a table for each object. The object now needs a something like a single byte of storage to encode its class. Suppose that the compiler meets a call of a virtual function on an object in an unknown type or class called C. It produces code that does the following:


    1. extract the code for the objects class from the object
    2. Goto the table for this class
    3. Pick up the address of the function from the table
    4. Execute this function.

    This is slower but the data in the program has shrunk by 1,000*10*2 - 1,000 + 10*2*number_of classes.

. . . . . . . . . ( end of section Inheritance and Polymorphism) <<Contents | End>>

Glossary

  • accessor::=`A Function that accesses information in an object with out changing the object in any visible way". In C++ this is called a "const function". In the UML it is called a query.
  • Algorithm::=A precise description of a series of steps to attain a goal, [ Algorithm ] (Wikipedia).
  • class::="A description of a set of similar objects that have similar data plus the functions needed to manipulate the data".
  • constructor::="A Function in a class that creates new objects in the class".
  • Data_Structure::=A small data base.
  • destructor::=`A Function that is called when an object is destroyed".
  • Function::programming=A selfcontained and named piece of program that knows how to do something.
  • Gnu::="Gnu's Not Unix", a long running open source project that supplies a very popular and free C++ compiler.
  • mutator::="A Function that changes an object".
  • object::="A little bit of knowledge -- some data and some know how". An object is instance of a class.
  • objects::=plural of object.
  • OOP::="Object-Oriented Programming", Current paradigm for programming.
  • Semantics::=Rules determining the meaning of correct statements in a language.
  • SP::="Structured Programming", a previous paradigm for programming.
  • STL::="The standard C++ library of classes and functions" -- also called the "Standard Template Library" because many of the classes and functions will work with any kind of data.
  • Syntax::=The rules determining the correctness and structure of statements in a language, grammar.
  • Q::software="A program I wrote to make software easier to develop",
  • TBA::="To Be Announced", something I should do.
  • TBD::="To Be Done", something you have to do.
  • UML::="Unified Modeling Language".
  • void::C++Keyword="Indicates a function that has no return".

    End