Vicare Scheme: machinery continuations non

16.5.4 Subordinate function calls with non–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 but does not call its escape function:

(import (rnrs))
(define (alpha A)
  (beta A))
(define (beta B)
  (call/cc
     (lambda (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 non.

      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 |         .
|----------------------|         --
|    argument B == 1   |         .
|----------------------|         . frame of beta
| return addr to beta  | <- FPR  .
|----------------------|         --
|   closure reference  |         . locals of call/cc
|----------------------|         .
|                      |
       low memory

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

For convenience we give a name to the closure (lambda (escape) (+ B 2)), let’s call it receiver⁴. 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 non.

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

Figure 16.18: 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 the time of creation. 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 non.
```
|--------|---| PCB
           |
     next_k --------> |-----|-| K_1
                             |
                         next -----> NULL
```
Figure 16.19: 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 non. 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.20: Closure object implementing the escape function for K_1.

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

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

Figure 16.21: 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 executes (+ B 2) and returns; there is only a single return value: it is put in AAR and the return from the closure is performed with a ret Assembly instruction. We skip the details of performing the addition and consider the stack right before the ret Assembly instruction is executed by the CPU, machinery continuations non.

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

Figure 16.22: Stack right before the receiver closure executes the ret Assembly instruction; the single return value is in AAR.

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 beta and a new continuation object K_2 referencing all the other frames, machinery continuations non.

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

Figure 16.23: 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 non.

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

Figure 16.24: 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 non.

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

Figure 16.25: 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 beta.

The code of beta 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 non. beta must return the same return value, which is already in the AAR: it executes a ret Assembly instruction.

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

Figure 16.26: Stack right before beta 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 multiframe continuation object as “next PCB continuation”, so split K_2 in two continuation objects: the mutated K_2 referencing only the frame of alpha and a new continuation object K_3 referencing all the other frames, machinery continuations non.

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

Figure 16.27: Continuation object K_2 mutated to reference a single frame.

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

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

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

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

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

Figure 16.29: 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 body of alpha.

The code of alpha is reentered right after the call to beta and the FPR is adjusted to reference the address of the stack underflow handler, compiler machinery continuations non. 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
|----------------------|                     -- frames
|  return addr to top  |                     .  in K_3
|----------------------|                     --
|    argument A == 1   |                     .
|----------------------|                     . frames
| return addr to alpha |                     . in K_2
|----------------------|                     --
|    argument B == 1   |                     . freezed
|----------------------|                     . frame
| return addr to beta  | <- pcb->frame_base  . in K_1
|----------------------|                     --
| ik_underflow_handler | <- FPR
|----------------------|
|                      |
       low memory

Figure 16.30: 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 as “next PCB continuation”, so set pcb->next_k to the next field in K_3, machinery continuations non.

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

Figure 16.31: Continuation object K_3 removed from the PCB.

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

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

Figure 16.32: Stack frame in K_3 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
|----------------------|                     -- frames
|  return addr to top  |                     .  in K_3
|----------------------|                     --
|    argument A == 1   |                     .
|----------------------|                     . frames
| return addr to alpha |                     . in K_2
|----------------------|                     --
|    argument B == 1   |                     . freezed
|----------------------|                     . frame
| return addr to beta  | <- pcb->frame_base  . in K_1
|----------------------|                     --
| ik_underflow_handler | <- FPR
|----------------------|
|                      |
       low memory

Figure 16.33: 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.

Footnotes

(4)

Springer and Friedman call it “receiver” in their “Scheme and the Art of Programming”, The MIT Press, 1989.