SICP exercise 5.20

32 views Asked by At

The exercise is from §5.3.1, and the text is copied below:

Draw the box-and-pointer representation and the memory-vector representation (as in figure 5.14) of the list structure produced by

(define x (cons 1 2))
(define y (list x x))

with the free pointer initially p1. What is the final value of free? What pointers represent the values of x and y?

I think what confuses me is precisely the linked figure,

enter image description here

considering that it's not explicitly mentioned why the entries 1, 2, 4, 5, and 7 are used.

I assume that the reason is that those where the first 5 free slots when the example list structure ((1 2) 3 4) was allocated. After all, that list must come from a '((1 2) 3 4) in Scheme code, which is the same as (cons (cons 1 (cons 2 '()) (cons 3 (cons 4 '())))), and about cons I read

Cons is performed by allocating an unused index and storing the arguments to cons in the-cars and the-cdrs at that indexed vector position.

If that's the case, then I believe the solution to the exercise is as follows, assuming the memory is all free initially:

       ┌───┬───┐    ┌───┬───┐
  y ──>│ + │ ──┼───>│ + │ / │
       └─┼─┴───┘    └─┼─┴───┘
         │            │
         ├────────────┘
         │
         v
       ┌───┬───┐    ┌───┐
  x ──>│ + │ +─┼───>│ 2 │
       └─┼─┴───┘    └───┘
         │
         │
         v
       ┌───┐
       │ 1 │
       └───┘

              0    1    2    3    4    5
            ┌────┬────┬────┬────┬────┬────┬────┬────┬────
  the-cars  │    │ n1 │ p1 │ p1 │    │    │    │    │
            ├────┼────┼────┼────┼────┼────┼────┼────┼────
  the-cdrs  │    │ n2 │ e0 │ p2 │    │    │    │    │
            └────┴────┴────┴────┴────┴────┴────┴────┴────
                   ^         ^    ^
                   |         |    |
                   |         |    |
                   x         y   free

Otherwise, I think, I should have been given an "evolution" for free, no?

0

There are 0 answers