Methods of Programming - 1 - Coroutines

Methods of Programming - 1 - Coroutines

Chapter : Coroutines

PLAN
1) Motivations.
2) Syntax
3) Scenario
4) Examples

1) Motivations.

In the practice of programming one meets frequently situations in which it is natural to split an algorithm between "actors". A simple example of creating a histogram can serve as a guide to our intuition. In order to create a histogram of experimental data one has to measure the data and to enter them into a table. Later the table is printed in graphical mode or in columns showing the effects of the experiment. It is quite natural to imagine that we have two algorithms which interleave their actions: one for the control of the experiment and another for introducing the data into histogram's table. This modular approach can assure more flexibility and adaptability of our software. We need not to change the module that controls the experiment and introduce into it a new functions every time we are modifying the way the data are used and interpreted.

Another place where coroutines are more than natural, where they are simply needed, is simulation. We shall present later a problem oriented language for simulation of any discrete time events together with an example of an application. The language is realized as a class Simulation and is an alternative to the Simula's simulation class.

Yet another natural application of coroutines are games. It is much easier to organize a match of two different strategies (say, they are implemented by two masters of chess) if they are programmed as coroutines.

The system of coroutines we present here seems to be simpler, easier to understand and to implement efficiently than others known to us.

2) Syntax

A coroutine module has the structure almost the same as a module of a class. The only visible difference is: where the keyword class was, now one finds another keyword coroutine. Hence a declaration of a coroutine has the form:

unit name_of_coroutine >: coroutine(<formal parameters>);
<local declarations
of variables, procedures, functions and classes!
begin
<instructions
endname_of_coroutine

The name of a coroutine may be prefixed as any module. Then the first line reads:
unit coroutine_name>: <prefixcoroutine(<formal parameters>);
A coroutine can also prefix another module: a class, a coroutine, a process

Every coroutine can serve as a pattern to create coroutine's objects. One uses exactly the same way in order to create an object:
new Cor1(<actual_parameters>).

Suppose we have declared a variable of type Cor1
var c: Cor1;
then the created object can be assigned to the variable c in a ususal manner
c:= new Cor1(<actual_parameters>) .

In a coroutine one can use two built in operations attach and detach. Their meaning is described below.

The word coroutine will denote modules as well as objects of the modules. We hope that no confusion will arise. Sometimes we shall use a lengthy word: coroutine-object.

3) Scenario

The diagram below can be conceived in two slightly different ways. First, it may illustrate the behaviour of a coroutine object. Second, it may be viewed as a partition of a set of coroutines (objects) that exist at any moment of a computation into subsets and as the indication which transitions are possible and what are the conditions necessary to move a coroutine from one set (read: state) into another. The subsets of partition are called the states: Initialization state, Passive state, Active state, Terminated state. Coroutine-objects are created by means of object generator expression which we know already. Then a coroutine is entering its initialization phase. This phase resembles very much an execution of a procedure, but it is exactly the initialization of an object phase. That is: an object is created, actual parameters are transmitted and the instructions of the object (i.e. modified instructions from the coroutine module) are executed in turn. Initialization ends when an instruction return was encountered and executed. Then the object is ready and it is put into the basket of Passivated coroutine-objects. It may happen that we executed all instructions and came to the end. What happens then? The answer reads: the coroutine becames a terminated object. The difference between a passive object and a terminated object lies in its ability to be activated. A passive coroutine can be activated by an external action, see the diagram - attach is outside the box PASSIVE. A terminated coroutine-object is just an object. It can serve with its resources (i.e. the variables and constants declared within) and with its methods (i.e. the functiuons and procedures of the objects which can be called remotely). An active coroutine-object executes its instruction continuing after the last point the execution of the coroutine was suspended. How to suspend the execution of a coroutine? First, it is the instruction return which finishes initialization of a coroutine-object, makes it passive, ready for future activation and suspends it. Second, it is the instruction attach(c) which suspends the currently executed coroutine, and moves the processor to the object c where the execution is resumed at the last point of suspension. The attach instruction can be successfully executed iff the object c is a coroutine-object in its passive state. Let us remark that none is not a coroutine-object, that a coroutine which executed all its instruction and went to its end is not a passive coroutine-object. At every moment when the processor leaves one coroutine-object and comes to another coroutine-object, notes are taken, where to resume the execution when the coroutine will be activated again? and every coroutine-object at its activation remembers the name of the coroutine which activated it (i.e. the coroutine that was the last active one). With this information, we are ready to learn about the detach instruction. Any active coroutine can perform a detach instruction. The effect of detach is equivalent to: attach(the coroutine-object that activated the current coroutine).
The picture is more complicated as it may seem, because usually there are objects of classes and activation records of procedures. We shall discuss it later, in the example of merging binary search trees.

