CHAPTER 14 - Side by Side

Coroutines

Masters and slaves or equal partners?

Even if you had never programmed before starting this book, the use of procedures should be becoming second nature to you by now. The ability to call on a handy sequence of instructions whenever it is needed is one of the most useful aids to programming offered by high level languages like SIMULA. Most people have a set of useful procedures which they like to use in just about all the programs they write. In fact most of us extend the SIMULA language with new features, many of which are procedures.

Although procedures are very useful, they are only one way of using independent pieces of code. The distinctive feature of procedures is that they are activated by being called from some point in the program and that when they have completed their instructions they return to that calling point. They are the slaves and the calling code is their master.

In the real world similar relationships exist. If we consider an office, the manager may need to write a report. To do this he will perhaps dictate it into a dictaphone and send the recording to the typing pool. For him the typing pool acts like a procedure. He passes it a recording of his report, like a parameter, and receives a typed version of it, like the result of that procedure.

If we broaden the scope of our view of the office, the manager may be one of several within his firm. He might be preparing his report as part of a monthly review process. This might involve all the managers preparing their own reports.

If we think of the managers as objects of class Manager, this preparing of reports would be the sequence of instructions within the class body of Manager. The facts on which the report is based would be given a parameters when the Manager is generated and the final report would be an externally visible attribute of Manager. Obviously specific managers might have extended definitions as subclasses of Manager.

Example 14.1 shows a pseudo-SIMULA program for this situation. Clearly this is not a program which could replace the managers in a real firm, but it does describe the operation of the firm. This is the use of SIMULA as a system description language. If you find this concept interesting, you should consult "SIMULA BEGIN" [Birtwistle et al, 2]. Here I am using it to show the limits of the concepts for producing independently acting components in our programs.

Example 14.1: A single manager making a report

begin

      ref(Document) procedure Typing_Pool(Draft);
                ref(Dictaphone_Recording) Draft;
      begin
         Typing_Pool :- new Document;
      end--of--Typing--Pool;

      class Document;
      begin
         comment Holds standard document for this company;
      end--of--Document;

      class Dictaphone_Recording;
      begin
         comment Holds dictaphone version of document;
      end--of--Dictaphone--Recording;

      class Manager;
      begin
         ref(Document) Report;
         Report :- Typing_Pool(new Dictaphone_Recording)
      end--of--Manager;

      new Manager;

   end++of++program
Previously, we have seen that our programs can describe service components, like the typing pool, as procedures. Now we can see that classes can be used to describe parallel components. These remain in existence once they have completed their actions, for as long as they are referenced. In this case we keep reference variables pointing at them. Thus the main program, which is the managing director or vice president, can read all the reports once they are complete.

If we include procedures as attributes of managers, the managing director can order his managers to do further things, but their independent actions cease once they have completed their reports. What is more they cannot interact. How, for instance, could we represent the situation where each manager wants to read all the other reports before allowing the managing director to read his? The ability to stop for a while and then start again, having allowed others to complete some task in the meantime, is vital to the way normal life is organised. It adds greatly to the power of a programming language, but very few allow it. It is one of SIMULA's great strengths that it does so; it is an even greater strength that it does so in a way that is simple to understand.

Example 14.2 shows the pseudo-SIMULA way of representing the situation where no manager makes his report available until all reports have been completed and revised in the light of reading the others. Notice that the managing director (main program) only starts the managers off, using Resume. All other interaction is between managers as equals. He can access their attributes once they have all terminated, however, as they are referenced by the elements of array Section_Head.

Example 14.2: Interacting managers writing reports.

begin

      integer C;
      Boolean array Ready(1:4);
      ref(Manager) array Section_Head(1:4);

      ref(Document) procedure Typing_Pool(Draft);
               ref(Dictaphone_Recording) Draft;
      begin
         Typing_Pool :- new Document
      end--of--Typing_Pool;

      class Document;
      begin
         comment Holds standard document for this company;
         procedure Read;;
      end--of--Document;

      class Dictaphone_Recording;
      begin
         comment Holds dictaphone recording of document;
      end--of--Dictaphone_Recording;

      class Manager(Id_No); integer Id_No;
      begin
         integer Count;
         Boolean Some_to_Read, Ready;
         Boolean array Report_Read(1:4);
         ref(Document) Report;

         Report_Read(Id_No) := True; ! No need to read his own;
         Report :- Typing_Pool(new Dictaphone_Recording);
         Ready := True;
         Detach;   ! Wait for others to be started;
         while Some_to_Read do
         begin
            Some_to_Read := False;
            for Count := 1 step 1 until 4 do
            begin
               if Section_Head(Count).Ready and (not Report_Read(Count)) then
               begin   !   Read this report for the first time;
                  Section_Head(Count).Report.Read;
                  Report_Read(Count) := True;
                  comment Update own report;
                  Report :- Typing_Pool(new Dictaphone_Recording);
               end..of..reading..another..report
               else Some_to_Read := True;
               Resume(Section_Head(Id_No+1)); ! Give the others a chance;
            end..of..one..pass..through..other..reports
         end..of..checking..other..reports
         All reports read so terminate
      end--of--Manager;

      for C := 1 step 1 until 4 do Section_Head(C) :- new Manager(C);
      Resume(Section_Head(1))
   end**of**program
