by Brad Cox
The Stepstone Corporation
75 Glen Road
Sandy Hook, CT 06482
203 426 1875

TaskMaster, Objective-C, ICpak, and Software-IC are trademarks of The Stepstone Corporation.


Table of Contents (toc)


Introduction (toc)

TaskMaster supports one of several layers in a multilevel object-oriented architecture that Stepstone has been building in a bottom-up fashion since its inception. This document will describe the kinds of user-programmable systems that we envision, a multilevel software architecture for building them, the role that TaskMaster plays within this architecture, and how TaskMaster relates to adjoining layers, such as C and the platform's operating system.

TaskMaster is a library of C-based functionality that supports lightweight multi-tasking and exception handling such that client applications are portable across hardware/software platforms. By portable, we mean that client applications access TaskMaster's features through an application program interface (API) that is platform-independent. This API is supported by a layer of platform dependent code (PDL) that adapts the API to the host hardware and software (operating system). For platforms that already support some of TaskMaster's capabilities (Mach, OS/2), the PDL uses the platform's capabilities. For platforms that lack these features (Unix, MS/DOS), the PDL provides them by directly manipulating the hardware (machine registers) that underlies the C run-time environment. For Sun Unix platforms, which is presently the only platform to which TaskMaster has been ported, the PDL is written in C with one small (8 statement) subroutine in assembler.

Customer inquiries are welcome regarding TaskMaster, either on its present Sun platform or ported to additional platforms. Contact K.K. Tan at 203 426 1875.

User-programmable Systems (toc)

The companion papers, Planning the Software Industrial Revolution and There is a Silver Bullet[2] describe the longer-range vision behind this work. They view the software crisis as an obstacle to moving from the Age of Manufacturing to the Age of Information, where computers become everyman's personal vehicle into a global information network, the Model T Ford of the Information Age. They see the software crisis as being solved as the telephone operator shortage was once solved, by making every computer user a `programmer'.

Of course, programmer will not mean what it does today. The word will acquire many different meanings appropriate to the skills and interests of diverse classes of users at different levels of a multilevel software architecture. For example, Tom, Dick, and Harry are typical `programmers' with entirely different skills and interests:

Tom is a programmer in the C++ sense of this word. Tom plays the role that silicon fabrication companies play in hardware, fabricating gate- and block-level silicon components into chip-level components that others with less specialized skills, such as Dick, can use. Gate- and block-level technologies, whether in hardware or software, are tightly-coupled activities in which optimization of the product, not their developer, is paramount.

Dick is an programmer in the Smalltalk or Objective-C sense of the word. Dick plays the role that board vendors play in hardware, assembling chip-level components that Tom produces into card-level components that others with even less specialized skills, such as Harry, can use. Chip-level technologies, whether in hardware or software, are loosely-coupled activities in which developer concerns such as pluggability, interchangeability, and reusability are paramount. Chip-level technologies support that crucial demarcation between tightly coupled fabrication technologies that only highly-skilled specialists use, such as silicon foundries, and the much simpler, loosely-coupled assembly technologies that non-specialists can use, such as screwdrivers and soldering irons.

Harry is an end user, one of `the rest of us'. Harry is a problem-domain expert with no specialized software expertise at all. The goal of the architecture to be discussed in this paper is to make Harry a `card-level programmer' in precisely that limited but nonetheless very real sense that end-users are card-level hardware designers when they choose which cards they'll buy to customize a personal computer.

Harry might be a clerk in an insurance office, a manager of a bank branch office, or in the following example, a homeowner using a personal computer to manage household finances. Today, Harry might be using an off-the-shelf personal finance program like ManagingYourMoney (MYM) on the Macintosh. Such programs let Harry manage his assets, liabilities, income, and expenses to provide an instantaneous reading of net personal worth. What today's programs and systems do not do is to help this class of users build their own custom solutions to their problem-specific needs. The Macintosh does not support end-user programming.

For example, suppose that some of Harry's assets are in stocks, bonds and mutual funds, whose contribution to net worth varies daily. When Harry tires of typing stock prices from the newspaper he might venture into the Information Age by programming his terminal emulator to acquire price information from an information service like Compuserve electronically. Although Harry unlikely to ever program in C or even Smalltalk, he might well reach the point of using a spreadsheet such as Excel to manage a database of price trends over time, perhaps using Excel's charting facilities to show trends graphically.

Today's non-programmable solutions are adequate only so long as Harry remains persuaded that all this mousing around[3] to open and close documents, start and stop applications, and cut and paste numbers is a major improvement over typing each number manually If Harry should insist on a way to build his own application to compute, with a single click, a graph of his personal net worth as it changes over time, his desires have exceeded what the Macintosh in particular, and the software industry as a whole, can deliver today.

The solution envisioned in this document is shown in Figure 1.


Figure 1: A program as might be created by an end-user, written in an iconic non-procedural card-level object-oriented `programming language' of the type envisioned in this document.

This figure is composed of Macintosh icons and screen dumps to imply that each icon behaves individually much as on the Macintosh today. However there are significant differences. The picture is not a collection of what-you-see-is-all-you-get icons that can only be used manually, and (except for manual cut and paste) individually. The figure is the `source listing' of a `program' that Harry has `written' in an iconic card-level `object-oriented programming language', whose `objects' are based on the lightweight multi-tasking facilities of this paper.

The icons represent lightweight tasks, or card-level objects. Harry might save his `Compute Net Worth' program as an new card-level component and use it alongside those shown here. However Harry didn't build the ones shown in this figure. He purchased them elsewhere, from Dick, who assembled them from chip-level components fabricated by Tom.

The tasks are initially inactive, each awaiting input on the incoming arrows. When the `Compute Net Worth' button (on another screen not shown here) is clicked, this produces the signal that the terminal emulator icon is waiting for. This triggers the task that the terminal emulator icon controls, which might be a card-level incarnation of a program like SmartComII, to dial the telephone, log into Compuserve, and type commands to download financial information.

