Home > Notes > Books > Notes and Solutions from Structure and Interpretation of Computer Programs

3.1 Assignment and Local State

View the world as populated by objects with state that changes over time. An object has state if behavior is influenced by history (e.g. bank account). State is characterized by state variables (e.g. current balance).

Objects are rarely completely independent.

The model should be decomposed into computational objects modeling actual objects. Each computational object has local state variables. If we model time by the elapsed time of the computer, we need to construct computational objects with behavior that changes as the program runs. If we want to model state variables by ordinary symbolic names, the language must provide an assignment operator, to change the value associated with a name.

3.1.1 Local State Variables

Ex. withdrawing moeny from a bank account:

(withdraw 25)
; => 75

(withdraw 25)
; => 50

(withdraw 60)
; => "Insufficient funds"

(withdraw 15)
; => 35

The expression (withdraw 25) yields different values at different times. This is a new kind of behavior. Until now, all procedures were specifications for mathematical functions. Two calls with the same args always produced the same result.

To implement:

#lang sicp
(define balance 100)

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

This uses the special form set!:

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

Where name is a symbol and new-value is any expression.

It also uses the begin special form to cause two expressions to be evaluated, first decrementing balance, then returning the value of balance.

This works but a problem is anyone can access balance. Better if we could make it internal somehow to withdraw, and any other procedure has to go through withdrawl to access it:

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

Now we use let to establish a local environment with variable balance. We use lambda to create a procedure that takes arg amount and behaves like the previous.

But this introduces a problem: when we introduced procedures, said that applying a proc should be interpreted as evaluateing the body with the formal params replaced by their values. But this is no longer an adequate model. We don't have a way to understand why this performs as claimed. Need a new model of procedure application. This comes in 3.2, but first some variations on the theme:

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

(define W1 (make-withdraw 100))
(define W2 (make-withdraw 100))

(W1 50)
; => 50

(W2 70)
; => 30

(W2 40)
; => "Insufficent funds"

(W1 40)
; => 10

We've created two completely independent objects with local state.

(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)

(define acc (make-account 100))

((acc 'withdraw) 50)
; => 50

((acc 'withdraw) 60)
; => "Insufficient funds"

((acc 'deposit) 40)
; => 90

((acc 'withdraw) 60)
; => 30

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 current 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

Solution

#lang sicp

(define (make-accumulator sum)
  (lambda (accumulate)
    (begin (set! sum (+ sum accumulate))
           sum)))

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 thread 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 verion of the sqrt procedure:

(define s (make-monitored sqrt))

(s 100)
; => 10

(s 'how-many-calls?)
; => 1

Solution

Previous