This paper explains system design as a process of active, local,
and opportunistic search through multiple dimensions. In the design
of object-oriented systems, four main types of link may be described:
control flow, data flow, sequence, and class encapsulation. Design
occurs by choosing an initial focus for design, choosing a type
of link to pursue, and then tracing out the system structure from
that focus along the link type in some direction.
Plans and objects are orthogonal, because a plan can use many
objects and an object can be used in many plans. This orthogonality
allows the structure of a system to be shown as a lattice of nodes,
where a node marks the intersection between a plan and an object;
a node is an abstract action that contains the code for the part
of a plan within an object. A design strategy defines a trajectory
through these nodes. A goal-based design strategy traces out and
adds one goal at a time, where a class-based strategy traces out
and adds one class at a time to the growing system. Real design
is not this simple, however, because design is essentially fractal
or scale-invariant. A design strategy may be applied to the whole
system, to a single plan, to a single object, to part of a plan
or object, to a single node, or to part of a node.
All correspondence should be sent to
Dr. R. S. Rist
School of Computing Sciences
University of Technology, Sydney
PO Box 123 Broadway, Sydney
NSW 2007
Australia
rist@socs.uts.edu.au
This paper presents a new, powerful, and detailed model of object-oriented
system design based on search from the current location. In this
model, design occurs by choosing a place to start, and searching
from that location along a specific type of link. The typical
novice design strategy, for example, is forward, concrete design.
The novice chooses to start design with the first input, and builds
the system by following the control flow to define a linear series
of actions. A more experienced programmer might choose the goal
of the system to begin design, follow the data flow links backwards
from the goal to the inputs to define the required plan actions,
and then choose some linear order for these actions. An experienced
object-oriented programmer might choose the most basic class to
start design, identify the data stored in that class and add the
class methods, then repeat the process for the next class. Each
design strategy defines a complete trajectory through the system
structure. The very different behaviours seen during design can
all be explained as search from the current location along a link
type.
The structure of an object-oriented system is determined by its
data flow, control flow, and class encapsulation. More formally,
the system structure is created by the interaction between the
plans and objects in the system. A plan is a set of actions that,
when executed in a correct order, achieve the goal of the plan;
a concrete action is a line of code, and an abstract action is
a routine. Plans and objects are orthogonal, because a plan can
use many objects and an object can be used in many plans. When
the actions in a plan are encapsulated in routines, and the routines
are encapsulated in classes, the plan actions are spread out among
the classes. To execute the plan, a routine in some class is called,
executes its code and in turn calls a routine in the next class,
and so on down to the last class at the end of the calling chain.
The structure of an object-oriented (OO) system can thus be shown
as a lattice where the classes are listed across the top of a
table and the goals are listed down the side. Each goal requires
a plan, and each plan can be drawn as a set of circles or nodes
that are called and execute across the classes; each node contains
the code for the part of the plan that is located in that object.
Goal-based design of object-oriented systems occurs by choosing
each goal in turn and defining its plan, where class-based design
occurs by choosing each class in turn and defining its routines.
For the nine experienced programmers described in this paper,
seven showed the typical novice design strategy of forward, goal-based
design. The remaining two programmers used mainly forward, bottom-up,
class-based design.
System structure is a powerful tool to analyze design, because
it can easily show the order in which nodes are added to a system.
Three dimension of design are needed to capture the order in which
nodes are added to the system structure: the link type (goal versus
class), level (top-down versus bottom-up), and direction (forward
versus backward). A design strategy is a point on this three-dimensional
space. No system protocol in the present study showed a complete,
systematic use of any strategy; rather, many strategies were applied
as needed, at various times, to various parts of the problem.
Design is essentially fractal, because a design strategy can be
and is applied at almost any scale: a chunk of the problem is
selected, a solution for that chunk is designed by following some
strategy, then a new chunk is selected and designed. Systematic
design occurs only when the same design strategy is applied to
the complete problem.
This paper is the second in a series. The first paper (Rist, in press-a) describes a cognitive architecture for program design that uses cue-based search (Norman and Bobrow, 1979) to find and link nodes. By using search from the current location as the basic design strategy, the model captures all the common program design strategies in a single architecture. This paper extends the model to the design of OO systems, by describing the structure and design of OO systems in three parts. First, the structure of an OO system is defined and design is explained as a trajectory through this structure. Second, a set of three system design protocols are presented in detail, to show that system structure captures detailed system design. Third, the 36 system design protocols are analyzed statistically to identify the common system design strategies and the amount of systematic design seen in the study. The concluding section presents some applications of the model of OO design.
This section explains how the structure of an OO system is determined
by the data flow, control flow, and data encapsulation in the
system. Each of these views of a system defines a set of nodes
that are chunked by the relevant link type; data flow groups code
into functional chunks, control flow groups code into procedural
chunks, and data encapsulation groups code into class chunks.
These three structures all exist in an OO system, but only the
class is a "first class" computational object that can
be stored and treated as a separate unit.
Studies of procedural program design have examined the separate
effects of control and data flow to show top-down design based
on the control flow (Adelson and Soloway, 1985), forward design
through the data or control flow (Pennington, 1987), backward
design through the data and control flow (Rist, 1989), and forward
design through the linear code structure (Rist, 1991). More recent
studies of OO systems have shown that novices tend to design by
tracing out either the control flow or the class structure separately,
and then integrating these two structures later (Détienne,
in press). Experts tend to design in a more integrated fashion
by following the class or goal as a primary link (Pennington,
Lee, and Rehder, in press) and attaching other links and structure
from the current location as they go.
To provide a common language for functional, procedural, and OO design, I have defined the basic unit of design as the node (Rist, in-press a). A concrete node is implemented as a line of code, and an abstract node is implemented as a routine. In either case, the node representation separates external behaviour from internal implementation and allows design and planning to occur, in a uniform representation, at abstract or concrete levels. A node is linked to other nodes by data and control flow, so it may use data from one or more lines, make data for one or more lines, obey another line, or control one or more lines. The external structure of a node is shown in Figure 1.
The data and control flow links define the essential structure
of a program; these links may be shown as a non-linear plan structure.
A linear order of the plan actions is usually not defined by the
data and control flow dependencies; instead, many linear orders
are possible and one is chosen by the designer. Data encapsulation
into classes is also implicit in the plan structure and has to
be made explicit, so a designer is free to define what data and
code are placed in a particular class. There are thus four types
of link between nodes in an OO system: data, control, linear,
and class. This section shows how all four relations can be captured
in a system structure chart.
Consider a simple system that deposits money into a bank account,
and shows the customer name and balance after the deposit. The
goal of the system is to deposit money, so the focus of the system
is the code to deposit money into an account. The outputs from
the system are the customer's name and account balance, after
the deposit. The plan to show the customer's name is trivial:
the name has to be read, stored and displayed. The plan to deposit
money is also simple: an initial balance has to be read and stored,
the deposit amount read and added to the balance, and the new
balance shown. The plan structure and Pascal code for both outputs
are shown in Figure 2, where a line indicates data flow; in this
system, there are two discrete, non-interacting sets of data flow.
The data dependencies allow a large number of orderings of the
plan actions, one of which is shown in the code in the centre
of Figure 2. Knowledge about objects has been used implicitly
in ordering the code, because the customer's name is read in before
the initial balance, and displayed before the new balance; purely
from the data dependencies, the name could be the last data value
read in by the code. This code could be abstracted into three
parts called initialise, deposit, and display, each consisting
of two lines of code, and a procedure wrapped around each chunk.
The abstract procedural structure of the deposit system is shown
to the right of Figure 2, where the three nodes are executed in
linear order.
The structure of an OO system is defined firstly by the choice
of where to store the data, and then by the way this decision
affects the plan actions. In the deposit system, there are two
clear objects: a customer has a name, and an account has a balance.
In the OO language Eiffel (Meyer, 1992), the code that sets an
attribute must be in the same class as the attribute, while the
code that uses a data value may be placed in the class, or in
some calling (client) class. Applying this rule, the location
of some of the code is now defined: the name should be read and
displayed by code in the class CUSTOMER, and the initial
balance should be read in and displayed by code in class ACCOUNT;
in Eiffel, class names are written in capitals. The code to change
the balance has to be located in class ACCOUNT, but the
code to read the deposit may be in either class. Because the customer
decides how much to deposit, I have chosen to place the input
code in class CUSTOMER, so the amount to deposit is read
in by code in the deposit routine of class CUSTOMER,
and passed as an argument to the deposit routine in ACCOUNT.
A simplified version of the Eiffel code for this ATM system is
shown in Table 1. The data in class CUSTOMER is the name
of the customer and the account, and the data in class ACCOUNT
is the balance. Each class consists of three routines as well
as the data. Each routine in class CUSTOMER does its part
of the plan, and calls a routine in class ACCOUNT to do
the rest of the plan; another class (call it BANK) is required
to drive the customer.
class
CUSTOMER class
ACCOUNT
name: STRING balance: REAL
account: ACCOUNT
make is make is
read (name) read (balance)
account.make
deposit is deposit (amount: REAL) is
read (amount) balance := balance + amount
account.deposit (amount)
display is display is
write (name) write (balance)
account.display
The system structure for the three classes in the system is shown
in Table 2, where the class names and attributes are listed across
the top of the table, and the goals down the side. A circle indicates
a node, a horizontal line indicates control flow and a vertical
line indicates sequence. Input and output are shown by arrows
above and below a node. Data flow between called nodes is shown
by arrows; routine arguments are shown by an arrow to the left
of a node, returned values from functions (none here) are shown
by an arrow to the right of the node. Data flow within a class
is not explicitly shown on a system structure chart, but could
easily be added to show all four types of structure in a single,
but quite complex, picture.
The sequence of actions is easily read from the system structure
chart. The bank starts up, and creates first the customer (with
name) and then the account (with initial balance). No further
routines are called by the make routine in ACCOUNT,
so control returns back to CUSTOMER and then back to BANK.
The bank then makes the customer deposit some amount of money,
and this amount is added to the balance. Finally, the bank shows
the name of the customer and the final account balance.
The structure of the OO system is shown by the control flow between the routines in the system, and these routines are defined by allocating the plan actions among the objects on the basis of where the data is stored. Each node is indexed by a pair of the form <goal, object>, so the code is easily indexed in memory. Because the basic unit of analysis is small and well-defined, a node is a natural unit both of planning and of reuse. The external behaviour of a class can be found by looking down the column for that class, and the signature of each routine in a class can be found by tracing out the data flow for that feature. While the links between all the routines in a system could be shown, the chart is normally levelled to show a single node at each intersection, so a line crosses either an object boundary or a goal boundary. The full set of symbols used in a system structure chart is shown in Table 3.
The unit of analysis in traditional OO notations is the class
(Booch, 1991; Rumbaugh, Blaha, Premerlani, Eddy, and Lorensen,
1991). The unit of analysis in a structure chart is the node,
so the system structure provides a much more detailed representation
of the system. The complete behaviour of a class is defined by
the behaviour of its exported features; that is, by the behaviour
of each node in the class. A complete class definition is thus
logically dependent on an analysis of the goals and plans in which
the object participates, and cannot be known before the plans
have been defined.
A system structure chart for part of an ATM (Automatic Teller Machine) system is shown in Table 4. This system was the most complex system in the protocol study; the full problem specification is given in Appendix A. At the start of the day, a bank clerk logs in and starts the ATM system (BANK), that then waits for a customer to arrive. The customer enters their user identifier (code in class BANK) that is used to look up the list of customers. If the customer is found on the list, then a password is read and checked (PASSWORD). If the password is valid, the customer is shown a menu and chooses an option (CUSTOMER); this option is then executed by the relevant class (ACCOUNT, SHORT, CHEQUE).
Alternate goal choices, such as the menu options to deposit,
withdraw, see the balance, show the choices, or exit, are shown
as a set of unconnected nodes in a column. Because a vertical
line indicates serial order, the choices cannot be connected by
a line; the choices do not execute in sequence. Instead, the line
stops at the first goal choice (deposit here), and resumes after
the last one. Alternate object choices, such as the choice of
a savings or cheque account, are shown as a set of unconnected
nodes in a row. Because a horizontal line indicates a feature
call, alternate objects cannot be connected by a line; the line
stops at the first object choice (savings account here), and resumes
after the last choice. In the ATM system shown in Table 4, no
actions are executed after either the goal choice or the object
choice.
Inheritance is captured by listing the classes across the top
of the table in client and then in inheritance order; there is
a general class ACCOUNT, and two specific types of account
SHORT and CHEQUE. The chart shows the location of
the code, so a plan may terminate at a parent class if the code
is shared, or at a child class if the code is unique. In the ATM
system, the rules to deposit money are the same for all accounts,
so the deposit plan terminates at the parent class ACCOUNT.
To withdraw money, however, the rules are different for savings
and cheque accounts, so the withdraw plan terminates at either
of the child classes SHORT or CHEQUE.
A system structure chart is the OO equivalent of a calling chart
in a procedural system. The order of actions in the chart can
be read by starting at the top, left corner and following first
the control flow and then the sequence. A monolithic program with
no abstract structure, such as that shown in Figure 2, defines
a single node with a huge amount of internal detail. When procedural
structure is added, the routines are executed in linear order
and the chart shows a single set of nodes down the left column.
When object structure is added, each procedural step is split
among its classes and the full system structure is defined.
System structure may be seen as a more formal version of Jacobson's
(1992) use case model. Where a use case concentrates on the user
interaction with a system, system structure provides a formal
notation for the internal system structure. Jacobson uses two
main diagrams in his approach, called the analysis model and the
interaction diagram. The analysis model is very close to the plan
structure of a system (Rist, 1994), because it is a least commitment
model that maps out the data dependencies between parts of a system.
The interaction diagram is very close to a system structure chart,
because it captures the serial order in which events occur and
shows how this serial order interacts with the class definitions.
Formally, a program plan is defined as a backward slice (Berzins,
1995; Horwitz, Prins, and Reps, 1989; Weiser, 1982) through the
code from a goal (an output) to its inputs, so the plan structure
automatically identifies all and only the code needed to achieve
the goal and produce the output. A plan is in general a non-linear
structure, and a use case is the part of a plan that is connected
to form a chunk of control flow. In using an ATM, for example,
the user has to enter their customer identifier and a password,
and the system checks these against the stored id and password.
Having the identifier and password stored in each object are prerequisites
for the action of logging in and are thus connected to that action
by data flow, but not by control flow. The use case consists of
logging in, then using a menu, then using an account, a set of
actions connected in serial order by control flow links. A primary
use case implements a basic goal of the system, captures the long
control flow from the start of a plan to its end, and is thus
an excellent basis for initial system design. A secondary use
case or extension is a new goal that uses the same data as an
existing goal. An abstract use case is simply a plan merge, where
two plans come together and share the same code.
In this paper, the term plan refers to the set of serially connected (non-linear plan) actions that define the use case for a goal, so the plan or use case for a goal corresponds to a horizontal line of nodes in the system structure. The creation, retrieval and use of non-linear plan structures is discussed in detail in Rist (in-press a).
System design occurs by choosing a place to start, choosing a
link to pursue, and then following the link to find and attach
the next part of the solution. That part then becomes the current
focus of attention, and the process repeats until a terminal node
is reached. At that point, a new focus, link type, and direction
has to be chosen to drive design; usually, a new focus is chosen
and the same link type and direction are retained. In forward,
top-down, goal-based design, for example, the designer might choose
to start with the first goal (forward), follow the control flow
to the end of that goal (goal-based, top-down), and then choose
the next goal (forward) and repeat the design strategy. If this
pattern is repeated for the whole system, then design is systematic
and easily described by the single strategy.
Nodes can be connected independently through their data, control,
or class structure. A node can be used as a unit in planning with
little thought about its internal implementation, so a designer
can create and connect a set of nodes by their control flow without
knowing how to implement these abstract actions. Alternately,
nodes can be connected through their data flow with no thought
to their control sequence. Alternately, the nodes in a class can
be defined with little thought to their control flow or implementation.
In the system structure, it is easy to trace the order that nodes
are added to the growing solution if the control flow, serial
order, or class links are pursued during design. Because the data
flow is implicit in the chart, it is much more difficult to show
the node emergence order when the designer follows the data flow.
This can be done, but such a display quickly becomes difficult
to read.
The main design strategies are shown in Table 5, applied to the
deposit system; each type of link defines a dimension of search.
Top-down design starts with the highest level calling node, at
the left of the system structure, and follows the calling structure
to the right; bottom-up design starts with the most basic actions
at the right of the chart, and adds actions leftwards. Forward
design starts with the first action or unit at the top of the
chart, and follows the serial structure down the chart; backward
design starts with the final actions, and adds pre-requisite actions
above that initial focus. In goal-based design the goal is the
basic unit, where the class is the basic unit in class-based design.
Goal-based design corresponds to Jacobson's model of design by
use cases, in which each use case is traced out (horizontally)
and then the actions are grouped (vertically) by the objects they
use.
A design strategy defines a visiting order on the nodes, but
does not say what to do at each node. This is a great source of
strength, because the same strategy can be applied to define the
class headers, the attributes, and the code. It is common for
the class names and attributes to be defined before any code is
written, but this is not necessary.
As shown in table 5, a top-down, forward design strategy starts
with the first action at the top, left corner of the system structure
chart. A forward, bottom-up, class-based strategy would start
at the top, right corner of the chart. Often, a designer will
choose some part of the problem as the essential, key, or focal
part and design the focus first. The focus is the line of code
that achieves the goal of the plan (Rist, 1989). In the deposit
system, this is the line of code that updates the balance and
makes the deposit, so that line may be the first part of the solution
to be identified and design then occurs from that line through
its linked nodes. In the design of an ATM system, the focus is
the customer interaction (login, select, and use), so design may
begin with that part of the system.
At the end of a design episode, a designer may choose to retain
the current node and vary the search strategy. Consider an initial
design strategy of forward, top-down, goal-based design. The designer
starts with the first action for the goal's plan, follows the
control flow right to the last action, and then has to decide
on what to do next. At this point, the designer is located at
the last (rightmost) class for this goal, and may decide to code
the attributes and the header for that class instead of starting
the next goal. In this case the current node acts as a pivot,
and the design strategy changes from top-down goal-based to backward
class-based design.
Design is basically active, local, and opportunistic, so novice
design shows this pattern. Truly expert design is dominated by
the retrieval of known solutions and their systematic expansion.
Most programmers lie between these two extremes, and a novice
can show expert behaviour on a very simple problem, an expert
can show novice behaviour on a complex or unfamiliar problem.
Program design has been described as serendipitous (Guindon, Krasner,
and Curtis, 1987) or opportunistic (Davies, 1993; Ormerod and
Ball, 1993; Visser, 1990) and this paper strongly supports such
a model. The paper goes beyond those accounts of general behaviour
by stating when and how such behaviour occurs. Design is situated,
so at any cognitive location (node) there are links to other nodes:
data, control, linear, and class links are used here. From a specific
node, a link can be followed opportunistically to add a new part
to the growing solution from that node, and these links are precise
and predictable for any given problem.
The process of design is captured by defining a start node and the direction, level, and link type that is used to add the next node to the evolving solution. The essence of design is situated: from here, there are lots of places to go next. The choice of a place to go defines the link type and direction and thus the search strategy, which in turn defines the order in which nodes are added to the growing solution. While it is a tautology that design must start at some place, the choice of where to start design and what links to pursue from that location is the key to the design of complex systems. One component of expertise is to know a lot of solutions, but another and higher-level skill is to know how to design.
A large study of 36 design protocols was undertaken to discover the common design strategies used for OO design. The study itself is described in this section, and analysed in the following two sections. The analysis is based on 56 hours of protocol data.
The nine subjects in the study were students at three universities.
Five of the subjects wrote in the language Eiffel, and four wrote
in the language C++. None of the subjects were professional programmers
and two had no previous programming experience, so they may all
be labelled as experienced programmers.
Two subjects (E1 and E2) were graduate students learning Eiffel as a first language. Three subjects (E3 to E5) were first-year undergraduate students who had completed one course in Eiffel, and were currently using Eiffel in a software engineering course; they had some procedural experience. The third group (C1 to C5) comprised five subjects in their last year of university. This group had learned four procedural languages on the average, and had completed one course in C++ and a large project in C++.
Each subject designed and coded solutions to four problems. The
first problem was to build a simple graphics system to create,
move and display a square and a triangle. The second problem was
to write a system to calculate the cost of building a house, for
both labour and materials. The third problem was to simulate a
plant nursery in which customers and suppliers could be paid by
cash or by credit, and the last problem asked the designer to
build an ATM system. The specification and focal code for the
bank system are given in Appendix A, as is the specification for
the nursery system.
The problems are grouped into two data flow problems (House and
Nursery) and two control flow problems (Graph and ATM). In the
first group, the data flow "dominates" the problem.
The House problem required a set of complex data calculations
that were executed in a simple order; a functional solution was
ideal for this problem, because no data was ever changed. The
difficult part of the Nursery problem was handling credit transactions;
a credit sale had to be stored as a transaction and the money
transferred four days later. This time delay created the need
to create and store transactions, decrement a day counter, and
transfer the money when the account was due, so handling the data
flow was the hard part of this problem. The remaining two problems
were essentially menu-driven with minimal data flow between nodes,
so mapping out the control flow was the hardest part of the solution.
The problem specifications listed the basic objects in the system
as well as the basic goals, so the subject had the goals and objects
explicitly available. The intent of the study was not to see how
a class is inferred from other descriptions, but to see what part
of a complex problem is selected to begin design, and how the
solution unfolds from that beginning. The basic process of design
consists of linking nodes, and the specifications were written
so as to present all the initial data and allow the designer to
choose where to start design.
Summary information about the four sets of solutions is given
in Table 6. From the solution sizes and times, the problems can
be divided into two groups of two and labelled easy and hard problems.
The first two problems required about 200 lines of code and took
about an hour and a half to solve, so these are comparatively
easy problems. The second two problems required about 300 lines
of code and took about two hours to solve, so they are comparatively
hard problems. While the size of a system does not perfectly predict
its difficulty, the lines of code in a solution is a reasonable
predictor that can be measured. These numbers severely under-estimate
the size of a complete solution, because subjects did not debug
their solutions to produce a complete, working system. The systems
are small by industrial standards, but were a challenge for the
subjects.
Graph House Nursery ATM
Classes 4.9 3.7 4.5 4.9
Routines 11.1 10.4 16.9 14.1
Lines of code 200 183 313 295
Time (mins) 65 95 106 108
Difficulty Easy Easy Hard Hard
Type Control Data Data Control
The number of classes was similar for all problems,. The number of routines per class increased from about three routines per class in the easy problems, to about four per class for the hard problems. The average size of a routine remained constant at about 20 lines of code.
Subjects were given a problem description, and asked to design
and code a solution on paper, in either Eiffel or C++. To try
to capture the raw design process without the constraints imposed
by computer screen entry (Green, 1989), no computer was used in
the study. Subjects were encouraged to speak aloud as they designed,
and a complete record of each session was made on videotape. The
camera was positioned behind the subject so that any written material
could be recorded on tape, and subjects were prompted if they
fell silent for more than about ten seconds. Little prompting
was required after the first session.
Two types of raw data were produced from the study. First, any written material - notes, diagrams, or code - was annotated with its emergence order, to record the generation order of the solution. Second, the audio tape was transcribed and annotated with the emergence order, so that each design episode could be recreated from the annotated verbal and code protocols.
An ideal system structure can be defined and used to analyse
an actual solution, because the actual solution structure is the
same as, or less complex than, the ideal solution. An ideal solution
has all the goal and object structure explicit, where an actual
solution will leave various amounts of this structure implicit.
A solution with no classes or routines has no explicit abstract
structure, yet some mechanism must be found to map the code onto
the abstract nodes in the system structure. The basic tool used
here is to define the focus (Rist, 1989, 1991, in-press-a) of
each node in the ideal solution, find the focus in the actual
protocol, and score the focus as a visit to the node. The focus
is the action in the plan that achieves the goal of the plan,
so it exists even when there is no abstract structure.
Using the focus as a diagnostic anchor in the protocol analysis
overcomes the enormous variability seen in system design. The
focus of the plan defines the most reliable evidence for that
plan; sometimes, the focus is the only part of the plan to appear
in the solution. Abstract structure is added to the essential
plan dependencies, first by the definition of routines and then
by the definition of classes. Given the same plan, different designers
will cut it up in different ways and generate different solution
structures, but the focus of each node will occur in all the structures.
Different plans with different foci can be used by different designers,
but this is a minor problem for two reasons. First, the number
of different plans for a single goal is small, so most designers
will use the same focus for their solution. Second, most of the
variability between solutions is caused by the higher-level structure
of merging, organisation, and encapsulation into routines and
classes (Rist, 1990), and this variability can be ignored by considering
only the focus of each node in the plan.
A design strategy may, or may not, be reflected in the final
solution; a goal-based design strategy, for example, can produce
an object-oriented solution, and a class-based design strategy
may produce a monolithic, procedural solution. A system protocol
captures the design strategies directly, instead of inferring
them from the structure of the final code. This is crucial for
analysis, because enormous variability was seen in the number
and definition of the classes and routines for each problem.
In abstract design, especially abstract verbal design, the names
of the goal and object may be the only evidence that a node was
considered. A design protocol can thus be mapped onto an ideal
solution at the abstract level by identifying the goals and objects
mentioned verbally or used to define the names of routine headers.
A code protocol can be mapped onto an ideal system structure by
identifying the focus of each ideal node and locating that code
in the protocol. Given the system structure, transitions between
nodes are easily identified by finding the link that connects
the current with the next node: data flow, control flow, sequence,
or class encapsulation.
The meaning of top-down design is that a routine is called before the code in the routine exists. Each node can contribute one or zero to the count of top-down design. A single node within a row or column is not scored, because there is nothing to compare it to within the row or column. In the system structure, top-down design corresponds to a left to right order of generation, so the numbers that indicate the emergence order increase from left to right. The rules for scoring top-down design are
1. Count the first (leftmost) node if it is the smallest.
2. Find the next generated node in the row; count it if the transition is to the right.
3. Repeat for all nodes in the row.
4. Repeat for all rows, first to last.
The meaning of forward design is that a line of code that makes some data value is generated before the code that uses that data. In the system structure, this corresponds to a top to bottom order of generation: top nodes are generated before bottom nodes, so the numbers increase top to bottom. The rules for scoring top-down design are
1. Count the first (top) node if it is the smallest.
2. Find the next generated node in the column; count it if the transition is down.
3. Repeat for all nodes in the column.
4. Repeat for all columns, left to right.
The meaning of a search strategy is that all the code within some category is generated in sequence; the category is defined by a goal or an object. In the system structure, this corresponds to a sequential order of generation within a row (goal or role) or within a column (an object). The rules for scoring a design strategy are
1. Score a node if it is part of a sequence in a row (column).
2. Subsequences (jumps within the row or column) are allowed.
3. Repeat for the next row (column).
The total score for a measure for a single system protocol is
the count of actual as a proportion of the possible. The actual
number in the row (column) is counted, the possible number in
a row (column) is counted, and the proportion of actual:possible
is expressed as a decimal value from zero to one.
The reliability of the scoring system was tested by having an
independent rater score the most complex system, the Bank system.
The rater had a degree in computer science. The author defined
the system structure, and the focal code for each node. The rater
was given an instruction sheet, the system structure, the description
(cue) of each node, and the focus of each node, and was asked
to record the order of node generation.
All sources of data - the verbal record, the code record, and
the recreation - were available to the rater. One protocol was
selected at random for the Bank system, and the rater scored that
protocol. Disagreements were then discussed, and the rater scored
the remaining eight protocols. Disagreements were again discussed,
revealing two situations not covered in the single, trial protocol.
First, there was disagreement over when the attributes or routines
in the header were to be scored; a decision was made to score
the first time an attribute or routine was listed. Second, the
rater did not score code to prevent an event, such as preventing
a long-term account being accessed. This can be done in various
ways, such as using a filter or a set of polymorphic routines.
The three situations were added to the instructions, and the recreations
scored using these rules. For the 36 protocols in the study, 281
class header and 811 code nodes were scored; these nodes form
the basic data analyzed in this paper.
The number of nodes scored, and the rater differences for the
eight test systems are shown in Table 7. A node can be omitted,
matched at the wrong time (misplaced), or matched incorrectly
to the code. Apart from slips (missing nodes), the only disagreement
was on the decision to score some nodes as generated during planning
or during coding (misplaced); sometimes it is difficult to draw
this line exactly. The two scorers differed on 17 nodes out of
301; overall agreement was 94%.
Nodes Missing Misplaced Mismatched
Author 297 4 1 -
Rater 293 8 4 -
The high rater agreement indicates the value of scoring a node by its focus. Structural measures such as routine definitions and classes cannot be used, because a routine (class) may not exist in a solution, or it may be merged with other routines (classes). Given the system structure, the focus of each node, and the protocols, the scoring method is virtually automatic.
The remainder of this paper applies the theoretical model to
empirical data. Three design protocols are presented in this section,
to illustrate the main system design strategies encountered: data-based
design, goal-based design, and class-based design. The protocols
demonstrate how the common procedural design strategies play out
in an OO language, and how object-orientation allows an additional
entry into the design process: search within and from the class.
This section presents the protocols and applies the design measures
to quantify the extent of top-down, forward, and goal- or class-based
design in each protocol. The next section statistically analyses
the 36 system design protocols to show the common design strategies
observed in the study, and deviations from each strategy.
A designer may plan some part of the solution mentally, describe
this verbally, write notes or code the solution. These steps may
occur for the whole solution, or be applied to a single part of
the solution. Prior planning is here defined as any planning
that occurs before executable code is written, so it may be mental,
verbal, or written. If there is no evidence of any prior planning,
the appearance order of the code directly reflects the problem
solving behaviour. More strongly, it is assumed that the same
process occurs for system design whether it is reflected in words,
notes on scrap paper, or directly in code.
One protocol for the Nursery problem and two protocols for the Bank problem are given below. Verbal and written evidence for prior planning is given to show the design strategies used during the first passes at design. The code protocols are mapped onto the system structure nodes by noting the focus of each node, and marking when that focus was coded.
The first protocol is the only protocol of the 36 with a large
amount of verbal prior planning, so it provides the best evidence
for early design processes. The protocol is taken from subject
E1, for the Nursery system. The Nursery system simulates a plant
nursery in which plants are bought and sold, for cash or credit.
The system offers a menu in which the choices are to sell trees,
buy trees, display the stock on hand, show all the details for
a single tree, show the capital, start a new day, show the menu
choices and exit the system. For a cash transaction, money is
added to or subtracted from the balance. For a credit transaction,
a record is created and stored in a credit list or in a debit
list, and all transactions are paid in full after four days. Time
is simulated by choosing the new day as a menu option.
The written protocol for the first pass at design is shown in
Figure 3 with the generation order for these notes; the verbal
protocol is barely more detailed than the notes, so it has been
omitted. The subject read the specification and immediately selected
for analysis two aspects of the problem as central: inventory
and accounting (1). The objects for each aspect were then defined:
money (3) and stock (4). A third expansion of these aspects was
then made, to define the types of stock and money: the tree types
(5), then the bank (6), credit sales (7), and debit sales (8).
Further detail was added when the subject noted that the capital
was calculated from these amounts by adding (9) and subtracting
(10).
Inventory and accounting 1
Keep track 2
Money: Bank + Credit sales - Suppliers 3: 6 9 7 10 8
Stock: Treetype 4: 5
customer supplier 11 12
sell buy 13 14
D money immediately D money 15 19 17
four days 20
D stock D
stock 16 18
The subject then defined the remaining obvious objects in the
system with no further discussion. First, the names of the objects
were listed - customers (11) and suppliers (12) - and then their
roles or operations: to sell plants to the customers (13) and
buy them from the suppliers (14). Each object in turn was then
chosen, and its semantics made explicit: they change the money
and stock (verbal only). These operations were added to the notes,
one object at a time, first the customer (15-16) and then the
supplier (17-18). The fact that money was paid immediately or
four days later was added to this solution fragment. The subject
then re-read the problem to find any other information relevant
to these goals for these objects.
This first pass at design shows a clear intent to define and
explore the most important objects and actions in the system.
The pass is divided into three steps. The first step was to select
the most important aspects of the problem from the detail provided
in the specification: inventory and accounting (1) or more specifically
stock and money (3-4). In the second step, each of these aspects
was elaborated to define the types of stock and money (5-8) and
their relationships to each other (9, 10). In the third step,
the remaining objects to change the stock and money were defined
(11, 12), and their roles defined (13-18) and elaborated (19,
20).
From the facts in the specification, the stock and money were
selected as the first parts to explore. The main objects (1-4),
and their goals were first defined: the three types of money that
define the balance of the nursery (6-10), and the way that money
and stock is changed by selling and buying (11-20). The second
pass at design expanded these three parts of the system (sell,
buy, calculate balance) by adding the relevant detail for each
goal. The solution was gradually built around the initial focus
by adding more detail both within a pass, and with each new pass.
The order of node generation in the system structure chart is
shown in Table 8, derived from the verbal protocol and the notes
on scrap paper given above.
The second pass at design elaborated this solution by defining
the money and stock classes and then listing the operations on
these classes, still staying within these three goals. The majority
of time in this pass was spent in tracing the flow of money through
the system, especially the order of events that occur for credit
transactions. These actions were then translated into a set of
objects and operations on these objects, written as a set of notes
rather than formal code. A third pass at design then went through
the goals in the specification in their listed order, checking
that everything important had been considered. The fourth and
last pass at design in the verbal protocol then examined how the
various objects would talk to each other, and tried to define
the exact classes and attributes needed for the system.
Most of the objects defined in these four passes by tracing out
the data flow turn out to be bogus. There is no need for the classes
CUSTOMER or SUPPLIER, because a customer simply
provides input to the system, and all supplies are always provided
as needed. There is a need to keep lists of debit and credit transactions,
but there is no need for three classes of money; the balance is
an attribute of the nursery and the amounts owing and owed are
calculated as needed rather than stored. These extra classes led
to a great deal of confusion when the subject wrote detailed code.
Analysis of the data flow is essential to any system analysis
and design, but it is a poor predictor of the class structure.
The order of code generation is shown on a system structure chart
in Table 9. There is no top, left corner node in this chart because
the class NURSERY inherits a MENU, so they are formally
the same class at run-time. The pattern of code development is
top-down at first, in which the main classes are declared (1,
2, 4, 5) and the top level of control is coded (3, 6-12) using
the order listed in the specification. Attention then turns to
the same data that was the focus of attention in verbal planning:
finding the money due on a new day (13-20), selling plants (21-26),
and buying plants (28-34).
The other goals were then considered in listing order. The code
to display the stock on hand was added (35-37), then the goal
to show a single tree's details was mentioned and the code described
as "same as for the display". The goal to calculate
the capital was then mentioned and the main formula to add the
three values was coded (38); the rest of the code consisted of
a set of (invalid) calls to the new day code that should have
returned these three values but did not. Finally, the goal to
show the choices was mentioned and the code verbally described.
Analysis of this verbal protocol indicates that the first step in design was to define the most important objects and operations: stock and money. These solution foci were then expanded through their data flow, not through the control flow or object encapsulation. Data flow was thus the primary type of link used in preliminary design. In the next three passes of prior planning, these same goals and their data were elaborated to the detail required for code. In the code protocol, the top-level class and calls were first coded, then each goal was coded in turn. For the code generation, then, the design strategy was a single top-down, class-based episode followed by a series of top-down, goal-based episodes. The first goal chosen for code expansion was not the first goal in the system, however; it was the goal most central in capturing the flow of money through the system, that linked buying and selling to the receipt and payment of money from credit transactions.
The second protocol demonstrates a top-down balanced design strategy.
The initial approach to planning was to start with the ATM menu,
and write down the sequence of actions needed to login to the
system and use an account; this is the focus of the Bank system.
A second pass was then made in which the three main classes were
defined, and their attributes (data) were listed. A third pass
then occurred in prior planning, as the subject wrote a flow chart
for the whole system. This chart placed the main activities (nodes)
of the system in their execution order, with no mention of the
classes. Coding then started by writing down the main program
and the top level routine calls, and the remainder of the system
was coded in procedural or execution order. For this protocol,
four types of design were observed: initial procedural design
for the system focus, then abstract OO design, then abstract procedural
design and finally procedural coding.
The first pass at design traced out the main control flow by
listing the serial order of the menu actions. A diagram of three
boxes connected by arrows was written on paper, as shown in Figure
4. The solution fragment started with the customer input and ended
with the menu presentation, so the customer was selected as the
focus of the system. This linear order of actions fixes the user
interaction by specifying the order of inputs and outputs for
the ATM, so the first cut at design showed forward, procedural
design of the system based on the control flow. The data was explicit
for the first (login) node, but implicit for the other two nodes.
The second pass at design listed the names and attributes of
the three classes BANK, CUSTOMER, and ACCOUNT. The
class was the unit of analysis, so the first class had its name
and attributes defined, then the next class, then the next. The
class headers were written as shown in Figure 5; the C++ code
was written down the page, but is shown here in three columns
from left to right. This second pass shows forward, abstract,
OO design.
class bank class customer class account
{ customer *cus; { char surname [20]; { float balance;
char password [6]; } char sex; float principal;
int userId; int period; }
char password [6];
account savings,
term,
cheque; }
The third pass at design consisted of a flowchart for the whole
system, showing three loops: a loop around customers, a loop around
accounts, and a loop around the actions on an account. The control
flow to exit the customer loop by entering a special userId was
also shown, leading to a box to add interest. This third pass
showed forward, abstract, procedural design around the focus of
the system, the menu and its actions.
Code was generated in a fourth pass using the balanced, top-down procedural strategy shown in Table 10. The class headers (name and attributes) were first declared (1-6); only three classes were explicitly defined in this solution. The first executable code was a routine call to read in the bank data (7) and the control loop to read and test input ids; code was not defined to read and test the system password, even though the variable "password" had been declared in the bank's header code. Routine calls to process customers (8), handle the interest (9), and save the data (10) were then added.
The code to read and test a customer's password was then added
(11, 12) and the exported routines from the class were defined
(13). The menu choice was then read in (14), and a set of tests
(15-19) and routine calls were coded for each choice. The exported
attributes for class ACCOUNT (20) and class BANK
(21) were then listed, and customer processing was completed by
calling routines to add interest to the customer's accounts (22).
The code to implement each menu choice was then defined (23-27)
in class ACCOUNT, as was the code to add interest (28).
The code generation order shows a systematic, top-down visiting
order for the system structure nodes. First the top level routine
calls were coded, then the next level, then a third level. Each
level corresponds to a class, respectively BANK, CUSTOMER,
and ACCOUNT, so the pattern of code generation was also
class-based, one class at a time. This top-down approach had two
consequences. First, only the top level routine calls were coded
to retrieve and store the data; no code was added later to implement
these calls. Second, every account was treated the same, except
that it was impossible to transfer money into a long-term savings
account. Separate account classes were not defined, and the different
rules for each class were forgotten or ignored. Again, the goal
to process a mature long-term account was omitted. These results
cannot be attributed to ignorance; rather, they seem to be natural
consequences of the top-down, procedural design strategy in which
general knowledge instead of the specification was used to define
the accounts.
The code to save and retrieve the data and to transfer a mature
account were omitted. The first two goals are crucial to the banking
system, and the third provides the whole reason to have a long-term
account. The subject wrote code to add interest to a long-term
account, and while doing so incremented a day counter, but the
counter was never used. These three omissions highlight the fact
that some parts of a system are important to the designer, and
some are not; the omitted goals were not important cognitively.
Every part of a computer system is equally important to the computer,
but not to the designer; the designer builds a system around its
focus. The focus of the banking system is the menu, and the goals
in the menu are to deposit, withdraw, show, transfer, and add
interest to an account. These goals were considered all the way
from the initial design to the detailed system, and the other
goals slipped out of the picture. Once the top level design was
specified, it set the context for further system design by defining
the questions to be asked during design.
Four design passes were observed in this protocol: procedural, OO, procedural, and OO. The first pass generated the global procedural structure of the system: login, choose an account, and choose an action. The second pass generated the global class structure and the class attributes; no mention was made of the goals. The third pass added the looping structure and more details to the existing procedural structure, and marked the end of prior planning. The last pass generated the code in a balanced, top-down order, one class at a time; this pattern of transitions in the code generation is described equally well as top-down OO design, or as top-down, balanced procedural design.
The final protocol demonstrates a fairly systematic, bottom-up
OO design strategy. The subject was at this time completing a
course in software engineering using Eiffel, so at this point
had had two semesters of Eiffel instruction. There were three
passes at design in this protocol. The first pass roughed out
the class structure by listing the three main classes and their
behaviour. The second pass traced out the main control flow in
the system. The last pass generated code for the complete system,
with a deviation for higher-level planning: a small amount of
code was generated for class ACCOUNT, coding stopped to
define the inheritance structure of the accounts, and then the
rest of the code was generated one class at a time, in largely
a bottom-up order. The three passes can thus be labelled as top-down
OO design, procedural design, and bottom-up OO design and coding.
"We've got bank (1), customer (2), and account
(3). Now account you can ... deposit (4), withdraw (5) (6) (7),
and increment daily interest (8), OK. Access account (9), interest
(10), OK"
1 BANK 2 CUSTOMER 3 ACCOUNT
9 access 4 deposit
10 interest 5 withdraw
6 show
7 transfer
8 interest
The first pass at design created the three main classes and their
behaviour; the notes made by the subject and their generation
order are shown above. Again, the header category (name, then
routines) was the primary key used to scan the specification,
and the object was the secondary key. The class names were generated
in client or calling order (BANK, CUSTOMER, and
then ACCOUNT), then the behaviours were added backward
from the end of that pass, first class ACCOUNT and then
class CUSTOMER.
The second pass over the solution was based on the control flow.
The verbal protocol is given below; nothing was written during
this pass. Again, the control flow was examined for the focus
of the system only, starting with the customer login and ending
with the menu selection. For the subject, this was clearly the
part of the solution that needed to be examined and fixed first
to provide a framework for the rest of the solution design.
"OK, flow of control ... Customer enters password,
and then control is passed to the customer object. Now when the
customer actually wants to access the account, is the control
transferred to the account or does the user interaction for selection
of account options take place in customer? I think it would take
place in accounts, in the lowest possible level."
The third pass at design started with the class ACCOUNT;
the generation order for this part of the system is shown to the
left of Figure 6. The account class name (1), behaviour (2) and
attributes (3) were listed, then the routine to add interest was
coded (4); this is actually the wrong location for this routine,
because not all accounts accrue interest. The subject then started
a display routine in class ACCOUNT, realized that not all
accounts can be displayed (a long-term account cannot be accessed
via the menu) and defined a new class SIGHT (5, 6) and a display
routine in class ACCOUNT (7), that was immediately scratched
out.
At this point, the subject decided to step back from coding to
work out the behaviour of each class, by specifying an inheritance
structure. The structure is shown to the right of Figure 5, and
was written from the top down: ACCOUNT, LONG, SIGHT,
SHORT, and CHEQUE. No mention was made of the attributes
or behaviour of these classes. The class header (8) and behaviour
(9) for a long-term account was then coded, and the three types
of long-term account were added to the inheritance diagram.
The rest of the system was then coded with little discussion,
as shown in Table 11. The attributes (principal and period) were
defined for a long-term account (10) and the account creation
routine was defined (11). The three types of long-term account
were then coded (not shown) to contain a single creation routine
to set the specific period and interest rate, and the interest
routine for a long-term account was added (12). A long-term account
cannot be accessed through the menu, so the designer coded a routine
called "interact" (13) that simply replied "No"
for the long-term account, and contained the menu system for the
interactive accounts (SHORT and CHEQUE).
Attention then moved to the interactive accounts, and a set of
routines were defined for class SIGHT: the interest routine
(14), then the deposit (15), display (16), and transfer (17) routines.
The class header, exported routines, and the withdrawal routine
were then defined for class CHEQUE (18-20) and for class
SHORT (21-23). At this point, all the behaviour for all
the accounts was defined. The complete code for class CUSTOMER
(24-36) and for class BANK (37-44) was then added to complete
the system.
In the third pass at design, the code was generated one class at a time, roughly from right to left in the system structure. The interest and display routines for an account were generated first, but the subject realized that the code was located in the wrong class and stopped coding to define the account inheritance hierarchy. The code for the various types of account was then generated, in the order LONG, 3MONTH, 6MONTH, 12MONTH, SIGHT, CHEQUE, and SHORT. The code for the class CUSTOMER was then added, and finally the top-level BANK routines.
The basic design strategy revealed by the pattern of transitions in Table 6 is bottom-up, class-based design. This approach to design generated the most complex solution for the Bank system, because the subject made almost all of the implicit class structure explicit. The subject showed three passes at design, that may be labelled top-down class, focal procedural, and bottom-up class design. Again, the goals to process a mature long-term account and to retrieve and save the data to file were omitted from the solution.
Three common system design strategies were illustrated in the
protocols: data-based design, top-down design, and object-based
design. Three main types of link were pursued in tracing out the
structure of a system: data flow, control flow, and object encapsulation.
In the verbal protocol, data flow was the primary link that was
traced, then the detailed control flow and class structure were
added in code design. Because the system classes were suggested
on the basis of data flow, many of the classes generated during
verbal planing did not fit into the eventual solution. In the
other two protocols, a series of passes over the solution were
made to trace out the procedural structure and the class structure
separately.
Measures of top-down, forward, OO and goal-based design for the
three code protocols are shown in Table 12. The numbers indicate
the amount of each type of design shown in the protocol; a value
of one indicates pure design on that measure and a value of zero
indicates no use of that design strategy. The measures have been
counted separately for the class header (name, attributes, and
routines) and for the code (nodes in the system structure), because
the header and code generation strategies were often different.
Forward Down OO Goal
E1 Nursery Header 1.00 1.00 1.00 0.00
Nodes 0.85 0.90 0.33 0.74
C2 Bank Header 1.00 0.78 0.67 0.22
Nodes 1.00 0.87 0.88 0.14
E3 Bank Header 0.82 0.29 1.00 0.29
Nodes 0.72 0.11 0.74 0.08
All protocols showed strong (> 0.67) forward design for header
and code generation. The first two protocols showed strong top-down
design for both header and code generation, but the last protocol
showed strong bottom-up design for both. All the protocols showed
strong OO design for the header generation. For the code generation,
however, two protocols showed strong class-based and two showed
strong goal-based generation. The patterns of transitions in the
protocols, and the reflection of these patterns in the strategy
counts, show that there were three types of code generation. The
code for the first system showed a single pass to define the top
level of control, followed by goal-based generation of code. The
second system showed top-down, class-based design, and the last
system showed bottom-up class-based design. No subject showed
a pure design strategy (direction, level, and link type) to build
the system, and there was only one example of a pure code generation
strategy on a single dimension: subject C2 showed pure forward
design.
No protocol showed a completely systematic design strategy. Instead, a main design strategy was pursued with deviations to add supporting code backward from the current node. The locations used to start design were the first actions, the focal actions, and the most basic class. The link types were data flow, control flow, and class encapsulation. The direction of design was primarily forward, with exceptions for focal and backward design.
Design through each of the three design dimensions is statistically analyzed in this section for the 36 protocols, together with the effects of problem type, problem difficulty, and expertise. The choice of design unit is the goal versus the class, the choice of control flow is top-down versus bottom-up, and the choice of sequence and (roughly) data flow is forward versus backward. The global strategies used to design a solution are reported first to provide an overall picture of design, then the data are examined at increasingly fine levels of detail. Finally, deviations from a main strategy are analyzed and the completeness of the solutions are examined.
The design strategies are shown as total percentages in Table
13, aggregated over the four systems and the nine subjects. From
these global measures, design was generally goal-oriented (one
goal at a time), top-down within a goal and forward between goals.
There was a correlation of -0.96 between the goal and object scores,
so these two strategies account for about 92% of the transitions
between nodes on this dimension. Due to this high correlation,
only the goal measure will be reported in the rest of this section.
Goal Object Top-down Forward
61.7 39.3 64.7 84.0
From these global figures, the main design strategy was forward, procedural design. The code for each goal was generated from the start of the control flow to the last operation for that goal. The plan for each new goal was coded in turn, from the first goal to the last in serial order. The normal novice design strategy was applied to the design of an OO system, but the percentages show that other strategies were also used. On the category dimension, only 7 systems out of 36 showed 100% goal- or class-based design; on the top-down dimension, only 9 systems showed 100% top-down or bottom-up design; and on the forward dimension, only 9 systems showed 100% forward design. No system showed 100% consistent design on more than a single dimension.
The four problems were divided into two easy (Graph, Bill) and
two hard (Nursery, Bank) groups, based on the length of time taken
to solve them. There was a main effect of problem difficulty for
the headers, F (1, 8) = 10.99, p = 0.01, where increased difficulty
led to an increase in object-oriented class header generation:
for each class, the class name, attributes, and routine names
were generated as a chunk. There were two main effects for the
code generation. For the goal versus object dimension, increased
difficulty led to an increase in goal-oriented generation of code,
F (1, 8) = 6.64, p = 0.03: for each goal, the code in the plan
was generated as a chunk. For the top-down versus bottom-up dimension,
increased difficulty led to an increase in top-down design, F
(1, 8) = 4.82, p = 0.06. Increased difficulty led to an increase
in the class header being coded as a unit, and an increase in
the system code being written for each goal as a unit and top-down
within the goal.
The four problems were divided into two problem types, data flow (Bill, Nursery) and control flow (Graph, Bank); the problems were written to emphasise either data or control flow. There was a main effect of problem type, F (1, 8) = 10.60, p =0.01 on code generation, where the data flow problems showed more backward generation; in backward generation, the code to use a data value is written before the value has been created.
Prior planning occurs before any code is written, and is seen
in the verbal protocols and in notes written on paper. Verbal
protocols are not analysed in this paper, due to interpretation
difficulties. Notes written on paper can be scored with some degree
of accuracy, but no statistics are applied to this data due to
its "soft" nature. Only one subject (E1) showed a large
amount of planning, writing more than the other eight subjects
combined for three of the four problems. The average amounts of
planning before and during coding, as a percentage of written
utterances, are shown in Table 14. The single, careful planner
has been omitted from the averages; that person did most planning
prior to coding, an average of 22.0% of written utterances versus
4.6% for the other eight subjects. The amount of prior planning
generally decreased over the four problems.
Graphic Bill Nursery Bank
Before coding 3.1 8.3 3.1 2.3
During coding 6.7 7.3 1.9 2.4
In their prior planning, subjects made a series of passes over
the problem to make some of the information in the problem explicit
and to structure it. The design notes written before any code
were analyzed for the number of passes, the content of each pass,
and the type of link followed (data or control flow). A summary
of the written prior planning is shown in Tables 17 and 18, for
each problem. Table 15 shows the content of the design notes,
aggregated over the nine subjects. In the first problem, for example,
all nine subjects made a pass over the solution to write the class
names. Only six subjects wrote down the attributes; of these,
only two listed the attributes within each class. Six subjects
also wrote down the goals for the system, but no-one listed the
goals for each class.
Classes Attributes Goals Class x Att Class x Goal
Graph 9 6 6 2 0
Builder 8 4 6 1 4
Nursery 8 4 2 2 4
Bank 6 3 2 2 3
The average number of passes and the type of link used by each
subject to connect the content is shown in Table 16, for the four
problems. The careful planner has been omitted from the number
of passes, and the link type was scored for any pass by the subject.
In the first problem, for example, each subject did roughly two
quick passes over the problem before coding; all the passes followed
the control flow, almost always in a top-down or calling order.
From the table, it may be seen that subjects traced through the
data flow only for the two problems (Builder and Nursery) that
emphasized data flow. It may also be seen that the amount of prior
planning decreased as subjects grew familiar with the task; for
the final problem, two subjects showed no prior planning at all.
Passes Control Data
Graph 1.9 9 0
Builder 2.2 5 5
Nursery 1.2 7 2
Bank 0.9 7 0
Little prior planning was shown in the study. Where it did occur, it usually identified the classes by following the control flow top-down. Although the design notes are less reliable to score than the code protocols, the same pattern was seen in each case: largely top-down design through the control flow, with little integration of knowledge sources.
Over half (60.5%) of the class headers were coded before any
of the executable code; call this batch generation of headers.
There was no effect of problem difficulty, problem type, expertise
or language. Batch generation was the normal strategy for seven
subjects, occurring for 78% of their class headers. For the remaining
two subjects, interleaved generation (for each class, write the
header and the code) was used 100% of the time.
Verbal planning was rich enough to record the generation of header
details for most (28 of the 36) of the protocols. Data indicating
the verbal and code generation strategies for the class headers
is shown in Table 17. Both verbal planning and code generation
showed strong top-down and forward design. The most common verbal
planning strategy was goal-driven across classes, meaning that
the primary design cue was the class name, then the attributes,
then the routines; the classes were varied as a secondary key
within the primary role key. Code generation showed the opposite
pattern of class-based design, so all three header roles for a
single class were typically generated before the next class was
attempted.
Goal Object Top-down Forward
Verbal 51.2 33.5 68.1 96.1
Code 36.1 69.6 65.6 89.2
On the dimension of goal versus class design strategy, there was a significant difference between the verbal and code generation strategies for the headers, F (1, 8) = 5.37, p = 0.05. There were no significant differences on the top-down or forward dimensions.
Individual subjects applied their own preferred design strategy, independent of the problem type or difficulty, the language used, and the training received. To see the pattern of strategies used in the study, the code generation score for each protocol on each dimension was placed into one of three groups: low (< 33.3%), medium (33.3% to 66.6%), and high (> 66.7%). The counts of each group are shown in Table 18, aggregated by subject (left) and by system (middle and right).
Aggregated over the four systems, all the programmers showed
high forward design. Three subjects showed high forward, top-down,
goal-based design; three subjects showed high forward and goal
design, but medium (mixed) top-down design; and three subjects
showed high forward and top-down design, with medium (mixed) goal-based
design.
Looking at the systems individually shows the same pattern, but
more variation. The most common design strategy (for 14/39 or
39% of systems) was forward, top-down, goal-based design. Most
of the systems (23/36 or 64%) showed high forward, and medium
to high top-down, goal-based design. Only eight (22%) systems
showed a high level of class-based design, in which the class
was the basic unit of design and code generation. Of these systems,
half showed class-based and bottom-up design, where the system
was built one class at a time from the most basic class to the
root class; within each class, node generation was still forward
from the first node to the last. Only a single system showed a
strong use of class-based, top-down, forward design. Over the
36 systems, there was a strong (r = .75) correlation between goal-based
and top-down design, but virtually no correlation between goal-based
and forward (r = .023), or forward and top-down (r = .018) design.
The system data were input to a cluster analysis program, and the output of the cluster analysis was examined to convert clusters of systems to clusters of subjects. This analysis revealed four groups of subjects in the study, defined by the interaction between their design strategy and the difficulty of the problem. The four groups and their numbers are shown in Figure 7, where an arrow goes from the scores on the easy problems to those for the hard problems. Scores for forward design were uniformly high and consistent, so they have been omitted from this analysis. There were no effects of language or training.
The strongest group consisted of two subjects with a class-based,
bottom-up design approach that was consistent over the four systems,
shown at the bottom, left of Figure 7. The next most obvious group
consisted of three subjects who adopted a goal-based, top-down
strategy with a small increase in this approach with increased
difficulty; this group is shown at the top, right corner of the
figure. Three other subjects showed the same pattern, but their
shift was so large that they moved from a class-based appraoch
to a goal-based approach. The remaining subject showed a small
reduction in goal-based design with increased difficulty, and
a small increase in top-down design.
There were thus three fairly stable groupings over the study: two groups that used a goal-based, top-down approach, and one that used a class-based, bottom-up approach. The remaining group of three shifted from class-based and top-down to goal-based and top-down design with an increase in problem difficulty.
A strategy shift occurs when the subject starts out by following
some strategy (such as goal-based, top-down, forward design) and
then switches to another strategy. This has been observed in opportunistic
design, where the subject shows a series of consistent decisions,
then deviates from the default strategy to seize an opportunity.
The average number of strategy shifts was two per problem, with
a range from one to seven shifts per problem. Most changes in
strategy were "persistent", where the new strategy was
followed for an extended period of time. There were 73 points
of strategy shift observed in the 36 solution protocols. Only
3 cases (4.1%) showed the pattern of a missing pre-requisite,
where the default strategy was abandoned to create pre-requisite
data. In only 7 cases (9.6%) did the subject resume the default
strategy immediately after the deviation.
The vast majority (62 cases or 85%) of shifts marked a change from goal to class design or vice versa. This usually occurred when a chunk of the solution had been coded and a new part of the solution had to be chosen to continue design. Often (30 cases or 41%), this shift occurred around a pivot node in which one of the pair <goal, object> was retained and the other varied. The second most common repeated pattern (10 cases) was to code the top level of the solution as a chunk (top-down, class-based design), and then code each of the remaining goals as a unit (top-down, goal-based design).
Changes in strategy during design were reported above; this section
examines the initial point chosen to start design. For the computer,
no part of the system is more or less important; they must all
work correctly. During design, however, the important parts of
the system are the foci of the nodes. These form the first part
of the node that is defined in detail, and other sections of code
are added around the focus. Each node in each system should have
been coded nine times, once for each subject. The number of times
each node was generated for the Bank system is shown in Table
19; some protocols had a node in the parent, some had it in the
child class, and some had it (incorrectly) in both places.
The ATM menu and the menu actions were the focus of this system; the system is essentially about providing an interactive service to the customer. Design of the system often started with this part of the problem. These nodes are the only set of nodes included in the solution by all subjects. The code to retrieve the data, to login to the bank, to add interest payments, and to store the data, were all secondary details during the design of the system. The code to transfer funds when a long-term account came due was omitted by almost all subjects, but was the whole point of having a long-term account; however, it had nothing to do with the ATM system. The only way to find this goal was by a careful reading and recall of the specification; this happened for two out of the nine subjects.
To start the design of the class headers, 15 of the protocols
started with the left, corner node in a chart (top-down, forward
design). From the remaining systems, 10 started their header generation
at the second class from the left (the first "real"
class after the root class) and 9 started at the right, top node
(bottom-up, forward design). The remaining two headers were started
with some other class in the middle of the chart. In the initial
design of the system code, 18 of the code protocols started with
the top, left corner (top-down, forward), and three started with
some other top-level node in the first column (top-down). Nine
protocols started with the most basic object (right column); of
these, six started with the first goal (create) for that basic
object (forward, bottom-up) and three started with some other
goal. The remaining six code protocols started at various places
in the middle of the system structure chart.
For both the class headers and code, it seems that forward, top-down, goal-based design was the main strategy and forward, bottom-up, class-based design was the second common strategy. These two strategies account for only two thirds of the starting points for design.
The individual subjects in the study showed a range of design strategies within each solution, but also showed a strong default or preferred strategy. There was little prior planning. The normal strategy was goal-based design, with two variations. The most common design strategy was forward, goal-based design, in which the system was built one goal at a time, from the start of the plan to its end within the goal, and in serial order between the goals. The second most common strategy was to code all the top level routines first to define the goals, then generate the code for each goal in turn, again top-down and forward. A second strategy was class-based, more formally forward, bottom-up, class-based design, in which each class was coded as a unit, from the start to the end within the class, and bottom-up between classes. These individual design strategies were independent of the expertise of the programmer, the training received, and the type of problem. The two main link types used to drive design were thus control flow and class encapsulation; analysis of the data flow may have occurred prior to the other link types, but there was little evidence of this.
This paper has presented a new tool for OO system analysis and design and has applied it to explain the design behaviour observed over 36 system protocols. By using the focus of each node in the system structure as a diagnostic anchor, reliable counts were made for each dimension of a system design strategy: link type (control, sequence, class), level (top-down or bottom-up) and direction (forward or backward). The counts showed that no single design strategy was applied over a complete solution; indeed, it was rare to see systematic design on even a single dimension. Instead, various design strategies were applied at various times to various parts of the solution, as needed.
A design strategy defines a characteristic starting point and
trajectory through the solution structure. Design is massively
redundant, because a link is found and connected at some point
if the design is complete, but the exact point can vary enormously.
A subject could choose to map out the complete data flow before
starting on the control flow. Alternately, a subject could start
with some data flow and then add the control flow just for that
part of the solution. Alternately, a subject could start with
the control flow and add the data flow links to each node as the
focus moves through each node, following the control flow.
A design strategy that fills all links of a single type (such
as data, then control, then object) is called a batch design strategy,
where a strategy that fills all the links in a node, then fills
the next node, and so on, is called an interleaved design strategy.
From the protocols, it seems that the class headers were typically
generated as a batch, then the code and remaining headers were
generated by an interleaved strategy based on following the control
flow and adding the data flow and classes as necessary.
The use of an expert design strategy should increase with expertise,
and decrease with problem difficulty (Rist, 1991). In this study,
increased difficulty led to an increase in goal-based, top-down
design, the opposite of previous results; it is surmised that
top-down design was used here as a means of controlling the complexity
for the harder problems. The effects of expertise could not be
tested in the study, due to the homogeneity of the subjects. Détienne
(in press) has also found that novices tend to generate a system
one goal at a time, paying little attention to the links between
the plan and the objects. They tend to adopt a batch strategy,
where the plans are first generated in isolation, then integrated
into classes in a separate, second pass. This strategy is visible
in the protocols, where the subjects made a series of passes over
their solution, adding structure with each pass. The more expert
subjects in her study favoured a single, integrated pass over
the solution to discover and immediately link the system nodes
as they are found.
The expert OO designers examined by Pennington et al.(in
press) adopted a similar strategy. Those experts spent the first
part of their design period defining goals and then interleaved
the generation of classes and routines to implement those goals;
in terms of the model presented here, there was a goal-based verbal
pass over the problem followed by a class-based generation of
the solution code. In her study, the novices adopted a rigid class-based
approach in which each class was designed in isolation (data,
then class, then methods) and then the classes were combined.
The novices hoped that their classes would be used later, where
the experts generated each class as needed. This pattern of novice
behaviour can be seen in the verbal protocol for the nursery system
here, where three types of money object were generated (cash,
debit, and credit) based on the data flow, but these classes had
little to do with the final system's classes. At the extreme,
expert planning would be almost automatic and thus absent even
from a verbal protocol, so only the integrated, class-based design
strategy would be seen.
The picture of design emerging from this paper is of an active,
local, and opportunistic approach that can start at almost any
location and proceed through any kind of link, in any direction,
at any level. Such a flexible model is required to capture the
enormous range of design strategies observed in these and other
design protocols. Four main strategies were observed in this study.
The most common strategy was forward, goal-based design. The second
most common was a variant of this, in which a first forward abstract
pass defined the top level of control, then each routine was expanded
in turn by forward, goal-based design. The third strategy was
forward, class-based bottom-up design, in which the system was
built one class at a time from the most basic class. The final
strategy observed was forward, goal-based, focal design, in which
a node in the middle of the system was selected to start design,
and a forward, goal-based strategy was applied from there.
A description of the global strategies misses all the fine detail, however. A design episode is defined by a start point and a strategy that generates the system structure from that point. For an expert, this form of systematic design may generate the whole system. For a novice, it is more common to apply a strategy to a small part of the problem, then apply the same or a different strategy to some other part of the problem. In this study, deviations from the dominant strategy were common and not explained by opportunistic design to add a pre-requisite; instead, at the end of each design episode a new strategy was chosen and applied to a large part of the problem.
System structure has been used to teach OO design in Eiffel to
students with no, minimal, or considerable expertise in procedural
programming (Rist, in press-b). The basic teaching approach is
to build a system in three stages: first define the data flow,
then add the control flow, then add the class encapsulation. This
approach uses the normal novice program design strategy as a basis
for the design of OO systems. The text book for the course (Rist,
in-press b; Rist and Terwilliger, 1995) lists 32 explicit design
rules that transform a flat, procedural solution into a set of
classes. Because the Eiffel language is so simple, the course
has to emphasise the range of design decisions and design tradeoffs
that occur during solution generation, and system structure provides
the basic tool to support this. For their assignments, in fact,
students have to hand in a system structure chart for their solution
long before the code is written.
An executable model of program design has been built (Rist, in
press-a) that generates Pascal code from English specifications;
the AI system is called Zippy. The model takes isolated pieces
of knowledge that define the roles, goals, and objects in a solution,
and dynamically combines them to form a plan structure. The non-linear
plan structure is then converted to serial code by a simple process
of constraint propagation on the order of the plan actions. The
model captures the enormous variability that is characteristic
of human program design by defining a start point, a design strategy,
and the knowledge of the designer, and letting these play out
in the particular problem. It would be a large engineering project
to extend this system to produce OO solutions, but the theory
of how to do this is clear: apply the 32 OO design rules to the
underlying plan structure.
It is exciting to think about a programming language that treated
both goals and classes as "first-class" entities. A
functional language encapsulates the goal and its plan as a first
class entity, a function. An OO language encapsulates a set of
data and its operations as a first class entity, the class. There
is a strong interaction between these two perspectives in OO design,
as illustrated by use cases, system structure, or design patterns
(Gamma et al., 1995). Goals and plans are not well captured
in an OO language, but define patterns that can be captured and
re-used. What is needed to do this is the ability to store goals
and classes as entities and combine them as needed. Zippy does
this for small pieces of knowledge, but classes and goal patterns
are much larger entities, that can still be profitably stored
and combined as needed. This approach in turn leads into two exciting
areas. First, the pair <goal, object> can be used to index
a knowledge base, find the required entities, and either return
them to the designer or combine them automatically. Second, a
system or set of systems could be scanned through their plan structures
to identify repeated plans that use the same objects, and the
repetition used to build higher-level entities, either abstract
classes or abstract goals.
The research reported in this paper is important because it applies a detailed cognitive model to show that design can be explained as a process of memory search and linking. The resultant picture of design is both accurate and reliable, and describes OO design in far more detail than other approaches can bring out. The data show that a key part of the problem is selected for analysis and a solution is built up around this focus by adopting a specific design strategy. More importantly, the research presents a new paradigm for system design that can be applied to build tools for code display, analysis, retrieval, and generation.
Adelson, B. & Soloway, E. (1985). The role of domain experience in software design. IEEE Transactions on Software Engineering, 11, 1351-1360.
Berzins, V. (1995). Software merging and slicing. Los Alamitos, CA: IEEE Computer Society Press.
Booch, G. (1991). Object-oriented design. Redwood City, CA: Benjamin/Cummings.
Davies, S. P. (1993). Externalising information during coding activities: effects of expertise, environment, and task. In C. R. Cook, J. C. Scholtz, and J. C. Spohrer (Eds.), Empirical Studies of Programmers: Fifth Workshop, pp. 42-61. Norwood, NJ: Ablex Publishing.
Détienne, F. (1995). Design strategies and knowledge in object-oriented programming: Effects of expertise. To appear in Human-Computer Interaction.
Gamma, E., Helm, R., Johnson, R., & Vlissides, J. (1995). Design patterns. Reading, MA: Addion Wesley.
Green, T. R. G. (1989). Cognitive dimensions of notations. In A. Sutcliffe and L. Macauley (Eds.), People and Computers V. Cambridge: Cambridge University Press.
Guindon, R., Krasner, H. & Curtis, B. (1987). Breakdowns and processes during the early activities of software design by professionals. In G. M. Olson, S. Sheppard & E. Soloway (Eds.), Empirical studies of programmers: Second workshop (pp. 65-82). Norwood, NJ: Ablex.
Horwitz, S., Prins, J., & Reps, T. (1989). Integrating noninterfering versions of programs. ACM trans. on Programming Languages and Systems, 11, 345-387.
Jacobson, I., Christerson, M., Jonsson, P., and Overgaard, G. (1992). Object-oriented software engineering. Reading, MA: Addison-Wesley.
Meyer, B. (1992). Eiffel: The language. Reading, MA: Prentice-Hall.
Norman, D. A. & Bobrow, D. G. (1979). Descriptions: An intermediate stage in memory retrieval. Cognitive Psychology, 11, 107-123.
Ormerod, T. C., & Ball, L. J. (1993). Does programming knowledge or design strategy determine shifts of focus in Prolog programming? In C. R. Cook, J. C. Scholtz, and J. C. Spohrer (Eds.), Empirical Studies of Programmers: Fifth Workshop, pp. 162-186. Norwood, NJ: Ablex Publishing.
Pennington, N. (1987). Stimulus structures and mental representations in expert comprehension of computer programs. Cognitive Psychology, 19, 295-341.
Pennington, N., Lee, Y. A., & Rehder, B. (1995). Cognitive activities and levels of abstraction in procedural and object-oriented design. To appear in Human-Computer Interaction.
Rist, R. S. (1989). Schema creation in programming. Cognitive Science, 13, 389-414.
Rist, R. S. (1990). Variability in program design: the interaction of process with knowledge. Int. J. Man-Machine Studies, 33, 305-322.
Rist, R. S. (1991). Knowledge creation and retrieval in program design: a comparison of novice and experienced programmers. Human-Computer Interaction., 6, 1-46.
Rist, R. S. (1994). Search through multiple representations. In D. J. Gilmore, R. L. Winder, and F. Détienne (Eds.), User-Centred Requirements for Software Engineering Environments, p. 165-176. Berlin: Springer-Verlag.
Rist, R. S. (in press-a). Program structure and design. To appear in Cognitive Science.
Rist, R. S. (in-press-b). Teaching Eiffel as a first language. To appear in the Journal of Object-Oriented Programming.
Rist, R. and Terwilliger, R. (1995). Object-oriented programming in Eiffel. Sydney: Prentice Hall.
Rumbaugh, J, Blaha, M, Premerlani, W., Eddy, F., and Lorensen, W. (1991). Object-oriented modelling and design. New York: Prentice Hall.
Visser, W. (1990). More or less following a plan during design: opportunistic deviations in specification. Int. Journal of Man-Machine Studies, 33, 247-278.
Weiser, M. (1982). Programmers use slices when debugging. Communications of the ACM, 25, 446-452.
Build a banking system that has Automatic Teller Machine (ATM)
access to accounts. A bank officer starts the system each morning,
enters the system password, then leaves the system to run all
day. At any time, a customer may use the system. The customer
enters a unique identification number and a password, and the
account type. The account menu then appears, the customer enters
her choice, and the ATM executes the choice on that account.
The menu choices are deposit, withdraw, check balance, and transfer.
A customer can do as many requests on a single account as she
wishes. When finished, she exits the account menu, and can then
repeat the process for another account; a customer may have up
to three accounts (short-term savings, long-term savings, cheque).
When she is completely finished, she exits back to the main ATM
menu and leaves. The ATM then waits for the next client. At the
end of each day, interest is added to the accounts, the updated
data is stored on file, and the system exits.
Classes
The basic classes are BANK, CUSTOMER, and ACCOUNT. There are
three types of accounts: short-term savings, long-term saving,
and cheque accounts. The savings accounts have different interest
rates; the cheque account gets no interest. Only the bank may
access a long-term account, to add interest. A customer may not
have two accounts of the same type.
A bank has the attributes: a list of customers
a system password: STRING
The initial value of the system password is "feedme".
A customer has attributes: surname: STRING
sex: CHARACTER (M or F)
userId: INTEGER
password: STRING
up to three ACCOUNTs
The userId has four digits. The first two are taken from the current
year (92), the second two are generated by the system in sequence
(9201, 9202, 9203, etc.). Assume that the surname is ² 20
characters, the password is ² 6 characters.
All accounts have a balance: REAL
A long-term account has principal: REAL
period: INTEGER
The types of accounts (SHORT, LONG, CHEQUE) may have additional
attributes specific to that type. Only cheque and savings accounts
can be examined and changed from the ATM. Cheque accounts do not
accrue interest; savings accounts do, but different rules apply
for short and long-term accounts. The balance in any account can
never go below zero.
A short-term savings account can be changed or examined from the
ATM. It accrues interest at a rate of 5.3%, calculated on the
current balance.
A cheque account can be changed or examined from the ATM. It does
not accrue interest. Every withdrawal costs the customer 15 cents,
taken from the account. If there are insufficient funds (the cheque
bounces), then $5 is taken from the account.
A long-term savings account contains a fixed principal that cannot
be changed. The behaviour of a long-term account is this: the
account is created, interest is added each month, then at the
end of the period, the total amount is transferred to the customer's
cheque account. When a customer gets a long-term account, therefore,
she is given a cheque account (with balance zero) if she does
not already have one.
A long-term account can run for 3, 6, or 12 months. The interest
is calculated on the amount of the principal. The table below
shows the basic interest rate per month:
Period of account Basic interest rate
3 months 8.2%
6 months 8.9%
12 months 10.3%
The basic client chart for the system is
Processing
The system reads all necesary details from file when it starts
up, the accounts are examined and updated via the menu, then the
updated accounts are written to file at close of trading. To get
into an account, the system requests a userId; the customer then
enters her userId, password, and the account to be accessed. Any
number of attempts to log in are allowed. The customer is then
presented with a menu showing her choices. She does what she wants
on that account, as many choices as she wants, until she exits
the account menu. She may then choose a new account to use. When
she is tired of dealing with her money, she exits back to the
main ATM menu. The ATM then waits for a new customer userId.
The account menu choices are
D deposit a sum of money
W withdraw
S show balance
T transfer between a customer's accounts
E exit account system
To exit the BANK system, a bank employee goes to the ATM and enters
a special userId, the number 666. Interest is then added to all
accounts (daily), calculated on the monthly rate (assume a month
has 30 days). All accounts are then stored to file, and the system
exits.
Abbreviations
-> x read (x) bal balance
x -> write (x) amt amount
<- x return x No not allowed