topical media & game development

[] readme course(s) preface I 1 2 II 3 4 III 5 6 7 IV 8 9 10 V 11 12 afterthought(s) appendix reference(s) example(s) resource(s) _

object-oriented programming

[] readme course preface 1 2 3 4 5 6 7 8 9 10 11 12 appendix lectures resources

Polymorphism

subsections:

Inheritance and delegation in Java
Polymorphism in C++
Assertions in C++
Canonical class idioms

Polymorphism is an intriguing notion. Briefly put, polymorphism is the ability of a particular entity (which may be an object, a function, or a variable) to present itself as belonging to multiple types. Object-oriented languages are not unique in their support for polymorphism, but it is safe to say that polymorphism is an important feature of object-oriented languages. As explained in chapter 9, polymorphism comes in various flavors. With regard to object-oriented languages, we usually mean inheritance or inclusion polymorphism. Even within this restricted interpretation, we have to make a distinction between syntactic polymorphism, which requires merely that interfaces conform, and semantic polymorphism, where conformance requirements also include behavioral properties.

In this section, we will look at some simple examples in Java that illustrate how we may use the mechanisms of inheritance and (simple) delegation to define objects that have similar functionality but differ in the way that functionality is realized. These examples prepare the way for the more complex idioms and patterns presented later in this chapter.

In the rest of this section we will look briefly at the polymorphic constructs offered by C++. We will also study how behavioral conformance can be enforced in C++ by including invariants and assertions. These sections may be skipped on first reading.

Inheritance and delegation in Java

Consider the example below, an envelope class that offers a message method. In this form it is nothing but a variation on the hello world example presented in the appendix.


  public class envelope {    envelope  
  
  public envelope() { }
  
  public void message() {
  	System.out.println("hello ... ");
  	}
  };

slide: Hello World

To illustrate the idea underlying idioms and patterns in its most simple form, we will refine the envelope class into the collection of classes depicted in slide 2-envelope-letter.

We will proceed in three steps: (1) The envelope class will be redesigned so that it acts only as an interface to the letter implementation class. (2) Then we introduce a factory object, that is used to create envelope and letter instances. (3) Finally, we refine the letter class into a singleton class, that prevents the creation of multiple letter instances.

slide: Envelope/Letter Factory

Envelope/Letter

The Envelope/Letter idiom was introduced in [Coplien92] as a means to separate interface aspects from implementation aspects. Here the call to message is simply forwarded to the letter object.


  public class envelope {    envelope  
  letter impl;
  public envelope() {
  	impl = new letter();
  	}
  
  public void message() {
  	impl.message();
  	}
  };


  public class letter {    letter  
  
  public letter() { }
  
  public void message() {
  	System.out.println("Message in a letter");
  	}
  };

slide: Envelope/Letter

Admittedly, there is no need here to make such a distinction, but the idea speaks for itself. As you will see, this distinction allows us to change the implementation without modifying the envelope or interface class.

Factory

In the next refinement, we introduce a factory object, that allows us to create envelope and letter instances without invoking a constructor.


  public class factory {    factory  
  
  public factory() { }
  
  letter letter() { return new letter(); }
  envelope envelope() { return new envelope(); }
  };


  public class envelope {    envelope  
  letter impl;
  public envelope() {
  	factory f = new factory();
  	impl = f.letter();   // obtained from factory
  	}
  
  public void message() {
  	impl.message();
  	}
  };

slide: Factory

The factory object is used in the envelope class to create a letter. The advantage here, as will be shown shortly, is that the envelope class does not need to have any information about the actual type of the letter.

Singleton letter

Finally, we refine the letter class into a singleton class. When you inspect the implementation, you will see that only one instance of a letter will be created.


  public class singleton extends letter {     singleton  
  
  static int number = 0;
  
  protected singleton() { }
  
  
  static letter instance() {
  	if (number==0) {
  		theletter = new letter();
  		number = 1;
  		}
  	return theletter;
  	}
  
  public void message() {
  	System.out.println("Message in a letter");
  	}
  
  static letter theletter;
  };

slide: Singleton letter

Note that the factory object must be modified so that the static method instance of singleton is invoked instead of the original constructor of letter.

Discussion

This example, however simple, demonstrates the implementation of some of the idioms and patterns that will be discussed in the rest of this chapter. It shows that the basic mechanisms of inheritance and simple delegation or forwarding are sufficient to implement these idioms and patterns. We have not discussed yet why we need idioms and patterns, but this will hopefully become clear later on.