Now, let us try to repeat: given set of coroutine-objects can be augmented by a new one if the coroutine-object generator expression new Cor1(act.par.) is elaborated and when the initialization meets the instruction return. The new coroutine-object is passive. At most one coroutine-object is active. That is in order to activate a coroutine another coroutine must suspend its activity. Therefore, the main program is also a coroutine. Each transfer of a coroutine-object from the set of Passive coroutine-objects to the set Active must be and is compensated by the suspension of the currently active coroutine-object. The means of the activation-passivation are: attach to an explicitly named coroutine, or detach return the processing ability to the coroutine-object to the coroutine-object that activated the currently active coroutine. Each coroutine may be turned to a terminated object when its instructions are exhausted, i.e. when it meets its end.

Fig. 3 Scenario of a coroutine_object

4) Examples

In the example below the cooperation of two coroutines is presented. One reads the real values from an input device, another prints these values in columns on a line-printer, n numbers in a line. The input stream ends with 0.

program prodcons;
varprod:producer,cons:consumer,n:integer,mag:real,last:bool;
unit producer: coroutine;
begin
return; (* 1 *)
do
read(mag); (* mag-nonlocal variable, common store*)
if mag=0
then (* end of data *)
last:=true;
exit
fi;
attach(cons); (* A *)
od;
attach(cons) (* B *)
end producer;

unit consumer: coroutine(n:integer);
var Buf:arrayof real;
var i,j:integer;
begin
new_array Buf dim(1:n);
return; (* 2*)
do
for i:=1 to n
do
Buf(i):=mag;
attach(prod); (* C *)
if last then exit exit fi;
od;
for i:=1 to n
do (* print Buf *)
write(' ',Buf(i):10:2)
od;
writeln;
od;
(* print the rest of Buf *)
for j:=1 to i do write(' ',Buf(j):10:2) od;
writeln;
attach(main); (* D *)
end consumer;

begin (* MAIN program *)
prod:=new producer;
read(n);
cons:=new consumer(n);
attach(prod); (* R *)
writeln;
end prodcons;

The execution of the prodcons program begins in the activation record of the main block of the program. It is also known as a coroutine object named main.
The instructions of
main
cause the creation (and initialization) of objects prod of type producer and cons of type consumer. The instruction attach(prod) causes that the main object is desactivated and
prod
becames the active coroutine. It executes its instructions till the command attach(cons) is reached. At that point prod becames passive object and
cons
object is activated. Cons executes its commands till the command attach(prod) will be reached. At that moment
prod
will be activated, at the point just after the last command attach were executed i.e. at its command marked A. It will execute its command once again and it will reach again the command attach(cons). The object
cons
will be activated at its latest activation point i.e. at the command marked C.

This will happen several times.
If prod coroutine object will find mag=0 it will put last=true and it will reactivate cons object. The cons coroutine will print the remainder of buffer and it will reactivate main object in order to terminate the program's execution.

The above task could be programmed without coroutines at all. The presented solution is, however, strictly modular, i.e. one unit realizes the input process, another realizes the output process, and both are ready to cooperate with each other.

LOGLAN-82 provides also a facility for the semi-coroutine operations. This is done by the simple statement detach. If X is the active coroutine object, then detach reactivates that coroutine object at where the last attach(X) was executed. This statement meets the need for the asymmetric coroutine cooperations. (for this reason it is called semi-coroutine operation). Operation attach requires a reactivated coroutine to be defined explicitly by the user as an actual parameter. Operation detach corresponds in some manner to return in procedures. It gives the control back to a coroutine object where the last attach(X) was executed, and that coroutine object need not be known explicitly in X. This mechanism is, however, not so secure as the normal control transfers during procedure calls and returns.

In fact, the user is able to loop two coroutines traces by :

attach(Y) in X attach(X) in Y

Then detach in X reactivates Y, detach in Y reactivates X.

In the example below a correct application of detach statement is illustrated.

Example:

