Monday, July 25, 2011

Object Oriented Design

I'm certainly not an expert but I think I know enough to give you some useful information if you've just started or want to start designing.
It is particularly useful if you've just started C++ and you're wondering how to decide what classes to use and what goes in them - that's exactly what design is about.
I hope it's useful as a starting place but you should definitely get hold of some more detailed and expert opinion if you're going to use object-oriented design for anything serious. 

We will cover the following task,

  • The concepts of object-oriented design
    • Objects
    • Classes
    • Abstraction
    • Inheritance
    • Polymorphism
  • A simple example of object-oriented design
    • A notation for designing
    • How the notation makes it easy to spot and solve a design problem
  • A more complicated example
    • Starting the design from requirements
    • Criticising and refining the design
  • Conclusions
    • A simplified design process
    • Other advice     

Object-Oriented Design

Design is something you do when your brain is too small to hold the entire project. Design is about managing complexity: a design method helps you to split big projects into manageable chunks the will fit in your brain.
Design methods provide a notation, which allows you to store (for  example, on paper or on computer) and communicate design decisions. Object-oriented design is not the only type of design. Other types include structured design and data-driven design. It's worth looking at other design methods: they all have their advantages and disadvantages. However, it's best to stick with just one and wait until you've grasped that before looking at other methods. In OOD, problems are modelled using objects. Objects have:

  • Behaviour (they do things)
  • State (which changes when they do things)
For example, a car could be an object. It has a state: whether its engine is running, and it has a behaviour: starting the car, which changes its state from "engine not running" to "engine running".
In object-oriented design, complexity is managed using abstraction. Abstraction is the elimination of the irrelevant and the amplification of the essential. For a real-world example of abstraction, we'll look at cars.

An Example of Abstraction

I can teach someone to drive any car by using an abstraction. I amplify the essential: I teach about the ignition and steering wheel, and I eliminate the details, such as the particular engine in this car or the way fuel is pumped to the engine where a spark ignites it, it explodes pushing down a piston and driving a crankshaft.
Problems usually have levels of abstraction. We can see a car at a high level of abstraction for driving but mechanics need to work at a lower level of abstraction: they do care about details and need to know about batteries and engines.
However, there are abstractions at the mechanic's level too. The mechanic might test or charge a battery without caring that inside the battery there's a complex chemical reaction going on. A battery designer would care about these details but wouldn't care about, say, the electronics that go into the car's radio.
We've seen that we can look at the details such as the battery or radio design, and they are separated in manageable chunks, and by using abstraction and ignoring the details, we can also look at the whole car as a manageable chunk.
Let's look at some common sorts of abstraction for software.

Abstraction for Programming


Imagine a picture made up of squares. Each square is an object. It has a state: its colour and position, and a behaviour: we can, amongst other things, change its colour and draw it. Each square is different but has much in common with other squares. So, we abstract out the commonalities: they share the same behaviour and have the same sort of attributes. We've ignored the particular values of the attributes. This abstraction is called a class.

As Grady Booch puts it:
A class is a set of objects that share a common structure and a common behaviour

Classes are useful because they act as a blueprint for objects. If we want a new Square, we use the Square class and simply fill in the particular details (i.e. its colour and position).
Figure 1 shows how we can represent the Square class. The dotted cloud means a class and we can see that is has two attributes: a colour and an array of points, and two operations: set_colour() and draw().

Figure 1: The Square class


Imagine that, as well as Squares, we have Triangles. Figure 2 shows the class for our Triangles.

Figure 2: The Triangle class

Now, comparing figures 1 and 2, we can see that there's some difference between Triangles and Squares. Triangles have three vertices; Squares have four. Also, the way that these shapes are drawn is different.
However, there are some similarities. For example, we can set the colour of both and both can be drawn (even if the way they are drawn is different). It would be nice if we could abstract: eliminate the details of each shape and amplify the fact that both can have their colours set and be drawn. For example, at a high level of abstraction we might want to think of a picture as made up of shapes and to draw the picture we draw each shape in turn. We want to eliminate the irrelevant details: we don't care that one shape is a square and the other a triangle as long as both can draw themselves.
To do this we move the important common parts out of these classes into a new class called Shape. Figure 3 shows the result.

Figure 3: Abstracting common features into a new class

This sort of abstraction is called inheritance. The lower-level classes (known as subclasses or derived classes) inherit state and behaviour from this higher-level class (known as a superclass or base class). So, for example, a Triangle object will have a colour, a set_colour() operation, three Points and a draw() operation.
We can inherit three sorts of things:

  • state: e.g. Colour
  • operations: e.g. set_colour()
    Shape knows enough to be able to set the colour for any shape
  • The interface of an operation

