This document was made by OCR from a scan of the technical report. It has not been edited or proofread and is not meant for human consumption, but only for search engines.

 

On the Transfer of Control between Contexts

 

B. W. Lampson, J. G. Mitchell and E. H. Satterthwalto Xerox Research Center

3180 Porter Drive

Palo Alto, CA 94304, USA

Abstract

We describe a single primitive mechanism for transferring control from one module to another, and show how this mechanism, together with suitable facilities for record handling and storage allocation, can be used to construct a variety of higher-level transfer disciplines. Procedure and function calls, coroutine linkages, non-local gotos, and signals can all be specified and Implemented in a compatible way. The conventions for storage allocation and • name binding associated with control transfers are also under the programmer's control. Two new control disciplines are defined: a generalization of coroutines, and a facility for handling errors and unusual conditions which arise during program execution. Examples are drawn from the Modular Programming Language; in which all of the facilities described are being Implemented.

1. Introduction

Transfers of control in programs can be divided into two classes. A local transfer stays within the same piece of program text, and does not change the naming environment. A goto which does not involve an exit

from a block has traditionally been the primitive local transfer operation, and other operations have been described by translating them into sequences of (possibly conditional) gotos and assignments. Recently there has' been a lot of effort to find a good set of higher-level local transfer operations, motivated by an awareness that the undisciplined use of the goto results in badly structured programs. The choice of if-then.-else, - for-while and case constructs, sometimes augmented by

loop and exit operations, has met with'wide acceptance. This is

not because of theoretical proofs- that they are sufficient to express any computation, but because many years of experimentation with the possibilities of the goto showed that it is most of fectively used in a few stylized

ways, from which these constructs were abstracted. In fact, the arguments for keeping goto available in programming languages are based on the observation that there are times when its use cannot readily be cast In one of these molds. •

A global transfer, on the other hand, does more than alter the .sequential


flow of control. It usually invokes a new piece of program text, and it always affects the allocation of storage and the binding of names. This paper is about global transfers. In fact, it is an attempt to find a suitable primitive (which we will call transfer) and to describe higher-level global transfers or‑

control disciplines by translating them Into sequences of

transfers, assignments and other data-handling operations.

There are two reasons why this seems worthwhile. First, it is difficult to describe clearly how the control disciplines in existing languages work without resorting to the construction of a formal interpreter [Fisher]. Non-interpretive descriptions either contain large quantities of ambiguous English prose, or they involve operations (such as the Algol 60 copy rule for procedure calls) which may be precise but are certainly not clear. if a language can be used to describe Itself, by defining certain operations in terrns. of sequences of simpler operations In the language, the amount of conceptual baggage required to understand It can be reduced considerably.

Second, It is our opinion that much remains to be learned about the proper choice of global transfer operations. Until recently very few languages other than assemblers gave the programmer any choice of control operations. Simula [Hoare and Dahl] and the new crop of languages for artificial Intelligence have changed this situation to some extent, but it will be a long time before the possibilities for global transfers have been thoroughly explored. If • programmers have the opportunity to create their own control disciplines they will certainly make a.lot of mistakes, but from this experimentation we can hope to learn what works well and what does not.

From this discussion the flavor of the paper should be clear. We will define a transfer primitive and then exploit the local expressive power of the language to describe some control disciplines which we happen to like. This

is not a trivial Job, since a 'good discipline must satisfy a number of constraints:

. programming generality [Dennis] - independently constructed modules can

work together without having to know each other's internal structure. In

particular, each module can choose its names and Its storage allocation

strategies independently of the others;

.   compatibility - modules using different disciplines can still communicate, or the advantages of diversity will be completely overwhelmed by the drawbacks of Babel;

.   robustness - it Is easy to get things set up, and restrictions and caveats are conspiclous by their absence;

.   reconfigurability - connections betweeen modules can easily.be broken and reestablished, so that debugging facilities can be spliced In and the behavior of a module can be changed by attaching "adaptors" to its external connections.

This approach should not be misinterpreted. The fact that a construct can be explicated in terms of simpler ones does not mean that the programmer must have this decomposition In mind whenever he uses it. On the contrary, if he uses it as part of his working vocabulary he will normally think of it as an atomic concept. The' explication Is helpful in making the definition precise, and in answering questions about what will happen in unfamiliar situations; It should be thought of In that light.

Questions about the binding of names are, in our view, orthogonal to the study


Un Lne iranSrer 01- %AMU-LH UtilWUU411 l,UIILt AL

of transfers, and are not considered in this paper. in particular, rules for binding non-local variables and for linking separately compiled modules are not discussed.

2. The _host language

The facilities- described in this paper are implemented in a general purpose system programming language called the Modular Programming Language (NIPL), which is a component of a system for modular programming. MPL borrows much of its local character from Pascal [Wirth] and EL/1 [Wegbreit]. In particular, it is a typed language in which new types can be built out of old ones using record, array and pointer declarations. There Is

also a way to prevent components of a record from being accessed except by a group of procedures which are declared with it. Such a record is called closed, and the procedures are called its handles. Finally, it is

possible to declare a record type s as a direct extension of another record type r, by adding additional components and handles. Extension is

the transitive closure of direct extension, and the set of all extensions of r is the class of r. Closed records and classes were inspired by the

class mechanism of Simula [Hoare and Dahl]; that language, howeveir, encourages the restriction of access to handles, but does not enforce it... The control transfer operations use closed records and classes to construct and manipulate their data structures.

