Structure and Interpretation of Computer Programs

[Go to first, previous, next page;   contents;   index]

1.2  Procedures and the Processes They Generate

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 defining

them as compound procedures. 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 procedures are worth defining). We lack the experience to predict the

consequences of making a move (executing a procedure).

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 procedures. Only after we have developed such a skill can we

learn to reliably construct programs that exhibit the desired behavior.

A procedure 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 procedure. 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

procedures. We will also investigate the rates at which these processes consume the important

computational resources of time and space. The procedures 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.1  Linear Recursion and Iteration

---

Figure 1.3:  A linear recursive process for computing 6!.

Figure 1.3:  A linear recursive process for computing 6!.

We begin by considering the factorial function, defined by

There are many ways to compute factorials. One way is to make use of the observation that n! is equal

to n times (n - 1)! for any positive integer n:

Thus, we can compute n! by computing (n - 1)! and multiplying the result by n. If we add the

stipulation that 1! is equal to 1, this observation translates directly into a procedure:

(define (factorial n)

  (if (= n 1)

      1

      (* n (factorial (- n 1)))))

We can use the substitution model of section 1.1.5 to watch this procedure in action computing 6!, as

shown in figure 1.3.

Now let’s take a different perspective on computing factorials. We could describe a rule for computing 

n! by specifying that we first multiply 1 by 2, then multiply the result by 3, then by 4, and so on until

we reach n. More formally, we maintain a running product, together with a counter that counts from 1

up to n. We can describe the computation by saying that the counter and the product simultaneously

change from one step to the next according to the rule

product 

 counter · product 

counter 

 counter + 1

and stipulating that n! is the value of the product when the counter exceeds n.

---

Figure 1.4:  A linear iterative process for computing 6!.

Figure 1.4:  A linear iterative process for computing 6!.

Once again, we can recast our description as a procedure for computing factorials:

29

(define (factorial n)

  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)

  (if (> counter max-count)

      product

      (fact-iter (* counter product)

                 (+ counter 1)

                 max-count)))

As before, we can use the substitution model to visualize the process of computing 6!, as shown in 

figure 1.4.

Compare the two processes. From one point of view, they seem hardly different at all. Both compute

the same mathematical function on the same domain, and each requires a number of steps proportional

to n to compute n!. Indeed, both processes even carry out the same sequence of multiplications,

obtaining the same sequence of partial products. On the other hand, when we consider the ‘‘shapes’’ of

the two processes, we find that they evolve quite differently.

Consider the first process. The substitution model reveals a shape of expansion followed by

contraction, indicated by the arrow in figure 1.3. The expansion occurs as the process builds up a chain

of deferred operations (in this case, a chain of multiplications). The contraction occurs as the

operations are actually performed. This type of process, characterized by a chain of deferred

operations, is called a recursive process. Carrying out this process requires that the interpreter keep

track of the operations to be performed later on. In the computation of n!, the length of the chain of

deferred multiplications, and hence the amount of information needed to keep track of it, grows

linearly with n (is proportional to n), just like the number of steps. Such a process is called a linear

recursive process.

By contrast, the second process does not grow and shrink. At each step, all we need to keep track of,

for any n, are the current values of the variables 

product

, 

counter

, and 

max-count

. We call this

an iterative process. In general, an iterative process is one whose state can be summarized by a fixed

number of state variables, together with a fixed rule that describes how the state variables should be

updated as the process moves from state to state and an (optional) end test that specifies conditions

under which the process should terminate. In computing n!, the number of steps required grows

linearly with n. Such a process is called a linear iterative process.

---