Albert Einstein Petrofsky <albert-einstein@petrofsky.org> wrote:
+---------------
| sesov@mail.ru (Oleg Sesov) writes:
| > > Note that this is equivalent to:
| > > (define (test)
| > > ((lambda (val resume) (display val) (set! val 1) resume)
| > > 0
| > > (call/cc (lambda (resume) resume))))
| > > The question now is: is the location `val' that (initially)
| > > holds the 0 created before or after the continuation is captured.
|
| It must be created afterward. The locations for the variables val and
| resume are created when the closure is applied, which is after all
| three positions of the combination ((lambda ...) 0 (call/cc ...)) have
| been evaluated.
+---------------
Indeed. Christian Queinnec gives an example quite similar to this
[sorry, the book's at work or I'd type it in] in "Lisp in Small Pieces",
Chapter 6 "Fast Interpretation", which he uses to show why -- at least
in the presence of "call/cc" -- procedure activation records must[1]
be allocated *after* the arguments are evaluated, even though this can
cause more temporary storage to be used (and immediately thrown away).
-Rob
[1] Well, if you can show that evaluating some subset of the arguments
can be done without the possibility of a procedure call that could
capture a continuation, then the evaluation of that subset can safely
be done after the procedure activation record is allocated, which
usually saves a lot of temp space. At a minumum, the subset includes
constants, global & lexical variables (and may include more in some
environments, e.g., compilers which make the global names of some
"safe" primitives immutable).
The (ex-)Rice PLT guys' "A-Normalization" algorithm[2] will extract
exactly those arguments which would require temporary space to be
allocated before the procedure activation record's allocation, and
make the allocation of those temps explicit (and incidentally make
the order of argument evaluation explicit). E.g., it converts this:
(* (+ a b) (- a b)
into this [assuming you've chosen left-to-right evaluation]:
(let ((t0 (+ a b)))
(let ((t1 (- a b)))
(* t0 t1)
That is, all procedure calls are transformed (by adding "let"s as
necesary) into calls of constants, lexicals, or globals (including
the procedure position, if that was a a complex expression). That
means that after A-Normalization it *is* safe -- even in the presence
of call/cc -- to allocate activation records *then* evaluate the
procedure call's arguments, since they'll all be "safe" simple
forms by then. Neat, eh?
[2] Flanagan, Sabry, Duba and Felleisen, "The Essence of Compiling with
Continuations" (PLDI 93) <URL:http://www.cs.rice.edu/CS/PLT/Publications/
pldi93-fsdf.ps.gz>. Introduces "Administrative Normal Form" or "A-Normal
Form" (or ANF), an alternate to doing CPS-conversion then optimizing
out the administrative redexes then back-converting from CPS to direct
form. A-Normalization goes straight from direct form to direct form.
-----
Rob Warnock, 30-3-510 <rpw3@sgi.com>
SGI Network Engineering <http://www.meer.net/~rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
[Note: aaanalyst@sgi.com and zedwatch@sgi.com aren't for humans ]