·      A construct patterned of ter Pascal'S with is used heavily as syntactic sugar by the control disciplines. Any block can be prefixed by one or more clauses of the form:           . •

USING p,

where p is a pointer to a record of type r. Within the block the names of the components of r can then be used without qualification. If c is such a component, then within the block c is short for p.c.

3. Contexts and frames

The entities between which global transfers occur we call contexts.

The definition which follows reflects our views about the properties which such entities ought to have. Although nearly all of the transfer operations of existing programming languages can be described within this framework, we are not making any claims for its universal applicability: Since we make use of its properties in constructing control disciplines, our constructions will not work in systems for which contexts-cannot be defined.

Within this framework we may restate the subject matter of thls.paper:

.  the nature of contexts, and their creation and destruction;

.                minimal primitives which are sufficient to describe any transfer of control between contexts;

.                definition of good higher-level transfer disciplines;

.                description of these disciplines in terms of the primitives.

A context consists of:

.        a pointer to the text of a program, which we shall abstract as an array of objects called Instructions whose Internal structure and


properties are left undefined. We assume that the program is not modified during execution;

. a binding rule for names, which we shall abstract as a function mapping names into pointers;      

some local storage, including an integer index into the program text called the piogram counter.

3.1 Representation of contexts

A context Is represented by a frame, which is a record whose components contain the information needed to define the context. More precisely, a context base Is a closed record type containing a program text pointer, a binding rule and a program counter; these components are accessible only to the control transfer primitives, which are the handles.               A
context can almost be described as a member of the class of context bases,. Unfortunately, this description cannot quite be taken literally, because we need the transfer primitive to describe how procedures are called, and hence-this primitive cannot be defined as a procedure. The other operations on contexts, however, can properly be defined in this way.

It is interesting to compare this situation with what happens if we try to define as a class some other type which is normally taken as primitive. A 32 bit integer, for example, could be defined as a closed record containing a Boolean array with 32 elements, and we could (rather clumsily) write procedures to implement the standard arithmetic operations, without becoming involved in any circularity. As with any other closed record, these procedures must cooperate in maintaining the consistency of the representation: If add assumes that the integer is represented in 2's complement, then multiply had better not assume sign-magnitude representation. All the questions of consistency are

out in the open, however, since everything having to do with the closed record • is expressed in the declaration of its handles.

For contexts the consistency requirement has a new aspect. The procedure which creates a context, f or instance, must build a data structure which Is consistent not only with the other handles of the class context, but also with the transfer primitive. This Is actually a rather strong requirement,                                                                                                                                     
because the transfer primitive causes instructions to
be executed from the .program text. When this text was constructed, some assumptions were made (by the compiler) about the environment which would be present during execution of the program. The creation procedure is responsible for setting up the environment so that these assumptions are satisfied. If they are not, chaos will result, since the foundation will be undermined on which the entire

representation of the program is based.                                  If care is taken to satisfy the
assumptions of the transfer primitive, then, we may think of a context as a class, and the remaining discussion will proceed on that basis.

We will call a pointer to a context an lnport. The name is intended to suggest the main purpose of this type, which is to be an operand for the transfer primitive. A pointer to an inport we will call an outport,                        

with the idea that most of the control disciplines we are interested in need this extra level of indirection so that transfers into a context can be trapped when necessary.

3.2 Creation of contexts


We now proceed to explore In detail how contexts are created. Our discussion concentrates on the logical structure of the creation process, ignoring the details of the implementation, in which much of the work Is done at compile or link time, and many of the operations described are coalesced for ef ficienCy. We say a good deal about the treatment of the types of the various objects Involved in order to make it clear that everything we are doing is consistent with the constraints of a fully typed language.

Since a context is an instance of a class, there must be a single create primitive which takes some arguments and creates a context. The arguments to create are:

.   a record called a program which contains

- an, array of program text,

- the type of the frame- record which the program expects;

.   a frame record (which is not yet a context).

We will consider later where- these records come from.

With these inputs, create's Job is easy. It checks that the frame record actually presented is of the type specified by the program (using the facilities of the type system to find out what the frame's type Is). Then it inserts a pointer to the program text array In the frame, initializes the program counter to zero, and returns the frame record as a context.

A program must be derived eventually from a source file which has been compiled by the MPL compiler. The output of the compiler is an object file which contains the same information as the program record. There Is an operation called load which converts a file name Into a program record,

after checking as best it can that the file Is in fact a legitimate object file (the-type checking machinery cannot be expected to handle this situation perfectly, since It has no control over the-way In which Information Is stored In the file system). The only hard work filed has to do Is to find space for the program text array in the addressable memory of the machine on which the program Is running. How this is done depends on the details of the machine and is not relevant to this paper.

Constructing a' frame is more difficult. Again, we can break this operation down into two parts:

. obtaining storage for the frame;

.  initializing this storage properly and returning it as the frame.

Any record type in MPL has a creation operation associated with it which is defined when the type is declared. This operation accepts a block of storage and perhaps some other parameters,- and produces a record of the proper type. it is the only way to make such a record. The create primitive for . contexts discussed above Is an example of such an operation.

An ordinary frame creator In MPL is a special case of this general mechanism, with two distinctive characteristics. First, it usually has a standard program text, for two reasons:

.  frames tend to have a rather stylized form, so that the differences between them can be efficiently encoded Into a data structure called a, frame descriptor which can then be accepted as a parameter and Interpreted by the standard creator program.

.    there is another circularity problem - someone has to create the frame


creator. A standard creator can Itself be created in a standard way which can be part of the initial system.

