
<<Part1.tioga>>
<<Swinehart, April 10, 1985 0:52:24 am PST>>
<<PolleZ, April 8, 1985 2:08:35 pm PST>>
<<Bob Hagmann April 4, 1985 7:50:39 am PST>>
The Structure of Cedar
1. Introduction
Cedar achieves:
increased convenience through automatic storage management
increased reliability through definition and use of the Cedar Safe Subset
increased flexibility through delayed type binding (limited polymorphism)
increased experimental ease and robustness through carefully layered abstractions
2. Cedar Overview
The present Cedar organization is the result of careful planning and of applying lessons learned from several earlier 
implementations; Figure 1 summarizes its overall structure, as a set of major layers or divisions each comprising a set of layered 
components.  Each component is built upon abstractions supplied by components at lower layers in the structure. << caption of 
figure 1(repeat some of it here?): not everything, block sizes not related to component sizes>><<possibly move this paragraph into 
introduction>>
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 description of the important features of the Cedar language.  It then presents an overview of the four 
Cedar divisions (from bottom to top in Figure 1).  
2.1 The Cedar Language
The Cedar programming language, a descendant of Mesa [8, 13, 16, 40], is a strongly-typed, compiler-oriented language in the Pascal 
family.  Mesa added facilities for modularization and separate compilation (with full type-checking across module boundaries), 
processes and monitors, exception handling, and first-class procedure variables.  Cedar extensions retain full type-checking while 
providing automatic storage management (via reference counting and garbage collection) and facilities for delaying the binding of 
type information until runtime.  In addition, Cedar provides immutable reference-counted strings, as well as LISP-like lists and 
atoms.  We begin with a reminder of some important characteristics that Cedar shares with Mesa, and then we discuss the facilities 
unique to Cedar.
Cedar features inherited from Mesa
A Cedar program typically consists of multiple separately-compiled text files or modules.  There are two kinds of modules: 
definitions and program modules.  Definitions modules describe a set of types, procedures, and variables that together specify a 
related set of functions or a data abstraction.  Definitions modules are compiled into symbol tables that are used to enforce 
inter-module type checking, both at compile time and when modules are bound together to form a program.  Program modules contain 
actual data declarations and executable statements.  A program module that defines a public item (an implementation module) exports 
it to a definitions module.  Other program modules that access the item (client modules) must import it from the definitions 
module.  
The configuration is another concept inherited from Mesa; it is a separate specification of how a set of modules should be combined 
to form a program.  The import list of each component in a configuration must be satisfied by the interfaces exported from other 
included components, or by a list of interfaces imported by the configuration itself.  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.
Cedar Extensions
The extensions that distinguish the Cedar language from Mesa provide automatic deallocation of dynamic storage (garbage 
collection), delayed type binding via generic pointers, and a runtime type mechanism.
Automatic storage deallocation.  Mesa's pointers to explicitly allocated and deallocated storage are subject to two classical 
problems: the dangling reference problem, in which a pointer to an object is used after the object has been deallocated, and the 
storage leak problem, in which an object becomes inaccessible without being deallocated for re-use.  Avoiding these and related 
problems occupied a large fraction of design and debugging time for many Mesa programmers.  In contrast, the possible benefits of 
automatic storage deallocation could be seen in the Lisp and Smalltalk environments: experimental programs were significantly 
easier to produce, and those systems also achieved a high degree of memory protection for programs sharing the same address space.  
Providing automatic storage deallocation was thus a major goal of the Cedar project.
However, to permit critical system code such as schedulers to be written in Mesa, the Mesa language includes ways to disable 
type-checking of an expression.  Such usage posed a real threat to the correct operation of a garbage collector.  The Cedar 
language extensions described below, plus a carefully-selected subset of the original Mesa language, form the safe subset of Cedar. 
 It has been formally demonstrated that even erroneous programs written in the safe subset cannot destroy the integrity of the 
memory allocation structures [18].  The more dangerous unsafe features 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 provides ample warning to the 
programmer that additional diligence extra care is required.
References, a new class of pointer data types analogous to Pascal's or Mesa's POINTER types, provide the means for safe program 
access to system-collectible storage.  A reference variable, called a REF, is declared to hold a reference to (that is, the address 
of) a collectible object of a specified data type.  To ensure that a newly-created REF cannot be used to assign through, trace, or 
deallocate non-existent objects, the system automatically initializes REFs to NIL.  The operator NEW allocates a new collectible 
object of a specified type, with optional initialization, and returns a reference to the new object.  References may be freely 
replicated and discarded, by assignment or by procedure parameter binding; the system releases a region of collectible storage only 
when no valid references to it remain.  For example, the declaration
    ri: REF INT;
declares a new variable ri to hold references to 32-bit integer values, while the statement
    ri _ NEW[INT _ 17];
allocates a new collectible object of type INT, initializes its value to 17, and stores a reference to the new object in ri.
In accordance with its philosophy of extensive compile-time checking, the Cedar compiler verifies the programmer's adherence to the 
restrictions of the safe subset.  Program regions are specified by the programmer to be one of CHECKED, TRUSTED, and UNCHECKED.  
Within CHECKED regions (the system default) only constructs in the safe subset are permitted; as a result, code in a CHECKED region 
can never be the cause of a memory smash.  Use of unsafe features is allowed in TRUSTED and UNCHECKED regions.  Within TRUSTED 
regions, the programmer is responsible for verifying that their use does not represent a safety violation.  Because a TRUSTED 
procedure is considered to provide a safe interface, a CHECKED region may call a TRUSTED procedure; it may not call an UNCHECKED 
procedure.
Unsafe language constructs include LOOPHOLEs yielding any REF-containing type, the original Mesa POINTERs, and address arithmetic.  
Furthermore, assignments to REF-containing variant records are not permitted to change the tag of the record.  Because the system 
deallocates procedure activation records when the procedure returns (i.e., there are no retained frames), procedures must not leave 
accessible REFs to their local variables when they return.  In addition, local PROCEDURE and SIGNAL values cannot be assigned to 
collectible storage or to a module's global storage.  The compiler also checks for conditions unrelated to pointers that could 
cause illegal memory accesses, including out-of-range assignments to numeric variables and array index bounds violations.
Delayed type binding.  Compile-time type specification, otherwise known as strong typing, can catch many common programming errors 
at compile-time and also allows the compiler to produce efficient code.  However, delaying type binding until runtime can provide 
important program flexibility.  For example, programming tools such as debuggers must be able to manipulate objects of any type.  
The original Mesa language offers very limited capabilities for delaying type binding: the choice among predeclared alternatives of 
a variant record may be made at runtime, and the lengths of sequences and descriptor-based strings and arrays may be specified at 
runtime.  Additional type flexibility in Mesa can only be achieved through use of the unsafe type escape mechanism LOOPHOLE.  Cedar 
extensions to Mesa to provide delayed type binding safely include a universal reference type and a runtime type system.
Note that the registration mechanism enabled by Cedar's ability to assign procedure values to variables discussed in Donahue's 
paper [ref] provides a form of delayed binding for procedure implementations.
Although Cedar does not permit a static variable to take on values of different types, it does provide a universal reference type, 
REF ANY.  A variable of type REF ANY can take on (through assignment or parameter passing) a value of type REF T for any type T.  
However, the actual type of the referenced object must be verified at runtime before the object can be examined or modified.  The 
runtime form NARROW[x,T] is defined to return x if the actual type of the object x is equal to the type T; otherwise it raises a 
runtime type error.
A special form of SELECT statement (similar to Pascal's case statement) has been defined to ease use of REF ANY variables (also 
variant records!):
    WITH v SELECT FROM
    v1: T1 => statements assuming type T1
    v2: T2 => statements assuming type T2
    ...
    vn: Tn => statements assuming type Tn
    ENDCASE => statements assuming type T
