Theories of Programming: Top-Down and Bottom-Up and Meeting in the Middle - Correct System Design: Recent Insights and Advances - page 2

at the top with a study of the most general kind of mathematical structure, as
exemplied by the category of sets. They then work downward to dene and
classify the canonical properties that distinguish more particular example struc-
tures from each other. Logicians on the other hand start from the bottom. They
search for a minimal set of primitive concepts and notations to serve as a foun-
dation for all of mathematics, and a minimal collection of atomic steps to dene
the concept of a valid proof. They then work methodically upward, to dene all
the more familiar concepts of mathematics in terms of the primitives, and to
justify the larger proof steps which mathematicians need for ecient prosecu-
tion of their work. Fortunately in this case too, the top-down and the bottom-up
styles of investigation both seek a common explanation of the internal structure
of mathematics and clarication of the relationship between its many branches.
Their ultimate goal is to extend the unreasonable power of mathematical cal-
culation and make it more accessible to the experimental scientist and to the
practicing engineer.
Computer science, like other branches of science, has as its goal the under-
standing of highly complex phenomena, the behaviour of computers and the
software that controls them. Simple algorithms, like Euclid's method of nd-
ing the greatest common divisor, are already complex enough; a challenge on a
larger scale is to understand the potential behaviour of the million-fold inter-
linked operating systems of the world-wide computing network. As in physics
or in mathematics, the investigation of such a system may proceed in a choice
of directions, from the top-down or from the bottom-up. In the following ex-
position, this dichotomy will be starkly exaggerated. In any particular scientic
investigation, or on any particular engineering project, there will be a rapid al-
ternation or mixture of the two approaches, often starting in the middle and
working outward. A recommendation to this eect is made in the conclusion of
the paper.
An investigation from the top-down starts with an attempt to understand the
system as a whole. Since software is a man-made artifact, it is always relevant
to ask rst what is its purpose? Why was it built? Who is it for? What are
the requirements of its users, and how are they served? The next step is to
identify the major components of the system, and ask how they are put together?
How do they interact with each other? What are the protocols and conventions
governing their collaboration? How are the conventions enforced, and how does
their observance ensure successful achievement of the goals of the system as a
whole?
A top-down theory of programming therefore starts by modelling external
aspects of the behaviour of a system, such as might be observed by its user.
A meaningful name is given to each observation or measurement, so that the
intended behaviour of the system can be described briefly and clearly, perhaps
in a user manual for a product, or perhaps even in a specication agreed with
the user prior to implementation. The set of observations is extended to in-
clude concepts needed to describe the internal interfaces between components
of the system. The goal of the theory is to predict the behaviour of a complex