The three string search icons are Harry's way of dealing with the fact that Compuserve does not provide financial information in a format that his spreadsheet can accept. He used a stream splitter process (the small black circle) to send the data to three string search processes, and has programmed these to find specific stock prices and format them as the three history spreadsheets expect. And so forth...

Unix programmers will recognize this as a variation on the pipes and filters scheme of Unix. But there is one big difference that my use of familiar Macintosh programs does not bring out clearly. Unlike Unix pipes that can only carry streams of bytes, the arrows in this figure can carry streams of chip-level objects. Unlike Macintosh spreadsheets that only accept text, the programs in this figure are written to accept data expressed as objects.

Objects can represent any structured data-type, including pointer-based structures like lists and trees. The arrow representing the input stream to the spread sheet icon need not be tab-delimited strings that the spreadsheet must parse and reformat internally. The arrow to the spreadsheet object could carry a stream of objects, instances of class Record, not a tab-delimited character stream as spreadsheets require today.

Multilevel Software Architecture (toc)

This document will use that fashionable but poorly understood buzzword, `object', with precisely the looseness of meaning this word has in hardware. That is, object will carry no technical meaning whatsoever, unless qualified to make the architectural context clear. Just as a gate-level hardware object has nothing in common with a chip-, card-, or rack-level hardware object, so it will be with the diverse software `objects' in the multilevel software architecture.

The architecture was motivated by appreciation for the multilevel architectures of hardware engineering, where high-level hardware objects such as office equipment are built from lower-level objects such as cards, card-level objects from lower-level objects such as silicon chips, and chip-level objects from lower-level objects such as silicon blocks and gates. It expects that the solution to the software crisis will evolve as it did in hardware, by stratifying users/programmers according to skill levels and interests, just as the plumbing supply market is stratified into homeowner, plumbers, retail outlets, factories, refineries, and mines.

End users, such as Harry, will use simplified modularity/binding technologies sufficient for limited categories of problems, such as the card-level objects described here. They will acquire the needed objects by subcontracting the work to more specialized lower level workers such as Tom and Dick.

Figure 2 shows the five levels of this architecture. Although the `objects' at every level meet the classic definition of objects as inseparable units of state and behavior, the modularity/binding mechanisms by which this is accomplished is totally diverse at the different levels:

The figure shows that C++, unlike Ada, provides limited support for chip-level programming in its virtual function mechanism, a form of dynamic binding. C++'s support for loose coupling is limited by its emphasis on tight-coupling, inheritance-based compile-time type-checking and static binding.


Figure 2: Object-oriented means different things at different levels of integration. Pie slices represent the extent to which several popular languages support work at each level.

Just as in hardware, what distinguishes chip-level modularity from gate- or block-level modularity is loose coupling, dynamic binding, or pluggability. Whereas gate and block-level technologies are fabrication technologies; ways of fabricating things from first principles, chip- and higher-level technologies are assembly technologies; ways of assembling things by plugging together off-the-shelf components from libraries of ready to use parts.

None of these levels are panaceas that eliminate the need for other levels. On the scale of any significant system, gate-, block-, and even chip-level objects are extremely small units of granularity--grains of sand where bricks are needed. But the rack-level modularity of operating systems like Macintosh and Unix go too far in the opposite direction. The rigorous encapsulation that makes rack-level modularity so useful for packaging software packages as independent programs, obstructs the free interchange of information between these objects so rigorously that end-user programming is not possible. Card-level modularity provides a middle ground, intermediate between the tightly encapsulated rack-level objects of operating systems like Unix and the chip-level objects of programming languages like Smalltalk.

Example: Fabrik and Smalltalk (toc)

The relationship between Fabrik[4] and Smalltalk is an excellent example of how card-level objects relate to lower-level objects. Fabrik was written in Smalltalk, so it consists internally of chip-level objects. Smalltalk programmers manipulate them via the Smalltalk programming language; a textual object-oriented user interface appropriate to software specialists like Dick.

Fabrik projects a higher-level kind of object onto the user interface; a `card-level' object. Non-programmers manipulate these via Fabrik's iconic user interface, which is a non-textual programming language suited to non-specialists like Harry. From Harry's perspective, these new objects are intuitively appealing for they are amenable to the reasoning skills of everyday life. They communicate, not synchronously through procedural invocation (something that only programmers find natural), but by an asynchronous model that is more closely related to how the familiar objects of everyday experience behave.

Card-level objects encapsulate a copy of the machine's thread of control on a software card, alongside the chip-level objects used to build that card. They are objects of the sort that programmers call lightweight processes; objects that operate as coroutines of one another, not subroutines. They communicate asynchronously by sending chip-level objects through communication channel objects such as streams.

Since software cards appear to run concurrently, their user interface is uniquely intuitive. For this reason alone, they are more fundamentally object-oriented than the procedural, single-threaded languages of today. Like the tangible objects of everyday experience, card-level objects provide their own thread of control internally, they don't communicate by procedural invocation, they don't support inheritance, and their user interface is iconic, not textual.

Card-level objects are similar to Unix pipes and filters They share the same non-procedural notion of concurrent processes communicating through asynchronous communication channel objects, or pipes. They differ in that card-level objects are lightweight processes. They share a common address space and are therefore not restricted to communicating value streams, or bytes. The streams between them can be reference streams that may contain embedded pointers such as linked lists or trees. Whereas pipes only carry bytes, streams can carry objects.

Example: Metaphor (toc)