The features used for synchronising these more or less parallel sequences are Detach and Resume. They are system procedures. Let us consider a simple example of their use in a real program.

A simple game example

Most of the examples used in this book have been aimed at practical problems, largely to do with text processing. The others have been artificial programs, merely designed to show a feature of SIMULA. Here in example 14.3, for a change, is a program designed for fun. It involves the game of noughts and crosses.

Example 14.3: Coroutines for noughts and crosses.

   begin

      character array Board(1:3,1:3);
      integer N,M;
      ref(Crosser) Cross_Player;
      ref(Noughter) Nought_Player;

      procedure Print_Board;
      begin
         integer N,M;
         for N := 1 step 1 until 3 do
         begin
            for M := 1 step 1 until 3 do OutChar(Board(N,M));
            OutImage
         end
      end++of++Print_Board;

      Boolean procedure Check_Board;
      begin
         comment Check for a winner;
         integer N;
         character Token;
         Boolean Check;
         for Token := 'O', 'X' do
         begin
            for N := 1 step 1 until 3 do
               if (Board(N,1)=Token and Board(N,2)=Token and Board(N,3)=Token) or
                  (Board(1,N)=Token and Board(2,N)=Token and Board(3,N)=Token) then
                  begin
                     Check := True;
                     go to Found
                  end;
            if (Board(1,1)=Token and Board(2,2)=Token and Board(3,3)=Token) or
               (Board(1,3)=Token and Board(2,2)=Token and Board(3,1)=Token) then
               begin
                  Check := True;
                  go to Found
               end
         end--of--Token--loop;
Found:
         if Check then
         begin
            OutText("Winner is ");
            OutChar(Token);
            OutImage;
            Check_Board := True
         end
      end++of++Check_Board;

      class Noughter;
      begin
         comment Reads in player's move and updates board;
         integer N,M;
         Detach;
         while not Check_Board do
         begin
            OutText("Give position for nought as: n,m.");
            OutImage;
            N := InInt;
            InChar;
            M := InInt;
            Board(N,M) := 'O';
            Print_Board;
            Resume(Cross_Player)
        end--of--loop
      end++of++Noughter;

      class Crosser;
      begin
         comment Plays for the machine;
         integer N,M;
         Detach;
         while not Check_Board do
         begin
            for N := 1 step 1 until 3 do
               for M := 1 step 1 until 3 do
                  if Board(N,M)=' ' then go to Found;
Found:
            Board(N,M) := 'X';
            Print_Board;
            Resume(Nought_Player)
         end--of--loop
      end++of++Crosser;

      for N := 1 step 1 until 3 do
         for M := 1 step 1 until 3 do Board(Count1,Count2) := ' ';
      Cross_Player :- new Crosser;
      Nought_Player :- new Noughter;
      Resume(Cross_Player)

   end**of**program
For those who are not familiar with it, noughts and crosses is a two player game, using a square sub-divided into nine equally sized squares. Each player in turn fills one of the boxes with his character, either a nought, 'O', or a cross 'X'. The first player to make a line of three of his characters, horizontally, vertically or diagonally but straight, wins.

The program contains two coroutines. One is used to read in the location where the person running the program wants to put his or her nought. This is typed in as two numbers, separated by a comma, giving the location in a two dimensional character array, which represents the game board.

The second coroutine represents the other "player". It selects its move according to a very simple set of rules, or algorithm. Basically, it scans each row from left to right, starting at the top. It places its cross in the first unoccupied location that it finds.

The procedures Print_Board and Check_Board are called by each coroutine after it has placed its character, to print the board and to check for a winner.

This may seem like a rather trivial program. It shows rather nicely, however, the operation of coroutines. They do not proceed genuinely in parallel. Instead, they take it in turns to become active. In this way they are exactly like many games, where each player has a turn and then waits idly until his turn comes again. Even the most complicated coroutine based programs are like this.

