Structure and Interpretation of Computer Programs (45 page)

In a system composed of many objects, the objects are rarely
completely independent. Each may influence the states of others
through interactions, which serve to couple the state variables of one
object to those of other objects. Indeed, the view that a system is
composed of separate objects is most useful when the state variables
of the system can be grouped into closely coupled subsystems that are
only loosely coupled to other subsystems.

This view of a system can be a powerful framework for organizing
computational models of the system. For such a model to be modular,
it should be decomposed into computational objects that model the
actual objects in the system. Each computational object must have its
own
local state variables
describing the actual object's state.
Since the states of objects in the system being modeled change over
time, the state variables of the corresponding computational objects
must also change. If we choose to model the flow of time in the
system by the elapsed time in the computer, then we must have a way to
construct computational objects whose behaviors change as our programs
run. In particular, if we wish to model state variables by ordinary
symbolic names in the programming language, then the language must
provide an
assignment operator
to enable us to change the value
associated with a name.

To illustrate what we mean by having a computational object with
time-varying state, let us model the situation of withdrawing money
from a bank account. We will do this using a procedure
withdraw
, which takes as argument an
amount
to be withdrawn.
If there is enough money in the account to accommodate the withdrawal,
then
withdraw
should return the balance remaining after the
withdrawal. Otherwise,
withdraw
should return the message
Insufficient funds.
For example, if we begin with $100 in the
account, we should obtain the following sequence of responses using
withdraw
:

(withdraw 25)
75
(withdraw 25)
50
(withdraw 60)
"Insufficient funds"
(withdraw 15)
35

Observe that the expression
(withdraw 25)
, evaluated twice,
yields different values. This is a new kind of behavior for a
procedure. Until now, all our procedures could be viewed as
specifications for computing mathematical functions. A call to a
procedure computed the value of the function applied to the given
arguments, and two calls to the same procedure with the
same arguments always produced the same result.
¹

To implement
withdraw
, we can use a variable
balance
to
indicate the balance of money in the account and define
withdraw
as a procedure that accesses
balance
. The
withdraw
procedure checks to see if
balance
is at least as large as the
requested
amount
. If so,
withdraw
decrements
balance
by
amount
and returns the new value of
balance
.
Otherwise,
withdraw
returns the
Insufficient funds
message. Here are the definitions of
balance
and
withdraw
:

(define balance 100)
(define (withdraw amount)
  (if (>= balance amount)
      (begin (set! balance (- balance amount))
             balance)
      "Insufficient funds"))

Decrementing
balance
is accomplished by the expression

(set! balance (- balance amount))

This uses the
set!
special form, whose syntax is

(set! <
name
> <
new-value
>)

Here <
name
> is a symbol and <
new-value
> is any expression.
Set!
changes <
name
> so that its value is the result obtained by
evaluating <
new-value
>. In the case at hand, we are changing
balance
so that its new value will be the result of subtracting
amount
from the previous value of
balance
.
²

Withdraw
also uses the
begin
special form to cause
two expressions to be evaluated
in the case where the
if
test is true: first decrementing
balance
and then returning the value of
balance
. In general,
evaluating the expression

(begin <
exp
₁
> <
exp
₂
> 
...
<
exp
_k
>)

causes the expressions <
exp
₁
> through <
exp
_k
> to be
evaluated in sequence and the value of the final expression
<
exp
_k
> to be returned as the value of the entire
begin
form.
³

Although
withdraw
works as desired, the variable
balance
presents a problem. As specified above,
balance
is a name defined in the global environment and is freely accessible
to be examined or modified by any procedure. It would be much better
if we could somehow make
balance
internal to
withdraw
, so
that
withdraw
would be the only procedure that could access
balance
directly and any other procedure could access
balance
only indirectly (through calls to
withdraw
). This would more
accurately model the notion that
balance
is a local state
variable used by
withdraw
to keep track of the state of the
account.

We can make
balance
internal to
withdraw
by rewriting the
definition as follows:

(define new-withdraw
  (let ((balance 100))
    (lambda (amount)
      (if (>= balance amount)
          (begin (set! balance (- balance amount))
                 balance)
          "Insufficient funds"))))

What we have done here is use
let
to establish an environment
with a local variable
balance
, bound to the initial value 100.
Within this local environment, we use
lambda
to create a
procedure that takes
amount
as an argument and behaves like our
previous
withdraw
procedure. This procedure – returned as the
result of evaluating the
let
expression – is
new-withdraw
,
which behaves in precisely the same way as
withdraw
but whose
variable
balance
is not accessible by any other
procedure.
⁴

