Implementing a simulation tool in a high-level language with no multitasking facilities

Ways to implement coroutines in a block-structured language with no multitasking facilities are presented. Coroutines are implemented as procedures. The reactivation points are kept in global variables, one variable for each procedure. Local variables whose values are required on re-entry are stored as STATIC objects. The variables or data of re-entrant coroutines are stored in an event list associated with each such coroutine. A procedure with several entries is a convenient mechanism to trap the primitive calls issued by the coroutines. This procedure returns to the master program by using a non-local GOTO. The implementation of the above in PL/I and C is described and a comparison is made with sequential Pascal. Ada includes constructs which satisfy most requirements.     

Bidirectional coroutines

The bidirectional coroutine is introduced as a mechanism for overcoming a shortcoming in the method of specification of the transfer of control between coroutines. An analogy is drawn between subroutines and coroutines by observing that coroutines, like subroutines, should not have to know with whom they are interacting. At present, most coroutine implementations require specific mention of the coroutine being resumed, or use a suspend mechanism in which case one coroutine acts as a slave (the suspending one) and the other as a master. In the second case, the slave need not know the identity of its master while the master must know the identity of its slave. For bidirectional coroutines, a coroutine need not know the identity of its master nor its slave. This is achieved by replacing the suspend primitive with two new primitives — resume master and resume slave.     

Coroutine behaviour and implementation

Algorithms using retentive control are currently being developed in operating systems, simulation, artificial intelligence and language implementation. This paper investigates two aspects of a form of retentive control, namely coroutines. The behaviour of coroutines and language primitives that express the operations on coroutines are explored by surveying the literature for coroutine usage. Secondly, the area of control implementation of coroutines is investigated by considering the Bobrow and Wegbreit spaghetti stack as a viable data structure for managing run-time storage. Changes in the basic model of the spaghetti stack, tailoring its use in a strictly coroutine environment with subsequent implementation alternatives, are explored. An investigation through experimentation is made of the effect control-related aspects of coroutines have on the revised spaghetti stack models. An analysis of the empirical results obtained provides a useful barometer for selecting appropriate storage management schemes based on coroutine design and usage.     

Guarded and unguarded coroutines: An implementation in BCPL

This paper describes an implementation of coroutines in BCPL, and gives an example of the use of the coroutine mechanism in an experimental compiler for Algol 68.     

An application of coroutines and backtracking in interactive systems

A software structure well-suited for the programming of interactive recognition and translation systems is described. This structure makes use of coroutines and backtracking in a highly coordinated and integrated fashion. A set of coroutine and backtracking primitives that supports this approach is defined. An example of the use of this approach is given.     

Proving correctness of coroutines without history variables

We examine the question of whether history variables are necessary in formal proofs of correctness for coroutines. History variables are special variables, which are added to a program to facilitate its proof by recording the sequence of states reached by the program during a computation; after the proof has been completed the history variables may be deleted. The use of such variables in correctness proofs was first suggested by Clint [CL73] in a paper entitled Program Proving: Coroutines; subsequently, history variables have been used by Owicki [OW76a] and Howard [HO75] in verifying concurrent programs and by Apt [APT77] in verifying sequential programs. We argue that recording the entire history of a computation in a single set of variables can actually complicate a correctness proof and should be avoided if possible. We propose a modification of Clint's axiom system and a strategy for constructing proofs that eliminates the need for history variables in verifying simple coroutines. Examples (including Clint's program Histo) are given to illustrate this technique of verifying coroutines, and our axiom system is shown to be sound and relatively complete with respect to an operational semantics for coroutines. Finally, we discuss extensions of the coroutine concept for which history variables do appear to be needed; we also discuss the question of whether such variables are necessary in verifying concurrent programs.The preparation of this paper was supported by NSF Grant MCS-75-08146.     

A coroutine mechanism for BCPL

In recent years interest in coroutines has increased considerably and their usefulness is no longer in question. This paper describes a simple coroutine mechanism that fits neatly into the philosophy of the BCPL language. A few diverse applications of the mechanism are presented at the end.     

Extension of Pascal by coroutines and its application to quasi-parallel programming and simulation

This paper describes an extension of Pascal by coroutines as a basic tool to make quasi-parallel programming possible. This extension is acheived by predefined procedures, i.e. by semantical means without modification of the syntax of the language. Process and simulation concepts are developed entirely in the extended Pascal. These concepts are suited for quasi-parallel programming and for process-oriented simulation of discrete-event systems. The presented simulation system is easy to implement, it is flexible and modifiable. It retains the powerful facilities and the portability and availability of Pascal.     

A note on extension of Pascal by coroutines

In this communication, a simplification is suggested for the coroutine extension of Pascal described by Kriz and Sandmayr. In addition to being simpler to implement, it is also more user-friendly and secure because most of the strict sequence constraints on procedure invocations are lifted. The scheme uses the Pascal-P compiler, without modification except for the addition of a few built-in procedures, together with a macroassembler for Pcode preprocessing.     

NSEDIT: A syntax-directed editor and testing tool based on Nassi—Shneiderman charts

This paper describes a programming environment for Pascal, called NSEDIT, which runs under VAX/VMS

1 VAX/VMS is a trademark of the Digital Equipment Corporation.

