How to do Structure and Interpretation of Computer Programs (SICP)

MIT taught some form of this book in their 6.001 course from 1980 (as lecture notes) until 2007 and I think still teaches it in 6.037 (now 6.9550). UC Berkeley teaches a Python derivative of the book and there is an authorized JavaScript 2022 version taught at the National University of Singapore but the authors have had to make significant changes in chapter 4 because of the limitations of JavaScript.

There is lectures from 1986 here and if you search YouTube many more recent lectures from Berkeley and countless hackathons or compsci reading groups have videos on working through the book.

To do the book read the setup instructions from Sussman's grad course and only use mit-scheme or you may have problems in later chapters when we need to use the picture language or parallel.scm or mutable lists. If you have to install a VM try the QEMU image for Guix System because it's entire configuration is done using scheme. Guile scheme may work for the entire book too but I have no idea, it has a picture language at least.

I'm aware of #lang sicp in DrRacket and many other 3rd party implementations you can start with those for the first few chapters but if you want to do Sussman's more recent books like SDF you're going to have to use the latest mit-scheme anyway so we may as well begin with using the language the book actually wants us to use.

Whatever you use keep some kind of exercise versioning so you can refer to them later in future chapters when the book asks you to use code you've already written. This can be simply saving them as their numbered identifier in the book or however you want. You can type scheme into any text editor, save as filename.scm, run mit-scheme, and load your file in the REPL manipulating it there you don't have to use an IDE. This is trivial with (load "filename.scm").

The only IDEs I use are emacs and edwin the editor that comes with mit-scheme. Edwin is a clone of an old emacs version (Emacs 18 I believe if you want to find a ref card for it) entirely written in scheme and is what 6.001 and the graduate courses have used for decades. Sussman still uses it as per his 2022 course setup notes. You start edwin with mit-scheme –edit and are good to go without needing to install anything else as a scheme shell spawns immediately upon opening and debugging is all built-in. However regular emacs will probably be more familiar to you with 'modern' default behavior like you'll have a GUI menu, ability to highlight and cut+paste with a mouse, delete key won't default to be a backspace etc.

• Editor setup from 6.945 and setup from 6.946 for emacs or edwin
• Sussman's .edwin config file here for better fonts (save in home directory as .edwin (with the period))
• Edwin specific docs here (it has a stepper too)
  • Edwin ref card
  • MIT lab doc on Edwin commands and how to use the debugger

If you choose emacs install vanilla emacs not any of those 'spacemacs' or whatever preconfigured versions that remove the GUI drop down menus. Click Options->Customize Emacs->Custom Themes and change the colors around if you want. You won't need a config file everything like MELPA package install is already included (and scheme mode) so you will automatically enter scheme mode when opening any file ending in .scm

I wouldn't recommend Paredit mode or Geiser or anything until you start writing larger programs in the later chapters because you learn scope in the beginning by seeing how all the parens close blocks of expressions and having something automatically shifting around parens when you don't have experience is going to be rage inducing. When your programs start becoming one big function in chapter 4 then install tools.

Commands:

• C-x C-c (exit emacs/edwin) is hold down Ctrl and type x, keep holding Ctrl and type c.
• C-h t is hold down Ctrl and type h, release Ctrl and type t (starts the tutorial).
  • PgUp/PgDn, End/Home, arrow keys and mouse all work too you don't have to use the movement commands in tutorial
• M-x the M is the 'meta' key which on a modern keyboard is usually ALT (sometimes the Windows key) but you can redefine both C and M to be something else.
• C-g or Ctrl-g is the escape key if you accidentally screw up mid command and want to try again.

Open multiple screens

In either edwin or emacs: use command C-x C-f and type test.scm to open or make a new file. Use C-x 3 and a new window should open to the right or if you want the new window below use C-x 2. Click on the new window and type C-x b and press enter to switch to the scheme REPL which was the buffer you saw when you first opened the editor. Now you have a screen to enter code with the output beside it. In emacs there is no default scheme buffer (unless you configure one) you have to select from the dropdown menu 'run inferior scheme' or M-x mit-scheme.

Eval code

Click on the test.scm buffer and enter some random code:

(define x 3)
(+ x 2)
(+ x 2 2)
"this is a string"
;this is a comment

How do you run this in the REPL? Either M-o or C-M-z (edwin) or follow the emacs GUI menus to 'evaluate region' all described in the docs and tutorial. Type C-h m to get a list of available commands in whatever current buffer. To switch out of the help buffer C-x b and default will be test.scm or wherever you were last. You can highlight with the mouse (in emacs) snippets of code and just eval that selected code.

Emacs you can evaluate the entire file with C-c C-l but Lisp/Scheme programming is typically done incrementally you write a function then C-x C-e to run it in the interpreter, switch to the interpreter and give it some sample inputs to test, switch back to write a new function and repeat. If emacs asks what scheme to load type 'mit-scheme'.

Errors

If you get something similar:

;Unbound variable: *2
;To continue, call RESTART with an option number:
; (RESTART 3) => Specify a value to use instead of *2.
; (RESTART 2) => Define *2 to a given value.
; (RESTART 1) => Return to read-eval-print level 1.

Then typing (restart 1) will return to the REPL or you can try option 3 and fix the typo, or break/kill it in emacs. The bulk of errors will be parens problems in the beginning but it's how you learn and after a few of them you're much more careful about code and what scope it's in. If you run the debugger type C-h m to get a list of commands (can run that in the REPL too).

I'm using the online version and one of the illicit pdfs floating around to see the figures which are impossible to read in the online html version.

A computational process I would interpret as a running program or the act of computation itself. A procedure is sometimes called a function in modern programming parlance but the book makes it clear later in this chapter these are different things pointing out how a math function definition is nothing like a procedure.

Ex 1.2 is an example of an impossible to read figure. Use the pdf.

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
   (* 3 (- 6 2) (- 2 7)))

Ex 1.3 simple (cond (and ())) you can write your own test cases/examples too:

(= (three-square-sum 1 2 3) (+ (* 2 2) (* 3 3))
(= (three-square-sum 3 1 2) 13)
(= (three-square-sum 3 2 1) 13)
(= (three-square-sum 1 1 1) 2)
(= (three-square-sum 0 1 0) 1)

Ex 1.4 many languages won't let you do this and is a good example of symbolic programming it evals to (+ a b) if b > 0 or (- a b) if not.

Ex 1.5 (define (p) (p)) is a non-terminating loop where (p) keeps calling itself. Since normal-order doesn't eval subexpressions into values until they are needed (p) is never run because it's never needed as (test 0 (p)) will always evaluate to 0.

Ex 1.6 new-if is a regular procedure so it's input (all the subexpressions) are evaluated first with applicative-order eval. The three inputs to new-if: (good-enough? guess x) returns a boolean, guess is already a value, but (sqrt-iter (improve guess x) x) will just keep improving the guess until the end of days as the cond predicate good-enough? is never reached to stop the recursion. The special-form if/else does not automatically evaluate the else clause it preforms the predicate test first.

Ex 1.7 try examples:

1 ]=> (sqrt 0.0009)
;Value: .04030062264654547

1 ]=> (sqrt 1000000000000000)
;takes forever, infinite loop?

(sqrt 0.0009) should be 0.03 and the gigantic number never terminates. This happens because using our current testing strategy of subtracting the square of the guess from the radicand the epsilon (0.001) isn't precise enough for small numbers and very large numbers clearly they never meet that precision or it takes too long to do so. If we ratio the change in guess with the existing guess, the closer they are together the closer they approach 1 so we can adjust our program to check for this by subtracting that ratio from 1 to see if the two guesses are within epsilon of each other.

(define (good-enough? guess x)
  (< (abs(- 1 (/ (improve guess x) guess))) 0.001))

Now gigantic square roots eval immediately and tiny square roots are close enough to wolfram alpha online calculator precision.

Ex. 1.8 The cube root of 8 is 2 or 2 * 2 * 2. Plugging that into the formula: (8/4 + 4)/3 or 6/3 = 2. All I did was change improve procedure and delete average procedure since it wasn't needed anymore:

(define (improve guess x)
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

1.1.8 Black-Box Abstractions if you look at the mit-scheme documentation and scroll to the index at the bottom you'll find definitions for exp and log which are e^x and log(x) base e. The square x function defined as (exp (double (log x))) if x is 8 then (exp ~4.16) which is 64. A log is a linearized exponent it tells us what the x in e^x = 8 is and it's 2.079. If we double that and feed it to e then e^4.16 = 64. We can see this ourselves using desmos go along the x-axis to 2, go up until it meets the blue log line, it lands at y = 0.7 or so. Double that to ~1.4 and travel x-axis to 1.4, go up to the exp(x) line and you'll see you intersect at y = 4 or the square of 2 is 4. Both e and it's log (usually written ln or 'the natural log') are preferred for math modeling because it has properties like the derivative of e is itself, this square property we just learned, and that you can estimate e^x and ln(x) simply on a piece of paper when working with small displacements. For example e^x for small x like 0.05 is 1 + x and ln(1 + x) is just x for 'small' x.

I rewrote fact-iter to instead be a function nested inside another function, with a 'trampoline' meaning execution falls to the bottom of the function hitting (f 1 n) and bounces back calling f. It's the same as what is in the book except simplified. A factorial is a product of every number up to the nth factorial so 3! is 1x2x3.

(define (factorial n)
  (define (f total counter)
    (if (< counter 2)
	total
	(f (* total counter) (- counter 1))))
  (f 1 n))

(factorial 6)
(factorial 1)
(factorial 0)

The difference in the book between the delayed chain of operations and the iterated version is called re-entry. The delayed chain has to re-enter the same function before returning a value so must keep all that accounting of state somewhere which we will eventually learn is the stack.

Ex 1.9 addition is defined as a function that uses a as a counter and increments b everytime there is still an a left until a = 0. The first function (inc (function call)) is going to return a chain of increments until a = 0 then all delayed increment operations will be done.

Ex 1.10 'concise math definitions' means turn (* 5 n n) into 5n² and if you plug in some values to f then f(n) = 2y. If you are using edwin you can run the stepper see the manual for mit-scheme. Otherwise hand step:

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

(define (g n) (A 1 n))
(define (h n) (A 2 n))

(g 2)
- (A 1 2)
- (A 0 (A 1 1))
- (A 0 (2)) 
- (* 2 2)
- 4

(h 3)
- (A 2 3)
- (A 1 (A 2 2)))
- (A 1 (A 1 (A 2 1)))
- (A 1 (A 1 2))
- (A 1 (A 0 (A 1 1)))
- (A 1 (A 0 (2)))
- (A 1 (* 2 2))
- (A 1 4)
- (A 0 (A 1 3))
- (A 0 (A 0 (A 1 2)))
- (A 0 (A 0 (A 0 (A 0 1))))
- (A 0 (A 0 (A 0 (2))))
- (A 0 (A 0 (4)))
- (A 0 (* 2 4))
- (A 0 (8))
- (* 2 8)
- 16