In addition to universal reference variables, Cedar also has universal procedure types.  Procedures can be declared to take values 
of type ANY as parameters, and/or return values of type ANY as results.  Universal procedure values must be narrowed analogously to 
universal reference types before use.
The provision of universal reference types allows procedures to manipulate objects of prearranged varying types, but does not 
permit procedures to examine or modify objects of completely unspecified type.  To fulfill this need, Cedar also provides library 
functions to manipulate runtime representations of types and runtime program structures, such as procedure linkages and process 
queues.  The current implementation of these functions are too slow to be a real substitute for full polymorphism in the language, 
but they do allow debuggers and other programs to handle variables of any type.  The runtime type system stores a hashed 
representation of the type of each collectible object with the object, allowing fast runtime type checking.  (Note that this 
information is also needed by the garbage collector.)  The types of static variables are determined by examining the 
compiler-generated symbol tables, allowing compact procedure activation records.
Finally, several other flexible data types have been introduced 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.
2.2 The Cedar Machine
All Cedar programming is done using the Cedar language; there are no assembly language routines.  The machine hardware, microcode, 
and low-level runtime support combine to form a virtual machine well-suited to the efficient execution of Cedar programs.  This 
section describes the components of this virtual machine.
Hardware: The Cedar programming environment runs on the family of Xerox Scientific Workstations, which includes the Xerox 1132 
(Dorado) and the Xerox 1108 (Dandelion).  The Dorado [11] is a high-performance personal workstation with 16-bit words, a cached 
virtual memory with a large virtual address space (24 bits, word-addressed), and up to 32 megabytes of physical storage (typically 
two to eight megabytes).  The pipelined processor has a 60 ns cycle time per microinstruction; its writeable microstore allows 
customized instruction sets for different languages and environments.  Input/output devices include a large high-resolution 
bitmapped black-and-white display, a keyboard, a mouse pointing device, and an Ethernet interface.  An additional color display is 
optional.
Cedar workstations operate in the Xerox Research Internet environment that includes database and file servers, shared printers, 
name authentication servers, and distributed electronic mail services [2, 33, 29].
Microcode: The Cedar microcode implements an extension of the Mesa machine architecture [10], which was designed for efficient 
execution of languages in the Pascal family.  Two factors combine to produce exceptionally compact representations of programs: a 
stack machine architecture, which allows zero-address instructions, and variable length byte-coded instructions, whose encodings 
are based upon an analysis of static instruction frequencies in existing compiled Mesa programs [32].  A compact program 
representation not only saves storage space, but it also contributes to faster execution, largely due to increased locality and 
hence fewer cache misses and page faults.  The architecture also supports arbitrary control transfer disciplines (such as 
coroutines): activation records are allocated from a heap rather than a stack.  In addition, the architecture allows for 
simultaneous execution of up to one thousand processes.  The microcode 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 invalid storage references.
Mesa Runtime Support: Low-level routines and data structure definitions provide a Cedar language interface to the microcoded 
processor architecture, supporting procedure linkage, process switching, and runtime error handling.  Although this component is 
not written in the safe language, its interfaces are asserted to be safe.
2.3 The Nucleus
The Cedar Nucleus contains the basic operating system facilities needed for memory management, process management, file system 
management, and communications with the user and the outside world. This section describes the major components of the Nucleus.
Device drivers: 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 microcode to include the 
peripherals as well.  For example, Cedar provides an interface abstractly defining the behavior of disk drives.  The Disk 
component, described below, can be programmed in terms of this interface, without detailed knowledge of the peculiarities of each 
type of drive that the underlying implementations must support.
Disk: The Disk component provides a uniform interface to the attached disk drives.  It provides low-level facilities for 
investigating the state and configuration of each drive, and for performing page-level input/output operations between specified 
disk addresses and virtual memory locations.  Clients of the Disk component must ensure that virtual memory buffers have physical 
memory allocated to them.
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.  Cedar represents virtual memory as a single backing 
file, employing a resident page map.  VM permits higher-level clients to ensure temporarily that a region of virtual memory has 
physical memory allocated to it, so that components at levels lower than VM can deal with memory through virtual addresses without 
incurring page faults.
File input/output must be accomplished by explicit operations, rather than as VM mapping actions.  The performance improvements, 
both for code swapping and for file 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 and the VM 
implementation itself need to deal with physical memory addresses.  Thus the preponderance of the Cedar system can operate in the 
virtual memory environment.
Safe Storage:  The safe storage extensions to the Cedar language are supported by the runtime type system described in section 2.1, 
a storage allocator (implementing the NEW operator), and a combination of garbage collection techniques derived from earlier 
designs by Deutsch and Bobrow [5].  A full description of the revised algorithms appears in Rovner's recent paper [20].
An incremental garbage collector runs at frequent intervals, triggered by specified elapsed-time or memory utilization criteria.  
It operates in a background process, so that other processes can run concurrently.  The incremental collector is able to reclaim 
most of the storage objects that are no longer referenced, using information obtained from reference counts and examination of 
current activation records.  Its algorithms do not permit compaction or relocation of allocated objects.
However, the incremental collector cannot detect cyclic data structures, such as those generated by two-way linked lists or certain 
queue implementations.  Programs can manually break links when they determine that a data structure is no longer needed.  In 
addition, a conventional, preemptive trace-and-sweep garbage collection algorithm has been included to allow such structures to be 
reclaimed.  The trace-and-sweep collector reclaims virtually all unreferenced storage, but monopolizes the machine for twenty 
seconds to several minutes in the process.   Servers or other programs that need to remain available for long periods of time 
without danger of storage leakage can invoke it directly.  Users may also run the trace-and-sweep collector manually.
A package that creates objects of a given type can also specify finalization code to be executed when an object of that type 
becomes inaccessible outside the package.  The finalization code is free to examine the object and perform any final operations 
such as removing the object from a cache, releasing a virtual memory buffer associated with the object, or breaking the circularity 
of a data structure to permit reclamation by the incremental collector.
File: The local file system underlying Cedar is straightforward.  It manages the configuration of one or more physical disk 
volumes, and their subdivision into logical volumes.  Within logical volumes, it manages the page-level allocation, deletion, 
reading, and writing of disk files.  The file structuring methods borrow heavily from earlier Xerox systems [28, 19].  In 
particular, 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 that applications can use to locate the files later.  Different applications may 
choose their own directory organizations for their files, but most choose to use the standard directory package.
FS: The Cedar workstation file management and directory package (FS) supports the appearance of a uniform file naming space, 
spanning the user's local disk and the set of shared file servers available through the attached communications network.  File 
names can represent two kinds of files: local files, where the only copy of the file resides on the workstation's disk; and 
attached files, where the file name is symbolic path name to a remote file.  Read-only copies of remote files are retrieved and 
cached as needed on the local disk.  FS provides its facilities by maintaining two logical directories describing the contents of 
the local disk: the local file name directory and the remote file cache directory.
The local file name directory provides a local, hierarchical name space for files.  Arbitrary nested directory structures can be 
expressed as subdirectories of the single root directory.  Entries in the local name directory may be either local files or 
attached files.  Thus, a local environment that describes a complete system or set of related tools can be created out of local and 
remote files.
The remote file cache directory organizes the set of remote files for which local copies exist.  Files may be referenced via local 
file name directory attachments or by using a full symbolic path name.  Depending on what the user is doing, often only a small 
subset of the files indicated by attachments will actually be cached.  Disk space is managed automatically by flushing 
least-recently-used remote file copies from the cache when additional space is needed.  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.  Therefore the file must first be written 
locally, entering its name 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 an attachment to the remote file.
IO: The IO interface defines generic procedures for creating and using streams of characters or words, including useful input 
scanning and output formatting routines.  The Cedar IO package contains over a dozen specific implementations of streams 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 implement asynchronous terminal emulation, a file transfer 
protocol, 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).  Otherwise ordinary 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 routine 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 reconstruct the parameters, 
complete the linkage to the actual procedure implementations, and compose the results into packets.  The Cedar RPC package, 
described by Birrell and Nelson in [3], performs two functions: it automatically constructs both sets of stub routines from the 
interface definitions, and it 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.
To date, we have produced three major Cedar systems that use RPC for all their communications:  a transaction-based file server, an 
experimental telephone and recorded-voice service, and a server that coordinates the assignment of computing tasks to idle 
processors.  All three are described further in section 2.5.  Furthermore, implementations of RPC for other languages and 
programming environments are beginning to extend the range of services that Cedar applications can provide or use.  A version of 
RPC has been implemented in Interlisp-D so that network clients can use an Interlisp-based dictionary service.  A version written 
for the Intel 8088 provides the link between the microcomputers used in the telephone project and a telephone control server.  
There is an RPC implementation for the Xerox Development Environment, and an implementation is planned for Smalltalk-80.
Terminal: Most Cedar applications are content with the higher-level display-management and user input facilities supplied by 
Viewers and TIP (section 2.4).  However, more radical applications may need to use the display screen or input devices in a 
conflicting way  to try out a new window package, for example.  The Terminal interface provides 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 
while 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 a desired system configuration for rapid restarts.
2.4 Life Support
The Life Support division provides standard user interaction facilities such as a screen manager, a text editor, command and 
expression interpreters, and program development and management tools.  Many of the Life Support components are quite large, 
providing functions directly to Cedar users or applications programmers; in this sense they more resemble user applications or 
packages than operating system components.  They are given a division of their own because their functions are vital to providing a 
complete working environment for users, and because the standard Cedar initialization procedure automatically includes them.  
Components above the Life Support level are selected and included in the system by individual users.
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 more 
complete discussion of these techniques appears in section $x.y.
Useful Packages: During the implementation of Cedar, many generally useful packages have been produced.  Examples include packages 
for sorting arbitrary values, for maintaining symbol tables, and for managing queues of user-invoked commands.  These packages can 
be thought of as extensions of the basic "Cedar machine."  As their numbers increase, they will make programming in Cedar 
increasingly convenient.
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 works better than direct sampling of the 
hardware by individual applications, because the Inscript package collects and timestamps the events using clocked interrupts; it 
is therefore less likely that events will be missed or that confusion about the timing of events will occur.  Each application must 
determine which of the input events are intended for it and what their semantics are, ignoring those intended for other 
applications that are sharing the screen.
Although the Inscript package can be used directly, most applications are satisfied to allow users actions to be interpreted by the 
Terminal Input Processor, or TIP.  TIP interprets Inscript input events based on easy-to-write specifications called TIP tables.  
For each event or event sequence (such as clicking a mouse button twice in succession or depressing a key for a long time), a TIP 
table entry specifies a procedure to carry out the semantics of the event.  Standard rules determine the choice of which TIP table 
to invoke for each event, as well as which screen region to include as a parameter to the procedure.
A high-priority process called the notifier interprets input events according to the current set of TIP tables.  A typical TIP 
procedure creates a new process to carry out the desired action, then returns immediately so that the notifier can react to the 
next event.  In this way, the user can initiate or control many concurrent applications; furthermore, programs can be written in a 
way that does not preempt the user's ability to choose from moment to moment which application to talk to.
Default TIP tables define standard behavior for the basic Cedar user interfaces.  Specialized TIP tables support the special input 
needs of advanced applications (such as drawing programs).  User-specified TIP tables give the user some ability to custom-tailor 
any existing application.
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 is a step in this direction.  Its facilities are all ultimately 
based on the symbol tables and program graphs that the compiler, binder, and program loaders produce.  Its primary use at present 
is in support of ordinary Cedar applications that serve as interactive interpreters, debugging tools, and other tools for 
presenting program data in a form sensible to users.  Rovner gives a more complete treatment of the Cedar Abstract Machine in [20].
The Abstract Machine implementation is based on the following concepts:
    1. Runtime types.  The unique Type identifiers that label allocated objects are also used by all the abstract machine interfaces as 
    runtime type values.
    2. Multiple virtual memory access.  The WorldVM interface provides access to the virtual memory of a local, worldswap (memory image 
    saved on disk) or remote (memory accessed over the Ethernet) Cedar system.  All Abstract Machine facilities are available 
    through WorldVM for any of these three modes of operation.
    3. Program control.  The AMEvents interface provides a set of low-level operations for setting breakpoints and for tracing program 
    flow.
    4. Type information.  The AMTypes interface provides procedural access to the names and structure of data types, including a 
    complete set of operations for analyzing the internal structure of composite types.
    5. Value manipulation.  Other AMTypes procedures permit the examination and modification of runtime values.  The association 
    between the referents of REF variables and their Type identifiers can be made safely and automatically by the system; for other 
    values, the associations are based on TRUSTED program assertions.  These operations support 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.
    6. Program and process structure information.  The AMModel interface allows a similar analysis for program structure: the makeup of 
    a procedures in terms of their embedded blocks, of program modules in terms of their procedures, and of configurations in terms 
    of their program modules and its subconfigurations.  A description of the loaded configurations and their associated global 
    frames within a running Cedar system is also available through AMModel.  Using the AMProcess interface, one can enumerate the 
    active processes, suspend or resume the operation of selected processes, and locate the top activation record for a given 
    process (for use perhaps in printing a stack trace for the process).  