The frame descriptor is usually stored In the object file along with the program text. Use of this scheme Is not compulsory, however. All of the facilities for creating records can be used to create frames.

The second unusual thing about a frame creator is that it has to provide the binding function for the context. Recall that this function maps the names used in the program text into pointers to the objects which are bound to those            '
names by this incarnation of the program. This is done by a generalization of . the
display which Is often used to implement the binding rules of Algol. The names used by the program have the form rp.v, where rp is a pointer to the frame of some other context and v is a variable local to'that context. We call the set of frames r, s, t, ... referenced by a context in this way the

neighborhood of the context; it Is defined by a collection rp, sp, tp,                           of
pointers to the frames. The context is automatically prefixed with a clause
of the f orrn

USING rp, sp, tp,                                .    

so that the program can refer to the variables without qualification, Just as it refers to non-local variables in Algol. One element of the neighborhood Is always the argument record.                         • -

To define the binding function, then, the creator has to define the neighborhood, i.e: set the pointers rp, sp, tp, ... to the proper frames. The type of each frame is of course fixed by the declarations in the source program, but there may several frames of the-same type to choose from.' As far as the typing and control mechanisms of the language are concerned, the creator Is free to choose any of them. One familiar possibility is the Algol rule, which takes the unique textually enclosing occurrence [Wang and Dahl]. In a more complex control environment, however, it may be difficult to define such a unique occurrence, or the programmer may want more flexibility In defining the environment. In any event, the choice of binding rule Is entirely under the programmer's control and Is not relevant to the subject of this paper.

3.3 Storage allocation

There remains the question of storage allocation for a frame.                          This must be
done with some care, since creating a context Is a rather common operation which Is required, for example, by every call of an Algol-like procedure. The standard solution Is to allocate frames from a stack; this works well in a control discipline which ensures that contexts are created and destroyed in last-in first-out fashion. Such a restriction would not be Incompatible with the basic control primitives, but it would-severely constrain the set of compatible higher-level disciplines which would be designed.

In order to avoid this problem, we have made a convention that frames are allocated on a heap; they can then be created and destroyed in any order. A standard non-compacting, coalescing free storage allocator [Knuth) is used, supplemented for speed by a vector of lists of available blocks for all the commonly used sizes. To keep the vector short, frame sizes are quantized by the complier so that they differ by about 10%. Thus the possible sizes might be 10, 12, 14, 16, 18, 20, 22, ..., 200, 220, etc. With this scheme only 40 sizes are required to span the range from 10 to 320, which is a much greater variation than Is likely to be encountered In practice. Furthermore, it Is


un the iransrer or control tretWeen Contexts

always possible to allocate a larger block than the one requested In order to reduce external fragmentation.

4. The transfer primitive

As-we have already seen, in order to handle transfers which change the environment we need at least one language feature orthogonal to that subset of the language,which is used for programs which run In a single environment.. This section describes a single primitive called transfer to meet this requirement.- We have tried to make this primitive do a minumum amount of work, leaving everything possible to be done by local code surrounding It In the two contexts which are involved in the transfer.

.       -

The basic transfer primitive, then, takes an Inport as its single argument.

Af ter it has been executed, the context which executed it is no longer running, and the context specified by the Inport has started running at the location specified by its program counter. In fact, this operation bears a striking similarity to the primitive used in Multics for switching control from one process to another [Seltzer], where the system scheduler, running within a • user process, picks another process to run and transfers to it. The difference is that in Multics there is no relationship between the processes except for that established by the implementation of the scheduler.

In our case, however, we almost always want to pass some kind of return link and some arguments to the new context. We do this by establishing the convention that the link should be put into a global variable called link, and the argument into another global called ergs, before the

transfer is executed. The context being entered must use the values of these variables, if it cares, before doing another transfer. Since this convention is followed In all our examples, the remainder of the paper uses a three-argument primitive

transfer(destination inport, return outport, argument pointer). - as an abbreviation for

deit := destination inport; link := return outport;

ergs := argument pointer; transfer;

In the implementation the global variables deal, link and ergs are of course machine registers.

For obvious reasons we make ergs a pointer to the argument•record.

From the point of view of the type machinery, this will be a "universal" pointer which carries Its type with it. When the receiving context tries to use it, a run-time type check is needed to ensure that it actually has the proper type. In most cases, however, this check can be done at binding time, as we shall see later.                                                                                                  . - '

Note that the transfer primitive says nothing about what is to be done

with the link or the arguments, and it does not create any contexts or allocate any storage. All of this is the responsibility of higher-level conventions or control disciplines, and the existing local features of the language, together with transfer, are sufficient to permit almost all of the transfer operations we know about to be programmed. An actual implementation, of course, may -favor certain disciplines by pre-defining them In a standard prologue and • generating especially good code for them, as ours does for the port, procedure and signal disciplines described below.


5. Conventions for compatible transfers

In defining control disciplines, we would like to have as much compatibility. as possible, so that it Is possible to leave a context using one discipline and enter a second context using a' different one. To make this work, we must be careful about storage allocation and about the rules for handling the arguments and return liriks. We have already discussed a suitably general method for allocating -frames. This section considers the other general problems encountered in designing a fairly broad set of compatible control disclpllr.es.

The transfer primitive allows for a single argument, which Is normally a

pointer to the record containing the arguments which the user wanted to pass. The semantics of binding a formal parameter, say x, to an actual parameter, say 14, Is very simple. The sender of the argument record assigns the actual parameter to a suitably named component of the argument record (actualargs.x := 14). When he has finished constructing the record and is ready to transfer, he does

