next up previous contents
Next: The Benefits of Introducing Up: Assignment and Local State Previous: Assignment and Local State

   
Local State Variables

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 exp1 exp2 ... expk)
causes the expressions exp1 through expk to be evaluated in sequence and the value of the final expression expk 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 [*]) 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 [*].) 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 [*] 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 [*], 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. 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. 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. 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. Modify the make-account procedure of exercise [*] 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.


next up previous contents
Next: The Benefits of Introducing Up: Assignment and Local State Previous: Assignment and Local State
Ryan Bender
2000-04-17