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.

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.

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:

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.

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.)

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.

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].

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:

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.

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].)

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 Java include int, float, char, and boolean. Arrays and classes 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 (re^it) and others using rectangular coordinate representation (a+bi). A polymorphic type often can be viewed as a family of logically related subtypes.

All Java classes can be regarded as polymorphic types because instances of an extension can be treated as instances of the super class. For example, assume the following Shape class has been declared:

Assume Triangle, Rectangle, and Circle extend the Shape class. For example:

A reference to a Shape can actually refer to any instance of a Shape extension. For example:

Even though the shape[i] reference is of type Shape, the actual object shape[i] refers to is a specific type of shape. The Java compiler doesn't decide which variant of draw() should be called. Instead, this decision is left to the Java virtual machine, which uses the type of the object, not the type of the reference to determine which draw() variant should be called. For example, the following statement draws a circle, rectangle, and triangle in the graphical context g:

When it is time to upgrade or replace a chip in a computer, the old chip is simply popped out of the motherboard, and the new chip is plugged in. It doesn't matter if the new chip and old chip have the same manufacturer or the same internal circuitry, as long as they both "look" the same to the motherboard and the other chips in the computer. The same is true for car, television, and sewing machine components. Open architecture systems and "Pluggable" components allow customers to shop around for cheap, third-party generic components, or expensive, third-party high-performance components.

An interface is a collection of operator specifications. An operator specification may include a name, return type, parameter list, exception list, pre-conditions, and post-conditions. A class implements an interface if it implements the specified operators. A software component is an object that is known to its clients only through the interfaces it implements. Often, the client of a component is called a container. If software components are analogous to pluggable computer chips, then containers are analogous to the motherboards that contain and connect these chips. For example, an electronic commerce server might be designed as a container that contains and connects pluggable inventory, billing, and shipping components. A control panel might be implemented as a container that contains and connects pluggable calculator, calendar, and address book components. Java Beans and ActiveX controls are familiar examples of software components.

Interfaces and Components in UML

Modelers can represent interfaces in UML class diagrams using class icons stereotyped as interfaces. The relationship between an interface and a class that realizes or implements it is indicated by a dashed generalization arrow:

Notice that the container doesn't know the type of components it uses. It only knows that its components realize or implement the IComponent interface.

For example, imagine that a pilot flies an aircraft by remote control from inside of a windowless hangar. The pilot holds a controller with three controls labeled: TAKEOFF, FLY, and LAND, but he has no idea what type of aircraft the controller controls. It could be an airplane, a blimp, a helicopter, perhaps it's a space ship. Although this scenario may sound implausible, the pilot's situation is analogous to the situation any container faces: it controls components blindly through interfaces, without knowing the types of the components. Here is the corresponding class diagram:

Notice that all three realizations of the Aircraft interface support additional operations: airplanes can bank, helicopters can hover, and blimps can deflate. However, the pilot doesn't get to call these functions. The pilot only knows about the operations that are specifically declared in the Aircraft interface.

We can create new interfaces from existing interfaces using generalization. For example, the Airliner interface specializes the Aircraft and (Passenger) Carrier interfaces. The PassengerPlane class implements the Airliner interface, which means that it must implement the operations specified in the Aircraft and Carrier interfaces as well. Fortunately, it inherits implementations of the Aircraft interface from its Airplane super-class:

An interface is closely related to the idea of an abstract data type (ADT). In addition to the operator prototypes, an ADT might also specify the pre- and post-conditions of these operators. For example, the pre-condition for the Aircraft interface's takeoff() operator might be that the aircraft's altitude and airspeed are zero, and the post-condition might be that the aircraft's altitude and airspeed are greater than zero.

Interfaces and Components in Java

Java allows programmers to explicitly declare interfaces:

Notice that the interface declaration lacks private and protected members. There are no attributes, and no implementation information is provided.

A Pilot uses an Aircraft reference to control various types of aircraft:

Java also allows programmers to explicitly declare that a class implements an interface:

The following code shows how a pilot flies a blimp and a helicopter:

It is important to realize that Aircraft is an interface, not a class. As such, it cannot be instantiated:

