TAOCP 1.4.2 Exercise 5

In the coroutine linkage of §1.

taocpmathematicsalgorithmsvolume-1simple

Section 1.4.2: Coroutines

Exercise 5. [15] Suppose both coroutines IN and OUT want the contents of register A to remain untouched between exit and entry; in other words, assume that wherever the instruction JMP IN occurs within OUT, the contents of register A are to be unchanged when control returns to the next line, and make a similar assumption about JMP OUT within IN. What coroutine linkage is needed? (Compare with (4).)

Verified: no
Solve time: 4m37s

Solution

In the coroutine linkage of §1.4.2,

OUT   STJ IN
      JMP OUT1

IN    STJ OUT
      JMP IN1

the locations IN and OUT are not fixed entry points. They are modified by STJ, so that a later JMP IN or JMP OUT resumes the suspended coroutine at the proper continuation point.

To preserve register $A$, each coroutine must have its own saved value of $A$. When a coroutine yields control, its current value of $A$ must be saved. When that coroutine is later resumed, the saved value must be restored before execution continues.

The restoration must therefore be incorporated into the continuation mechanism itself.

Let AIN and AOUT be memory cells containing the saved values of $A$ for coroutines IN and OUT, respectively. Replace the linkage by

OUT    STA AOUT
       STJ OUTRET
       JMP OUT1

OUTRET LDA AOUT
       JMP *

IN     STA AIN
       STJ INRET
       JMP IN1

INRET  LDA AIN
       JMP *

AIN    CON 0
AOUT   CON 0

Here OUTRET and INRET are the locations used in the coroutine linkage. The instruction STJ OUTRET stores the return address into the address field of the instruction at OUTRET; similarly STJ INRET stores a return address into INRET.

To see how this works, suppose IN executes JMP OUT with $A=a$.

  1. Control enters OUT.
  2. STA AOUT saves the value $a$ belonging to the suspended coroutine IN's partner, namely the coroutine being entered will later need its own value preserved.
  3. STJ OUTRET records the continuation point of IN in the usual coroutine manner.
  4. JMP OUT1 begins or resumes execution of OUT.

Now suppose later OUT executes JMP IN with $A=b$.

  1. Control enters IN.
  2. STA AIN saves the value $b$ associated with OUT.
  3. STJ INRET records the continuation point of OUT.
  4. JMP IN1 transfers to the address currently stored in location IN.

But location IN was previously modified by STJ OUTRET. Hence control returns to

OUTRET LDA AOUT
       JMP *

The instruction LDA AOUT restores the value of $A$ that belonged to OUT when it last yielded control. The following JMP * then jumps to the continuation address that STJ OUTRET placed into the instruction.

Thus OUT resumes exactly where it left off, with the same contents of register $A$.

The argument for IN is symmetric. When IN is later resumed, execution first reaches

INRET  LDA AIN
       JMP *

which restores the value of $A$ that IN had when it previously yielded control, and then continues at the recorded return address.

Therefore the required coroutine linkage is obtained by replacing each return location with a two-instruction sequence

RET    LDA saved_A
       JMP *

and arranging that each coroutine saves its own value of $A$ before yielding. This preserves register $A$ across every JMP IN and JMP OUT, while retaining the normal coroutine return mechanism.