ergs := actuaiargs; transfer(destination).

The receiver does -formalargs := args,

and (automatically) prefixes his block with the clause

USING formalargs,

where formalargs is declared to have the type of the argument record he expects.

The effect of all this is that:

.   the lowrlevel convention for passing arguments is very simple - one pointer is passed;

.   the entire collection of arguments is treated as a unit, so that it can be passed on unchanged by a context which IS simply doing monitoring or tracing and Is not interested' in the Internal structure of the arguments;

.   the receiver can reference the formals with the usual syntax;

.   the language facilities for constructing and decomposing records are automatically available for arguments. These allow, among other things

-    component values to be specified by name, by position or by default;

-    a record to be decomposed by assigning it to an extractor; a

·   syntactic construct which looks exactly like a record constructor except that all the components are treated as left-hand-sides of assignment operators;

-    variable-length records.

In this way a fairly elaborate set of facilities Is made to do double duty without any need to introduce new semantics Into the language.

To preserve generality, we must ensure that the storage occupied by the

. argument record will not be reused until the receiver Is through with it. It is undesirable to put this storage in the sender's frame, as is customary in Algol implementations, because the sender's frame may not live as long as the receiver (e.g. when the sender Is a returning procedure; this case can be handled specially in Algol because of the restrictions on what a function can return). We therefore allocate separate storage for the arguments, and require the receiver to free this storage when he Is done with it.

Copying the entire argument into the receiver's frame would be another


alternative, but is is unattractive for variable length argument records and In situations where a receiver is not interested in the values of the arguments, but Is simply going to pass them on to someone else. Copying does work well f or short argument records, however, especially since the record can.be constructed in the machine's registers, and this strategy Is used for records of -less than 6 words.            .

         6. Coroutines and ports                                                       -

.         

In this section we take up a pair of control disciplines which treat the two parties to a transfer as equals. In particular, this means that no creation of contexts or allocation of storage is Involved In a transfer, and that the relation between the parties is symmetric - each thinks that it is calling on the other one.

6.1 Coroutines

A coroutine (more or less as in Simula [Hoare and Dahl]; see also

[Mcilroy] and [Conway] ) is a context which, when entered, continues execution where it left off the last time it relinquished control. Local storage survives unchanged from exit to entry (as in a Fortran procedure, Interestingly enough). This is the simplest control discipline, and the easiest to describe. Each context Is pointed to by static inports set up at link time. Hence a transfer passes no return outport. The linkages are normally symmetric, as shown In figure 1.

There are three problems with coroutines of this kind as a general-purpose control discipline.           One is that, because of the fixed linkages, a coroutine
cannot be used to provide a service to more than one customer. A procedure, by contrast, is Ideally suited for this purpose, since it is created as a result of a call and destroyed when its work is done.

A second difficulty is that the control Is entirely anarchic. There is nothing to prevent control from entering a coroutine In an entirely unsymmetric way. For example, in figure 1 context 0 might gain control over inport a from line sl of P, even though its program counter Is at U. If subjected to an appropriate discipline this kind of control transfer might be useful, but no such discipline is present In the simple coroutine scheme.

6.2 initialization of coroutines

The third problem is proper initialization of a collection of coroutines. Recall that a transfer from context P to context Q does not change Q's program counter, but simply causes execution to resume at the point where it stopped, or at the beginning if Q has never run before. Since no buffering of ergs or link is provided by transfer, must save their values before doing another transfer. In general it will do this properlj, only If It is sitting immediately after a transfer to P. in figure 1, for example, If P is started first, it will transfer to Q at sl. but 0 will transfer to R and thus lose P's argument record.

This difficulty can be reduced by initializing more cautiously, as follows: (a) Start each context In turn by transfering to it, let It run up to Its


first transfer, and stop it before it sets up ergs and firth.

(b) Carefully choose one of the contexts and restart it by transferring to it.

Step (a) is unattractive because it requires a kind of control over the internal activities of the contexts which is quite different from what Is needed for normal transfers. Step (b) has more serious problems, which will become apparent on further examination.

Suppose in figure 1 that P is acting as a producer of data and Q as a consumer -who may occasionally return a reply. The fact that P and Q play different' roles Is concealed in the figure by the identical form of the skeletal program text. In figure 2 this difference has been brought out by expanding the argument handling associated with each transfer Into send and receive operations. The sequence of processing is:                                                                                                                             -

P:    setup - send                  transfer - receive - compute - send - transfer -

•••                 -            .

Q:     setup -                         transfer - receive - compute - send - transfer -

The two sequences: are identical except for the phase at initialization: in both cases there is a send - transfer - receive sequence which is the expansion of the simple transfer of ligure 1.

The differencein phase is quite Important, however, for step (b) of our cautious initializatioii procedure. If we choose P to restart, it will immediately transfer to 0, which will immediately transfer back, and Ws•first

message will be lodt. If, on the other hand, we choose Q to restart, all will be well. Unfortunately, It is hard to see how to make the proper choice in more complex situations (If indeed it is always possible).

6.3 Processes and messages as a model.

Rather than making further attempts to patch up the simple coroutine discipline, we now turn to a much more powerful scheme: processes executing In parallel and communicating via event channels. This, of course, Is more power than we need or want, but by extracting the essential functions of the parallelism and message buffering we can design a control discipline with understandable properties which preserves the strengths of coroutines while avoiding their - problems

 