Metaphor[5] is an related example with significant differences. Fabrik and Metaphor are similar in that both support an iconic programming language oriented towards non-programmers. Both are based on a non-procedural bubbles and arrows programming paradigm like the Unix pipes and filters paradigm. Both differ from Unix in that the bubbles can exchange reference streams (pointer-based structures) such as objects, rather than only value-streams as with Unix pipes.

The significant difference is the absence of the open architecture that Fabrik acquires from being based on an open standard like Smalltalk.

I understand that internal coding standards do exist whereby Metaphor's card-level objects communicate by a tabular representation oriented towards spreadsheet data. I understand that Metaphor now views this representation as an obstacle to continued growth, presumably because difficulty of forcing non-tabular data that occasionally recurs in customer applications to fit within Metaphor's tabular data model. I understand that relieving this and other barriers, such as non-portability, is the motivation for the recent Metaphor/IBM joint venture; Patriot Partners.

The multi-layered approach advocated in this document addresses the problems that Metaphor encountered by trying to represent all lower-level data structures with a single closed standard representation for tabular data. A chip-level object-oriented programming language like Objective-C provides an open-ended standard for representing structured data. They allow programmers to develop new data representations by defining new classes of objects, using object-oriented features like encapsulation, inheritance and polymorphism. The languages are supported by state of the art programming tools like browsers and by comprehensive libraries of trust-worthy, ready-to-use, pre-tested classes. Since chip-level objects are, by definition, loosely-coupled, pluggable, polymorphic and dynamically type-checked, newly-created objects can be immediately recognized and processed by pre-existing applications without having to recompile or otherwise modify the applications.

Example: TaskMaster and Objective-C (toc)

Stepstone's experience with Objective-C is a final example of why a multilevel software architecture is desirable. Whereas Metaphor's experience shows that skilled programmers need lower-level architectural standards than Metaphor's card-level objects, Stepstone's experience shows that users need higher-level kinds of objects than the textual, synchronous objects of Objective-C; objects that communicate by sending each other messages where the receiver computes as a subroutine of the sender, rather than as a coroutine.

The key concepts that distinguish higher-level user-programmable systems from the specialized programming languages of today, of which Objective-C is a typical example, are an iconic user interfaces (instead of a textual programming language) and concurrent (asynchronous, non-procedural) objects that operate as coroutines of one another, not subroutines.

