Home > Archive > Scheme > December 2006 > letrec without magic
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 |
letrec without magic
|
|
| Marlene Miller 2006-12-25, 7:10 pm |
| Question: When evaluating a letrec expression, the "magic" (recursion)
disappeared. Where did it go?
(letrec ((even (lambda (n)
(if (= n 0) #t (odd (- n 1)))))
(odd (lambda (n)
(if (= n 0) #f (even (- n 1))))))
(odd 22))
EoPL section 3.6 Recursion shows 3 ways to evaluate letrec. I am curious to
see how they handled the recursion in letrec. The first way, they use letrec
of the defining language to evaluate letrec of the defined language. Ok but
not very satisfying. The third way, the environment data structure **points
to itself** and they use **set!**. Ok.
The second way, they delay the creation of the closure until the procedure
name in the letrec body is evaluated.
1. Before evaluating the letrec body (odd 22), they extend the environment.
They store the pieces they will need later to create a closure. They do not
evaluate the lambda expressions (the closures would need this environment
they are at the moment creating). The environment record looks like this:
<list of names>: (even odd)
<lists of params>: ((n) (n))
<list of bodies>: ((if ... odd...) (if ... even...))
<old environment>: ()
2. When they evaluate the letrec body (odd 22), they must look up the
procedure name "odd" in the environment. When they find the procedure name
in the <list of names>, they extract the params and body and build a
closure.
<params> (n)
<body> (if ... even...)
<recursive environment>
To me this looks very straightforward. I don't see any recursion. Hmmm.
However, in Theories of Programming, Reynolds section 11.6 An Eager
Functional Language, Direct Denotational Semantics, when they describe the
denotational semantics of letrec, they refer to the least fixed-point
theorem section 2.4. This book is too advanced for me, but I think that
theorem has something to do with Y and recursion. I have a hunch you cannot
remove the recursion from the description of letrec.
Am I on the right track to suspect that when you describe the evaluation of
letrec, somewhere there has to be something like Y?
Where did the recursion go in EoPL evaluation method #2?
| |
| Marlene Miller 2006-12-25, 7:10 pm |
| > Where did the recursion go in EoPL evaluation method #2?
I've read The Little Schemer chapter 9 at least 6 times, and made it to the
end of the chapter twice. It's okay with me if you want to assume I
understand that much about Y, but no more.
| |
| Nils M Holm 2006-12-26, 4:17 am |
| Marlene Miller <marlenemiller@worldnet.att.net> wrote:
> The second way, they delay the creation of the closure until the procedure
> name in the letrec body is evaluated.
As you probably know, the problem with the creation of recursive
closures is that the symbol binding to the recursive function is
closed over /before/ it is bound to the function. Here is a simpler
example:
(define f #f)
(let ((f (lambda (x) (and (pair? x) (f (cdr x))))))
(f '(x y z))) => bottom
To distinguish the inner and outer F, I will refer to them as
Fi (inner F) and Fo (outer F):
(let ((Fi (lambda (x) (and (pair? x) (Fo (cdr x))))))
(Fi '(x y z))) => bottom
What happens is this:
1. First LAMBDA closes over Fo, giving a closure C.
2. Fi is bound to C.
In the lexical environment of Fi, f==Fo, which is bound to #F.
No recursive function is created. No surprise here.
Now to the method suggested in EoPL.
(letrec ((Fi (lambda (x) (and (pair? x) (Fo (cdr x))))))
(Fi '(x y z)))
1. An extended environment is created. The value of the inner
F is not yet known:
((Fi . #<void> ))
2. The F's of the closure bodies are looked up in the inner
environment, essentially giving
(letrec ((Fi (lambda (x) (and (pair? x) (Fi (cdr x))))))
(Fi '(x y z)))
At this moment, Fi is still bound to #<void>, but this will
soon be fixed:
3. LAMBDA closes over Fi, giving C.
4. C is stored in the location bound to Fi.
Because F was closed over /after/ looking it up in the
/inner/ environment, it now binds to Fi. The value of Fi
is finally changed to C.
The Fi of C now refers to a storage location referring to Fi.
Voila, recursion.
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
| |
|
| [clipped]
> Because F was closed over /after/ looking it up in the
> /inner/ environment, it now binds to Fi. The value of Fi
> is finally changed to C.
>
> The Fi of C now refers to a storage location referring to Fi.
Tangenital to this discussion, I'm wondering, do any other
non-lisp-based languages have semantic equivalents to letrec?
| |
|
|
|
|
|