Java also allows programmers to create new interfaces from existing interfaces by extension:

Although a Java class can only extend at most one class (multiple inheritance is forbidden in Java), a Java interface can extend multiple interfaces and a Java class can implement multiple interfaces. A Java class can even extend and implement at the same time:

Classes only inherit obligations from the interfaces they implement-obligations to implement the specified member functions. By contrast, an abstract class is a partially defined class. Classes derived from an abstract class inherit both features and obligations. For example, airplanes, blimps, and helicopters all have altitude and speed attributes. Why not declare these attributes, as well as their attending getter and setter functions, in the Aircraft base class:

Aircraft is no longer an interface, because it contains fields and implemented methods. But takeoff(), fly(), land() are abstract methods, which means users still won't be allowed to instantiate the Aircraft class.

Names of abstract classes and virtual functions are italicized in UML:

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.

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 interface.

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

MFW is unable to implement the play() member function, so it is declared as a pure virtual function. Implementation 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() method of each instrument:

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 implementation classes. For example:

Here is how trios are created and played in the customization:

A container or collection is an object that stores other objects. Stacks and queues are familiar examples of containers. A heterogeneous container stores objects of different types. For example, an orchestra can be regarded as a container of different types of instruments:

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

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

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:

Now that we can talk about notes in MFW perhaps we can replace the Instrument interface by a concrete class:

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:

There are three variations of the pattern: virtual, smart, and template factory methods. Template factory methods are unavailable in Java, while smart factory methods will be discussed in Chapter ?.

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

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

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

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

Java allows programmers to declare products to be inner classes of factories:

Declaring HornNote to be an inner class of Horn will discourage harps and drums from making horn notes:

Unlike C++, inner class Java objects are always created by outer class factories, but the syntax is weird:

Of course this technique for constructing notes fails if HornNote is declared as a private inner class. In this case clients are forced to use our makeNote() factory method.

Inner class objects can access the public, protected, and private fields and methods of their factories, but the syntax is weird:

Note: this isn't true if the inner class is declared static.

UML doesn't have a notation for inner classes; we can use a stereotyped association:

Classes can even be defined inside of a method:

We don't even have to name classes:

The general syntax is:

A functor (also called functional or function object) is an object that behaves like a method. A thunk (also called a promise) is a special type of functor. It's special because a thunk invocation can be frozen (delayed). Later, the frozen thunk can be thawed (forced), causing it to compute and return a value. The interesting thing is that a thunk remembers its freezing environment, which it uses to produce its value when thawed, even if the thawing environment is different. (Thunks are closely related to closures. A closure is a method that remembers its defining environment.)

Every thunk must implement a thaw() method that returns the computed value as an Object:

In this demo we want to convert the method ThunkDemo.foo() into a thunk. The foo() method simply computes the sum of two parameters and a local variable, but in reality, when called, foo() creates and returns an anonymous thunk that computes this value when thawed:

The test driver defines a couple of local variables, a = 3 and b = 4, then freezes a call to foo(a, b). Much later, the frozen call is thawed and produces the value 3 + 4 + 10 = 17, even though the values of a and b have been changed!

A memoization thunk caches its computed result so subsequent thaws don't need to re-compute anything. In this case Thunk becomes an abstract base class that provides the cache:

In this version of the test harness the thunk is thawed twice. The first time it computes the sum, the second time it simply returns the cached value:

Clearly this is an advantage if computing the value requires a lot of time.

Thunks are useful for representing streams. A stream is a potentially infinite sequence:

A stream is represented as a pair:

In the following demo, the tail of a stream representing the infinite sequence of integers always produces the next integer by incrementing the cache:

Here is a test harness that prints out the first 20 values of a potentially infinite stream, s:

Here's the program output:

Note: I'm not sure this example is very interesting, because one clould more easily accomplish the same thing in Java without using thunks.

Meta-classes and power-classes allow modelers to separate class from type. Instead of representing types implicitly as classes with no runtime existence, we can represent types as objects that instantiate meta or power classes.

For example, there are many types of aircraft: airplanes, blimps. helicopters, space ships, etc. We could represent this situation by introducing blimp, helicopter, and airplane as subclasses of an aircraft base class:

