Extendible Concurrent Control Structures for Smalltalk

A reactive system maintains ongoing interactions with the environment to affect the processes in the environment and the control system. Object orientation of a reactive system offers an intuitive design that employs life objects, which stem from state encapsulation and message passing interfaces, to represent the real world objects. A life object can take on an active role by encapsulating one or more processes. Ada and Modula programming languages include the language constructs and built-in mechanisms to define active objects. The notion of an active object is not well-defined in the Smalltalk programming language, because in this language a process is derived from a message chain that necessarily involves the fine-grained objects that compose the basic building blocks in the Smalltalk environment.

The BlockClosure class in Smalltalk language provides a versatile mechanism for developing extendible control structures, including the fundamental control structures for selection and repetition. The Smalltalk environment also incorporates an explicit mechanism for exception signaling and transfer of control to exception handlers, which are defined using the BlockClosure class. The context chain of a process defines the operational semantics for the exception signaling mechanism. Concurrency is introduced into the Smalltalk programming environment by simultaneous activation of processes, however, the environment lacks the high-level language constructs to define concurrency. Another deficiency of the environment is the lack of a prevailing mechanism to extend the exception signaling to concurrent processes. I propose a high-level programming construct for the Smalltalk language in which concurrent structures are reduced to algebraic expressions. The composite block closures, which are presented as the generalizations of the elementary BlockClosure in Smalltalk, can be defined using the extendible concurrent control structures I present. The execution models of the extendible control structures show that the exception signaling operational semantics can be unified with the high-level concurrency constructs.

Concurrency is an important construct, especially in reactive systems that, when embedded in the plant which they control, are concurrent components in the total system that comprises the controllers and the plant. The plant is made up of concurrently active physical objects. In an object-oriented architecture like the ControlWORKS,* the computing agents in the reactive system represent the real-world objects. Concurrency constructs tremendously enhance the expressive power of the language to model the simultaneity of the physical objects.

The Smalltalk programming environment provides a versatile mechanism based on the BlockClosure class to extend the language's control structures. Some basic control structures for selection and repetition have been adopted as the kernel language constructs. Concurrency can be also derived from the fork primitive in the BlockClosure class. The fork primitive and the extendibility of control structures offer a sufficient facility to develop high-level concurrency constructs. Despite this capability, a standard high-level concurrency construct has not been adopted for the Smalltalk language. Nor is there a prevailing work to unify the exception signaling with the concurrent structures. I now propose extendible concurrent control structures for Smalltalk whose salient features are their exception handling mechanisms. These new control structures are applied to the reactive control strategies in the ControlWORKS architecture.

Most modern programming languages include programming constructs that separate the concerns of the programmers to help them divide and conquer problems. One recent development is the separation of exception handling from a program's main flow. Inline coding of the exception handling can obscure a program's logic. By separating exception handling programmers can effectively express their intentions and assumptions about the normal conditions under which the control flows. The flow of control to handle the exceptions can be identified easily. By forcing separate flows of control after raising the exceptions, the programmers can be more vigilant in handling the exceptions that often escape detection in conventional languages.

Language constructs to handle exceptions appeared in ParcPlace Smalltalk1 shortly before 1988. The Smalltalk version uses signal objects to raise exceptions. When a raise message is sent to a signal object, the object searches the sender chain of the current process, starting from the current context, for occurrences of the Signal>>handle:do: for a matching signal. The flow of control is then transferred to the handle block as if the contexts between the block's and that where the signal was raised have disappeared. Only the unwind blocks nesting the exception occurrence are invoked when the flow of control unwinds the intervening contexts. If no matching Signal>>handle:do: is found after searching up to the head of the current process, the ParcPlace implementation does not propagate the exceptions to parent processes. Interprocess exception propagation is essential for coordination among a related set of processes. Sometimes an exception has to be propagated from one process to another process because it represents the distributed termination condition for the concurrent processes. Exception propagation is also needed if an application requires that exceptions be handled in a central or "trunk" process.