Cedar Imager: Cedar runs on powerful personal workstations that rely on the power and flexibility of high-resolution bitmapped 
display terminals.  In earlier Xerox systems, system support for interactive graphics was limited to low-level bitmap operations, 
such as the RasterOp (BitBlt) function described by Newman and Sproull in [17].  While it is possible in Cedar to manipulate 
bitmaps directly, most applications instead use the Cedar Imager package, which provides support for the presentation of such 
graphical images 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: 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.  The 
Viewers package manages the allocation of viewers to the available real estate, "painting" the contents of each viewer based on 
client-supplied specifications.  Similarly, it allocates and paints iconic (small) versions of "closed" viewers.  It also provides 
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.  (Other widely-used user interface facilities, such as menu buttons, are also implemented by 
packages in Life Support.)
In actuality, there is a hierarchy of viewers.  Within the top-level viewers we have been discussing here, one may nest subviewers 
 perhaps to provide a subwindow whose contents must be scrolled separately, a subwindow whose contents is provided by some other 
application, or an area which must otherwise be managed differently from other information displayed in the viewer.  Subviewers may 
be quite small.  For example, the menu buttons that appear in each top-level viewer are represented as small subviewers.
Top-level Cedar viewers never overlap, but instead reside within two columns, sharing the available height with other viewers 
assigned to the same column.  (If an auxiliary color display is available, a third column of viewers can appear on it.)  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.  This tiled design 
was enforced by its designers as an experiment in minimizing user window scaling and positioning commands; the underlying graphics 
facilities 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.
Tioga: Tioga is the tree-structured text editor used to create Cedar programs and formatted documents.  Tioga is a galley editor 
(it does not support page makeup) that can manage tree-structured text documents.  Nodes (corresponding approximately to 
paragraphs) and text content can be decorated with user-specified styles and font information that control their displayed and/or 
printed appearance. 
Tioga displays its files in text viewers, making extensive use of TIP tables to simplify the specification of the user interface.  
Tioga implements a simple postfix language in which its operations are expressed.  This provides a common approach for the meanings 
of the interactive editing operations, the definitions of command abbreviations, and other prerecorded sequences of editing 
actions. 
Apart from its value for editing 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.
Although Tioga does not understand Cedar syntax, we find that using Tioga as a program editor has several important benefits.  
First, viewing programs as formatted documents with common stylistic conventions makes them easier to read and share.  Furthermore, 
Tioga's flexible search commands, combined with a small number of special-purpose connections to the Cedar Abstract Machine, allow 
it to approach the usefulness of the special-purpose program development tools found in other current programming environments:
    �    Simple pattern-matching allows Tioga's abbreviation expansion command to construct easily-filled-in templates for language 
    constructs and procedure call parameters.  Tioga's node structure and its level hierarchy provide holophrasting (suppression of 
    detail for a larger contextual view [39]) and the ability to manipulate an entire construct as a unit.  These capabilities 
    provide many of the advantages of modern syntax-directed editors [35, 36, 37].
    �    Tioga also performs the use-to-definition portion of the Masterscope functions in Interlisp [25].   A selection of the form 
    interface.item may be used to request a new viewer displaying the file that defines (implements) the item, scrolled to the 
    item's definition.  (If an implementation of interface has been loaded, AMModel functions are used to locate the implemention 
    file name; otherwise, Tioga makes a guess based on program naming conventions.) Unfortunately, mapping from an item's 
    definition to its uses is beyond Tioga's capabilities; it would require the capabilitis of Cedar system modelling, a 
    partially-implemented extension to the DF Package (see section 3.1).
    �    The debugger for the AT&T Blit Workstation [38] constructs menus of currently-visible procedure, variable, and field names to 
    ease user input.  <<In Cedar, Tioga's client interface, combined with the ability to copy text freely between viewers, permit 
    the Cedar debugger to show a breakpoint or error location as a highlighted region in a source viewer; the user can thus see 
    legal procedure and variable names in context and copy desired names to the debugger area.>>