program reader_writers;
(* In this example a single input stream consisting of blocks of numbers, each ending with 0, is printed on two printers of different width. The choice of the printer is determined by the block header which indicates the desired number of print columns. The input stream ends with a double 0. m1 = the width of printer_1, m2 = the width of printer_2 *)
const m1=10,m2=20;
var reader:reading,printer_1,printer_2:writing;
var n:integer,new_sequence:boolean,mag:real;
unit writing:coroutine(n:integer);
var Buf: arrayof real, i,j:integer;
begin
new_array Buf dim (1:n); (* array generation *)
return; (* return terminates coroutine initialization *)
do
attach(reader); (* reactivates coroutine reader *)
if new_sequence
then
(* a new sequence causes buffer Buf to be cleared up *)
for j:=1 to i do write(' ',Buf(j):10:2) od; writeln;
i:=0; new_sequence:=false; attach(main)
else
i:=i+1; Buf(i):=mag;
if i=n
then
for j:=1 to n do write(' ',Buf(j):10:2) od; writeln;
i:=0;
fi
fi
od
end writing;

unit reading: coroutine;
begin
return;
do
read(mag);
if mag=0 then new_sequence:=true; fi;
detach; (* detach returns control to printer_1 or printer_2 depending which one reactivated reader *)
od
end reading;

begin
reader:=new reading;
printer_1:=new writing(m1);
printer_2:=new writing(m2);
do
read(n);
case n
when 0: exit
when m1: attach(printer_1)
when m2: attach(printer_2)
otherwise write(" wrong data"); exit
esac
od
end;

The above picture shows the configuration of coroutine_objects. The red(thick) lines show the activation of coroutine_objects. Remark that the detach statement in the reader object will return the control to the object printer1 or printer2 whichever executed the command attach(reader) lastly.

