call/cc and recursive vm invocations

[Andy Wingo <wingo@pobox.com>]

Hey folks,

One of the last missing features / regressions on my list for 2.0 is to
fix make-stack and start-stack to work with the VM.

In case you haven't noticed yet, if you get an error at the REPL and ask
for a backtrace from the debugger, you get not only the frames that
pertain to your own computation, but also frames from the REPL
implementation itself. That's not good, and it's a regression.

The solution is to implement start-stack for the VM. Prompts provide an
ideal set of primitives. So start-stack can be this:

  (define (start-stack tag exp)
    (let ((prompt-tag (fresh-tag)))
      (with-fluids ((stacks (acons tag prompt-tag (fluid-ref stacks))))
        (% prompt-tag
           exp
           (lambda (k . args)
             (apply values k args))))))

This assumes some fluid is around named "stacks". Then we can implement
make-stack:

  (define (make-stack tag . narrowing)
    (let ((prompt-tag (assq-ref (fluid-ref stacks) tag)))
      (unless prompt-tag
        (error "prompt tag not found quoi"))
      (narrow-stack
       (continuation->stack
        (call/cc
         (lambda (k) k)
          prompt-tag))
       narrowing)))
  
And this assumes that we factor out stack narrowing to its own
procedure, and that continuation->stack exists (it does now, inside
scm_make_stack)...

...and, that we have a call/cc that takes two arguments.

Now, currently "full" continuations integrate just fine with delimited
continuations. (Recall that full continuations copy the whole stack,
both on the C and Scheme level.) But here we'd like the ability to
capture just the Scheme stack, and only up to a certain delimiter
(prompt).

In fact this actually adds more power to call/cc, by allowing the user
to delimit the scope of the continuations that it captures (via
prompts). However it seems that one cannot implement call/cc purely in
terms of prompt and abort -- because with prompt and abort, reifying a
continuation only happens on an abort, which unwinds the dynamic state.
Likewise invoking a "full" (but delimited) continuation needs to replace
the continuation from a prompt, but might not need to unwind all the way
to the prompt, if the current and future continuations share part of
their dynamic extents.

Finally, delimiting call/cc makes it more expressive when invoked from a
callback API. Imagine you have some inversion-of-control library that
calls your code every so often -- currently in Guile you can't capture
the continuation in one callback, then invoke it in the next, because it
means your first callback would return twice. Well, truth is you can,
but often callback-style APIs are implemented in C or such, and often
such code can't handle multiple returns.

Reinstating a full-but-delimited continuation, on the other hand, can
happen in different dynamic contexts -- each callback can set up a
prompt, and calling a continuation with a specific prompt tag will
overwrite the stack only up to the prompt with that tag.

Relatedly, delimiting the continuations makes it easier to think about
shipping them across the network.


                              *  *  *

So, that's the upside. The downside of delimiting "full" continuations
is that you can't capture the C stack.

This has a number of ramifications, but first, a little eulogy for
Guile's current implementation of "full" continuations: it has been nice
to be able to capture the C stack. It makes C coding more like Scheme
coding, to know that control may flow through your functions in more
than one way. I enjoyed it.

But of course, to each implementation its own time, and this approach to
continuations has been nearing its expiration date for years now. Most C
code can't deal with nonlocal exits, let alone multiple returns. So the
utility of this construct has been limited.

Now, with the VM and partial continuations, we have the ability to
capture the Scheme stack apart from the C stack, and more and more can
be done within the VM itself. Call/cc is mostly useful in a pure Scheme
context anyway, so it's natural to start thinking of an implementation
of continuations that does not capture the C stack.

(FWIW, the ability to exit from C code nonlocally is key to Guile's C
API, and I don't see a move away from that in any foreseeable future.
The issue at hand here is *capture* of the C stack.)


Anyway, enough about that. Practically speaking, not capturing the C
stack means that you cannot invoke a continuation that was captured
outside the current VM invocation. For example, there are a number of
primitive functions that end up calling scm_call_1 or such, like
scm_map. So this wouldn't work:

  (let ((k (call/cc (lambda (k) k))))
    (map (lambda (x) (k x)) list-of-things))

because the lambda gets called within a recursive VM invocation, so
there are intermediate C frames on the stack, so the continuation cannot
be invoked. (The code to detect this exists already.)

I did an informal experiment to see what code caused recursive VM
invocations during a repl startup. The total was about 3500 VM
invocations, most of those singly-recursive. I don't think this is
expensive, but it's a bit unnecessary.

The most common causes for recursive incovations for a repl startup
were, in no order:

  primitive-load
  load-compiled/vm
  primitive-load-path
  call-with-input-string (only once or so)
  map
  for-each
  hash-for-each
  scm_eval_closure_lookup (?)
  scm_thunk_p (calls program's meta-thunk to get arity; wasteful GC-wise)
  scm_resolve_module (calls Scheme resolve-module)
  filter

Note that dynamic-wind and with-fluids are no longer on there,
thankyouverymuch. thunk? is only on the list because of the dynamic-wind
invocations that are there, many of which could be replaced by
with-fluids I think. (We should expose the current ports as fluids I
think.)

Map and for-each are interesting cases, actually:

  http://www.r6rs.org/formal-comments/comment-36.txt
  http://lists.r6rs.org/pipermail/r6rs-discuss/2007-March/001956.html

But regardless of that, I think they should be in Scheme for purposes of
inlining. (map (lambda (x) ...) '(list of few things)) should be
inlined, and (for-each (lambda (x) ...) l) should always be inlined,
because it allows further optimizations.

                              *  *  *

Practically speaking... I think I can delimit call/cc with not much work
(perhaps tomorrow). But it is a visible change (if you're looking), so I
wanted to put this mail out there to get comments. I had thought this
was a 2.2 feature, but given the make-stack implications, I'm thinking
it's a 1.9.9 feature. Reactions?

Happy hacking,

Andy
-- 
http://wingolog.org/