Not all coroutines take turns in strict order, of course. The next one to be made active might depend on some condition which changes each time. Even this is like some games, where the value of a card or a number called can change the direction or sequence of play.

Because of these characteristics, coroutine programs are often called quasi- parallel systems.

Procedure Detach

Detach is a procedure which is an attribute of all class objects. A call of Detach within a class body renders the class object "detached". It is meaningless to try to detach a block or procedure. This will either result in the object to which the block or procedure is local becoming detached or, if there is no object containing it, there will be no effect.

The state detached is a waiting state. A detached object may be used as a co-routine and resumed from outside.

When an object detaches itself, the program goes back to the point where that object was activated, i.e. immediately after the Detach, new or Resume statement in the object or block which initiated the current phase of activity in this object.

Procedure Resume

Resume is a procedure which has one parameter, which may be a reference to any class object. This breaks the normal rules for the type of a reference parameter. Resume is allowed to do this, but no user defined procedure may.

Resume restarts a detached object. The program moves to the statement following the last call of Detach or Resume which has been made by the object being resumed. If the Resume call is made from within an object, this object becomes detached. If the Resume comes in a block such as the program block, a subsequent call of Detach by the Resumed object will return activity to the next statement in that block.

If the object is not detached, trying to resume it is a runtime error.

Possible states

When an object is executing the body of code declared in its class declaration, including that of any prefixing classes, and has not executed a Detach, it is said to be "attached" to the point at which it was generated. If it is executing, an object which is not a coroutine can only be attached.

If an object executes a Detach, it forms a coroutine. It enters the "detached" state.

An object which has been resumed is in the "resumed" state.

An object which has just resumed another object is in the "detached" state, i.e. it can become active either by the object which it resumed detaching or by an explicit resume.

An object, whether a coroutine or an ordinary class object, which passes through its final end, becomes "terminated". Terminated objects continue to exist as long as they are referenced from somewhere else in the program. A terminated object with no references to it is regarded as having ceased to exist.

Exercise

14.1 Write a program which uses three coroutines - Read, Sort and Check - to read in names, add them to a linked list in correct alphabetical order and check that this has been done correctly.

Text processing with coroutines

An important reason for using coroutines is to keep information, which has been accumulated by one class object, alive when that object has completed one part of its sequence of actions and then resuming it when its next sequence is required, with its data intact. This can be made even more powerful by making the whole or part of the sequence of actions loop. In this way more and more information can be accumulated as the sequence is repeated.

An example of the use of this is in the automatic generation of an index. Each time a page is complete, the indexing process can be reactivated to scan it and note any words for indexing. If a procedure were to be used, all its local data would be lost after each call. This would mean that it would have to store its information in variables outside of itself. This would make it impossible to write a really self-contained indexing process. By using a coroutine, this is avoided. Instead of calling a procedure, the index coroutine is simply resumed. Once it is finished it detaches itself and waits to be resumed again.

A text processing system might have several parallel components. Example 14.4 shows the skeleton of such a system, using the sort of informal, half-SIMULA we have seen before. Diagram 14.1 shows the design of the system in general terms. There are two coroutines, Indexer and Command_Interpreter.

Example 14.4: Outline of a text processer using coroutines.

