Subject: Re: continuations in combinations?
From: (Rob Warnock)
Date: 1998/11/10
Newsgroups: comp.lang.scheme
Message-ID: <7299t3$>
<> wrote:
| what rules apply when a continuation captured while evaluation
| the expressions in a combination is invoked?
| e.g (foo a (call-with-current-continuation bar) b),
| where bar stores the escape procedure passed to it in a location allready
| bound to a variable in the environment in wich bar was created. Are all the
| arguments (except for the one wich is set by the escape procedure)
| re-evaluated, or are only the arguments wich where not yet evaluated when the
| continuation was captured re-evaluated, and the "old" values wich wich where
| already evaluated when the continuation was captured re-used?

The latter, partly because in general the evaluator has no way to know which
arguments caused continuations to be captured.

Consider that the situation may be even more pathological than your example.
In particular, (1) the continuation might not be captured in the top level
of the argument evaluation, and (2) there might be more than one continuation
being captured. That is, the call might be (foo a (bar b c) (gorp d e) f),
where a call/cc occurs somewhere inside the call to "bar", and another call/cc
occurs somewhere inside the call to "gorp". Thus, potentially, *any* argument
evaluation which is other than a literal or simple variable may result in a
captured continuation which may later be re-used. And "the right thing" has
to happen if neither or one or all of those captured continuations are ever
used again (possibly multiple times).

The Scheme standard does not specify an order for argument evaluation, but
it *does* require that the arguments of a given call be evaluated in a way
consistent with *some* sequential order. (Using call/cc as per your example
is one way to find out that order. Caveat: It is allowed to vary from call
to call!)

| If so, are these "old" values bound somwhere when the continuation is
| captured, as a part of the continuation, or are they lexically bound to
| the expressions in the combination? I hope you can parse the question...

"Bound" to named variables, no. "Stored", yes, in the implicit continuation
of the argument evaluation process itself. That is, having captured a
continuation (as above), any already-evaluated arguments must remain
available (in the [extended] continuation) as long as there is a possibility
that the captured continuation might be called. On the other hand, you may
have no way to "see" the values stored in that continuation other than to
invoke it.

[Note: This gets a *lot* simpler to understand if you re-write the procedure
application process in continuation-passing style, whereupon the "inter-
argument" continuations become apparent & obvious, and your question almost
answers itself.]

Anyway, as someone else replied, *all* of the actual arguments have to be
evaluated before *any* of the argument values can be lambda-bound to the
formal argument variables. Yes, this does imply that (unless the evaluator
can prove that it's not necessary) a *copy* has to be made of the actual
arguments in the process of binding the formals. The R5RS spec *almost*
makes this clear (sections 4.1.3 & 4.1.4) but you still have to read between
the lines just a little.

Queinnec, in "Lisp In Small Pieces", states it much more clearly, and gives
a contorted example (below) which will fail if the evaluator doesn't follow
this (that is, will fail if the evaluator uses "incremental binding" of the
arguments). The following should yield the value "(2 1)":

	(let ((k 'wait)
	      (f '()))
	  (set! f (let ((g ((lambda (a) (lambda () a))
			    (call/cc (lambda (nk) (set! k nk) (nk 1))))))
		    (cons g f)))
	  (if (null? (cdr f)) (k 2))
	  (list ((car f)) ((cadr f))))

It gives the correct answer on (at least) MzScheme, SCM, Elk, TinyScheme,
MiniScheme, & Gambit-C (interp). It blows up with varying errors on some
others. You may wish to try it on your favorite...

[I suspect that a simpler example exists, but haven't derived one yet.]


Rob Warnock, 8L-855
Applied Networking
Silicon Graphics, Inc.		Phone: 650-933-1673
2011 N. Shoreline Blvd.		FAX: 650-964-0811
Mountain View, CA  94043	PP-ASEL-IA