2. Cedar Overview
The present Cedar organization is the result of careful planning and of applying lessons learned from several earlier implementations; Figure 1 depicts its overall structure, as a set of major layers or divisions each comprising a set of layered components. By convention, a component may only call upon the facilities supplied by components at the same or lower levels.
The four major Cedar divisions are: the Cedar Machine—hardware, microcode, and primitives needed to execute the language; the Nucleus—the operating system kernel; Life Support—the basic facilities needed for program development; and Applications—packages and tools written by and for the Cedar user community. Underlying the entire system are the facilities of the Cedar language. This section begins with a reminder of the important structural features of the language. It then presents an overview of the four Cedar divisions (from bottom to top as depicted in Figure 1), emphasizing the organization of the components and the orderings among them.
2.1 The Cedar Language
The Cedar language is a direct descendant of Mesa [8, 13, 16], inheriting from it a Pascal-like syntax, strong typing, exception handling, first-class procedure variables, and a modular structure based on independently specified interface and program modules. Like Mesa, Cedar also includes full support for multiple processes whose interactions within a shared single address space are protected by monitors.
The interface or definitions module provides a means for describing a set of types, procedures, and variables that together specify a related set of functions or a data abstraction. In Mesa and Cedar, interface modules are compiled into symbol tables that are used both at compile time and when modules are bound together to enforce inter-module type checking. Program modules contain actual data declarations and executable procedures. A program module exports its implementation to satisfy the specifications of one or more definitions modules. Program modules gain access to the implementations of other interfaces by mentioning their interface names in import lists.
The configuration is another concept inherited from Mesa; it is a composite implementation module produced by combining other program modules or configurations. The import list of each component in a configuration must be satisfied by the interfaces exported by other included components, or by a list of imported interfaces that forms part of the specification of the configuration. A configuration may be constructed to export (make available outside the configuration) all or only some of the interfaces that are exported by its components. This is an important attribute in controlling system structure.
Safe storage is the designation for the extensions that distinguish the Cedar language from Mesa. These extensions provide automatic storage management and delayed type binding in the guise of generic pointers, and a runtime type mechanism. The objective was to achieve for the strongly-typed Cedar language the benefits of automatic storage management that have always characterized implementations of languages such as Lisp and Smalltalk. Aside from programmer convenience, these benefits include the provision, within a single address space, of a high degree of memory protection.
References, a new class of pointer data types analogous to Pascal or Mesa's POINTER types, provide the means for program access to safe storage. As with Mesa pointers, a reference (REF) variable is declared to hold a reference to (the address of) information of a specified data type. A special operator (NEW) allocates a new value of a specified type, yielding a reference to the new value. References may be freely replicated and discarded (by assignment or by procedure parameter binding), subject only to type constraints, without any concern over possible storage leaks (storage objects that are no longer referenced but have not been freed) or dangling references (storage objects have been prematurely freed, even though active references still remain); the system releases a region of storage only when no valid references to it remain. This is also true of nested references, which may be produced by allocating them directly, using NEW, or by allocating records that have references declared within them.
The language extensions supporting references, plus a carefully-selected subset of the original Mesa language, form the safe subset of Cedar. Within code declared to be safe, the compiler generates additional runtime traps that detect assignments to numerical variables falling outside their declared ranges, attempts to dereference NIL, and array index bounds violations. Furthermore, reference variables are always initialized to the NIL value. Based on these and other safeguards, it has been formally demonstrated that programs written in the safe subset cannot destroy the integrity of the memory allocation structures [18]. The more dangerous features (including the original pointer types and pointer arithmetic) that remain outside the safe subset must occasionally be used, most often in the lower levels of the system. The additional syntax required to use them provide ample warning to the programmer that additional diligence is required.
Many languages include the notion of generic procedures. Typically, these procedures either manipulate data structures consisting of objects of unspecified types (such as lists, arrays, or trees), or they are willing to accept any of a number of specific object types as parameters, using some runtime method to determine which type has been supplied.
In Cedar, these capabilities may be implemented by declaring generic reference variables (denoted as REF ANY) that do not define the types of their referents. To examine or modify a REF ANY's contents, one must assign the reference to a REF variable bearing its type. This assignment includes a runtime verification which reports an error if it fails. However, any reference may be stored in a generic reference variable, either through assignment or parameter binding. Generic references do not provide a complete realization of a polymorphic data type system, but the use of even this limited capability to provide generic procedures for manipulating objects such as text streams adds to the flexibility and convenience of many Cedar packages.
Safe storage has made it possible to introduce a number of valuable data types into Cedar. Notable among them are variable-length text strings (known as ROPEs), variable-length linked lists and arrays containing values of arbitrary (but specified) type, and ATOMs -- uniquely addressed values much like Lisp atoms, which can be located by their client-assigned names, decorated with lists of properties, and compared for equality using a simple pointer test. The language supports the most common operations on these quantities; the others are supplied by packages in the Nucleus.
In addition, the runtime type capabilities needed to support safe storage also enable the Abstract Machine capabilities described in section $1.4.
2.2 The Cedar Machine
The Cedar compiler produces byte-coded instructions that can be executed by microcode for our processors [10]. The microcode also provides linkages to compiled fault and exception-handlers; extensions for Cedar in support of safe storage include reference-counted store instructions and additional exception handlers that intercept dangerous storage references.
Cedar has borrowed from the Mesa/Pilot system the notion of abstract device interfaces [19]. Corresponding implementations on each processor for each specific device type extend the virtual machine defined by the byte codes to include the peripherals as well.
I don't feel inclined to expand this much, since these features aren't Open-sub-anything.
2.3 The Nucleus
The Cedar Nucleus comprises the basic operating system facilities needed for memory management, process management, file system management, and communications with the user and the outside world. Here we list all the major components of the Nucleus.
Disk: The Disk component provides a uniform interface to the attached disk drives. It provides low-level facialities for investigating the state and configuration of each drive, and for performing page-level input/output operations between specified disk addresses and physical memory locations. (or does it use the map but blow up if page faults occur? Don't know.) The Disk routines support concurrent operations by different processes, providing any needed synchronization among simultaneous requests.
Virtual Memory: The Cedar virtual memory (VM) differs in philosophy from its most recent ancestor, Pilot [19]. Pilot was designed for processors that had relatively small physical memories and disk capacities. This required a space-efficient but complex implementation based on mapping regions of virtual memory to named disk files. Cedar, intended for larger machines, has been able to abandon this approach in favor of a simpler, more time-efficient scheme reminiscent of earlier VM systems [27]. Cedar represents virtual memory as a single backing file, employing a resident page map. File input/output must be accomplished by explicit operations, rather than as VM mapping actions. The performance improvements, both for code swapping and for files access, have been significant. Perhaps more importantly, this design permits the virtual memory implementation to occupy a position quite low in the Cedar level structure; only the Cedar machine implementation, the Disk component, and the VM implementation itself need to deal with physical memory addresses. The preponderance of the Cedar system can operate in the virtual memory environment.
SafeStorage: The safe storage extensions to the Cedar language are supported by a runtime type system, a storage allocator, and a combination of garbage collection techniques derived from earlier designs by Deutsch and Bobrow [5], then later revised. A full description of these algorithms appears in Rovner's recent paper [20].
The compiler generates information sufficient to assign a unique runtime type identifier to each data type used in a program, and to build a map locating reference-containing fields within composite data types such as records. The allocator, which implements the Cedar NEW operator, stores a type identifier as auxiliary information associated with every allocated object.
An incremental garbage collector runs at frequent intervals, triggered by specified elapsed-time or memory utilization criteria. It operates in a background process, using no more than one quarter of the available processor cycles. This does not interfere noticeably with interactive operation. The incremental collector is able to reclaim most of the storage objects that are no longer referenced.
However, The incremental collector cannot detect cyclic data structures, such as those generated by two-way linked lists or certain queue implementations. A conventional, preemptive
trace-and-sweep garbage collection algorithm has been included in order to be sure that such structures can be reclaimed. The trace-and-sweep collector reclaims virtually all unreferenced storage, but monopolizes the machine for several minutes in the process. It is usually invoked manually; however, servers that need to remain avaialable for long periods of time without danger of storage fragmentation can invoke it directly.
[warn about needing T&S for circular references, and about conservative scan, or leave this to Paul?]
Do we need to discuss finalization?
File: The local file system underlying Cedar is straightforward. It manages the configuration of one or physical disk volumes, and their subdivision into logical volumes. Within volumes, it manages the page-level allocation, deletion, reading, and writing of disk files. The file allocation methods borrow heavily from earlier Xerox systems [28],[19]: redundant information stored with each file page permits recovery if portions of files or directories are damaged. Only primitive locking facilities are provided, based on many-reader, one-writer write locks.
The File component does not include a directory implementation, leaving that up to higher-level applications. Instead, the file-creation procedures return unique identifiers which the calling applications can use to locate them later. Different applications may choose their own directory organizations for their files, which may or may not also appear in the standard directory provided by the FS package.
FS: The Cedar file management and directory package (FS) represents a major improvement over our previous programming environments. FS supports the appearance of a uniform file naming system spanning the user's local disk and the set of shared file servers available through the attached communication network. FS provides its facilities by maintaining two directories: the local file directory and a local cache directory.
{This is all there was before. Which is better?} The implementation includes a cache for local copies of recently-referenced remote files, a local directory structure that includes links to remote files, and file transfer mechanisms that are invoked automatically to cache a local copy when a program uses FS to open a remote file. Our current file servers have limitations that prevent reading and writing of remote files from being treated entirely symmetrically (files must first be written locally, then transferred as a whole); FS enforces these restrictions.
A full FS file name has the form
(coonsider a table or figure here with sample names.)
[HostName]<Directory>Subdirectory>...>FileName.extension!version,
where HostName names a file server connected to the communications network. For instance,
[Indigo]<Cedar5.2>Viewers>ViewerOps.mesa!42
describes a program source file that forms part of the current Cedar release, and
[]<>Users>Hagmann.PA>Lupine>LupineRuntime.bcd!1
names a file in the local directory. This latter syntax is a shorthand for
[LocalCedarVolume]<Root>Users>Hagmann.PA>Lupine>LupineRuntime.bcd!1
Default working directory names may be set up so that shorter names can be used for most purposes. {This is more detailed than anything else -- somehow felt unspecified without it.}
The local file directory provides a local, hierarchical name space for files. Arbitrary nested directory structures, including subdirectories assigned to different users, can be expressed as subdirectories of the single root directory. Entries in the local directory may be implemented either as references to local files or as links (expressed as full path names) to remote ones. Thus, a local environment can be created, describing for example a complete system or set of related tools. Only the files whose contents are actually needed will be copied to the local cache. Depending on what the user is doing, often only a small subset of the files will actually actually need to be retrieved.
The local cache directory organizes the set of remote files for which local copies exist. Whenever a program issues an Open request for a file that is not in the cache, FS performs a network file transfer to obtain the local copy; the calling program always reads from the local file. The request may have named the file directly, or may have resulted from following a local directory link. Disk space is managed automatically by flushing inactive files from the cache to make room for new ones. Cache entries refer to specific versions of remote files, by name and creation time.
Our current file servers have limitations that prevent reading and writing of remote files from being treated entirely symmetrically. FS will not accept a request to open a remotely-named file for writing. The file must therefore first be written locally, and its name entered in the local directory. A special FS copy routine may then be invoked to create a new remote copy and replace the local directory reference with a link to the remote one.
IO: The IO interface defines generic procedures for creating and using streams of characters or words, including handy input scanning and output formatting routines. The Cedar IO package contains specific implementations supporting several sources and destinations, among them disk files, the keyboard and display, the Ethernet, and pipes (objects that provide the buffering and synchronization needed to connect an output stream from one process directly to the input stream of another [30]).
It is easy to define specialized streams for specific applications. Programs that read and write streams can be coded without explicit knowledge of the source or destination medium.
Communications: Network communications require substantial software support beyond the low-level device drivers. Cedar includes a complete implementation of the experimental "Pup" internetwork protocols described by Boggs et al in [29]. Lower levels of the Pup package provide a basic datagram (packet-level) service. Higher levels perform asynchronous terminal emulation, file transfer, a remote procedure call facility, and a range of information utilities, such as time and name lookup services.
Of the higher-level protocols, the most important for new Cedar applications is the communications support for remote procedure calls (RPC). Ordinary procedure calls to procedures in specified interfaces execute on remote machines, returning any results to the caller as usual. The implementation is based on stub routines that field the client's calls locally. A stub implementation composes procedure parameters into data packets, handles the reliable communication of requests to the remote site, then removes any result values from incoming packets for return to the caller. Corresponding stub routines at the remote site complete the linkage to the actual procedure implementations. The Cedar RPC package, described by Birrell and Nelson in [3], provides the underlying algorithms that complete the calls reliably, efficiently, and securely (using optional DES encryption techniques). Cedar RPC builds its protocols directly on the datagram-level of the Pup package.
Implementations of RPC for other languages and programming environments are beginning to extend the range of services that Cedar applications can provide or use. Is there a way to mention Courier?
Terminal: Most Cedar applications are content with the display-management and user input facilities supplied by Viewers (section 2.4.5) and TIP (section 2.4.2). Viewers allow applications to share regions of a single screen view, and to sort out the user actions that are intended for them. However, more radical applications may need to use the display screen or input devices in a conflicting way -- to try out a new or heavily-modified window package, for example. The Terminal interface is a clean abstraction to the display, keyboard, and mouse. There may be several instances of Terminal, each with its own full-screen bitmap. Operations are available to switch the use of the physical hardware (and thus the entire screen view) among the Terminal instances. The standard Cedar view is obtained through the use of just one Terminal instance; another is employed to drive a much simpler user interface when the system is being loaded.
Running programs. At the "top" of the Nucleus are two final components. The Loader provides the capability to load additional components into a running Cedar environment. (The Nucleus is loaded and initialized using booting methods outside the scope of this paper.) The Checkpoint/Rollback component permits the user to save the present Cedar environment (that is, the contents of virtual memory) in a checkpoint file, as well as to restore ("roll back") a machine to the state represented by such a file. Checkpoints can be used to preserve desired a standard system configuration for rapid restarts, or to save the evidence after a crash.
2.4 Life Support
The Life Support division depends on the Nucleus and adds more sophisticated packages and tools. It provides standard user interaction facilities such as a screen manager, a text editor, command and expression interpreters, and program management tools.
From this level on, it is relatively easy to experiment with alternative components, either by replacing existing components with variants, or simply by including the alternatives in private configurations and ignoring the system-provided components. A fuller discussion of these techniques appears in section $x.y.
This section sketches the standard life-support components included with Cedar.
Useful Packages: During the implementation of Cedar, many packages have been produced that have proved generally useful. A number of them are included as part of the standard life support system of Cedar. Examples include packages for sorting arbitrary values, for maintaining symbol tables, and for managing queues of user-invoked commands. These packages might be thought of as extensions of the basic "Cedar machine." As their numbers increase,they will make programming in Cedar increasingly convenient.
JaM? TIP and later Tioga make extensive use of JaM. So does Cedar Graphics. We should probably mention it explicitly and then sprinkle references to it here and there. Too bad JaM was never published separately -- or was it?
The Inscript and TIP Tables: The user communicates with Cedar by typing, by moving the mouse, and by clicking mouse buttons. The Inscript package buffers time-stamped versions of these input events. If an application has special high-performance user input requirements, such as the need to react in real time to the trajectory of the mouse-driven cursor, it can use the inscript package directly and independently to extract the input events from the buffered stream. This technique is usually superior to the direct sampling of the hardware by individual applications because the system collects and timestamps the events regularly, using a high-priority process; it is therefore less likely that events will be missed or that confusion about the intervals between events will occur. Each application must determine which of the input events are intended for it and what their semantics are, rejecting those that are intended for other applications that are sharing the screen.
Most applications, are satisfied to allow the user's actions to be interpreted by the the Terminal Input Processor, or TIP. The TIP interprets input events based on easy-to-write specifications, called TIP tables. A TIP table entry associates each event with a procedure that represents the semantics of the event. Standard rules determine the choice of which TIP table to invoke for each event, as well as which viewer, or screen region, to include as a parameter to the procedure. There are default TIP-tables that define standard behavior for the basic Cedar user interfaces, specialized TIP tables for nonstandard or specialized applications (such as a drawing program), and user-specified TIP-tables that allow the user to custom-tailor somewhat the interfaces to any application.
Based on the buffered timestamps, TIP provides support for time-dependent actions, such as clicking a mouse button twice in rapid succession or depressing a key for an extended period of time. A typical TIP procedure creates a new process to carry out the desired action; this is the origin of concurrent user-invoked activities within Cedar.
The Cedar Abstract Machine: An original goal for Cedar was to combine a compiled, strongly-typed language with the interpretive symbolic power of Interlisp or Smalltalk. The Abstract Machine (AM) is a step in this direction. It is based on the following concepts:
1. Runtime types. Cedar assigns a unique runtime identifier to every type declared by every program module that enters the system. Thes are the same runtime values that the garbage collectors use to determine the types, and thus the layouts, of allocated objects.
2. Type information interface. The AMTypes interface provides procedural access to the names and structure of data types. Given a runtime type identifier one can determine its name and its class: composite (record), redefinition of a previously-declared type, pointer or reference, procedure, stack frame, basic (INTEGER, for example), etc. Non-basic types are derived one way or another from other types. For any non-basic type, depending on its class, there are AMTypes operations that yield the number of components and the type identifier of each component. Special functions deal with the cardinality of array and sequence types, etc.
3. Value manipulation. Other AMTypes procedures allow for the examinion and modification of the components of runtime values, based on the type information obtained from AMTypes procedures. The association between the referents of REF variables and their runtime type information can be made safely; for other values, the associations are based on TRUSTED program assertions. Facilities exist both for examining and modifying runtime values through abstract machine operations. These operations are useful in the construction of interpretive programs that can operate on arbitrary data structures; they are always significantly more expensive than the corresponding compiled Cedar statements operating directly on the same objects.
4. The AMModel interface plays a similar role for program structure and runtime program configurations. One can determine the makeup of a procedure in terms of its embedded blocks, of a program module in terms of its procedures, and of a configuration in terms of the program modules and other configurations that comprise it. Based on this structure, one can determine which programs have actually been loaded into the system, and where their code and global storage frames are located in virtual memory.
5. The AMProcess interface provides the corresponding operations for the active processes in a running Cedar system.
6. Finally, AMEvents provides a set of low-level operations for settting breakpoints and for tracing program flow.
The implementations of these capabilities are ultimately all based on the symbol tables and program graphs that the Compiler, Binder, and program loaders produce. (The runtime type identifiers are also derived from symbol tables and from other derived structures.)
Given the abstract machine, it is possible to write as ordinary Cedar applications interactive interpreters, debugging tools, and other applications that need to be able to present program structures in a form sensible to users. In fact, Cedar's debugging and interactive interpretation tools have undergone several rounds of design and testing, largely independent of refinements to the abstract machine.
Graphics: Cedar runs on a powerful personal workstations that relies heavily on the power and flexibility of high-resolution bit-mapped display terminals. In earlier Xerox systems, the programmer was provided only with low-level bit map operations, such as the RasterOp function described by [who] in [what], that did not provide very convenient graphical abstractions for applications programmers. While it is possible to manipulate bit maps directly in Cedar, virtually all existing applications instead make use of the Cedar Graphics package, which provides support for the presentation of such graphical entities as multiple-font text, lines, curves, closed outlines, and sampled images. Most of these images can be scaled, rotated, translated, and clipped to arbitrary rectangular boundaries simply by providing the package with simple specifications. Images can be rendered in a device-independent fashion on color or black and white display devices, or on a variety of laser printers.
Viewers: Most applications are intended to be used in a cooperative fashion, sharing the display real estate with concurrent applications. They do this using Viewers. Viewers are Cedar's display windows— non-overlapping rectangular regions whose positions and overall sizes are managed by the Viewers package, but whose contents are the business of the individual applications that create them. Clients can also register TIP tables and their associated semantic routines with individual viewers in order to provide specialize user interfaces. The Viewers package manages the allocation of viewers to the available real estate, "painting" the contents of each viewer based on client-supplied specifications, allocating and painting iconic versions of "closed" viewers, etc. (Other widely-used user interface facilities, such as menu buttons, are also implemented by packages in Life Support.)
We will use Viewers as an example of the open, or translucent, architecture of Cedar, by describing the successive steps a programmer could take to bypass first the standard viewer methods for displaying information, then the Graphics interface (while continuing to use a Viewer), and finally the Viewers mechanism itself (by saving the current bitmap and managing the entire screen directly.)
2.4.5 Viewers
Most clients confront the Cedar display through at least one more level of abstraction, provided by the Viewers package. Viewers are Cedar's display windows -- rectangular regions whose positions and overall sizes are managed by the Viewers package, but whose contents are the business of the individual applications that create them.
Besides providing a standard wholesale way to allocate the screen, Viewers provide the linkages for connecting the user's input actions, via TIP tables, to the actual functions performed by the applications, for serializing these actions when the user types faster than the actions can be performed, and for automatically updating the screen when viewers are added or removed.
Cedar Viewers never overlap, but instead reside within a fixed number (two or three) of columns, sharing the available height with other viewers assigned to the same column. Viewers can either allow their height to vary to share the available space equitably, or can insist on some fixed or minimum size that they must occupy. The user can override the assigned widths of the columns, and the heights of individual viewers. Viewers whose contents the user would like to have handy but does not need immediately can be "closed" -- represented as small icons that occupy the bottom inch or so of the screen until their are reopened. This tiled design was enforced by its designers, not by any limitation on the underlying graphics facilities, which would also support the more common overlapping-window model.
The Viewers package also serves as a point of integration for Cedar applications. Viewer instances are assigned to Viewer classes. A viewer's class determines its display and user interface behavior. Programmers can create viewers as members of standard system classes, or can define their own viewer classes. A viewer can also be associated with a custom TIP table, and with other attachments that customize its operation. There is a provision in a viewer's data structures to store the information necessary to associate, for instance, a text file or a telephone directory with the viewer so that its contents can be updated when the information changes or restored when its icon is next opened.
A summary and apologia here cited Rick's [1] and Warren's [24] papers as sources of more information about graphics and viewers in Cedar. In original paper, this apologia appeared after and also referred to Tioga.
Tioga: The components in the upper levels of the Cedar Life Support division resemble user applications more than components of an operating system, in that they are quite large and they provide functions directly to Cedar users. However, because their functionality is vital to providing a complete, working environment for users, they are included in the Life Support division.
A good example is Tioga, the structured text editor used to develop Cedar programs and formatted documents. Tioga is a galley editor (it provides little support for page makup or the assignment of information to printed pages) that can manage tree-structured text documents. Nodes (paragraphs, approximately) and text content can be decorated with user-specified styles and font information that control their displayed or printed appearance. Tioga makes extensive use of TIP in the specification of its user interface. It extends the use of the JaM interpreter beyond its use in TIP tables to define the semantics of user actions: JaM sequences are used to provide history-lists that support "undo" operations, and to provide the semantics for abbreviations and other prerecorded sequences of editing actions.
Apart from its use in the editing of documents, Tioga is an important Cedar resource, since it can be used in any text-based viewer. This means that applications like command language interpreters and specialized display-based tools can employ Tioga's well-understood user interface and text-manipulation features. It also means that text and other attributes can be freely copied among various classes of viewers. For example, one can record the results of a command in a file, or invoke a command by copying it from a "recipe-book" document, using only the mouse-driven text-editing operations of Tioga.
Compiler, Binder, Loader: The Cedar compiler runs as a multiple-pass (non-interactive) program. The binder, also a separate batch application, produces larger configurations of modules from individually-compiled modules and previously-bound configurations. During this process, it extends Mesa's strong type checking by ensuring that the names and time-stamps of exported interfaces match those specified by the components that import them. Some of the binder's capabilities reappear in the Cedar loader program, which loads modules and bound configurations into a running system, resolving the remaining imported references. The loader can be called by a program or invoked by explicit user commands. {Loader is funny. Belongs here functionally, but obviously is situated lower in the structure. Wanted to get the relationship in.}
Command Tool: Cedar Life Support includes a conventional command interpreter in the form of a viewer into which the user and results of user-invoked commands type alternately. The command syntax, an amalgam derived both from UNIX [31] and earlier Xerox systems, includes provisions for redirecting command output to another destination (usually a file or a pipe to a process executing a concurrent command), or for accepting command input from another source (also usually a file or a pipe).
The Command Tool provides a small number of built-in commands, primarily for running programs and for examining and manipulating local and remote file directories through the services of FS (list, delete, copy, etc.). As applications are started, they may register additional commands with the command tool, extending the set of operations it can support. Commands are usually executed sequentially, or in a tightly-coupled fashion using pipes, but it is also possible to invoke a command such that it runs concurrently, using a separate viewer for its input and output activities.
Source-Level Debugging: The Abstract Machine forms the basis for a number of standard tools that collectively enable interactive source-level debugging: an interpreter for expressions in the Cedar language, which can be called from a program or driven directly by the user (for instance, in response to a breakpoint); a tool for exhibiting the state of all the running processes; commands for setting and clearing breakpoints; and so on. In addition, specialized diagnostic routines can be built for specific purposes, calling on the facilities of the Abstract Machine.
Package Management: {help, please!} Even with conventional timesharing systems, existing file directories do not provide adequate support for the maintaining consistent versions of software packages and applications. Component developers often find that they are working with inconsistent sets of sources and imported object files; component users discover inconsistencies in the files they need to run them. These problems get worse in a distributed system like Cedar, where one works with local file copies.
An application with a very important role in structuring Cedar components is the DF Tool. The DF Tool operates on a DF file: a text file containing the (unique) full names of the file versions comprising some package or program. Here describe the most important DF file operations, please. Schmidt describes the value of DF files in maintaining self-consistent versions of programs, and as a means for documentation, in his PhD dissertation [21]. A variant of the DF Tool has also been adapted for use in XDE [23]. Should really extend with indication that system modelling is a further extension -- more language semantics -- that we haven't got to yet. There's stuff in the original StructureOfCedar.tioga version that discuss DF files more fully.
2.5 Applications
Applications that have been built using Cedar include: the Alpine transaction-based network file service; the Cypress relational database package [4]; the Walnut electronic mail system, based on Cypress and the Grapevine message transport mechanism [2]; numerous specialized graphics applications [1]; an experimental telephone and voice recording system [22]; and a suite of VLSI design, simulation, and analysis tools [14]. [To indicate the range and magnitude of implementations that Cedar will support, the full paper will describe a few of these applications in more detail.]
2.5 Applications
It should by now be clear that any distinction between "the system" and "the applications" is a matter of convenience, as is the assignment of components to particular levels. Components that are originally developed as applications are often evaluated, modified, and incorporated into lower levels, usually in the region known as Life Support. Others are more clearly user programs that provide explicit functions for users or that support specialized needs.
There is only space here to mention a few of the applications that have been produced to date in Cedar. These applications will be the subjects of future publications.
The Debug Tool is an example of an application under development that will probably find its way into Life Support. It provides the user with a way to view the set of active and suspended processes, to "freeze" selected processes so that their execution will not proceed until "thawed", and to examine the procedure call stacks associated with each process.
Cedar includes a number of components to support data base applications. Alpine is a transaction-based network file service, written in Cedar, and running on a dedicated Dorado. Cypress is a relational data base package that runs in a user's workstations but stores its database on Alpine servers. Walnut is an electronic mail system that operates in conjunction with the Grapevine message transport mechanism [Grapevine], using Cypress and Alpine to manage each user's messages.
Cedar applications in the area of computer graphics include programs for producing illustrations, for manipulating three-dimensional synthesized graphical objects, for processing scanned images, and for driving experimental printers. [Beach?] A server and individual workstation programs have been developed to support the operation of an experimental telephone system that uses Ethernet communications to transmit voice conversations. [Swinehart]. Hardware designers have produced a suite of IC design, simulation, and analysis tools in Cedar. [ChipNDale? -- any refs?] Projects of similar scope and magnitude are underway.
References
[1] R. Beach. ``Experience with the Cedar Programming Environment for Computer Graphics Research,'' Graphics Interface 84.
[2] A. Birrell, R. Levin, R. Needham, and M. Schroeder. ``Grapevine: An Exercise in Distributed Computing,'' CACM 25, 4, Apr 82.
[3] A. Birrell and B. Nelson. ``Remote Procedure Call,'' ACM TOCS 2, 1, Feb 84.
[4] R.G.G. Cattell. Design and implementation of a relationship-entity-datum data model, Xerox PARC Report CSL-83-4, May 83.
[5] P. Deutsch and D. Bobrow. ``An Efficient, Incremental, Automatic Garbage Collector,''CACM 19, 7, July 76.
[6] P. Deutsch and E. Taft. Requirements for an Experimental Programming Environment, Xerox PARC Report CSL-80-10, 1980.
[7] J. Donahue. Integration Mechanisms in Cedar, Xerox PARC Report in preparation, 1984.
[8] C. Geschke, J. Morris, and E. Satterthwaite. ``Early Experience with Mesa,'' CACM 20, 8, Aug 77.
[9] A. Goldberg and D. Robson. Smalltalk-80: The Language and its Implementation, McGraw-Hill, 1983.
[10] R. Johnsson and J. Wick. ``An Overview of the Mesa Processor Architecture,'' SIGPLAN Notices 17, 4, Mar 82.
[11] B. Lampson and K. Pier; B. Lampson, G. McDaniel, and S. Ornstein; D. Clark, B. Lampson, and K. Pier. The Dorado: A High Performance Personal Computer, Three Papers, Xerox PARC Report CSL-81-1, Jan 81.
[12] B. Lampson and E. Schmidt. ``Organizing Software in a Distributed Environment,'' Proc. of SIGPLAN 83 Symposium on Programming Language Issues in Software Systems, San Francisco, June 83.
[13] H. Lauer and E. Satterthwaite, The Impact of Mesa on System Design. Proc of the 4th Int'l Conference on Software Engineering, Munich, Sept 1979.
[14] E. McCreight. ``The Dragon Computer System: An Early Overview,'' in Proceedings of the NATO Advanced Study Institute on Microarchitecture of VLSI Computers. Urbino, Italy, July 1984.
[15] R. Metcalfe and D. Boggs; R. Crane and E. Taft; J. Shoch and J. Hupp. The Ethernet Local Network: Three Reports, Xerox PARC Report CSL-80-2, Feb 80.
[16] J. Mitchell. Mesa Language Manual, Xerox PARC Report CSL-79-3, 1979.
[17] W. Newman and R. Sproull. Principles of Interactive Computer Graphics, 2nd ed., McGraw-Hill, 1979.
[18] S. Owicki. ``Making the World Safe for Garbage Collection,'' POPL 8, Jan 81.
[19] D. Redell, Y. Dalal, T. Horsley, H. Lauer, W. Lynch, P. McJones, H. Murray, and S. Purcell. ``Pilot: An Operating System for a Personal Computer,'' CACM 23, 2, Feb 80.
[20] P. Rovner. On Adding Garbage Collection and Runtime Types to a Strongly-Typed, Statically-Checked, Concurrent Language. To appear.
[21] E. Schmidt. Controlling Large Software Development in a Distributed Environment, PhD Thesis, U.C. Berkeley 1982; also available as Xerox PARC Report CSL-82-7, 1982.
[22] L. Stewart, D. Swinehart, and S. Ornstein. ``Adding Voice to an Office Computer Network,'' Proc. of GlobeCom 83, IEEE Communications Society Conference. Nov 83.
[23] R. Sweet. The Mesa Programming Environment, to appear.
[24] W. Teitelman. ``A Tour Through Cedar,'' IEEE Software, April 1984.
[25] W. Teitelman and L. Masinter. ``The Interlisp Programming Environment,'' Computer 14, 4, 1981, 2533.
[26] C. Thacker, E McCreight, B. Lampson, R. Sproull, and D. Boggs. ``Alto: a Personal Computer,'' Computer Structures: Readings and Examples (Sieworeck, Bell, and Newell, eds.), 1979.
[27] Authors. ``A paper describing a VM system like Cedar's''.
[28] Lampson and Sproull. ``Alto Architecture''.
[29] Boggs et al. ``Pup papers''.
[30] Authors. ``Something that describes UNIX pipes''.
[31] Authors. ``Something that describes UNIX shell''.