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.