Paul McJones, editor
paul@mcjones.org
https://mcjones.org/dustydecks/
Last modified 7 April 2026
The goal of this project is to preserve the history of the Mesa family of system programming languages designed at Xerox PARC (with early collaboration with SRI ARC) in the 1970s and 1980s—MPS/MPL, Mesa, and Cedar—via primary and secondary source materials including personal recollections, specifications, source code, documentation, memos, and papers.
This project is based on personal recollections as well as documents and source code from several archival collections. Thanks to Ed Satterthwaite for his recollections of MPL, Mesa, and Cedar as well as the Mesa group photograph and to Peter Deutsch, Butler Lampson, Ed McCreight, Jim Mitchell, and Ed Satterthwaite for permission to include their documents from the Charles H. Irby Papers at Stanford. Thanks to Dick Sweet for [Wirth1977] and to Nick Briggs for his recollections of the Cedar Roadrunner project. The archival collections include:
Items are indicated by a URL with the anchor text "PDF at bitsavers.org".
Items are indicated by a URL with anchor text of the form: [volume]<directory>subdirectory>filename.extension!version
Items are indicated by a notation of the form: Charles H. Irby Papers, box N, folder M. Posted here courtesy of the original author and the Department of Special Collections, Stanford University Libraries.
Items are indicated by the notation: Computer History Museum, acquisition number X9513.2021.
In order to understand the environment in which Mesa originated it is interesting to trace forward from the beginning of computer research in the San Francisco Bay Area. One of the earliest projects in the area was the CALDIC digital computer, led by Paul Morton (1906–1995) at the University of California, Berkeley. The project began in 1948 and the machine was running by the early 1950s. One of the participants was Douglas Engelbart (1925–2013).
In 1954, Harry Huskey (1916–2017) joined Morton on the Berkeley faculty. Huskey had worked on ENIAC with John von Neumann (1903-1957) , on the Pilot Ace with Alan Turing (1912-1954), and then designed the Standards Western Automatic Computer (SWAC) at the National Bureau of Standards in Los Angeles. Around the time he joined the Berkeley faculty, he was also designing the G-15 for Bendix. In the late 1950s Huskey led the development of NELIAC, an ALGOL 58 dialect whose compiler was written in NELIAC. In the early 1960s, his student Niklaus Wirth (1934–2024) used NELIAC to implement the first version of his language EULER, a generalization of ALGOL 60. After getting his PhD at Berkeley, Wirth joined the Stanford University Computer Science Department and worked on a series of programming languages: a revised EULER, the machine-oriented PL360, and finally ALGOL W (which was implemented in PL360). One of the graduate students who worked on PL360 and ALGOL W was Edwin Satterthwaite (1943–). At about this time, Wirth returned home to Switzerland, taking a position at the University of Zürich for one year, and then moving to ETH Zürich for the rest of his career. At ETH, Wirth continued to design programming languages: Pascal [Wirth1971, 1973], Modula and Modula-2, and finally Oberon.
Meanwhile, in 1962 on the east coast, J. C. R. Licklider (1915–1990) was appointed director of the ARPA Information Processing Techniques Office, and began issuing grants for time sharing-system research. He also issued a small grant to Huskey and David Evans (1924–1998), who Huskey had recruited from Bendix, where he'd been the project manager for the G-15 and G-20 projects. This first project was just to set up remote teletype access to the timesharing system for the AN/FSQ-32 computer at System Development Corporation, but it was followed by Project Genie, a timesharing system based on a modified SDS 930 (later named the SDS 940—see photo). Much of the software for Project Genie was written by Butler Lampson (1943–), another of Huskey's PhD students, and L. Peter Deutsch (1946–), a precocious undergraduate who'd already written an interactive LISP system and the first TRAC interpreter, both for the PDP-1. Lampson and Deutsch collaborated on QSPL [Deutsch1967], a systems programming language for the SDS 940.
In parallel with these activities at Berkeley, Doug Engelbart, who'd joined SRI (originally the Stanford Research Institute and now SRI International) in 1957, had been doing early work on NLS (oNLine System). He struggled for funding, but found a sponsor in Robert W. Taylor (1932–2017) at NASA. Taylor's mentor was Licklider, and Engelbart's vision of augmenting human capabilities with computers fit Licklider's vision as Taylor interpreted it. Taylor moved from NASA to ARPA and increased the funding for Engelbart. Engelbart built a team of dedicated engineers, who were joined for the summer of 1965 by interns Lampson and Deutsch.
In 1967 the Project Genie timesharing system was working smoothly and Engelbart acquired an SDS 940. Work on NLS proceeded, and in December 1968 Engelbart and his team, which included William H. Paxton III (1946?–2025) by this point, gave a demonstration at the Fall Joint Computer Conference. Engelbart sat in front of the audience with his display, keyboard, mouse, and 5-finger keyset; his screen was visible to the audience via a projector and large screen. Engelbart collaborated with colleagues at SRI in Menlo Park to edit documents and hold a video conference. This "Mother of All Demos" deeply impressed the audience of computer researchers. Charles H. Irby (1945–2024) was inspired by the demo to join the project.
The Project Genie designers, pleased with their success, wanted to build a larger system. ARPA would have funded it, but dealing with the university bureaucracy was too difficult, so they founded the Berkeley Computer Corporation with venture financing. Joined by recent Berkeley physics graduate Charles P. Thacker (1943–2017), they built a first prototype, the BCC 500, but ran out of funding as the system was being finished. Taylor convinced ARPA to acquire the prototype for the University of Hawaii, where it ran through the 1970s. One feature of the BCC 500 was a systems programming language called SPL [Lampson1969]. Inspired by QSPL, it was a more powerful and polished language.
Now we temporarily leave the Bay Area. In 1968, William Wulf (1939–2023) joined the Carnegie-Mellon University faculty. He wanted to design an operating system, but first launched the Bliss project to design an appropriate implementation language [Wulf1971]. One of the graduate students assisting him was Charles Geschke (1939–2021), whose research focused on object code optimization. Richard Johnsson (194?–) joined the project later. Also at CMU was graduate student James Mitchell (1944?–), who graduated with a PhD in interactive programming languages in 1970 and joined BCC as it was winding down.
By 1970 all these threads began to come together. Xerox Corporation, whose invention and refinement of xerographic plain-paper copiers had pushed it to position #9 on the S&P 500 and given it the cash to acquire Scientific Data Systems, maker of the SDS 940, opened the Palo Alto Research Center (PARC) to develop "the architecture of information." Robert Taylor was hired to staff the Computer Science Laboratory; his early hires included BCC veterans Lampson, Thacker, Deutsch, and Mitchell. And the next year he hired a group of people from Engelbart's Augmentation Research Center (ARC). With this talented and growing group of researchers, interesting things began to happen at PARC, and one of them emerged initially as a collaboration with ARC: the Modular Programming System (MPS) with the Modular Programming Language (MPL).
The MPS project got underway in 1971 with the goal of producing "a set of tools for the development and continuing evolution of large software systems in an interactive environment" based on a modular runtime architecture and a matching higher-level language, MPL. Initial project personnel were to include William Paxton and Charles Irby at ARC and James Mitchell and Peter Deutsch at PARC, with Butler Lampson and Alan Kay at PARC expected to be contributing to the design [Paxton1971]. The target of MPS would be systems constructed by groups of people, and consisting of separately-developed programs. A reimplementation of NLS for MPS was discussed [Irby197x], and would allow porting NLS to other computers [Engelbart1973]. MPS was to be structured in terms of components called modules that could be written and compiled independently, but could be linked together in flexible ways, supporting flexible control structures such as messages sent over ports. Data definition facilities would allow defining structures used in the interfaces between modules, and also those used internally to the implementation of a module. Libraries of software components—modules of high generality—would be built up over time [Footnote 1]. There would be integration with NLS, a source language debugger, and the ability to recompile and replace a module in a running system [Paxton1971], [Mitchell1972a]. By this time NLS was running on the PDP-10 under BBN's TENEX.
The version of NLS running on the SDS 940 had been built using tools developed at SRI. MOL940 [Hay1968] was a machine-oriented language with an ALGOL-like syntax, somewhat like Wirth's PL360. Tree Meta was a translator-writing system used to build the parser for MOL940 as well as several Special Purpose [domain-specific] Languages [Hay1968], [Andrews1967], [Engelbart1968]. In 1970, when it was decided to reimplement NLS on a PDP-10 running the TENEX operating system, a new language L10 was designed to replace MOL940. It was bootstrapped on the 940, using Tree Meta [Engelbart1971]. Tree Meta and L10 were used to build the first version of MPS and MPL, and the MPL specifications used Tree Meta notation for syntax.
The PARC researchers wanted their own PDP-10 running TENEX, but weren't allowed to purchase a competitor's machine (Xerox had acquired SDS in 1969). Their response was to design and build a PDP-10 clone called Maxc. Until it was completed (around 1973), they used the NLS PDP-10 at SRI.
MPL, the language component of MPS, built on languages familiar to the designers but sought to provide a new modular framework, with emphasis "on the more global parts of a programming system: control transfers between modules, binding of external references, [and] specifying the execution context of a module" [Lampson197x]. Lampson's undated document described an intriguing system. A module would contain a set of ports, each labeled with an identifier and tagged with a type consisting of a pair of record types: arguments and results of a control transfer. A port could be bound to a port in another module with matching types; this could occur during runtime or earlier. A set of partially-bound modules could be configured as a new module, with only the unbound ports exposed. Instances of modules could be created dynamically. A single control transfer mechanism would unify procedure call/return, coroutines, and signals (dynamically-bound exception handlers with resumption, termination, and unwind handlers). Types could be built up using the type constructors array, record, pointer, and union. Type descriptors were to be another type that could be manipulated by programs such as the binder (which could check for compatibility between source and destination ports) and the debugger. In general, the MPS environment would be a carefully-specified virtual machine all of whose components would be accessible to a program. There were many new ideas here, although the paper credited Bliss, Pascal, and SUE for control and data structuring mechanisms, Simula for dynamic creation of module instances, PL/I and Snobol for ideas leading to signals, Algol 68 and Pascal for type constructors, BBN Lisp for a logically complete virtual machine plus the ability to trace or trap a function call, and Multics for dynamic linking.
The earliest known MPL language specification [Mitchell1972d] describes a language with a global structure similar to BCC's SPL: a sequence of data and program modules, each of which could use INCLUDE directives to gain access to declarations from other data modules. Data modules contained declarations of constants and variables. Program modules contained declarations of constants, variables, and procedures, and also included an unnamed block that executed at initialization time. Both data and program modules could have a formal parameter list to pass values when an instance of that module was created.
Declarations were Algol-like, introduced with the keyword DECLARE and possibly including an initial or constant value:
DECLARE INTEGER i, j ← 0, K = 50; % INTEGER assumed if no type given %
Types included INTEGER, STRING, SIGNAL, ARRAY, FIELD, PROCEDURE, and PORT. Apparently the only array element type was INTEGER. A FIELD defined a bit offset and size of a field within a word. A SIGNAL defined an exceptional return from a procedure. A PORT defined a cell used to coordinate coroutine linkage between programs. There was a separate RECORD declaration that allowed definition of groups of fields that were not tied to any particular pointer or record type, and a REGISTER declaration for defining an (integer) variable with a specified machine address; addresses 0–15 on the PDP-10 were the registers.
Expressions included the usual Algol-like operators (including conditional and case expressions). The relational operators include ones for classifying characters within various subsets such as uppercase letter, digit, etc. Primaries included constants, variables, register variables, procedure calls, array references, and pointer dereferencing (with or without field selection). Operators were provided to use an integer as a pointer.
Statements included assignments, if and case statements, a rich set of iterative statements, procedure call/return (optionally with multiple result values), process control statements for instantiating, starting, stopping, and transferring control to program modules. It was planned that the hierarchical structure of NLS document files would eventually replace the use of BEGIN and END as a means of forming compound statements.
Meeting notes from February 1972 by Charles Irby (then at SRI) gave this tentative schedule [Irby1972]:
- Rewrite MPL in MPL: mid February to mid March
- Design data typing facility for MPL: mid February to mid March
- Implement data type facility: mid March to ?
- Start design for NLS: mid March to ?
- Start implementing NLS in MPL: July to ?
- MPL on mini: ?
- MPL operating system: ?
Consistent with that schedule, a March 1972 memo described an "MPL Datatype Facility"
[Paxton1972b]. This memo mentioned Pascal-like basic types and type constructors for pointers, dynamic arrays, records, records, and unions—similar to [Lampson197x]. It also spoke of the benefits of type checking for debugging and raising the level of abstraction of the program. It critiqued Algol 68 for its choice of structural type equivalence for record types, citing the example of a complex number represented with cartesian or polar coordinates and concluding the need to "label" record types. ([Lampson197x] says "It is possible to compare two types for
structural or for literal identity.") Paxton's memo mentioned automatic coercions but said most coercions would be handled with explicit transformation functions.
Ed Satterthwaite arrived at PARC and joined the MPL project around this time: [Satterthwaite 2025]
"By the time I arrived at PARC (August 1972) there was a working but incomplete MPL. ... MPL evolved in part from a language called L10, which was a structured implementation language for the PDP-10/DEC10/DEC20 done at SRI. There was some collaboration and perhaps some shared code for a while. If I recall, Bill Paxton was our primary contact at SRI."
[Mitchell1973a] is a specification for the data portion of the language. It is substantially advanced from [Mitchell1972d], having comparable functionality to [Paxton1972b] but is worked out in detail rather than being a high-level overview. Perhaps it was a proposal for the future, because the later [Satterthwaite1974a] described a simpler language that seems to have actually existed at the time it was written [Footnote 2]. In Satterthwaite's document the global structure of the language was relatively unchanged. There was still no way to define an interface for a set of procedures, as became possible with the definitions modules of Mesa and, later, Modula-2. Variable declarations were similar to Pascal, but type expressions were still limited (e.g., array elements were still restricted to single-word values and pointer types could only be declared for record or field types. TYPE declarations were restricted to RECORD types. Type checking was restricted to checking overall size (number of bits); pointers could be declared without a target type, and field selectors could be applied to any pointer value.
Here's a short example [Satterthwaite1974a]:
f: PROCEDURE [n : INTEGER] RETURNS [INTEGER] =
BEGIN -- an MPL factorial function of course --
x: INTEGER ← 1; i: INTEGER;
FOR i THRU (1..n] DO x ← x*i;
RETURN[x]
END
Library code written the previous month (see NEWFSP.NLS and NEWMPSSTR.NLS below) provides larger examples. The use of the NLS system for source code is evidenced by the hierarchical line numbers in the right margin and by identifiers enclosed in parenthesis used as labels—these were links, analogous to hyperlinks in modern web documents.
The earliest known MPS planning documents [Paxton1971] and [Mitchell1972a] both indicate the desire for non-local control structures more general than procedure call/return. Paxton specifically mentioned Rudy Krutar's use of ports for coroutine discipline in a parser, and "somewhat more grandiose schemes" considered by Robert Balzer. Presumably the corresponding publications were [Krutar1971] and [Balzer1971]. To address this desire, a design emerged based on a universal sequential control transfer primitive known as XFER [Lampson1972]. The design, further refined and abstracted in [Lampson1974], unified port calls (coroutines), procedure call/return, and signals [Footnote 3]. The mechanisms (including heap-allocated frames) described in this report became part of the Mesa virtual machine specification [PrincOps1977], [Johnsson1982]. Further, they were supported in the Mesa language via the PORT and SIGNAL mechanisms of Mesa (see Chapters 8 and 9 of [Mitchell1978]). [Lampson1982] revisits XFER and presents a set of performance optimizations for the procedure call/return case. [Lampson1983a] says "Use of ports is complex, unsafe and not recommended." Finally, the XDE Mesa Language Manual released in 1984 omits ports entirely [XDE1984].
[Deutsch1972a] and [Mitchell1972b] describe the control transfer mechanism as well as mechanisms for binding contexts at runtime. Deutsch's paper was written for the Fall Joint Computer Conference, but never published. [Mitchell1972c] is a reference for the runtime. [Paxton1972a] is a reference for the MPS segmented virtual memoy implemented in software above the TENEX operating system's paged virtual memory.
"There is also a way to prevent components of a record from being accessed except by a group of procedures which are declared with it. Such a record is called closed, and the procedures are called its handles. Finally, it is possible to declare a record type s as a direct extension of another record type r, by adding additional components and handles. Extension is the transitive closure of direct extension, and the set of all extensions of r is the class of r. Closed records and classes were inspired by the class mechanism of Simula [Hoare and Dahl]; that language, however, encourages the restriction of access to handles, but does not enforce it."
Improved debugging was one of the earliest MPS goals. Source-level debugging and integration into the NLS environment with its multiple-windowed graphical display were cited. Some of the improvements to debugging were expected to follow from the modular nature of the system, such as controlling intermodule connections to isolate a module for testing and using the system itself to build new debugging tools [Paxton1971], [Mitchell1972a]. An unsigned, undated memo titled "The MPS Debugger" outlines facilities to be provided to the user and system facilities required from the runtime for use by the debugger [Anonymous197x].
June 1972 minutes by PARC researcher Ed McCreight reported on an MPS debugger design meeting held on 8 June 1972 by Lampson, Deutsch, Mitchell, and McCreight [McCreight1972]. Several aspects of MPS's use of ports and context pointers rather than call stacks were explored. There was also a brief digression into accounting for resource usage by a service process (coroutine) invoked by several user processes.
A September 1972 document from Mitchell and recently-arrived Satterthwaite combined minutes from meetings in June and August with an initial specification for debugger functionality and implementation [Mitchell1972e]. The June meetings included Mitchell, Lampson, and Irby (6/21), and Mitchell, Lampson, Deutsch, and Paxton (6/27), and covered requirements for debugger functionality. The August meetings (8/23–25) included Mitchell, Satterthwaite, and Donald D. Cowan (Mitchell's undergraduate supervisor from Waterloo, on sabbatical at Stanford and PARC), and descended to various aspects of debugger implementation as well as approaches for name binding within the debugger's interpretive command language. The final section, "Initial Debugger Design Specification", was written by Mitchell, and sketched the command language, which was based on an interpreter for MPL-like expressions (including assignment) supplemented with procedures for examing and modifying data structures, tracing, setting breakpoints, etc. It also covered how variables of this interpretive language would be represented in the debugger.
By January 1973, Satterthwaite, whose Ph.D. thesis work involved symbolic debugging and tracing in the Algol W context, had released the first of several detailed specifications for the debugger, which included a number of built-in procedures and which could invoke externally-defined packages [Satterthwaite1973a]. One such package was Meter, which was documented in [Satterthwaite1973b]. An updated version of the debugger document was published in 1974 [Satterthwaite1974b].
"We always re-invent the wheel 'just one more time, then it'll be right.' We essentially went back to the machine level to implement MPS, rather than starting with an established system. We could have lifted the BLISS compiler, used SIMULA 67 as a semantic base, or written an interpreter in LISP. Although Tree-Meta and L10 have helped us write our own code, we haven't used any part ot them or any part of any other existing software."
By late 1974, the MPL(B) implementation included a loader, debugger, and editor. It ran on MAXC, PARC's PDP-10 clone running TENEX. The name Mesa was beginning to be used, a port to the Alto was being planned, and the system was being used "by many people at PARC" [Heinrich1974]. Mesa had a richer type system and strong type checking. Its syntax was based on Pascal; its type system was influenced by Pascal and Algol 68.
Three memos from the summer of 1974 give a feeling for the design work taking place. [Mitchell1974] discussed "What Mesa needs in an Alto Virtual Memory Scheme." The Alto did not have dedicated hardware for memory mapping, but could be microcoded to use its hardware registers as base pointers for things like local and global frames and code segments. Mitchell's memo suggested a notion of page groups (adjacent pages) that would be contiguous both in memory and on the disk backing storage. [Wegbreit1974] reports on dynamic and static measurements taken of two Mesa programs using an instrumented PDP-10 emulator (running on Maxc, PARC's PDP-10 clone). The dynamic measurements were then used with a page replacement model to predict the performance of Alto Mesa. The static measurements were used to guide design of compact encodings for the instruction set of a virtual machine designed to run Alto Mesa programs. [Satterthwaite1974c] presented a plan for porting Mesa to the Alto. The plan, including a dependency diagram and time estimates, suggested that the four implementors (Geschke, Mitchell, Satterthwaite, and Richard Sweet) could complete a "slow but usable" version by the end of 1974, although that would delay planned work on data structuring facilities. One step of the plan was to "write an interpretive engine in BCPL." Satterthwaite notes "I'm reasonably sure that never happened. I think we just ran on increasingly complete and accurate simulators on Tenex and then went to microcode" [Satterthwaite2026].
The Alto, PARC's pioneering personal computer, was conceived in late 1972. The first prototype ran in April 1973 and the first software (operating system, BCPL compiler, and simple text editor) was released in March 1974. The first batch of production machines were built between March and September 1974 [Thacker1988].
Satterthwaite noted [Satterthwaite2025]:
"Chuck Geschke arrived at PARC not too long after I did [August 1972]. He spent his initial few months on MAXC diagnostics and commissioning, then joined the MPL project. When the first Altos were imminent, Chuck and I wanted to move immediately to the Alto. ... Eventually Chuck and I decided to ... [devote] all our efforts to a port and refinement of Mesa on the Alto."
The 1976 paper "Early Experience With Mesa" reported [Geschke1976a]:
"... Most major aspects of the language were frozen when implementation was begun in the autumn of 1974. ...
...
A cross-compiler for Mesa became operational in the spring of 1975. We used it to build a small operating system and a display-oriented symbolic debugger. By early 1976, it was possible to run a system built entirely in Mesa on our target machine, and rewriting the compiler in its own language was completed in the summer of 1976. The basic system, debugger, and compiler consist of approximately 50,000 lines of Mesa code, the bulk of which was written by four people. Since mid-1976, the community of users and scope of application of Mesa have been expanding rapidly, but its most experienced and demanding users are still its implementers."
The small operating system was written by Richard Johnsson and John Wick and interoperated with the existing BCPL-based system [Lampson1988], providing a debugger, display services, stream I/O, etc. The Alto's single address space was shared by the operating system and the user program, as was the case with later personal computers such as the Altair and the Apple II.
On 1 December 1976 the TENEX cross-compiler was deleted, and the Alto version was officially released. The extensive system documentation included a grammar for the language; apparently a Mesa Language Manual, Version 1.0, was published but no copies are known [Geschke1976b].
On 11 January 1977, Niklaus Wirth, then on sabbatical at Xerox PARC, gave a talk on his experience with Mesa. The next month he wrote a memo with the sample programs he'd written and comments about the Mesa language [Wirth1977].
"We are concerned about parts of the proposed action plan for implementing Mesa on the Sigma under CP-V.
First, the MAXC version of Mesa is not the appropriate take-off point for such an implementation. The Alto version is the one to start with. We are now concentrating on the Alto version, making considerable improvements in it, and are not intending to upgrade the Maxc version to maintain compatibility between it and the Alto one.
... A Mesa Virtual Machine has not yet been specified and needs to be."
"The Mesa, language, compiler and programming system are the product of a long-standing research project at Parc, in which Chuck Geschke, Butler Lampson, Jim Mitchell, and Ed Satterthwaite have been the main participants. The current compiler was written by Geschke and Satterthwaite. They also wrote the debugger and support software needed to run Mesa programs on the Alto, in collaboration with Jim Mitchell and with Charles Irby, Richard Johnsson and John Wick of SDD/Palo Alto. Compiler testing has been done by Jim Frandeen of SDD/Palo Alto."
By 1974 Xerox had launched the OIS (Office Information System) group to design and build computer-based office automation systems. The group was based in El Segundo, California, and was staffed by former Scientific Data Systems employees. Early planning indicated the need for a high-level systems programming language for OIS, and MPL, or Mesa as it was beginning to be called, was selected [Heinrich1974], [Frandeen1974], [Elkind1975]. By 1976 the OIS effort had expanded to include an organization known as SDD in Palo Alto that was responsible for OIS hardware (processor and local area network) and system software: the Mesa compiler, debugger, and other tools, plus an operating system, Pilot, that included communications and networking, all written in Mesa. The group in El Segundo focussed on application software: a compound document editor, electronic filing and mail, etc. This was first released in 1981 as the Xerox Star 8010 Information System. While Mesa development shifted from PARC to SDD, PARC researchers continued to use Mesa.
At some point between MPL(B) and Mesa 1.0, the DEFINITIONS module was added to the language. Containing constants, types, procedure and signal (exception) signatures, it formalized the interface between client modules and implementing modules. This had an immediate positive effect on how programmers structured and documented their programs [Lauer1979]. Niklaus Wirth, who'd spent a sabbatical at PARC in 1976, later said, "The idea of separate modules with separate interface definitions stemmed from the Mesa project at Xerox PARC, and it truly constituted one of the rare breakthroughs in software engineering" [Wirth1992].
Although DEFINITIONS modules allowed typesafe separate compilation of clients and implementors, the original system didn't give precise control over the binding of modules; for example, it might obtain Allocate from one module and Free from an entirely unrelated one [Lauer1979]. This was improved in Mesa 3. Compiling an interface effectively produced an interface record containing procedure- and signal-valued fields. Calls in a module importing this interface were type-checked against the types in the interface record, as were the corresponding declarations in a module exporting this interface. A new tool, the Binder, combined a set of compiled modules into a unit, copying the procedure and signal descriptors from exporters to importers, an interface at a time [Satterthwaite1977]. To ensure that the importers and exporters had been compiled with the same version of each interface, a compiled DEFINITIONS module contained a timestamp-based internal name [Lauer1979].
The binder was changed to support a configuration language, C/Mesa, that allowed modules to be grouped in subconfigurations, with control over what interfaces were exported from or imported into each subconfiguration and the ability to name individual instances of an interface [Mitchell1978].
In early 1977 a joint SDD-CSL (PARC) working group was convened to determine what process mechanism(s) should be included in the OIS environment: Mesa and the Pilot operating system [Redell1977]. Although there was some sympathy toward the simplicity of non-preemptive scheduling, it was generally agreed that preemptive scheduling would be necessary. Monitors and condition variables were identified as the appropriate synchronization mechanism [Brinch Hansen1973], [Dijkstra1972], [Hoare1974]. The resultant design simplified and optimized the wait/notify semantics and added a cancellation mechanism [Redell1978], [Lampson1980a]. Processes were added to Mesa 4.0 in May 1978. A very similar design was used in Modula-2+ and Modula-3 at the DEC Systems Research Center, and was later standardized as IEEE POSIX Threads.
While the original MPL compiler generated standard PDP-10 machine instructions, the Alto offered a challenge and an opportunity. The challenge was its small address space: 16-bit addresses and 16-bit words. The opportunity was the Alto's writable control store, which allowed the instruction set to be tailored for a specific language. The default microcode (used for BCPL programs) was based on the Nova minicomputer. Smalltalk had its own instruction set. The Mesa instruction set was designed to maximize code density based on an empirical study of the entropy in a large set of Mesa programs [Sweet1978, 1982].
"It is ironic that some of our successes have produced some of our largest shortcomings. The Alto, on which we first implemented Mesa, was a very modest machine with only 16 bits of address space and no hardware support for virtual memory. We nonetheless implemented a compiler for a large language that ran on the Alto with respectable performance. This was done by carefully tailoring the data structures and algorithms to fit into the restricted space. As machines became larger, the data structures could not gracefully grow, so the current compiler still limits program size to about 1000 lines. The Mesa language itself has not been immune from this type of premature optimization. The two classes of pointers (short and long) in the language are largely an artifact of the original Alto implementation. The treatment of OPEN as substitution by name was partly motivated by the need to live with relocating storage management schemes on the Alto" [Sweet1985].
Alto/Mesa used 16-bit word addresses to access variables in local and global frames and heap zones. A special version, XMesa, supported the four switched memory banks of a "wide-bodied Alto" for code segments. With the adoption of Mesa for Office Information System (OIS) products, the address space was expanded to 24 bits of paged virtual memory. Part of the process state was a page-aligned base pointer to a 64K-word Main Data Space (MDS), which held the local and global frames. The instruction set was formalized as the OIS Processor Principles of Operation [PrincOps1977]. The initial implementations of this architecture were the D0, renamed the Dolphin, and the D1, renamed Dorado. Later came Dandelion and Dicentra.
After Mesa 5.0, the paths taken by PARC and SDD began to diverge. Some of the early language changes for Cedar were incorporated into Mesa 6.0. The development of Cedar is covered in the section The Cedar Language below. The development environment for Mesa shifted from the Alto to the Dolphin and Dandelion running Pilot. This environment was initially called Tajo, and later became the Xerox Development Environment (XDE) product marketed by the Xerox Information Systems Division [Tajo1980], [Sweet1985].
"The language accepted by the Mesa 4.0 compiler has several significant extensions and a few minor changes. It features a process mechanism, enhanced arithmetic capabilities, long and base-relative pointers, and more general block structure" [Satterthwaite1978].
- - -
"The primary emphasis in this release has been on three areas: implementation of features required by Pilot and Dstar applications for effective use of the new machine architecture (processes. monitors, long pointers, etc.), reduction of overhead in the basic system structures and improved performance of the Mesa runtime environment (faster microcode, smaller global frames, more efficient memory management). and extension of the debugger's capabilities (primarily an interpreter for a subset of the Mesa language)" [Redell1978].
"Note also that Mesa 6.0 adopted, at least in part, a number of the additions to Mesa proposed in [Cedar] 6C2. These include the ability to control the initialization of a variable according to its type, generic NIL, zones with NEW and FREE operations, sequence types, and a restricted form of opaque types." [CLFDC1981]
Released circa 1981. (Cedar 7T7 was released in May 1981 [Satterthwaite1981a].)
Released April 1982 [Sweet1985].
Released 1984? See [XDE1984]. Also, a Mesa Language Manual draft version 11.0, March 1984 is cited in Introduction to Cedar, Cedar 7.0, March 1987 (see Cedar 7.0 below).
"With Pilot 14.0, global frames are not allocated from the main data space (MDS). This architectural change causes some small semantic changes to the Mesa language. These language changes are documented in the Mesa Language Manual Change Summary." [Page 3-3]
As soon as Mesa was running on the Alto, it began being used at PARC for research projects and shortly thereafter at Xerox SDD for a family of office automation products. Some of PARC's research projects written in Mesa include:
Contains [Birrell1982], [Schroeder1984], and Andrew Birrell: The Grapevine Interface, December 1983.
Some of Xerox's products built with Mesa include:
With its 16-bit address space and 128–512 kByte memory (the latter requiring bank-switching), the Alto seems like a toy compared to modern computers, and yet the PARC researchers built a series of pioneering applications, including the Bravo WYSIWYG text editor, the Draw and Markup illustration programs, and the Grapevine electronic mail system. But integration of these applications had to happen through the file system; it wasn't possible to run more than one at a time.
By 1978, the first prototype of the Dorado personal computer was running. This machine, with a much faster processor, a 28-bit virtual address space, and 2 to 8 MByte of memory, would allow the design of large, integrated systems combining text, graphics, audio, and more [Lampson1980b], [Pier1983]. That year a planning activity took place in the Computer Science Laboratory, taking stock of the three main environments in use at PARC (Interlisp, Mesa, and Smalltalk) and deliberating on what should come next [CedarPlanning]. A first working group reviewed the three environments, producing "a catalog of programming environment capabilities which included justified value, cost, and priority evaluations. [Deutsch1980]." It was agreed early on that Smalltalk should be dropped from further. The group concluded: "CSL should launch a project on the scale of the Dorado [~20 person-years] to develop a programming environment for the entire laboratory starting from either Lisp [Interlisp] or Mesa". A second working group met for three months and concluded that a suitable environment could be built with either language. For non-technical reasons, Mesa was chosen as the starting point [Teitelman1984], [CedarPlanning]. "The general idea was that we wanted to combine the best features of the Lisp/Smalltalk environments automatic storage management, delayed binding, fast turn-around, and an integrated environment with those of the Mesa language static checking, explicit interfaces, and efficient use of machine resources [Morris1980].
As a result of this effort, the Cedar project began in 1979, producing a new Cedar language as well as a rich programming environment—see The Cedar system below. During spring 1979 various language design subgroups investigated proposals for individual features, especially objects and safety. By fall a series of Cedar language proposals began appearing, with the initial digit (5, 6, 7) taken from the corresponding Mesa release.
The resultant Cedar language extended Mesa in several ways [CLFDC1979a], [Horning1986]:
[Owicki1981] presents the formal specifications of garbage collection that were used to define the safe subset of Mesa. [Rovner1982] and [Rovner1984] discusss implementation details for garbage collection and runtime types. [Boehm1994] discusses the ROPE type and refinements to its implementation.
Having evolved over a decade from its MPL and Mesa roots, Cedar was a large and complex language. The challenge of documenting it was approached in two ways:
"Programming language designers have invented a number of features to support the writing of large programs in a modular way which takes advantage of type-checking. ... This paper describes a small programming language called Pebble, which provides a precise model for these features. It is a functional language, based upon the lambda calculus with types. It is addressed to the problems of data types, abstract data types and modules. It also deals with the idea of generic values. It does not reflect all aspects of programming languages, since we have not dealt with assignment, exceptions or concurrency, although we believe these could be added to our framework. Our intention is that it should be possible to express the semantics of a sizeable part of a real programming language by giving rules which rewrite it into Pebble. This follows the method used by Bauer and his colleagues [Bauer et al. 1979] to express the semantics of their wide spectrum language. We were particularly concerned with the Cedar language (an extension of Mesa [Mitchell et al. 1979]) which is in use at Xerox. One of us (BL) has defined the quite complex part of this language which is concerned with data types and modules in terms of rewrite rules which convert Cedar to an earlier version of Pebble; this work is described in an unpublished report [Footnote 4]."
MPL, Mesa, and Cedar were designed for writing large, complex systems. The structure of modules and interfaces allows programs to be built up from component modules with explicit control of the interconnections. For example, there may be multiple implementation modules for a single interface, these implementation modules may be used in different configurations (e.g., different device drivers for different hardware) or even within the same configuration, for example different implementations of a hash table interface. The configuration language C/Mesa facilitated these uses. The System Modeling project, at the center of which was SML, the System Modelling Language, took this to a further stage [Lampson1980c, d], [Lampson1983b, c], [Schmidt1982a, b]. The full SML is defined in Section 3 of [Lampson1983b]; an earlier version is defined in [Schmidt1982a]. It is a functional (side-effect free) typed lambda calculus operating on primitive values (STRING, TYPE, and INTERFACE n) and functions (built-in and closures), bindings (ordered sets of [name, type, value] triples and declarations (ordered sets of [name, type] pairs) and is "roughly the applicative subset of the Cedar Kernel language."
Also published in Semantics of Data Types, Lecture Notes in Computer Science 173, Springer, 1984, pages 1-50. Later version: B. Lampson and R. Burstall. Pebble, a Kernel Language for Modules and Abstract Data Types. INFORMATION AND COMPUTATION, Volume 76, pages 278-346 (1988). ScienceDirect
The Cedar language design and implementation was fairly far along by the end of 1981, but producing a new programming environment to take advantage of the language was a larger project involving a number of people for several more years. Jim Morris had agreed to manage the overall Cedar project:
In 1979 a large, distributed design effort was begun on many different topics: user facilities, display packages, language changes, communications, management of large programs, filing, etc. This effort was coordinated by a steering committee consisting of Peter Deutsch, Jim Horning, and Butler Lampson, and involved a substantial fraction of the laboratory. An external design review was held in September. The organization of the implementation efforts began in the late summer of 1979 and the programming of certain things started in the Fall." [Morris1980].
Bootstrapping the Cedar system began with an Interim Mesa Environment (IME) running in Alto emulation mode but supporting more than 512K words of memory [Lampson1978]. IME allowed editing/compiling/loading and was running on the Dorado by late 1979. The next step ported Pilot, the product operating system, to the Dorado, since it supported a paged virtual memory and a more robust filesystem. Cascade, an IME replacement that could edit, compile, bind, execute and debug, was available by late 1980. In January 1981 a project review was carried out; its report noted progress in every area, but pointed out a need to coordinate development in the various areas and push to complete a version of Cedar that could be more widely used [Ayers1981]. By December 1983, Pilot had been replaced by the native Nucleus. For more detail about early development, a "tour" and an assessment (as of 1984), see [Teitelman1984]. For a detailed description of the system some two years later, see [Swinehart1985, 1986]. For a video of a demonstration of the Cedar system running on a Sun Microsystems workstation, see [Bier2019].
One of the important goals of Cedar was to support the Interlisp and Smalltalk programming styles, with late binding, access to program text at runtime, etc. To support this goal, the Abstract Machine package was designed. Its interfaces allowed manipulating types, variables, programs, and processes and was used to implement debugger features, including an interpreter. Section 6.4 of [Swinehart1986] discusses the Abstract Machine in some detail, concluding "The Abstract Machine interface provides complete access to Cedar types and values at run-time in a consistent fashion. Unfortunately, the interface is complicated and clumsy to use, despite many attempts to simplify it. Further research is required to allow easier program access to this information."
[Warnock1982] introduced a device-independent two-dimensional imaging model based on stroking, filling, and clipping based on paths composed of straight and curved (cubic Bézier) line segments. An implementation of this imaging model was created for the JaM language. It was also used for Cedar. Later, at Adobe Systems, it was combined with a reimplementation of JaM and a proprietary font-hinting technology to became the basis of the PostScript page description language [Warnock2012, 2018].
The Graphics package was replaced by the Imager.
Remote procedure call extends familiar synchronous procedure calls to span address space and machine boundaries. A program transformation tool ([Nelson1982]) transforms a DEFINITIONS module into client-side and server-side stub modules which are linked with a runtime module that handles retransmissions, acknowledgements, packet routing, and encryption [Birrell1983]. [Nelson1981] explores many design possibilities and includes references describing much of the previous work. A similar system was later built for DEC SRC's Modula-2+ system. Birrell and his colleagues then generalized this: see Network Objects in Software Preservation > Modula-3.
Early in the Cedar planning process a database package was determined to be useful. Examples of usage were databases of Mesa modules and their interdepencies, the CSL Notebook (a database holding CSL memoranda) , and database of Mesa source programs decomposed to the level of procedures, types, and variables [Morris1981], [Cattell1983a].
At this time database research was a relatively new field, and various data models were being considered. The Cedar developers were impressed by the RSS (Relational Storage System) layer of IBM's System R, which provided transactional tuple-at-a-time access to base tables, via any of several access paths: full table scans, indexes, and inter-tuple links [Astrahan1976]. Cedar's DBTuples interface was based on a simplified version of the RSS [Brown1981a], [Cattell1983a].
The initial implementation used the Juniper distributed file system for storing the files holding a database. Juniper ran on an Alto, limiting its performance, so a new design commenced, called FileStore, which was changed to Alpine. See below for for design documentation and [Brown1984] for a report on the system after it had been in use for 10 months. ***** Did Alpine later replace IFS as well as Juniper (adding directories, ftp, etc.?)
Later work on the database layer by Cattell added a higher-level data model, the entity-relationship-datum model and renamed the system Cypress [Cattell1983a]. An entity represents a concrete or abstract object in the world. A datum represents some information such as a date or part name. A relationship is a tuple of entities and datums. The Cypress model was inspired by Chen's entity-relationship model [Chen1976], but is arguably cleaner. Cypress replaced Juniper with the Alpine transactional file server [Brown1984], and could also use the local Pilot file system, which provided transactions [Cattell1983a].
One of the main uses of Cypress was to hold the messages of the Walnut email user agent; another application was Hickory, a calendar/appointment database.
Cedar, like Mesa before it, was implemented using a specialized virtual machine implemented in microcode and ran on the Dorado and the Dandelion (the machine used for the Xerox Star system). By the late 1980s these D-machines were being outrun by commercial workstations, and it was decided to rewrite Cedar into a form easily ported across architectures. The Mimosa project [Atkinson1989] rewrote the compiler using machine-dependent C as the target language, developed a language-independent Portable Common Runtime [Weiser1989], and finally wrote a large subset of the Cedar-specific runtime in a subset of the Cedar language.
***** Did the Abstract Machine survive the transition to Portable Cedar?
The Xerox PARC Interim File System (IFS) archive at the Computer History Museum contains snapshots of source code, executables, documentation, font files, and other files from the IFS servers that supported the Xerox PARC Alto and Cedar systems. For more about the archive, see:
This section links to a sequence of Cedar releases within the IFS archive. For releases not followed by a question mark (?), the version numbers, dates, and release descriptions (through 6.0) are from Appendix B of [Swinehart1986]; otherwise they are derived from archive content.
"Major maintenance release, Abstract Machine introduced."
"Command Tool, Interpreter Tool, maintenance release"
"RopeFile, Squirrel database browsing tool, maintenance release"
"maintenance release"
"Cedar off Pilot base, FS, VM, Safe Storage, IO, four major layers: Machine, Nucleus, Life Support, Applications"
maintenance release?
"The current version of Cedar (Cedar 6.0) occupies more than 17 million bytes of disk storage and contains over 1,500 source files, more than 400,000 lines of source code, approximately 150 DF files, and over 100 configurations."
"Interface housecleaning, Imager (replacing Cedar Graphics package—see section 9.1 of [Swinehart1986]), Interpress, logical file servers (246 application components in CedarChest)"
A version of Portable Cedar was released on a CDROM accompanying a CSL technical report: "Using Threads in Interactive Systems: A Case Study" [Hauser1993]. This version runs on Sun Microsystems SPARC-based SunOS4.1.x and Solaris2 machines. The CDROM also contains source code (except for the POSIX Portable Common Runtime) and Tioga document viewers for the Andrew ez editor and Emacs. A primer is included for navigating the Cedar environment on the CDROM [Oki1993].
There are some 144052 files (excluding duplicates) in the IFS archive; you are invited to explore and report back.
Incense debugger (pre-Cedar). [Myers1980]
Tioga document editor and typesetter. Designed by Bill Paxton.
Griffin illustrator. Originally on Alto; ported to Cedar. [Baudelaire1980]
Walnut email user agent. It used the Grapevine message transport system and stored messages in a Cypress database.
SolidViews three-dimenional interactive illustration. [Bier1986]
Gargoyle interactive illustration. [Pier1988]
Juno two-view constraint-based drawing program. [Nelson1985]
Etherphone voice transport, storage, and manipulation. [Swinehart1984], [Ades1986], [Etherphone1988]
Mockingbird music capture and composition. [Maxwell1981, 1983]
CaminoReal interative mathematical notebook and front-end for computer algebra systems (Reduce. SMP, and SAC-2). [Arnon1988]
Roadrunner production printing software. [Li1992], [Briggs2026]
Software for the DocuPrint NPS (and NPS/IPS) series of printers (internal name "Roadrunner") was written at CSL in PARC using Cedar running on a Sun Microsystems processor. The Cedar Imager was deployed as the imaging layer in the DocuPrint NPS/IPS series of products, driving Xerox production print engines covering the range from 50 PPM through 180 PPM monochrome, along with the highlight color engines (4850, 4890 as DocuPrint 350HC and DocuPrint 92C respectively) and the full color 60 PPM DocuPrint 2060. As installed, these systems were capable of printing Interpress, Postscript Level 2, PCL5e, and optionally IPDS data streams.
A condensed version of "A Tour through Cedar" appeared in: Proceedings of the 7th International Conference on Software Engineering (ICSE '84). IEEE Press, 1984, pages 181–195. ACM Digital Library
Josh Dersch. Darkstar. Emulator for Xerox Dandelion workstation, commonly known as the 8010 (when running Star or XDE), or 1108 (when running Interlisp-D).
Don Woodward. Dawn PrincOps D-machine emulator with XDE disk image.
Yasuhiro Hasegawa. Guam mesa-emulator. Can use disk images from Dawn (see above) or from GVWin (see below).
devhawala. Dwaarf Mesa machine emulator and Dodo Services.
***** Joe Pasqua. https://mastodon.social/@bitsplusatoms/113176827322915041