INTRODUCTION TO OBJECT-ORIENTED DESIGN PART 1 - ABSTRACTION
Up until now we've largely avoided discussing object-oriented design (OOD). This is a topic with a variety of methods put forward, and people tend to have strong views about it. But there are some useful general principles that can be stated, and we will present some of them in a series of articles.
The first point is perhaps the hardest one for newcomers to OOD to grasp. People will ask "How can I decide what classes my program should have in it?" The fundamental rule is that a class should represent some abstraction. For example, a Date class might represent calendar dates, an Integer class might deal with integers, and a Matrix class would represent mathematical matrices. So you need to ask "What kinds of entities does my application manipulate?"
Some examples of potential classes in different application areas would include:
GUI/Graphics - Line, Circle, Window, TextArea, Button, Point
Statistics - Mean, ChiSquare, Correlation
Geography - River, Country, Sea, Continent
Another way of saying it would be this. Instead of viewing an application as something that performs steps A, B, and C, that is, looking at the program in terms of its functions, instead ask what types of objects and data the application manipulates. Instead of taking a function-oriented approach, take an object-oriented one.
One obvious question with identifying potential classes is what level of granularity to apply. For example, in C++ an "int" is a primitive type, that represents an abstraction of mathematical integers. Should int be a class in the usual C++ sense? Probably not, because a class implies certain kinds of overhead in speed and space and in user comprehension. It's interesting to note that Java(tm), a newer object-oriented language, also has int, but additionally supports a "wrapper" class called Integer that represents an integer value. In this way, an application can manipulate integers either as primitives or as classes.
Consider a slightly more ambiguous case. Suppose that you're writing a Date class, and you want to express the concept "day of week". Should this be a class of its own? Besides devising a class for this purpose, at least five other representations are possible:
int dow : 3; (bit field)
char dow;
short dow;
int dow;
enum Dow {SUN, MON, TUE, WED, THU, FRI, SAT};
The "right" choice in this case is probably the enumeration. It's a natural way of representing a limited domain of values
Direct use of primitive types for representation has its drawbacks. For example, if I choose to represent day of week as an integer, then what is meant by:
int dow;
...
dow = 19;
The domain of the type is violated. As another example, C/C++ pointers are notorious for being misused and thereby introducing bugs into programs. A better choice in many cases is a higher-level abstraction like a string class, found in the C++ and Java standard libraries.
On the other end of the scale, it's also possible to have a class try to do too much, or to cover several disparate abstractions. For example, in statistics, it doesn't make sense to mix Mean and Correlation. These statistical methods have little in common. If you have a class "Statistics" with both of these in it, along with an add() member function to add new values, the result will be a mishmash. For example, for Mean, you need a stream of single values, whereas for Correlation, you need a sequence of (X,Y) pairs.
We will have more to say about OOD principles. A good book illustrating several object-oriented design principles is "Designing and Coding Reusable C++" by Martin Carroll and Margaret Ellis, published by Addison-Wesley.
INTRODUCTION TO OBJECT-ORIENTED DESIGN PART 2 - DATA ABSTRACTION
As we said in the previous issue, object-oriented design has many aspects to it, and a variety of strong views about which approach is "right". But there are some general techniques that are useful.
One of these, one that constitutes a whole design method in itself, is data abstraction. Simply stated, data abstraction refers to identifying key data types in an application, along with operations that are to be done on those types.
What does this mean in practice? Suppose that we are doing graphics of some sort, and are concerned with X,Y points on a screen. Now, at a low enough level, a point might be described via a couple of floating-point numbers X and Y. But with data abstraction, we define a type "Point" that will refer to a point, and we hide from the users of the type just how such a point is implemented. Instead of directly using X,Y values, we present Point as a distinct data type, along with some operations on it.
In the case of a Point type, two of those operations are (1) establishing a new Point instance, that describes an actual screen point, and (2) computing the distance between this point and another point.
If Point was written out as a C++ class, it might look like:
class Point {
float x;
float y;
public:
Point(float, float);
float dist(const Point&);
};
We've declared a class Point with a couple of private data members. There is a constructor to create new object instances of Point, and a member function dist() to compute the distance between this point and another one.
Suppose that we instead implemented this as C code. We might have:
struct Point {
float x;
float y;
};
typedef struct Point Point;
float Point_dist(Point*);
and so on.
The C approach will certainly work, so why all the fuss about data abstraction and C++? There are several reasons for the fuss. One is simply that data abstraction is a useful way of looking at the organization of a software program. Rather than decomposing a program in terms of its functional structure, we instead ask the question "What data types are we operating on, and what sorts of operations do we wish to do on them?"
With data abstraction, there is a distinction made between the representation of a type, and public operations on and behavior of that type. For example, I as a user of Point don't have to know or care that internally, a point is represented by a couple of floating-point numbers. Other choices might conceivably be doubles or longs or shorts. All I care about is the public behavior of the type.
In a similar vein, data abstraction allows for the formal manipulation of types in a mathematical sense. For example, suppose that we are dealing with screen points in the range 0-1000, typical of windowing systems today. And we are using the C approach, and say:
Point p;
p.x = 125;
p.y = -59;
What does this mean? The domain of the type has been violated, by introduction of an invalid value for Y. This sort of invalid value can easily be screened out in a C++ constructor for Point. Without maintaining integrity of a type, it's hard to reason about the behavior of the type, for example, whether dist() really does compute the distance appropriately.
Also, if the representation of a type is hidden, it can be changed at a later time without affecting the users of the type.
As another simple example of data abstraction, consider designing a String class. In C, strings are implemented simply as character pointers, that is, of type "char*". Such pointers tend to be error prone, and we might desire a higher-level alternative.
In terms of the actual string representation, we obviously have to store the string's characters, and we also might want to store the string length separately from the actual characters.
Some of the operations on strings that we might want would include:
- creating a String from a char*
- creating a String from another String
- retrieving a character at a given index
- retrieving the length
- searching for a pattern in a String
Given this very rough idea for a data type, we could write C++ code like so:
class String {
char* str;
int len;
public:
String(const char*);
String(const String&);
char charAt(int) const;
int length() const;
int search(const String&) const;
};
and so on.
In medium-complexity applications, data abstraction can be used as a design technique by itself, building up a set of abstract types that can be used to structure a complete program. It can also be used as part of other design techniques. For example, in some application I might have a calendar date type, used to store the birthdate of a person in a personnel record. Data abstraction could be used to devise a Date type, independent of any other design techniques used in the application.
There is an excellent (but out of print) book on data abstraction, with the title "Abstraction and Specification in Program Development", by Barbara Liskov and John Guttag (published 1986 by MIT Press). Note also that data abstraction is only one part of object-oriented design and programming. Some languages (Modula-2, Ada 83) support data abstraction without being fully object-oriented.
INTRODUCTION TO OBJECT-ORIENTED DESIGN PART 3 - POLYMORPHISM
The example in the previous section illustrates another aspect of object-oriented design, that of polymorphism. This term means "many forms", and in the context that we are using refers to the ability to call member functions of many object types using the same interface.
The simplest C++ example of this would be:
#include
class A {
public:
virtual void f() {cout << "A::f" << endl;}
};
class B : public A {
public:
virtual void f() {cout << "B::f" << endl;}
};
int main()
{
B b;
A* ap = &b;
ap->f();
return 0;
}
which calls B::f(). That is, the base class pointer ap "really" points at a B object, and so B::f() is called.
This feature requires some run-time assistance to determine which type of object is really being manipulated, and which f() to call. One implementation approach uses a hidden pointer in each object instance, that points at a table of function pointers (a virtual table or vtbl), and dispatches accordingly.
Without language support for polymorphism, one would have to say something like:
#include
class A {
public:
int type;
A() {type = 1;}
void f() {cout << "A::f" << endl;}
};
class B : public A {
public:
B() {type = 2;}
void f() {cout << "B::f" << endl;}
};
int main()
{
B b;
A* ap = &b;
if (ap->type == 1)
ap->f();
else
((B*)ap)->f();
return 0;
}
that is, use an explicit type field. This is cumbersome.
The use of base/derived classes (superclasses and subclasses) in combination with polymorphic functions goes by the technical name of "object-oriented programming".
It's interesting to note that in Java, methods (functions) are by default polymorphic, and one has to specifically disable this feature by use of the "final", "private", or "static" keywords. In C++ the default goes the other way.
INTRODUCTION TO OBJECT-ORIENTED DESIGN PART 4 - DATA HIDING
Another quite basic principle of object-oriented design is to avoid exposing the private state of an object to the world. Earlier we talked about data abstraction, where a user-defined type is composed of data and operations on that data. For example, in C++ a type Date might represent a user-defined type for calendar dates, and operations would include comparing dates for equality, computing the number of days between two dates, and so on.
Suppose that in C++, a Date type looks like this:
class Date {
public:
int m; // month 1-12
int d; // day 1-31
int y; // year 1800-1999
};
and I say:
Date dt;
dt.m = 27;
What does this mean? Probably nothing good. So it would be better to rewrite this as:
class Date {
int m;
int d;
int y;
public:
Date(int, int, int);
};
with a public constructor that will properly initialize a Date object.
In C++, data members of a class may be private (the default), protected (available to derived classes), or public (available to everyone).
A simple and useful technique for controlling access to the private state of an object is to define some member functions for setting and getting values:
class A {
int x;
public:
void set_x(int i) {x = i;}
int get_x() {return x;}
};
These functions are inline and have little or no performance overhead.
In C++ there is another sort of hiding available, that offered by namespaces. Suppose that you have a program with some global data in it:
int x[100];
and you use a C++ class library that also uses global data:
double x = 12.34;
These names will clash when you attempt to link the program. A simple solution is to use namespaces:
namespace Company1 {
int x[100];
}
namespace Company2 {
double x = 12.34;
}
and refer to the values as "Company1::x" and "Company2::x". Note that the Java language has no global variables, and similar usage to this example would involve static data defined in classes.
Data hiding is a simple but extremely important concept. Without it, it is difficult to reason about the behavior of an object, given that its state can be arbitrarily changed at any point.
INTRODUCTION TO OBJECT-ORIENTED DESIGN PART 5 - REPRESENTATION HIDING
In the last issue we talked about data hiding, where the internal state of an object is hidden from the user. We said that one reason for this hiding is so that the state can not be arbitrarily changed.
Another aspect of hiding concerns the representation of an object. For example, consider a class to handle a stack of integers:
class Stack {
???
public:
void push(int);
int pop();
int top_of_stack();
};
It's pretty obvious what the public member functions should look like, but what about the representation? At least three representations could make sense. One would be a fixed-length array of ints, with an error given on overflow. Another would be a dynamic int array, that is grown as needed by means of new/delete. Yet a third approach would be to use a linked list of stack records. Each of these has advantages and disadvantages.
Suppose that the representation was exposed:
class Stack {
public:
int vec[10];
int sp;
...
int top_of_stack();
};
and someone cheats by accessing top of stack as:
obj.vec[obj.sp]
instead of:
obj.top_of_stack()
This will work, until such time as the internal representation is changed to something else. At that point, this usage will be invalidated, and will not compile or will introduce subtle problems into a running program (what if I change the stack origin by 1?).
The point is simply that exposing the internal representation introduces a set of problems with program reliability and maintainability.
INTRODUCTION TO OBJECT-ORIENTED DESIGN PART 6 - EXTENSIBILITY
Thus far we've looked at object-oriented design in isolation, focusing on individual classes as abstractions of some real-world entity. But as you're probably already aware, C++ classes (and ones in other languages as well) can be extended by deriving subclasses from them. These classes add functionality to the base class.
Suppose that we have a class:
class A {
private:
int x;
protected:
int y;
public:
int z;
};
The declarations of the members indicate that x is available only to member functions of the class itself, y is available to subclasses, and z is available to everyone.
How do we decide how to structure a class for extensibility? There are several aspects of this, one of them being the level of protection of individual members. There is not a single "right" answer to this question, but one approach is to ask how the class is likely to be used. For example, with a Date class:
class Date {
private:
long repr; // days since 1/1/1800
};
it's unlikely that a derived class will need to directly access repr, because it's in an arcane format and because the Date class can supply a set of functions that will suffice to manipulate Dates. There is a steep learning curve in learning how to directly manipulate the underlying representation, and a consequent ability to mess things up by getting it wrong.
On the other hand, for a Tree class:
class TreeNode {
protected:
TreeNode* left;
TreeNode* right;
int value;
public:
TreeNode(TreeNode*, TreeNode*, int);
};
making the internal pointers visible may make sense, to facilitate a derived class walking through the tree in an efficient manner.
It's useful to distinguish between developers, who may wish to extend a class, and end users. For example, with the Date class, the representation (number of days since 1/1/1800) is non-standard, and in a hard format to manipulate. So it makes sense to hide the representation completely. On the other hand, for TreeNode, with binary trees as a well-understood entity, giving a developer access to the representation may be a good idea.
There's quite a bit more to say about extensibility, which we will do in future issues.
INTRODUCTION TO OBJECT-ORIENTED DESIGN PART 7 - MORE ABOUT EXTENSIBILITY
In the last issue we started talking about extending the functionality of a base class via a derived class. Another aspect of this simply deals with the issue of how far to carry derivation. In other words, how many levels of derived classes make sense?
In theoretical terms, the answer is "an infinite number". That is, you can carefully design a set of classes, with each derived class adding some functionality to its base class. There is no obvious stopping point for this process.
In practical terms, however, deep class derivations create more problems than they solve. At some point, humans lose the ability to keep track of all the relationships. And there are some hidden performance issues, for example with constructors and destructors. The "empty" constructor for C in this example:
#include
class A {
public:
A() {cout << "A::A\n";}
~A() {cout << "A::~A\n";}
};
class B : public A {
public:
B() {cout << "B::B\n";}
~B() {cout << "B::~B\n";}
};
class C : public B {
public:
C() {cout << "C::C\n";}
~C() {cout << "C::~C\n";}
};
void f()
{
C c;
}
int main()
{
f();
return 0;
}
in fact causes the constructors for B and A to be called, and likewise for the destructor.
As a simple rule of thumb, I personally try to keep derivations to three levels or less. In other words, a base class, and a couple of levels of derived classes from it.
INTRODUCTION TO OBJECT-ORIENTED DESIGN PART 8 - A BOOK ON C++ DESIGN
In issue #027 the new edition of Bjarne Stroustrup's book "The C++ Programming Language" was mentioned. This book came out a few months ago, and contains about 100 pages on design using C++. It starts out by discussing design at an abstract level, and then moves on to cover specific design topics as they relate to C++. Recommended if you're interested in this topic.
INTRODUCTION TO OBJECT-ORIENTED DESIGN PART 9 - TEMPLATES VS. CLASSES
In previous issues we've looked at some of the aspects of template programming. One big issue that comes up with object-oriented design is when to implement polymorphism via a template (a parameterized class or function) in preference to using inheritance or a single class.
This is a hard question to answer, but there are several aspects of the issue that can be mentioned. Consider first the nature of the algorithm that is to be implemented. How generally applicable is the algorithm? For example, sorting is used everywhere, and a well-designed sort function template for fundamental or user-defined types would be very handy to have around.
On the other hand, consider strings. Strings of characters are very heavily used in programming languages. But what about strings of doubles? For example, does taking a substring of doubles from a string mean very much? In certain applications it might, but clearly this feature is not as generally useful as strings of characters.
On the other side of this same argument, if we want to implement an algorithm for a set of types, and some of those types are much more widely used than others (such as a string of chars), then template specializations offer a way to tune performance. For example, a string template might be defined via:
templateclass string { ... };
with a specialization for characters:
class string{ ... };
that is optimized. Of course, if strings of chars represent 99% of the use of the string template, then perhaps simply devising a string class would make more sense.
Another question to ask is whether all the types of interest fit cleanly into a single class hierarchy. For example, a hierarchy for a GUI window system might have:
class Component { ... };
class Container : public Component { ... };
class Window : public Container { ... };
class Frame : public Window { ... };
That is, all types are in one hierarchy. Such a type hierarchy is often best managed via abstract classes and virtual functions, without the use of templates. Note that using virtual functions allows for access to runtime type information, whereas templates are more of a compile-time feature. Newsletter issues #024, #025, and #026 give some examples of the use of virtual functions and runtime type identification.
No comments:
Post a Comment