Peter Deutsch and Allan Schiffman proposed a tentative solution for interprocess exception propagation based on the interprocess interrupt primitive in ParcPlace Smalltalk.1 They introduced the notion of an effective context chain that extends the context chain of an inferior process with the context chain in the superior process leading up to the context where the inferior process is forked. The effective context chain defines the operational semantics for interprocess exception propagation. Most of the behavior of their interprocess exception propagation mechanism can be seen in the forkInferior method, which defines how the exception in a process is propagated outward from the context, in the superior process, represented by the variable thisContextOfParent:

(BlockClosure) forkInferior
	| parentProcess thisContextOfParent |
	parentProcess := Processor activeProcess.
	thisContextOfParent := thisContext.
	[ Object errorSignal
		handle: [ :ex | | sync result myProcess |
			sync := Semaphore new.
			myProcess := Processor activeProcess.
			parentProcess interruptWith: [
				[ result := self propagate: ex from: thisContextOfParent sender.
				sync signal ]
					valueOnUnwindDo: [ myProcess terminate ]].
			sync wait.
			ex proceedWith: result ]
		do: self ] fork.
This method provides a strategy to proceed or unwind from the point of exception in the inferior process. If the exception handler in the superior process performs an exception proceedWith: result operation, the result will be propagated back to the context in the inferior process that signaled the exception to allow the process to proceed. If the exception handler requests a return from the exception, the inferior process will be terminated at the same time the superior process unwinds from the intervening contexts. The following method:

(BlockClosure) propagate: anException from: aContext
	^Object errorSignal
		handle: [ :exc | exc propagateFrom: aContext ]
		do: [ Object errorSignal raiseRequestWith: anException parameter ]
introduces an exception object for propagation along the context chain in the superior process. A separate exception object must be introduced for the superior process to prevent the proceedWith: message from being sent more than one time to the exception object generated in the inferior process. This scheme requires that the context chain of the superior process has not unwound from thisContextOfParent sender context. Otherwise, the effective context chain is broken.

The interrupt message to the superior process can force the process to stop whatever it is doing to evaluate the interrupt block. Critical sections may have to be invoked from within the contexts of [criticalSection] valueUninterruptably to prevent undesirable effects. This may be an extreme measure, but without it there is a good chance that the interruption will cause the superior process to unwind after partial state changes, thereby leaving the objects in inconsistent states.

The preceding scheme introduces a general notion of the effective context chain involving superior and inferior processes. It does not offer a complete solution to avoid partial state changes, and requires additional constructs to ensure that thisContextOfParent sender remains active in the context chain.

I use lifelines to describe the execution models of the programming constructs proposed here. A lifeline outlines a trace of events in a dependency structure. In my example, an event corresponds to the activation of a context in a Smalltalk process. Unlike the context chain in a Smalltalk process, the lifeline includes activation events for contexts that are no longer in the context chain after the process unwinds from them. The lines in Figures 1–14 represent the lifelines of Smalltalk processes. A solid line represents a trace of events during the normal control flow. Dotted lines indicate the dependency of events during the creation of new processes. Dashed lines indicate the dependency of events for the control flows that involve exception signaling or process termination.

The exception propagation mechanism defined in the forkInferior method is depicted with lifelines in Figure 1. The events in the lifelines are labeled from 0 to 13 to illustrate the chronology. The scenario involves the parent and inferior processes, which are referred to, respectively, as parentProcess and myProcess, following the Smalltalk codes for forkInferior. The scenario starts at event 0. Event 1 represents the creation of myProcess using the forkInferior method. Event 2 represents the start of myProcess. The exception is raised by myProcess at event 3. The diagram shows three fictitious exception handlers along the context chain in myProcess that reject the exception one after another as indicated by events 4, 5, and 6. Since the application process cannot resolve the exception, the signal handler in forkInferior eventually captures the exception. The parent process is interrupted from this context.

The interrupted parent process propagates the exception from its context for event 1. The interrupt block is executed between events 8 and 9. Only the exception handlers among the contexts between events 0 and 1 can service the exception. Event 10 in the diagram represents a fictitious exception handler that also rejects the exception. The exception is finally serviced at event 11. This handler may request that myProcess either returns or resumes from the exception. The diagram describes the resumption scenario where the interrupt process signals a semaphore that allows myProcess to proceed with the result from exception handling event 11. myProcess proceeds at event 13, which follows event 12 in forkInferior.

