We have now considered the elements of programming: We have used
primitive arithmetic operations, we have combined these operations, and
we have abstracted these composite operations by
declaring them as compound functions.
But that is not enough to enable us to say that we know
how to program. Our situation is analogous to that of someone who has
learned the rules for how the pieces move in chess but knows nothing
of typical openings, tactics, or strategy. Like the novice chess
player, we don't yet know the common patterns of usage in the domain.
We lack the knowledge of which moves are worth making
(which functions are worth declaring).
We lack the experience to predict the
consequences of making a move (executing a
The ability to visualize the consequences of the actions under
consideration is crucial to becoming an expert programmer, just as it
is in any synthetic, creative activity. In becoming an expert
photographer, for example, one must learn how to look at a scene and
know how dark each region will appear on a print for each possible
choice of exposure and development
conditions. Only then can one
reason backward, planning framing, lighting, exposure, and development
to obtain the desired effects. So it is with programming, where we
are planning the course of action to be taken by a process and where
we control the process by means of a program. To become experts, we
must learn to visualize the processes generated by various types of
Only after we have developed such a skill can we learn
to reliably construct programs that exhibit the desired behavior.
is a pattern for the local evolution of a
computational process. It specifies how each stage of the process is
built upon the previous stage. We would like to be able to make
statements about the overall, or global, behavior of a
process whose local evolution has been specified by a
This is very difficult to do in general, but we can at least try to
describe some typical patterns of process evolution.
In this section we will examine some common
shapes for processes
generated by simple
We will also investigate the
rates at which these processes consume the important computational
resources of time and space.
we will consider
are very simple. Their role is like that played by test patterns in
photography: as oversimplified prototypical patterns, rather than
practical examples in their own right.
and the Processes They Generate