Shape contains the interface of the draw() operation because the draw() interface for Triangle and Square is identical but the code for the operation remains in the subclasses because it is different.
When we abstract just the interface of an operation and leave the implementation to subclasses it is called a polymorphic operation.
So, we've seen that we can abstract by pulling out important state, behaviour and interface into a new class. Remember, we can also abstract by combining objects inside a new object. In the car example, a car combines a battery, engine and other objects into a new object and provides a simple interface for driving that hides these details. There are different sorts of abstraction and finding the best ways to apply abstraction to a problem is what design is all about.
In summary, with object-oriented design you use abstraction to break a problem in to manageable chunks. You can comprehend the problem as a whole or study parts of the problem at lower levels of abstraction.
If you work at an appropriate level of abstraction then any problems you find can be solved relatively easily. As an example of not working at the right level of abstraction, imagine that I tried to build a house by going out with some bricks and just building. The chances are I'd finish, try to put the bath in and discover that the bathroom was too small. So, I'd have to knock down and rebuild a wall. That's a lot of work, assuming it could be done. If I'd designed the house, including where the fittings were going, I'd have noticed the problem and fixing it would've taken about 10 seconds with my eraser and pencil.
We've seen the key parts of OOD, so let's do some designing.

An Example: Multiple Views

Our example application is a picture editor. One requirement is that we can have several windows showing the picture at one time.
The important thing about multiple views is that when the picture changes (through the user editing it in one window), all of the windows are updated. The problem is to model how this update occurs in our program.

An Object Diagram

Let's think about the objects that might be involved. We've been talking about pictures and views so we'll use the words Picture and PictureViewer as classes. We won't use Window or PictureWindow because PictureViewer is a more abstract term. We can make our own meaning for "viewer" and it might include, say, a menu or toolbar but window has a particular meaning in terms of the operating system.
Now let's look at how their objects interact. Figure 4 shows how objects from the Picture and PictureViewer class might interact to cause the update that we need.

Figure 4: Updating multiple views (an object diagram)

We're using a graphical notation to write down our design, this is Booch's notation. The cloud on the left is an object from the Picture class. The first thing that happens is that it is told that it has been updated (who by, we will decide later - for example, the Picture could notify itself, or whoever changed it could tell it to update).
The second thing that happens is that picture tells a number of PictureViewer objects to update themselves (notice the clouds are stacked up to show several objects).
Notice that there are no parameters to the operations. At the moment we don't know enough to say what parameters are needed, so we defer the decision. Parameters would be filled in when we worked out how the PictureViewers update themselves.

Class Diagrams

Now we can draw a class diagram to see how the Picture and PictureViewer classes are related.

Figure 5: How Picture and PictureViewer are related (a class diagram)

Classes are shown using a dotted cloud (compare this to the solid clouds used in the object diagram).
Notice, from figure 4, that a Picture must communicate with a number of PictureViewers. It must also know which PictureViewers are associated with it. The topmost black circle and line in figure 5 captures this information: it means that Picture "has" a number of PictureViewers. This doesn't mean that Picture actually contains the PictureViewers: it might look them up in a table or database or use some other object to store them.
We've also got a "has" going the other way. A PictureViewer has to know what Picture it is viewing and it will have to call operations such as draw() on the Picture. This will be confirmed if we draw object diagrams for update() and other operations.
You might be thinking that these diagrams are trivial and that there's no point in drawing them. However, the class diagram clearly shows an important problem: Picture and PictureViewer depend on each other and so cannot be used separately. The classes are tightly coupled.
Tight coupling means that if you change one, both must be recompiled. More importantly, Picture might be useful in other applications, as part of a DTP document for example, but it's likely we wouldn't want a PictureViewer - we'd probably just have a DTPdocument viewer.
Tight coupling is not always a bad thing, for example, we would expect list and list_iterator to be tightly coupled. It doesn't make sense to have one without the other.
To make Picture independent, we abstract out the elements of PictureViewer that it relies on. Figure 6 shows the result. We pull out just the interface of update() and leave behind the implementation (and everything else that makes up a PictureViewer).

Figure 6: Using abstraction (inheritance) to make Picture re-usable

