set-car! and set-cdr! turn pairs into mutable building blocks. Queues, tables, and circuits built from mutation. But sharing creates identity puzzles: eq? vs equal?.
Mutable list structure
set-car! and set-cdr! mutate the two halves of a pair in place. With these primitives, lists become mutable data structures.
Scheme
; Mutating pairs with set-car! and set-cdr!
(define x (list 123))
(display "before: ") (display x) (newline)
(set-car! x 99)
(display "after set-car!: ") (display x) (newline)
(set-cdr! x (list 78))
(display "after set-cdr!: ") (display x) (newline)
; Sharing: z1 and z2 look the same but differ in structure
(define a (list 12))
(define z1 (cons a a)) ; both car and cdr point to SAME list
(define z2 (cons (list 12) ; car and cdr are DIFFERENT lists
(list 12)))
(set-car! (car z1) 99)
(display "z1: ") (display z1) (newline) ; ((99 2) 99 2) โ shared!
(display "z2: ") (display z2) ; ((1 2) 1 2) โ independent
Python
# Python lists are mutable by default
x = [1, 2, 3]
print(f"before: {x}")
x[0] = 99print(f"after x[0]=99: {x}")
x[1:] = [7, 8]
print(f"after slice: {x}")
# Sharing vs copying
a = [1, 2]
z1 = [a, a] # both elements ARE a
z2 = [[1, 2], [1, 2]] # independent lists
a[0] = 99print(f"z1: {z1}") # [[99, 2], [99, 2]] โ shared!print(f"z2: {z2}") # [[1, 2], [1, 2]] โ independent
Representing queues
A queue needs O(1) insertion at the rear. The trick: maintain a pointer to both the front and rear of the list. set-cdr! on the rear pair threads in new elements.
fromcollectionsimport deque
q = deque()
q.append('a')
q.append('b')
q.append('c')
print(list(q)) # ['a', 'b', 'c']
q.popleft()
print(list(q)) # ['b', 'c']# Under the hood, deque uses a doubly-linked list# SICP's version is a singly-linked list with a rear pointer
Representing tables
A table is an association list with a header. Lookup scans the list; insert either updates an existing entry or prepends a new one. Two-dimensional tables nest a table inside each entry.
# Python dict is the built-in table
t = {}
t['a'] = 1
t['b'] = 2
t['c'] = 3print(t.get('b')) # 2
t['b'] = 99# updateprint(t.get('b')) # 99print(t.get('d')) # None
A simulator for digital circuits
Wires carry signals; gates transform them. Each wire maintains a list of action procedures that fire when its signal changes. This is event-driven simulation built from mutation and closures.
Scheme
; Simplified wire and gate simulation; Wires hold a signal and a list of actions
(define (make-wire)
(let ((signal 0) (actions '()))
(define (set-signal! new)
(if (not (= signal new))
(begin (set! signal new)
(for-each (lambda (a) (a)) actions))))
(define (add-action! proc)
(set! actions (cons proc actions))
(proc)) ; run once to initialize
(define (dispatch m)
(cond ((eq? m 'get-signal) signal)
((eq? m 'set-signal!) set-signal!)
((eq? m 'add-action!) add-action!)
(else (error "Unknown wire op" m))))
dispatch))
(define (get-signal w) (w 'get-signal))
(define (set-signal! w v) ((w 'set-signal!) v))
(define (add-action! w proc) ((w 'add-action!) proc))
; Inverter: when input changes, flip output
(define (inverter input output)
(add-action! input
(lambda ()
(let ((new (if (= (get-signal input) 0) 10)))
(set-signal! output new)))))
(define in (make-wire))
(define out (make-wire))
(inverter in out)
(display "out: ") (display (get-signal out)) (newline) ; 1
(set-signal! in 1)
(display "out: ") (display (get-signal out)) ; 0
Scheme pairs are the universal building block. Python has no mutable pair primitive; lists, deques, and dicts replace the various structures SICP builds from cons cells.
The circuit simulator's "action procedures on wires" pattern is the Observer pattern. Python typically uses callbacks or event libraries for the same thing.
Sharing bugs (mutating a shared substructure) are identical in both languages. The fix is the same too: copy when you need independence.
Wikipedia: Linked list