Re: Continuations, closures, etc.

I've been working on a CPS transformer, more macro-based (any form->form conversion emits a result that expands based on the outer context's own macrolet)

Focuses:

Keeping multiple-value results (but determining single-value where relevant to salvage performance)
Interoperability across function calls, with detection of "regular" or "transformed" functions via input parameters. MOP used to highlight first class functions that can be called with "normal" parameters (the normal way) to start a new context, or with CPS parameters for execution within an existing one.
unwind-protect etc all work correctly
Cloneable continuations - Each running instance has a context with distinct storage for mutables. This is achieved through examination/determination of which variables are mutable. Optional "deep clone" supported for variable groups (necessary for cloning (loop for ... collect) etc). This behavior has a cost, and is optional.
Trampolining. Each execution thunk is declared in a macro which returns to the top of the stack for actual execution. I'm uncertain if there would be value to having this be tuneable at compile or runtime to execute in place rather than return every time (obviously executing in place is faster; but will grow stack).
Support for return-type dispatch via some type proliferation. Haven't delved into this yet; but conforming code at both calling and callee end are already talking in terms of a return sink, and a lot of the lexical context is known, shouldn't be too much of a stretch. It's a future research topic to look into, I want it to get decent support for monad experimentation.
Ability to specify lisp-1 for sub-sections of code for convenience. This was trivial/free give the amount of lexical scope info that's kept anyway. Will probably add arc-type container-as-function funcionality here too (e.g. (let ((my-array (make-array))) (my-array 3)) ) - and even take out the runtime check in certain cases where the variable is immutable and created from a literal.
Preserving the usefulness and idioms of coding with CLs' dynamic-scope elements (special vars, etc) - that code can interact with "normal" libraries that use them with standard CL type code

The last point is where it gets interesting. In practical CL coding, there are a lot of "with-blahblah" macros or libraries where to interact you have to locally bind a special variable. They still have to be bound dynamically, which means they must be bound "under" the trampolining loop. To do this, the code at point of binding instructs the loop to reexecute itself under the new binding - by providing it a function that takes a function that it runs after the binding. This is, of course, also absolutely necessary for the continuations, cloned or not - as the continuation is returned through this stack - and to resume execution, must be able to recreate the stack by caching these "run-with-binding" functions along with the values.

(defparameter *my-special* nil)

(let ((*my-special* 5))
    (call/cc #'identity)
    (some-normal-library-func-that-uses-*my-special*))

I have this case working.   But another challenge that comes up is that this consumes real stack in recursive cases (in pure CL this may be an implementation detail; but it seems to consume stack in the implementations I've tried). Given how cps + trampolining is supposed to be so useful in avoiding stack bloat even in non-tail recursion, it seems a shame that:

(defun test ()
(let ((*my-special* (random)))
   (test)))

Would consume true stack space.

My current development effort is in getting a solution in that would keep only one binding per special variable on the stack underneath the primary loop (keeping the prior bindings' values on the heap, and substituting them back in to the true stack binding when the prior leaves scope); but preserving also the true CL catch-blocks and handler-bindings. This will undoubtedly involve selective removals of items from the middle of the stack at times, and possibly reordering of elements on the true stack.

Obviously, the support of true CL special variables/dynamic constructs imposes a cost on true single-stepping on the order of N, with N being the number of distinct special-variable symbols or bindings in-scope (which must be recreated each step). Use them - pay, don't use them, no real cost.

That aside, CPS + trampolining has the added side-effect of having variables become eligible for collection as of the very last instance they are referenced, as there is simply no way for the old reference to perpetuate itself (including at the caller's side of calls to functions - i.e. the issue goes beyond putting "nil" in a variable the last time you touch it). Technically, Lispworks tends to do this compiled; but such a code transformation makes the behavior deterministic across implementations (that don't do so) and even in interpreted mode. This can eliminate certain memory use spikes - you may be exchanging execution speed for peak memory use.

Sorry if I went off on too much of a tangent. Just throwing out that I see the issues also in terms of interop with existing lisp stuff, the degree to which you support dynamic, (CL stack) usage and peak heap use. And the last 2 here are where you get the benefit in exchange for the (possibly brutal) speed hit.

David McClain wrote:

(sorry if this appears more than once, I thought the original would bounce on an unrecognized e-mail signature...)

There has been a lively discussion about CPS and its speed impact on the Gambit thread. My own experience in the past, on several different implementations, has shown it to be approximately 30% (1 sig fig) slower than direct coding.

Given that Lisp does not offer first class continuations, and remains a largely imperative language (hence very speedy!), I am curious about creative alternatives in Lisp. Does anyone have any references or great ideas here?

Dr. David McClain

Chief Technical Officer

Refined Audiometrics Laboratory

4391 N. Camino Ferreo

Tucson, AZ 85750

email: dbm@refined-audiometrics.com

phone: 1.520.390.3995

web: http://www.refined-audiometrics.com