Data Structures and Algorithms
2. Programming Strategies

It is necessary to have some formal way of constructing a program so that it can be built efficiently and reliably. Research has shown that this can be best done by decomposing a program into suitable small modules, which can themselves be written and tested before being incorporated into larger modules, which are in turn constructed and tested. The alternative is create what was often called "sphaghetti code" because of its tangled of statements and jumps. Many expensive, failed projects have demonstrated that, however much you like to eat sphaghetti, using it as a model for program construction is not a good idea!

It's rather obvious that if we split any task into a number of smaller tasks which can be completed individually, then the management of the larger task becomes easier. However, we need a formal basis for partitioning our large task into smaller ones. The notion of abstraction is extremely useful here. Abstractions are high level views of objects or functions which enable us to forget about the low level details and concentrate on the problem at hand.

To illustrate, a truck manufacturer uses a computer to control the engine operation - adjusting fuel and air flow to match the load. The computer is composed of a number of silicon chips, their interconnections and a program. These details are irrelevant to the manufacturer - the computer is a black box to which a host of sensors (for engines speed, accelerator pedal position, air temperature, etc) are connected. The computer reads these sensors and adjusts the engine controls (air inlet and fuel valves, valve timing, etc) appropriately. Thus the manufacturer has a high level or abstract view of the computer. He has specified its behaviour with statements like:

"When the accelerator pedal is 50% depressed, air and fuel valves should be opened until the engine speed reaches 2500rpm".

He doesn't care how the computer calculates the optimum valve settings - for instance it could use either integer or floating point arithmetic - he is only interested in behaviour that matches his specification.

In turn, the manager of a transport company has an even higher level or more abstract view of a truck. It's simply a means of transporting goods from point A to point B in the minimum time allowed by the road traffic laws. His specification contains statements like:

"The truck, when laden with 10 tonnes, shall need no more than 20l/100km of fuel when travelling at 110kph."

How this specification is achieved is irrelevant to him: it matters little whether there is a control computer or some mechanical engineer's dream of cams, rods, gears, etc.

There are two important forms of abstraction: functional abstraction and structural abstraction. In functional abstraction, we specify a function for a module, i.e.

"This module will sort the items in its input stream into ascending order based on an ordering rule for the items and place them on its output stream."

As we will see later, there are many ways to sort items - some more efficient than others. At this level, we are not concerned with how the sort is performed, but simply that the output is sorted according to our ordering rule.

The second type of abstraction - structural abstraction - is better known as object orientation. In this approach, we construct software models of the behaviour of real world items, i.e. our truck manufacturer, in analysing the performance of his vehicle, would employ a software model of the control computer. For him, this model is abstract - it could mimic the behaviour of the real computer by simply providing a behavioural model with program statements like:
if ( pedal_pos > 50.0 ) {
	set_air_intake( 0.78*pedal_pos);
	set_fuel_valve( 0.12 + 0.32*pedal_pos);
Alternatively, his model could incorporate details of the computer and its program.

However, he isn't concerned: the computer is a "black box" to him and he's solely concerned with its external behaviour. To simplify the complexity of his own model (the vehicle as a whole), he doesn't want to concern himself with the internal workings of the control computer; he wants to assume that someone else has correctly constructed a reliable model of it for him.

Key terms

Producing a computer program rapidly, without thought and without any design methodology.

Continue on to Objects and ADTs
Back to the Table of Contents
© , 1998