Scheme - location

Author

location

Marlene Miller

2007-03-18, 4:23 am

My evaluator has an environment function and a store function.

(define eval-expression
(lambda (exp env store)
(cases expression exp
(app-exp (rator rands)

When the procedure is applied to 100 (at line 3), the environment has one
binding and the store has *two* locations, right?

(let ((p (let ((b 2))
(lambda (a) (set! b (+ b 10)) (+ a b)))))
(p 100))

L1 -> 2
L2 -> #procedure

Do locations bound to free variables of procedures exist for the life of the
program?

Marlene Miller

2007-03-18, 4:23 am

Variation on previous question...

(let ((p (let ((b 2))
(lambda (a) (set! b (+ b 10)) (+ a b)))))
(p 100))

b -> L1 -> 2
p -> L2 -> #procedure

- - - - - - - - - -
(let ((p (let ((b 2)) (set! b 3) b)))
p)

b -> L1 -> 2
p -> L2 -> 3

When p is evaluated, does the store have *two* locations? Does the free
variable b make a difference?

George Neuner

2007-03-18, 4:23 am

On Sun, 18 Mar 2007 02:45:14 GMT, "Marlene Miller"
<marlenemiller@worldnet.att.net> wrote:

>My evaluator has an environment function and a store function.
>
>(define eval-expression
> (lambda (exp env store)
> (cases expression exp
> (app-exp (rator rands)
>
>When the procedure is applied to 100 (at line 3), the environment has one
>binding and the store has *two* locations, right?
>
>(let ((p (let ((b 2))
> (lambda (a) (set! b (+ b 10)) (+ a b)))))
> (p 100))
>
>L1 -> 2
>L2 -> #procedure
>
>

I'm not sure exactly how you are using the terms "environment" and
"store", so I'm going to explain it in terms of Scheme and, hopefully,
you can transliterate.

Environment diagrams get messy with closures and function locals but
the picture is something like this:

---------------
global | ?: |
---------------
^ ^
| |
------- |
E1 | p:+ |<--+ |
----|-- | |
| | |
| | |
| ------
| E2 | b: |
| ------
| ^
v |
{\P.a:...} -+

The top level named LET creates environment E1 which extends the
global environment with the name of the procedure "P".

The nested LET creates environment E2 which extends E1 and the global
environment with "b". I'll get to why I've shown them extended
separately in just a minute.

Procedure P must close over E2 because it requires "b". Whether the
closure of P really consists of two chained environment blocks or puts
"a" and "b" together somehow is an implementation detail.

E1, however, may not need to be closed over ... technically, once P's
recursive call is resolved, E1 is no longer needed - in this way a
named LET is not the same as LETREC. A compiler, for example, could
reasonably be expected to throw E1 away immediately after P is
compiled. How long it needs to stick around depends on how your
evaluator works.

>Do locations bound to free variables of procedures exist for the life of the
>program?

Not necessarily. The name binding will exist for the life of the
closure. If the procedure uses SET!, the name may be bound to a new
location and the original location may become garbage.

In your particular example, "b" is being bound only to fixnums so they
will likely just reuse the same location. If you wrote instead

(let ((p (let ((b (list 2)))
(lambda (a)
(set! b (list (+ (car b) 10)))
(+ a (car b))))))
(p 100))

original list will be garbage after the SET!.

George
--
for email reply remove "/" from address

Max Hailperin

2007-03-18, 8:19 am

"Marlene Miller" <marlenemiller@worldnet.att.net> writes:

> My evaluator has an environment function and a store function.
>
> (define eval-expression
> (lambda (exp env store)
> (cases expression exp
> (app-exp (rator rands)
>
> When the procedure is applied to 100 (at line 3), the environment has one
> binding and the store has *two* locations, right?
>
> (let ((p (let ((b 2))
> (lambda (a) (set! b (+ b 10)) (+ a b)))))
> (p 100))
>
> L1 -> 2
> L2 -> #procedure

Right (or at least approximately so) -- the environment in which
(p 100) is evaluated contains the binding of p to a location (L2) that
contains a procedure, whereas that environment (in which p is
evaluated) does not contain the binding of b to the the location (L1)
containing 2.

The reasons why this is only an approximation to the truth are:

(1) The environment in which (p 100) is evaluated contains more than
just the binding for p, even though it doesn't contain a binding
for b. In particular, it contains a binding for +. At least,
that's the way it works in a language like Scheme or ML where +
is just another variable.

(2) You'll notice that I am careful to say "the environment in which
(p 100) is evaluated" as opposed to your "the environment."
There is more than one environment in existence at this point in
the program's execution. The procedure stored in location L2 is
closed over an environment containing the binding of b to
location L1, the location containing 2. As such, both
environments are still "live" in the sense of that they are
potentially relevant in the current evaluator state -- a garbage
collector couldn't collect either of them yet. The binding of b,
although not visible in the environment in which (p 100) is
evaluated, is still relevant to the future of the computation.

>
> Do locations bound to free variables of procedures exist for the life of the
> program?

In the conventional mathematical model used for languages like Scheme,
all locations exist for the life of the program; there is an
allocation function but no deallocation. In an actual implementation,
the system is free to deallocate a location as soon as it can show it
has no impact on the future of thee computation. There are a variety
of ways in which this is done -- for example, sometimes a compile-time
analysis shows that at runtime, stack allocation/deallocation will
suffice. However, at a minimum it can be done as my comment (2) above
suggested, by the use of garbage collected heap allocation. Your
interpreter probably isn't sophisticated enough to contain a garbage
collector. As such, it probably corresponds to the mathematical
abstraction, where the store just keeps monotonically accumulating
allocated locations. (In an interpreter that didn't use an explicit
store function, you would have been able to piggyback on Scheme's
garbage collector, because the Scheme object representing a location
would become unreachable within Scheme when the location became
unreacable within the interpreted language.) -max

Max Hailperin

2007-03-18, 8:19 am

"Marlene Miller" <marlenemiller@worldnet.att.net> writes:

> Variation on previous question...
>
> (let ((p (let ((b 2))
> (lambda (a) (set! b (+ b 10)) (+ a b)))))
> (p 100))
>
> b -> L1 -> 2
> p -> L2 -> #procedure
>
> - - - - - - - - - -
> (let ((p (let ((b 2)) (set! b 3) b)))
> p)
>
> b -> L1 -> 2
> p -> L2 -> 3
>
> When p is evaluated, does the store have *two* locations? Does the free
> variable b make a difference?

As explained in my other followup, your interpreter probably follows
the convention of monotonically accumulating allocated locations.
Note that if you had a language that only allowed situations like the
second one -- a language like Algol -- then it would be easy for the
interpreter to do stack allocation/deallocation. Once the block in
which b is bound was evaluated, you would know that the location bound
to b could never possibly be used again (becuase no procedure could
still be live that was closed over b). -max

Sponsored Links