The idea of processes executing in parallel we assume to be familiar [Dijkstra]. A message channel is an object on which two basic actions can be performed by a process: send a message and receive a message. A message is an arbitrary record, and_the channel can buffer an arbitrary number of messages. An attempt to receive a message from an empty channel causes the receiving process to wait until a message is sent to that channel. There Is no constraint on the number of processes which can send or receive messages on a given channel.                                      This facility is synthesized from two operating systems
[Lampson, Brinch Hansen]; we have suppressed many details which are Irrelevant to our purpose.

Any transfer operation can now be modeled by some combination of send and receive. We don't have to worry about losing messages, because of the buffering provided by the channels; each process will get around to processing Its messages In due course. Nor is the order in which

" -


processes run of any importance; in fact, it is not even defined, except when processes must wait for messages. We still need-a convention which allows one process to provide service for many customers, however. We get it by analogy with the link parameter of the transfer primitive: an event channel on which to return a reply goes along with each message.

6.4 Ports

The process-channel model has added three essential features to the coroutirie discipline:

.                  parallel execution;

·      buffering of messages;

.                  Indirect access to processes through message channels.

Figure 3 illustrates the structure of a symmetric connection. We now proceed to adapt these features to a sequential, unbuffered environment. The first step is to define a new type for symmetric transfer of control, called a port,-to replace the <channel, outport> pairs in figure 3 [Balzer, Krutar]. Each port is likewise a pair, consisting of an Inport IP and an outport OP. IP points to the context which will get control when a transfer is made through this port, and OP is where the return link will be stored.

We can avoid the need for parallel execution in a straightforward way, by modeling the notion of "a process waiting for a message on a channel" with the new concept of "a context being pending on an Inport". Since a process can only be waiting on one channel, we will insist that a context can only be pending on one inport. Now, if all transfers are to pending Inports, it will always be possible to run the context to which a transfer is directed, and there will be no need for parallel execution. A transfer which does not obey this rule will not be executed, but instead will cause a control fault, with consequences which we will explore shortly. .

Rather than explicitly associating the attribute "pending" with each inport, we can observe that an inport is a capability to start execution of a context, and interpret the pending rule as a requirement that only one non-null inport at a time should exist for each context. The inport components of all the other ports associated with a context Will be null, and a transfer to a null inport will cause a control fault. We thus complicate the semantics of transfer as little as possible.

Note that the pending rule has nothing to do with the transfer primitive, but is a convention which we introduce in order to construct a useful higher-level control discipline, that of ports. Even within this context, it may be proper to break the rule if It can be shown that no untoward consequences will result. Since the-rule is strictly internal to the port discipline, it stands or falls solely on the consistency of that discipline, and it is entirely Independent of the requirements of any other, separate convention for control transfers.                                        

We do, however, want it to be compatible with a procedure discipline;                        
fortunately, this causes no trouble.

A context gets- to be pending on an Inport In the same way that a process gets to be waiting for a message on a particular channel: by executing a receive operation on the port containing that inport. There Is a definite relationship between the value of the program counter and the pending Inport: the program is at the point where-it expects control to arrive over that port.


As a result, there is no need for message buffering in a successful port transfer, since the receiving context is ready and willing to pick up the message at once.

6.5 Control faults and message buffering

During normal execution a control fault indicates an error, an attempt to transfer control to a context which was not interested in receiving it In that way. During initialization, on the other hand, a control fault may simply be an Indication that there is another context to start. When a fault occurs, therefore, control Is passed to the owner of the faulting context; the owning context must decide whether another context should be started. The mechanism by which this is done Is described In section 9. Here we confine ourselves to the local consequences of the fault. The argument used above to show that no message buffering is required depended on the absence of control faults. When a fault does occur, what action should be taken to ensure that no messages are lost?

First of all, If no message is being sent (I.e. ergs is null) there is.no need f or buffering. For instance, when two contexts have a strict producer-consumer relationship, transfers from the consumer to the producer involve no message. This explains why no special action was needed during the simple coroutine initialization (discussed In section 6.2 above) when we chose to restart the consumer.

When a control fault occurs during a transfer from P to Gl (see figure 6). and ergs is not null, we actually have to do something. We would like

not to Introduce any new kinds of objects, and not to complicate any existing operations. Since our repertoire of objects and operations is limited, things look unpromising at first sight. Fortunately, however, we do have contexts at our disposal, and within a context we can embed any kind of special processing and storage we want, as long as it interfaces properly to the rest of the world.

In particular, what we can do is to construct a buffer context B with a standard program text, and local storage within which we keep the argument. We want B to emit the argument the next time control is transferred to P through the port a. To get this effect, we put an Inport for B Into a's Inport component, and save the inport for P which normally is there in B's local storage. When B gets control, it will restore P's inport, transmit the saved argument and destroy itself. It does this by executing:

a.lnport := savedinport; transfer(DC, B, (a, savedargument));

where DC Is a system-provided context which destroys B and then does: transfer(a.outport, address(a.innort), savedargument);

The cost of all this machination is quite moderate (which is not actually very important, since control faults take place only at Initialization if there are no errors), and it has the great advantage that normal transfers are not complicated at all by the requirements of control faults. Figure 6 illustrates the successive stages of Initialization for our familiar two-context example.

6.6 Linkage faults

We also want to be able to do dynamic linking, as in Multics [Bensoussan et. - al], so that we must be prepared to deal with a transfer through an


outport which has not yet been defined. Fortunately, the techniques we have developed can handle this situation without difficulty. Undefined outports are initialized to point to a standard context which constructs a buffer context, if necessary, to save the argument of the transfer which caused the linkage