. NSEDIT is based upon the notion of Nassi-Shneiderman charts (abbreviated to N-S charts in this paper) and is designed for ease of use by novice programmers in a teaching situation. A key component of the system is the editor, which enables structural features of Pascal to be manipulated in terms of their N-S chart box representations. Simultaneous editing of more than one program or module is permitted. Another key feature of the system is a semiautomatic interface to the VAX/VMS Pascal compiler, with subsequent display of execution counts as part of the N-S charts. In this way users can obtain immediate feedback on the coverage of program elements by test runs, while still inside an editing session.     

Experiences with coroutines in BCPL

This communication describes a typical application of BCPL coroutines in simplifying the implementation of a multi-event task, together with some problems encountered. The problems fall into two major groups: those associated with the routing of operating system messages to coroutines within a task, and those connected with data shared between coroutines. General solutions are suggested to these problems, which can occur in any program employing similar structures.     

Linear Continuation-Passing

Continuations can be used to explain a wide variety of control behaviours, including calling/returning (procedures), raising/handling (exceptions), labelled jumping (goto statements), process switching (coroutines), and backtracking. However, continuations are often manipulated in a highly stylised way, and we show that all of these, bar backtracking, in fact use their continuations linearly; this is formalised by taking a target language for CPS transforms that has both intuitionistic and linear function types.     

Program proving: Coroutines

Summary Proof methods adequate for a wide range of computer programs have been given in [1–6]. This paper develops a method suitable for programs which incorporate coroutines. The implementation of coroutines described follows closely that given in SIMULA [7, 8], a language in which such features may be used to great advantage. Proof rules for establishing the correctness of coroutines are given and the method is illustrated by the proof of a useful program for histogram compilation.     

A FORTRAN implementation of Concurrent Pascal

This paper describes the transportation of sequential and concurrent Pascal from the SOLO distribution tape to a non-PDP-11 like mainframe (IBM 370/145). An interpreter for the idealized virtual machine was written in FORTRAN. Subsequently the PDP-11 dependencies were removed from the interpreter and compilers so that a more transportable version of concurrent Pascal could be generated. A FORTRAN system was then constructed which simulated an operating system environment in which the interpreter could run. Clock and device interrupts are simulated so that process scheduling can be undertaken as if real interrupts were being generated. The system was constructed for a teaching environment so that several students could make use of the Polytechnic's interactive computer system each running their own concurrent system.     

Performance evaluation methodologies for abstract data type implementation techniques

The runtime management system for a programming language must allow the efficient manipulation of complex objects, such as instances of abstract data types (ADTs). We describe an implementation model for ADTs based on coroutine objects (i.e. as an alternative to ad hoc modifications of the runtime stack). We evaluate the performances of variants of our implementation model using two different approaches: a benchmarking technique which monitors actual costs for test programs and a “pseudo-execution” technique which estimates costs based on idealized instruction timings. The results of our comparison indicate that the two forms of evaluation give very similar cost estimates, supporting the use of the (cheaper) pseudo-execution technique. The overall performance results identify applications in which our coroutine implementation model has definite strengths and weaknesses. Finally, our implementation approach is compared with modified stack implementations used in other ADT systems.     

A heap-based implementation of the programming language Pascal

The implementation of Pascal known as Pascal ‘P’ was modified so that activation records for blocks (procedures and functions) were no longer allocated on a stack, but were instead allocated on a heap. This was done partly to test the feasibility of using Pascal ‘P’ for experimenting with extensions to Pascal, and partly to assess the efficiency of implementing Pascal procedures and functions in this way. The necessary changes to Pascal ‘P’ are described; where alternative strategies were possible, these are outlined and the reasons for the final choice given. The heap management algorithms used are presented and, in particular, their behaviour when managing the activation records of Pascal programs which do not involve dynamic variables is explained. Quantitative comparisons are made between Pascal ‘P’ and the version with heap-allocated activation records, to assess their relative efficiencies; these comparisons indicate that the modified system uses more storage, but it gives rise to only slightly longer execution times. Alternative heap management algorithms are discussed. Finally, some advantages of heap-allocated activation records are presented.     

Declarative diagnosis of missing answers

This paper investigates algorithms for declarative diagnosis of missing answers in Prolog programs, especially programs which use coroutines. The logic of the problem is first presented, in the form of the simplest possible debugger. Next, we compare several previously published declarative debuggers based on Shapiro’s work. Examples showing incompleteness, incorrectness and equivalence of debuggers are given. Several enhancements to these debuggers are presented which can reduce the number and complexity of questions asked of the oracle, while still supporting coroutines. Although no debugger considered is best in all cases, the new algorithms are a practical contribution. Finally, we discuss diagnosis algorithms based more on Pereira’s work. These algorithms ask easier questions than Shapiro’s algorithms but rely on the standard left to right computation rule. We discuss possible ways to adapt these algorithms to handle coroutining. Completeness of debuggers is also discussed.     

A low-cost implementation of coroutines for C

We identify a set of primitive operations supporting coroutines, and demonstrate their usefulness. We then address their implementation in C according to a set of criteria aimed at maintaining simplicity, and achieve a satisfactory compromise between it and effectiveness. Our package for the PDP-11 under UNIX? allows users of coroutines in C programs to gain access to the primitives via an included definitions file and an object library; no penalty is imposed upon non-coroutine users.     

The solo operating system: Job interface

This paper describes the interface between sequential Pascal programs and the Solo operating system.* A sequential program interacts with the operating system by means of procedure calls. A program prefix defining these procedures and their parameters enables the compiler to make complete type checking of calls to the operating system. The Solo interface permits Pascal programs to call one another recursively. This makes it possible to use Pascal as the job control language.