sicp-ex-3.14

<< Previous exercise (3.13) | Index | Next exercise (3.15) >>

x3v

Apologies if diagram is unclear.

Below is the final box and pointer diagram after the procedure mystery is called.

W will point at the box pointing at d, whose cdr will point at the box pointing at c, so on and so forth until it reaches the box pointing at a, whose cdr points at '(). Therefore, W is now the reversed order of V.

V still points at the box pointing at a, but the cdr of a was set to be '() in the first iteration of loop. Therefore, V is now (a). 

w ---------------------------------------------------+
                                                     |
                                       +-------------+----+
                                       |             |    |
                          +------------+----+        |    |
                          |            |    |        |    |
             +------------+---+        |    |        |    |
             |            |   |        |    |        |    |
         +---v-+----+  +--v-+-+--+  +--v-+--+-+    +-v--+-+-+
         |     |    |  |    |    |  |    |    |    |    |   |
v ------>|  |  |'() |  |  | |    |  |  | |    |    | |  |   |
         +--+--+----+  +--+-+----+  +--+-+----+    +-+--+---+
            |             |            |             |
            v             v            v             v
            a             b            c             d

meteorgan

  
  
  The procedure mystery will produce the inverse order of x.  
 v 
 => (a b c d) 
 w 
 => (d c b a)

Rather Iffy

 Call : (mystery '(a b c d)) :

 +------------------------------------------------------------------------+
 |     x:    .                                                            |
 |     y: /  |                                                            |
 +------------------------------------------------------------------------+
             |                                           +----------------+
             |                                           | temp:  .       |
             |                                           +------- |-------+
             |                                                    |
             |                                                    |
             --------               ------------------------------
                     v              v
                 +---+---+      +---+---+      +---+---+      +---+----
                 | . | .------->| . | .------->| . | .------->| . | / |
                 +-|-+---+      +---+---+      +-|-+---+      +-|-+---+
                   v              v              v              v
                 +---+          +---+          +---+          +---+
                 | a |          | b |          | c |          | d |
                 +---+          +---+          +---+          +---+

 Result after 1 cycle through loop

 +------------------------------------------------------------------------+
 |     x:    .----------------------                                      |
 |     y:    .                      |                                     |
 +----------------------------------|-------------------------------------+
             |                      |                    +----------------+
             |                      |                    | temp:  .       |
             |                      |                    +--------|-------+
             |                      |                             |
             |                      |                             |
             --------               |              |---------------
                     v              v              v
                 +---+---+      +---+---+      +---+---+      +---+----
                 | . | /        | . | .------->| . | .------->| . | / |
                 +-|-+---+      +---+---+      +-|-+---+      +-|-+---+
                   v              v              v              v
                 +---+          +---+          +---+          +---+
                 | a |          | b |          | c |          | d |
                 +---+          +---+          +---+          +---+
 

 Result after 2 cycle

 +------------------------------------------------------------------------+
 |     x:    .-------------------------------------                       |
 |     y:    .                                     |                      |
 +-------------------------------------------------|----------------------+
             |                                     |     +----------------+
             |                                     |     | temp:  .       |
             |                                     |     +--------|-------+
             |                                     |              |
             |                                     |              |
             -----------------------|              |              |
                                    |              |              |
                                    |              |              |
                     ----------------------        |              |
                     v              v      |       v              v
                 +---+---+      +---+---+  |   +---+---+      +---+----
                 | . | /        | . | .----    | . | .------->| . | / |
                 +-|-+---+      +---+---+      +-|-+---+      +-|-+---+
                   v              v              v              v
                 +---+          +---+          +---+          +---+
                 | a |          | b |          | c |          | d |
                 +---+          +---+          +---+          +---+

 Result after 3 cycle

 +------------------------------------------------------------------------+
 |     x:    .-----------------------------------------                   |
 |     y:    .                                         |                  |
 +-----------------------------------------------------|------------------+
             |                                         | +----------------+
             |                                         | | temp:  /       |
             |                                         | +----------------+
             |                                         |
             |                                         |
             --------------------------------------    -----------
                                                   |              |
                                    ----- -------------- --       |
                                    |              |      |       |
                     ----------------------        |      |       |
                     v              v      |       v      |       v
                 +---+---+      +---+---+  |   +---+---+  |   +---+----
                 | . | /        | . | .----    | . | .----    | . | / |
                 +-|-+---+      +---+---+      +-|-+---+      +-|-+---+
                   v              v              v              v
                 +---+          +---+          +---+          +---+
                 | a |          | b |          | c |          | d |
                 +---+          +---+          +---+          +---+

 Result after 4 cycle

 +------------------------------------------------------------------------+
 |     x:    /                                                            |
 |     y:    .                                                            |
 +------------------------------------------------------------------------+
             |                                           +----------------+
             |                                           | temp:  /       |
             |                                           +----------------+
             |
             |
             -----------------------------------------------------|
                                                    ---------------------
                                                   |              |      |
                                                   |              |      |
                                    ----- -------------- --       |      |
                                    |              |      |       |      |
                     ----------------------        |      |       |      |
                     v              v      |       v      |       v      |
                 +---+---+      +---+---+  |   +---+---+  |   +---+---+  |
                 | . | /        | . | .----    | . | .----    | . | .----|
                 +-|-+---+      +---+---+      +-|-+---+      +-|-+---+
                   v              v              v              v
                 +---+          +---+          +---+          +---+
                 | a |          | b |          | c |          | d |
                 +---+          +---+          +---+          +---+

 Result after 5 cycle

 Printed value  :
 w : (d c b a)

Sphinxsky

meteorgan is wrong. The interpreter just made a shallow copy when it passed mystery parameters, so statement “(set-cdr! x y)” affects the value of v.

v => (a) w => (d c b a)


master

I don't really get it, why is v modified in the first iteration of loop but not the second?

intarga

Because in the second iteration, v is passed in as the second argument, not the first. Only the first argument is mutated.



Last modified : 2022-03-28 12:00:12
WiLiKi 0.5-tekili-7 running on Gauche 0.9