CprS376 Schedule
CprS376 Class 10
CprS376 Class 12

Assignment and Local State

Class 11 - Section 3.1



Contents

Accounts
;; accounts.ss

;; SICP source code

;;;SECTION 3.1.1

;: (withdraw 25)
;: (withdraw 25)
;: (withdraw 60)
;: (withdraw 15)

(define balance 100)

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


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


(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)
;: (W2 70)
;: (W2 40)
;: (W1 40)


(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)
;: ((acc 'withdraw) 60)
;: ((acc 'deposit) 40)
;: ((acc 'withdraw) 60)

;: (define acc2 (make-account 100))


;; EXERCISE 3.1
;: (define A (make-accumulator 5))
;: (A 10)
;: (A 10)


;; EXERCISE 3.2
;: (define s (make-monitored sqrt))
;: (s 100)
;: (s 'how-many-calls?)


;; EXERCISE 3.3
;: (define acc (make-account 100 'secret-password))
;: ((acc 'secret-password 'withdraw) 40)
;: ((acc 'some-other-password 'deposit) 50)

Accounts Transcript


;; accounts.transcript


;; accounts.transcript

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;;  SICP section 3.1.1 -- local state variables
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;; computational objects with local state

; First, try using a global variable

(define balance 100)

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

; testing

balance
; => 100

(withdraw 25)
; => 75

(withdraw 25)
; => 50

(withdraw 60)
; => "insufficient funds"

(withdraw 15)
; => 35

; Would be better to encapsulate the variable within the procedure

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

; testing

(new-withdraw 25)
; => 75

(new-withdraw 25)
; => 50

(new-withdraw 60)
; => "insufficient funds"

(new-withdraw 15)
; => 35

;; another approach

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

; testing

(define W1 (make-withdraw 100))
; => w1

(define W2 (make-withdraw 100))
; => w2

(W1 50)
; => 50

(W2 70)
; => 30

(W2 40)
; => "insufficient funds"

(W1 40)
; => 10


;;; bank-account objects -- message-passing

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

; testing

(define acc (make-account 100)); => acc
((acc 'withdraw) 50)
; => 50

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

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

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

; a stylistic variation

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

; testing

(define acc (make-account 100))
(acc 'withdraw 50)
; => 50

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

(acc 'deposit 40)
; => 90

(acc 'withdraw 60)
; => 30

(acc 'say-what? 0)
; => ERROR:  Unknown request -- MAKE-ACCOUNT
;      say-what?

Monte Carlo

;; monte-carlo.ss

;; SICP source code


;;;SECTION 3.1.2

;; *following uses rand-update -- see ch3support.scm
;; *also must set random-init to some value

(define random-init 7)                  ;**not in book**

(define rand
  (let ((x random-init))
    (lambda ()
      (set! x (rand-update x))
      x)))


(define (estimate-pi trials)
  (sqrt (/ 6 (monte-carlo trials cesaro-test))))

(define (cesaro-test)
  (= (gcd (rand) (rand)) 1))

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

;; rand-update
;; From the SICP source code file "ch3support.ss":
;; For Section 3.1.2 -- written as suggested in footnote,
;; though the values of a, b, m may not be very "appropriately chosen"

(define (rand-update x)
  (let ((a 27) (b 26) (m 127))
    (modulo (+ (* a x) b) m)))

;; testing

(estimate-pi 100)
; => 3.429971702850177

(estimate-pi 1000)
; => 3.3806170189140663

(estimate-pi 10000)
; => 3.3841641928004607

(estimate-pi 100000)
; => 3.3844549105183512

; hmmm


;; second version (no assignment)
(define (estimate-pi trials)
  (sqrt (/ 6 (random-gcd-test trials random-init))))

(define (random-gcd-test trials initial-x)
  (define (iter trials-remaining trials-passed x)
    (let ((x1 (rand-update x)))
      (let ((x2 (rand-update x1)))
        (cond ((= trials-remaining 0)   
               (/ trials-passed trials))
              ((= (gcd x1 x2) 1)
               (iter (- trials-remaining 1)
                     (+ trials-passed 1)
                     x2))
              (else
               (iter (- trials-remaining 1)
                     trials-passed
                     x2))))))
  (iter trials 0 initial-x))

;; testing

(estimate-pi 100000)
; => 3.3844549105183512


; hmmm


;; EXERCISE 3.5
(define (random-in-range low high)
  (let ((range (- high low)))
    (+ low (random range))))

Pitfalls

;; pitfalls

;; SICP source code

;;;SECTION 3.1.3

(define (make-simplified-withdraw balance)
  (lambda (amount)
    (set! balance (- balance amount))
    balance))


;: (define W (make-simplified-withdraw 25))
;: (W 20)
;: (W 10)


(define (make-decrementer balance)
  (lambda (amount)
    (- balance amount)))

;: (define D (make-decrementer 25))
;: (D 20)
;: (D 10)

;: ((make-decrementer 25) 20)
;: ((lambda (amount) (- 25 amount)) 20)
;: (- 25 20)

;: ((make-simplified-withdraw 25) 20)

;: ((lambda (amount) (set! balance (- 25 amount)) 25) 20)
;: (set! balance (- 25 20)) 25

;;;Sameness and change

;: (define D1 (make-decrementer 25))
;: (define D2 (make-decrementer 25))
;: 
;: (define W1 (make-simplified-withdraw 25))
;: (define W2 (make-simplified-withdraw 25))
;: 
;: (W1 20)
;: (W1 20)
;: (W2 20)

;: (define peter-acc (make-account 100))
;: (define paul-acc (make-account 100))
;: 
;: (define peter-acc (make-account 100))
;: (define paul-acc peter-acc)

;;;Pitfalls of imperative programming

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
      product
      (iter (* counter product)
            (+ counter 1))))
  (iter 1 1))

(define (factorial n)
  (let ((product 1)
        (counter 1))
    (define (iter)
      (if (> counter n)
        product
        (begin (set! product (* counter product))
               (set! counter (+ counter 1))
               (iter))))
    (iter)))

; (factorial 5)

;; EXERCISE 3.7
;: (define paul-acc
;:   (make-joint peter-acc 'open-sesame 'rosebud))

SICP Source Code

Programming Exercises

In class today we will begin to work on the following exercises from chapter 3: 2, 3, 4, 7, 16, 17, 18, 19, 21, 22, 23, 28, 29, 30, 33, 34, 35, 36, 37, 51, 52, 53, 54, 55, 56, 58, 59.