This execution model for interprocess exception propagation illustrates a semantically veritable extension to the standard intraprocess exception propagation. The model is based on the principle that the effective context chain for exception propagation should include the context chain of myProcess and the context chain in the parent process that precedes the creation of myProcess. The solid gray lines in Figure 1 depict the effective context chain.

Concurrency constructs in a standard Smalltalk environment are provisioned at BlockClosure level, supported by a set of fork messages. Many new languages have been proposed to express concurrency at a higher level of abstraction by mathematically and semantically more appealing constructs based on algebraic expressions.2 Algebraic expressions containing parallel and sequential operators can be defined as generalizations of BlockClosure. An instance of generalized block closure, for example [A;[B||[C;D;E]||F]||G;H], is a composite structure composed from composite and elementary blocks using the sequential ";" and parallel "||" operators. Concurrency is derived from the subprocesses associated with the "||" operators.

A composite block in the generalized block closure is comprised of a group of parallel processes as denoted by or a concatenation of elementary or composite blocks as denoted by [S1; S2; . . . ;Sn] for sequential operation. In my execution models, composite blocks are referred to as composite control structures. An elementary control structure, which corresponds to a single block in Smalltalk, is referred to as an action. The process Si in the sequential control structure (SCS) can be an action or a composite control structure. Each process Pi in the parallel control structure (PCS) can be an action or a composite control structure. The control structures Si and Pi are said to appear, respectively, in the contexts of the composite control structures SCS and PCS.

Generalized block closure can be invoked by sending a value message to the block. To remain compatible with the operational semantics of usual BlockClosure, exceptions should be raised through the value message that the clients send to invoke the blocks. In this case the effective context chain of an elementary block includes the context chain of the block and the context chain leading up to the context in which the block is invoked. To provide the desired execution model of the concurrency constructs, we need a mechanism to perform the interprocess propagation of exceptions without the use of the interprocess interrupt primitive of Smalltalk. The new exception propagation mechanism should avoid the problem of partial state changes. In Deutsch and Schiffman's scheme,1 the exception propagation mechanism is built on the interprocess interrupt mechanism. In the new scheme the roles are reversed—the exception propagation mechanism is used to implement a more robust interrupt mechanism that does not entail partial state changes.

The semantics of concurrency constructs are simple, provided each of the components terminates normally. An exception propagation mechanism must support centralized exception handling and distributed process termination. I introduce a thread control mechanism comprised of a thread controller and several thread joints and threads. The information structure of this mechanism is depicted in Figure 15. A thread object represents a concurrent process. A thread joint associates the threads that join at the same point to facilitate dependency on the termination of processes. Each thread controller may simultaneously control more than one composite control structure. This mechanism extends the operational semantics of concurrent control structures by propagating exceptions from context chains in any subprocess, at any level of nesting, to the exterior context of the composite block. It turns out that interruption of the control structures can be defined as the propagation of exception signals from external agents into the control structures. It is a natural extension to the outward propagation of exceptions from the nested control structures.

In my execution models, the process that executes a control structure is referred to as a control thread, and is distinguishable from the application processes that are referred to as action threads. The lifelines in Figure 2 depict the execution model of the PCS [A1||A2||A3||A4], which is comprised of the elementary blocks A1, A2, A3, and A4. The control thread P forks off the action threads A1, A2, A3, and A4. It then waits at the thread joint for a semaphore signal, indicated at the point J in the lifelines. Each time a parallel process terminates, the corresponding thread joins the thread joint. The thread joint tallies the threads to signal the semaphore when the joint is done.

The lifelines depicting the execution model of an SCS are shown in Figure 3. The block expression for this SCS is [[A1||A2||A3]-->[A4||A5]]. In this execution model, each composite control structure uses a control thread to control the parallel or sequential components. For example, the S control thread sequentially creates and waits for P1 and P2 control threads whereas the P1 and P2 control threads control the two groups of parallel action threads according to the association P1::[A1||A2||A3] and P2::[A4||A5].

PCS and SCS are two of the regular control structures. Additional control structures can be defined to implement the irregular patterns needed for specific applications. Figure 4 depicts an irregular control structure that begins with the control thread consecutively creating four action threads A1, A3, A4, and A2. A1 and A2 join at J2 while the other two action threads, A3 and A4, join at J1. The control thread may perform an arbitrary amount of operations before waiting for joint. Then after creating two asynchronous actions B1 and B2, it waits for joint J2. The lifelines illustrate that the asynchronous action threads continue to run after the control thread terminates at J3. This scenario is equivalently defined by the composite control structure:


However, according to the execution models for PCS and SCS, the composite structure will utilize three additional P control threads and one additional S control thread as shown in Figure 5. The alternate symbol Bk denotes the elementary blocks that are executed asynchronously. Although the control thread does not depend on completion of the asynchronous actions, it may still be affected by exceptions in the asynchronous actions that are propagated to the exterior context.

The exception propagation in the control structures should be a veritable extension to the intraprocess exception propagation. The effective context chain for an action should only include the context chain along the action thread and the context chain leading up to the control thread of the root control structure. The context chains of the other actions are uncoupled from the effective context chain of an excepted action. This centralizes the exception handling to the process that enters the root control structure from the client. If the exception handlers in the action thread can resolve the exception, the exception need not be propagated to the client. I adopted operational semantics that treat the whole control structure as an integral unit such that restarting, returning, or proceeding from an exception, if done by the client, affects the whole control structure. The restart of an exception by the client process can result in restarting the execution of the control structure from the root context. The return from an exception causes the client process to unwind from the control structure's root context. Likewise, an exception proceed request from a client allows the control structure to run to completion. The latter case assumes that the action threads in other parts of the control structure have been running during the time the exception is being processed by the client. For the client to restart or unwind a composite control structure, all the action and control threads in the control structure must have been gracefully terminated. I introduce the notion of anti-actions in the execution model to facilitate early termination of the actions. Each of the actions is paired with an anti-action, which is executed as part of the exception recovery process.

The collective restarting or unwinding operational semantics of composite control structures have been used effectively to develop reactive control strategies for the Process Module Controller (PMC) where the concurrent actions in a control structure form a set of cooperating processes that must be running in sync. In this application, the excepted action should not proceed after being held up for an indeterminate amount of time while the other actions are progressing in phases. Furthermore, the other actions may have to terminate gracefully because one of the required actions has aborted. For example, the pressure control process should abort gracefully if the gas flow control process has aborted after failing to stabilize the gas's rate of injection.

Several exception reaction scenarios involving collective resumption or distributed termination are described in the following diagrams. Distributed termination involves anti-actions. In these scenarios, the anti-actions are invoked before the exceptions are propagated to the client. In other scenarios, the anti-actions may be invoked by the client after it decides to resume, restart, or return from the control structure.

The circular shaped icons in Figure 6 represent the application of transitive closure on the dependency relations between the incoming and outgoing arrows. These icons are used in the following figures to abstract out the lifelines that are not directly involved in the effective context chains for exception propagation.

The exception raised by the action thread A2 is propagated to the control thread at event 4. The control thread performs a depth-first traversal of the SCS to invoke the anti-actions at events 6 and 7. The anti-action of A3 is not invoked because A3 has not been invoked. The exception is propagated to the client process. The client process unwinds from the SCS and continues on a new path at event 11. Figure 8 depicts the resumption scenario for the same SCS. The SCS proceeds to invoke the pending action A3 following the response from the client. Where the SCS appears in the context of another composite control structure, a scenario involving anti-actions is depicted in Figure 9 and another scenario involving resumption is depicted in Figure 10. Figures 11 and 12 depict the exception propagation from the PCS. The exception propagation from the PCS that appears in the context of a composite control structure is described in Figures 13 and 14. In all cases the action thread A2 raises the exceptions.

A thread can be assigned a conjunctive or disjunctive attribute that prescribes the behavior of its thread join operation. These attributes are borrowed from the parallel prolog execution models.3 A thread joint that exclusively contains conjunctive threads requires termination of all threads before the join operation is complete. The termination of any disjunctive thread in a thread joint results in the completion of the join operation.

Conjunction is akin to the logical AND operator, whereas the disjunction is akin to the logical OR operator. This relationship is admissible from the development of a parallel logic execution model for the following conditional statement, denoted as a pseudo-Smalltalk expression:

[[A v B]^C] ifTrue: aBlock