Combining
set!
with local variables is the general programming
technique we will use for constructing computational objects with
local state. Unfortunately, using this technique raises a serious
problem: When we first introduced procedures, we also introduced the
substitution model of evaluation
(section 
1.1.5
) to provide an interpretation of
what procedure application means. We said that applying a procedure
should be interpreted as evaluating the body of the procedure with the
formal parameters replaced by their values. The trouble is that, as
soon as we introduce assignment into our language, substitution is no
longer an adequate model of procedure application. (We will see why
this is so in section 
3.1.3
.) As a
consequence, we technically have at this point no way to understand
why the
new-withdraw
procedure behaves as claimed above. In
order to really understand a procedure such as
new-withdraw
, we
will need to develop a new model of procedure application. In
section 
3.2
we will introduce such a model,
together with an explanation of
set!
and local variables.
First, however, we examine some variations on the theme established by
new-withdraw
.

The following procedure,
make-withdraw
, creates “withdrawal
processors.” The formal parameter
balance
in
make-withdraw
specifies the initial amount of money in the
account.
⁵

(define (make-withdraw balance)
  (lambda (amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds")))

Make-withdraw
can be used as follows to create two objects
W1
and
W2
:

(define W1 (make-withdraw 100))
(define W2 (make-withdraw 100))
(W1 50)
50
(W2 70)
30
(W2 40)
"Insufficient funds"
(W1 40)
10

Observe that
W1
and
W2
are completely independent objects,
each with its own local state variable
balance
. Withdrawals
from one do not affect the other.

We can also create objects that handle deposits as well as
withdrawals, and thus we can represent simple bank accounts. Here is
a procedure that returns a “bank-account object” with
a specified initial balance:

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (dispatch m)
    (cond ((eq? m 'withdraw) withdraw)
          ((eq? m 'deposit) deposit)
          (else (error "Unknown request -- MAKE-ACCOUNT"
                       m))))
  dispatch)

Each call to
make-account
sets up an environment with a local
state variable
balance
. Within this environment,
make-account
defines procedures
deposit
and
withdraw
that access
balance
and an additional procedure
dispatch
that takes a “message” as input and returns one of the two local
procedures. The
dispatch
procedure itself is returned as the
value that represents the bank-account object.
This is precisely the
message-passing
style of programming that we saw in section 
2.4.3
, although
here we are using it in conjunction with the ability to modify local
variables.

Make-account
can be used as follows:

(define acc (make-account 100))
((acc 'withdraw) 50)
50
((acc 'withdraw) 60)
"Insufficient funds"
((acc 'deposit) 40)
90
((acc 'withdraw) 60)
30

Each call to
acc
returns the locally defined
deposit
or
withdraw
procedure, which is then applied to the specified
amount
. As was the case with
make-withdraw
, another call to
make-account

(define acc2 (make-account 100))

will produce a completely separate account object, which maintains its
own local
balance
.

Exercise 3.1.
  An
accumulator
is a procedure that is called repeatedly with a
single numeric argument and accumulates its arguments into a sum.
Each time it is called, it returns the currently accumulated sum.
Write a procedure
make-accumulator
that generates accumulators,
each maintaining an independent sum. The input to
make-accumulator
should specify the initial value of the sum; for
example

(define A (make-accumulator 5))
(A 10)
15
(A 10)
25

Exercise 3.2.
  In software-testing applications, it is useful to be able to count the
number of times a given procedure is called during the course of a
computation. Write a procedure
make-monitored
that takes as
input a procedure,
f
, that itself takes one input. The result
returned by
make-monitored
is a third procedure, say
mf
,
that keeps track of the number of times it has been called by
maintaining an internal counter. If the input to
mf
is the
special symbol
how-many-calls?
, then
mf
returns the
value of the counter. If the input is the special symbol
reset-count
, then
mf
resets the counter to zero. For any other
input,
mf
returns the result of calling
f
on that input
and increments the counter. For instance, we could make a monitored
version of the
sqrt
procedure:

(define s (make-monitored sqrt))
(s 100)
10
(s 'how-many-calls?)
1

Exercise 3.3.
  
Modify the
make-account
procedure so that it creates
password-protected accounts. That is,
make-account
should take
a symbol as an additional argument, as in

(define acc (make-account 100 'secret-password))

The resulting account object should process a request only if it is
accompanied by the password with which the account was created, and
should otherwise return a complaint:

((acc 'secret-password 'withdraw) 40)
60
((acc 'some-other-password 'deposit) 50)
"Incorrect password"

Exercise 3.4.
  Modify the
make-account
procedure of
exercise 
3.3
by adding another local state
variable so that, if an account is accessed more than seven
consecutive times with an incorrect password, it invokes the procedure
call-the-cops
.