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++programPreviously, 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**programThe 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.
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**programFor 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.
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.
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.
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.
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**programFigure 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.
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.
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.
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.
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**programThis 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.
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.
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.