Coroutines play the substantial role in process simulation. Class Simulation provided in Simula-67 makes use of coroutines at most degree. LOGLAN-82 provides for easy simulation as well. The LOGLAN-82 class Simulation is implemented on a heap what gives O(log(n)) time cost (in contrast with O(n) cost of the Simula'67 implementation). It covers also various simulation problems of large size and degree of complexity.

In the example below coroutines cooperate nicely with recursive procedures. Remark how a detach statement may appear in a procedure and what it causes.

To understand the example you have to imagine how a binary search tree will be constructed by the consecutive calls of n.INS, where n denotes a NODE object. Then think of procedure T (it is in the unit TRAVERS). For the beginning replace the word detach in T by write(val). What will happen if you will call T? Good, the sequence of numbers stored in the tree will appear in the increasing order. Now, what happen when we put "detach" back to its place? Suppose that an external coroutine repeats attach(your_root). Aha, the same ordering result can be observed. Now, have a look at the source of the complete program. I suggest, run it! and see.

PROGRAM Merge;
(* COROUTINES MERGE BINARY SEARCH TREES *)
UNIT NODE : CLASS;
(* NODE OF BINARY TREE *)
VAR LEFT,RIGHT : NODE, VAL : INTEGER; (*SEARCHING KEY *)
UNIT INS : PROCEDURE (VALUE : INTEGER);
BEGIN
IF VAL> VALUE
THEN
IF LEFT = NONE
THEN
LEFT := NEW NODE;
LEFT.VAL := VALUE
ELSE
CALL LEFT.INS(VALUE)
FI
ELSE
(* ELEMENTS NOT LESS THAN VAL ARE LOCATED IN RIGHT SUBTREE*)
IF RIGHT = NONE
THEN
RIGHT := NEW NODE;
RIGHT.VAL := VALUE
ELSE
CALL RIGHT.INS(VALUE)
FI
FI;
END INS;
END NODE;
UNIT TRAVERS : COROUTINE (X :NODE);
(* CONSECUTIVE ELEMENTS OF TREE NODE ARE LOCATED IN THE GROWING ORDER TOTHE "MAIL BOX" VAL AND SENT TO THE ATTACHING UNIT *)
VAR VAL : INTEGER;
UNIT T : PROCEDURE (Y : NODE);
(* RECURSIVE PROCEDURE FOR INFIX TRAVERSION BRINGS THE TREE'S ELEMENTSIN NOT DECREASING ORDER *)
BEGIN
IF Y =/= NONE
THEN
CALL T(Y.LEFT); (* after you visited the left
subtree, you give val and detach *)
VAL := Y.VAL;
DETACH;
(* CONSECUTIVE ELEMENTS OF TREE Y ARE SENT FOR FURTHER PROCESSING TO THE MASTER PROGRAM *)
CALL T(Y.RIGHT);
FI
END T;
BEGIN
RETURN;
CALL T(X);
VAL := M;
(* VAL IS MAXIMAL VALUE TREATED AS A SENTINEL WHILE ENTIRE TREE IS TRAVESED *)
END TRAVERS;
VAR N,I,J,MIN,M,K : INTEGER,
(* N - TNE NUMBER OF TREES
M - MAXIMAL KEY VALUE + 1
MIN- MINIMAL VALUE PRODUCED AT A GIVEN MOMENT BY SYSTEM OF COROUTINES*)
D : ARRAYOF NODE,
TR : ARRAYOF TRAVERS;
BEGIN
WRITELN(" PROGRAM USES COROUTINES AND MERGES A GIVEN NUMBER ",
" OF BINARY SEARCHING TREES");
DO WRITELN(" GIVE THE NUMBER OF TREES:");
READ(N);
WRITELN(N);
IF N>0 THENEXIT ELSE WRITELN(" THE NUMBER MUST BE > 0") FI
OD;
WRITELN(" ELEMENTS OF THE TREES ARE INTEGERS");
WRITELN(" TO TERMINATE INSERTING ANY TREE TYPE -1.");
WRITELN(" THIS NUMBER IS NOT INSERTED AS AN ELEMENT");
ARRAY D DIM(1:N);
FOR I := 1 TO N
DO
WRITELN(" GIVE THE SEQUENCE OF NUMBERS ",
"FOR THE TREE NO.",I:4);
READ(J); WRITE(J);
IF J>M THEN M :=J FI ;
D(I) := NEW NODE;
D(I).VAL := J;
DO
READ(J);
IF J = -1 THEN WRITELN; EXIT FI;
WRITE(J);
IF J > M THEN M := J FI;
CALL D(I).INS(J)
OD;
OD I;
M := M+1;
WRITELN(" THE MERGED SEQUENCE IS:");
ARRAY TR DIM(1:N);
MIN := 0;
(* GENERATE THE TRAVERSERS SYSTEM *)
FOR I:= 1 TO N
DO
TR(I) := NEW TRAVERS (D(I));
ATTACH(TR(I));
OD;
K:=0;
(* HERE THE MERGING ALGORITHM BEGINS ITS WORK *)
DO
IF MIN = M THEN EXIT FI; (* ALL ELEMENTS WERE PRINTED exit*)
(* FIND THE SMALLEST ONE *)
MIN := TR(1).VAL;
J :=1;
FOR I:= 2 TO N
DO
IF MIN>TR(I).VAL THEN MIN:= TR(I).VAL; J := I FI;
OD;
IF MIN< M
THEN
WRITE(' ',MIN); (* PRINT IT *)
ATTACH(TR(J)); (* ATTACH THE J-TH COROUTINE, LET IT MOVE
AND FIND THE NEXT SMALLEST NUMBER IN TREE number J*)
K:=K+1;
IF K=10 THEN WRITELN FI
FI
OD;
WRITELN
END merge

Definition

By a dynamic chain of a coroutine we understand a sequence of objects and dynamic instances of other modules (e.g. records of activation of procedures)

X1, ... , Xk

such that X1 is a coroutine-object and for i<k the execution of Xi has caused the creation and execution of Xi+1.

An active coroutine-object is executed till a command attach or detach will be encountered. This explains that the creation of other objects or activation records does not change the active coroutine-object. Even an eventual initialisation of another coroutine-object is "booked" as an action of the active coroutine-object. The instances do really form a chain subordinated to the active coroutine-object.

There is as many coroutine systems, for a program, as many is created processes. The main program itself is a process. Every process is a coroutine too.

Hence, at least one coroutine system exists at any moment. It is the system of main program. Obviously it may limit itself to the one coroutine-object = the activation record of the Main block of program.

Let us recall that in any moment and for every coroutine system, exactly one coroutine-object is active.

We can conceive any configuration of the execution of a program as a collection of disjoint dynamic chains. For every coroutine system, exactly one dynamic chain is active.

The initial configuration contains only one instance, the activation record of the main program = coroutine-object main.

A coroutine-object which is in its initialisation phase does not form an independent dynamic chain, it belongs to the dynamic chain of the coroutine object which caused its creration, together with other instances created by the coroutine.

A command attach (detach respectively) activates the last element of a dynamic chain, i.e. the last created one.