Stepstone has not taken, and is unlikely to take, the final step of building user-programmable systems ourselves. We see our role as the provider of horizontal components that customers will use to build vertical end-user solutions.

  • ICpak 101 is a library of foundation classes that tend to be used in almost every application. The most widely used resident of this library is the Object class, which as the root class of most inheritance hierarchies, supplies functionality to all other classes, such as the storeOn:/readFrom: mechanism for automatically converting objects (reference streams) into a character representation (value stream) for storage or transmission over networks or pipes. This library also provides commonly-useful data structure classes like Sets, Dictionaries, Arrays, Lists, and Strings. This library is not sold separately, but is bundled with the compiler.

  • ICpak 201 is a far larger library of classes for building iconic user interfaces in a platform-independent manner. Its portability is also due to a distinct API/PDL interface. On many platforms, ICpak 201's PDL is based on X-Windows, but this PDL can be, and has been, based on other graphics libraries, including bare graphics hardware.

  • TaskMaster is a library of classes for building asynchronous card-level objects that operate as coroutines of one another, not subroutines.

    These libraries are based on Objective-C, which Stepstone also markets as the enabling loosely-coupled chip-level binding technology for providing large class libraries that are sufficiently loosely-coupled to their environment that they can be used in diverse customer applications. Objective-C is a hybrid object-oriented programming language that supports the Smalltalk chip-level object model as a strictly upwards-compatible extension to the gate- and block-level objects of a conventional programming language like C or C++:

  • Users of Stepstone's Objective-C compiler, which is based on ANSI C, express gate- and block-level operations in C. A version based on C++ is planned, but is not presently available.

  • Users of NeXT's Objective-C compiler, which is based on GNU C++, express gate- and block-level operations in either C or C++.

    Stepstone does not view itself as a language vendor, even though one of our most popular products is a compiler for the Objective-C programming language. We view ourselves as a software components vendor, with the language as enabling technology for gluing components together. We do not see Objective-C as `competing' with other popular programming languages, whether they be C, Ada, Smalltalk, C++, or the Unix shell. Objective-C is an extension to C. Insofar as C++ is a better C, it is a better platform than C for building a better Objective-C.

    TaskMaster Technical Description (toc)

    So much for the destination. The rest of this document is a tour of a vehicle for going there, from stateroom to boiler-room. It will show how user programmable card-level systems can be assembled from chip-level software components of Objective-C, and these from the gate- and block-level technologies of C or C++. Since the presentation will be progressively narrower and more technical from here on, those uninterested in boiler-room matters may wish to refer the more technical portions to a specialist.

    TaskMaster's goal is to provide a lightweight multi-tasking object model with low enough overhead that programmers will not be reluctant to use it as extensively as they use subroutine calls and messages today. Since lightweight tasks share the same address space, they can freely exchange structured pointer-intensive data, such as Objective-C objects.

    One sign of this low-overhead philosophy is that most of TaskMaster's facilities are accessible through a pair of API's. In addition to a message-passing interface resulting from TaskMaster's implementation as an Objective-C class library, each class's methods are also packaged so that they can also be called as ordinary C subroutines, thus allowing ordinary C programs to invoke TaskMaster's full functionality in the absence of Objective-C. In other words, TaskMaster is not specific to Objective-C, and can be used by ordinary C programs. However, for clarity in what follows, I shall describe TaskMaster in terms of its Objective-C API.

    Lightweight Tasks and Context Switching (toc)

    Ordinary C (and Objective-C) programs' external assumptions about their execution environment are quite simple. A program finds itself loaded into a computer domain (an address space), divided into four arenas; code, data, stack and heap. The code arena holds the program's code, the data arena holds the program's static data, and the stack and heap arenas are initially empty. The machine's program counter (PC) points to the program's starting address in the code arena and its stack pointer (SP) points to the stack, which is initially empty except for command-line arguments (argc, argv, and the like). Additional registers are usually involved as well, but so long as they are saved and restored correctly during task switching, it will be useful to ignore them.

    This initial situation is shown in Figure 3. A domain(perhaps one of several on a time-sharing system) is shown adjacent to two others. The domain object is pre-initialized for use as code, data, and heap arenas. These not drawn as separate regions since they are best regarded as subdivided among the objects drawn as small squares. The initial stack is the rounded rectangle at the bottom. The machine's registers are shown at the bottom, initialized so that the PC points to the first instruction and the SP points to the first slot of the (empty) stack arena.

    When TaskMaster is linked into such a program, it is automatically invoked at start up time via Objective-C's class initialization mechanism. The initialization allocates several TaskMaster objects to formalize the situation as objects. It creates an instance of Domain, theDomain, to model the address space as a whole, and an instance of Task, rootTask, to formalize the root task represented by the initial register settings.

    The initialization also initializes several global and static variables for its subsequent use, the primary ones being a currentTask variable, initialized to rootTask, and readyQueue, initialized to empty (since no other tasks exist yet).

    Additional tasks are created when rootTask requests it through any of a variety of ways, differing only in syntactic convenience. What follows will be presented in terms of a uniform syntactic mechanism, Actions, which are modeled after Smalltalk's Block mechanism. The Action mechanism will be, but is not yet, supported by the Objective-C compiler. Until it is described later, think of actions as a more powerful, easier to use and understand, replacement for many of the things function pointers are used for in C.

    The simplest way to create additional tasks (remember, other ways are also provided, including invoking the task creation logic by ordinary C function calls) is to send a fork message to an instance of Action. Actions incorporate a C function that plays the role that main(argc, argv) played for the domain as a whole:

    aTask = [anAction fork];

    The message returns a new instance of Task. This involves allocating a stack arena[7] for the new task from the heap initialized such that, when the task is executed for the first time, the action's initial C subroutine will find its arguments in the normal fashion for any C subroutine.

    The newly created task is automatically linked onto the readyQueue for eventual execution. The rootTask might create several such tasks, sending messages and calling functions as it does so, thus modifying the stack space of rootTask. Figure 4 shows rootTask's situation at an arbitrary point in its computation, three levels deep into a subroutine call or message send:

    Since TaskMaster does not provide preemptive scheduling, rootTask will remain in control until it performs some action that will put it to sleep and let one of the queued tasks proceed. Normally, a task does not do this by explicitly invoking the low-level primitives to be described here. It does so implicitly, by invoking a lightweight I/O operation on one of the I/O channel mechanisms described in the next section.

    The highest-level kernel entry that a user might access directly is the Semaphore class. Semaphores are a queue on which tasks can to wait for a resource and a count of available resources[8]. Suppose that some task does a lightweight read operation (anObject = [aStream get]) on a communication channel, such as a stream, whose internal buffer is initially empty. Streams use semaphores to monitor the status of this buffer, so the emptySemaphore's resource count variable will indicate that currentTask must wait for another task to add something to the buffer. Therefore, the semaphore will delay the task by linking it onto the semaphore's queue of waiting tasks and call taskScheduler to put the current task to sleep and start another one running. The task scheduler chooses the topmost task in the readyQueue[9] as nextTask, and calls the context switching routine as follows:

    contextSwitch(&currentTask->registers, &nextTask->registers, nextTask);

    This is where the magic happens. Whereas it was currentTask that called this function, a different task is running when it returns. This new task has its very own execution history (stack area) exactly as it was when the task was last put to sleep by contextSwitch.

    The magic is quite simple. A lightweight task is simply the machine's execution state along with the call history that produced that state. Both are represented by the machine's SP register. Calling a subroutine pushes these registers into the address in the SP register, and returning restores them from the address in the same register. The contextSwitch routine accomplishes its magic by saving the current task's execution state, the SP register, in currentTask->registers and loads another task's SP from nextTask->registers[10], where the new task was saved when it was put to sleep. New tasks are handled the same way; by initializing the stack arena and the task's register save area such that contextSwitch will start the task as if its entry subroutine had been called via an ordinary subroutine call.

    The size of a task's stack arena is established when the task is created, either with a reasonable default size or a size specified by the programmer. This arena cannot be enlarged thereafter because of deep-seated assumptions in C's run-time model that are beyond TaskMaster's control. If a task uses more than this amount, perhaps because of unforeseen recursion, the results would be unpredictable. Since providing a more robust subroutine-call mechanism in C is not practical, TaskMaster takes a less drastic approach. It initializes each stack arena with a block of guard information, which taskScheduler checks before every context switch to detect whether the task that has just finished running has overrun its allocation.

    Lightweight I/O (across tasks) (toc)

    The previous section showed how TaskMaster supports semaphores within an vanilla C environment, without depending on platform facilities whose absence would lead to non-portability. Semaphores are an extremely low-level scheduling primitive, too powerful for non-specialists in the same way that assembly language is too powerful. Although TaskMaster does provide semaphores, they should be regarded as a low-level mechanism for experts to use in building higher-level mechanisms that are not already available off-the-shelf.

    TaskMaster applications are concurrent applications (in the restricted sense of the previous section). Concurrently active tasks must be careful to synchronize the tasks' access to shared data so that race conditions do not occur. The computer literature is full of ways for doing this, ranging from extremely low-level and general mechanisms like semaphores and event counts at the one extreme, to intermediate-level mechanisms like the Ada rendezvous mechanism at the other, to the ultra-high-level but ultra restrictive pipes and filters mechanism of Unix.

    The synchronization mechanisms that are most highly developed in TaskMaster today are oriented toward supporting the higher-level of object-oriented granularity that was described earlier as card-level integration; libraries of loosely-coupled, iconic, concurrent modules that non-programmers can plug together (at runtime, not compile time) to create custom applications. The higher-level task mechanisms to be described next follow the Unix pipes and filters model, modified to assume lightweight tasks (card-level modules) that communicate by sending chip-level objects through lightweight communication channels such as streams[11].

    This philosophy departs from other workers in this field. For example, Grady Booch's library of Ada components takes a different approach, in which every reusable object (say, a Collection class), must allow for the fact that it may be accessed concurrently by multiple tasks. In practice, this means that every collection class must exist in multiple versions, one with guard logic to support concurrent access and others that do not for non-shared applications.

    Card-level objects reflect a different philosophy. Just as hardware cards do not share chips, software card-level objects (tasks) do not share chip-level objects such as collections. Rather, they communicate through specialized communication channel objects such as Streams; a software analog for hardware busses between cards. Of course, hardware analogies are seldom perfect in software. As we shall see, the `signals' that these software `buses' carry are the same kind of chip-level objects that comprise the cards themselves. Whereas Booch would speak of two tasks `sharing' a common object, we view them as each `owning' the object at different times, passing it through a communication channel object that provides whatever sharing paradigm is needed.

    Streams are the simplest sharing paradigm of all; `I own it unless I give it to you'. Since the stream sharing paradigm is simple to explain and to use, we expect that it will be the prevalent, but never the only, synchronization mechanism in user-programmable systems[12]. For example, Harry's program (Figure 1) is built entirely of task instances (icons) connected by stream instances (arrows). The large icons are tasks programmed to operate on objects flowing through streams and the small black dots represent generalized stream operations such as fork and join.

    Each of the tasks in such a system are programmed in a similar fashion, as a loop that reads objects from an incoming stream, processes them, and emits objects on an outgoing stream. For example, here is how a task might be coded in ordinary Objective-C, without using Action expressions:

    static void task1Fn( struct { Stream *inStream, *outStream; } *s )

    {

    while (not done) {

    inObject = [s->inStream get];

    ...process inObject; compute outObject...

    [outStream put:s->outObject];

    }

    }

    The two streams in this example, inStream and outStream, may have been preallocated by the rootTask and passed to this task as formal parameters as argc and argv are passed to Unix programs. It is also possible to pass such information in global variables (all tasks share the same global address space), or to create them within the task itself. The following larger example creates three tasks that communicate via two streams[13], using action expressions to avoid the syntactic clutter that would result had this been written using functions and function pointers:

    main(int argc, char **argv, char** envp)

    {

    Stream* stream1 = [Stream forObjects];

    Stream* stream2 = [Stream forObjects];

    Task* task1 = [{

    while (!terminationCondition) {

    id outObject;

    ...compute outObject...

    [stream1 put:outObject];

    }

    } fork];

    Task* task2 = [{

    while (!terminationCondition) {

    id inObject = [stream1 get], outObject;

    ...process inObject; compute outObject...

    [stream2 put:outObject];

    }

    } fork];

    Task* task3 = [{

    while (!terminationCondition) {

    id inObject = [stream2 get];

    ...process inObject...

    }

    } fork];

    [currentTask waitForExit:task3];

    }

    In this example, the rootTask is creating three sub-tasks, which are automatically enrolled them on the readyQueue for eventual execution. When this task executes the [currentTask waitForExit:...] message, it will be suspended[14] and the first task on the readyQueue, task1, will begin executing.

    The [Stream forObjects] message creates streams that, by default[15], support buffered communication. In this respect, streams are similar to the formatted I/O of C stdio functions like fopen(), fread(), printf() and so forth. Stream I/O is buffered I/O, as distinct from the unbuffered I/O of primitives like open(), read(), write(), etc.

    Since task1's output is buffered, it will loop repeatedly, putting an additional object reference into stream1's internal buffer each time. Eventually the semaphore that stream1 uses to detect a full buffer will determine that task1 must wait. The semaphore will stop the task by linking it onto a queue for consideration once more room becomes available. The next task in the readyQueue (task2) will be scheduled to begin emptying stream1's buffer. And so forth...

    Heavyweight I/O (across domains) (toc)

    The preceding section has outlined an architecture in which card-level objects (tasks) communicate by a card-level communication mechanism (streams). And it has showed how card-level objects are constructed from the chip-level mechanisms of Objective-C and these, in turn, from the gate- and block-level mechanisms of C. Now we turn to showing how lightweight tasks couple with the heavyweight processes and I/O mechanisms of a time-sharing operating system, for which Unix is a typical example (Figure 4).

    Harry's program in Figure 1 contains many examples of where a lightweight task must synchronize with events outside the domain in which the task resides. Three examples are mouse clicks, activity on the modem or the keyboard, and disk I/O.

    The simplicity that makes Unix so convenient for C and shell programming makes it a worst-case environment for the kind of lightweight tasking extensions described here, far more difficult than environments like VMS or MS/DOS for example. Our success in implementing the TaskMaster PDL within the restrictive Unix environment shows that the TaskMaster API can be implemented on less restrictive platforms like OS/2, MS/DOS, Windows, Mach and other Unix platforms. This section will describe how the TaskMaster API deals with heavy-weight I/O, and then look beneath the covers at how this API was implemented under Sun Unix.

    The code within a card-level object (a task) should be independent of whether the task happens to be connected to another task, or to an external I/O device, which TaskMaster models as instances of a special class, Port. Whereas streams support a buffered I/O model as in C's stdio library, ports model unbuffered I/O devices, as in I/O system calls.

    The logic for filling and emptying a stream's buffer depends on whether the stream is connected to a task or to a Port. TaskMaster handles this by providing two stream classes. The Stream class is used only for connecting tasks to tasks. The PortStream class is used for connecting tasks to ports. The two streams offer the same message interface to their clients.

    By default under Unix, all I/O operations are blocking; the whole domain is suspended until I/O is complete. This means that if any task within a domain invokes Unix kernel I/O directly, the kernel will block the domain and every sub-task until the operation has completed. Since this is usually not what is wanted, lightweight tasks avoid doing kernel I/O operations directly by using Streams (for buffered I/O) or Ports (for unbuffered I/O). Streams provide a message protocol that supports all stdio I/O operations, including formatted I/O as in printf(), and ports provide a similar protocol for all kernel I/O operations. Although invoking stdio or kernel I/O directly does no harm apart from the blocking behavior mentioned above, tasks generally use streams or ports for all I/O.

    Non-blocking I/O is supported by the Port and Sensor classes. The Port class tracks the tasks that have I/O outstanding and schedules them so that other tasks can run while the I/O is pending. It is supported by Sensor, a platform-dependent class in the TaskMaster PDL, whose sole instance, theSensor, provides platform-specific logic for non-blocking I/O. Under Sun Unix, Sensor is based on the Unix select(2) system call.

    A complication is that streams can carry either references (objects) or values (characters) to other tasks in the same domain, whereas PortStreams can only pass values to Ports. This arises from the fundamental limitation that card-level (lightweight) processes can exchange references (pointers) to chip- and lower-level objects freely, while rack-level (heavyweight) processes can only exchange values (character strings).

    The PortStream class helps to hide, but of course can never eliminate, the distinction between lightweight and heavyweight I/O[16]. It implements its reference-stream I/O methods (put: and get) in terms of the storeOn: and readFrom: methods that all objects inherit from the Objective-C root class, Object. The put:method uses storeOn: to represent the argument (and everything it references) as a string of ASCI characters. The get method uses the complementary method, readFrom:, to reconstruct the object from this encoding.

    Exception handling (toc)

    Consider a subroutine, main(), which calls foo(), which calls bar(). The runtime stack that underlies the C runtime environment extends to record that main has called foo and that foo has called bar. Then it retracts as bar returns to foo and as foo returns to main. The same call/return path is used unconditionally, regardless of whether the subroutines ran successfully or failed because of an exception.

    The absence of a way of handling exceptions explicitly, independently from normal processing, is a severe obstacle to software quality and reusability. Since subroutines routines return the same way, regardless of whether they succeed or fail, a method that should return a handle to a new object might instead return an error code to indicate that it could not, perhaps because of insufficient memory. Since any such call might fail, the caller must check every return value, reporting any failures to higher levels with similar means. This is sufficiently tedious that it is neglected, allowing unhandled exceptions to crash the application.

    An `exception' is a situation where a computation does not proceed as planned, perhaps because of I/O errors, inability to allocate a new object because of insufficient memory, or defects in the software itself. `Exception handling' is a language/environmental feature that reserves the normal subroutine/message return channel exclusively for normal processing. Routines that return normally can be assumed to have succeeded, since those that fail will return via a independent channel reserved for exceptions. Low-level routines never fail by returning an error code for the caller to decipher, but by `raising an exception'. Higher level routines establish code fragments, `exception handlers', that will receive control if the exception they are to handle is raised by a lower-level routine.

    The following shows how exception handling might be done in C, in order to show the limitations of this solution and how these limitations are addressed in TaskMaster. TRY() is a C macro that uses setjmp() to record the machine's register settings before entering the computation that might fail; the foo subroutine.

    main() {

    TRY() {

    int v = foo();

    ...normal processing...

    } HANDLE(OUTOFMEMORYEXCEPTION) {

    ...handle low memory exceptions...

    } HANDLE(IOEXCEPTION) {

    ...handle IO failure exceptions...

    } OTHERWISE() {

    ...handle any other exceptions...

    }

    }

    foo() {

    TRY() {

    int v = bar();

    ...normal processing...

    } HANDLE(OUTOFMEMORYEXCEPTION);

    }

    bar() {

    id newObject = [SomeClass new];

    ...normal processing...

    }

    If the foo() subroutine, or any subroutine that it calls, fails because of some exception, it does not return normally. Instead, it `raises an exception', which returns directly to the higher-level routine, by using longjmp() to return directly, bypassing the intervening subroutines altogether. The TRY() macro detects the abnormal return and transfers to the appropriate handler, which handles the exception in some case-specific fashion. By having the TRY() macro manage saved register settings on LIFO stack, exception handlers can be nested so that exceptions are presented to their handlers in deepest-first sequence. The low-level exception handlers may choose to pass control to the next higher-level handler by popping the higher-level registers from the exception handler's stack and calling longjmp() again.

    The problems with this scheme will be familiar to anyone who has used it extensively. Since the exception handlers unconditionally execute in the context of the calling routine, as opposed to as a subroutine of the routine that detected the exception, information is unconditionally lost as to what sequence of calls triggered the exception. For example, foo's OUTOFMEMORYEXCEPTION handler can determine that bar, or one of its subroutines, failed because of insufficient memory. But it cannot tell which one, because the stack has been rewound before the handler has been invoked. This makes it useless for exception handlers to invoke process inspectors (debuggers), since the debugging information has been unconditionally discarded.

    TaskMaster takes a different approach. It exports the handler to the exception, rather than the other way around. By invoking the exception handler as a subroutine of the exception, the stack is never erased until the user's code has had a chance to use it. One way to think about the difference is that TaskMaster exception handlers are first class C subroutines, not compound statements as in the preceding example. They are passed as function pointers[17] in the exception handler stack and invoked as subroutines by the logic for raising an exception.

    Action expressions are a compiler-supported enhancement to deal with the fact that code that uses function pointers extensively can be hard to write and nearly impossible to understand later. This extension, which is planned for a future compiler release and is not yet available, would let this example be coded like this:

    main() {

    [{ int v = foo();

    ...normal processing...

    } ifException:{

    if (OUTOFMEMORYEXCEPTION) {

    ...handle low memory exceptions...

    } else if (IOEXCEPTION) {

    ...handle IO failure exceptions...

    } else {

    ...handle any other exceptions...

    }

    }];

    foo() {

    [{ int v = bar();

    ...normal processing...

    } ifException: {

    ...handle exceptions...

    }];

    }

    bar() {

    id newObject = [SomeClass new];

    ...normal processing...

    }

    The statements that look like C compound statements used as expressions, in {bold braces}[18], are action expressions, which will be described in the next section. Their relevance to exception handling is that

  • The code to be protected from exceptions, and the code for providing that protection, can be written alongside each other in a familiar readable fashion, without the syntactic clutter of working with function pointers directly.

  • The compiler will generate the necessary boiler plate automatically, transforming the action expressions into function definitions that the underlying C compiler knows how to handle. Although actions look syntactically like expressions, they are semantically analogous to function pointers that the exception handler can invoke as a subroutine of the exception, as opposed to within the scope of the calling site.

  • TaskMaster's run-time support for this style of exception handling is in place today, and can be used by following the code generation strategy that the extended compiler will use; coding action instantiation statements by hand.

    A final TaskMaster feature is that exception handling is closely integrated with lightweight multi-tasking. Each task maintains an independent stack of exception handlers that inherits any exception handlers of its parent task. For example, a parent task can provide supply handlers of last resort for exceptions in its subtasks. TaskMaster automatically initializes the root task with a default handler for all possible exceptions.

    This handler of last resort features an interactive task inspector with interactive debugging facilities. A programmer can use the inspector to examine the call history that led to the exception and specify whether to exit the application, produce a file suitable for detailed debugging, or to continue in spite of the exception.

    The inspector is based on a library of routines that interpret C call histories in terms that a programmer can easily understand. For example, call histories are not presented as hexadecimal numbers but in symbolic terms. Subroutine and selector names are spelled out with all arguments decoded. Object references are presented in terms of the object's class name and its address, string pointers are presented in terms of the string's contents, and so forth. These decoding facilities are based on a library of platform-dependent routines in the TaskMaster PDL. These routines support such platform-dependent operations as loading the application's symbol table. They also provide the heuristic rules that determine which format should be used in presenting the otherwise untyped numbers in a C call stack[19].

    Apart from such convenience features, the exception handling is not particularly dependent on the target platform. Exception handling is based on a pair of routines, setjmp() and longjmp(), in the standard[20] C run time library. Nor is it particularly dependent on multi-tasking, except that bundling exception handling with multi-tasking makes it possible for subtasks to manage exceptions independently from other tasks. Nor is exception handling specific to Objective-C. Its benefits are equally germane to ordinary C programs. This is another reason why TaskMaster's exception handling facilities are brought forth through two API's, a message-based API for users who want to treat exceptions as objects and a function-based API for those who want to treat them as functions.

    Action expressions (toc)

    Action expressions in Objective-C are related to block expressions in Smalltalk, with differences that adapt to the constraints of stack-based languages like C. Action expressions are a way to express actions, or deferred computations; computations to be written at one place but invoked from another.

    The classical examples of a deferred computation is a computation that a collection is to perform on each of its members or that a menu is to perform when selected. As the following examples show, action expressions are generally useful, especially for defining menus, operating on collection members, handling exceptions, and defining lightweight tasks:

    [ aMenu str:"Open" action:{ code to do a menu operation }];

    [ { code that might fail } ifException: { code to handle the exception } ];

    [ anyCollection do:{ code to be applied to each member } ];

    [ { code to run as a separate task } forkWith:2, arg1, arg2];

    Here is an a simpler example of how action expressions help to express a deferred computation. In this example, a printf() statement is to be passed to a subroutine, bar(), which will execute it at its convenience. Notice that the deferred computation is written right inside the foo subroutine, just like any C expression. But it is not to be executed there. The action is passed as an argument to the bar routine, so that bar can decide whether, and when, to invoke it later.

    extern int aGlobal;

    foo(aFormal)

    int aLocal;

    ...long, involved computation...

    /*

    * Pass this action to bar, which may run it later

    */

    bar({ int formalArg; | printf("...", aGlobal, aFormal, aLocal, formalArg);});

    ...long, involved computation...

    }

    An action expression can be thought of as any legal C compound statement, used in a context where an expression is otherwise expected[21]:

    Action expressions' usefulness becomes most obvious in contrast with how this example would be coded in ordinary C, using function pointers:

    
            extern aGlobal;

    static dummyFv, dummyLv;

    static dummyFn(formalArg)

    {

    printf("...", aGlobal, dummyFv, dummyLv, formalArg);

    }

    foo(aFormal) {

    int aLocal;

    ...long, involved computation...

    /*

    * Pass dummyFn to bar as a function pointer

    * so that bar can run it later

    */

    dummyFv = aFormal;

    dummyLv = aLocal;

    bar(dummyFn);

    ...long involved computation...

    }

    This is less desirable than the original code for reasons referred to earlier as syntactic clutter.

    Objective-C actions have a key restriction that is not present with Smalltalk blocks. The code inside a action accesses copies of the variables that it references in the enclosing scope. These copies are made when the action is instantiated, not when it is invoked, as is the case with Smalltalk Blocks. The copies are stored as indexed instance variables inside the Action object and not in the enclosing scope (foo's stack frame).

    When the underlying C function is invoked, these variables are exported to the function via a structure pointer, as can be seen in the following example. For example, the aGlobal, aFormal, and aLocal variables in this example are copied when the action is created (i.e. just before bar is called), not when the deferred computation is invoked (inside bar). Objective-C action expressions do not share memory with their enclosing scope, they cannot export changes to the enclosing scope as in Smalltalk. Changes to action variables is ineffective, since the change affects a copy, not the original.

    This may have made the simple seem unduly complicated. What is going on here can seen by examining the C code that the compiler would emit for this example:

             static void fn(struct { int aGlobal, aFormal, aLocal; } *c, int formalArg) 

    {

    printf("...", c->aGlobal, c->aFormal, c->aLocal, formalArg);

    }

    foo(aFormal) {

    extern int aGlobal;

    int aLocal;

    ...long, involved computation...

    bar(createAction(fn, 3, aGlobal, aFormal, aLocal));

    ...long, involved computation...

    }

    Of course, this example was intentionally simplified by choosing an example in which everything is of type int. This does not mean that actions will only be usable for integers; just that the adjustments that the compiler would emit for other types seem obvious. Until the compiler has been enhanced to emit this code automatically, this example shows what a present-day Objective-C user would write to use TaskMaster's action-based library facilities today.

    References (toc)


    [2] Brad Cox; IEEE Software; November 1990

    [3] Brad Cox; Byte magazine; October 1990.

    [4] I chose this example because of personal experience. Although my programming skills are like Tom's and Dick's in other programming environments, I am like Harry on the Macintosh. If the Macintosh provides any solution to the example in this section, the solution has proven inaccessible to me, and by extension, to the Harrys of this world.

    [5] Dan Ingalls, Scott Wallace, Yu-Ying Chow, Frank Ludolph, Ken Doyle; "Fabrik; A Visual Programming Environment"; OOPSLA `88 Proceedings.

    [6] Metaphor is a office automation product of Metaphor Computer Systems; Mountain View, CA. Since I have only limited access to information about this system, this section may contain errors of misunderstanding. I believe that is essentially accurate with respect to Metaphor's philosophy and architecture, but potentially inaccurate with respect to its implementation.

    [7] My original source of information is a non-technical presentation by Metaphor's CEO, David Liddel, at an IBM symposium on object-oriented technologies. This information is now several years old and may be out of date and partially incorrect. Subsequent technical discussions conform the broad outlines of these statements, but of course do not compensate for my lack of direct hands-on experience with this system.

    [8] How large a stack arena should be created, and what happens if more than this is used, will be discussed later.

    [9] In other words, semaphores are Dijkstra counting semaphores, not the usual binary semaphores.

    [10] Since the present incarnation of TaskMaster uses only a single readyQueue, there is no way of assigning different priorities to different tasks. A prioritized scheduling scheme has been requested by those who want to use TaskMaster for real-time scheduling, and will likely be added in the next release. The change is likely to be as simple as making readyQueue an array instead of a single variable.

    [11] To protect against the possibility of C compilers doing fancy register optimizations across function boundaries, contextSwitch() currently saves and restores all registers, not just the SP.

    [12] This does not mean that TaskMaster only supports simple stream-based synchronization This document focuses on the simplest model because of its simplicity and its relationship to end-user programming. More complicated synchronization mechanisms are also provided for more complex tasks, and others can be added, based on lower-level mechanisms like Semaphore.

    [13] This does not mean that streams will be the only mechanism that will be used `under the covers', nor does it mean that streams are the only mechanism that TaskMaster provides.

    [14] This program uses Blocks to eliminate the syntactic clutter that would obscure this example if written in ordinary Objective-C. Task bodies (the statements enclosed in {bold braces} within the [{...} fork] messages) are written in-line rather than as separate C function definitions. A block can access variables in its enclosing C scope. Notice that these blocks reference auto variables of the main subroutine, stream1 and stream2.

    [15] The waitForExit: mechanism is based on a separate task synchronization mechanism, different from Streams, called Events. Whereas Streams support a narrow-casting, or point-to-point communication model, Events are a broadcast mechanism. Until task3 broadcasts an event signaling its termination, rootTask will remain suspended on a queue managed by the task3 termination event..

    [16] Other messages are available for specifying the buffer capacity. Setting the buffer size to 1 is one way to obtain strict alternation between producer/consumer tasks.

    [17] Passing a reference to an object does not replicate the object; only the reference. But passing the object by value replicates the object itself.

    [18] Actually, they are passed in the handler stack as pointers to instances of Action, which are objects that hold a function pointer internally, along with copies of data that the action expression references from its enclosing scope.

    [19] Bold braces are purely a typography convention used within this document to suggest an as-yet-undetermined set of block-delimiter tokens. The ideal choice would be ordinary braces, as this would suggest that a block is a compound statement used as an expression. However it is not yet clear that this could be unambiguously distinguished by a parser.

    [20] These routines are highly platform dependent, and are by far the least portable aspect of TaskMaster's PDL For example, it may prove to be impractical to provide them, and the task inspector that they support, on at least some RISC machines.

    [21] I do not know if these routines are specified by any formal standard. I only know that they have been present in every C environment that I've ever used, and that they can be easily provided in assembly language if an environment fails to provide them. For example, the contextSwitch() subroutine described in the previous section is nothing more than a setjmp to save the current task's SP (and other registers) and by a longjmp to load the new task's SP. In fact, contextSwitch() was originally implemented in precisely this way. This scheme was replaced with the present only because of nagging uncertainty as to the detailed behavior of setjmp and longjmp on all platforms (does this platform's setjmp save all registers - or only the SP?).