Heading 1 - SJSU



3. Frameworks, Toolkits, and Polymorphsim

Overview

Polymorphism allows programmers to declare partially complete classes and functions. The idea being to complete the declaration with a subclass or a template instantiation when more application-specific information is available. Of course this is also the idea behind frameworks, toolkits, and many design patterns. In each case application-independent logic is captured by one part of the program, while application-dependent logic is concentrated in another.

After a brief survey of frameworks and a more formal introduction to polymorphism, fragments of a fictional music framework called MFW are presented as a pretext to introducing virtual functions, abstract classes, templates, and several important design patterns. These patterns and mechanisms are subsequently assembled to create a working computer game framework called FUN (application frameworks will be developed in Chapter 6) and a working toolkit called PIPES for assembling applications that instantiate the Pipe and Filter architectural pattern.

Frameworks

A framework is a library of collaborating base classes that capture the logic, architecture, and interfaces common to a family of similar applications. Frameworks are customized into specific applications by deriving classes from framework classes.

[pic]

A horizontal framework provides general services, and so can be customized into a wide assortment of diverse applications. A vertical framework fixes a narrow application domain and therefore requires less customization:

[pic]

The idea of a partially completed application sounds strange at first. Why would anyone want such a thing? But the idea makes sense for organizations that can't afford custom software, and that require something beyond the general features of off-the-shelf software.

Typically, framework developers are not the application developers who customize the framework. But if a framework for a particular application doesn't exist, it might make sense for the application developers to create their own framework as a first step. In this way a library of frameworks evolves that enables developers to quickly produce new applications based on combinations of frameworks that have already been tested by previous applications. This is called framework-based software development [ROG]. Framework-based development also makes sense for students, who can gain experience writing challenging code without devoting too much time to application domain details.

Example: Application Frameworks

Although word processors, spread sheets, and database browsers don't have much in common, they all have elaborate, platform-dependent graphical user interfaces, and they can all save the user's work into a file or database. Application frameworks such as Microsoft Foundation Classes (MFC), Object Windows Library (OWL), ET++, and JFC provide generic graphical user interfaces with windows, menus, toolbars, dialog boxes, and other common user interface components. (Application frameworks are covered in detail in Chapter 7.)

[pic]

Example: Expert System Shells

Expert systems are interactive programs that automate the collection, representation, and generation of knowledge in a specific application domain. Expert systems are used by doctors to diagnose patients (MYCIN), by geologists to locate good places to drill for oil (PROSPECTOR), and by engineers to configure computers (XCON). These applications are different, but they have common features such as user interfaces, inference engines, and schemes for representing and organizing knowledge (semantic networks, frames, scripts, rules, etc.). These common features can be captured in an expert system framework (more commonly called an expert system shell). Examples include ART (Automated Reasoning Tool by Inference Corporation), KEE (Knowledge Engineering Environment by IntelliCorp), and GURU (by Micro Data Base Systems). See [FIRE] for a survey of expert systems.

[pic]

Example: Client-Server Frameworks

In a client-server application shared data is maintained by a program called the server, and presented and manipulated by programs called clients. Often machine or network boundaries separate clients and servers. The World Wide Web (WWW) is a typical client server application. Web servers maintain collections of web pages that are delivered upon request to web clients (i.e., web browsers).

In fact, WWW is such a generic client-server application, that Java has created a client-server framework that piggy backs on top of WWW. An applet is a customizable client that is executed by a web client. The applet communicates with a customizable server called a servlet that is executed by a web server. Applets and Servlets are documented on the web at [WWW 7].

[pic]

Example: Workflow Frameworks

A workflow is a routine business or engineering process. For example, the workflow of a grocery store check-out clerk might be described by the following state diagram:

[pic]

A workflow application is a program that guides a worker through a workflow. For each state, the workflow application prompts the worker for the information required to complete the state. This may involve fetching and updating records in various remote databases. When the information is collected, the application determines which state to move to next.

For example, a help desk application guides a customer service agent through a sequence of diagnostic questions and tests; a warehouse inventory management system guides warehouse workers through an order processing workflow; and a point-of-sale application guides check-out clerks through the states described above. When a sale is completed, the inventory database is updated, any accounting software is notified, and the total amount in the cash register is recomputed.