Alternatively, we could define a single Aircraft class and represent the different types of aircraft by different instances of an AircraftType power class. In this case it's common for instances of the power class to act as a factories that create instances of the type of objects they represent, the same way a class would provide a constructor for creating instances:

How can we insure that users won't bypass the factory and directly create aircraft? This can be done in Java by defining Aircraft to be a private inner class of AircraftType. We begin by introducing an aircraft interface:

Next, we define the AircraftType class with a private inner class and a factory method:

Here is how a client might create an aircraft:

Of course reflection is built into Java, so we can use the Java meta classes Class, Field, Method, etc. without writing extra code. For example, let's drop the getType() function from the IAircraft interface:

Assume Helicopter and SpaceShip implement this interface:

Here is how a client might build and takeoff in an aircraft without knowing the type of aircraft:

A toolkit (also called an abstract factory or simply a kit) is a class or object that provides factory methods that produce the components needed to construct all or part of an application. In a sense, toolkits are precursors to frameworks. While a framework is already assembled and only requires customization, a toolkit only provides the components programmers will need to assemble an application. The advantage of a toolkit is that the entire assembly process can be described relative to the toolkit. Thus, the toolkit decouples the assembly process from the details of how the components are created. Toolkits are formalized by the abstract factory design pattern:

As an example, let's consider building graphical user interfaces (GUIs). Unfortunately, the standard C++ library doesn't provide GUI components such as windows, menus, and buttons. Part of the reason for this is that GUI components are highly platform-dependent. So instead, these components are supplied by platform-specific libraries such as the X-Windows library. This creates a huge problem when its time to port an application to a new platform. Studies show that a GUI might comprise 30% to 60% of a commercial application's code, all of which must be rewritten for the port!

We can partially relieve the pain of a port by using a toolkit to decouple the construction of a GUI from the details of how the GUI components are constructed. We begin by defining an abstract user interface toolkit:

In addition, the toolkit includes a hierarchy of abstract component classes or interfaces:

Here is a sketch of the component hierarchy's base class:

The GUI for a particular application is constructed by a function parameterized by UIToolkit:

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.):

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:

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

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

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.

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:

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

Sometimes we want a class to have at most one instance. Why? Multiple instances might lead to confusion. For example, it would be confusing if an application had multiple user interfaces, simultaneously:

Multiple instances might lead to sharing problems. For example, changes to one instance of a company's budget must be reflected in other instances:

In some situations, multiple instances might simply be illogical:

The Singleton pattern solves this problem by making all constructors private. A public factory method is provided that allows users to create instances, but the factory method always returns pointers to the same hidden instance:

But doesn't this create a chicken and egg problem? How do we get the first instance of the class from which we can invoke the factory method:

This problem is solved by making the factory method static:

For example, let's apply the singleton pattern to the TheFifth class from the previous example:

Notice that the default constructor is private. The reference to the one and only instance is declared to be a private static variable.

Unsuspecting clients can call the factory method as many times as they want, but only one instances is ever created:

Any attempt to create instances using the new operator generates an error message:

Java's platform independence means, among other things, that the Java VM doesn't care how characters and numbers are represented on the host platform. This makes writing a simple interactive program with a console user interface (CUI) a bit of a challenge. Since this is a common task, we now present the first of two CUI-based application frameworks. The entire framework consists of two classes: Console and AppError.

As a demonstration of how to customize the framework, we present a simple calculator. Here are the basic commands:

The about command displays information about the framework and the customization:

Of course we can do arithmetic and small errors don't break the calculator:

The console framework provides two classes: Console and AppError. All application-specific errors discovered in the customization are handled by throwing an AppError. The Console class supplies a control loop, and overridable help(), about() , handle(), and execute() methods. In fact, execute() is abstract, which means Console is an abstract class and extensions are required to implement an execute method.

A pipe is a message queue. A message can be anything. A filter is a process, thread, or other component that perpetually reads messages from an input pipe, one at a time, processes each message, then writes the result to an output pipe. Thus, it is possible to form pipelines of filters connected by pipes:

The inspiration for pipeline architectures probably comes from signal processing. In this context a pipe is a communication channel carrying a signal (message), and filters are signal processing components such as amplifiers, noise filters, receivers, and transmitters. Pipelines architectures appear in many software contexts. (They appear in hardware contexts, too. For example, many processors use pipeline architectures.) UNIX and DOS command shell users create pipelines by connecting the standard output of one program (i.e., cout) to the standard input of another (i.e., cin):

In this case pipes (i.e., "|") are inter process communication channels provided by the operating system, and filters are any programs that read messages from standard input, and write their results to standard output.

LISP programmers can represent pipes by lists and filters by list processing procedures. Pipelines are built using procedural composition. For example, assume the following LISP procedures are defined. In each case the nums parameter represents a list of integers:

We can use these procedures to build a pipeline that sums the squares of odd integers:

Here's the corresponding LISP definition:

Pipelines have also been used to implement compilers. Each stage of compilation is a filter:

The scanner reads a stream of characters from a source code file and produces a stream of tokens. A parser reads a stream of tokens and produces a stream of parse trees. A translator reads a stream of parse trees and produces a stream of assembly language instructions. We can insert new filters into the pipeline such as optimizers and type checkers, or we can replace existing filters with improved versions.

There's even a pipeline design pattern:

There are four types of filters: producers, consumers, transformers, and testers. A producer is a producer of messages. It has no input pipe. It generates a message into its output pipe. A consumer is a consumer of messages. It has no output pipe. It eats messages taken from its input pipe. A transformer reads a message from its input pipe, modulates it, then writes the result to its output pipe. (This is what DOS and UNIX programmers call filters.) A tester reads a message from its input pipe, then tests it. If the message passes the test, it is written, unaltered, to the output pipe; otherwise, it is discarded. (This is what signal processing engineers call filters).

Filters can also be classified as active or passive. An active filter has a control loop that runs in its own process or thread. It perpetually reads messages from its input pipe, processes them, then writes the results to its output pipe. An active filter needs to be derived from a thread class provided by the operating system:

An active filter has a control loop function. Here's a simplified version that assumes the filter is a transformer:

We will explore active filters in Chapter ?.

When activated, a passive filter reads a single message from its input pipe, processes it, then writes the result to its output pipe:

There are two types of passive filters. A data-driven filter is activated when another filter writes a message into its input pipe. A demand-driven filter is activated when another filter attempts to read a message from its empty output pipe.

Assume a particular data-driven pipeline consists of a producer connected to a transformer, connected to a consumer. The producer writes a message to pipe 1, the transformer reads the message, transforms it, then writes it to pipe 2. The consumer reads the message, then consumes it:

A data-driven pipeline pushes messages through the pipeline. A demand-driven pipeline pulls messages through the pipeline. Imagine the same set up using demand-driven passive filters. This time read operations propagate from the consumer back to the producer. A message is produced and written to pipe 1. The transformer reads the message, transforms it, then writes it to pipe 2. This message is the value returned by the consumer's original call to read():

Both diagrams reveal a design problem. How does the transformer know when to call pipe1.read()? How does the data-driven consumer know when to call pipe2.read()? How does the demand-driven producer know when to produce a message? Active filters solve this problem by polling their input pipes or blocking when they read from an empty input pipe, but this is only feasible if each filter is running in its own thread or process.

We could have the producer in the data-driven model signal the transformer after it writes a message into pipe 1. The transformer could then signal the consumer after it writes a message into pipe 2. In the demand-driven model the consumer could signal the transformer when it needs data, and the transformer could signal the producer when it needs data. But this solution creates dependencies between neighboring filters. The same transformer couldn't be used in a different pipeline with different neighbors.

Our design problem fits the same pattern as the problem of how the reactor in Chapter 2 communicates with its unknown monitors. We solved that problem by making the reactor a publisher and the monitors subscribers. We can use the publisher-subscriber pattern here, too. Pipes are publishers and filters are subscribers. In the data-driven model filters subscribe to their input pipes. In the demand-driven model filters subscribe to their our output pipes.