The evaluations of the operands A, B, and C in the Boolean expression are performed in parallel processes. It is not hard to think of a scenario where these parallel processes are distributed to three computers to search and retrieve objects from distributed databases. While evaluating the logical OR operation [A / B] in parallel, one of the two parallel processes can return with a value ahead of the other. The value from the faster disjunctive process is sufficient to complete the evaluation without waiting for the value from the slower process. The expression then depends only on the value of the conjunctive process C. In the database retrieval scenario, the disjunctive parallelism allows the execution to proceed nondeterministically. The disjunctive threads can be used to implement a composite control structure based on Dijkstra's guarded commands with nondeterminism.4

In the above expression, bi is a Boolean valued guard and Si is a process. The guarded process can execute only if its guarding expression is evaluated to true. If multiple guards in the n-nary guarded commands are evaluated to true, the operator [ ] requires the implementation to nondeterministically select a process Si corresponding to one of the true guards for execution. If none of the guards are true, the command terminates. The guards can be executed as disjunctive threads in my model, in which case the process guarded by the guard that finishes first can be selected for execution. It is easy to extend my model to execute a guarded command repeatedly until each of the processes corresponding to a true guard is executed.

The information structure for the threads control mechanism is shown in Figure 15. The facade class in my multithreading mechanism is called threadsControl because it controls the application processes by attaching control behaviors to application processes to perform thread join and exception propagation. threadsControl contains a method to execute a block in a parallel thread. The thread joins a thread joint upon termination. Another method is used to control processes that may or may not terminate and therefore are not required to join other threads.

threadsControl contains two protocols to wait for thread joins. One wait protocol may propagate the exceptions from the exception queue. The second protocol does not propagate the exceptions. When a disjunctive thread joins a thread joint, the joint is done and consequently the waiting process is signaled. If the joining thread is conjunctive, it requires scanning the state of all the threads to determine the state of the joint. The joint is done only if all conjunctive threads are done. The following features are useful in many situations.

Quiescent state
When an exception is propagated to a waiting process, the process can unwind the messages by performing the exception return or restart operations. After recovery operations, the client may be required to wait until all activities in the threads are consummated. A query message is provided to test if all the threads have returned to quiescent state.

Exceptions are primarily propagated outward from the processes controlled by the thread control mechanism. External agents can also propagate exceptions into the controller. In fact, external agents can use exception propagation to interrupt concurrent structures.

Exception stubs
The exception is wrapped in the exception stub that inherits the behavior of the exception object by delegating the messages to it. The exception stub is time-stamped when it is added to the exception queue. The time stamp is used to retrieve the oldest exception.

Control epochs
The threads control mechanism records the time on the system clock when a thread is created. The mechanism also records the time when the control commences. A method is provided to recommence the control epoch. The exceptions generated by the threads created before the start of the control epoch are discarded.

Walk backs
Exceptions that are not handled in the application process are captured by one of the handlers in the root frame of the process. The mechanism may allow a walk back from the exception after it has been propagated into the exception queue. The walk back windows can be used to inspect the state of the processes. Walk backs may be inhibited.

When multiple control threads are simultaneously engaged in the wait messages to the threads controller, the exception is propagated to an arbitrary control thread. To maintain the centralized exception-handling pattern, only one control thread should be engaged in the wait-with-exception-propagation protocol. However, multiple control threads can be engaged in the wait-without-exception-propagation protocols. This anomaly is avoided in the control structure (described in the next section) that designates a root control thread for exception propagation.

Control structures were introduced earlier in this article as generalizations of the Smalltalk BlockClosure. They provide the programming constructs at higher levels than the threads control and exception propagation mechanisms described in previous sections, and support centralized exception-handling patterns. Control structures are defined using the Composite Design pattern from the Design Patterns.5 Composite Design lets the clients treat individual objects and compositions of objects uniformly. The class diagram for the composite control structures is given in Figure 16.

The abstract class ControlStructure defines a uniform interface for configurable actions and the parallel or sequential compositions of actions. The abstract class defines the execute protocol to invoke the control structure. If the root object is a composite control structure, it propagates the executeAsChild messages to its components. Thus each of the descendants of the root is executed as a child. The configurable actions define the same behavior for execute and executeAsChild. The differentiation is important only in the composite control structures where, to avoid the anomaly of the thread control mechanism, only the root control thread is engaged in the wait-with-exception-propagation protocol. All other descendant control threads use the wait-without-exception-propagation protocol. Exception signals are propagated only to the root control thread, which is part of the client process. This facilitates centralized exception handling in the client process.

