Vicare Scheme: machinery continuations escape

16.5.5 Subordinate function calls with invoked continuation

We assume the validity of machinery simplifications to focus on some aspect of the runtime behaviour, Simplification assumptions. Let’s consider the following program that creates a continuation and invokes its escape function:

(import (rnrs))
(define (alpha A)
  (call/cc
     (lambda (escape)
       (beta escape A))))
(define (beta escape B)
  (escape (+ B 2)))
(alpha 1)

we can understand how the stack grows until right after the call to call/cc but before call/cc actually does something, machinery continuations escape.

      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler |
|----------------------|         --
|  return addr to top  |         . frame of toplevel
|----------------------|         --
|    argument A == 1   |         .
|----------------------|         . frame of alpha
| return addr to alpha |         .
|----------------------|         --
|      receiver        |         . locals of call/cc
|----------------------|         .
|                      |
       low memory

Figure 16.34: Stack right after the call to call/cc but before call/cc does something.

call/cc creates a continuation object by freezing the call frames currently on the stack between FPR and 2 words below pcb->frame_base, machinery continuations escape.

      high memory
|                      |
|----------------------|
|                      | <- pcb->frame_base
|----------------------|
| ik_underflow_handler |
|----------------------|         --
|  return addr to top  |         .
|----------------------|         . freezed
|    argument A == 1   |         . frames
|----------------------|         .
| return addr to alpha | <- FPR  .
|----------------------|         --
|       receiver       |         . locals of
|----------------------|         . call/cc
|                      |
       low memory

Figure 16.35: Region of stack freezed by call/cc.

The continuation object references the array of freezed words on the stack, keeping a reference to the value of FPR at creation time. The continuation object is also a node in a simply linked list of continuation objects, whose head is stored in a field of the PCB: pcb->next_k. In more detail call/cc does the following:

Create the continuation object and prepend it to the list in pcb->next_k; let’s call this continuation object K_1; machinery continuations escape.
```
|--------|---| PCB
           |
     next_k --------> |-----|-| K_1
                             |
                         next -----> NULL
```
Figure 16.36: Continuation object K_1 inserted as new “next PCB continuation”.
Create a closure object implementing the escape function associated to the continuation object, the one that will be bound to escape in the example; machinery continuations escape. In the closure object: the address of the code entry point references the special subroutine SL_continuation_code, the single slot for free variables references the continuation object.
```
|-----|-----| closure object
   |     |
   |      --------> |------| K_1
   |
    --------------> |------| code object
```
Figure 16.37: Closure object implementing the escape function for K_1.

Prepare the application of the receiver closure to the escape function: the reference to the receiver closure is moved in the CPR; the address of the underflow handler is moved on the stack and the FPR is set to reference it; the value of pcb->frame_base is set to exclude the freezed frames from the stack segment; machinery continuations escape.

      high memory
|                      |
|----------------------|
| ik_underflow_handler |
|----------------------|                     --
|  return addr to top  |                     .
|----------------------|                     . freezed
|    argument A == 1   |                     . frames
|----------------------|                     . in K_1
| return addr to alpha | <- pcb->frame_base  .
|----------------------|                     --
| ik_underflow_handler | <- FPR
|----------------------|                     -- locals of
|    escape closure    |                     .  receiver
|----------------------|                     .  closure
|                      |
       low memory

Figure 16.38: Stack right before the call to the receiver closure.

Perform a direct jump to the entry point of the receiver closure without pushing a return address on the stack. The FPR is left referencing the entry point of the stack underflow handler.

In this example, the receiver closure calls beta with 2 arguments, machinery continuations escape.

      high memory
|                      |
|----------------------|
| ik_underflow_handler |
|----------------------|                     --
|  return addr to top  |                     .
|----------------------|                     . freezed
|    argument A == 1   |                     . frames
|----------------------|                     . in K_1
| return addr to alpha | <- pcb->frame_base  .
|----------------------|                     --
| ik_underflow_handler |
|----------------------|                     -- frame of
| return addr to receiv| <- FPR              .  receiver
|----------------------|                     --
|    escape closure    |                     . locals
|----------------------|                     . in beta
|    argument B == 1   |                     .
|----------------------|                     .
|                      |
       low memory

Figure 16.39: Stack right after the call to beta.

beta applies the escape closure to the result of (+ B 2), let’s skip the details of performing the addition. To apply the escape closure to the single argument representing the addition: the reference to escape function is copied in the CPR, the single argument is placed after an empty machine word, the FPR is moved right above the empty word, finally a call Assembly instruction is executed, machinery continuations escape.

      high memory
|                      |
|----------------------|
| ik_underflow_handler |
|----------------------|                     --
|  return addr to top  |                     .
|----------------------|                     . freezed
|    argument A == 1   |                     . frames
|----------------------|                     . in K_1
| return addr to alpha | <- pcb->frame_base  .
|----------------------|                     --
| ik_underflow_handler |
|----------------------|                     -- frame of
| return addr to receiv| <- FPR              .  receiver
|----------------------|                     --
|    escape closure    |                     .
|----------------------|                     .  frame
|    argument B == 1   |                     .  of beta
|----------------------|                     .
| return addr to beta  | <- FPR              .
|----------------------|                     --
|   argument fixnum 3  |                     . locals of
|----------------------|                     . escape
|                      |
       low memory

Figure 16.40: Stack right after the call to escape.

A continuation’s escape function is a special subroutine that throws away all the stack frames up to, and excluding, the undeflow handler address below the pcb->frame_base, machinery continuations escape.

      high memory
