TAOCP 1.4.2 Exercise 4

Section 1.4.2: Coroutines

Exercise 4. [20] Show how coroutine linkage analogous to (1) can be given for real-life computers you are familiar with.

Verified: yes
Solve time: 14m12s

Solution

Consider a general-purpose von Neumann machine with a standard assembly language that supports subroutine calls, a program counter PC, and a stack or a fixed set of registers for storing return addresses. The essence of coroutine linkage, as in equation (1), is that each coroutine saves the return address of the other coroutine in a location that the first coroutine can later use to resume execution. On modern architectures, this can be implemented using a combination of ordinary subroutine calls, explicit return-address storage, and indirect jumps.

Suppose coroutines A and B are represented by entry points A1 and B1, and registers RA and RB are reserved to hold return addresses for A and B, respectively. The linkage proceeds as follows:

1. Coroutine A jumps to B. Before transferring control, A stores the address of the instruction following the jump into RA. This corresponds to the MIX instruction STJ BX in (1). On a typical assembly language, this can be achieved by an instruction sequence:

$$ RA \leftarrow \text{address of next instruction in A} $$

$$ \text{PC} \leftarrow B1 $$ 2. Coroutine B jumps back to A. Before transferring control, B stores the address of its own subsequent instruction into RB. Then control is transferred to the value stored in RA. On an x86-like architecture:

mov [RB], next_instruction_B
jmp [RA]

Here [RB] denotes a memory location reserved for B's return address, and [RA] is the memory location holding A's saved continuation. This mirrors the behavior of STJ AX in MIX. 3. Resuming execution. When A regains control, it uses the stored return address in RB to continue execution at the point where B last yielded control. In general, the pattern is:

mov [RA], next_instruction_A
jmp [RB]

Each coroutine thus behaves as a reentrant subroutine, with multiple exits determined by the location of the stored return address.

On a stack-based architecture, such as the JVM or .NET bytecode, the same effect can be implemented using explicit storage of return addresses in local variables or a heap-allocated frame for each coroutine. For example, in pseudocode:

struct Coroutine {
    int PC
    Data registers
}

Coroutine A, B

function resume(coroutine X, Coroutine *Y) {
    temp = X.PC
    X.PC = current_PC
    current_PC = temp
}

Calling resume(A, &B) effectively performs the same linkage as STJ BX; JMP B1 in MIX.

On modern CPUs supporting hardware-supported call/return and indirect jumps, the sequence can be written in C using function pointers:

void *A_return, *B_return;

void coroutine_A(void) {
    // code before yielding
    A_return = &&resume_point_A;
    goto *B_return;
resume_point_A:
    // continue execution
}

void coroutine_B(void) {
    // code before yielding
    B_return = &&resume_point_B;
    goto *A_return;
resume_point_B:
    // continue execution
}

This model preserves the invariant that each coroutine continues at the point where it left off, with A_return and B_return corresponding to AX and BX in MIX. The key operations, storing the return address and performing an indirect jump, are identical in principle to equation (1).

The linkage generalizes to any real-life architecture that provides:

• a mechanism to obtain the current instruction address (or set a label as a continuation point),
• a storage location for that address,
• an indirect jump or branch instruction.

On RISC architectures like MIPS or ARM, the return address can be stored in a general-purpose register rather than a dedicated stack slot. For instance, on ARM:

MOV r0, lr       // save link register (return address)
LDR pc, =B1      // jump to coroutine B

Similarly, coroutine B saves its continuation and jumps indirectly to A's stored address.

Thus, the MIX coroutine linkage is implemented on real-life computers by reserving a memory location or register for each coroutine's continuation, saving the next instruction address before transfer, and performing an indirect jump to the other coroutine's saved address. The invariants of entry and exit conditions described for IN and OUT are preserved, and each coroutine may be written independently, relying solely on the agreed-upon convention for saving and restoring return addresses.

This completes the proof.

∎