Polymorphism in C++

Polymorphism essentially characterizes the type of a variable, function or object. Polymorphism may be due to overloading, parametrized types or inheritance. Polymorphism due to inheritance is often considered as the greatest contribution of object-oriented languages. This may be true, but the importance of generic (template) types and overloading should not be overlooked.

Overloading

print


  extern void print(int);
  extern void print(float);

Generic class -- templates

list< T >


  template< class T > class list { ... }
  list* alist;

Polymorphism by inheritance

shape


  class shape { ... };
  class circle : public shape { ... } 
  shape* s = new circle;

slide: Polymorphic type declarations

In slide 1-polymorphism some examples are given of declarations involving polymorphic types. The function print is separately defined for int and float. Also, a generic list class is defined by means by employing templates. The list may be used for any kind of objects, for example integers. Finally, a shape class is defined from which a circle class is derived. An instance of the circle may be referred to by using a shape pointer, because the type shape encompasses circle objects.

The Standard Template Library (STL)

The Standard Template Library for C++ provides a generic library of data structures to store, access and manipulate data. It is a generic library based on templates. In fact, it uses templates in such an aggressive way that the C++ standardization committee was forced to reconsider its definition of the generic template facility in C++. See [STL].

Standard Template Library

STL

containers -- to hold objects
algorithms -- act on containers
iterators -- to traverse containers
functions -- as objects
adaptors -- to transform objects
allocators -- for memory management

slide: The Standard Template Library

The Standard Template Library (STL) offers containers, to hold objects, algorithms, that act on containers, and iterators, to traverse containers. Algorithms, which are implemented as objects, may use functions, which are also defined as objects, overloading the application

operator()

method. In addition, STL offers adaptors, to transform objects, and allocators, for memory management.

STL is supported by C++ compilers that adhere to the C++ standard, including Microsoft Visual C++ and the Cygnus/GNU C++ compilers. A more extensive discussion of STL is beyond the scope of this book, but the reader is advised to consult [STL], which gives an introduction to STL and its history, as well as a thorough course on programming with STL.

Assertions in C++

Whatever support a language may offer, reliable software is to a large extent the result of a disciplined approach to programming. The use of assertions has long since been recognized as a powerful way in which to check whether the functional behavior of a program corresponds with its intended behavior. In effect, many programming language environments support the use of assertions in some way. For example, both C and C++ define a macro assert which checks for the result of a boolean expression and stops the execution if the expression is false.

In the example below, assertions are used to check for the satisfying of both the pre- and post-conditions of a function that computes the square root of its argument, employing a method known as Newton iteration.


  double sqrt( double arg ) {    sqrt  
  require ( arg >= 0 );
  double r=arg, x=1, eps=0.0001;
  while( fabs(r - x) > eps ) {
     r=x; x=r-((r*r-arg)/(2*r));
     }
  promise ( r - arg * arg <= eps );
  return r;
  }

slide: Using assertions in C++

In the example, the macro assert has been renamed require and promise to indicate whether the assertion serves as, respectively, a pre- or post-condition. As the example above shows, assertions provide a powerful means by which to characterize the behavior of functions, especially in those cases where the algorithmic structure itself does not give a good clue as to what the function is meant to do. The use of assertions has been promoted in [Meyer88] as a design method for object-oriented programming in Eiffel. The idea is to define the functionality of the various methods by means of pre- and post-conditions stating in a precise manner the requirements that clients of an object must meet and the obligations an object has when executing a method. Together, the collection of methods annotated with pre- and post-conditions may be regarded as a contract between the object and its potential clients. See section contracts.

Whereas Eiffel directly supports the use of assertions by allowing access to the value of an instance variable before the execution of a method through the keyword old, the C++ programmer must rely on explicit programming to be able to compare the state before an operation with the state after the operation.


  class counter {    counter  
  public:
  counter(int n = 0) : _n(n) {
  	require( n >= 0 );
  	promise( invariant() ); // check initial state
  	}
  
  virtual void operator++() {
  	require( true ); // empty pre-condition
  	hold(); // save the previous state
  	_n += 1;
  	promise( _n == old_n + 1 && invariant() );
  	}
  
  
  int value() const { return _n; }  // no side effects
  
  virtual bool invariant() { return value() >= 0; }
  
  protected:
  int _n;
  int old_n;
  virtual void hold() { old_n = n; }
  };

slide: The counter contract