|                      |
|----------------------|
| ik_underflow_handler |
|----------------------|                     --
|  return addr to top  |                     .
|----------------------|                     . freezed
|    argument A == 1   |                     . frames
|----------------------|                     . in K_1
| return addr to alpha | <- pcb->frame_base  .
|----------------------|                     --
| ik_underflow_handler | <- FPR
|----------------------|
|                      |
       low memory

Figure 16.41: Stack right after escape has thrown away the useless stack frames.

The argument of the escape function becomes its return value; in this example there is a single return value, so it is moved in the AAR. The continuation object K_1 in the escape closure is stored in pcb->next_k, becoming the “next PCB continuation”; the old value of pcb->next_k is simply overwritten: a new list of continuations is installed in the PCB. Finally a ret Assembly instruction is executed.

The FPR references the underflow handler, so the ret instruction will cause the execution flow to jump there; the stack underflow handler does the following:

Detect the presence of a multiframe continuation object as “next PCB continuation”, so split K_1 in two continuation objects: the mutated K_1 referencing only the frame of alpha and a new continuation object K_2 referencing all the other frames, machinery continuations escape.

      high memory
|                      |
|----------------------|
| ik_underflow_handler |
|----------------------|                     -- freezed
|  return addr to top  |                     .  frame K_2
|----------------------|                     --
|    argument A == 1   |                     . freezed
|----------------------|                     . frame
| return addr to alpha | <- pcb->frame_base  . in K_1
|----------------------|                     --
| ik_underflow_handler | <- FPR
|----------------------|
|                      |
       low memory

Figure 16.42: Continuation object K_1 mutated to reference a single frame.

Insert K_2 in the linked list of continuation objects after K_1 and register it as the new “next PCB continuation”, machinery continuations escape.

|--------|---| PCB
           |
     next_k|     |-----|-| K_1
           |            |
           |        next -->|
            --------------->|-----|-| K_2
                                   |
                               next -----> NULL

Figure 16.43: Continuation object K_2 inserted as new “next continuation”.

Duplicate the stack frame referenced by K_1 below the address of the underflow handler, adjust the FPR to reference the return address of the frame, machinery continuations escape.

      high memory
|                      |
|----------------------|
| ik_underflow_handler |
|----------------------|                     -- freezed
|  return addr to top  |                     .  frame K_2
|----------------------|                     --
|    argument A == 1   |                     . freezed
|----------------------|                     . frame
| return addr to alpha | <- pcb->frame_base  . in K_1
|----------------------|                     --
| ik_underflow_handler |
|----------------------|
|    argument A == 1   |
|----------------------|
| return addr to alpha | <- FPR
|----------------------|
|                      |
       low memory

Figure 16.44: Stack frame in K_1 duplicated below the underflow handler address.

There is a single return value, so: perform a ret Assembly instruction to go back to the body of alpha.

The code of alpha is reentered right after the call to call/cc and the FPR is adjusted to reference the address of the stack underflow handler, compiler machinery continuations escape. alpha must return the same return value, which is already in the AAR: it executes a ret Assembly instruction.

      high memory
|                      |
|----------------------|
| ik_underflow_handler |
|----------------------|                     -- freezed
|  return addr to top  |                     .  frame K_2
|----------------------|                     --
|    argument A == 1   |                     . freezed
|----------------------|                     . frame
| return addr to alpha | <- pcb->frame_base  . in K_1
|----------------------|                     --
| ik_underflow_handler | <- FPR
|----------------------|
|                      |
       low memory

Figure 16.45: Stack right before alpha executes the ret Assembly instruction; the return value is in the AAR.

The stack underflow handler is reentered and does the following:

Detect the presence of a single–frame continuation object K_2 as “next PCB continuation”, so store its next continuation reference in pcb->next_k, machinery continuations escape.
```
|-----|---| PCB
        |
  next_k|   |-----|-| K_1
        |          |
        |      next -->|-----|-| K_2
        |                     |
        |                 next -----> NULL
         --> NULL
```
Figure 16.46: Continuation object K_2 removed from the PCB.

Duplicate the stack frame referenced by K_2 below the address of the underflow handler, adjust the FPR to reference the return address of the frame, machinery continuations escape.

      high memory
|                      |
|----------------------|
| ik_underflow_handler |
|----------------------|                     -- freezed
|  return addr to top  |                     .  frame K_2
|----------------------|                     --
|    argument A == 1   |                     . freezed
|----------------------|                     . frame
| return addr to alpha | <- pcb->frame_base  . in K_1
|----------------------|                     --
| ik_underflow_handler |
|----------------------|
|  return addr to top  | <- FPR
|----------------------|
|                      |
       low memory

Figure 16.47: Stack frame in K_2 duplicated below the underflow handler address.

There is a single return value, so: perform a ret Assembly instruction to go back to the top level expression.

The code of the top level expression is reentered right after the call to alpha and the FPR is adjusted to reference the address of the stack underflow handler, compiler machinery continuations escape. The top level expression is the last one in the program, so it returns the return value it receives, which is already in the AAR: it executes a ret Assembly instruction.

      high memory
|                      |
|----------------------|
| ik_underflow_handler |
|----------------------|                     -- freezed
|  return addr to top  |                     .  frame K_2
|----------------------|                     --
|    argument A == 1   |                     . freezed
|----------------------|                     . frame
| return addr to alpha | <- pcb->frame_base  . in K_1
|----------------------|                     --
| ik_underflow_handler | <- FPR
|----------------------|
|                      |
       low memory

Figure 16.48: Stack right before the top level expression executes the ret Assembly instruction; the return value is in the AAR.

The underflow handler is reentered again with NULL as “next PCB continuation”: this means the program is terminated, so the underflow handler does what is needed.

We can understand that this mechanism of duplicating the freezed frames can be repeated any number of times, allowing the execution flow to go back to a saved continuation any number of times.