notes from reading Structure and Interpretation of Computer Programs
Other useful materials helpful in exploration of elegant weapons:
- Brian Harvey’s SICP lectures
- Programming Languages Virtual Meetup SICP
- Lambda? You Keep Using that Letter - Kevlin Henney
To run Scheme interpreter on Mac M1 with ARM silicon the best tool I've found is Gambit Scheme as it's readily available on Homebrew. To install it, simply run brew install gambit-scheme
For using Scheme in Jupyter Notebook I've used Calysto Scheme
Great explanation of recursive procedures vs recursive processes, illustrated with factorial function.
def factorial1(n):
if n == 0:
return 1
else:
return n * factorial1(n-1)- recursive procedure - factorial1 calls itself in the definition
- recursive process - chain of deferred operations, interpreter keeps track of operations to be performed later
def factorial2(n):
def factorial(product, counter, max_count):
if counter > max_count:
return product
else:
return factorial(product * counter, counter + 1, max_count)
return factorial(1, 1, n) - recursive procedure - factorial calls itself in the definition
- iterative process - state can be summarized by state variables (product, counter, max_count) that we pass from one state to the next
def factorial3(n):
product = 1
counter = 1
max_count = n
while counter <= max_count:
product *= counter
counter += 1
return product- iterative process - no self-reference in the function definition, use of "looping construct" (while)
- iterative process - state summarized by fixed number of state variables
More exploration in processes.ipynb and similar functions in Scheme
Recursive process
(define (fib1 n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib1 (- n 1))
(fib1 (- n 2))))))Iterative process
(define (fib2 n)
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
(fib-iter 1 0 n))Files with the same example fibonacci.scm and fibonacci.py
Many similar procedures like:
(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b))))
(define (sum-cubes a b)
(if (> a b)
0
(+ (cube a) (sum-cubes (+ a 1) b))))can be defined in terms of the pattern they share:
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b)))) Procedure for summing cubes can now be rewritten as:
(define (sum-cubes a b)
(sum cube a inc b))
(define (inc n) (+ n 1))However, sum procedure is only one example of this class of functions. Another example:
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))Here, we can again see many similarities between these procedures. In the same way as sum-integers and sum-cubes are just special cases of a more general procedure sum, sum and product can be viewed as special cases of a more general procedure accumulate:
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate combiner null-value term (next a) next b))))See ex1.32 for comaprison of recursive and iterative accumulate
Defining procedure as a special cases of some more abstract (higher-order) procedure is possible thanks to first-class functions.
Once we have higher-order function that operate on other procedures we frequently need to define smaller, helper procedures like:
(define (inc n) (+ n 1))It's not very convenient to create a new procedure for simplest operations like increment and that's why anonymous procedures become useful:
(lambda (n) (+ n 1))Data can be defined in terms of its behaviour specified by constructor (make-rational) and selectors (nominator, denominator):
(define x (make-rational n d))
(= (/ (numer x) (denom x)) (/ n d))in a simlar way we can define cons, car and cdr by its behaviour:
(define z (cons x y))
(= (car z) x)
(= (cdr z) y)We can implement such behaviour without any data structures, only using prodecures:
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1 -- CONS" m))))
dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))Data can be implemented in terms of procedures.
Similar example in Python:
# pairs as data
def cons_d(x, y):
return (x, y)
def car_d(pair):
return pair[0]
def cdr_d(pair):
return pair[1]# pairs as procedures
def cons_p(x, y):
def dispatch(m):
if m == 0:
return x
elif m == 1:
return y
else:
raise ValueError()
return dispatch
def car_p(pair):
return pair(0)
def cdr_p(pair):
return pair(1)Examples of usage: pairs.py
Sequence processing can be defined in many ways:
(define (sum-odd-squares tree)
(cond ((null? tree) 0)
((not (pair? tree))
(if (odd? tree) (square tree) 0))
(else (+ (sum-odd-squares (car tree))
(sum-odd-squares (cdr tree))))))(define (even-fibs n)
(define (next k)
(if (> k n)
`()
(let ((f (fib k)))
(if (even? f)
(cons f (next (+ k 1)))
(next (+ k 1))))))
(next 0))In these implementations sum-odd-squares and even-fibs are structurally different, but in fact they consist of similar operations:
- enumerate initial data
- filter them
- transform with some function
- accumulate the result
We can define these underlying operations and think about program as a flow of "signals" from one stage to the next.
- Enumerate interval/tree
(define (enumerate-interval low high)
(if (> low high)
`()
(cons low (enumerate-interval (+ low 1) high))))
(define (enumerate-tree tree)
(cond ((null? tree) `())
((not (pair? tree)) (list tree))
(else (append (enumerate-tree (car tree))
(enumerate-tree (cdr tree))))))- Filter
(define (filter predicate sequence)
(cond ((null? sequence) `())
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))-
Transform -
map -
Accumulate
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))With these operations defined sum-odd-squares and even-fibs can be reformulated as a signal flow.
(define (sum-odd-squares tree)
(accumulate +
0
(map square
(filter odd?
(enumerate-tree tree)))))
(define (even-fibs n)
(accumulate cons
`()
(filter even?
(map fib
(enumerate-interval 0 n)))))Not exactly eval and apply functions from Scheme, but something very similar was used to implement calculator interpreter.
Separate README for the exploration of this topic.
First example of this technique was shown in section What Is Meant by Data?, where cons pair was coded as a dispatch procedure. In a similar way, we can create "object" to represent a bank account that is again implemented as a dispatch procedure.
(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)Great chapter full of drawings and great explanations of how Scheme is actually evaluated. Go read it directly from the book.
As we know from What Is Meant by Data?, pairs can be represented purely in terms of procedures:
(define (cons x y)
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
(else (error "Undefined operation: CONS" m))))
dispatch)
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))We can construct mutable data in a similar way.
(define (cons x y)
(define (set-x! v) (set! x v))
(define (set-y! v) (set! y v))
(define (dispatch m)
(cond ((eq? m 'car) x)
((eq? m 'cdr) y)
((eq? m 'set-car!) set-x!)
((eq? m 'set-cdr!) set-y!)
(else
(error "Undefined operation: CONS" m))))
dispatch)
(define (car z) (z 'car))
(define (cdr z) (z 'cdr))
(define (set-car! z new-value)
((z 'set-car!) new-value) z)
(define (set-cdr! z new-value)
((z 'set-cdr!) new-value) z)The book has a great comment on that:
Assignment is all that is needed, theoretically, to account for the behavior of mutable data. As soon as we admit set! to our language, we raise all the issues, not only of assignment, but of mutable data in general. On the other hand, from the viewpoint of implementation, assignment requires us to modify the environment, which is itself a mutable data structure. Thus, assignment and mutation are equipotent: Each can be implemented in terms of the other.
Full Scheme implementation can be compared with Python implementation.
Not too many practical insights about concurrency, but a very interesting comment:
The basic phenomenon here is that synchronizing different processes, establishing shared state, or imposing an order on events requires communication among the processes. In essence, any notion of time in concurrency control must be intimately tied to communication. It is intriguing that a similar connection between time and communication also arises in the Theory of Relativity, where the speed of light (the fastest signal that can be used to synchronize events) is a fundamental constant relating time and space. The complexities we encounter in dealing with time and state in our computational models may in fact mirror a fundamental complexity of the physical universe.