begin
      comment Outline text processer using detach/resume;

      comment General support procedures;

      text procedure InLine;
      begin
         InImage;
         InLine :- SysIn.Image.Strip
      end++of++InLine;

      procedure OutLine(T); text T;
      begin
         OutText(T);
         OutImage
      end++of++OutLine;

      comment Some list handling definitions;

      class Linker;
      begin
         comment Prefix for linked list handling;
         ref(Linker) Link;
         procedure Add_To(List); name List; ref(Linker) List;
         begin
            this Linker.Link :- List;
            List :- this Linker;   ! Requires List to be in name mode;
         end--of--Add_To;
      end++of++Linker;

      Linker class Word_List_Entry(Word); text Word;
      begin
         Add_To(Word_List)
      end++of++Word_List_Entry;

      Linker class Index_List_Entry(Word,Page_No);
               text Word; integer Page_No;
      begin
         comment Holds occurences of words to be indexed;
      end++of++Index_List_Entry;

      Linker class Chapter(Title); text Title;
      begin
         integer Chapter_No;
         ref(Page) Page_List Current_Page;
         procedure Print
         begin
            ref(Page) Next;
            Next :- Page_List;
            while Next=/=None do
            begin
               Next.Print;
               Next :- Next.Link
            end..of..while
         end--of--Print;
         Current_Chapter_No := Current_Chapter_No + 1;
         Chapter_No := Current_Chapter_No;
         Current_Chapter :- this Chapter;
         Add_To(Chapter_List)
      end++of++Chapter;

      Linker class Page;
      begin
         integer Page_No, Current_Line;
         text array Line(1:60);
         procedure Print;
         begin
            integer Count;
            for Count := 1 step 1 until Current_Line do OutLine(Line(Count))
         end..of..Print;
         Current_Page_No := Current_Page_No + 1;
         Page_No := Current_Page_No;
         Current_Chapter.Currrent_Page :- this Page;
         if Page_No=1 then
         begin
            Line(2) :- Current_Chapter.Title;
            Current_Line := 4
         end else Current_Line := 1;
         Add_To(Current_Chapter.Page_List)
      end++of++Page;

      ref(Chapter) Chapter_List;

      comment Principal coroutines and records;

      class Command_Interpreter;
      begin
         comment Read in commands and resume appropriate coroutine.
                 Implemented as a coroutine;

         text Command, Current_Line;

         while True do
         begin
            Current_Line :- InLine;
            Command :- Current_Line.Sub(1,2);
            Current_Line :- Current_Line(2,Current_Line.Length-2);

            if Command="$I" then
            begin
               new Word_List_Entry(Current_Line).Add_To(Index.Word_List)
            end else
            if Command="$I" then
            begin
               if Current_Chapter=/=None then Resume(Current_Chapter);
               new Chapter(Current_Line)
            end else
          ! if Command= etc. then
          ! begin
          ! Perform appropriate action
          ! end else;
            if Command="$E" then
            begin
               new Printer
            end==checking==command
         end..while
      end++of++Command_Interpreter;

      class Indexer;
      begin
         ref(Index_List_Entry) Index_List, Next;
         ref(Word_List_Entry) Word_List;
         procedure Print;
         begin
          ! Sort the index list;
          ! Print the index list;
         end--of--Print;
         while True do
         begin
            Detach;
            comment Resumed at the end of each page;
          ! For each line of Current_Page, search for each word on Word_List;
            if found then new Index_List_Entry(current word).Add_To(Index_List)
         end--of--loop
      end++of++Indexer;

      class Printer;
      begin
         ref(Chapter) Next;
         comment Print contents page;
         OutImage;
         OutText("Contents");
         OutImage;
         Eject(6);
         Next :- Chapter_List;
         while Next=/= None do
         begin
            OutInt(Next.Chapter_No,8);
            OutText("      ");
            OutText(Next.Title);
         end..printing..contents..page;
         comment Print chapters;
         Next :- Chapter_List;
         while Next=/=None do
         begin
            Next.Print;
            Next :- Next.Link
         end--of--printing--chapters
         comment Print index;
         Index.Print
      end++of++Printer;

      comment Main program;

      ref(Chapter) Current_Chapter;
      ref(Indexer) Index;
      integer Current_Chapter_No, Current_Page_No;

      Index :- new Indexer;
      new Command_Interpreter

   end**of**program
Figure 14.1: Coroutines for text processing.
      ---------------          ---------------
      I             I        ->I             I
      I             I       /  I             I
      I             I      /   I             I
      I   Command   I------    I    Indexer  I
      I Interpreter I<-        I             I
      I             I  \       I             I
      I             I   \      I             I
      I             I    ------I             I
      ---------------          ---------------
              \                      ^
               \                    /
                \                  /
        Writes   \                /   Reads
                  V              /
                  ----------------
                  I              I
                  I    Page      I
                  I              I
                  ----------------
The number of parallel components and the exact work performed by each is to some extent a question of choice. What seems an obvious design to some people, could seem odd to others. One useful rule is to build the system in a way that seems natural to you. If you think of certain sequences of actions as happening in parallel, reflect that in your programs.

Example 14.4 could have been written without coroutines. Our earlier chapter processing system did not use them, although it could have been written very simply as a set of parallel processes.

The key fact about this type of program is that none of the processes is the boss. Each has overall control whilst it is executing, but must wait to be resumed once it has detached. With procedures control passes down a chain of calls and back again to the original caller. With coroutines control can pass backwards and forwards as the situation dictates. All the coroutines can remain ready to be resumed, but none need be made active unless required. Even a terminated coroutine may still have its data accessed, as long as it is referenceable.

The indexer in detail

Like all the coroutines, the first thing that the Indexer object does is to perform any initial actions and then detach itself. This is a useful start, setting all the coroutines in place and ready to be used. The main program then schedules the first to be needed, in this case the Command_Interpreter, by calling Resume.