When an exception occurs in an action in one part of the control structure, the other actions may have to be gracefully terminated. The provision for anti-actions may be used to develop the mechanism for graceful termination of processes. I have developed a rendezvous mechanism for the actions and anti-actions to interact. The recursive or iterative processes of the actions can be guarded by rendezvous to allow them to terminate gracefully. The control thread reverts to the exception-handling priority to perform a depth-first traversal of the control structure to invoke the anti-actions. All the anti-actions are executed in parallel processes that join at the same joint. The client can wait for the completion of the anti-actions by engaging in a wait.

ControlStructure also provides an interrupt method, which uses exception propagation to interrupt the root control thread. The interrupt message does not interrupt descendant control threads. Descendant control threads should be terminated when the client invokes the anti-actions to terminate the actions. The quiescent state of the control structure can be monitored to verify that all actions and anti-actions are terminated. The ControlStructure defines the controller: method as a subclass responsibility to implement a mechanism that fans out the threadsControl to all components in the control structure.

Composite control structures
CompositeControlStructure is also an abstract class. It contains an ordered collection of components, which can be arbitrary control structures. The order of the collection specifies the order of execution of the components. The actual order of execution of components in the parallel control structure is determined by their priority. The sequential control structure defines a control thread to invoke the subprocesses sequentially. Two types of parallel control structures are defined—for conjunctive or disjunctive processes.

Configurable actions
ConfigurableAction is an abstract class in which clients install BlockClosures for actions and anti-actions. Unlike the synchronous actions, the asynchronous actions do not wait for the action to join back.

The Smalltalk programming environment provides a versatile mechanism based on the BlockClosure to extend the language's control structures. The mechanism is sufficiently versatile for development of high-level concurrency constructs. Some language elements have been incorporated into Smalltalk for exception signaling, but Smalltalk lacks a prevailing work to unify exception signaling with concurrent structures. My work begins with an analysis of the interprocess exception propagation scheme first proposed by Deutsch and Schiffman.1 Several deficiencies of the scheme are uncovered.

The operational semantics of exception signaling among concurrent processes have to be developed. Deutsch and Schiffman's scheme provides a model for interprocess exception propagation based on the effective context chain that is a veritable extension of the context chain in a single process. The Smalltalk BlockClosure can be generalized to algebraic expressions by recursively defining the composite block closures using the parallel and sequential connectives. The composite block closure notation implies the effective context chains consistent with the centralized exception-handling pattern. The execution models of composite block closures are described pictorially by lifelines. The execution models of the generalized blocks are defined using composite control structures supported by the threads control mechanism. The threads control mechanism propagates the exception from any subprocess in the composite block closure to the exterior context that belongs to the client process.

Anti-actions are introduced in the control structures for development of distributed termination mechanisms. Distributed termination is prerequisite to restarting the composite control structure after an exception. The introduction of disjunctive and conjunctive attributes leads to some new control structures. After describing the desired execution models for the concurrent control structures, I describe the implementation of the threads control mechanism and the class diagram for composite control structures.


  1. Deutsch, P. and A. Schiffman. An unpublished report from ParcPlace, Inc., 1988.
  2. Hoare, C. A. R. Communicating Sequential Processes, Prentice–Hall International, Englewood Cliffs, NJ, 1985.
  3. Wise, M. J. Prolog Multiprocessors, Prentice–Hall International, Englewood Cliffs, NJ, 1986.
  4. Dijkstra, E. W. "Guarded Commands, Nondeterminacy, and Formal Derivation of Programs," Communications of ACM, 18(8): 453–457, 1975.
  5. Gamma, E. et al. Design Patterns: Elements of Reusable Object-Oriented Software, Addison–Wesley, Reading, MA, 1995.

* ControlWORKS is a trademark of the Adventa Control Technologies, Inc.

Unhandled exceptions are detected by external agents who are human operators. Use or abuse of the exception signaling to involve human intervention in recovering from algorithm bugs is generally discouraged.