Text Box:  f ault,.and then passes the fault on to the owner of the faulting context. If the. owner fills in the outport and transfers to it, everything will proceed exactly as for a control fault. Indeed, It Is quite possible that a control fault will then occur.

6.7 Railroad switching

As we have already pointed out In passing, the outport component of a port is used to hold the return link passed by transfer. Figure 6 makes the purpose of this arrangement clearer. If context Q transfers through port q which is Joined to context R through port r, then r.outport Is set to q. A subsequent transfer through r will then return control to Q. If later P transfers through p to r, then r.outport will be reset to p, so that control will subsequently return to P. This action, which resembles the action of a spring-loaded railroad switch, allows many-to-one connections of ports, and provide's the memory required to return control correctly. Switching is done by the receiving context, since it is part of the port control discipline and has nothing to do with the transfer primitive. Often It produces no change, • as for example In the transfers from R back to P or Q. To preserve compatibility with procedure returns (section 7.3) we make the convention' that a null link suppresses switching.

7. Procedures

Procedures have semantics much like that of Algol procedures. The implementation makes use of almost all the facilities which have been described in the preceding sections.

7.1 Procedure calls

If p is declared as a procedure, then p(a,b,...) is a procedure call, just as It

would be a port call if p had been declared as a port. There. are two                                                                                   -
differences:

Text Box:  a procedure p Is simply an outport; all procedure calls from a given context share a single inport In the frame, called the shared lnport. Since only one such call can be outstanding at a time (because of the pending rule), the pair (p, shared Inport) behaves exactly like a port. . . there is no switching done when control returns from a procedure call, because the call is regarded as a completed event, which may be repeated

. but cannot be resumed.                              .

Because of the way In which responsibility Is distributed during a transfer, these attributes of a procedure call are not visible to the

context which receives control, but are solely the local responsibility of the                                                                 (

Ob

context making the call.

7.2 Procedure entry

Whenever a procedure Is entered, a context P must be created..This Is done


by another context C called the creator, as discussed In section 3. Since the transfer which results in creation of a procedure context is not special in any way, the creator must also take care to start the newly created context and pass It the argument supplied by the transfer. Furthermore, C must leave itself ready to create additional contexts, since the procedure may be entered recursively. Thus there must be a unique inport for C, and the behavior of C must be constant with respect to all transfers through that inport. On the other hand, C is basically an artifact Introduced to obtain a uniform control interface, and there Is no reason for it to be Involved in the return of control from P.

The consequence of these design constraints Is that the transfer operation which suspends the creator Is used In a somewhat unconventiontli manner. The link that was received in C-when It was started is simply passed on

to P. The inport through which control arrived in C remains unchanged, and C loops right after the transfer to P, so that it will execute the same code the next time it gets control.

The following, somewhat simplified code describes the body of a typical procedure creator:

start: q            ALLOCATE(framesize);        _

q.pc := initialpc; q.neighborhood := accesslink;

q.sharedport := NIL; q.startport := q;

transfer(q.startport, link, ergs);

goto start                 

When the creator is created, the values of the local variables frameslze and initialpc are extracted from the text of 0, and accesslink Is set up based on the rules for defining the binding function.

This code is misleadingly long in.the sense that a clever implementation can achieve the effect It describes-with just a few machine Instructions, and it Is too short In the sense that the "ALLOCATE" operator conceals some additional complexity; It has been discussed In section 3.

7.3 Procedure return

A procedure context has an outport called returnport into which it puts link when it is entered.    A first stab at its return sequence would be:
transfer(returnport, NIL, returnargs);

but this won't do, because it ignores the fact that the context must be destroyed as part of the return. The caller cannot be expected to take care of this, since he doesn't necessarily know that he called a procedure. The actual return, then, Is more like the sequence-Used by a buffer context (section 8.5):

transfer(DP, self, (returnport, returnargs));

where DP is a standard context which destroys link and then does.

transfer(returnport, NIL, returnargs);                                                                               -
Note that this, like the procedure call described In section 7.1, is fully compatible and does not, f or example, depend on any assumptions about the • nature of the context pointed to by the returnport. Furthermore, an arbitrary. return record can be transmitted. The null
link suppresses railroad

switc ig if the call was made through a port (see section 8.7).

8. Signals


Finally, we take up a control discipline designed to handle.. exceptional events' ef ficiently and conveniently. The basic elements of this discipline are:

·    a set of names f or events, called signal codes (e.g. "out of storage", "overflow");   

·    for each context, an ordered set of outports called handlers;

.   a system_ procedure called the signaller whose argument s Is a pair (signal code, argument record).

Text Box:  8.1 Signalling

Anyone can signal the occurrence of an event by calling the signaller with the appropriate signal code as an argument, thus:

signal(OutOfStorage, spaceneeded);

The second argument may be an arbitrary. record which can be used to pass additional Information to the handler. 'There is also an optional third argument which specifies the•context in which the signal should be generated; usually this is the current context. An identifier declared as a signal code is treated by default like an identifier declared as a procedure: a search Is made, according to whatever binding rules are in force, for a definition which can be bound to the Identifier. The value of a signal code is simply an Integer, guaranteed tobe different for different codes. Its only purpose Is to "permit two signal codes to be compared for equality.

The signaller calls the first handler, passing it s. as an argument. If the handler returns to the signaller, Its result r is a pair (action, return record). If the action is reject, the signaller tries the next handler; If It Is

resume, the signaller returns the return record to its caller.

Usually each context supplies a handler, starting with the current context, and the handlers are ordered by a_pointer in each context called the signal port, which can be set by the=-user. The default choice of signal port for a procedure is the return link. Thus if all the contexts were Algol procedures, the effect would be to search up the stack, trying each procedure to see If it was interested In the signal.

Normally, handlers are declared in line with the program text of the context which will supply them, and there is convenient syntax for declaring a handler with each control transfer and with each block. If several handlers are -declared in a context, they are concatenated into a single one, using the same rule that the signaller uses. These declared handlers have the form of case statements which test the value of the signal code. By writing any as a case, however, the programmer can get hold of all the signals that go by and apply his own tests to them.

Thus, for example, one can write:

begin

enabling OutOf Storage: •

begin print("Storage exhausted"); exit computation end

•••

BulldTable(x. y

enabling OutOfStorage(spaceneeded: integer): if tablespace > 1000 then return


GetTableSpace(spaceneeded) else reject );

end

if the OutOf Storage signal is generated within the call of BuildTable, it will                                                               
first be given to the handler associated with the call of BuildTable, and then to the. handier for the block. The first (innermost) handler checks to see If more space is available. If so, it obtains the space and returns it to the context ' which did the signalling. If not, It rejects the signal, and It Is passed to the handler for the block, which prints an error message and does a (structured) non-local goto. The consequences of this last action are discussed later.

The handlers have the same semantics as ordinary procedures, differing only-In the syntax for declaring them. Furthermore, the programmer is free to provide his own handler f or a context; all he has to do is to put an outport into the component called handier in the context's frame. The handlers declared with enabling have some advantages, however. A great deal of trouble Is           .
taken to make the cost of declaring a handler small, since it is assumed that signals are unusual, so that most declarations will never be Invoked. In fact, entering the scope of a declared handler does not cause any instructions to be executed. Instead, the compiler generates some recognizable instructions which do nothing, and distributes them strategically In the program text where the signaller can find them.

When the signaller gets to a context which has no explicit handler, then, it examines the program text for in-line handlers. If one is found, Its associated program text is located from the clues left by the compiler, and it Is called in the usual way.

-This scheme for handling signaFs has a good deal In common with the ON-condition facilities of PI/1. There are also a number of differences, however:

a)    enabling a handier In MPL Is a declaration, not an executable statement;