<<cite Rick's [1] and Warrent's papers and Donahue's?>>
See Teitelman's Cedar user interface paper [24] for an expanded discussion. 
Compiler, Binder, and 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.
Command Tool: Cedar Life Support includes a conventional command interpreter in the form of a text viewer into which the user types 
commands and the system responds with results.  The command syntax, an amalgam derived both from UNIX [31] and from 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, and the like).  As applications are started, they 
may register additional commands with the command tool, extending the set of available operations.  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 several 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.  Debugging can be performed in any address space that the WorldVM interface can 
reach (local, worldswap, or remote Cedar systems).
Version Management: Even with conventional timesharing systems, existing file directories do not provide adequate support for 
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 become 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 Package.  The DF Package operates on a DF file, 
a text file containing the (unique) full names of the file versions comprising some package or program.  Like programs, DF files 
have imports, exports and implementations.  Imports define the modules needed by a package that are located in a different DF file, 
exports specify the modules that are public, and the implementation is a list of files comprising the package itself.  Packages are 
interrelated by the matching of the exports and imports of their DF files.
To modify a package, the DF Package is used to make local names in a subdirectory on the workstation link to (see FS above) the 
names specified in the DF file.  Parts of the package may be edited, created or deleted  the latter two involve edits to the DF 
file.  When the package is consistent, the DF Package is used to discover changed or new files, and to cause FS to copy them to a 
file server, and to update the DF file.
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 Package has also been adapted for use in XDE [23].
2.5 Applications
By now it should 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.  This section describes many of the applications that 
have been produced to date in Cedar.
Cedar includes a number of components to support database applications.  Alpine is a transaction-based network file service, 
written in Cedar, and running on a dedicated Dorado [33].  Cypress is a relational database package that runs in a user's 
workstation but stores its database on Alpine servers [4].  Walnut is an electronic mail system that operates in conjunction with 
the Grapevine message transport mechanism [2], 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 [1].  A 
server and individual workstation programs have been developed to support the operation of an experimental telephone and voice 
recording system (the Etherphone project) that uses Ethernet communications to transmit voice [22].  Hardware designers have 
produced a suite of VLSI design, simulation, and analysis tools in Cedar [14].  The Cedar Spy is a decedent of [34] that does CPU, 
allocation or page fault performance monitoring.  Celtics counts the number of times a statement is executed.  Whiteboard allows 
use of the display screen similar to a whiteboard: text regions and icons can be displayed and browsed.  Griffin is an interactive 
illustrator for creating full-page color illustrations composed of lines, curves, filled areas, and captions.  Other projects of 
similar scope and magnitude are underway. <mention compute server?>
<These descriptions should probably be lengthened a bit.
<This has been more than the tip of the iceberg, but there's a lot more we haven't talked about.  Include a few statistics: number 
of modules, lines of code, kilopages of file storage>
3. Part 2 
The Cedar System was conceived as a development project aimed at providing an operating system, programming environment, and 
application execution environment for a new generation of personal computers (Dorados).  Although it was clear that some unsolved 
problems would be addressed, the intent was to combine well-understood methods and technologies in one system.  Extensive 
preliminary discussions, outlined in an early Cedar requirements report [6] and further discussed in [24], produced a set of design 
goals for Cedar, many of which have been achieved.  Although not all of them are relevant to the topics of this paper, and although 
some of the important attributes of Cedar did not arise directly from them, we summarize the higher-priority objectives here to 
establish the context in which the system was developed.
    �    Automatic management for storage objects  garbage collection, reference counting.
    �    Large virtual address space (
    �    Statically checked type system (inherited directly from Mesa).
    �    Abstraction mechanisms; explicit notion of interface (inherited directly from Mesa).
    �    Adequate runtime efficiency.
    �    Programs as data (includes the need for a run-time type system, and generic (REF ANY) pointers, but includes many other 
    requirements as well that Cedar has not yet provided).
    �    Fast turnaround for minor program changes (less than 5 seconds).
    �    Support for the programming styles of Mesa, Lisp, and Smalltalk, in order to accommodate programmers familiar with any of 
    these environments.
    �    Supports both large and small (one-person) programming projects well.
Cedar, as an operating system and as a programming environment, is the direct descendant of earlier Xerox systems.  The progression 
began with a simple system for the Alto, using the BCPL language and basing its structure on the notion of an open architecture 
[28].  When the Mesa language was developed for the Alto, its implementors also produced a faithful rendering of the Alto/BCPL 
system components, without extending its concepts.   The next major development was the Mesa-based Pilot operating system [19] and 
its associated Tajo programming environment [],  designed for use with a second generation of workstations that included memory 
mapping and larger physical memories.
Early versions of Cedar were built on a Pilot base, adopting a number of important ideas from more traditionally interactive 
language systems, notably Interlisp and Smalltalk, in order to achieve some of the objectives listed above.  Later revisions have 
benefited not only from observations of shortcomings in the first attempts, but also from approaches found in the Xerox Development 
Environment (XDE), which was being developed in parallel to Cedar.
Cedar has also borrowed from more conventional current operating systems, among them UNIX {TM and all that}.  But there are also 
some significant differences, leading to markedly different methods for achieving some desirable properties.  In fact, neither 
Cedar nor any of the systems with which we can most usefully compare it (Interlisp, Smalltalk, UNIX) achieve all these properties 
equally well.
In Part I we described the major Components of Cedar, choosing an order that progressed from the low-level "virtual machine" 
capabilities to the more important user applications.  In Part II, we concentrate on the overall structure of the system; what it 
is, why it is that way, and what facilities have been provided in the language and in the environment to support the development of 
programs.  We will address this issue through a discussion of the following topics:
    �    Cedar Architecture: The approach that was used to structure the components of Cedar; language attributes, memory management 
    components, and structuring philosophies that were used to achieve the system objectives.
    �    Structural Choices in Cedar:  A discussion of the careful design choices that led to the ordering of components within Cedar.
    �    Comparisons: Areas of similarity and difference between the architectures of Cedar and selected other programming 
    environments, identifying valuable features that should be considered for inclusion in future Cedar systems.
    �    Case Studies:  A few brief examples of the application of Cedar to program development projects.
Cedar Architecture
Cedar as an Open system
Much of the design philosophy of Cedar can be traced back to the BCPL-based system designed in the mid-1970's for the Alto personal 
computer.  The designers of the Alto/BCPL system called it an open system, contrasting it with conventional multi-user operating 
systems, which they termed closed [28].
 A closed system, as defined in the Alto/BCPL report, has hardware memory protection, generally in the form of hardware support for 
separate address spaces for the operating system routines and for each user application.   The operating system provides user 
programs with special methods for invoking a fixed set of operations.  The routines used to provide these operations, unless they 
are also explicitly exported as system operations, are not available to client programs.
The Cedar open operating system is essentially a collection of program modules (containing sets of related procedures) sharing the 
machine's single address space.  The important aspects of this open approach are:
    �    The operating system modules are written in Cedar (or at least designed with the same calling sequences), and their clients 
    can call their procedures in the ordinary way.
    There is thus no sharp boundary between client programs and system routines.
    �    The components of Cedar are carefully arranged into layers.  Higher-level layers (Life Support and Applications) are built on 
    the capabilities of the lower-level ones (the Cedar Machine and the Nucleus). 
    �    The components in one layer may only call procedures located in the same or lower layers.  This restriction is enforced only 
    by convention, although violations often result in system errors. (In the Alto system, it was possible to free for other uses 
    the memory occupied by unneeded higher-level layers; inadvertant upward calls had disastrous results.  In Cedar, problems can 
    occur due to the order in which components are loaded or initialized.)
    �    This structure differs from the virtual machine concept, where each level of a system is implemented only in terms of the 
    abstractions provided by the next-lower one.  The difference is that in open systems such as Cedar the lower-level modules 
    remain directly available to clients at all higher levels.  An application can generally choose to use facilities at any level 
    or replace them with custom-built ones fashioned in terms of lower-level components.
The influence of Mesa
It proved possible to produce a BCPL-based open system for the Alto, but the resulting system had many shortcomings.  BCPL is a 
typeless language that provides many opportunities for errors that the type systems of Mesa (and thus Cedar) would prevent.  The 
strong type-checking of Mesa has demonstrably improved the reliability and the ease of development of programs produced for Xerox 
workstations [8].
The interface concept introduced by Mesa is very useful in describing and delimiting the capabilities supplied by a particular 
system component.  Further, the ability to combine the modules that export a given interface into a configuration makes it possible 
to identify within the language the implementation of the associated component.  Configurations provide the means for identifying 
the public interfaces to be made available to all higher layers in the system, but they also make it possible to confine the 
implementations of some sub-components to use within a publicly-available component.
 Sometimes it is desirable to use an implementation normally found in lower-levels of the Cedar structure, but to bind it in such a 
way that it uses private versions of the interfaces that it imports.  This sort of thing was possible in the earlier Alto/BCPL 
system, but not straightforward; if nothing else, various subterfuges were required to deal with multiply-defined symbols and to 
produce the proper bindings.  In Cedar, the configuration language inherited from Mesa provides direct support for this kind of 
flexible and controlled binding.  As we will see in section $x.y, configurations can even be used to develop new components and to 
debug them in the same environment, using the facilities of their predecessors.
It would be wrong to say that Mesa's interfaces and configurations provide a complete descriptive tool for the structure of Cedar.  
It is possible to specify, through an export list, which of the interfaces available within a component are private to the 
component and which are public.  This would appear to be an adequate tool for enforcing the restriction against calls from 
lower-level layers to higher-level ones, but in practice Cedar does not use configurations in that way; the resulting 
multiply-nested configurations would be too clumsy to produce and maintain.   The major layers of Cedar all reside in the 
"top-level" configuration simulated by the system as programs are loaded.  The layered structure is, as we have mentioned, enforced 
largely by convention.  The system modelling language of Lampson and Schmidt [12] is a more powerful specification tool for 
defining system structure than the existing configuration language, but it would need to be extended in order to make the layered 
structure and its corresponding constraints explicit.  This is a topic for additional research.
The influence of Safe Storage
The major structural ideas in Cedar originated in the BCPL system for the Alto.   Strong-typing, explicit interfaces, and the 
configuration facilities of Mesa added sufficient control and descriptive ability for an open system to be comprehensible and 
readily usable by careful programmers possessed of only ordinary training and abilities.
Cedar's primary contribution to the evolution of this family of open systems is safe storage.  Neither the BCPL system nor the 
Mesa-based open systems are immune from catastrophic damage due to invalid memory references  the kinds of unrecoverable mishaps 
that traditional "closed" systems were designed to protect against.  Where traditional systems confine such damage to the process 
or job that causes it, Cedar's aim is to prevent the damage entirely, through its combination of compile-time and run-time tests  
a technique that is known to work well in Interlisp and Smalltalk implementations for the same class of machines.
Earlier systems were also susceptible to so-called storage leaks: the slow erosion of available memory due to the occasional 
failure to free up a data object whose usefulness had expired.  Storage leaks are as much an impediment to robust implementations 
as are invalid memory references.  Storage leaks, while infrequent, can occur in the safe subset of Cedar, between invocations of 
the Trace-and-Sweep garbage collector (which can reclaim circular structures).
Many applications have now been developed using only the safe subset of the Cedar language.  These programs have required far less 
diligence and attention to the details of memory management than their earlier counterparts did.  In addition to the direct 
protection benefits of safe storage, we have been pleased by some additional flexibilities that automatic storage management 
permits.   In systems that require explicit release of no-longer-needed objects, there is always an ownership issue to address when 
passing references to objects as procedure parameters.  For example, a routine that prints text strings might be supplied either 
with a fixed value, whose storage should not be released since it will be used repeatedly, or with a constructed value whose 
lifetime need not extend beyond the completion of the printing routine.  The client must either surrounding the call with 
allocation-management statements, or must somehow be able to charge the printing routine with the responsibility for managing the 
parameter's storage; either method is clumsy.  In other Mesa-based systems, this question of ownership has resulted in severe 
procedural constraints in the design and permitted use of operating system features.
In Cedar, we have found it convenient to define system routines that accept reference values (sometimes of specified type, 
sometimes REF ANY) without any concern for the eventual disposition of their storage.   Conversely, it is easy for system routines 
to manufacture new reference values (or optionally to recycle old ones) and return them to clients.  In contrast, 
explicitly-managed systems often require clients to supply the storage for return values, or they find it necessary to copy client 
values (e.g., data blocks destined for output)  [LFCabrera buffering horror stories?], especially when multiple address-spaces are 
involved.
It is not immediately obvious, but safe storage also increases the value of "call-back" or "registered" procedures.  One way for a 
high-level client procedure to safely and effectively thwart the policy forbidding direct upward calls is to supply a procedure 
value as the parameter to a lower-level service {help  want to use words like client, supplied, and service to identify the three 
procedures} procedure.  If the supplied procedure is to be called during the execution of the service procedure, it is known as a 
call-back procedure; its definition may be embedded in the client procedure so that the service procedure can read and alter the 
client's state.   Typically, call-back procedures are supplied by callers of enumeration procedures, which supply successive values 
for consideration in the context of the client.  If the service procedure stores away the supplied procedure for later invocation 
when specified conditions arise, the supplied procedure is known as a registered procedure, which must be a top-level procedure in 
some program module.  A good example of registered procedures are the routines that provide the meaning for user actions as 
specified by TIP tables.  Call-back procedures and registered procedures may be invoked either to obtain information during the 
operation of a lower-level procedure, or to supply information to the higher-level clients.   In either case, since the client 
supplies the procedure, there is a reasonable guarantee that the higher-level component exists and is initialized.  Again, the 
existence of automatically-managed storage provides additional flexibility in the kinds of values that can be exchanged through 
these procedures.  Without safe storage, concern over the lifetime of explicitly-managed storage objects led to restrictions on the 
use of procedure variables in system calls [Does Pilot paper talk about these restrictions? If so, include the citation].  In 
closed systems, difficulties in establishing the proper memory environment generally prohibit the use of either registration or 
call-back procedures. 
3.2 The Layered Structure of Cedar
Cedar is layered quite carefully, based on observations and problems with earlier systems, to optimize several (sometimes 
conflicting) goals.  The structure should be clean, have a hierarchical call structure, be coherent, and have any remaining 
exceptions ostracized and well-marked.  Some programs should be moved to the lowest level possible, but this must be balanced 
against increasing the complexity and size of the lower levels.  Having a program at a low level makes its services more 
universally available.  However, lower level programs are harder to debug and modify, and must be more stable to provide a reliable 
system.
Sometimes the layering requires that a small number of high level procedures be called from a lower level.  The high level program 
at initialization calls the low level program passing a procedure parameter for the desired procedure(s) (procedure registration).  
Non-critical parts of programs can then be divested and placed at a higher level.
Many programs in Cedar have been divided (using an interface) to separate the inner implementation and the higher level tool or 
control software.  We see this both as a complete split between the programs (e.g., File and FS, or Abstract Machine and the Debug 
Tool), and as a subdivision within a program.  By exposing the interface, other clients can be supported and the inner 
implementation can often be moved lower in the layering.  For example, the Alpine File System uses the File Package.
Implementors are encouraged to provide three ways to use a program: via an interface, by a command interpreted by the CommandTool, 
or by the use of a tool.  A tool is a Viewer that provides a user interface to the functions of a program.  Buttons, menus, mouse 
position, mouse key clicks, and type-in are typical methods for acquiring parameters or starting functions.
Some programs occupy interesting places in the layering.  A few of them are described in the following paragraphs.
The only program above the Cedar Machine that does not use Virtual Memory is the Virtual Memory implementation (VM) itself.  By 
reducing the complexity of such modules as device drivers, file system, and safe storage, the software has been easier to build and 
maintain.  VM is so low in the structure that it cannot even find the disk file used to back up memory: when the File Package 
initializes, it calls VM to inform it of the backing file location.  The simple design of VM makes this possible, since file 
directories or even file concepts are not required to get the single backing file VM to work.
The other software that is very low in the layering is Safe Storage.  We view this as a convenience since almost every program can 
then be a client of Safe Storage, and as a way of improving the safety since much of the system can then be written in the safe 
subset of the Cedar language.  Currently, clients include the File System, Loader, Terminal and Communications as well as almost 
all programs above the Nucleus.  The incremental garbage collector is included in Safe Storage, but the trace and sweep garbage 
collector is part of the Life Support level, and is invoked using a registered procedure.  The Nucleus is thus reduced in size and 
complexity.
Cedar has many useful data types.  A few of them are ATOM, ROPE, STREAM (in IO), FILE, and REF ANY.  By making VM and Safe Storage 
as low as possible in the layering, all data types can be freely used in layers above their implementation.  ATOM, ROPE, and REF 
ANY can be used anywhere above Safe Storage.
IO is part of the Nucleus, even though some of its advanced features, such as printing a REF ANY, require the Abstract Machine.  
Much of the Nucleus can then use the normal features of IO to format and scan.  The Abstract Machine registers the needed 
procedures for the advanced features with IO. The IO program was one of the major problems with earlier versions of Cedar: it 
caused awkward compilation dependencies and inelegant program splitting.  By using registration and only a subset of the features 
of IO in the Nucleus, the system is cleaner and easier system to build.
The Abstract Machine is a low level Life Support program that provides a means for making symbolic access to the system as early as 
possible.  These features are used by many high level packages such as the Celtics, CommandTool, Cypress, DebugTool, Interpreter, 
Spy, Tioga, Viewers, and Whiteboard packages.
Graphics, Viewers and Tioga provide much of the framework for screen displaying and editing.  Placing these programs in the Life 
Support level makes their facilities available to all Applications level programs, plus some of the Life Support programs.  The 
Tioga editing paradigm is used throughout screen manipulations by many Applications level programs.  This eases the implementation 
of these programs, and presents to the user a more consistent means of interaction with Cedar.
At the higher levels of Cedar, the layering is not as important.  The main problem at the high level is finding an acceptable 
initialization order for interrelated programs.
There are problems in moving programs to lower positions.  One of these is that the debugging and error handling tools depend upon 
much of the system (e.g., Abstract Machine, FS, File, Safe Storage, Graphics, Viewers and Tioga).  Same world debugging for these 
packages is delicate, and often the world swap or teledebugger must be used when working in this region.
Comparisons
To put Cedar in perspective, we will compare its structure with those of a small number of programming environments that were not 
part of Cedar's direct evolutionary chain, looking at both the similarities and the differences in their designs.  Some of the 
differences are inherent, while others provide insights that could lead to future developments in Cedar.  We will look at the two 
systems from which Cedar has borrowed most heavily: the Xerox implementation of Interlisp-D, and the Smalltalk-80 system.  We also 
include a discussion of UNIX {TM and all that}, a traditional system whose ideas have influenced Cedar significantly.
There are a number of important programming environment attributes that we are not considering in this paper: facilities for 
treating programs as data, for providing fast turn-around for program changes during system development, and other interesting 
user-interface issues.  We are not addressing these attributes in our comparisons, choosing instead to concentrate on structural 
aspects.
Interlisp-D
Interlisp was initially developed as a Lisp dialect designed to operate within the Tenex [] operating system for the DecSystem-10 
family of computers.  Since Interlisp provides a single global name space, and since virtually all of the system except the 
lowest-level primitives and the access to operating system facilities are written in Lisp, the design is inherently an open one.  
However, the input/output facilities and wholesale memory management facilities were limited to whatever the Tenex system provided. 
In recent years, Interlisp has been transported to Xerox personal workstations (Dolphin, Dandelion, and Dorado).  It has been 
enhanced with a powerful display and window management package (based on earlier prototype work using Tenex Interlisp with Altos as 
terminals), reappearing as Interlisp-D.  Interlisp-D would have to be classed as an open system, in the sense that all of the 
components comprising the system are available to client programs.
All Lisp dialects rely centrally on automatic memory management of their list structures; the clear success of Lisp 
garbage-collection methods led us to explore the application of garbage collection to Cedar.  When programs use only the basic 
functional primitives of Lisp, they are inherently safe.  But most implementations, including Interlisp-D, are not fully safe, 
since they include functions that can modify existing list structures in ways that can lead to storage leaks through the production 
of uncollectable circular structures.  To handle concurrent processing, Interlisp-D includes a simple non-preemptive process 
scheduler with no semaphore or monitoring facilities.  Errors in process synchronization cannot interfere with proper memory 
management, but one must exercise care to avoid invalid application-level states.
A running Lisp system has no identifiable component structure or explicit layering, but rather contains a vast collection of 
individual procedures.   Of course, the user documentation does present the system in an orderly fashion, clustering groups of 
related procedures according to their purpose.
Smalltalk-80
Smalltalk systems, beginning with Smalltalk-72 and ending with the present Smalltalk-80, have also evolved towards a greater degree 
of openness.  As with Lisp, the parts of the systems written in Smalltalk are universally available, since Smalltalk operates in a 
global name space.  And like Lisp, the amount of the system written in Smalltalk has increased as the implementation became more 
efficient.  Now virtually any aspect of Smalltalk is available to programmer except a very small kernel.
Smalltalk systems have always required automatic memory management, dealing with allocated objects more complex than those of Lisp. 
 Objects are represented as variable-sized records containing embedded object references.  These implementations provided a partial 
existence-proof for the kind of memory management Cedar needed.
The object-oriented approach exemplified by Smalltalk-80 was also a goal of Cedar, a goal so far only partly met.  The language now 
provides some simple syntax that makes explicit the object-oriented flavor of invoking procedures through variables stored in 
records.  Many Cedar facilities operate in this style, but the construction and management of such objects are the responsibility 
of each programmer.  Moreover, neither the Cedar language nor the system provides any support for the important Smalltalk-80 notion 
of class-inheritance: specific object classes specified as extensions to the specifications of more general ones.  Class 
inheritance is an orthogonal structuring approach to the explicit layering of Cedar components, dealing with the relationships 
between implementations of related object types, rather than the relationships between callers and callees.  Classes and class 
inheritance are important concepts that should be looked at in the context of strongly-typed languages like Cedar.
Although the Smalltalk-80 implementation does not exhibit an explicit layering of components, it does have very powerful means for 
clustering the operations belonging to each component, as collections of operations implemented by a particular class.  In fact, 
the Smalltalk-80 system supports a further organization of operations within a class, encouraging the programmer to group these 
operations into more specifically-defined categories.  This is also an idea that could be used to advantage in Cedar.
UNIX
We have used UNIX as an example of a traditional operating system, which relies on hardware memory protection to partition the code 
and data used by the system for its operation from those of the user processes, and similarly to protect the user processes from 
each other.  This approach has disadvantages which led to the development of open systems like Cedar, but it also has important 
advantages.  To review:
Disadvantages
    �    The clear boundary between the application and the system is apparent in the application programs, usually appearing 
    explicitly as system call of some kind.  Subcomponents of the facilities available as system calls are often not directly 
    available to applications.
    �    Applications that run as parts of an integrated system often benefit from the ability to share common memory.  In particular, 
    the management of the common screen-view within systems like Cedar are heavily dependent on shared memory.  System performance 
    and convenience suffer when applications are forced to take a more arms-length approach to communication.
    �    Changing of the operating system to provide new or different functions is not a as straightforward as it is in Cedar.  
    (However, we should point out that since UNIX sources are generally available and not incomprehensable, it is possible to 
    customize a UNIX system.)
Advantages
    �    A user process cannot readily interfere with the operation of the system or another process, independent of the "safety" of 
    the programs running in the process.
    �    User applications can be terminated and their space entirely reclaimed as easily as they can be loaded and started.
    �    Multiple address spaces make it easier to support more than one programming language or environment on the same machine; 
    detailed memory-management decisions (which are the primary difficulties in getting languages to coexist) are left to the 
    individual processes in their individual address spaces.
    �    Debuggers can run in protected processes, using system-provided facilities for accessing the target memory and other runtime 
    state, which can be completely frozen during the debugging activity.  Cedar's "same-world" debugging can break down due to 
    process deadlock or failure in the safety mechanisms; one must then resort to remote debugging or "world-swap" debugging, both 
    fairly clumsy methods. 
We believe these are important advantages.  Combining the advantages of both approaches to programming environment design, 
beginning with either base, is an important topic for future research.
3.4 Case Studies
When testing new versions of Cedar software, there are three main techniques for managing versions inside a running Cedar world: 
program replacement, multiple versions of a program, and configurations with restricted exports.  With program replacement, there 
is exactly one copy of a program in the system, but it is a new version.  If name hiding is required to avoid name clashes or 
improper binding of names, then an opaque configuration can be built that does not export the names.  Thus the latter two 
techniques are often combined.
A Cedar system is constructed by making a boot file from the Cedar language components of the Nucleus and Cedar Machine levels.  
When this file is booted, it reads a "boot configuration file" that contains a list of programs to load.  The default programs are 
those in Life Support.  Each user has a file for the user profile that specifies what Applications level programs should be loaded 
immediately after a boot.  During normal system operation, the CommandTool can load other programs.
For program replacement, the level of the program is important.  If the software is in the Cedar Machine or Nucleus levels, then a 
new boot file must be constructed and the workstation rebooted (five minutes to build and boot on a Dorado).  If the software is at 
the Life Support level, then the boot configuration file must be altered to specify a mix of new and old software from Life Support 
(two minutes to boot).  If the software is at the Applications level, then before testing a fast form of boot (rollback) can be 
done (one minute).
For multiple versions of a program and configurations with restricted exports, the software is treated as if it is at the 
Applications level.  Occasional rollbacks are performed to get clean systems, but normally installing a new version by loading it 
from the CommandTool is nearly instantaneous.  Most programs are developed this way.
An example of program replacement at the Life Support level is modifying the Tioga editor.  A new boot configuration file is 
constructed with the normal Tioga replaced by the test version.  The system is rebooted and tested.  For more complicated changes, 
only a subset of the normal boot configuration file might be used to limit the amount of programs that must be compatible.
A recent example of both multiple versions of a program and configurations with restricted exports is the current revision of the 
Graphics Package; the new one supports improved device independent graphics, but it is incompatible with the old one.  During 
testing, we want to use the existing and working debugging tools that are based on the released versions of Viewers and Tioga.  An 
opaque configuration is constructed with all the new software, including the new Graphics package with new versions of Tioga and 
Viewers.  A few extra programs are included in the configuration since they use globally named variables; including them in the 
configuration provides private copies of the variables.  When this configuration is started from the CommandTool, it gets a new 
"virtual terminal" from the Terminal Package.  The virtual terminal may be connected to the real display and input devices; special 
keystrokes allow for switching between virtual terminals.  The standard system viewers and debuggers can then be used to examine 
and debug the new packages from the normal display, and the virtual terminal can be switched to view the effects.
One of the goals of Cedar was to provide for fast turnaround from small program changes.  Program replacement in a running system 
has not been achieved: a program cannot be removed from a running Cedar system.  We have program replacement during boot or load, 
or we load multiple versions of a program.
Conclusions
Conclusions
Conclusions
Conclusions
Conclusions 
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, 2533.
[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.


[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''.
[32]    R. Sweet, J. Sandman, Jr. "Empirical Analysis of the Mesa Instruction Set," SIGPLAN Notices 17, 4, Mar 82.
[33]    M. Brown, K. Kolling, and E. Taft. The Alpine File System, Xerox PARC Report CSL-84-4, 1984.
[34]    G. McDaniel. ``The Mesa Spy: An Interactive Tool for Performance Debugging,'' Proc. of 1982 ACM SIGMETRICS Conference on 
Measurement and Modleing of Computer Systems.  Aug 82.
[35]    Syntax-directed editing in Lisp.
[36]    Cornell Program Synthesizer.
[37]    Magpie, Tektronix.
[38]    Blit terminal debugging.
[39]    Mentor?
[40]    Mesa 11 Manual.