Composable continuation (1)

After 2 weeks of fighting, I've finished implementing composable continuation. This is my memo of how I understand composable continuation and what I've done to implement it.

How it works

If I google it, I can find a lot of (maybe not so many) articles and/or papers regarding composable continuation. All those papers are, of course, very abstracted, means it wasn't intuitive for me. (I'm not good at those symbols, unfortunately.) So, let me illustrate a bit more concretely.

CAVEAT: This is how I understand and how it works on Sagittarius.

First, Sagittarius is a VM machine using stack as its call frames. The same model as previous article. When call/cc is called, then the call frames are move to the heap with the same structure. It'd be like this:

~ before call/cc ~
 [ call frame 0] <-- VM's cont register
 [ call frame 1]
 [ call frame 2]
  :
 [ call frame n]
 
~ after call/cc ~
 [ call frame 0] -> [ call frame 1] -> [ call frame 2] -..> [ call frame n]

This only means, stack call frames became heap call frames. When the captured continuation is invoked, then it'd simply replaces the VM's current cont frame to captured one.

[ call frame 0] -> [ call frame 1] -> [ call frame 2] -..> [ call frame n]
~~~~~~~~~~~~~~~
VM's cont register

When the heap call frame is returned, then the call frame will be poped. Then the saved arguments will be pushed into the bottom of the stack, like this:

[ call frame 0] -> [ call frame 1] -> [ call frame 2] -..> [ call frame n]
~~~~~~~~~~~~~~~
This is poped

[ arg n ] <- stack pointer
 :
[ arg 1 ]
[ arg 0 ] <- frame pointer = bottom of stack
~~~~~~~~~~
These arguments are form [ call frame 1 ]

In this way, the local argument reference doesn't require special handling, but just refering the same relative location. (i.e. LREF 0 always refers *fp, LREF 1 is *(fp + 1).)

Now, we have composable continuation. A composable continuation captures the call frames up until the specified prompt. So, conceptionally, the captured call frames are like this:

~ before call/comp ~
  [ call frame 0 ]
  [ call frame 1 ]
  [   prompt 0   ] <- capture until here
  [ call frame 2 ]
   :
  [ call frame n ]
 
~ captured continuation ~
[ call frame 0 ] -> [ call frame 1 ] -> [ prompt 0 ]

And when the captured continuation is invoked, then call frames will be like this.

~ before invocation ~
  [ call frame a ]
  [ call frame b ]
      :
  [ call frame z ]

captured continuation: [ call frame 0] -> [ call frame 1] -> [ prompt 0 ]

~ after invocation ~
  [ call frame 0 ]
  [ call frame 1 ]
  [   prompt 0   ]
  [ call frame a ]
  [ call frame b ]
      :
  [ call frame z ]

So, the captured continuation will be stack up on top of the current call frames. This means, it returns to the same location from the invocation. For example, this shows 1,3,2,3, instead of 1,3,

(call-with-continuation-prompt
 (lambda ()
   (call-with-composable-continuation
    (lambda (k)
      (display "1,")
      (k 1)
      (display "2")))
   (display "3,")))

If you replace call-with-composable-continuation with call/cc, then it shows 1,3,.

Closest prompt

When it comes with abort-current-continuation, composable continuations are not that much intuitive. See the script below:

;; invoking captured k means calling the thunk passed as an argument
(let ((k (call-with-continuation-prompt ;; (1)
          (lambda ()
            ((call-with-composable-continuation
              (lambda (k) (lambda () k))))))))
  (call-with-continuation-prompt ;; (2)
   (lambda ()
     (+ 99 (k (lambda () (abort-current-continuation 
                          (default-continuation-prompt-tag)
                          8)))))
   (default-continuation-prompt-tag)
   values))

Initially, I thought this would be like this cont frame transition.

prompt/handler notation, #f means no handler

~ capture ~ 
[ cont frame 0 ]
[  prompt/#f   ] <- default prompt tag + #f

~ invocation ~
[  cont frame 0 ]
[   prompt/#f   ]
[  cont frame 1 ] <- (+ 99 ...)
[ prompt/values ] <- default prompt tag + values

So, my mind said this should throw an error. But it ends up returning 8. Why?

The prompet inserted by the continuation invocation should come after the one inserted by the call-with-continuation-prompt (2). If I only see the call frame stack, the prompt/#f is the closest, but because it's composable continuation, the stacked up prompt must be after.

;; prompt order
~ my intuition ~
[ prompt/#f ] -> [ prompt/values ]

~ how it should be ~
[ prompt/values ] -> [ prompt/#f ]

This means, I need to manage the prompt insertion order separately as well.

It's getting longer than I though, so to be continnued.