SICP 09 - Mutable data, queues, tables

Read Section 3.3.1-3.3.3

Encompasses lectures 24, 25, 26

The Sections mostly describe the difference between the substitution and environment model of evaluation in reference to lists, and how allowing someone to modify the underlying data in a list additionally complicates things.

For example, the primitive mutators for pairs are set-car! and set-cdr!. set-car! takes two arguments, the first of which must be a pair. It modifies this pair, replacing the car pointer by a pointer to the second argument of set-car!

Once you introduce these versions of set! calls, whether or not two items are the same item (i.e. identity) becomes more important. Allowing any set! call to modify the tail of a list means that you can share nodes between different variables, but it also means data can change from underneath you. This is basically the same problem as sharing references to variables when parallelizing code.

In simple lisp programs, testing for equality is the same as identity, because you just substitute the values for the free variables.