set-car! by example

Some remedial semantics while I'm feeling sick as a dog...

What's happening in this program?

(define x (cons 'a 'b))
(define y (cons 'c 'd))
(define z (cons x y))
(set-car! z y)
(set-car! y 'e)
z
; => ((e . d) e . d)

First remember that expressed values are the values the expressions can evaluate to, and denoted values are the values that are stored in environments--in Scheme, denoted values are locations in the store, and expressed values include mutable pairs, which are pairs of store locations.

Let's be the interpreter. After the first two definitions, we have the following configuration:

env: [x -> 2][y -> 5]
store:
0 : 'a
1 : 'b
2 : (0, 1)
3 : 'c
4 : 'd
5 : (3, 4)

Next we define the pair (cons x y). The evaluation of x and y gives us expressed values (0, 1) and (3, 4). Evaluation of the cons duplicates these pair values, and the new pair points to these two new copies:

env: [x -> 2][y -> 5][z -> 8]
store:
0 : 'a
1 : 'b
2 : (0, 1)
3 : 'c
4 : 'd
5 : (3, 4)
6 : (0, 1)
7 : (3, 4)
8 : (6, 7)

Now, for the first set-car!, the first argument evaluates to the pair associated with z, i.e., the expressed value (6, 7). The second argument evaluates to the expressed value (3, 4). Because the pair is really a pair of pointers, we don't touch its value but rather change the value in the cell pointed to by the car of the pair, i.e. cell 6:

0 : 'a
1 : 'b
2 : (0, 1)
3 : 'c
4 : 'd
5 : (3, 4)
6 : (3, 4)
7 : (3, 4)
8 : (6, 7)

Now the second set-car! evaluates its first argument to the pair (3, 4) and again mutates the cell pointed to by the car of the pair:

0 : 'a
1 : 'b
2 : (0, 1)
3 : 'e
4 : 'd
5 : (3, 4)
6 : (3, 4)
7 : (3, 4)
8 : (6, 7)

By the end, we have multiple copies of y, but they all point to the same location 3, which has been mutated.

My kingdom for ref-cells!