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.

Continuation prompt

Since long time ago, I was thinking if Sagittarius can have some nice async/await equivalent things. I'm using Java/Kotlin at my work, occasionally TypeScript, they, execpt Java, have nice async/await thing. So, I asked my new shiny friends, Copilot or ChatGPT, if it's possible to implement it with continuation. And the answer was yes, also it'd be cleaner if I use delimited continuation.

Now, I remember that SRFI-226 defines delimited continuation. And I vaguely remember one of the discussions saying it can be implemented with continuation prommpt and composable continuation. I've been avoiding to touching the continuation, but it seems it's time for me to have some courage.

With my shallow understanding, composable continuation requires continuation prompt, so I decided to implement continuation prompt first. A continuation prompt can be implemented as a boundary frame. Currently, Sagittarius's call frame is implementented like this:

[  cont 0  ] <-- top
[  cont 1  ]
[  cont 2  ]
[ boundary ] <-- when C calling Scheme procedure
[  cont 3  ]
  :
[  cont n  ] <-- bottom

Now, I should be able to implement prompt as an extra frame like this:

[  cont 0  ] <-- top
[  cont 1  ]
[  cont 2  ]
[  prompt  ] <-- prompt frame
[  cont 3  ]
  :
[  cont n  ] <-- bottom

There's a very good reason why I should do this. Sagittarius' compiler optimises let with very advanced (I want to believe) way. It takes frame size into account. This means, I can't add extra field into the call frame structure. Because of this reason, I can't annotate the call frame with prompt tag by adding an extra struct member. The boundary frame is already using one of the members to hold a mark. In other words, I can use one member to hold prompt information.

Now, inserting prompt seems easy job, then next step, abort-current-continuation. It seems this is required to implement delimited continuation. Reading the document doen't really click what it does. So checked the behaviour with Racket. Started with the very simple example below.

(call-with-continuation-prompt
  (lambda ()
    (abort-current-continuation (default-continuation-prompt-tag) 1)
    (display 'not-reached) (newline))
  (default-continuation-prompt-tag)
  values)
;; -> 1

My easily get hallucinated brain understood that abort-current-continuation aborts the current continuation up to the specified prompt tag and invokes the abort-handler... this is what the document says... If I draw a diagram then it looks like this

[  cont 0  ] <-- abort/cc
[  cont 1  ]
[  cont 2  ]
[  prompt  ] <-- target   == after  ==>  ;; the rest of the call frame
[  cont 3  ]					         [  cont 3  ]
  :								           :
[  cont n  ]           			         [  cont n  ]

Okay, it looks easy enough to do it.

(Until I fell into a lots of pitfalls...)