Although these applications are different, they have a much in common that can be captured in a workflow framework. Each consists of a number of well defined transactions. A graphical user interface displays each transaction and provides controls for completing, canceling, undoing, redoing, saving, and restoring the transaction. Information gathered during a transaction determines the next transaction.

[pic]

IBM San Francisco is a family of workflow frameworks written in Java that can be customized into a variety of business management systems. Currently, IBM San Francisco offers three frameworks: a general ledger framework that provides the core functionality used by most accounting applications, including budgeting, accounts receivable, and accounts payable; a warehouse management framework which provides warehouse control, picking stock, reception, and shipment processes needed by most warehouse management systems; and an order management framework which provides the business logic required in many manufacturing applications, including sales orders, purchase orders, and pricing. (Documentation about IBM San Francisco can be found on the web at [WWW 10].)

Polymorphism

A type system for a language L is a set of primitive types together with a set of rules for constructing, comparing, and naming types, as well as rules for binding types to the expressions and values of L. For example, the primitive types of C++ include int, float, char, and bool. Arrays, structs, unions, and pointers are examples of constructed types.

Instances of a monomorphic or uniform type all have the same representation, while instances of a polymorphic or multi-form type can have a variety of representations. For example, a monomorphic Real type might represent all real numbers using the IEEE floating point standard representation, but a polymorphic Complex type might represent some complex numbers using polar coordinate representation (reit) and others using rectangular coordinate representation (a+bi). A polymorphic type often can be viewed as a family of logically related subtypes.

In C++ an abstract class is a class with one or more pure virtual functions. In the following example, Shape is an abstract class with a pure virtual draw() function:

class Shape

{

public:

virtual void draw() = 0;

// etc.

};

Abstract classes can be regarded as polymorphic types[1] in the sense that instances of concrete shape-derived classes can be treated as generic shapes. For example, although we can't declare instances of the Shape class, we can declare Shape pointers that can point at any instance of a concrete Shape subclasses:

Shape* s[3];

s[0] = new Triangle();

s[1] = new Circle();

s[2] = new Rectangle();

for(int i = 0; i < 3; i++) s[i]->draw();

A C++ class template defines a paremeterized family of types, and therefore can also be regarded as a polymorphic type (although this is somewhat at odds with C++ terminology). For example, the list template in the standard template library defines a family of types, including:

list

list

list

etc.

The term "polymorphic" is also applied to functions, although a polymorphic function is simply an instance of a polymorphic function type. More concretely, a polymorphic function is a family of closely related functions. For example, the virtual Shape::draw() function is a polymorphic function that represents the family of draw() functions defined in the Shape-derived classes.

C++ allows programmers to define function templates:

typedef

void swap(T& x, T& y)

{

T temp = x;

x = y;

y = temp;

}

We can think of the swap() template as the polymorphic representative of the family of its instances.

Even a family of functions that simply share a name:

double area(Triangle x) { return x.height * x.base / 2; }

double area(Rectangle x) { return x.height * x.width; }

double area(Circle x) { return pi * x.radius * x.radius; }

can be thought of as variants of a single polymorphic function.

Working with Unknown Classes

In a sense, a framework is a polymorphic application. A framework is an application that can take on many forms, depending on how it is customized. As such, framework programmers often need to refer to classes that won't be defined until the framework is customized, and of course different customizations may define these classes in different ways. Polymorphism allows framework programmers to work around these critical pieces of missing information.

MFW: A Framework for Music Applications

Assume we are developing a music framework called MFW. MFW is a horizontal framework that can be customized into various musical applications such as score editors, virtual recording studios, virtual instruments, expert systems for composers, and interfaces to computer controlled instruments such as synthesizers.

One part of MFW defines various ensembles of musical instruments: bands, orchestras, trios, quartets, etc. Unfortunately, the types of musical instruments will be defined much later in the various customizations of the framework. How can MFW form ensembles without knowing the identity of their constituent instruments? There are two solutions: make Instrument an abstract class in MFW, or make Instrument an MFW template parameter.

MFW with Abstract Classes

Although the specific types of instruments may be unknown, MFW can define an abstract Instrument base class:

class Instrument

{

public:

virtual void play() = 0;

};

