Assignment & State

Abelson & Sussman · 1996 · SICP §3.1

set! introduces time into the model. Once variables can change, substitution breaks down. Objects with local state model real-world entities but sacrifice referential transparency.

Local state variables

make-withdraw returns a procedure that remembers its balance. Each call to the returned procedure mutates the enclosed variable. The procedure has state.

Scheme

; A withdraw procedure with local state
(define (make-withdraw balance)
  (lambda (amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds")))

(define W (make-withdraw 100))
(display (W 25)) (newline)   ; 75
(display (W 25)) (newline)   ; 50
(display (W 60)) (newline)   ; Insufficient funds
(display (W 15))             ; 35

A full bank account bundles deposit and withdraw behind a message-passing interface:

Scheme

; Bank account with deposit and withdraw
(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" m))))
  dispatch)

(define acc (make-account 100))
(display ((acc 'withdraw) 50)) (newline)  ; 50
(display ((acc 'deposit) 40)) (newline)   ; 90
(display ((acc 'withdraw) 60))            ; 30

The costs of introducing assignment

Without set!, calling a procedure with the same arguments always returns the same result. That is referential transparency. Assignment destroys it: (W 25) returns different values on successive calls. The substitution model cannot explain this; we need the environment model (next chapter).

Scheme

; Referential transparency: pure version
; Same input always gives same output
(define (make-decrementer balance)
  (lambda (amount) (- balance amount)))

(define D (make-decrementer 100))
(display (D 25)) (newline)  ; always 75
(display (D 25)) (newline)  ; always 75

; Now compare with set! version:
; Same call, different results
(define (make-withdraw balance)
  (lambda (amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds")))

(define W (make-withdraw 100))
(display (W 25)) (newline)  ; 75
(display (W 25))            ; 50 — not the same!

The benefits of assignment: Monte Carlo

Assignment enables clean modular design when modeling processes with internal randomness. The Monte Carlo method estimates π by testing random points in the unit square. The random number generator hides its state; the estimator does not need to know how randomness works.

Scheme

; Monte Carlo estimation of pi
; Using assignment for a simple linear-congruential RNG

(define rand-state 42)

(define (rand)
  (set! rand-state
        (modulo (+ (* 1103515245 rand-state) 12345)
                (expt 2 31)))
  rand-state)

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

; Cesaro test: are two random numbers coprime?
(define (cesaro-test)
  (= (gcd (rand) (rand)) 1))

(define fraction (monte-carlo 1000 cesaro-test))
(display "fraction coprime: ")
(display fraction) (newline)
(display "pi estimate: ")
(display (sqrt (/ 6.0 fraction)))

Sameness and change

If two variables refer to the same mutable object, changing one affects the other. Before set!, "same" meant "equal value." After set!, we must distinguish identity (same object) from equality (same value).

Scheme

; Identity vs equality with mutable 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" m))))
  dispatch)

(define acc1 (make-account 100))
(define acc2 (make-account 100))

; acc1 and acc2 have equal balances but different identity
((acc1 'withdraw) 30)
((acc2 'withdraw) 10)

; acc1 has 70, acc2 has 90 — same starting value, different state
(display "acc1: ") (display ((acc1 'withdraw) 0)) (newline)
(display "acc2: ") (display ((acc2 'withdraw) 0)) (newline)

; Aliasing: acc3 IS acc1
(define acc3 acc1)
((acc3 'deposit) 50)
(display "acc1 after acc3 deposit: ")
(display ((acc1 'withdraw) 0))

Notation reference

Scheme	Python	Meaning
`(set! x v)`	`x = v`	Mutation — assign new value
`(begin e1 e2)`	`e1; e2`	Sequencing — evaluate in order
`(lambda (x) body)`	`lambda x: body`	Closure — captures enclosing scope
`(eq? a b)`	`a is b`	Identity — same object
`(equal? a b)`	`a == b`	Equality — same value

Translation notes

Scheme closures capture variables by reference. Python closures do the same, but rebinding requires nonlocal or a mutable container (list cell).
set! is Scheme's only mutation primitive for variables. Python uses bare assignment, with nonlocal to reach enclosing scopes.
Message-passing dispatch with cond maps directly to Python classes with methods.

Neighbors

Ready for the real thing? Read SICP §3.1.

← Generic Operations by june.kim Environment Model · 10 of 22 →