The annotated counter above includes a member function hold to store the value of its instance variable. It is used in the operator++ function to check whether the new value of the counter is indeed the result of incrementing the old value.

Assertions may also be used to check whether the object is correctly initialized. The pre-condition stated in the constructor requires that the counter must start with a value not less than zero. In addition, the constructor checks whether the class invariant, stated in the (virtual) member function invariant, is satisfied. Similarly, after checking whether the post-condition of the operator++ function is true, the invariant is checked as well.


  class bounded : public counter {    bounded  
  public:
  bounded(int b = MAXINT) : counter(0), max(b) {}
  void operator++() {
  	require( value() < max ); // to prevent overflow
  	counter::operator++();
  	}
  
  bool invariant() {
  	return value() <= max && counter::invariant();
  	}
  
  private:
  int max;
  };

slide: Refining the counter contract

When employing inheritance, care must be taken that the invariance requirements of the base class are not violated. The class bounded, given above, refines the class counter by imposing an additional constraint that the value of the (bounded) counter must not exceed some user-defined maximum. This constraint is checked in the invariant function, together with the original

counter::invariant()

, which was declared virtual to allow for overriding by inheritance. In addition, the increment operator++ function contains an extra pre-condition to check whether the state of the (bounded) counter allows it to perform the operation.

From a formal perspective, the use of assertions may be regarded as a way of augmenting the type system supported by object-oriented languages. More importantly, from a software engineering perspective, the use of assertions is a means to enforce contractual obligations.

Canonical class idioms

The multitude of constructs available in C++ to support object-oriented programming may lead the reader to think that object-oriented programming is not at all meant to reduce the complexity of programming but rather to increase it, for the joy of programming so to speak. This impression is partly justified, since the number and complexity of constructs is at first sight indeed slightly bewildering. However, it is necessary to realize that each of the constructs introduced (classes, constructors and destructors, protection mechanisms, type conversion, overloading, virtual functions and dynamic binding) may in some way be essential to support object-oriented programming in a type-safe, and yet convenient, way.

Having studied the mechanisms, the next step is to find proper ways, recipes as it were, to use these mechanisms. What we need, in the terminology of [Coplien92], are idioms, that is established ways of solving particular problems with the mechanisms we have available. In his excellent book, Coplien discusses a number of advanced C++ idioms for a variety of problem domains, including signal processing and symbolic computing.

In this section, we will look at the concrete class idiom for C++, which states the ingredients that every class must have to behave as if it were a built-in type. Other idioms, in particular an improved version of the handle/body or envelope/letter idiom that may be used to separate interface from implementation, will be treated in the next section.

Concrete data types in C++

A concrete data type is the realization of an abstract data type. When a concrete data type is correctly implemented it must satisfy the requirements imposed by the definition of the abstract data type it realizes. These requirements specify what operations are defined for that type, and also their effects. In principle, these requirements may be formally specified, but in practice just an informal description is usually given. Apart from the demands imposed by a more abstract view of the functionality of the type, a programmer usually also wishes to meet other requirements, such as speed, efficiency in terms of storage and error conditions, to prevent the removal of an item from an empty stack, for example. The latter requirements may be characterized as requirements imposed by implementation concerns, whereas the former generally result from design considerations.

Canonical class in C++

default constructor
copy constructor
destructor
assignment
operators

Abstract data types must be indistinguishable from built-in types

slide: Canonical class

To verify whether a concrete data type meets the requirements imposed by the specification of the abstract data type is quite straightforward, although not always easy. However, the task of verifying whether a concrete data type is optimally implemented is rather less well defined. To arrive at an optimal implementation may involve a lot of skill and ingenuity, and in general it is hard to decide whether the right choices have been made. Establishing trade-offs and making choices, for better or worse, is a matter of experience, and crucially depends upon the skill in handling the tools and mechanisms available.

When defining concrete data types, the list of requirements defining the canonical class idiom given in slide 2-canonical may be used as a check list to determine whether all the necessary features of a class have been defined. Ultimately, the programmer should strive to realize abstract data types in such a way that their behavior is in some sense indistinguishable from the behavior of the built-in data types. Since this may involve a lot of work, this need not be a primary aim in the first stages of a software development project. But for class libraries to work properly, it is simply essential.

[] readme course(s) preface I 1 2 II 3 4 III 5 6 7 IV 8 9 10 V 11 12 afterthought(s) appendix reference(s) example(s) resource(s) _

You may not copy or print any of this material without explicit permission of the author or the publisher. In case of other copyright issues, contact the author.