adrianwong programmer · retired coal miner

SICP section 3.1 - assignment and local state

Selected exercises

Exercise 3.01

(define (make-accumulator initial)
  (lambda (x)
    (set! initial (+ initial x))
    initial))

Tests:

(define A (make-accumulator 5))
(define B (make-accumulator 10))

(A 10) ; 15
(A 10) ; 25

(B 10) ; 20
(B 10) ; 30

Exercise 3.02

(define (make-monitored f)
  (let ((count 0))
    (define (mf m)
      (cond ((eq? m 'how-many-calls?) count)
            ((eq? m 'reset-count) (set! count 0))
            (else (begin (set! count (+ count 1))
                         (f m)))))
    mf))

Tests:

(define monitored-sqrt (make-monitored sqrt))

(monitored-sqrt 100)
(monitored-sqrt 81)
(monitored-sqrt 'how-many-calls?) ; 2

(monitored-sqrt 64)
(monitored-sqrt 'how-many-calls?) ; 3

(monitored-sqrt 'reset-count)

(monitored-sqrt 49)
(monitored-sqrt 'how-many-calls?) ; 1

Exercise 3.03

Given the procedure make-account:

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

…we have to modify it so it creates password-protected accounts:

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

Exercise 3.04

We have to modify make-account yet again, so that it invokes the procedure call-the-cops if an account is accessed more than seven consecutive times with an incorrect password. A bit excessive if you ask me, but perhaps those were darker times…

(define (make-account balance password)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (calling-the-cops amount)
    "Calling the cops!")
  (let ((attempts 0))
    (define (dispatch p m)
      (if (eq? p password)
          (begin (set! attempts 0)
                 (cond ((eq? m 'withdraw) withdraw)
                       ((eq? m 'deposit) deposit)
                       (else (error "Unknown request: MAKE-ACCOUNT"
                                    m))))
          (begin (set! attempts (+ attempts 1))
                 (if (> attempts 7)
                     calling-the-cops
                     (lambda (amount) "Incorrect password")))))
    dispatch))

Tests:

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

((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #1
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #2
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #3
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #4
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #5
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #6
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #7

((acc 'secret-password 'deposit) 50)     ; 150

((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #1
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #2
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #3
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #4
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #5
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #6
((acc 'some-other-password 'deposit) 50) ; "Incorrect password" #7
((acc 'some-other-password 'deposit) 50) ; "Calling the cops!"

Exercise 3.05

This was a fun one, mainly due to my never having considered that \(\pi\) could be estimated in such a fashion. The gist of it is:

  1. Create a circle \(C\) centered at \((x_1, y_1)\) with a radius \(r\).
  2. Select a rectangle \(R\) with width \(w\) and height \(h\) large enough to contain \(C\).
  3. Pick a random point within \(R\). Does this point also fall within \(C\)?
  4. Repeat #3 as many times as desired. The fraction of points that fall within \(C\) is an estimate of the proportion of \(C\) to \(R\). With this, we can estimate the area of \(C\), which allows us to estimate the value of \(\pi\):
$$\begin{align*} area_C &\approx area_R * \frac{points_C}{points_R} \\ \pi{r^2} &\approx w * h * \frac{points_C}{points_R} \\ \pi &\approx \frac{1}{r^2} * w * h * \frac{points_C}{points_R} \end{align*}$$

Time to translate this into code. Given:

(define (random-in-range low high)
  (let ((range (- high low)))
    (+ low (random range))))

(define (monte-carlo trials experiment)
  (define (iter trials-remaining trials-passed)
    (cond ((= trials-remaining 0)
           (/ trials-passed trials))
          ((experiment)
           (iter (- trials-remaining 1)
                 (+ trials-passed 1)))
          (else
           (iter (- trials-remaining 1)
                 trials-passed))))
  (iter trials 0))

…we can implement the estimate-integral procedure:

(define (square n) (* n n))

(define (P xc yc radius)
  (lambda (x y) (<= (+ (square (- x xc))
                       (square (- y yc)))
                    (square radius))))

(define (estimate-integral P x1 x2 y1 y2 trials)
  (define (experiment)
    (let ((x (random-in-range (exact->inexact x1)
                              (exact->inexact x2)))
          (y (random-in-range (exact->inexact y1)
                              (exact->inexact y2))))
      (P x y)))
  (* (* (- x2 x1) (- y2 y1))
     (monte-carlo trials experiment)))

Using estimate-integral to produce an estimate of \(\pi\):

(exact->inexact (/ (estimate-integral (P 5 7 3) 2 8 4 10 1000000)
                   (square 3)))
; ~3.142

Exercise 3.06

(define random-init 0)

(define rand-update inc)

(define rand
  (let ((x random-init))
    (lambda (symbol)
      (cond ((eq? symbol 'generate)
             (set! x (rand-update x))
             x)
            ((eq? symbol 'reset)
             (lambda (new-value)
               (set! x new-value)
               x))
            (else (error "Unknown request: RAND"
                         symbol))))))

Note: all rand-update does is return its argument’s value, incremented by 1.

Tests:

(rand 'generate)   ; 1
(rand 'generate)   ; 2
(rand 'generate)   ; 3

((rand 'reset) 42) ; 42

(rand 'generate)   ; 43
(rand 'generate)   ; 44
(rand 'generate)   ; 45

Exercise 3.07

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

(define (make-joint account password extra-password)
  ((account password 'make-joint) extra-password))

The approach I’ve taken is to modify dispatch so it takes a password argument and returns a two-argument lambda that closes over password. This lambda is returned when we call make-account or dispatch to make-joint on an existing account object.

Tests:

(define peter-acc (make-account 100 'open-sesame))
(define paul-acc (make-joint peter-acc 'open-sesame 'rosebud))

((peter-acc 'open-sesame 'withdraw) 15) ; 85
((paul-acc 'rosebud 'withdraw) 15)      ; 70
((peter-acc 'open-sesame 'withdraw) 15) ; 55

; Attempt withdrawals with each other's passwords
((peter-acc 'rosebud 'withdraw) 10)     ; "Incorrect password"
((paul-acc 'open-sesame 'withdraw) 10)  ; "Incorrect password"

Exercise 3.08

(define f
  (let ((n 1))
    (lambda (x) (set! n (* n x)) n)))

Tests:

; "Left to right"
(f 0) ; 0
(f 1) ; 0

; "Right to left"
(f 1) ; 1
(f 0) ; 0