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 function).
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
processes generated by simple
We will also investigate the rates at which these processes consume the
important computational resources of time and space. The
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.
1.2 Functions and the Processes They Generate