| |
Chapter 1 Object Orientation and State Systems |
|
This chapter uses simple state machines to introduce the basic concepts
of object orientation. You have run across state system concepts in earlier
courses, such as discrete math. One immediate advantage of using such concepts
is that they enable us to describe the functioning of an object in a form
independent of any particular software implementation. Using state diagrams
we can specify what functionality we want to obtain and then investigate
different ways to achieve it. One of the simplest, yet non-trivial, examples
of a finite state machine is the binary counter. We first implement this
machine in C using a non object-oriented implementation. Then we will show
how this machine can be implemented in C++. This will provide the basis
for comparing the two kinds of approaches to programming, and thereby to
demonstrate the advantages of object-orientation. |
| RETURN TO CONTENTS |
| |
Chapter 2 Object Behavior Specification: Software Blueprints |
|
It may be difficult to imagine yourself simultaneously playing the roles
of designer, implementer, tester and user of a software tool. But that's
what best describes your activities if you are writing a program for your
own later use. When you graduate, you might participate in a software development
team where it is now common that designer, implementer, tester and other
roles are assumed by specialists on the team. For now, let's stick with
the case where you are the designer, implementer, tester and user of a
software tool. Some form of abstract specification of the software is needed
to facilitate communication among designer, implementer and user. We'll
call it a blueprint (playing the same role as design sketches used
by building architects. As designer you should create a blueprint to provide
the implementer (yourself) with clear guide lines on the code to be written.
As tester, you should use the blueprint to develop your tests for correctness
(i.e., to see if the classes realize the desired behavior). Later, as user,
you will be glad to have the blueprint around when you have forgotten how
to use some of the features that were obvious to you when you were in the
development stage. While needed by an individual developer such as yourself,
such a blueprint is essential in a software team setting. |
| RETURN TO CONTENTS |
| |
Chapter 3 Lists: Behavior Specification, Models and Implementations |
|
You are familiar with linked lists from earlier courses in programming.
Some languages, such as Lisp and Scheme, provide lists as built-in data
structures together with some essential associated operations. But most
languages don't provide lists as basic data structures so we must create
and manipulate using their basic data structuring and procedure definition
facilities. How would we go about defining a class of list objects and
methods in such a language? |
| Indeed, let's go one step further. Suppose that the language of interest
provides object-oriented programming features.How would we define lists
as a class of objects? C++ is a case in point: it provides powerful OO
features but programmers must define their own lists classes. Sure, object
libraries, such as NIHCL, provide such classes. But to use these, you must
understand the behavior of list objects to apply them with confidence. |
| The objective of this chapter is show how lists
can be modelled as state machines -- not finite but so-called "infinite"
state machines since lists need not have an upper bound on their lengths. This will
help us to understand how to describe their behavior in the terms we have already
introduced: namely, as responses to query-terminated sequences of commands. |
| RETURN TO CONTENTS |
| |
Chapter 4 Inheritance Hierarchies and Hierarchical Construction |
|
This chapter introduces the concept of inheritance
in object-oriented programming and design. Inheritance is an essential
and powerful mechanism that enables new classes to be constructed on the
basis of existing classes. Inheritance also helps to organize large software
systems into manageable pieces through inheritance hierarchies.
We also discuss a related concept, hierarchical construction, often
called aggregation in database contexts, that allows software modules
to be connected together to form larger systems. |
| RETURN TO CONTENTS |
| |
Chapter 5 Containers -- An Object Behavior Specification |
|
Chapter 4 presented an object behavior specification of the list
class and explained the advantages of such a specification. We saw that
there are many ways to implement list behaviors -- in particular, sequential
and parallel implementations differ radically. Earlier, in Chapter 1 we
mentioned that containers are basic classes that help store, retrieve
and organize interacting objects. We said then that container were generalized
forms of lists. Actually, once we have freed ourselves from thinking in
sequential processing terms, we can start with container as the
more basic concept and derive lists as one of the special subclasses that
happen to be natural for sequential processing but are not really fundamental
in general. |
| This chapter introduces the specification hierarchy of container classes
roughly characterized as follows: |
|
container -- the base class, provides basic services
for the derived classes |
|
bag -- counts numbers of object occurrences |
|
set -- only one occurrence of any object is allowed in. |
|
relation -- is a set of key-value pairs, used in dictionary
fashion |
|
function -- is a relation in which only one occurrence
of any key allowed |
|
order -- maintains items in given order |
|
queue -- maintains items in first-in/first-out (FIFO)order |
|
stack -- maintains items in last-in/first-out (LIFO)order |
|
list -- maintains items in order determined by an insertion index |
| RETURN TO CONTENTS |
| |
Chapter 6 Ensemble-Based Implementation of Containers |
|
In earlier chapters, we found primitives for list implementations in serial
computers. Historically, these pointer-based primitives were the first
to be developed. But with the advent of parallel processing, and in view
of new technologies likely to emerge for computation, we should not be
limited to the conventional primitives. This chapter shows that the ensemble
methods for containers can serve as primitives for implementing all the behaviors
of the containers hierarchy that we have identified. Ensemble methods
turn out to be very suited to exploit parallel computation. To be more
specific we will show how the methods of all container subclasses can be
implemented using only ensemble methods and a small number of ordinary
methods. Moreover, we will not allow ourselves to use any information about
containers' internal structure. In the language of C++, containers must
serve as a private base class for any derived class. Working within
this constraint forces us to be very explicit in our implementation. We
can't use anything about container's behavior that is not provided by the
external interface. To implement a behavior we must use only ensemble methods
and introduce any new helping methods explicitly. The end result helps
us to understand what basic functionality must be provided by an implementation
in a new language, platform or technology. |
| RETURN TO CONTENTS |
| |
Chapter 7 Testing Based on Behavior Specification |
|
While "getting it right the first time" is an admirable goal, no one is
able to write code that is guaranteed to work as intended without testing
and debugging. Testing is the process of uncovering errors or "bugs" in
code. Debugging is the process of removing them. The many books on object
oriented programming, C++ in particular, tend not to deal with these issues.
Books on software engineering do discuss testing as an important phase
within software system development, but a good approach to testing that
is tuned to the special characteristics of object orientation is not yet
available. This chapter provides the beginnings of such an approach that
emerges naturally from the concepts of behavior specification developed
earlier in the book. This methodology should attempt (or even guarantee)
to produce a test suite that is as thorough as time and money allow.
A failed test should its targetted behavioral aspect thus providing
a useful starting point for the debugging process. The test suite should
be able to evolve as the software system evolves, making sure each
update or release maintains the levels of performance that were achieved
in the past. |
| RETURN TO CONTENTS |
| |
Chapter 8 Constructing Inheritance Class Hierarchies |
|
We formulate a heuristic procedure that can produce an inheritance class
hierarchy. The procedure is heuristic since we don't spell out how to make
key decisions, such as finding common features for a group of classes.
These decisions have to be made based upon your knowledge of the application
domain. Let's suppose that you have a collection of classes in mind already
and are seeking to organize them to take the most advantage of commonalities
using inheritance. For example, you might know that investments can be
made in a number of different ways and have formulated these ways as classes,
such as various kinds of stocks, bonds and ways to earn money from savings.
After discussing the procedure for constructing a class hierarchy, we show
how class variables and ensemble methods are useful in implementing the
resulting system. |
| RETURN TO CONTENTS |
| |
Chapter 9 C++ Implementation of a Heterogeneous Container
Class Library |
|
This chapter discusses an implementation of the containers hierarchy in
C++ called Heterogeneous Container Class Library (HCCL). Recall
that "container" refers to a list-like structure to store data items and
"heterogeneous" means containers can hold different kinds of items. Therefore
HCCL provides a collection of list-like structures that are able to store
different kinds of items. HCCL mitigates typing constraints in C++ since
programmers are spared the task of implementing new container types for
each new kind of object they develop. |
| More specifically, our container objects should have the following properties: |
|
multiple occurrence in the same container: the same
object can appear many times in a container,for example,a has 5 occurrences in:(a b r a c a d a b r a). |
|
multiple occurrences in different containers: the
same object can appear in any number of containers, for example,
a occurs in: (a b r a c a d a b r a) and also in (a n y). |
|
heterogeneity: different kinds of objects can be included in a container,
for example, the container (a "abc" 0) contains a character, a string,
and a number. |
|
multilevel or hierarchical construction: containers
that contain other containers as items can themselves be placed
into containers; for example, the container ( (a 0) (b 1)(c
2)) has three items each of which is a container |
|
HCCL was developed to enhance the C++ object-oriented programming (OOP)
environment. One of the main advantages of OOP is that development time
and effort can be greatly reduced through the use of reusable code. This
is because programmers no longer have to spend their time in coding something
which is provided in a reusable library. This works well providing that
code placed into a reusable library has been well tested. In this case,
the only bugs introduced are those that arise from the new code that is
built on the reused components. |
| RETURN TO CONTENTS |
| |
Chapter 10 Ordered Containers and Their Implementation |
|
We continue with the second branch of the containers specification
hierarchy, that of ordered containers. Consideration starts
with class order, which is general enough to serve as a base class
for classes stack, queue, and list. The underlying
new concept is a linear ordering method, called greater-than?, which
is assumed to be available to order the items in a container. By characterizing
this method as a state-representing query, we obtain a generic capability
to order container contents that can be readily specialized to any appropriate
subclass. In particular, by properly defining greater-than? for
stack,queue,and list we can derive their behaviors
from the base class order.(We will show in a later chapter how this
differs from the usual specifications of stacks and queues which don't take
advantage of state representing queries.)The last part of the chapter
discusses several alternative implementations of the order hierarchy. One
approach employs ensemble methods and is therefore appropriate to both
parallel and sequential implementation. Given the multiple implementations
possible, the choice of which to use must depend on other considerations
such as efficiency. |
| RETURN TO CONTENTS |
| |
Chapter 11 More Useful Concepts for Containers |
|
This chapter starts by showing how predicate logic constructs, such as
(for all) (there exists), can be formulated as ensemble methods for containers.
Such methods are not really new since they can be derived from those already
discussed. However, it may be desirable to implement them as primitives
in an OOP environment for efficiency reasons. |
| We then discuss the problem of defining equality
for the different container classes and show how the logic ensemble methods make it
straightforward to implement the equality methods. |
| RETURN TO CONTENTS |
| |
Chapter 12 Working with Ensemble-based Containers |
|
This chapter presents a variety of examples of fairly complex systems that
can be given quite elegant constructions using the concepts developed in
the previous chapters. |
| RETURN TO CONTENTS |
| |
Chapter 13 Java and Threaded Containers |
|
We start with a review of Java and its relation C++.
Ensemble methods offer a challenge for Java implementation for two reasons::
a) Java does not have a preprocessor, as does C++, b) Java does support
multithreading Point a) means that we do not have the ability to write macros
enabling ensemble methods to flexibly accept method names and other arguments.
Point b) however, gives us the ability to implement ensemble methods in a truly
parallel/distributed processing environment. Working within these constraints,
we discuss an approach to implementing ensemble methods in Java. |
| RETURN TO CONTENTS |
Chapter
1 Object Orientation and State Systems