b)    the program has much greater control of signal handling than In PI/1. in particular:

·  any and reject together .allow decisions about signal handling to be made in a very flexible way;

.             if this isn't good enough, the user can write his own handler, rather than use enabling;

c)    arguments can be passed with a. signal, and results can be returned, as in the example above;

d)    the zero time-cost for enabling chandler makes the facility very attractive to use. •

8.2 Unwinding .

Sometimes is is necessary to abandon a computation In mid-flight and restart from some earlier point. We call this operation unwinding. For example,

when an error is detected in a compiler, the current state becomes useless and we want to make a fresh start, perhaps with the input advanced to the next statement of the source program. In general when this happens there Is some • collection of contexts which are no longer useful and should be destroyed. To


deal with this situation, we need:

a)     a way of deciding which contexts should be destroyed;

b)   a procedure for destroying each context in an orderly way; c) some place to send control when the unwinding Is complete.

If there are a lot of contexts around which are not related hierarchically, It is not at all clear who should be destroyed during unwinding. We therefore provide a standard procedure which does the right thing for nested procedure calls, and leave It to the programmer to write his own unwinder for more complex situations, using the operations of the next two paragraphs. The standard procedure is

unwind(from context, to context, signal),

and it destroys all the contexts encountered in propagating the signal between the two contexts, not including the end points. It is normally used in a handler, thus:

unwind(myself, myparent, mysignal).

The parent is passed to the handler when it is entered, along with the signal and signal argument.

Destroying a context is a two-step process. First It must be given a chance to put its house in order, i.e. to restore to a consistent state any non-local data structures which it may have been modifying. This is done by passing the signal cleanup to Its handler. If the context wants to get control before being destroyed, it should enable this signal. When the handler returns, the context is destroyed, using the same facilities which would be used to destroy any other record. With the destroy operation In hand, we can write a skeletal program for unwind:

c := fromcontext;

- for c := NextSignalkandier(c, signal) while c # tocontext do

destroy(c).

Finally, we consider how to continue the computation, for the special case in which the context doing the unwind is an in-line handler of the one which Is to receive control. Since the handler knows about the program text of the destination in this case, it can simply set the destination's program counter to. the proper value, and then exit by destroying Itself, exactly like a buffer . context (section 6.5). The exit statement in the previous "OutOf Storage" example is syntactic sugar for:

unwind(myself, myparent, mysignal);

myparent.programcounter := ExitfromComputation;

transfer(DC, myself, (myparent, NIL) ).

The Muffles system [Organick] supports an unwind operation somewhat similar to what has Just been described.

9. Control faults

The discussion of control faults in section 6.6 left two questions open:

.  who gets notified when a control fault occurs?

.  how is the notice served?

The first question is handled like the similar problem for signals. Each context has an owner outport which defines who should be notified. By default this is set to the creator of the context, but .the user can establish any


relationships he likes by resetting it. •

When a control fault occurs, it is simply converted Into a signal called controlfault which is started of f at the context specified by the owner outport of the f aulter, and then propagates In the usual way. This makes it reasonably convenient for the owner to differentiate a fault from a normal exit. During startup, when control faults are expected, each handler will probably. specify an exit to the next statement.

10. Conclusion

