Home > Archive > Scheme > January 2006 > Difference between let, let* and letrec
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 |
Difference between let, let* and letrec
|
|
| bobueland@yahoo.com 2006-01-22, 10:00 pm |
| In R5RS they have an example of letrec as follows
(letrec ((even?
(lambda (n)
(if (zero? n)
#t
(odd? (- n 1)))))
(odd?
(lambda (n)
(if (zero? n)
#f
(even? (- n 1))))))
(even? 88))
Evaluating this In DrScheme gives #t. Changing the word letrec to let
(or to let*) gives exactly the same answer. So is there no use for
letrec or is the example given not good enough for showing the
necessity of letrec, or has this to do with implementation of DrScheme,
or ..??
Bob
| |
| Lauri Alanko 2006-01-22, 10:00 pm |
| In article <1137948463.097368.94850@g43g2000cwa.googlegroups.com>,
<bobueland@yahoo.com> wrote:
> In R5RS they have an example of letrec as follows
[even? and odd? defined with mutual recursion]
> Evaluating this In DrScheme gives #t. Changing the word letrec to let
> (or to let*) gives exactly the same answer.
This is because even? and odd? are names of standard procedures so the
variables are already bound at top level, so when using let instead of
letrec, you are defining your own odd? in terms of the _standard_
even?, and vice versa. Try changing the names of the variables in your
own code to something else.
Lauri
| |
| bobueland@yahoo.com 2006-01-22, 10:00 pm |
| Lauri Alanko wrote:
> This is because even? and odd? are names of standard procedures so the
> variables are already bound at top level,
Thanks Lauri
I've changed even? -> ev? and odd? -> od? and now it works.
| |
| bobueland@yahoo.com 2006-01-22, 10:00 pm |
| OK now that the following code
(let ((ev?
(lambda (n)
(if (zero? n)
#t
(od? (- n 1)))))
(od?
(lambda (n)
(if (zero? n)
#f
(ev? (- n 1))))))
(ev? 88))
brakes down giving the error "reference to undefined identifier: od?"
I'm trying to understand why. The syntax for let is
(let ((<var1> <exp1> )
(<var2> <exp2> ))
<body> )
In my case var1 is ev? and exp1 is the procedure
(lambda (n)
(if (zero? n)
#t
(od? (- n 1))))
So I have a procedure called od? which is defined a bit later in the
code. But so what
When you are defining only procedures, the order of definitions does
not matter. Hence both
(define (g x) (+ (f x) 2))
(define (f x) (+ x 1))
and
(define (f x) (+ x 1))
(define (g x) (+ (f x) 2))
are fine.
However, the order for variable definitions is significant. Therefore,
(define x 5)
(define y (* 2 x))
is fine, but
(define y (* 2 x))
(define x 5)
produces the error "reference to undefined identifier: x".
But in my case od? is a procedure, so the order wouldn't matter? I'm
missing something here??
| |
| Marlene Miller 2006-01-22, 10:00 pm |
|
<bobueland@yahoo.com> wrote in message
news:1137948463.097368.94850@g43g2000cwa.googlegroups.com...
> In R5RS they have an example of letrec as follows
>
> (letrec ((even?
> (lambda (n)
> (if (zero? n)
> #t
> (odd? (- n 1)))))
> (odd?
> (lambda (n)
> (if (zero? n)
> #f
> (even? (- n 1))))))
> (even? 88))
>
> Evaluating this In DrScheme gives #t. Changing the word letrec to let
> (or to let*) gives exactly the same answer. So is there no use for
> letrec or is the example given not good enough for showing the
> necessity of letrec, or has this to do with implementation of DrScheme,
> or ..??
>
> Bob
>
"The Seasoned Schemer" might be a good book for learning about letrec.
| |
| bobueland@yahoo.com 2006-01-22, 10:00 pm |
| I'm trying to reply to my own mail
Since let is just syntactic sugar for lambda expression, the expression
(let ((ev? (lambda (n) (if (zero? n) #t (od? (- n 1)))))
(od? (lambda (n) (if (zero? n) #f (ev? (- n 1))))))
(ev? 88))
can be rewritten as
((lambda (ev? od?)
(ev? 88))
(lambda (n)
(if (zero? n) #t (od? (- n 1))))
(lambda (n)
(if (zero? n) #f (ev? (- n 1)))))
When trying to evaluate we use the substitution model on the body
(ev? 88) and get (since od? has no part in body)
((lambda (n) (if (zero? n) #t (od? (- n 1)))) 88)
But now trying to evaluate this we clearly see that od? is not defined.
Is this thinking correct?
Bob
| |
| Max Hailperin 2006-01-22, 10:00 pm |
| bobueland@yahoo.com writes [but I inserted one comment]:
....
> Since let is just syntactic sugar for lambda expression, the expression
>
> (let ((ev? (lambda (n) (if (zero? n) #t (od? (- n 1)))))
> (od? (lambda (n) (if (zero? n) #f (ev? (- n 1))))))
> (ev? 88))
>
> can be rewritten as
>
> ((lambda (ev? od?)
> (ev? 88)) ; <- Here is where the scope of ev? and od? ends
> (lambda (n)
> (if (zero? n) #t (od? (- n 1))))
> (lambda (n)
> (if (zero? n) #f (ev? (- n 1)))))
>
> When trying to evaluate we use the substitution model on the body
>
> (ev? 88) and get (since od? has no part in body)
>
> ((lambda (n) (if (zero? n) #t (od? (- n 1)))) 88)
>
> But now trying to evaluate this we clearly see that od? is not defined.
>
> Is this thinking correct?...
Yes, though you don't even need to do the substitution. Once you've
rewritten the let expression as an application of a lambda expression,
you can take a look at what the scope is of each binding. The names
ev? and od? are bound by the first lambda; their scope ends with
the second right parenthesis on the next line, as I have marked. The
uses of od? on the fourth line and ev? on the sixth line are outside
this scope. -max
| |
| bobueland@yahoo.com 2006-01-22, 10:00 pm |
| Thanks Max, you're quite right, it's easier to see it the way you
explained. However here's a new question, regarding what let. let* and
letrec are sugar of.
We know that
(let ((var1 exp1)
(var2 exp2))
body)
is sugar for:
((lambda (var1 var2)
body)
exp1 exp2)
My guess is that
(let* ((var1 exp1)
(var2 exp2))
body)
is sugar for:
((lambda (var1)
(lambda (var2)
body)
exp1) exp2)
Is that correct?
What is letrec sugar of?
| |
| Abdulaziz Ghuloum 2006-01-22, 10:00 pm |
| bobueland@yahoo.com wrote:
> Thanks Max, you're quite right, it's easier to see it the way you
> explained. However here's a new question, regarding what let. let* and
> letrec are sugar of.
>
> We know that
> (let ((var1 exp1)
> (var2 exp2))
> body)
>
> is sugar for:
>
> ((lambda (var1 var2)
> body)
> exp1 exp2)
>
> My guess is that
>
> (let* ((var1 exp1)
> (var2 exp2))
> body)
>
> is sugar for:
>
> ((lambda (var1)
> (lambda (var2)
> body)
> exp1) exp2)
>
> Is that correct?
Yes.
> What is letrec sugar of?
(letrec ([x* v*] ...) b b* ...)
==
(let ([x* #f] ...)
(let ([t* v*] ...)
(set! x* t*) ...
b b* ...))
| |
| bobueland@yahoo.com 2006-01-22, 10:00 pm |
| I don't quite follow. First you are setting x* to false. Then you
introduce a temporary variable t*, that you set to v*, and then you
set x* to the t*. Why don't you set x* to v* directly. Could you
explain how the original
(letrec ((ev?
(lambda (n)
(if (zero? n)
#t
(od? (- n 1)))))
(od?
(lambda (n)
(if (zero? n)
#f
(ev? (- n 1))))))
(ev? 8))
would work with your equivalence.
-----
Remark
I was expecting that
(letrec ((var1 exp1) (var2 exp2))
body)
was sugar for something like
(lambda (var1 var2)
(set! var1 exp1)
(set! var2 exp2)
body)
But I don't get it since exp1 and exp2 are normally procedures in this
context so var1 and var2 are pointer to procedures, so if we go back to
ev? and od? case we would get
(lambda (ev? od?)
(set! ev? (lambda ...)
(set! od? (lambda ...)
(ev? 88))
which is nothing plausible?
Confused
| |
| ncruces@gmail.com 2006-01-22, 10:00 pm |
| It is plausible.
I would say:
(letrec ((ev? (lambda (n) (if (zero? n) #t (od? (- n 1)))))
(od? (lambda (n) (if (zero? n) #f (ev? (- n 1))))))
(ev? 8))
Is the same as:
((lambda (ev? od?)
(set! ev? (lambda (n) (if (zero? n) #t (od? (- n 1)))))
(set! od? (lambda (n) (if (zero? n) #f (ev? (- n 1)))))
(ev? 8)) (if #f #f) (if #f #f))
Where (if #f #f) represents "no particular value" or "undefined" - some
would use #f or (values) instead.
| |
| Pascal Bourguignon 2006-01-22, 10:00 pm |
| bobueland@yahoo.com writes:
> I was expecting that
>
> (letrec ((var1 exp1) (var2 exp2))
> body)
>
> was sugar for something like
>
> (lambda (var1 var2)
> (set! var1 exp1)
> (set! var2 exp2)
> body)
>
> But I don't get it since exp1 and exp2 are normally procedures in this
> context so var1 and var2 are pointer to procedures, so if we go back to
> ev? and od? case we would get
>
> (lambda (ev? od?)
> (set! ev? (lambda ...)
> (set! od? (lambda ...)
> (ev? 88))
>
> which is nothing plausible?
You mean:
(let (ev? od?)
(set! ev? (lambda ...))
(set! od? (lambda ...))
(ev? 88))
or:
((lambda (ev? od?)
(set! ev? (lambda ...))
(set! od? (lambda ...))
(ev? 88)) '() '())
--
__Pascal Bourguignon__ http://www.informatimago.com/
This universe shipped by weight, not volume. Some expansion may have
occurred during shipment.
| |
| bobueland@yahoo.com 2006-01-22, 10:00 pm |
| Pascal and ncruces. Both of you put some dummy variables at the end.
When I put them in DrScheme it works, but without them it doesn't work.
What role are they playing there? Explain slowly to a newbie.
Thanks
| |
| Max Hailperin 2006-01-22, 10:00 pm |
| Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> writes:
> bobueland@yahoo.com wrote:
>
> Yes....
Actually, no. I think you checked Bob's work too quickly, assuming
that if it looked approximately correct, then it is. The correct
expansion does include two lambdas. However, it is
((lambda (var1)
((lambda (var2)
body)
exp2))
exp1)
which is exactly what you would get if you expanded it first to
(let ((var1 exp1))
(let ((var2 exp2))
body))
and then used the previously mentioned expansion of let into
application of a lambda. -max
| |
|
|
bobueland@yahoo.com wrote:
> Pascal and ncruces. Both of you put some dummy variables at the end.
> When I put them in DrScheme it works, but without them it doesn't work.
> What role are they playing there? Explain slowly to a newbie.
>
> Thanks
I'm sure that they can explain with more precision specific to this
example, but the generic thing that is going on is that the dummy
variables are passed into the lambda.
For instance, if I type:
(lambda (x) (* x x))
I get something back that indicates a procedure, e.g.: #<procedure>
If I type:
( (lambda (x) (* x x)) 5 )
I get 25, because the first item is un-named procedure that takes the
square of a number, and the second item is the number itself. If I had
named the procedure square in a prior step, I could have typed (square
5), which is more legible; however, there are some cases for which
unnamed lambdas are definitely preferable.
| |
| bobueland@yahoo.com 2006-01-22, 10:00 pm |
|
H. wrote:
> ( (lambda (x) (* x x)) 5 )
> I get 25
So much I understand. But what bothers me is if you first set a
variable eq? to point to a procedure and then try to substitute the
empty list (or some other dummy value) for the same variable in order
to force the execution.
| |
| Abdulaziz Ghuloum 2006-01-22, 10:00 pm |
| Max Hailperin wrote:
> Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> writes:
>
>
>
>
> Actually, no. I think you checked Bob's work too quickly, assuming
> that if it looked approximately correct, then it is. The correct
> expansion does include two lambdas. However, it is
>
> ((lambda (var1)
> ((lambda (var2)
> body)
> exp2))
> exp1)
>
> which is exactly what you would get if you expanded it first to
>
> (let ((var1 exp1))
> (let ((var2 exp2))
> body))
>
> and then used the previously mentioned expansion of let into
> application of a lambda. -max
You're of course correct. I did check it too quickly.
Aziz,,,
| |
| ncruces@gmail.com 2006-01-22, 10:00 pm |
| I'm afraid it's the other way arround.
This lambda expression:
(lambda (ev? od?)
(set! ev? (lambda (n) (if (zero? n) #t (od? (- n 1)))))
(set! od? (lambda (n) (if (zero? n) #f (ev? (- n 1)))))
(ev? 8))
Returns a procedure that takes 2 arguments. However, this procedure
discards the value of those 2 arguments, by setting each of them to a
new value. Since it is a 2 argument procedure, you need to apply it to
2 arguments - it doesn't matter, though, what they are (since the
procedure will simply discard their values).
| |
| bobueland@yahoo.com 2006-01-23, 3:58 am |
| ncruces@gmail.com wrote:
> I'm afraid it's the other way arround.
>
> This lambda expression:
> (lambda (ev? od?)
> (set! ev? (lambda (n) (if (zero? n) #t (od? (- n 1)))))
> (set! od? (lambda (n) (if (zero? n) #f (ev? (- n 1)))))
> (ev? 8))
>
> Returns a procedure that takes 2 arguments. However, this procedure
> discards the value of those 2 arguments, by setting each of them to a
> new value. Since it is a 2 argument procedure, you need to apply it to
> 2 arguments - it doesn't matter, though, what they are (since the
> procedure will simply discard their values).
I guess my problem is that I try to use the substitution model here
which transforms
((lambda (ev? od?)
(set! ev? (lambda ...))
(set! od? (lambda ...))
(ev? 8)) dummy1 dummy2)
into
(set! dummy1 (lambda (n) ..))
(set! dummy2 (lambda (n ..)))
(dummy1 8)
Now if dummy1 and dummy2 are both '() you end up with something totally
unintelligable. But now I remember that in SICP they said something
that substitution model breaks down when you have set!
Now I try to figure out what's the right way of thinking when seeing
((lambda (ev? od?)
(set! ev? (lambda ...))
(set! od? (lambda ...))
(ev? 88)) dummy1 dummy2)
"We have an anonymous procedure (the first lambda) having two pointers
ev? and od? as arguments. Now it seems that those two pointers are not
there in order to provide input to the procedure (as is normally done)
but rather to provide pointers where the procedure can store its
output. But somehow Scheme being silly doesn't understand our
intention. It regards ev? and od? as input parameters so we have to
trick it by supplying dummy variables which are never used."
This way of thinking can't be right. People who designed Scheme
couldn't possible have done it this way. So I must be me who is
thinking in a silly way. Can somebody explain??
| |
| Pascal Bourguignon 2006-01-23, 3:58 am |
| bobueland@yahoo.com writes:
> Now I try to figure out what's the right way of thinking when seeing
>
> ((lambda (ev? od?)
> (set! ev? (lambda ...))
> (set! od? (lambda ...))
> (ev? 88)) dummy1 dummy2)
>
> "We have an anonymous procedure (the first lambda) having two pointers
> ev? and od? as arguments. Now it seems that those two pointers are not
> there in order to provide input to the procedure (as is normally done)
> but rather to provide pointers where the procedure can store its
> output. But somehow Scheme being silly doesn't understand our
> intention. It regards ev? and od? as input parameters so we have to
> trick it by supplying dummy variables which are never used."
What are dummy1 and dummy2 ?
If they're not defined, you'll get an error.
I didn't write dummy1, I wrote '().
If you don't want to bind a determined value, it has been showed you
how to generate a void value: (if #f #f).
(define void (if #f #f))
Note that:
(let (x) (display x)) --> let: bad syntax in: x
And:
((lambda (x) (display x))) --> too few arguments given to lambda
You MUST give it an argument!
(define void (if #f #f))
((lambda (x) (display x)) void)
> This way of thinking can't be right. People who designed Scheme
> couldn't possible have done it this way. So I must be me who is
> thinking in a silly way. Can somebody explain??
The point is that lambda do two things:
- it requires and accepts arguments,
- it binds these arguments to the parameters.
--
__Pascal Bourguignon__ http://www.informatimago.com/
IMPORTANT NOTICE TO PURCHASERS: The entire physical universe,
including this product, may one day collapse back into an
infinitesimally small space. Should another universe subsequently
re-emerge, the existence of this product in that universe cannot be
guaranteed.
| |
| bobueland@yahoo.com 2006-01-23, 3:58 am |
| >I didn't write dummy1, I wrote '().
The dummy I wrote was not intended as a variable but as '() or 6 or 9
or "a" or .. No matter what *value* I write there the right value is
evaluated.
(But without writing something there I don't get the right value, so
Scheme forces me to give some dummy values that it doesn't use.)
>The point is that lambda do two things:
> it requires and accepts arguments,
> it binds these arguments to the parameters.
If you give it the arguments '() '() as you suggested (see code below),
in what way does it bind these argument to the parameters ev? and od?
?
((lambda (ev? od?)
(set! ev? (lambda ...))
(set! od? (lambda ...))
(ev? 8)) '() '())
| |
| bobueland@yahoo.com 2006-01-23, 3:58 am |
| ((lambda (ev? od?)
(set! ev? (lambda ...))
(set! od? (lambda ...))
(ev? 8)) '() '())
Could it be that first ev? and od? get '() bound to them, but later
these values are overwritten by the set!. That would explain it. And
the reason why Scheme is asking for "dummy values" is that it doesn't
like dangling pointers.
If my reasoning is correct then the substitution
(lambda ('() '())
(set! ev? (lambda ...))
(set! od? (lambda ...))
(ev? 8))
is correct, but not the substitution
(lambda ('() '())
(set! '() (lambda ...))
(set! '() (lambda ...))
('() 8))
But still that leaves the question of when can I substitute the
arguments into the body and when not.
| |
| Pascal Bourguignon 2006-01-23, 7:58 am |
| bobueland@yahoo.com writes:
> If you give it the arguments '() '() as you suggested (see code below),
> in what way does it bind these argument to the parameters ev? and od?
> ?
>
> ((lambda (ev? od?)
> (set! ev? (lambda ...))
> (set! od? (lambda ...))
> (ev? 8)) '() '())
((lambda (ev? od?)
(display (list 'ev? '= ev?)) (display (list 'od? '= od?)) (newline)
(set! ev? (lambda ...))
(display (list 'ev? '= ev?)) (display (list 'od? '= od?)) (newline)
(set! od? (lambda ...))
(display (list 'ev? '= ev?)) (display (list 'od? '= od?)) (newline)
(ev? 8)) '() '())
--
__Pascal_Bourguignon__ _ Software patents are endangering
() ASCII ribbon against html email (o_ the computer industry all around
/\ 1962:DO20I=1.100 //\ the world http://lpf.ai.mit.edu/
2001:my($f)=`fortune`; V_/ http://petition.eurolinux.org/
| |
| ncruces@gmail.com 2006-01-23, 7:05 pm |
| > Could it be that first ev? and od? get '() bound to them, but later
> these values are overwritten by the set!. That would explain it. And
> the reason why Scheme is asking for "dummy values" is that it doesn't
> like dangling pointers.
Yes, exactly.
> If my reasoning is correct then the substitution
> ...
> is correct, but not the substitution
> ...
Not quite (see below) but, if that helps you understand it, you're free
to see it that way.
> But still that leaves the question of when can I substitute the
> arguments into the body and when not.
You have already answered that yourself:
> But now I remember that in SICP they said something
> that substitution model breaks down when you have set!
Generally you _can_ use the substitution model when there are _no_ side
effects (that is, when there is no set!).
So, you really can't apply substitution here, but as I said: if that
helps you better understand it...
| |
| Marcin 'Qrczak' Kowalczyk 2006-01-26, 7:04 pm |
| Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> writes:
>
> (letrec ([x* v*] ...) b b* ...)
> ==
> (let ([x* #f] ...)
> (let ([t* v*] ...)
> (set! x* t*) ...
> b b* ...))
No. Initial values are not #f, nor even unspecified values. Initially
the variables are unbound and it is an error to access them before all
v* are evaluated, though Scheme implementations aren't required to
detect the error. Letrec can't be emulated using other constructs.
--
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
| |
| Abdulaziz Ghuloum 2006-01-26, 9:57 pm |
| Marcin 'Qrczak' Kowalczyk wrote:
> Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> writes:
>
>
>
>
> No. Initial values are not #f, nor even unspecified values. Initially
> the variables are unbound and it is an error to access them before all
> v* are evaluated, though Scheme implementations aren't required to
> detect the error. Letrec can't be emulated using other constructs.
Yes yes. I am aware of all of that. I was just simplifying a bit.
More information about how to transform letrec into scheme code that
detects and reports violations of the letrec condition, refer to:
@article{Waddell:fixing-letrec,
author = {Oscar Waddell and Dipanwita Sarkar and R. Kent Dybvig},
title = {Letrec: A Faithful Yet Efficient Implementation of Scheme's
Recursive Binding Construct},
journal = {Higher-order and and symbolic computation},
year = 2004,
texturl = "http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf",
abstracturl =
"http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec-abstract.html",
note = "to appear",
annote = {Describes how Chez Scheme handles {\tt letrec} expressions
efficiently and with full enforcement of the revised
report's restriction preventing evaluation of left-hand-side
variable references and assignments before the righ-hand
sides have been evaluated.}}
Aziz,,,
| |
| Abdulaziz Ghuloum 2006-01-26, 9:57 pm |
| Marcin 'Qrczak' Kowalczyk wrote:
> Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> writes:
>
>
>
>
> No. Initial values are not #f, nor even unspecified values. Initially
> the variables are unbound and it is an error to access them before all
> v* are evaluated, though Scheme implementations aren't required to
> detect the error. Letrec can't be emulated using other constructs.
I would like to add that the transformation given above is a
correctness-preserving transformation. It is not an error-preserving
transformation. This means that the transformation, when applied to a
correct scheme program, will yield a correct program. The inverse
transformation (from the lets and set!s to a letrec even if an
unspecified value is placed in place of the #fs) is incorrect in
general.
Aziz,,,
| |
| Anton van Straaten 2006-01-27, 3:59 am |
| Marcin 'Qrczak' Kowalczyk wrote:
> Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> writes:
>
>
>
>
> No. Initial values are not #f, nor even unspecified values. Initially
> the variables are unbound
<pedantic>
That should be "undefined", not "unbound". R5RS says "The <variable>s
are bound to fresh locations holding undefined values". They have to be
bound in order to assign them later on, unless some kind of funky
just-in-time binding is done.
According to the formal semantics, given an "undefined" value, those
variables will behave as though they're unbound, giving an undefined
variable error if accessed too early.
> and it is an error to access them before all
> v* are evaluated, though Scheme implementations aren't required to
> detect the error. Letrec can't be emulated using other constructs.
But since that error doesn't have to be detected, a letrec
implementation which initially gives some other value to its variables
still satisfies the report: since the only purpose for the "undefined"
value is to force an error, if you're not going to generate that error,
it doesn't matter if you use something other than the undefined value.
Also, if an implementation were to provide an extension which generates
an 'undefined' value, then letrec could be implemented in terms of that.
In fact, the formal semantics mentions "an expression that evaluates
to 'undefined'" at the end of its introduction.
</pedantic>
Anton
|
|
|
|
|