sicp-ex-3.20


<< Previous exercise (3.19) | Index | Next exercise (3.21) >>

codybartfast




            para: x                                        para: z
            para: y              para: z      para: z      para: new-value
          (define (set-x!...    (z 'car)     (z 'cdr)     ((z 'set-car!)...
                ^                  ^            ^               ^
                │                  │            │               │
                @ @ ─┐             @ @ ─┐       @ @ ─┐          @ @ ─┐
                 ^   │              ^   │        ^   │           ^   │
global env ──┐   │   │              │   │        │   │           │   │
             v   │   v              │   v        │   v           │   v
┌──────────────────────────────────────────────────────────────────────────┐
│cons:───────────┘                  │            │               │         │
│car:───────────────────────────────┘            │               │         │
│cdr:────────────────────────────────────────────┘               │         │
│set-car!:───────────────────────────────────────────────────────┘         │
│                                                                          │
│(after calls to cons)                                                     │
│x:┐                                  z:┐                                  │
└──────────────────────────────────────────────────────────────────────────┘
 ┌─┘                             ^      │                               ^
 │                               │      │                               │
 │ ,───────────────────────────────────────────────<──┐                 │
 │/                              │      │             │                 │
 │ ,────────────────────────────────────────────<──┐  │                 │
 │/                              │      │          │  │                 │
 │                               │      │          │  │                 │
 │              call to cons     │      │          │  │   call to cons  │
 v      ┌────────────────────────┴──┐   │      ┌────────────────────────┴──┐
 │      │x: 1 (17 after set-x!)     │   │      │x:─┘  │                    │
 │ E1 ->│y: 2                       │   │ E2 ->│y:────┘                    │
 │      │set-x!:────────────────┐   │   │      │set-x!:────────────────┐   │
 │      │set-y!:─────────┐      │   │   │      │set-y!:─────────┐      │   │
 │      │dispatch:┐      │      │   │   │      │dispatch:┐      │      │   │
 │      └───────────────────────────┘   │      └───────────────────────────┘
 │                │  ^   │  ^   │  ^    │                │  ^   │  ^   │  ^
 ├──>─────────────┤  │   │  │   │  │    └───┬──>─────────┤  │   │  │   │  │
 │                v  │   v  │   v  │        │            v  │   v  │   v  │
 │               @ @ │  @ @ │  @ @ │        │           @ @ │  @ @ │  @ @ │
 │               │ └─┘  │ └─┘  │ └─┘        │           │ └─┘  │ └─┘  │ └─┘
 │               │      │      │            │           │      │      │
 │               ├──────────────────────────────────────┘      │      │
 │               │      └───────────────────────────┬──────────┘      │
 │               │             └────────────────────│───────────────┬─┘
 │               │                          │       │               │
 │               v                          │       v               v
 │          parameter: m                    │  parameter: v    parameter: v
 │   (define (dispatch m)                   │   (set! x v)      (set! y v)
 │        (cond ((eq? m 'car) x)            │
 │              ((eq? m 'cdr) y)            ^
 │              ((eq? m 'set-car!) set-x!)  │
 │              ((eq? m 'set-cdr!) set-y!)  │
 │              (else ... )))               │
 ^                                          │
 │                                          └─────────┐
 ├─────────┐                                          │
 │         │   call set-car!                          │
 │      ┌───────────────────────────┐                 │
 │      │z:┘                        │                 ^
 │ E3 ─>│new-value: 17              ├─> global env    │
 │      │                           │                 │
 │      └───────────────────────────┘                 │
 │                                                    │
 │                                        ┌───────────┘
 │                         call to cdr    │
 │                ┌───────────────────────────┐
 │                │z:─────────────────────┘   │
 │           E4 ─>│                           ├─> global env
 │                │                           │
 │                └───────────────────────────┘
 │
 │
 │                               call to z (dispatch)
 │                          ┌───────────────────────────┐
 │                          │m: 'cdr                    │
 │                     E5 ─>│                           ├─> E2
 │                          │                           │
 │                          └───────────────────────────┘
 │                           (returns 'x' (E1 dispatch))
 │
 ^
 │
 │                    call to z (dispatch)
 │                ┌───────────────────────────┐
 │                │m: 'set-car                │
 │           E6 ─>│                           ├─> E1
 │                │                           │
 │                └───────────────────────────┘
 │
 │
 │                                 call to set-x!
 │                          ┌───────────────────────────┐
 │                          │v: 17                      │
 │                     E7 ─>│                           ├─> E1
 │                          │                           │
 │                          └───────────────────────────┘
 │                                 (E1 modified)
 ^
 │
 └─────────┐
           │     call to car
        ┌───────────────────────────┐
        │z:┘                        │
   E8 ─>│                           ├─> global env
        │                           │
        └───────────────────────────┘


                      call to z (dispatch)
                  ┌───────────────────────────┐
                  │m: 'car                    │
             E9 ─>│                           ├─> E1
                  │                           │
                  └───────────────────────────┘
                         (returns 17)

seok

What an awesome drawing by codybartfast!

I just want to point out that E5 should be E3, E3 should be E4 and E4 should be E5 in the diagram above. During the evaluation of (set-car! (cdr z) 17), the environment for set-car! is first constructed and the next is the environment for cdr. Refer to Figure 3.5 in 2nd edition for a similar case.

Thank you very much for detailed correction and reference to fig 3.5. I've updated the diagram above and I hope it properly incorporates your correction. Cheers!