G seems to produce 2ⁿ while H generates sequence 2, 4, 16, 65536… or \(2^{2^2..}\).

Phi or \(\phi\) is a constant like e that is solely here to illustrate (fib n) process is exponential.

The 'golden ratio' is anything satisfying \(\frac{a + b}{a} = \frac{b}{a}\) and is found in taking diagonals of pentagons and other geometry you can look up on YouTube and phi is this ratio. In case it wasn't clear in the book the iterative algorithm comes from the observation that 0, 1, 1, 2, 3, 5.. the next in the sequence is the sum of the previous 2 numbers.

Hand step the count-change procedure with only 2 coins and amount 1:

• (+ (cc 1 2 (+ (cc 1 1) (cc 1 0))))
• (+ (cc 1 2 (+ (cc 1 1) 0)))
• (+ (cc 1 2 (+ (cc (1 - 1) 0))))
• (+ (cc 1 2 (+ 1 0)))
• (+ (cc (1 - 2) 1))
• (+ 0 1)
• 1

The computations are delayed as (+) needs two arguments so recursion is unrolled fully then evaluation can begin once it stops with 0 or 1.

Watch the lecture for this chapter where he explains what time and space means the whole lecture is worth watching but the specific time/space explanation starts around 17:09. Time is the amount of steps that are evaluated and space is the amount of data needing to be stored. The numbers 16 and 8 differ by a constant factor of 2 and by a constant factor of 8 but as he says in this analysis we don't care what the constant is just that it is a constant and not changing with the input. Try the iterative procedure in the lecture that uses '1+' and '-1+' both built-in increment/decrement functions. He redefines '+' procedure which you can do in lisp you can rename or redefine anything you want. That iterative procedure uses an accumulator the y parameter keeps incrementing until x is 0 and y is returned.

He uses big-O in the lecture and big-theta in the book. O(n) is an upper bound and \(\theta\)(n) is both a lower and an upper bound. We don't say 'the' upper bound since an upper bound for y is y or y² or y^y there's many upper bounds but they don't all describe the behavior of the process completely like big-theta does which says a process y grows at least \(\theta\)(f(x)) and at most \(\theta\)(f(x)).

In the book the definition for \(\theta\) is \(k_{1}f(n) \le R(n) \le k_{2}f(n)\) where the two k's represent constants that can be the same or different, R(n) is a function that represents the resources for a process (space or steps/time to complete) and f(n) is the function inside O(f(n)) or \(\theta\)(f(n)) that is chosen from a list of existing math functions to best describe the behavior of R(n). If R(n) grows to at least n² and at most n² then R(n) is in \(\theta\)(n²).

The definition of big-theta is \(k_{1}f(n) \le R(n) \le k_{2}f(n)\) and fib(n) steps/time is: \[\frac{1}{\sqrt 5}\cdot\phi^n \le fib(n) \le \frac{1}{\sqrt 5}\cdot\phi^n = \theta(\phi^{n})\]

The definition of big-O is \(R(n) \le kf(n)\) so (fib n) is:

\[fib(n) \le \frac{1}{\sqrt 5}\cdot\phi^n \in O(\phi^{n})\]

Since phi is equal to 1.6180.. and (1.6)ⁿ won't grow faster than 2ⁿ this is another legit upper bound though not as tight:

\[fib(n) \le \frac{1}{\sqrt 5}\cdot\phi^n \in O(2^{n})\]

The last two inequalites use \(\in\) or 'is in' because there's an order hierarchy for asymptotics where big-theta means roughly equal, big-O means greater than or equal, little-o is strictly less than, big-Omega is strictly greater, etc. To be precise the function inside O() or any other asymptotic bound represents a 'family of functions' so means every function who's growth is bounded by the function inside O(). Watch this to learn more like O-tilde, poly(), and what exactly are the standard form functions that are 'chosen from a list' in O(f(n)).

TODO