TAOCP 1.4.2 Exercise 2
The coroutine linkage is OUT STJ INX OUTX JMP OUT1 IN STJ OUTX INX JMP IN1
Exercise 2. [20] The program in the text starts up the OUT coroutine first. What would happen if IN were the first to be executed, that is, if line 60 were changed from JMP OUT1 to JMP IN1?
Verified: yes
Solve time: 39s
Solution
The coroutine linkage is
OUT STJ INX
OUTX JMP OUT1
IN STJ OUTX
INX JMP IN1
and in the text the program is initialized by
START ENT6 0
ENTX 0
JMP OUT1
so that the output coroutine performs its initialization before the input coroutine is ever entered.
Suppose instead that the last instruction is changed to
JMP IN1
and execution begins with IN.
The first entry into IN occurs through
IN1 JMP NEXTCHAR
and eventually a translated output character is produced. The details of the translation are immaterial; let the first character produced be $c_1$. At the point where IN has finished producing $c_1$, that character is in register $A$, and IN executes
JMP OUT
to hand the character to the output coroutine.
Since OUT has never yet been entered, the instruction at OUTX is still its original value
OUTX JMP OUT1 .
Hence the transfer proceeds as follows:
OUT STJ INX
OUTX JMP OUT1
The STJ INX stores the return address, namely the location immediately following the JMP OUT in IN. Then control goes to OUT1.
Now OUT performs its startup sequence:
OUT1 ENT4 -16
ENT1 OUTPUT
MOVE -1,1(16)
and reaches the point where it requests a character from IN:
1H JMP IN
The jump to IN executes
IN STJ OUTX
INX JMP ...
The instruction STJ OUTX replaces the original JMP OUT1 by a jump back to the point immediately following this JMP IN. Since INX was previously modified by OUT, control now resumes exactly where IN left off, namely at the instruction after the original JMP OUT.
Observe what has happened. When IN first transferred to OUT, the character $c_1$ was available in register $A$. But OUT did not execute its normal character-receiving code. Instead, because OUTX still contained JMP OUT1, it executed its initialization code and then immediately requested another character from IN.
Thus $c_1$ was never consumed by OUT. The output coroutine has effectively skipped the first item produced by the input coroutine.
After resuming, IN continues its computation and eventually produces the next output character $c_2$. When it again executes
JMP OUT
the situation is different. The instruction at OUTX no longer jumps to OUT1; it now jumps to the point immediately following the request
1H JMP IN
in the output coroutine. Therefore this second transfer is the first one that reaches the normal character-processing code of OUT, and the character received by OUT is $c_2$, not $c_1$.
The same pattern continues thereafter. The output coroutine receives
$$ c_2,; c_3,; c_4,; \ldots $$
instead of
$$ c_1,; c_2,; c_3,; \ldots $$
Hence the first translated character $c_1$ is lost permanently, and every subsequent output position contains the character that should have appeared one position later.
Therefore the program no longer produces the correct output. Starting execution with IN causes the first character generated by the input coroutine to be discarded, because the first transfer to OUT is consumed by OUT's initialization rather than by its normal character-receiving code. All later coroutine exchanges proceed normally, but with the output stream missing its first character. ∎