From: Pupeno
Subject: Recursive environments (closures-related)
Date: 
Message-ID: <07-01-050@comp.compilers>
Hello,
Maybe this is off-topic because I am not writting a compiler yet. I am
starting with an interpreter which is easier and I'll do that until my
language has a clear shape.

My main source of knowledge is "Programming Languages: Application and
Interpretation"[1] and I am also starting to dig in "Essentials of
Programming Languages" so, I am starting to write a Lispy language and
I am doing it in Scheme (actually I am writting a Schemy language, but
I'll get away from that soon, there's already one Scheme, or 5 or 10).
In PLAI, to do recursive binding to be able to do things such us:

(let* ((r (lambda (x)
 �  �  �  �  �  � (if (zero? x)
 �  �  �  �  �  �  �  � x
 �  �  �  �  �  �  �  � (r (- x 1))))))
 � (r 10))

it first binds r to a bogus value (actually a box containing a bogus
value[2]) then it interprets what would be the real value, that is the
lambda that upon interpretation generats a procedure. And then put
that procedure where the bogus value was.

I've done it differently and I'd like to know if my solution is
wrong. I first interpret the value of the binding and bind it to its
name creating a new environment. If the new value is a procedure then
I change its environment for the new one (the one that contains a
reference to itself) effectively creating the recursive
environment. So far it seems to work and it evens has the improvement
of not requiring that the value of a recursive binding be a procedure
(since I only turn it into a recursive environment if it is a
procedure). Am I doing something wrong ? is there anything I am not
seeing ?  Any thoughts are appreciated.  Thank you.  Pupeno
<······@pupeno.com> (http://pupeno.com)

[1] http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/
[2] Any particular reason to use a box instead of cons, car, cdr, set-car!
and set-cdr! ?

PS: This is the code that interprets a recursive binding in my interpreter:

((rec-binding-node? program)
 �(let* ((new-value (interpret (rec-binding-node.value program) env))
 �  �  �  � (new-env (env.add-binding (rec-binding-node.name program)
 �  �  �  �  �  �  �  �  �  �  �  �  �  �  �  �  � new-value
 �  �  �  �  �  �  �  �  �  �  �  �  �  �  �  �  � env)))
 � (when (closure-value? new-value)
 �  �  �  � (set.closure-value.env! new-value new-env))
 � (interpret (rec-binding-node.exp program) new-env)))

I am not sure how understandable it is without the rest of the program, but
basically the when form does the trick of setting the right environment if
and only if the value is a closure.

From: George Neuner
Subject: Re: Recursive environments (closures-related)
Date: 
Message-ID: <3jutq2hd9d915m2bfl6nouakf50rbc2239@4ax.com>
Rearranged a bit for clarity
On 17 Jan 2007 17:31:39 -0500, Pupeno <······@pupeno.com> wrote:

>In PLAI, to do recursive binding to be able to do things such us:
>
>(let* ((r (lambda (x)
> �  �  �  �  �  � (if (zero? x)
> �  �  �  �  �  �  �  � x
> �  �  �  �  �  �  �  � (r (- x 1))))))
> � (r 10))
>
>it first binds r to a bogus value (actually a box containing a bogus
>value[2]) then it interprets what would be the real value, that is the
>lambda that upon interpretation generats a procedure. And then put
>that procedure where the bogus value was.
>
>I've done it differently and I'd like to know if my solution is
>wrong. I first interpret the value of the binding and bind it to its
>name creating a new environment. If the new value is a procedure then
>I change its environment for the new one (the one that contains a
>reference to itself) effectively creating the recursive
>environment.

>Am I doing something wrong ? is there anything I am not seeing?

>PS: This is the code that interprets a recursive binding in my interpreter:
>
>((rec-binding-node? program)
> �(let* ((new-value (interpret (rec-binding-node.value program) env))
> �  �  �  � (new-env (env.add-binding (rec-binding-node.name program)
> �  �  �  �  �  �  �  �  �  �  �  �  �  �  �  �  � new-value
> �  �  �  �  �  �  �  �  �  �  �  �  �  �  �  �  � env)))
> � (when (closure-value? new-value)
> �  �  �  � (set.closure-value.env! new-value new-env))
> � (interpret (rec-binding-node.exp program) new-env)))


PLAI's approach is equivalent to Scheme's LETREC - it creates dummy
bindings in the current environment to act as forward references for
mutually recursive procedures.

Your solution is the equivalent of LET - only bindings in the
enclosing environment can be seen (LET* is the equivalent of nested
LETs).  Allowing a recursive procedure is a nice extension.

The only issue I see with your solution (if it is important to you) is
that it doesn't directly support mutual recursion.  Because you add
bindings to the environment only after evaluating the init form,
forward references to procedures not yet seen will fail.  You can
still code such procedures by binding their names to dummy values and
then SET!ing them later.

Technically LETREC is all you need - Scheme also includes LET because
by creating new names up front, LETREC can unintentionally shadow
bindings in the enclosing environment, potentially resulting in use of
the wrong variable if the programmer is not careful.


>[2] Any particular reason to use a box instead of cons, car, cdr, set-car!
>and set-cdr! ?

Boxes exist for efficiency of compiled code.  Logically a cons cell
works just as well for indirection.  

George

--
for email reply remove "/" from address
From: Kalle Olavi Niemitalo
Subject: Re: Recursive environments (closures-related)
Date: 
Message-ID: <87mz4gf22p.fsf@Astalo.kon.iki.fi>
Pupeno <······@pupeno.com> writes:

> I've done it differently and I'd like to know if my solution is
> wrong. I first interpret the value of the binding and bind it to its
> name creating a new environment. If the new value is a procedure then
> I change its environment for the new one (the one that contains a
> reference to itself) effectively creating the recursive
> environment. So far it seems to work and it evens has the improvement
> of not requiring that the value of a recursive binding be a procedure
> (since I only turn it into a recursive environment if it is a
> procedure).

(letrec ((r (list (lambda () r))))
  (eqv? ((car r)) r)) ; expected result: #t

I think your solution would note that the value of r is a list,
not a procedure, and so skip changing the environment.  And then
((car r)) would call the procedure, which would look up r in the
wrong environment and not find it and signal an error.

If you think you can just recursively examine the value, consider

(let ((p 1) (r 2))
  (let ((q (lambda () (list r 3))))
    (letrec ((r (begin (set! p (lambda () (list r 4))) q)))
      5)
    (eqv? (car ((car (p)))) 2))) ; expected result: #t

This code has two traps for your solution.  The procedure
resulting from the (lambda () (list r 4)) must use the
environment where letrec has bound r, but the procedure is not
part of the value in that binding, so not even a recursive walk
can find it.  Instead, the value of the binding is the procedure
resulting from the earlier (lambda () (list r 3)); if your letrec
is lured into attaching that to the wrong environment, then the
procedure will use the wrong r and the result won't match.