Subject: Re: Continuations
From: (Rob Warnock)
Date: 14 Oct 2001 10:51:11 GMT
Newsgroups: comp.lang.scheme
Message-ID: <9qbqmv$rhnnb$>
Albert Einstein Petrofsky  <> wrote:
| (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).


[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:>. 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		<>
SGI Network Engineering		<>
1600 Amphitheatre Pkwy.		Phone: 650-933-1673
Mountain View, CA  94043	PP-ASEL-IA

[Note: and aren't for humans ]