PIPES is a package containing reusable declarations of pipes and filters. Programmers create filters (transformers, testers, producers, and consumers) by creating extensions of PIPES classes. Pipelines are constructed by instantiating these extension classes, then connecting them with pipes. (Thus, PIPES is a toolkit, not a framework.)

For example, here is how a PIPES user constructs a pipeline that sums the squares of odd integers read from the keyboard. The partial sums are displayed in the console window.

The first step is to import the pipes package:

Next, a pipeline class is declared. We have chosen to declare the particular types of filters we are interested in as inner classes. The constructor actually constructs the pipeline and starts it:

Here is the output produced by a sample run of the program:

PIPES provides a PipelineError extension of Java's Exception class. Programmers throw these exceptions whenever pipeline-specific errors occur:

Users of a pipeline toolkit will want to add and remove filters from pipelines without too much difficulty. Therefore, filters in a pipeline should be independent of each other. In other words, a filter should only know the identity of the pipes that connect it to its neighboring filters, not the neighbors themselves. A pipe should be able to connect any filters. Therefore, although a filter may know the identity of its input and output pipes, a pipe is loosely coupled to the filters it connects. As mentioned earlier, this creates a notification problem. How will a pipe in a data-driven pipeline notify its downstream filter that a message has arrived? We use the Publisher-Subscriber problem to solve this problem. Pipes are publishers, and filters are subscribers that subscribe to their input pipes in data-drive pipelines.

Using the Publisher-Subscriber pattern may be an example of over-design. After all, a pipe only has one filter it must notify when a message arrives. Although we don't demonstrate this feature, our pipes can also be used as tees. A tee can connect a filter to multiple downstream filters.

In this case a pipe may need to notify unknown numbers and types of downstream filters when a message arrives.

Although a particular pipeline processes a particular type of message, different pipelines may process different types of messages. In any case, the toolkit can make no assumption about the types of messages that will be processed. This information will be supplied by users as they build pipelines. We could deal with this missing information the same way the FUN framework dealt with monsters and heroes: by introducing Msg (Message) as an abstract base class. For variety, PIPES takes a different approach: Msg will be a template parameter.

The following class diagram shows the relationships between the principle classes of the PIPES framework. The toolkit itself is not shown:

The Filter base class maintains one or two pointers to pipes. These are the input and output pipes. It also provides a virtual start function that is redefined in the Producer class. This is the engine that drives the pipeline. In a demand-driven pipeline the consumer implements start(). Filter is shown as an abstract class because it doesn't provide an implementation of the pure virtual update() function inherited from the Subscriber class. This job is left to the Filter-derived classes.

Filters are observers. They must implement an update() function that reads, processes, and writes messages. If an exception is thrown during processing, the update method must handle the exception, because the update method specified in the Observer interface doesn't throw exceptions. Unfortunately, a filter in the middle of a long pipeline is in no position to handle an exception. Exceptions should be handled by the pipeline driver (the producer in the case of a data-drive pipeline), which can shut the pipeline down if necessary.

Our hack for solving this problem is to provide a global error flag that will be checked by every update method. If the flag is not null, then an update method does nothing. If not null, and if an exception is thrown while the update method is processing a message, then the update method catches the exception and quietly assigns it to the global error flag.

UML can be extended using stereotypes. A stereotype is an existing UML icon with a stereotype label of the form:

A collaboration is a group of classes that work together to achieve a particular goal. Although a certain collaboration may have wide applicability, the actual classes that appear in this collaboration may have different names and meanings from one application to the next. In this case stereotypes can be used to indicate the role a class plays within the collaboration. For example, suppose Secretary class has a member function called type() that creates Report objects:

In Chapter 3 we will learn that this type of a member function is called a factory method. The class containing the factory method plays the role of a "factory", the return type of the factory method plays the role of a "product", and the association between the factory and product classes is that the factory class creates instances of the product class. We can suggest these associations by simply attaching stereotypes to the icons in our diagram:

Commonly used UML class stereotypes include:

In some cases a stereotype is so common that it earns its own icon. For example, in UML actors are sometimes represented by stick figures:

The following class diagram shows many of the interfaces and implementation classes in the new Java Collections Framework (located in java.util):

