sicp-ex-5.20



<< Previous exercise (5.19) | Index | Next exercise (5.21) >>


aos

Here's my answer to this one!

  
  
 ;   ----->  x  <----- 
 ;   |   ---------   | 
 ;   |   | 1 | 2 |   | 
 ;   |   ---------   | 
 ;   |   3           | 
 ; ---------       --------- 
 ; | ● | ● |  -->  | ● | / | 
 ; ---------       --------- 
 ; 1               2 
  
 ;            0   1    2    3     4 
 ;          ------------------------- 
 ; the-cars |   | p3 | p3 | n1 |    | 
 ;          ------------------------- 
 ; the-cdrs |   | p2 | e0 | n2 |    | 
 ;          ------------------------- 

codybartfast





          [.|.] --> [.|/]
         3 │       2 │
           └────┐ ┌──┘
                v v
               [.|.]
              1 │ │
                V V
                1 2


Index      0  1  2  3  4  5
         ┌──┬──┬──┬──┬──┬──┐
the-cars │  │n1│p1│p1│  │  │
         ├──┼──┼──┼──┼──┼──┤
the-cdrs │  │n2│e0│p2│  │  │
         └──┴──┴──┴──┴──┴──┘

free = p4
x    = p1
y    = p3

Looking at various answers on the interweb there seems to be litte agreement
on the order in which values are allocated to memory. A common variation is:

Index      0  1  2  3  4  5
         ┌──┬──┬──┬──┬──┬──┐
the-cars │  │n1│p1│p1│  │  │
         ├──┼──┼──┼──┼──┼──┤
the-cdrs │  │n2│p3│e0│  │  │
         └──┴──┴──┴──┴──┴──┘

This doesn't look right to me because the address that (p1 . e0) is stored
in is not known until after (p1 . e0) is saved to memory:

  (perform
   (op vector-set!) (reg the-cars) (reg free) (reg <reg2>))
  (perform
   (op vector-set!) (reg the-cdrs) (reg free) (reg <reg3>))
  (assign <reg1> (reg free))  ;; <-- address not avialable until here
  (assign free (op +) (reg free) (const 1))

So the contents of the inner cons must already be stored before the outer
cons can use the address of the inner cons as its cdr.

Generally, when looking at Lisp expressions, I would imagine values are
stored in the order that operations complete, not in the order that they are
called.


revc

 Box-and-pointer and memory-vector representations:

here