Home > Archive > Scheme > December 2006 > Help>>>SICP>>>exercise 3.10
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Help>>>SICP>>>exercise 3.10
|
|
| netawater 2006-11-25, 10:05 pm |
| Exercise 3.10. In the make-withdraw procedure, the local variable
balance is created as a
parameter of make-withdraw. We could also create the local state
variable explicitly, using
let, as follows:
(define (make-withdraw initial-amount)
(let ((balance initial-amount))
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))))
Recall from section 1.3.2 that let is simply syntactic sugar for a
procedure call:
(let ((<var> <exp> )) <body> )
is interpreted as an alternate syntax for
((lambda (<var> ) <body> ) <exp> )
Use the environment model to analyze this alternate version of
make-withdraw, drawing figures
like the ones above to illustrate the interactions
(define W1 (make-withdraw 100))
(W1 50)
(define W2 (make-withdraw 100))
Show that the two versions of make-withdraw create objects with the same
behavior. How do
the environment structures differ for the two versions?
Do let version & lambda version differ for the environment?
Does interpreter just do a simple displacement?
| |
| Marlene Miller 2006-11-26, 4:20 am |
| "netawater" wrote
> Do let version & lambda version differ for the environment?
> Does interpreter just do a simple displacement?
"Incidentally, a let expression is nothing more than the direct application
of a lambda expression to a set of argument expressions." (section 2.5)
"In fact, a let expression is a syntactic extension defined in terms of
lambda and procedure application, which are both core syntactic forms."
(section 2.5)
"A Scheme implementation expands syntactic extensions into core forms as the
first step of compilation or interpretation, allowing the rest of the
compiler or interpreter to focus only on the core forms." (section 3.1)
quotes from The Scheme Programming Language http://www.scheme.com/tspl3/
| |
| Marlene Miller 2006-11-26, 10:01 pm |
| > Do let version & lambda version differ for the environment?
> Does interpreter just do a simple displacement?
What does the R5RS have to say about transforming let to lambda...
"Expression types are categorized as primitive or derived. [...] Derived
expression types are not symantically primitive, but can instead be defined
as macros." (R5RS 4 [.0])
"This section gives macro definitions for the derived expression types in
terms of the primitive expression types (literal, variables, call, lambda,
if, set!) [...] (define-syntax let [...]" (R5RS 7.3)
See section 4.2. Derived Expression Types, 4.2.2 Binding constructs, (let
[...] and notice the Semantics does not mention lambda.
http://www.schemers.org/Documents/Standards/R5RS/HTML/
- - - - - - - - - -
"Many of the special forms specified in this report can be translated into
more basic special forms. For example, let expressions can be translated
into procedure calls and lambda expressions. [...] Special forms like let
expressions are called derived forms because their semantics can be derived
from that of other kinds of forms by a syntactic transformation." (Revised
5.91 Scheme, section 1.8.)
"The keyword let could be defined in terms of lambda and letrec using
syntax-rules (see section 9.21) as follows: (define-syntax let [...]"
(Revised 5.91 Scheme, section 9.19.)
http://www.r6rs.org/r6rs_91.pdf
| |
| Marlene Miller 2006-11-26, 10:01 pm |
| > Do let version & lambda version differ for the environment?
> Does interpreter just do a simple displacement?
I noticed in EOPL the interpreters do not evaluate a let as a transformed
lambda.
"The first strategy is the use of {interpreters} to explain the run-time
behavior of programs in a given language. Interpreters express language
design decisions in a manner that is both formal (unambiguous and complete)
and executable. Furthermore, our interpreters are generally expressed in a
fashion consistent with the principles of denotational semantics; they
express key ideas of denotational semantics in a concrete way." Essentials
of Programming Languages, Preface 1st edition
http://www.cs.indiana.edu/eip/eopl.html
(define eval-expression
(lambda (exp env)
(cases expression exp
[...]
(let-exp (ids rands body)
(let ((args (eval-rands rands env)))
(eval-expression body (extend-env ids args env))))
The arguments (rands) are evaluated in the current environment, the
environment is extended with the let variables and values, and then the body
is evaluated in the extended environment.
(Essentials of Programming Languages 2nd edition, 3.4 Local Binding, page
8.3, Figure 3.6)
http://www.cs.indiana.edu/eopl/
In EOPL, let is discussion before lambda. Maybe that is why they do not
evaluate let in terms of lambda. I am not sure.
(The authors have been distributing drafts of the 3rd edition to their
students this year.)
| |
| netawater 2006-11-27, 8:03 am |
| "Marlene Miller" <marlenemiller@worldnet.att.net> writes:
>
> I noticed in EOPL the interpreters do not evaluate a let as a
> transformed
> lambda.
>
> "The first strategy is the use of {interpreters} to explain the run-time
> behavior of programs in a given language. Interpreters express language
> design decisions in a manner that is both formal (unambiguous and
> complete)
> and executable. Furthermore, our interpreters are generally expressed in
> a
> fashion consistent with the principles of denotational semantics; they
> express key ideas of denotational semantics in a concrete way."
> Essentials
> of Programming Languages, Preface 1st edition
>
> http://www.cs.indiana.edu/eip/eopl.html
>
> (define eval-expression
> (lambda (exp env)
> (cases expression exp
> [...]
> (let-exp (ids rands body)
> (let ((args (eval-rands rands env)))
> (eval-expression body (extend-env ids args env))))
>
> The arguments (rands) are evaluated in the current environment, the
> environment is extended with the let variables and values, and then the
> body
> is evaluated in the extended environment.
>
> (Essentials of Programming Languages 2nd edition, 3.4 Local Binding,
> page
> 8.3, Figure 3.6)
>
> http://www.cs.indiana.edu/eopl/
>
> In EOPL, let is discussion before lambda. Maybe that is why they do not
> evaluate let in terms of lambda. I am not sure.
>
> (The authors have been distributing drafts of the 3rd edition to their
> students this year.)
Thank you very much for your detailed reply.
But how can I tell the difference from let with lambda if they are different,
or SICP has said "A let expression is simply syntactic sugar for the
underlying lambda application", so MIT Scheme treat they as the same thing.
| |
| Marlene Miller 2006-11-28, 4:06 am |
| "netawater" wrote
> But how can I tell the difference from let with lambda if they are
different,
> or SICP has said "A let expression is simply syntactic sugar for the
> underlying lambda application", so MIT Scheme treat they as the same
thing.
I wonder if maybe you are uncertain how to get started on Exercise 3.10.
(define (f a b)
(let ((x a) (y b))
(+ x y)))
(f 2 3) => 5
; alternate syntax for define
(define f
(lambda (a b)
(let ((x a) (y b))
(+ x y))))
(f 2 3) => 5
; alternate syntax for let
(define f
(lambda (a b)
((lambda (x y) (+ x y))
a b)))
(f 2 3) => 5
I suggest you rewrite the second version of make-withdraw using the
alternate syntax for let. Then follow the examples of the previous section
for evaluating lambda expressions and procedure application to draw the
environment diagrams. When you compare your diagrams with the ones in the
book for the first version, you will see an interesting difference in the
structure of the environment. The difference is not between let and lambda.
The difference occurs when the procedure is applied.
| |
| Marlene Miller 2006-11-28, 4:06 am |
| > The difference is not between let and lambda.
Well, that is not what I meant. What I meant was I think you are looking for
the environment difference in the wrong place. You can use the alternate
syntax for let. Draw the diagrams for the 3 interactions. You will see a
difference in the way the environment grows.
| |
| Marlene Miller 2006-11-29, 4:08 am |
| "netawater" wrote
[...]
> Show that the two versions of make-withdraw create objects with the same
> behavior. How do
> the environment structures differ for the two versions?
>
> Do let version & lambda version differ for the environment?
> Does interpreter just do a simple displacement?
I was wondering whether defining let in terms of lambda was special to
Scheme. Here are some interesting comments...
Theories of Programming Languages, John C. Reynolds, page 229.
The Formal Semantics of Programming Languages, Glynn Winskel, page 132.
Types and Programming Languages, Benjamin C. Pierce, page 124.
| |
| netstandin-002@yahoo.com.cn 2006-11-29, 8:04 am |
| "Marlene Miller" <marlenemiller@worldnet.att.net> writes:
> "netawater" wrote
> different,
> thing.
>
> I wonder if maybe you are uncertain how to get started on Exercise 3.10.
>
> (define (f a b)
> (let ((x a) (y b))
> (+ x y)))
>
> (f 2 3) => 5
>
> ; alternate syntax for define
> (define f
> (lambda (a b)
> (let ((x a) (y b))
> (+ x y))))
>
> (f 2 3) => 5
>
> ; alternate syntax for let
> (define f
> (lambda (a b)
> ((lambda (x y) (+ x y))
> a b)))
>
> (f 2 3) => 5
>
> I suggest you rewrite the second version of make-withdraw using the
> alternate syntax for let. Then follow the examples of the previous
> section
> for evaluating lambda expressions and procedure application to draw the
> environment diagrams. When you compare your diagrams with the ones in
> the
> book for the first version, you will see an interesting difference in
> the
> structure of the environment. The difference is not between let and
> lambda.
> The difference occurs when the procedure is applied.
Yes, you got my point, thank you very much!
Please check my diagrams:
;lambda version.
;global env:make-withdraw W2 W1
; | | | | | |
; @@--- | | | E1:initial-amount=100
; | | | @@-------|
; paramters:intial-amount | | |
; body:... | | paramters:void
; | | body:...
; @@-E2:initial-amount=100
; |
; paramters:void
; body:...
| |
| netawater 2006-11-29, 8:04 am |
| Sorry, error name for modifying gnu.el.
| |
| Marlene Miller 2006-11-30, 4:16 am |
| > Yes, you got my point, thank you very much!
Good. You are welcome.
> Please check my diagrams:
> ;lambda version.
> ;global env:make-withdraw W2 W1
> ; | | | | | |
> ; @@--- | | |
E1:initial-amount=100
> ; | | | @@-------|
> ; paramters:intial-amount | | |
> ; body:... | | paramters:void
> ; | | body:...
> ; @@-E2:initial-amount=100
> ; |
> ; paramters:void
> ; body:...
This part needs some work: paramters:void
- - - - - - - - - -
(define (make-withdraw-2 initial-amount)
(let ((balance initial-amount))
(lambda (amount)
(- balance amount))))
(make-withdraw-2 200) => #<procedure>
((make-withdraw-2 200) 20) => ?
The value of the expression (make-withdraw-2 200) is a procedure object. I
can apply the procedure object to the value 20. The procedure has a
parameter. What is the parameter - initial amount? balance? amount?
| |
| netawater 2006-11-30, 8:01 am |
| "Marlene Miller" <marlenemiller@worldnet.att.net> writes:
>
> Good. You are welcome.
>
> E1:initial-amount=100
>
> This part needs some work: paramters:void
>
> - - - - - - - - - -
> (define (make-withdraw-2 initial-amount)
> (let ((balance initial-amount))
> (lambda (amount)
> (- balance amount))))
>
> (make-withdraw-2 200) => #<procedure>
> ((make-withdraw-2 200) 20) => ?
>
> The value of the expression (make-withdraw-2 200) is a procedure
> object. I
> can apply the procedure object to the value 20. The procedure has a
> parameter. What is the parameter - initial amount? balance? amount?
Please check my revised version, thanks,:)
; global env: W1
; | |
; | E1: lambda function, initial-mount = 100
; | |
; | | |>E2: balance = 100
; | @@----------
; | |
; |---------->paramters:amount
; body:...
| |
| Steve VanDevender 2006-12-01, 4:08 am |
| "Marlene Miller" <marlenemiller@worldnet.att.net> writes:
> - - - - - - - - - -
> (define (make-withdraw-2 initial-amount)
> (let ((balance initial-amount))
> (lambda (amount)
> (- balance amount))))
>
> (make-withdraw-2 200) => #<procedure>
> ((make-withdraw-2 200) 20) => ?
>
> The value of the expression (make-withdraw-2 200) is a procedure object. I
> can apply the procedure object to the value 20. The procedure has a
> parameter. What is the parameter - initial amount? balance? amount?
(make-withdraw-2 200) will give you the procedure object:
(lambda (amount)
(- balance amount))
So applying that procedure to an argument binds its parameter "amount"
to the argument value. "balance" has been bound to 200 before the
procedure object is created.
In Scheme it owuld be entirely equivalent to write this as
(define make-withdraw-2
(lambda (initial-amount)
((lambda (balance)
(lambda (amount)
(- balance amount)))
initial-amount)))
--
Steve VanDevender "I ride the big iron" http://hexadecimal.uoregon.edu/
stevev@hexadecimal.uoregon.edu PGP keyprint 4AD7AF61F0B9DE87 522902969C0A7EE8
Little things break, circuitry burns / Time flies while my little world turns
Every day comes, every day goes / 100 years and nobody shows -- Happy Rhodes
| |
| Marlene Miller 2006-12-01, 4:08 am |
| > Please check my revised version, thanks,:)
>
> ; global env: W1
> ; | |
> ; | E1: lambda function, initial-mount = 100
> ; | |
> ; | | |>E2: balance = 100
> ; | @@----------
> ; | |
> ; |---------->paramters:amount
> ; body:...
This is not correct.
E1: lambda function, initial-mount = 100
lambda function? Are you guessing?
Maybe you are not clear about how to evaluate expressions like this:
(lambda (a b)
((lambda (x y) (+ x y)) a b))
((lambda (a b)
((lambda (x y) (+ x y)) a b)) 1 2)
If so, you might try experimenting in an interactive Scheme environment. Or
you might try rereading the previous sections with expressions like this in
mind. Or you might try explaining your diagram to a friend using the rules
for procedure application and procedure creation. Or you might try writing
down the sequence of steps it takes to evaluate such an expression.
What I am trying to get at is, be careful and meticulous about following the
evaluation rules. Extend the environment at the exact place where they say
to. Bind the parameters to the arguments where they say. Create a procedure
where they say. Your diagram is missing some pieces.
| |
| netawater 2006-12-02, 8:01 am |
| "Marlene Miller" <marlenemiller@worldnet.att.net> writes:
>
> This is not correct.
>
> E1: lambda function, initial-mount = 100
> lambda function? Are you guessing?
>
> Maybe you are not clear about how to evaluate expressions like this:
>
> (lambda (a b)
> ((lambda (x y) (+ x y)) a b))
>
> ((lambda (a b)
> ((lambda (x y) (+ x y)) a b)) 1 2)
>
> If so, you might try experimenting in an interactive Scheme
> environment. Or
> you might try rereading the previous sections with expressions like this
> in
> mind. Or you might try explaining your diagram to a friend using the
> rules
> for procedure application and procedure creation. Or you might try
> writing
> down the sequence of steps it takes to evaluate such an expression.
>
> What I am trying to get at is, be careful and meticulous about following
> the
> evaluation rules. Extend the environment at the exact place where they
> say
> to. Bind the parameters to the arguments where they say. Create a
> procedure
> where they say. Your diagram is missing some pieces.
The question may be less complex than I think.
Besides book's version for make-withdraw, there are two other version.
(define (make-withdraw initial-amount)
(let ((balance initial-amount))
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))))
;global env: make-withdraw
; | |
; | |
; @@--->E1:balance = initial-amount
; |
; parameter:intial-amount
; body:...
(define (make-withdraw initial-amount)
((lambda (balance)
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds")))
initial-amount)
)
;global env: make-withdraw
; | |
; | |
; @@----
; |
; parameter:intial-amount
; body:...
Are these correct? Sorry for trouble you!
| |
| Marlene Miller 2006-12-02, 10:02 pm |
| > The question may be less complex than I think.
I see this exercise as applying the rules described in the previous
sections. It's more difficult than the examples because there are more
lambda expressions to evaluate and procedure objects to apply. I don't think
it is tricky. You have to be meticulous about doing all the steps and in the
right order. In the next chapter you will write code to do the same thing
and it will take only a few lines. It's good to work on this problem. When
you feel comfortable about evaluating lambda expressions and procedure
applications, then the next chapter where you write an interpreter to
evaluate the expressions will make sense.
> Besides book's version for make-withdraw, there are two other version.
>
> (define (make-withdraw initial-amount)
> (let ((balance initial-amount))
> (lambda (amount)
> (if (>= balance amount)
> (begin (set! balance (- balance amount))
> balance)
> "Insufficient funds"))))
>
> ;global env: make-withdraw
> ; | |
> ; | |
> ; @@--->E1:balance = initial-amount
> ; |
> ; parameter:intial-amount
> ; body:...
>
I don't see anything in the book about drawing environment diagrams for let
expressions. There is a diagram for lambda expression and a diagram for
procedure application. So I cannot say whether this diagram is correct or
not.
> (define (make-withdraw initial-amount)
> ((lambda (balance)
> (lambda (amount)
> (if (>= balance amount)
> (begin (set! balance (- balance amount))
> balance)
> "Insufficient funds")))
> initial-amount)
> )
>
> ;global env: make-withdraw
> ; | |
> ; | |
> ; @@----
> ; |
> ; parameter:intial-amount
> ; body:...
>
> Are these correct? Sorry for trouble you!
I don't see any arrows, so I am not sure what is pointing to what. Otherwise
this looks to me like a correct diagram for the "define" expression. The
procedure object is attached to/points to the global environment. That's an
important idea to learn. When a procedure is created, it "remembers" the
current environment. That environment will be extended when the procedure is
later applied.
Where are the three other diagrams for the three "interactions"?
(define w1 (make-withdraw 100))
(w1 50)
(define w2 (make-withdraw 100))
When you evaluate a lambda expression, the value is a procedure object. Make
sure to get the procedure parameters correct and make sure to attach/point
the procedure to the correct environment. When you evaluate a procedure
application, make sure to extend the current environment and bind the
procedure parameters to the arguments.
| |
| Marlene Miller 2006-12-03, 4:29 am |
| > When you evaluate a procedure
> application, make sure to extend the CORRECT environment and bind the
> procedure parameters to the arguments.
errata.
| |
| netawater 2006-12-03, 8:04 am |
| "Marlene Miller" <marlenemiller@worldnet.att.net> writes:
>
> I see this exercise as applying the rules described in the previous
> sections. It's more difficult than the examples because there are more
> lambda expressions to evaluate and procedure objects to apply. I don't think
> it is tricky. You have to be meticulous about doing all the steps and in the
> right order. In the next chapter you will write code to do the same thing
> and it will take only a few lines. It's good to work on this problem. When
> you feel comfortable about evaluating lambda expressions and procedure
> applications, then the next chapter where you write an interpreter to
> evaluate the expressions will make sense.
Thanks, I will try my best.
>
>
> I don't see anything in the book about drawing environment diagrams for let
> expressions. There is a diagram for lambda expression and a diagram for
> procedure application. So I cannot say whether this diagram is correct or
> not.
It is just my own idea for let expression, :)
>
> I don't see any arrows, so I am not sure what is pointing to what. Otherwise
> this looks to me like a correct diagram for the "define" expression. The
> procedure object is attached to/points to the global environment. That's an
> important idea to learn. When a procedure is created, it "remembers" the
> current environment. That environment will be extended when the procedure is
> later applied.
;global env: make-withdraw<|
; | |
; | |
; |> @@----
; |
; |>parameter:intial-amount
; body:...
>
> Where are the three other diagrams for the three "interactions"?
> (define w1 (make-withdraw 100))
> (w1 50)
> (define w2 (make-withdraw 100))
>
> When you evaluate a lambda expression, the value is a procedure object. Make
> sure to get the procedure parameters correct and make sure to attach/point
> the procedure to the correct environment. When you evaluate a procedure
> application, make sure to extend the current environment and bind the
> procedure parameters to the arguments.
;use let version
;global env: W1<|
; | |
; | |>E1: balance = initial-amount
; | |>E2: initial-amount = 100<|
; |>@@ |>E3 amount = 50
; |>parmaters: amount (if (>= balance amount)
; |>body: ... (begin (set! balance (- balance amount))
; balance)
; "Insufficient funds")))
;global env: W2<|
; | |
; | |>E1: balance = initial-amount
; | |>E4: initial-amount = 100
; |>@@
; |>parmaters: amount
; |>body: ...
;
|
|
|
|
|