Picture now only relies on PictureObserver. If we re-use Picture we take PictureObserver along too, but PictureObserver only contains the interface of the update() function - that's useful: the DTPdocument might need to reformat itself if the picture changes so it would inherit from PictureObserver.
Another benefit of this abstraction is that we can have different types of observers. For example, if we wanted to add a statistics window showing say, amount of memory used by the picture and how many shapes were in it, we would want it to update as the window was changed, and, to do so, we simply derive a StatsViewer class from PictureObserver.
Now, we've seen some example of object and class diagrams and we've seen an instance of tight coupling - generally considered a bad thing - and how to get round it.
We've put in a bit of sweat to this bit of design and there will be more to do as we consider how a new view is created (and how Picture comes to know about the PictureViewer) and what happens when a view is closed. However, for this problem, we'd have saved ourselves a lot of time, if we'd known about design patterns.

Design Patterns

Design patterns name, explain and evaluate important and recurring design fragments. They capture design experience, which is exactly what you don't have but could really do with when you're a newcomer to design. For our problem, we would've used the Observer design pattern, which explains how a subject informs a number of observers that it has changed. It includes an interface for attaching and detaching observers from their subjects. It discusses design and implementation issues that will help, for example, when examining PictureViewer's update() function.
Unfortunately, we don't have time to do discuss design patterns in any detail so we'll plough on without them. But at least you now know that they're useful and you should find out about them.

The Picture Editor's Requirements

We'll now have a look at a more complicated example and, this time, we'll start with list of requirements for our program.

How Not to Write Requirements :-)

  1. The user can create a new picture
    • The new picture will contain no shapes
    • A window will be opened displaying the new picture
  2. The user can add a shape to the picture
  3. The user can create a "new view" of a picture
    • This means there may be several windows showing the same picture at one time
    • Changes to the picture made via one window must be reflected in all windows showing that picture
  4. The user can select a number of objects (the objects are known as the selection)
    • A rectangle is drawn around shapes that are selected
    • Each window has its own unique selection
5. The user may move the selection.
6. The user may delete the selection.

These are not particularly good requirements. They are not complete and they are not very detailed. Requirement 4, for example, covers a number of requirements in that we would expect to be able to add and remove objects from a selection. However, they'll do for this example.
One way to begin a design is to look for nouns or noun phrases to be classes (the verbs and verb phrases to be operations). Not all of these will or should end up in your final design and you'll add classes and operations that aren't generated by this technique. This technique is not some sort of magic class generator that does your design for you. It simply gives you something to start working with.
We'll pick out Picture, Shape, PictureViewer (which I use instead of Window) and Selection. The requirements suggest some relationships between these classes. So we'll draw a class diagram and mark on the relationships. Requirements 1 and 2 suggest that a Picture "has" a number of Shapes. Requirement 4 suggests that a Selection also "has" a number of Shapes. Requirement 1 suggests that each window (PictureViewer) has one Picture. Requirement 4 says that each PictureViewer has one Selection. Note that an alternative to this last relationship is that the Picture has a Selection, which would be shown in every window. This is what !Draw does but Acorn's latest guidelines are that windows have unique selections (see Acorn's Clipboard application note for details).
Figure 7 is the class diagram showing these relationships.

Figure 7: Relationships between classes implied by requirements

The next step is to pick one of the requirements and work out an object diagram for it. We haven't got time to look at them all but I'm going to pick on one interesting problem based on the multiple views update that we've already looked at.
When we move a selection of objects, the picture changes and so is updated. However, if a shape that moved was selected in another window, the rectangle surrounding it must be moved too. Assuming Selection is responsible for drawing itself (the rectangles), it must be informed of changes in the picture.
Let's see if we can come up with an object diagram for this.

Updating the Selection

Attempt 1

The first assumption we'll make is that the Shape object is responsible for calling update on the Picture (so the multiple views get updated).
Notice I'm cheating here, we should really be looking at moving a selection and one possibility is that the selection moves the shapes and then calls update on the picture. However, concentrating on shapes simplifies the discussion and diagrams a little.

Figure 8: How the display is updated when a Shape moves (first attempt)

Looking at the object diagram in figure 8, we can see that, after being informed that it has been updated, Picture calls update on all of its PictureViewers (from our earlier discussions about re-usability, this should be PictureObservers but we'll ignore that for simplicity).
Next (step 4, on the diagram), PictureViewer updates the shape on screen somehow. Now, we don't want to bother with the details of the update here (we're abstracting), so we'll create a new operation update_display(). We can worry about update_display() (and draw an object diagram for it) later on.
Now, so that the Selection can update itself if necessary, PictureViewer forwards the update to the Selection. The Selection must check that the Shape is actually in the selection. Ahhh... but how does it know what Shape to check for? We give the Shape a name, s, and pass it around as a parameter. We don't pass it in to update_display() because we don't know anything about update_display() and what parameters it requires yet. When we do look at update_display() we may have to come back to this diagram and add more parameters.
Now that's one way of doing it. The point about working at a high level of abstraction like this is that we can easily try out alternatives. This is the first thing we've thought of and it doesn't mean it's the best. We should try and think of alternatives and one way I find useful is to find picky points wrong with the current diagram and think of ways round them.

