Archives


« Prev:

» Next:


SICP section 3.2

September 28th, 2007 at 6:06 pm

I’m using the excellent online Visio clone Gliffy to draw the diagrams for this section. It takes quite a long time to draw them, but understanding these diagrams is very important. If you’re still not 100% clear on what is exactly meant by lexical scope, read this section several times until you understand.

For those who already understand what it is and how the real evaluation model of Lisp works, constructing these diagrams is still important in order to understand the implementation of the Scheme evaluator in chapter 4 of the book.

Exercise 3.9

Since it’s tiresome to draw diagrams, I’ll assume the call is (factorial 3) instead of (factorial 6). It illustrates the point just the same. Here’s the environment for the recursive call:

The iterative version produces the following environment diagram:

Exercise 3.10

The result of defining make-withdraw is similar to figure 3.6 in the book, except for the body of the make-withdraw function which is a little different (as defined in the exercise).

The two versions of make-withdraw create objects with the same behavior. To demonstrate the subtle difference, it is enough to consider what happens when (define W1 (make-withdraw 100)) is evaluated:

Since let is equivalent to lambda, another environment is created – in which balance is defined. Now the W1 object has two “private” variables – balance and initial-amount, and both can be changed separately from one another.

Exercise 3.11

After the line:

(define acc (make-account 50))

The environment is:

The call:

((acc 'deposit) 40)

Produces:

I removed the pointer from withdraw to the internal withdraw lambda in environment E1 for clarity. The call (acc 'deposit) evaluates to a call to dispatch with the argument deposit, which is depicted in environment E2. Note that the environment’s ancestor is E1 and not the global env, since this E1 is the env for acc.

I’ll skip the call to withdraw because it’s similar. The call:

(define acc2 (make-account 100))

Generates (the balance of E1 is the result of the deposit and withdraw):

The accounts in acc and acc2 are distinct because each one has an environment of its own. In drawing this diagram I assumed that the code is shared, although this is an implementation detail, as explained in footnote 15 in the book.

Related posts:

  1. SICP section 3.1.1
  2. SICP 3.4
  3. SICP section 1.2.2
  4. SICP section 3.3.1
  5. SICP section 3.3.3

This entry was posted on Friday, September 28th, 2007 at 18:06 and is filed under SICP. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

19 Responses to “SICP section 3.2”

  1. Debi KNo Gravatar Says:
    October 16th, 2007 at 18:58

    Thanks for using Gliffy for your diagrams. We value any feedback or suggestions you have based on your use ~ Best, debik (at) gliffy (dot) com

  2. SiberiaNo Gravatar Says:
    June 17th, 2008 at 09:18

    Can’t believe you really draw these pictures! Awesome.

  3. SiberiaNo Gravatar Says:
    June 17th, 2008 at 16:10

    You are the only one posting these diagrams for the exercises of SICP in the whole web. You’re so diligent.

  4. SiberiaNo Gravatar Says:
    June 18th, 2008 at 07:35

    I believe there is a flaw in your diagram for exercise for exercise 3.10

  5. elibenNo Gravatar Says:
    June 20th, 2008 at 07:23

    Siberia,

    Could you please be more specific about the diagram – where is there a flaw ?

  6. jtukiNo Gravatar Says:
    August 25th, 2008 at 19:04

    Thx for sharing all these answers. :)

    I think the parameter of make-withdraw in 3.10 should be initial-amount rather than balance.

  7. elibenNo Gravatar Says:
    August 28th, 2008 at 18:54

    jtuki: I think you’re right, but I just can’t force myself to go back drawing those horrible diagrams :-)
    If someone will be kind enough to send me a fixed diagram, I’ll gladly post it ;-)

  8. SumeetNo Gravatar Says:
    January 3rd, 2009 at 20:46

    Hi Eli,

    Your diagrams aren’t visible on my browser. In safari, it shows a blue question mark, and in firefox it simply doesn’t display anything. When I browsed to know the cause of this problem, most forums said it has to do with the website designer. Could you please let me know the solution in case you know it?

    Btw, I owe you a great thanks. You have done a wonderful job by posting such nice explanatory solutions to SICP.

  9. elibenNo Gravatar Says:
    January 3rd, 2009 at 21:17

    @Sumeet,

    It was my problem, indeed. Fixed it – and I hope you can see them now.

  10. SumeetNo Gravatar Says:
    January 3rd, 2009 at 22:56

    Yeah, they are visible now! Thanks a lot!

  11. ndNo Gravatar Says:
    January 17th, 2009 at 23:49

    Could you explain a solution to ex. 3.10 please?

    As far as I understand, if (let ((var value)) body) is the same as ((lambda (var) body) value), then we have to apply this lambda to argument value, so isn’t new environment created when we define make-withdraw procedure (with binding something like balance = initial-amount)?

  12. SICP LoverNo Gravatar Says:
    February 26th, 2009 at 17:47

    Dear Eli,

    In my opinion, there is an error in your iterative diagram for exercise 3.9. I think there should be an additional environment where product:6, counter:4 and max-count:3.

    What do you think?

    Greetings,
    SICP Lover

  13. elibenNo Gravatar Says:
    February 27th, 2009 at 08:47

    @SICP Lover,

    I’m not sure, as for that call the function returns.

  14. PeterNo Gravatar Says:
    March 14th, 2009 at 07:59

    Hi Eli:
    Why do acc and acc2 share
    ”
    parameters:m
    body:
    body of dispatch
    ”
    ?
    I think they share no parameter and only “dispatch”,because the body of dispatch is ‘defined’ in procedure make-account.The body of dispatch is a part of E1 and E2.
    What do you think about this?
    ————————–
    Sorry for my bad English skill.And I read the Chinese version SICP so some words might be wrong…
    ————————–
    And thx very much for sharing the solutions of SICP~

  15. elibenNo Gravatar Says:
    March 14th, 2009 at 08:21

    @Peter,

    acc and acc2 share the same code, but differ in the environment. The code object has m as an argument and the body of dispatch.

    Try to understand the authors’ explanation of figure 3.10, I think it’s a similar case.

  16. PeterNo Gravatar Says:
    March 14th, 2009 at 08:37

    Oh…Maybe I should try to explain my tought better^_^
    They share the same code.I think here “code” just means “dispatch”,and what dispatch means is explained in E1 & E2.
    I think if we use (lambda (m) …) style instead of (define (dispatch m)…) they will share the whole code but when dispatch is defined,they only share “dispatch” itself.
    Actually,I feel a little dizzy and confused…

  17. elibenNo Gravatar Says:
    March 14th, 2009 at 08:59

    When dispatch is defined explicitly, there’s no difference from returning a lambda, because the code object is returned anyway. This code object has an argument and a body, so it’s just like a lambda.

  18. PeterNo Gravatar Says:
    March 14th, 2009 at 09:09

    I see…
    Thank you for making it clear to me!
    Now I know how it runs~
    But does it mean that the “dispatch” in E1 & E2 would never be used?Will the shared body call withdraw and deposit in E1 & E2 directly?

  19. elibenNo Gravatar Says:
    March 14th, 2009 at 09:17

    @Peter,

    I’m not sure. Perhaps it would for recursive calls to dispatch, if there were any.