MFW is unable to implement the play() member function, so it is declared as a pure virtual function. Derived class programmers will be required to provide implementations. Even though MFW couldn't implement play(), it can still call play(). For example, here is the MFW definition of Trio. Notice that Trio::play() calls the play() function of each instrument:

class Trio

{

public:

Trio(Instrument *a = 0, Instrument *b = 0, Instrument *c = 0)

{

first = a;

second = b;

third = c;

}

void play()

{

if (first) first->play();

if (second) second->play();

if (third) third->play();

}

private:

Instrument *first, *second, *third;

};

Suppose a programmer customizing MFW wishes to create and play trios consisting of different combinations of horns, harps, and drums. The first step is to create Instrument derived classes. For example:

class Harp: public Instrument

{

public:

void play()

{

cout play();

}

Clients of the orchestra class can add a variety of instruments to orchestra instances:

Orchestra orch;

orch.add(new Horn());

orch.add(new Harp());

orch.add(new Horn());

orch.add(new Harp());

orch.add(new Drum());

orch.play();

Unfortunately, orchestras can only hold Instrument pointers, not the instruments themselves. Why?

Virtual Factory Methods

Let's enhance MFW by adding an abstract Note class. Each note encapsulates a frequency and a duration:

class Note

{

public:

Note(double f = 100, double d = 300) { freq = f; duration = d; }

virtual void play() = 0; // quality? timbre?

protected:

double freq; // in Hz

double duration; // in mSec

};

Of course any musician will tell you that a note played on a guitar sounds quite different from the same note played on a horn. For this reason we have left the implementation of play() to MFW customizations; for example:

class HornNote: public Note

{

public:

HornNote(double f = 100, double d = 300): Note(f, d) {}

void play()

{

cout play();

delete n;

}

}

But how can the Instrument class know what type of Notes to create? It would seem that creating an unknown type of object is more difficult than simply using an unknown type of object. How much memory should be allocated? How should the memory be initialized? Creating unknown objects is a common theme in programming. The various approaches to this problem are summarized by the Factory Method design pattern:

Factory Method [Go4]

Other Names

Virtual constructor.

Problem

A "factory" class can't anticipate the type of "product" objects it must create.

Solution

Provide the factory class with an ordinary member function that creates product objects. This is called a factory method. The factory method can be a virtual function implemented in a derived class, or a template function parameterized by a product constructor.

There are three variations of the pattern: virtual, smart, and template factory methods. Template factory methods will be discussed later in the chapter, while smart factory methods will be discussed in Chapter 5.

An ordinary member function that creates and returns new objects is called a factory method. Although C++ doesn't allow virtual constructors, factory methods can be virtual:

class Instrument

{

public:

void play();

// virtual factory method:

virtual Note* makeNote(double f = 100, double d = 100) = 0;

};

The obligation to implement the virtual factory method falls on the shoulders of derived classes:

class Horn: public Instrument

{

public:

// factory method:

Note* makeNote(double f = 100, double d = 100)

{

return new HornNote(f, d);

}

};

One problem associated with virtual factory methods is that programmers must maintain two parallel inheritance hierarchies, one for factories, and one for products:

[pic]

If a programmer creates a new type of note, he must remember to create the corresponding factory instrument that creates the note.

MFW with Templates

Instead of introducing an abstract Instrument class, MFW could have used templates parameterized by instruments. For example MFW could have defined a trio to be a template parameterized by the types of instruments in the trio:

template

class Trio

{

public:

Trio()

{

first = new A();

second = new B();

third = new C();

}

void play()

{

if (first) first->play();

if (second) second->play();

if (third) third->play();

}

private:

A* first;

B* second;

C* third;

};

Notice that the template parameters not only parameterize the types of instruments in the trio, they also parameterize the instrument constructors called by the Trio constructor.

Because there is no abstract Instrument base class, MFW customizers don't need to derive their instrument classes:

class Drum

{

public:

void play() { cout makeWindow();

Button* b = tk->makeButton();

w->adopt(b);

EditBox* e = tk->makeEditBox();

w->adopt(e);

// etc.

return w;

}

We only need to describe the construction of our GUI once, in makeMyGUI(). If we want to construct a GUI for a particular platform, we simply call makeMyGUI() with a platform-specific implementation of UIToolkit.

For example, assume Z Windows is a library of GUI components for a particular platform (e.g., Z = X, MFC, MacApp2, etc.):

[pic]

Someone knowledgeable in Z Windows programming could provide implementations of each of the UIToolkit interfaces. This can be done using adapters (which will be discussed in Chapter 4). For example:

class ZButtonAdapter: public Button

{

public:

ZButtonAdapter() { peer = new ZButton(); }

~ZButtonAdapter() { delete peer; }

void draw() { peer->paint(); }

void handle(Message msg) { peer->onMsg(msg); }

private:

ZButton* peer; // the corresponding Z component

};

We must also provide a Z Windows implement the abstract toolkit class:

class ZUIToolkit: public UIToolkit

{

public:

virtual Window* makeWindow() { return new ZWindowAdapter(); }

virtual Button* makeButton() { return new ZButtonAdapter(); }

virtual MenuItem* makeMenuItem() { return new ZMenuItemAdapter(); }

virtual EditBox* makeEditBox() { return new ZEditBoxAdapter(); }

virtual ListBox* makeListBox() { return new ZListBoxAdapter(); }

// etc.

};

Here is how the programmer might start an application using the ZUIToolkit:

int main()

{

Window* appWindow = makeMyGUI(new ZUIToolkit());

appWindow->draw(); // draw app window & start msg loop

return 0;

};

Generic Methods

Sometimes the general sequence of tasks a function must perform is the same across a variety of applications, suggesting that the function belongs in a common framework. However, the tasks performed by the function are application-specific, suggesting the function belongs in the various framework customizations.

The generic algorithm design pattern solves this problem. Move the function into the framework and declare the application-specific tasks to be pure virtual functions in the framework. A function like this is called a generic algorithm or a template method.[3]

Generic Algorithm [Go4], [ROG]

Other Names

Template method

Problem

Parts of an algorithm are invariant across a family of framework customizations, while other parts are not.

Solution

Move the algorithm into the framework. Replace the non-invariant parts by calls to virtual functions that can be implemented differently in different customizations.

Generic algorithms follow the inverted control structure sometimes called the Hollywood principle: "Don't call us, we'll call you."

Let's start with a trivial example to clarify the idea; more serious examples will come later. Suppose we want to add a symphony class to our music framework, MFW. Symphonies are usually divided into four movements, so playing a symphony is easy: play the first movement, then the second, then the third, finally the fourth. Of course the similarity between symphonies ends here. The particulars of each movement vary from one symphony to the next, and will have to be specified in various customizations of the framework. We can still add an abstract symphony base class to our framework, but play() will have to be a generic algorithm:

class Symphony

{

public:

void play() // a generic algorithm

{

doFirstMovement();

doSecondMovement();

doThirdMovement();

doFourthMovement();

}

protected:

virtual void doFirstMovement() = 0;

virtual void doSecondMovement() = 0;

virtual void doThirdMovement() = 0;

virtual void doFourthMovement() = 0;

};

Framework customizers will have to subclass Symphony and implement the do-functions. For example:

class TheFifth: public Symphony

{

void doFirstMovement()

{

cout drink

Lancelot drinks 5 energy bowls

done

-> grab

Lancelot collects 1 keys.

done

->

When the hero moves into a room in which the number of locks is less than or equal to the number of keys the hero has collected, the hero escapes and the game ends in a victory for the user:

-> move n

Lancelot has escaped!

Of course in a space-age customization of FUN heroes are spacemen, rooms are labs, and monsters are killer robots:

-> move w

This is a creepy lab where horrible experiments occur

(# of monsters = 1)

(# of energy bowls = 5)

(# of keys = 1)

(# of locks = 26)

A robot crushes Buzz (damage = 8)

Buzz zaps a robot (damage = 1)

done

-> check

Buzz is a futuristic spaceman with a lazer gun

(Buzz.energy = 91)

(Buzz.keys = 0)

done

The Design

Players will use a game console to navigate their heroes through a maze of monster-inhabited rooms. A game factory decouples the construction of the maze from the construction of monsters and rooms. Here's our design:

[pic]

Customizations of FUN will be expected to complete implementations of critical functions in classes derived from the abstract Hero, Room, and Monster classes.

The Cast of Characters

Although we don't know the exact nature of heroes and monsters, we can introduce abstract Hero and Monster base classes in FUN. These classes derive from FUN's Character base class:

class Character

{

public:

Character(string nm = "unknown")

{

name = nm;

energy = 100;

}

virtual ~Character() {}

int getEnergy() { return energy; }

void setEnergy(int e) { energy = e; }

string getName() { return name; }

int injure(Character* c);

virtual void describe() = 0;

protected:

int energy; // dead = 0% energy) throw AppError(c->name + DEAD);

int damageCaused = rand() % (DAMAGE_CONTROL + energy/c->energy);

int damageSustained = 1; // cuz fight'n is tough work

c->energy = max(c->energy - damageCaused, 0);

energy = max(energy - damageSustained, 0);

return damageCaused;

}

The only thing we can say in FUN about monsters is that they are characters who attack heroes:

class Monster: public Character

{

public:

Monster(string nm = "unknown"): Character(nm) {}

virtual ~Monster() {}

virtual void attack(Hero* h) = 0;

virtual void describe() = 0;

};

We can say more about heroes in FUN. A hero is a character who defends himself against monsters. In addition, a hero can move from room to room, collect keys, pick fights with monsters, and invigorate himself by drinking from energy bowls:

class Hero: public Character

{

public:

Hero(string nm = "unknown"): Character(nm) { keys = 0; room = 0; }

virtual ~Hero() {}

virtual void defend(Monster* m) = 0;

void move(Direction d); // move to a new room

void invigorate(); // drink room's energy bowls

int getKeys() { return keys; }

void takeKeys(); // collect room's keys

Room* getRoom() { return room; }

void setRoom(Room* r) { room = r; }

void fight(); // fight room's monsters

virtual void describe() = 0;

private:

Room* room; // = current location

int keys; // = # of keys collected

};

Even though describe() is a pure virtual function in both the Character and Hero classes, we can still provide them with implementations:

void Character::describe()

{

cout makeMonster());

}

rooms[0][0]->setLocks(KEYS); // the only way out

}

Of course the number of keys, locks, monsters, energy bowls, and neighbors a room has can be easily adjusted in framework customizations.

The FUN framework provides an abstract factory for making game components:

class GameFactory

{

public:

virtual ~GameFactory() {}

virtual Monster* makeMonster() = 0;

virtual Hero* makeHero() = 0;

virtual Room* makeRoom(int e = 5, int k = 1, int l = KEYS + 1) = 0;

virtual Maze* makeMaze() { return Maze::makeMaze(this); }

};

Dungeons and Dragons

Dungeons and Dragons is an adventure game set in Medieval times. We implement Dungeons and Dragons as a customization of the FUN framework. Monsters are fire-breathing dragons:

class Dragon: public Monster

{

public:

Dragon(string nm = "dragon"): Monster(nm) {}

void attack(Hero* h)

{

cout read();

val = transform(val);

outPipe->write(val);

}

private:

TransformerProc transform;

}; // Transformer

Testers

A tester implements update() by reading a message from its inherited input pipe, then writing the message to its inherited output pipe if it passes a test given by the function pointer passed to the constructor:

class Tester: public Filter

{

public:

Tester(Pipe* ip, TesterProc f, Pipe* op)

: Filter(ip, op)

{

test = f;

}

void update(Publisher* p, void* what)

{

Msg val = inPipe->read();

if (test(val)) outPipe->write(val);

}

private:

TesterProc test;

}; // Tester

Consumers

A consumer implements update() by reading a message from its inherited input pipe, then passing the message to a consumer function pointer specified by the constructor:

class Consumer: public Filter

{

public:

Consumer(Pipe* ip, ConsumerProc f)

: Filter(ip, 0)

{

consume = f;

}

void update(Publisher* p, void* what)

{

Msg val = inPipe->read();

consume(val);

}

private:

ConsumerProc consume;

}; // Consumer

Producers

A data-driven producer implements update() as a no-op. This is because the producer has no input pipe that is subscribes to. A producer must redefine the inherited start() function. The start() function is the engine that drives a data-driven pipeline. It repeatedly calls the producer function initialized by the constructor. By assumption, this function either stores a new message in the val variable and returns true (recall that the producer's parameter is a reference), or it returns false. If it returns true, the message in val is written to the inherited output pipe and the loop repeats. Otherwise the start() function terminates. This terminates the flow of messages through the pipeline. If an exception is thrown anywhere in the pipeline, it will be caught by the producer:

class Producer: public Filter

{

public:

Producer(ProducerProc f, Pipe* op)

: Filter(0, op)

{

produce = f;

}

void update(Publisher* p, void* what) {} // no op

void start()

{

bool more = true;

Msg val;

while(more)

try

{

more = produce(val);

if (more) outPipe->write(val);

}

catch(PipeLineError e)

{

cerr setNeighbor(E, rooms[i][j + 1]);

rooms[i][j + 1]->setNeighbor(W, room);

}

if (0 < i && rooms[i - 1][j])

{

room->setNeighbor(N, rooms[i - 1][j]);

rooms[i - 1][j]->setNeighbor(S, room);

}

if (i + 1 < ROWS && rooms[i + 1][j])

{

room->setNeighbor(S, rooms[i + 1][j]);

rooms[i + 1][j]->setNeighbor(N, room);

}

}

character.cpp

Here is how the hero moves to another room:

void Hero::move(Direction d)

{

if (!energy) throw AppError(name + DEAD);

if (!room) throw AppError(name + LOST);

if (!room->getNeighbor(d)) throw AppError("That door is locked");

room = room->getNeighbor(d);

room->enter(this);

}

The invigorate() function is called when the hero drinks energy bowls:

void Hero::invigorate()

{

if (!energy) throw AppError(name + DEAD);

if (!room) throw AppError(name + LOST);

energy = min(energy + room->takeEnergy(this), 100);

}

If the hero wants to, he can pick a fight with the monsters in his current room:

void Hero::fight()

{

if (!energy) throw AppError(name + DEAD);

if (!room) throw AppError(name + LOST);

room->attack(this);

}

Other character.cpp functions are relatively straight forward and are left to the reader.

Problems

Problem 3.1

Create and test a template version of the UIToolKit.

Problem 3.2

Complete the FUN framework. (A few function definitions are missing.) Test FUN by using it to create and play an adventure game set in outer space.

3.1 Problem: A Two Player Game Framework

Most two player card and board games follow the same basic pattern:

Player 1 and player 2 alternate turns. Usually, points are scored on each turn. When one player accumulates enough points, he wins and the game is over.

We can capture this pattern in a generic algorithm, which can be the basis for a mini framework for developing two player computer games. The framework allows tournaments consisting of multiple games, so it keeps track of the total number of player 1 and player 2 wins, which it displays with the showStats() function. The generic algorithm is play()[5]:

void Game::play()

{

bool again = true;

while (again)

{

score1 = score2 = 0;

doInitGame(); // reinitialize game environment

while(!doGameOver())

try

{

cout start().

Obviously filters subscribe to their output pipes instead of their input pipes in a demand driven pipeline. When a down stream filter reads from its input pipe, the pipe automatically notifies the upstream filter that data is needed.

Two special problems arise in the demand driven case. First, what happens when data is demanded from the output pipe of a tester? The tester needs to repeatedly read from its input pipe until the pipeline is empty or until it receives a data item that passes its test and can be written to its output pipe.

Second, how does a demand drive pipeline shut down? In the data driven case this was easy because the producer controlled the while loop in start() and the producer knew when it was finished producing data. When produce() returned true, the loop control variable was set to true and the start() function, hence the pipeline, terminated. In a demand-driven pipeline the consumer controls the while loop in start(). How can the producer signal the consumer that it's done producing data? The answer is by throwing a ProducerQuitting exception. This means the while loop in start() must contain a try-catch block:

while(!fail)

{

try

{

???

}

catch(ProducerQuitting pqe)

{

fail = true;

}

}

Try declaring ProducerQuitting as a derived class from the exception class defined in the C++ standard library:

class ProducerQuitting: public exception {};

This could also be an inner class of PipelineKit.

2.12. Problem: Using Functors

A functor or function object, is an object that can be called like a function. This is accomplished by making the function call operator a member function. For example:

class Square

{

public:

double operator()(double x) { return square(x); }

// etc.

};

We can now define some Square functors:

Square f, g, h;

Like ordinary objects, these objects can be passed as parameters, returned as values, or assigned to variables. But they can also be called like functions:

cout ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download