If we examine the Indexer coroutine in more detail we can see how it fits with Command_Interpreter. Essentially it is activated by calls of Resume from Command_Interpreter, each time a page of the book has been completed. It then scans the page just finished, looking for words on its wanted list. If it finds one, it creates a new entry on Index_List for that word. This list is a linked list of index/page reference objects whose header is a ref variable inside the body of class Indexer.

Once the whole page has been scanned, Indexer detaches. A detach takes the program back to the point where the coroutine was activated. The initial detach in Indexer took it back to the place in the main program where the Indexer object was generated. This detach takes it back to the resume in Command_Interpreter.

Indexer makes its second detach just before the end of its while loop. This means that every time it is resumed it goes straight to the top of this loop and repeats the sequence.

The loop is a while loop, but instead of a normal condition it contains the Boolean literal True. This means that the loop will continue for as long as the coroutine is resumed. This sort of indefinite loop allows "immortal" coroutines to be created. They will always be either active or waiting.

Indexer is a fairly simple coroutine. Since Detach and Resume are procedures they can be used wherever any statement can be used, although the effect will depend on whether or not they are called from within a class object, as explained above. During its complete sequence of actions, a coroutine can detach several times or resume any coroutines with which it is operating in parallel. It is important to understand the simple logic of Indexer before moving on to more complex problems.

Making a coroutine into a slave

This chapter only deals with coroutines in a very simple manner. There remains one basic feature of SIMULA which relates to them and which is not even superficially treated by the preceding sections.

It is possible to activate a detached object by using Resume, as we have seen. This makes an independent but passive object into an independent and active one. It does not attach the resumed object to the point from which it was resumed, except that it may choose to return there by calling Detach.

When an object is generated, we have seen that it is attached to the point where it was created. It is an extension of the block where it was generated, not an independent object, until it detaches or terminates.

A detached object may lose its independence and be reattached. This can be done by any block, not just the one where it was created. It is done by the procedure Call.

Once a detached object has been called it acts as if it had been generated at the point where it was called. It restarts from its last Detach and remains attached to the calling block.

Call takes one general class object reference parameter, just like Resume.

Restrictions on Call and Resume

The use of Call allows an object which was generated at one point in a program and which then detached itself, to be restarted later from another point, as does Resume. However, while Call is allowed for objects anywhere in the program, Resume is illegal for objects local to other class objects or to procedure bodies. Only objects which are defined by classes whose bodies are declared in sub-blocks or prefixed blocks can be resumed. We shall look in more detail at prefixed blocks in chapter sixteen and we have seen the use of sub-blocks. If an object Resumes itself this has no effect.

A Call can be made on objects whose class declarations are local to classes and procedures, as well as on those allowed for Resume. An object may not call itself without a runtime error being reported.

The use of both Call and Resume is illegal on objects which are not detached, including those which have terminated. It is also illegal on None.

The restriction on Resume is to prevent seriously ambiguous situations developing. The SIMULA Standard gives more technical detail.

Using Call

Example 14.5 shows an example using Call. Since the objects used are local to class Master, it would be illegal to Resume them. This means that they cannot interact as equals, but must be controlled by Master while active.

Example 14.5: Use of Call

   begin
         
      class Master;
      begin
      
         class Slave;
         begin
            OutText("Action before detach");
            OutImage;
            Detach;   ! Leaves Slave detached;
            OutText("Action when reattached by Call");
            OutImage
         end--of--Slave;
         
         ref(Slave) Servant;
         
         Servant :- new Slave;
         OutText("Action of Master when Slave detaches");
         OutImage;
         Call(Servant);
         OutText("Final action by Master when Slave has terminated");
         OutImage
      end++of++Master;
    
   end**of**program
This simple example should help to make clear how we use Call, even if the technical reasons for needing it as well as Resume go beyond the scope of this book.

Exercise

14.2 Improve the noughts and crosses program by adding a better set of rules for judging where the noughts should be placed. There is no definitive solution to this.

Some more on games

Noughts and crosses is a very simple game, but the basic principles used here can be applied to many other game playing programs. Even a chess playing program could be written on the same basis. The board would be more elaborate and the rules for deciding moves more involved, but that is all.

It is also possible to write programs to play multi-player games. A game of bridge, for instance, would involve four coroutines, with two phases - bidding and playing. If you enjoy bridge, this would be an interesting project to attempt. Chapter 20 will show you how to generate "random" numbers, to represent the dealing of the cards. One last possibility is to make all the coroutines internal and to let the program play itself. This is a way of testing alternative strategies.

Summary

We have covered coroutines and quasi-parallel systems rather informally.

We have seen the sequencing control procedures Detach and Resume and their use.

We have seen the possible states that a class object can be in.

We have seen the use of Call and something of the difference between Call and Resume.