Basically, a set is an unordered collection with no duplicate elements, while a list is an ordered collection with duplicate elements allowed. A map is a table or dictionary. Readers should consult the online Java Tutorial for more details.

Assume a many-to-one relationship between an Airplane class and a Fleet class:

We could provide a Java Fleet with a set of Airplane references:

A Java iterator is initialized so that it points to a "location" before the first element of its implicit argument, and provides methods for determining if there is a next element and for moving to and accessing the next element. For example, assume a fleet of three airplanes is created:

Here is how we would command each airplane in the fleet to takeoff:

The explicit downcast is necessary because Java collections are generic-- they hold Objects. Since every class implicitly extends the Java Object class, templates aren't needed.

Monsters

Knights

The Game

Program Output

A UML Class Diagram

Killer Robots

Space Men

The Game

Program Output

Implement the data-driven Pipeline Toolkit. Test your implementation by constructing a pipeline that reads a text file through standard input, eliminates all punctuation marks, and writes the result to a file through standard output.

Problem

We can imitate LISP using the algorithms from the standard C++ library. Assume isEven() and square() are ordinary global functions:

The declarations of remove_if() and transform() are declared in the <algorithm> header file:

Repeat the data driven example using demand driven filters. Use the same test driver. The only difference is that f1->start() is replaced by f4->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:

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

This could also be an inner class of PipelineKit.

Let FSM be the class of all finite state machines:

A finite state machine, M, is a mathematical model of a simple computational device that is always in one of finitely many states:

We will assume q₀ is M's initial state. We will also assume one of M's states is designated as a final state, q_fin. For our purposes it is sufficient to assume states are simply consecutive integers:

M has a control function called run(), which expects a string as input and returns a bool:

The control function examines each character in s, once, from beginning to end. Examining a character causes M to change state. The new state is given by a function called next():

If M is in the final state, q_fin, after it examines the last character in s, then run() returns true and we say M accepts s. Otherwise, run() returns false and we say M rejects s.

M also has a user interface function called test(), which perpetually resets M's current state to q₀, prompts the user for an input string, s, then prints an acceptance message if run(s) returns true, and a rejection message otherwise.

Here's a sample output using a three state machine, M. M is in state q_i if it has examined the character '0' k times, and k % 3 == i. M's final state is q₀. Thus, M accepts s if and only if the number of zeroes in s is divisible by 3:

Implement a framework for building finite state machines. There are two approaches: Either next() can be specified in a user-defined derived class, or the user can pass a function object (i.e., a functor) representing next() to the finite state machine constructor. Use the first approach for this exercise. Of course run() and next() should throw exceptions if they get into trouble, and test() should catch these exceptions.

Test your framework by building and testing a finite state machine that accepts all strings that contain the same number of zeroes as ones.

Customize the Console framework into a stack-based rational number calculator:

For partial credit, customize the console into a real number (i.e., Double) calculator.

Let's put the patterns we have learned together by building a framework for text-based adventure games. Our framework will be called FUN. The restriction to text-based games (yes, such things really did exist) is only because of the unavailability of graphics utilities in the standard library, but the architecture of the framework could easily be used for graphics-based games.

The framework is possible because most adventure games follow the same basic plot:

This plot can be captured in the FUN framework. The nature of the rooms, monsters, and heroes is specified in various customizations of the framework. For example, here are some excerpts from a Medieval customization of the FUN framework called Dungeons and Dragons. The user controls the hero using commands for moving, fighting, drinking, and other of life's basic necessities:

The maze is an N by M grid of rooms. Thus, each room has two, three, or four neighboring rooms. The game begins with the hero standing in the North-West corner room of the maze:

When the hero moves into a new room, the room is described. In a graphics-based game a picture or animation of the room might be displayed in a window. If there are monsters in the room, they attack and the hero defends:

Notice that the hero's energy level has dropped from 100%, the maximum, to 96% as a result of the fighting.

In addition to monsters, some rooms contain keys and energy bowls. The hero drinks from the bowls and collects the keys:

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:

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

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:

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

Implement FUN. Test your framework by providing medieval and space-age customizations.