Attempt 2

Picky point one: there's quite a complicated chain of updates and PictureViewer is responsible for passing things on to Selection. Surely, Selection is a sort-of PictureObserver; it wants to be updated when the Picture changes.
So, one new approach is to make Selection a PictureObserver and register it with Picture. Figure 9 shows this idea as a class diagram. Figures 10 and 11 show how the update works using object diagrams (i.e. these replace figure 8).

Figure 9: Both Selection and PictureViewer are PictureObservers: they can both be updated

Figure 10: How the display is updated when a Shape moves (second attempt)

Figure 11: How Selection updates itself

Attempt 3

Picky point two: we don't know how Selection's is_in() is implemented but, if there are a lot of shapes in the selection, it could be expensive. Our requirement is actually to move selections so, if is_in() is linear, we could have an O(nІ) algorithm. Can we do without it?
This is a picky point, we shouldn't be making implementation decisions about is_in() yet, but it does help to direct a search for alternatives.
What if, instead of observing Pictures, we observed Shapes? We could register Selections as "shape observers". Figure 12 shows how shapes would notify their observers that they had moved. Figure 13 shows how the classes involved are related.

Figure 12: How observers are notified when a Shape moves

Figure 13: How the classes involved in display update are related

Now we can compare and contrast the alternatives.
The new version is extremely simple: PictureViewer doesn't have to forward things to Selection and Picture doesn't have to forward things to PictureViewer.
It's also efficient: Selections are only informed when a Shape they are viewing moves rather than when any Shape moves.
Figure 12 is a complete replacement for figure 8; you can see how much simpler this approach is (we don't need update_display() because the update() operations now only need to update the display - they don't need to forward the call or check that a shape is in the Selection as they did before).
You might be worried about Shape having to keep track of some number of ShapeObservers. If there were a lot of small (in terms of memory) Shapes, storing (references to) these physically would mean a big overhead. As I mentioned earlier, "has" doesn't necessarily mean physical containment, we can store this relationship in some other way and exactly how we do is a problem for later on - at a lower level of abstraction.
Although this approach looks like the best, we should evaluate it in the context of other scenarios. Although it makes update very straightforward it might make other parts of the design more complicated.

The Next Step

We're working at a high level of abstraction, with objects very close to the user. Once we've covered all or most of the requirements, we'll need to move down a level and investigate some of the details such as how PictureViewer actually updates the display and, perhaps, how Shape knows about its observers.
As we look at these we'll probably discover flaws in the original diagrams or think of problems that affect higher levels - perhaps missing or vague requirements. That's to be expected and we would go back and fix or improve the earlier diagrams.


A simplified design process

  1. Generate a list of requirements for the system.
  2. Pick a requirement.
  3. Identify some classes whose objects might be involved in satisfying the requirement.
  4. Do the requirements suggest any relationships between the classes? (draw class diagrams).
  5. Work out how the objects interact to satisfy the requirement (draw object diagrams).
  6. Add operations and any new relationships between classes to the class diagram.
  7. Try to think of other ways (different classes, different interactions between objects) to satisfy the requirement. The first thing you think of is not usually the best.
  8. Do your decisions have repercussions for earlier parts of the design?
  9. Pick another requirement...

Other Advice

Try to work in "levels" of abstraction

Start at a high level and as each level "firms up" start looking at the layer below. It isn't necessary to have a level complete before moving on - remember problems that occur in one level may have an effect on the level above.

Defer decisions

Don't make decisions about, say, physical containment early on. Things like storage in a list or hash table are fairly low-level details.
Create new operations to avoid dealing with details.

Find out what makes a good design

We've already seen that tight coupling can be a problem. Another "rule of thumb" is that classes that are used by many other classes should be stable (because changing them affects many other classes) and that often means that they consist purely of interface.
You can measure how good your design is using metrics.

Anticipate likely modifications and likely candidates for re-use

Design with these in mind, but don't go too mad - you could create an impenetrable jungle of classes.

The End

Well, that's it. I hope you've found this talk useful and it's given you enough information to start designing your own programs. 

Reference Books

You can follow some of the good books for Object Oriented Design 

  1. Design Patterns: Elements of Reusable Object-Oriented Software
  2. Object-Oriented Analysis and Design with Applications (3rd Edition)
  3. Object-Oriented Analysis and Design with Applications (3rd Edition)

No comments:

Post a Comment