Subject: Re: Making Lisp popular - can it be done?
From: rpw3@rpw3.org (Rob Warnock)
Date: Thu, 15 Jan 2009 19:30:41 -0600
Newsgroups: comp.lang.lisp
Message-ID: <yf2dnSZSuejcfvLUnZ2dnUVZ_hudnZ2d@speakeasy.net>
Stanis� aw Halik  <sthalik@test123.ltd.pl> wrote:
+---------------
| thus spoke Slobodan Blazeski <slobodan.blazeski@gmail.com>:
| > ex 4 Scheme has continuations, could your VM support them efficiently
| > or will die when grab one from a deep nested stack?
| 
| Stack? What stack? CPS-transformation seems to be the only robust
| implementation choice.
+---------------

1. There are other robust choices: A-normalization, SSA, etc.

2. Even CPS-transformed Scheme has a "stack", it's just that
   the stack is hidden in the environments of the continuations
   themselves, which is where the information about where to
   "return" to is encoded.

3. Slobodan's "grab one from a deep nested stack" also addresses
   the issues of invoking a continuation *other* than the normal
   "next thing to do", such a continuation explictly reified by
   the user (with CALL/CC) or a continuation reified by some
   exception-handling system. CPS-transformed code always needs
   to be able to handle the case of the normal continuation
   being *abandoned* and some other continuation called instead.
   [And, indeed, this is one of the advantages touted for CPS,
   that it makes that abandonment easier!]

So Slobodan's question seems perfectly reasonable to me:
How (or how well) does your VM support abandonment of the
current "normal" continuation and the invocation of some
different continuation which was created much higher in
the dynamic function-calling nesting level [a.k.a. "stack"]?

And specfically for Scheme, How (or how well) does your VM
support the invocation of the *same* continuation a *second*
(or third, or fourth) time, when that continuation was originally
created & captured deep in the dynamic function-calling nesting
level [a.k.a.  "stack"] but was not invoked the second time until
that dynamic function nesting had already been completely unwound?

If your VM cannot support "use many times" continuations,
then it cannot support Scheme.

CL, of course, supports "escaping" continuations [exceptions
and other non-local transfers of control], but *only* those.
Still, getting one's VM to support even "just" those can be
quote a challenge, since that includes such things as this:

    (tagbody
      restart
      ...
      (some-function (lambda() (go restart)) other-args...)
      ...)

where SOME-FUNCTION is certainly permitted to FUNCALL it's
first argument, or even pass it off into a very deeply-nested
set of function calls, one of which FUNCALLs the LAMBDA with
the GO in it, forcing a stack-unwind which properly restores all
of the intermediate dynamically-bound variables and executes all
of the intermediate UNWIND-PROTECT cleanup blocks. Can your VM
support that?


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607