Composable continuation (3)

Dynamic winder is always a headache. It doesn't matter in which situation. For the composable continuation, it's not an exception at all.

For example the below script

(define saved #f)
(define count 0)
(call/prompt
 (lambda ()
   (dynamic-wind
       (lambda () (display "pre1\n"))
       (lambda ()
         (call/prompt
          (lambda ()
            (dynamic-wind
                (lambda () (display "pre2\n"))
                (lambda () #t)
                (lambda ()
                  (call/comp (lambda (k) (set! saved k) ))
                  (display "post2\n"))))))
       (lambda () (display "post1\n")))
   (unless (= count 1)
     (set! count (+ count 1))
     (saved 'again))))

This results like this

pre1
pre2
post2
post1
post2

And if I swap call/comp with call/cc then it'd print this

pre1
pre2
post2
post1
pre1
post2
post1

The second post2 is wrapped with pre1 and post1 which are the winders of the outer dynamic-wind.

If I see how it's written, it makes sense. The captured continuation is in the second prompt, so it shouldn't invoke the outer prompt winders. It makes sense, that doesn't mean it's easy to achieve.

Prompt as winder boundary

The winders are basically chains managed on VM. At the deepest location of the above example, the winder looks like this

[pre2 . post2] - [pre1 . post1] - [... system winders]
              ^^^
             prompt

The prompt is in between the first and the second winders. So, when the composable continuation is captured, then it only considers the first winder.

Though, if I replace only the first winder but without the rest of the [... system winders], then it'd cause a problem. So, it has to have some sort of filtering.

Filtering winders

One of the easiest filtering is that if the captured continuation is partial a.k.a composable, then no before thunk is needed. I'm not entirely sure if this assumption is actually correct, but it seems working. So, keep it like that...

Then the next one is that comparing the current winders and capture winders.

Captured:
[pre2 . post2] - [pre1 . post1] - [... system winders]
              ^^^
             prompt

Current:
[... system winders]

After exiting from the both dynamic-winds, then the current winders contains only the [... system winders] for the above example. So, it should take up until the prompt, then append the current winder.

Again, I'm not sure if the current implementation is correct, but it's working. So, I'm fine for now until I find a bug...

Composable continuation (2)

I've written how it works (as my memo), so now it's time to write what I've done (as my memo, again).

Capture composable continuation

Capturing a composable continuation is basically the same as capturing a full continuation. This means, we copy the entire stack frame into the heap area. In theory, we can copy up until the target prompt, so that we don't have to allocate unnecessary heap. Though, it wasn't that easy to achieve partial copy due to the process of popping a heap allocated continuation frame.

Currently, when a heap allocated continuation frame is popped, then it resets the stack pointer and frame pointer to the bottom of the stack, however if the stack contains both heap and stack allocated continuation frame, this can happen if we do the partial copy, then then popping a heap allocated continuation frame results incorrect state of the stack.

At this moment, I don't have a good way of avoiding this situation, I decided to copy the entire stack to the heap. This means capturing a composable continuation is as expensive as capturing a full continuation. I handed over this problem to the future me, which I already know I would suffer...

Splicing continuation frame

Composable continuation splices the continuation frame on top of the current continuation frame as the diagram below (copied from the previous article)

~ 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 ]

When continuation frames are spliced, then the previous pointer of the bottom continuation frame needs to be updated to the top of the current continuation frame. It's okay to do it, if the continuation is oneshot, however it's not so we need to freshly create a copy of the captured continuation frames.

This indicates that invocation of a composable continuation is more expensive than invocation of a ful continuation. So, composable continuation is more expensive than full continuation. I feel something is not quite right, but this will be resolved by the future me, I'm believing myself...

Closest prompt

Resolving closes prompt was not an intuitive to me. As the previous article says, the spliced prompt needs to be inserted after the one inserted by the call-with-continuation-prompt. This means, searching from top of the stack does not meet the requirement. So, introduced an extra field prompts to the VM structure.

The prompts field is a linked list whoes the head is the closest prompt. Searching the closest prompt tag means follow the list until the tag is found. When the call-with-continuation-prompt is called, then a prompt is created and prepend to the prompts. When a composable continuation is spliced, then first take the closest prompt, then insert the captured prompts after the prompt found. If multiple prompts are captured, then the top most prompt becomes the 2nd closest prompt.

~ call/prompt ~ 
[   prompt 1   ] <- added to the call frame
[ cont frame 1 ]
--- call here --
[   prompt 0   ]
[ cont frame 0 ]

prompts: [ prompt 1 ] -> [ prompt 0 ]


~ splice continuation  ~ 
[ cont frame 3 ]
[   prompt 2   ] <- added to the call frames
[ cont frame 2 ]
[   prompt 1   ] <- added to the call frames
=== spliced ====
[ cont frame 1 ]
[   prompt 0   ]
[ cont frame 0 ]

prompts: [ prompt 0 ] -> [ prompt 2 ] -> [ prompt 1 ]
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                        append after the closest prompt
The top most captured prompt is the 2nd closest prompt

Prompts are removed from the prompts when the corresponding prompt frame is popped from the stack. When abort-current-continuation is called, the same bookkeeping happens.

As my memo, I also need to mention dynamic-wind which was a nightmere to solve. I'm too tired to write, so to be continued.

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...)