Paul McJones, editor
paul@mcjones.org
https://mcjones.org/dustydecks/
Last modified 29 January 2026
The goal of this project is to preserve the history of the Mesa family of system programming languages designed at Xerox PARC in the 1970s—MPL, Mesa, and Cedar—via primary and secondary source materials including specifications, source code, manuals, memos, and papers.
***** Items flagged like this are reminders to the author of things needing follow-up
***** PDFs of papers from the Charles Irby Papers (Stanford Special Collections M0671) await clearance by authors
In order to understand the environment in which Mesa was designed 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) and 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 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). Several graduate students worked on ALGOL W; one of them 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, including a project for the AN/FSQ-32 computer at System Development Corporation in Santa Monica, California. He also issued a small grant to Huskey and David Evans (1924–1998), who Huskey had recruited to Berkeley 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 at SDC, 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, a systems programming language for the SDS 940 [Deutsch1967].
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 Taylor 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 was able to continue funding Engelbart. Engelbart slowly 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 editing documents and holding 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 production system. ARPA would only fund early research, so they started 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. Inspired by QSPL, it was a more powerful and polished language [Lampson1969].
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) [Footnote 1]. 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." Bob 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 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 (see [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 2]. 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 was built using tools developed at SRI. MOL940 was a machine-oriented language with an ALGOL-like syntax, somewhat like Wirth's PL360 [Hay1968]. 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 L10. 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 use Tree Meta notation for syntax.
The PARC researchers wanted a 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 NLS PDP-10 at SRI.
The design for MPL 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]. This undated document described an intriguing system. A module would contain a set of ports, each labeled with an identifier and tagged with a type: apparently two record types, describing 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 would 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.
The data model was similar to QSPL or BCPL: single-word types, no differentiation between integers and pointers, integer arrays, bit-oriented field definitions. Declarations were Algol-like, introduced with the word 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, which 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).
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 on 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 a high-level overview. Perhaps it was a proposal that wasn't implemented at the time, because the later [Satterthwaite1974a] described a simpler language that seems to have actually existed at the time it was written [Footnote 3]. The global structure of the language was relatively unchanged. There was still no way to define an interface to 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, 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 keyword MODE was used instead of TYPE. 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. The mechanisms (including heap-allocated frames) described in this report became part of the Mesa virtua machine specification [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. And [Lampson1983a] says "Use of ports is complex, unsafe and not recommended."
[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.
***** Ed: Do you recall discussions about the following language features mentioned in [Lampson1974]?
"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 MDS Debugger (this is, of course, a first draft)" 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,24,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."
The document erroneously says "1/3/72".
***** Ed: When were DEFINITIONS modules added? [Deutsch1972a] says:
"We have in mind that during early development of a program, when the human overhead of writing declarations might be onerous, and also in those few cases where it is impossible to specify the interface properly within the language, we will have some kind of interpretive mechanism which will verify the compatibility of data across control interfaces at run time."
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 underway, and the system was being used fairly widely within 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.
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."
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, a PDP-10 clone). The dynamic measurements were then used with 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 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 1976 paper "Early Experience With Mesa" reported [Geschke1976a]:
"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 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. The original Alto operating system was written in BCPL and assembly language. As part of the effort to port Mesa to the Alto, Richard Johnsson and John Wick wrote a Mesa operating system that could interoperate with the BCPL file system and provided a debugger, display services, stream I/O, etc.
As the native Alto version of the Mesa compiler was being finished during 1976, the cross-compiler that ran on MAXC and generated code for the Alto was available to users as well as the Mesa development team, but there were frequent releases of the native Alto version. On 1 December 1976 the TENEX version of the Alto/Mesa compiler was deleted, and the Alto version was officially released. The extensive system documentation included a reference grammar for the language; apparently a Mesa Language Manual, Version 1.0, had been 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:
Date: 10 JAN 1977 0947-PST From: JENKINS Subject: DEALER, Tuesday, 11 January 1976 To: PARC/SDD: Niklaus Wirth of CSL will talk about Joys and Perils with Mesa on Tuesday, 11 January 1976 at 1:15 pm, CSL Common. ABSTRACT: I have recently studied Mesa in the recommended and popular "do it" manner. As Mesa will have to be learned by many Xerox programmers in the near future, perhaps a report about a novice's successes and frustrations will be of interest. I will comment on some language features and relate them to similar constructs in Pascal.
In 1992, he 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]
"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."
***** Were any of these ideas implemented in Mesa? E.g., types and constants as record fields, generic procedures (overloaded on argument/result types). Note the single reference to "MPL," at the bottom of page 32.
"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.
While the original MPL compiler generated standard PDP-10 machine instructions, the Alto offered a challenge and an opportunity. The challenge was a small address space: 16-bit addresses and 16-bit words. The opportunity was the Alto's writable control store, allowing 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].***** Is there more to say about packed records or ... ?
***** Does Ed have more to say about this?"In 1977 (Mesa 3.0), we introduced strong intermodule type checking by means of interfaces and the Binder. The ability to check procedure parameters at compile or load time was a clear win. It often took a while to produce a consistent version of a large system, but once it could be loaded, it would usually run well enough that the programmer could start looking for logic errors. The early days of binding are described in some detail in a paper by Lauer and Satterthwaite [Lauer1979]." [Sweet1985]
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, and was later standardized as IEEE POSIX Threads.
Alto/Mesa used 16-bit word addresses to access variables in local and global frames and heap zones. A special version, XMesa, supported the 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. But eventually the needs of garbage collection and other changes led to incompatibility at the virtual machine level and higher. The development of Cedar is covered in the section The Cedar Language below. Mesa became part of the Xerox Development Environment, which included ...
"The Pilot/Tajo programming environment was used within Xerox to create the Star and Viewpoint office systems, and later became the Xerox Development Environment (XDE) product, marketed by the Xerox Information Systems Division." [Swinehart1986]
***** WALLACE, D. Tajo Functional Specification, version 6.0. Xerox internal document, Oct. 1980.
***** [Sweet1985]
***** https://bitsavers.org/pdf/xerox/xde/
"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].)
"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.
***** Look through CSL reports for more
***** Add http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-77-1_Schemes_-_A_High_Level_Data_Structuring_Concept_197701.pdf ?
***** http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-79-12_Violet_an_Experimental_Decentralized_System.pdf
***** http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-79-14_Weighted_Voting_for_Replicated_Data.pdf
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 8 MByte or more memory, would allow the design of large, integrated systems combining text, graphics, audio, and more. [Lampson1980b], [Pier1983].
An effort was initiated with the Computer Science Laboratory to take stock of the three main environments in use at PARC (Interlisp, Mesa, and Smalltalk) and plan for the future [EPEWG], Deutsch1980]. 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.
- Mesa 5C1
- 1 September 1979: see [CLFDC1979]
- Mesa 5C2
- Series of proposals from October 1979 through January 1980
- Mesa 6C2
- 15 February 1980: see [CLFDC1980]
- 6C2 Atom amendment
- 22 April 1980: see [Horning1980]
- Processes
- 2 April 1980—coexistence with the garbage collector: see [Birrell1980]
- Signalling
- 7 May1980—exception handling within layered abstractions: see [Levin1980]
- Mesa 6T5
- 16 January 1981—"a partial implementation of Mesa 6C2": see [CLFDC1981]
- Cedar 7T7
- 20 May 1981—syntax for discriminated types; type discrimination; ROPE literals: see [Satterthwaite1981a]
- Cedar 7T10
- 18 December 1981—predeclared types BOOL, CHAR, INT; numeric types and conversions; escape convention for text literals; APPLY and RETURN: see [Satterthwaite1981b]
- Cedar 7T11
- 15 February 1982—dynamically typed procedures; SAFE/UNSAFE and CHECKED/TRUSTED/UNCHECKED: see [Satterthwaite1982]
The resultant Cedar language extended Mesa with [Anonymous1986]:
[Rovner1984] discussses implementation details for garbage collection and runtime types. [Owicki1981] presents the formal specifications of garbage collection that were used to define the safe subset of Mesa.
Having evolved over a decade including its MPL and Mesa roots, Cedar was a large and complex language, and documenting it was a challenge. This challenge was approached in two ways:
[Burstall1984] notes:
"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. This led to the System Modeling project [Lampson1980c, d], [Lampson1983b, c], [Schmidt1982a, b], at the center of which was SML, the System Modelling Language. 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."
***** Review/incorporate remaining documents from [_CD8_]<cedardocs>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 the work of 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]
Ib February 1981 a project review was carried out [Ayers1981].
Jim Morris. Cedar Status. 19 February 1981. [_CD8_]>cedardocs>status.memo!2
R. Ayers, F. Baskett, P. Deutsch, C. Geschke, J. Warnock, J. Wick, J. Morris (editor). Internal Review of Cedar. 19 February 1981. [_CD8_]>cedardocs>review.memo!4
Cedar, like Mesa before it, was implemented using a specialized virtual machine implemented in microcode and ran on the Dorado and the Dandelion (a 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 intermediate 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.
Remote procedure call extends familiar synchronous procedure calls to span address space and machine boundaries. A program transformation tool ([Nelson1982]) transforms an interface (Mesa DEFINITION module) into client-side and server-side stubs 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.
***** [Weiser1989], [Li1992], [Hauser1993], ...
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
See Appendix B of [Swinehart1986] for table of releases from 1 to 6.0.
"No Copilot dependencies, Abstract Machine, world-swap debugging, performance improvements, Alpine transaction file server introduced" [Swinehart1986, Appendix B]
"Cedar off Pilot base, FS, VM, Safe Storage, IO, four major layers: Machine, Nucleus, Life Support, Applications" [Swinehart1986, Appendix B]
"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." [Swinehart1986]
A major change was the replacement of the Cedar Graphics package by the Imager. See [Swinehart1986, section 9.1].
*****
The Cedar language was used for many additional research projects running on the Dorado and other "D-machines."
***** Add more Cedar papers and reports, for example from here: https://xeroxparcarchive.computerhistory.org/Xerox_PARC_source_code.html#Cedar/Mesa
Brad Myers: Incense https://bitsavers.org/pdf/xerox/parc/techReports/CSL-80-7_Displaying_Data_Structures_for_Interactive_Debugging_198006.pdf
Alpine database
Tioga document editor
Griffin illustration program
Walnut email client
Eric Bier?
***** See https://github.com/rochus-keller/Cedar
***** Add Josh Dersch's Mesa emulator?
***** Move this to the front, and provide abbreviations for each archive, for use in link anchors
***** Add xeroxparcarchive.computerhistory.org and bitsavers.org as archives
Thanks to Ed Satterthwaite for his recollections of MPL, Mesa, and Cedar, Al Kossow for bitsavers.org, and Charles Irby for donating his papers:
Charles H. Irby Papers, 1962–1975, Stanford Libraries Special Collections, M0671. Finding aid at Online Archive of California