Information Technology Reference
In-Depth Information
Theories of Programming:
Top-Down and Bottom-Up and Meeting in the
Middle
C.A.R. Hoare
Oxford University Computing Laboratory,
Wolfson Building, Parks Road, Oxford, OX1 3QD
tony.hoare@comlab.ox.ac.uk
Abstract.
A theory of programming provides a scientic basis for pro-
gramming practices that lead to predictable delivery of programs of high
quality. A top-down theory starts with a specication of the intended
behaviour of a program; and a bottom-up theory starts with a descrip-
tion of how the program is executed. The aim of both theories is to prove
theorems (often algebraic laws) that will be helpful in the design, devel-
opment, compilation,testing,optimisation and maintainance of all kinds
of program. The most mature theories are those that are presented both
in bottom-up and top-down fashion, where essentially the same laws are
valid in both presentations.
1
Introduction
The goal of scientic research is to develop an understanding of the complex-
ity of the world which surrounds us. There is certainly enough complexity out
there to justify a wide range of specialist branches of science; and within each
branch to require a wide range of investigatory styles and techniques. For ex-
ample, among the specialists in Physics, cosmologists start their speculations in
the vast distances of intergalactic space, and encompass the vast time-scales of
the evolution of the stars. They work methodically downward in scale, until they
nd an explanation of phenomena that can be observed more or less directly by
the naked eye. At the other end of the scale, particle physicists start with the
primitive components of the material world, currently postulated to be quarks
and gluons. They then work methodically upward in scale, to study the compo-
sition of baryons, hadrons, and leptons, clarifying the laws which govern their
assembly into atoms and molecules. Eventually, they can explain the properties
of materials that we touch and smell and taste in the world of every day. In spite
of the dierence in scale of their starting points, and in the direction and style
of their investigations, there is increasing excitement about the convergence and
overlap of theories developed by cosmologists and by particle physicists. The
point at which they converge is the most signicant event in the whole history
of the universe, the big bang with which it all started.
The same dichotomy between top-down and bottom-up styles of investiga-
tion may be found among mathematicians. For example, category theorists start