We have created an environment f or describing global control disciplines, consisting of contexts within which execution takes place, and a                                                                                                                                      
transfer primitive for passing control from one context to another.

Records and classes were used to create contexts and to handle arguments. We showed how to define the binding function for names In a fairly general way, and described a strategy which allocates storage for contexts. We established conventions for passing arguments and return links which can accomodate a wide variety of control disciplines in a compatible way.

Ports were Introduced as a non-hierarchical control discipline, and we saw how to Initialize a collection of contexts connected by ports, how to handle linkage faults, and how to switch port connections so that several contexts can use a single port. We showed how to handle Algol-like procedures without any new primitives, and compatibly with ports.

Finally, we introduced signals as a control discipline for dealing with

unusual events, described how to give the programmer complete control over signal propagation and how to:4mplement signal handlers efficiently, and used the signal mechanism to provide for orderly retreat from untenable situations.

References

Balzer, R. M., "PORTS - A Method f or Dynamic Interprogram Communication and Job Control," Proc AFIPS Conf. 39 (1971 SJCC)

Bensoussan, A. et. al, "The Multics Virtual Memory: Concepts and Design," Comm ACM 15, 5 (May 1972)        -

Bobrow, D. G. and Wegbreit, B., "A Model and Stack Implementation of Multiple Environments," Comm. ACM 16, 10 (Oct 1973)

Brinch Hansen, P., "The Nucleus of a Multiprogramming Systeni," Comm. ACM 13, 4 (April 1970)

Conway, M. E., "Design of a Separable Transition-diagram Compiler," Comm. ACM 6, 7 (July 1963)


Dennis, J'. B., "Programming Generality, Parallelism and Computer Architecture," Proc. IF/P Congress 1968, North-Holland Publishing Co., Amsterdam, 1969

Text Box:  Dijkstra, E. W., "Cooperating Sequential Processes," in Programming Languages, Genuys, ed., Academic Press, New York, l967

Fisher, D. A., Control Structures for Programming Languages, Ph.D. Thesis, Carnegie-Mellon University, May 1970 (AD 708611)

Hoare, C. A. R. and Dahl, 0-J., "Hierarchical Program Structures," In Structured Programming, Academic Press, New York, 1972

Knuth, D., Fundamental Algorithms, Addison Wesley, Reading, Mass., 1968, p. 425

Krutar, R. A., "Conversational Systems Programming," In SIgplen Notices 6, 12 (Dec 1971)

Lampson, B. W., "On Reliable and Extendable Operating Systems," In The Fourth Generation, tnfotech, Maidenhead, Berks., 1971

Mcllroy, M. D., "Coroutines: Semantics in Search of a Syntax," Bell Telephone Laboratories, Murray Hill, N.J., unpublished report

Organick, E. 1., The Multics System: An Examination of Its Structure, MIT

Press, Cambridge, Mass., 1972

Seltzer, J. H., Traffic Control In a Multiplexed Computer System, Sc.D. Thesis, MIT, 1966 (MAC TR-30)

Wang, A. and Dahl, 0-J.., "CoreCitine Sequencing In a Block Structured Environment," BIT 11 (1971), p 426

Wegbreit, B., "The Treatment of Data Types In ELM," Comm. ACM 17, 4 (April 1974)

Wirth, N., "The Programming Language Pascal," Acta Informatica 1, 1 (1971)


 

P: context

 

 

Q: context

 

pc:     si

1--1>775-ET-Za

 

 

program text:

 

program text:

start:

 

a:         inport

 

inport

 

 

:start

 

 

 

 

 

V

 

 

 

 

14--

sl:

transfer(a)

 

 

 

 

Ir-4n1

transfer(c)

:t1

 

 

 

 

 

: inport

 

 

 

5           :

transfer(a)

 

 

 

R                     14-

 

transfer(b)

:t2

 

 

 

 

 

 

 

 

.                                                                                                                        .

.                                                                                                                                                                            .

Figure 1: Coroutine linkages

 

 


 

 

 

 
start:

P (producer)

start:

Q (consumer)

 

 

loop:

send message

transfer

receive reply

loop:

transfer

receive message

 

.      .

goto loop

 

·   -

send reply.

goto loop



Text Box: 	 	
•		
 		

P: process                                                                                                                Q: process

Text Box:  Text Box: •Text Box: •Text Box: other outportSText Box: - other outportsText Box: b: outportText Box: ac: channel- A	bc: channelText Box: •..        .

-                                                                          .                  •.   .    ..      _     • .                   7-:-

-. Figure 3: Symmetric communication between processes_using message channels -

                                                                                        -                                                       -    -

- •                                                                                                                                               -        -

.     -   •.-                .     ,

Text Box:  Text Box: P: context	 	Q: context

Text Box:  Text Box: : portText Box: b: port
a : outportF I Q: inport 
Text Box: : outportText Box: P: inportText Box: other outportsText Box: other-outportsText Box: •Figure 4: Symmetric communication between contexts using ports

i;!1


Text Box:  Text Box: •Text Box: •Text Box: p: portText Box: q: portText Box: Q: -contextText Box: 'P: contextText Box: p: port  HIL 
I	NIL	.1
Text Box: -	.
(a) Before P has attempted to use p
Text Box: (c) Q has been created and started, and q has been connected to pText Box: (d),Q has transferred through q and p to B, which is runningText Box: (e) B has destroyed itself and returned to 17; / Initialization is complete	•Text Box: Figur§ e 5: Initialization using a buffer conte§ xt to handle control faultiText Box: P: context