XPARC Algol dialect 

Xerox PARC, 1977.

System and application programming for proprietary hardware: Alto, Dolphin, Dorado and Dandelion.

Pascal-like syntax, Algol68-like semantics.

An early version was weakly typed. Mesa's modules with separately compilable definition and implementation parts directly led to Wirth's design for Modula. Threads, coroutines (fork/join), exceptions, and monitors. Type checking may be disabled.

Mesa was used internally by Xerox to develop ViewPoint, the Xerox Star, MDE, the Pilot Personal Operating System and the controller of a high-end copier.

It was released to a few universitites in 1985. Succeeded by Cedar.

Related languages
ALGOL 68 => Mesa   Implementation
Pascal => Mesa   Influence
Mesa => Cedar   Evolution of
Mesa => Modula-2   Influence
Mesa => Modula-3   Influence
Mesa => Pascal*   Influence
Mesa => Protel   Influence
Mesa => Zuse   Influence

  • Geschke et al, "Early Experience with Mesa" view details Abstract: The experiences of Mesa's first users—primarily its implementers—are discussed, and some implications for Mesa and similar programming languages are suggested. The specific topics addressed are: module structure and its use in defining abstractions, data-structuring facilities in Mesa, an equivalence algorithm for types and type coercions, the benefits of the type system and why it is breached occasionally, and the difficulty of making the treatment of variant records safe. DOI Extract: Introduction
    1. Introduction
    What happens when professional programmers change over from an old-fashioned systems programming language to a new, modular, type-checked one like Mesa? Considering the large number of groups developing such languages, this is certainly a question of great interest.

    This paper focuses on our experiences with strict type checking and modularization within the Mesa programming system. Most of the local structure of Mesa was inspired by, and is similar to, that of Pascal [14] or Algol 68 [12], while the global structure is more like that of Simula 67 [1]. We have chosen features from these and related languages selectively, cast them in a different syntax, and added a few new ideas of our own.

    All this has been constrained by our need for a language to be used for the production of real system software right now. We believe that most of our observations are relevant to the languages mentioned above, and others like them,, when used in a similar environment. We have therefore omitted a comprehensive description of Mesa and concentrated on annotated examples that should be intelligible to anyone familiar with a similar language. We hope that our experiences will help others who are creating or studying such languages.

    An interested reader can find more information about the details of Mesa elsewhere. A previous paper [7] addresses issues concerning transfer of control. Another paper [3] discusses some more advanced data-structuring ideas. A paper on schemes [8] suggests another possible direction of advance. In this paper we restrain our desires to redesign or extend Mesa and simply describe how we are using the language as currently implemented.

    The version of Mesa presented in this paper is one component of a continuing investigation into programming methodology and language design. Most major aspects of the language were frozen when implementation was begun in the autumn of 1974. Although we were dissatisfied with our understanding of certain design issues even then, we proceeded with implementation for the following reasons.

    -We perceived a need for a "state of the art" implementation langauge within our laboratory. It seemed possible to combine some of our ideas into a design that was fairly conservative, but that would still dominate the existing and proposed alternatives.

    -We wanted feedback from a community of users, both to evaluate those ideas that were ready for implementation and to focus subsequent research on problems actually encountered in building real systems.

    -We had accumulated a backlog of ideas about implementation techniques that we were anxious to try.

    It is important to understand that we have consciously decided to attempt a complete programming system for demanding and sophisticated users. Their own research projects were known to involve the construction of "state of the art" programs, many of which tax the limits of available computing resources. These users are well aware of the capabilities of the underlying hardware, and they have developed a wide range of programming styles that they have been loath to abandon. Working in this environment has had the following consequences.

    -We could not afford to be too dogmatic. The language design is conservative and permissive; we have attempted to accommodate old methods of programming as well as new, even at some cost in elegance.

    -Efficiency is important. Mesa reflects the general properties of existing machines and contains no features that cannot be implemented efficiently (perhaps with some microcode assistance); for example, there is no automatic garbage collection.

    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. It is in this context that we shall try to describe our experiences and to suggest some tentative conclusions. Naturally, we have discovered some bugs and omissions in the design, and the implemented version of the language is already several years from the frontiers of research. We have tried to restrain our desire to redesign, however, and we report on Mesa as it is, not as we now wish it were.

    The paper begins with a brief overview of Mesa's module structure. The uses of types and strict type checking in Mesa are then examined in some detail. The facilities for defining data structures are summarized, and an abstract description of the Mesa type calculus is presented. We discuss the rationale and methods for breaching the type system and illustrate them with a "type-strenuous" example that exploits several of the type system's interesting properties. A final section discusses the difficulties of handling variant records in a type-safe way.
    Extract: Modules
    2. Modules
    Modules provide a capability for partitioning a large system into manageable units. They can be used to encapsulate abstractions and to provide a degree of protection. In the design of Mesa, we were particularly influenced by the work of Parnas [10], who proposes information hiding as the appropriate criterion for modular decomposition, and by the concerns of Morris [9] regarding protection in programming languages.

    Module Structure
    Viewed as a piece of source text, a module is similar to an Algol procedure declaration or a Simula class definition. It typically declares a collection of variables that provide a localized database and a set of procedures performing operations upon that database. Modules are designed to be compiled independently, but the declarations in one module can be made visible during the compilation of another by arranging to reference the first within the second by a mechanism called inclusion. To decouple the internal details of an implementation from its abstract behavior, Mesa provides two kinds of modules: definitions and programs.

    A definitions module defines the interface to an abstraction. It typically declares some shared types and useful constants, and it defines the interface by naming a set of procedures and specifying their input/output types. Definitions modules claim no storage and have no existence at run time. Included modules are usually definitions modules, but they need not be.

    Certain program modules, called implementers, provide the concrete implementation of an abstraction; they declare variables and specify bodies of procedures. There can be a one-to-many relation between definitions modules and concrete implementations. At run time, one or more instances of a module can be created, and a separate frame (activation record) is allocated for each. In this respect, module instances resemble Simula class objects. Unlike procedure instances, the lifetimes of module instances are not constrained to follow any particular discipline. Communication paths among modules are established dynamically as described below and are not constrained by, e.g., compile-time or run-time nesting relationships. Thus lifetimes and access paths are completely decoupled.


    Mesa allows specification of attributes that can be used to control intermodular access to identifiers. In the definition of an abstraction, some types or record fields are of legitimate concern only to an implementer, but they involve or are components of other types that are parts of the advertised interface to the abstraction. Any identifier with the attribute PRIVATE is visible only in the module in which it is declared and in any module claiming to implement that module. Subject to the ordinary rules of scope, an identifier with the attribute PUBLIC is visible in any module that includes and opens the module in which it is declared. The PUBLIC attribute can be restricted by specifying the additional attribute READ-ONLY. By default, identifiers are PUBLIC in definitions modules and PRIVATE otherwise.

    [...]Abstraction contains definitions of shared types and enumerates the elements of a procedural interface. Implementer uses those type definitions and provides the bodies of the procedures; the compiler will check that an actual procedure with the same name and type is supplied for each public procedure declared in Abstraction.

    A module that uses an abstraction is called a client of that abstraction. Interface definitions are obtained by including the Abstraction module. Any instance of a client must be connected to an instance of an appropriate implementer before the actual operations of the abstraction become available. This connection is called binding, and there are several ways to do it.

    Binding Mechanisms
    A client module can request a system facility called the binder to locate and assign appropriate values to all external procedure names, such as px. The binder follows a well-defined binding path from module instance to module instance. When the binder encounters an actual procedure with the same name as, and a type compatible with, an external procedure, it makes the linkage. The compiler automatically inserts an EXTERNAL procedure declaration for any procedure identifier, such as p, that is mentioned by a client but defined only in an included definitions module. The binder also checks that all identifiers from a single definitions module are bound consistently (that is, to a single implementer).

    The observant reader will have noticed that this binding mechanism and the undisciplined lifetimes of module instances leave Mesa programs vulnerable to dangling reference problems. We are not happy about this, but so far we have not observed any serious bugs attributable to such references.

    As an alternate binding mechanism, Mesa supports the Simula paradigm [...where ] the client creates an instance of Implementer directly. Through a pointer to the frame of that instance, the client can access any public variable or invoke any public procedure. Note that the relevant declarations are in Implementer; the Abstraction module is included only for type definitions. Some of the binding has been moved to compile time. In return for a wider, not necessarily procedural interface (and potentially more efficient code), the client has committed itself to using a particular implementation of the abstraction. Because Mesa has procedure variables, it is possible for a user to create any binding regime he wishes simply by writing a program that distributes procedures. Some users have created their own versions of Simula classes.

    They have not used the binding mechanism described above for a number of reasons. First, the actual implementation of an abstract object is sometimes unknown when a program is compiled or instantiated; there might be several coexisting implementations, or the actual implementation of a particular object might change dynamically. Their binding scheme deals with such situations by representing objects as record structures with procedure-valued fields. The basic idea was described in connection with the implementation of streams in OS6 [11]: some fields of each record contain the state information necessary to characterize the object, while others contain procedure values that implement the set of operations. If the number of objects is much larger than the number of implementations, it is space-efficient to replace the procedure fields in each object with a link to a separate record containing the set of values appropriate to a particular implementation.

    We believe that we could not have built the current Mesa system if we had been forced to work with large logically monolithic programs. Assembly language programmers are well aware of the benefits of modularity, but many designers of high-level programming languages pay little attention to the problems of independent compilation and instantiation. Since these capabilities will be grafted on anyway, they should be anticipated in the original design. We have more to say about interfa.ce control in our discussion of types, but it is hard to overestimate the value of articulating abstractions, centralizing their definitions, and propagating them through the inclusion mechanism.

          in [ACM] CACM 20(08) (Aug 1977) view details
  • Horsley, Thomas R. and Lynch, William C. "Pilot: A software engineering case study" view details Abstract: Pilot is an operating system implemented in the strongly typed language Mesa and produced in an environment containing a number of sophisticated software engineering and development tools. We report here on the strengths and deficiencies of these tools and techniques as observed in the Pilot project. We report on the ways that these tools have allowed a division of labor among several programming teams, and we examine the problems introduced within each different kind of development programming activity (ie. source editing, compiling, binding, integration, and testing).

          in Proceedings of the 4th International Conference on Software Engineering 1979, Munich, Germany view details
  • Lauer, Hugh C.; Satterthwaite, Edwin H. "The impact of mesa on system design" view details Abstract: The Mesa programming language supports program modularity in ways that permit subsystems to be developed separately but to be bound together with complete type safety. Separate and explicit interface definitions provide an effective means of communication, both between programs and between programmers. A configuration language describes the organization of a system and controls the scopes of interfaces. These facilities have had a profound impact on the way we design systems and organize development projects. This paper reports our recent experience with Mesa, particularly its use in the development of an operating system. It illustrates techniques for designing interfaces, for using the interface language as a specification language, and for organizing a system to achieve the practical benefits of program modularity without sacrificing strict type-checking. Extract: Introduction

    Mesa is a programming language designed for system implementation. It is used within the Xerox Corporation both by research laboratories as a vehicle for experiments and by development organizations for "production' programming. Some of our initial experience with Mesa was reported previously [Geschke et al 1977]. Since that time, the language has evolved in several directions and has acquired a larger and more diverse community of users. That community has accumulated a substantial amount of experience in using Mesa tO design and implement large systems, a number of which are now operational. It has become increasingly clear that the value of Mesa extends far beyond its enforcement of type-safety within individual programs. It has profoundly affected the ways we think about system design, organize development projects, and communicate our ideas about the systems we build.

    This paper reports some of our recent experience with Mesa. It is based primarily upon the development of one particular system--what we refer to as the Pilot operating system--for a small, personal computer. We also draw upon the lessons learned from other systems. These represent a non-trivial amount of programming; a survey of just the authors' immediate colleagues at the end of 1978 uncovered several hundred thousand lines of stable, operational Mesa code. Pilot itself is a 'second generation' client of Mesa. It is the first major system to take advantage of explicit interface and configuration descriptions (discussed below) in its original design. In addition, its designers were able to make careful assessments of earlier systems to discover both the benefits and pitfalls of using Mesa. As a result, we were able to profit from, as well as add to, the accumulated 'institutional learning' about the practical problems of developing large systems in Mesa.

    The purpose of this paper is to communicate those lessons, which deserve more emphasis and discussion than they have received to date in the literature. We concentrate upon the impact and adequacy of the Mesa programming language and its influence upon system design; a comparison paper [Horsley and Lynch, 1979] focuses upon organizational and management issues. This paper contains three main sections. First, the facilities provided by Mesa for supporting the development and organization of modular programs are discussed. In the second section, we describe the role played by the Mesa interface and configuration languages in system design, particularly from the perspective of Pilot. The final section is a qualitative assessment of the adequacy of Mesa as a system implementation language.


    Mesa is both a language and a system. The Mesa language [Mitchell et al, 1979] features strict type-checking much like that of PASCAL [Wirth, 1971] or EUCLID [Lampson et al, 1977], with similar advantages and disadvantages. In particular, the type-checking moves a substantial amount of debugging from run-time to. compile-time. Much has been written on this subject; our views and design decisions have changed little since our earlier report [Geschke et al, 1977]. The type system of Mesa pervades all other aspects of the language and system. The latter consists of a compiler, a binder, a source language debugger, and a number of other tools and utilities. The system has been implemented on machines that can be microprogrammed at the register transfer level; thus we have also been able to design and implement a machine architecture specifically tailored to Mesa.

    The Pilot operating system upon which this report is based is programmed entirely in Mesa, as are all of its clients. In addition to providing the usual set of operating-system facilities, Pilot implements all of the run-time machinery needed to support the execution of Mesa programs, including itself. The clients are assumed to be friendly and cooperating, not hostile or malicious. Since no debugging takes place on machines that are simultaneously supporting other users, no attempt has been made to provide a strong protection mechanism; instead the goal has been to minimize the likelihood of uncontrolled damage due to residual errors. Pilot was designed and implemented by a core group of six people, with important contributions by members of other groups in specialized areas. By' late 1978, the total system consisted of approximately twenty-five thousand lines of Mesa code.
          in Proceedings of the 4th International Conference on Software Engineering 1979, Munich, Germany view details
  • Mitchell, J.G. et al, "Mesa Language Manual", Xerox PARC, CSL-79-3 (Apr 1979). view details
          in Proceedings of the 4th International Conference on Software Engineering 1979, Munich, Germany view details
  • Lampson, Butler W.; Redell, David D. "Experience with processes and monitors in Mesa" view details Abstract: The use of monitors for describing concurrency has been much discussed in the literature. When monitors are used in real systems of any size, however, a number of problems arise which have not been adequately dealt with: the semantics of nested monitor calls; the various ways of defining the meaning of WAIT; priority scheduling; handling of timeouts, aborts and other exceptional conditions; interactions with process creation and destruction; monitoring large numbers of small objects. These problems are addressed by the facilities described here for concurrent programming in Mesa. Experience with several substantial applications gives us some confidence in the validity of our solutions. Extract: Introduction and Replacing interrupts
    1. Introduction
    In early 1977 we began to design the concurrent programming facilities of Pilot, a new operating system for a personal computer [18]. Pilot is a fairly large program itself (24,000 lines of Mesa code). In addition, it must support a variety of quite large application programs, ranging from database management to internetwork message transmission, which are heavy users of concurrency; our experience with some of these applications is discussed later in the paper. We intended the new facilities to be used at least for the following purposes: Local concurrent programming. An individual application can be implemented as a tightly coupled group of synchronized processes to express the concurrency inherent in the application. Global resource sharing. Independent applications can run together on the same machine, cooperatively sharing the resources; in particular, their processes can share the processor.

    Replacing interrupts.

    A request for software attention to a device can be handled directly by waking up an appropriate process, without going through a separate interrupt mechanism (e.g., a forced branch). Pilot is closely coupled to the Mesa language [17], which is used to write both Pilot itself and the applications programs it supports. Hence it was natural to design these facilities as part of Mesa; this makes them easier to use, and also allows the compiler to detect many kinds of errors in their use. The idea of integrating such facilities into a language is certainly not new; it goes back at least as far as PL/I [1]. Furthermore the invention of monitors by Dijkstra, Hoare, and Brinch Hansen [3, 5, 8] provided a very attractive framework for reliable concurrent programming. There followed a number of papers on the integration of concurrency into programming languages, and at least one implementation [4].

    We therefore thought that our task would be an easy one: read the literature, compare the alternatives offered there, and pick the one most suitable for our needs. This expectation proved to be naive. Because of the large size and wide variety of our applications, we had to address a number of issues which were not clearly resolved in the published work on monitors. The most notable among these are listed below, with the sections in which they are discussed.

    (a) Program structure. Mesa has facilities for organizing programs into modules which communicate through well-defined interfaces. Processes must fit into this scheme (see Section 3.1).

    (b) Creating processes. A set of processes fixed at compile-time is unacceptable in such a general-purpose system (see Section 2). Existing proposals for varying the amount of concurrency were limited to concurrent elaboration of the statements in a block, in the style of Algol 68 (except for the rather complex mechanism in PL/I).

    (c) Creating monitors. A fixed number of monitors is also unacceptable, since the number of synchronizers should be a function of the amount of data, but many of the details of existing proposals depended on a fixed association of a monitor with a block of the program text (see Section 3.2).

    (d) WAIT in a nested monitor call. This issue had been (and has continued to be) the source of a considerable amount of confusion, which we had to resolve in an acceptable manner before we could proceed (see Section 3.1).

    (e) Exceptions. A realistic system must have timeouts, and it must have a way to abort a process (see Section 4.1). Mesa has an UNWIND mechanism for abandoning part of a sequential computation in an orderly way, and this must interact properly with monitors (see Section 3.3).

    (f) Scheduling. The precise semantics of waiting on a condition variable had been discussed [10] but not agreed upon, and the reasons for making any particular choice had not been articulated (see Section 4). No attention had been paid to the interaction between monitors and priority scheduling of processes (see Section 4.3).

    (g) Input-output. The details of fitting I/O devices into the framework of monitors and condition variables had not been fully worked out (see Section 4.2). Some of these points have also been made by Keedy [12], who discusses the usefulness of monitors in a modem general-purpose mainframe operating system. The Modula language [21] addresses (b) and (g), but in a more limited context than ours.

    Before settling on the monitor scheme described below, we considered other possibilities. We felt that our first task was to choose either shared memory (i.e., monitors) or message passing as our basic interprocess communication paradigm.

    Message passing has been used (without language support) in a number of operating systems; for a recent proposal to embed messages in a language, see [9]. An analysis of the differences between such schemes and those based on monitors was made by Lauer and Needham [14]. They conclude that, given certain mild restrictions on programming style, the two schemes are duals under the transformation
    message -> process
    process o monitor
    send/reply o call/return
    Since our work is based on a language whose main tool of program structuring is the procedure, it was considerably easier to use a monitor scheme than to devise a message-passing scheme properly integrated with the type system and control structures of the language. Within the shared memory paradigm, we considered the possibility of adopting a simpler primitive synchronization facility than monitors. Assuming the absence of multiple processors, the simplest form of mutual exclusion appears to be a nonpreemptive scheduler; if processes only yield the processor voluntarily, then mutual exclusion is insured between yield-points. In its simplest form, this approach tends to produce very delicate programs, since the insertion of a yield in a random place can introduce a subtle bug in a previously correct program. This danger can be alleviated by the addition of a modest amount of"syntactic sugar" to delineate critical sections within which the processor must not be yielded (e.g., pseudo monitors). This sugared form of non-preemptive scheduling can provide extremely efficient solutions to simple problems, but was nonetheless rejected for four reasons:
    (1) While we were willing to accept an implementation which would not work on multiple processors, we did not want to embed this restriction in our basic semantics.
    (2) A separate preemptive mechanism is needed anyway, since the processor must respond to time-critical events (e.g., I/O interrupts) for which voluntary process switching is clearly too sluggish. With preemptive process scheduling, interrupts can be treated as ordinary process wakeups, which reduces the total amount of machinery needed and eliminates the awkward situations which tend to occur at the boundary between two scheduling regimes.
    (3) The use of nonpreemption as mutual exclusion restricts programming generality within critical sections; in particular, a procedure that happens to yield the processor cannot be called. In large systems where modularity is essential, such restrictions are intolerable.
    (4) The Mesa concurrency facilities function in a virtual memory environment. The use of nonpreemption as mutual exclusion forbids multiprogramming across page faults, since that would effectively insert preemptions at arbitrary points in the program.
    For mutual exclusion with a preemptive scheduler, it is necessary to introduce explicit locks, and machinery which makes requesting processes wait when a lock is unavailable. We considered casting our locks as semaphores, but decided that, compared with monitors, they exert too little structuring discipline on concurrent programs. Semaphores do solve several different problems with a single mechanism (e.g, mutual exclusion, producer/consumer) but we found similar economies in our implementation of monitors and condition variables (see Section 5. l).
    We have not associated any protection mechanism with processes in Mesa, except what is implicit in the type system of the language. Since the system supports only one user, we feel that the considerable protection offered by the strong typing of the language is sufficient. This fact contributes substantially to the low cost of process operations.

          in [ACM] CACM 23(02) February 1980 view details
  • Redell, David D.; Dalal, Yogen K.; Horsley, Thomas R.; Lauer, Hugh C.; Lynch, William C.; McJones, Paul R.; Murray, Hal G.; Purcell, Stephen C. "Pilot: an operating system for a personal computer" view details Abstract: The Pilot operating system provides a single-user, single-language environment for higher level software on a powerful personal computer. Its features include virtual memory, a large "fiat" file system, streams, network communication facilities, and concurrent
    programming support. Pilot thus provides rather more powerful facilities than are normally associated with personal computers. The exact facilities provided display interesting similarities to and differences from corresponding facilities provided in large multi-user
    systems. Pilot is implemented entirely in Mesa, a high-level system programming language. The modularization of the implementation displays some interesting aspects in terms of both the static structure and dynamic interactions of the various components.
    Extract: Introduction and Pilot Interface
    I. Introduction
    As digital hardware becomes less expensive, more resources can be devoted to providing a very high grade of interactive service to computer users. One important expression of this trend is the personal computer. The dedication of a substantial computer to each individual user'suggests an operating system design emphasizing close user'system cooperation, allowing full exploitation of a resource-rich environment. Such a system can also function as its user's representative in a larger community of autonomous personal computers and other information resources, but tends to deemphasize the largely ajudicatory role of a monolithic time-sharing system.

    The Pilot operating system is designed for the personal computing environment. It provides a basic set of services within which higher level programs can more easily serve the user and/or communicate with other programs on other machines. Pilot omits certain functions that have been integrated into some other operating systems, such as character-string naming and user-command interpretation; such facilities are provided by higher level software, as needed. On the other hand, Pilot provides a more complete set of services than is normally associated with the "kernel" or "nucleus" of an operating system. Pilot is closely coupled to the Mesa programming langauge [16] and runs on a rather powerful personal computer, which would have been thought sufficient to support a substantial time-sharing system of a few years ago. The primary user interface is a high resolution bit-map display, with a keyboard and a pointing device. Secondary storage is provided by a sizable moving-arm disk. A local packet network provides a high bandwidth connection to other personal computers and to server'systems offering such remote services as printing and shared file storage.

    Much of the design of Pilot stems from an initial set of assumptions and goals rather different from those underlying most time-sharing systems. Pilot is a single-language, single-user'system, with only limited features for protection and resource allocation. Pilot's protection mechanisms are defensive, rather than absolute [9], since in a single-user'system, errors are a more serious problem than maliciousness. All protection in Pilot ultimately depends on the type-checking provided by Mesa, which is extremely reliable but by no means impenetrable. We have chosen to ignore such problems as "Trojan Horse" programs [20], not because they are unimportant, but because our environment allows such threats to be coped with adequately from outside the system. Similarly, Pilot's resource allocation features are not oriented toward enforcing fair distribution of scarce resources among contending parties. In traditional multi-user'systems, most resources tend to be in short supply, and prevention of inequitable distribution is a serious problem. In a single-user'system like Pilot, shortage of some resource must generally be dealt with either through more effective utilization or by adding more of the resource.

    The close coupling between Pilot and Mesa is based on mutual interdependence; Pilot is written in Mesa, and Mesa depends on Pilot for much of its runtime support. Since other languages are not supported, many of the language-independence arguments that tend to maintain distance between an operating system and a programming language are not relevant. In a sense, all of Pilot can be thought of as a very powerful runtime support package for the Mesa language. Naturally, none of these considerations eliminates the need for careful structuring of the combined Pilot/Mesa system to avoid accidental circular dependencies.

    Since the Mesa programming language formalizes and emphasizes the distinction between an inteoCace and its implementation, it is particularly appropriate to split the description of Pilot along these lines. As an environment for its client programs, Pilot consists of a set of Mesa interfaces, each defming a group of related types, operations, and error signals. Section 2 enumerates the major interfaces of Pilot and describes their semantics, in terms of both the formal interface and the intended behavior of the system as a whole. As a Mesa program, Pilot consists of a large collection of modules supporting the various interfaces seen by clients. Section 3 describes the interior structure of the Pilot implementation and mentions a few of the lessons learned in implementing an operating system in Mesa.

    2. Pilot Interfaces
    In Mesa, a large software system is constructed from two kinds of modules: program modules specify the algorithms and the actual data structures comprising the implementation of the system, while definitions modules formally specify the inteq'aces between program modules. Generally, a given interface, defined in a definitions module, is exported by one program module (its implementor) and imported by one or more other program modules (its clients). Both program and definitions modules are written in the Mesa source language and are compiled to produce binary object modules. The object form of a program module contains the actual code to be executed; the object form of a definitions module contains detailed specifications controlling the binding together of program modules. Modular programming in Mesa is discussed in more detail by Lauer and Satterthwaite [ 13].

    Pilot contains two kinds of interfaces:
    (1) Public interfaces defining the services provided by Pilot to its clients (i.e., higher level Mesa programs);
    (2) Private interfaces, which form the connective tissue binding the implementation together.

    This section describes the major features supported by the public interfaces of Pilot, including files, virtual memory, streams, network communication, and concurrent programming support. Each interface defines some number of named items, which are denoted Interface.Item. There are four kinds of items in interfaces: types, procedures, constants, and error signals. (For example, the interface File defines the type File. Capability, the procedure File.Create, the constant file.maxPages PerFile, and the error signal File. Unknown.) The discussion that follows makes no attempt at complete enumeration of the items in each interface, but focuses instead on the overall facility provided, emphasizing the more important and unusual features of Pilot.
          in [ACM] CACM 23(02) February 1980 view details
  • Lauer, Hugh C. "Observations on the development of an operating system" view details Abstract: The development of Pilot, an operating system for a personal computer, is reviewed, including a brief history and some of the problems and lessons encountered during this development. As part of understanding how Pilot and other operating systems come about, an hypothesis is presented that systems can be classified into five kinds according to the style and direction of their development, independent of their structure. A further hypothesis is presented that systems such as Pilot, and many others in widespread use, take about five to seven years to reach maturity, independent of the quality and quantity of the talent applied to their development. The pressures, constraints, and problems of producing Pilot are discussed in the context of these hypotheses.
          in Proceedings of the Eighth ACM Symposium on Operating Systems Principles, 1981, Pacific Grove, California, United States view details
  • Mitchell, James G. "Mesa from the perspective of a designer turned user" view details Abstract: The Mesa language and run-time environment were designed for the purpose of building systems programs such as compilers, operating systems, graphics software and so on. It is a relatively high-level language with strong type checking and supports the ideas of modular programming and abstract data types. Although the system is compiler-based, one can debug programs interactively in source-language terms. The language has been in rather heavy use since 1976 by a programming community of a few hundreds of professional programmers within the Xerox Corporation, and a large amount of code has been written in it. This talk will give a designer's retrospective view of Mesa from the vantage point of a serious user and will attempt to evaluate its strengths and weaknesses as a vehicle for systems programming. DOI
          in [ACM SIGAPL] APL Quote Quad 12(1) September 1981, Proceedings of the international conference on APL 1981, San Francisco, California, United States view details
  • Steensgaard-Madsen, J. " Statement-Oriented Approach to Data Abstraction" pp1-10 view details Extract: Introduction

    Programming languages traditionally offered procedures and functions as the only means of abstraction, that is, of providing powerful and high-level concepts while suppressing the details of their realization. The last ten years have seen many efforts to devise better abstraction facilities. SIMULA 67, Concurrent PASCAL, MODULA, CLU, and MESA are some of the newer languages offering abstraction mechanisms.

    The facilities offered by those languages are intended to hide by abstraction the interplay of different operations on the same data and to prevent access to the common data except by use of the abstract operations. Most researchers have looked to the type concept as a basis for an abstraction mechanism. However, no single type-based approach has been generally accepted.

    The approach taken in this paper differs from previous ones in a fundamental way. It is not based on a generalization of the type concept. Instead, the emphasis is on statements and procedures.

    The syntax we introduce is similar to that used for other proposed abstraction mechanisms. In order to avoid confusion, the reader must initially assume a simplified notion of types. A type is considered to be a set of values. From a theoretical point of view a type is considered to be a set component of an algebra, and a distinction is made between an algebra and its sets of values. This attitude differs essentially from Guttag and Horning's [5]. The algebra itself can be identified with other parts of this proposal, but this is not done explicitly here.

    This paper introduces the proposed language constructs in steps, each including examples. Section 2 concentrates on how to use an abstraction; it is divided into subsections of increasing complexity. Section 3, showing how abstractions are defined, is also subdivided according to complexity. Section 4 specifies the semantics using rewriting rules and thus indicates a possible implementation. Section 5 presents some final remarks.
          in TOPLAS 3(1) January 1981 view details
  • Johnsson, Richard K.; Wick, John D. "An overview of the mesa processor architecture" view details Abstract: This paper provides an overview of the architecture of the Mesa processor, an architecture which was designed to support the Mesa programming system. Mesa is a high level systems programming language and associated tools designed to support the development of large information processing applications (on the order of one million source lines). Since the start of development in 1971, the processor architecture, the programming language, and the operating system have been designed as a unit, so that proper tradeoffs among these components could be made.
          in [ACM] Proceedings of the first international symposium on Architectural support for programming languages and operating systems Palo Alto, California, United States March 1982 view details
  • Lampson, Butler W. "Fast procedure calls" view details Abstract: A mechanism for control transfers should handle a variety of applications (e.g., procedure calls and returns, coroutine transfers, exceptions, process switches) in a uniform way. It should also allow an implementation in which the common cases of procedure call and return are extremely fast, preferably as fast as unconditional jumps in the normal case. This paper describes such a mechanism and methods for its efficient implementation.
          in [ACM] Proceedings of the first international symposium on Architectural support for programming languages and operating systems Palo Alto, California, United States March 1982 view details
  • McDaniel, "Gene An analysis of a mesa instruction set using dynamic instruction frequencies" view details Abstract: The Mesa architecture is implemented on a variety of processors, and dynamic instruction frequency data for two programs is used to analyze the architecture in an implementation independent fashion. The Mesa compiler allocates variables in an order based upon their static frequency of use, and measurements are provided that show that these static predictions predict run time usage as well. We provide an evaluation of the advantages and costs of Mesa's compact byte encoding, its reliance upon an evaluation stack, and its use of memory. The Mesa language has evolved over time in a hardware environment oriented around 16-bit quantities with growing use of and accommodations to 32-bit quantities. The cost of emulating 32-bit data paths on a 16-bit machine is identified for a program that heavily exploits longer values. Several potential areas for improving the execution speed of a Mesa processor with special purpose hardware are identified. DOI
          in [ACM] Proceedings of the first international symposium on Architectural support for programming languages and operating systems Palo Alto, California, United States March 1982 view details
  • Nelson, Le Roy E and Harslem, Eric "A retrospective on the development of Star" view details Abstract: Star, officially known as the Xerox 8010 Information System, is a workstation for professionals, providing a comprehensive set of capabilities for the office environment. The Star software consists of just over 250,000 lines of code. Its development required 93 work years over a 3.5 year period. The development of Star depended heavily on the use of powerful personal computers connected to a local-area network and on the use of the Mesa language and development environment. An Integration Service was introduced to speed up the building of Star and to relieve the programmers of many complex, but repetitive, tasks.
          in Proceedings of the 6th International Conference on Software Engineering 1982 , Tokyo, Japan view details
  • Spector, David "Ambiguities and insecurities in Modula-2" pp43-51 view details Extract: Introduction
    While it is not yet clear whether Ada, BLISS, Mary/2, Modula-2, Mesa, C, CLU, Edison, Concurrent Euclid, Icon, Newton, PLAIN, PLUS, Praxis, Smalltalk, SQURL, Y, or some other language is "best" for systems programming, each language represents an advance towards the goal of supporting an understandable and efficient organization of the many details and relationships inherent in systems programming.
    Unfortunately, no one language has yet achieved the delicate balance between simplicity and power that would distinguish it as ideal, but it appears that Modula-2 comes quite close. Modula-2 represents a step forward in language design, both because it incorporates existing features instead of inventing its own, and because of its evident concern for simplicity.
    Modula-2 offers the following valuable language features:
    Few primitive datatypes are defined, few control constructs are supported (there is no "go to"), and input-output operations are not provided as part of the language (they can be provided via extensions written in Modula-2). This simplicity allows for easier standardization and better portability than can be achieved with most other languages.
    A module is a named collection of variables and procedures, similar to an Ada package. It controls the interfacing and encapsulation of the conceptual parts making up large software systems. Modules provide a more flexible solution to the problem of partitioning the name space of a large program than does the more familiar hierarchical nesting of procedures. They are so valuable they are even being force-fitted onto existing languages.
    Separate Compilation.
    Modules may be compiled separately, providing good management for large programsr and definition modules allow for specifying interfaces without giving implementation details.
    Flexible Datatypes.
    Strong datatypes are enforced, but this can be relaxed when necessary in systems programming to just declaring a parameter to be a word, an address, or an array of words.
    Machine Access.
    Access to specific memory addresses and other characteristics of the underlying machine is supported.
    Flexible and efficient tasking is provided by coroutine management routines.
          in SIGPLAN Notices 17(08) August 1982 view details
  • Sweet, Richard E. and Sandman, James G. Jr. "Empirical analysis of the mesa instruction set" view details Abstract: This paper describes recent work to refine the instruction set of the Mesa processor. Mesa [8] is a high level systems implementation language developed at Xerox PARC during the middle 1970's. Typical systems written in Mesa are large collections of programs running on single-user machines. For this reason, a major design goal of the project has been to generate compact object programs. The computers that execute Mesa programs are implementations of a stack architecture [5]. The instructions of an object program are organized into a stream of eight bit bytes. The exact complement into of instructions in the architecture has changed as the language and machine micro architecture have evolved. In Sections 3 and 4, we give a short history of the Mesa instruction set and discuss the motivation for our most recent analysis of it. In Section 5, we discuss the tools and techniques used in this analysis. Section 6 shows the results of this analysis as applied to a large sample of approximately 2.5 million instruction bytes. Sections 7 and 8 give advice to others who might be contemplating similar analyses. DOI
          in [ACM] Proceedings of the first international symposium on Architectural support for programming languages and operating systems Palo Alto, California, United States March 1982 view details
  • R.P. Cook and T.J. LeBlanc "A Symbol Table Abstraction to Implement Languages with Explicit Scope Control" from IEEE Transactions on Software Engineering, January 1983 view details
          in [ACM] Proceedings of the first international symposium on Architectural support for programming languages and operating systems Palo Alto, California, United States March 1982 view details
  • Ichbiah, Jean D.; Barnes, John G.P.; Firth, Robert J.; Woodger, Mike "Ada 83 Rationale" HONEYWELL, Systems and Research Center, Minneapolis, and ALSYS La Celle Saint Cloud, France January 31, 1984 view details Extract: Separate compilation
    Separate compilation of program units is a practical necessity. Its basic goals are to permit the separation of large programs into simpler, more manageable parts, and to create libraries of program units. Separate compilation helps to reduce compilation costs and to simplify the development and management of program corrections and modifications.
    For large projects involving several programmers, separate compilation permits program texts to be separated physically in a way that reflects the division of work and responsibilities. Once the common interface between two parts has been agreed upon and recorded, the two parts can be developed and compiled separately. The fact that the common interface is a physically separate text guarantees that separate recompilation of either part does not invalidate the common interface.

    The physical separation of program texts may be viewed as a support facility for the structured programming concept of refinement. It may also be used to conceal the text of a subprogram body from users who are only allowed to call the subprogram. Such concealment may be justified either for reasons of confidentiality or in order to prevent the user from inferring implicit properties or making assumptions regarding the functioning of the subprogram. Finally this physical separation facilitates the construction of libraries and reusable software components.

    It is appropriate at this stage to introduce the distinction between independent and separate compilation (following J.J. Horning). Independent compilation has been achieved by most assembly languages and also by languages such as Fortran and PL/1. Compilation of individual modules is performed independently in the sense that the modules have no way of sharing knowledge of properties defined in other modules.

    Independent compilation is usually achieved with a lower level of compile-time checking of consistency between units than is possible within a single compilation unit. In consequence, independent compilation came into disrepute and was rejected by safety-minded early typed language definitions such as Algol 68 and Pascal. Fast compilation of the complete program was often advocated by promoters of these languages as a safe alternative to independent compilation. However, fast compilation has its limits, and it fails to answer the needs of confidentiality and libraries.

    Separate compilation, on the other hand, reconciles type-checking safety and the pragmatic reasons for compiling in parts. It is based on the use of a program library which contains a record of previous compilations of the units that form a program. It has been developed in the language Sue and in later languages such as Lis, Jossle, Mesa and later extensions of Pascal and Algol 68. We next discuss its properties in terms of what is provided in Ada.

    When a program unit is submitted to the compiler, the compiler also has access to the program library and is therefore able to perform the same level of checking (in particular type checking) whether a program is compiled in many parts or as a whole. It is the existence of the program library that makes the compilation separate but not independent.

    Using the general information available in the program library, the compiler will be able to assist the user in organizing recompilations. In particular, it will be able to display information about the current state of the compilation of a program that is divided into several compilation units: which separate program units have been compiled, and which need to be recompiled because of prior recompilations.

    It is thus for reasons of safety and utility that Ada offers a powerful facility for separate compilation. Two additional criteria have been followed in this design, namely simplicity of use and simplicity of implementation.

    Separate compilation being a user-oriented facility, it should be simple to understand and use. Consequently it should not introduce other concepts than those required by the nature of separate compilation. Scope rules and the general form of separately compiled program units should be similar to those of other program units.

    In addition, separate compilation should be implementable simply and efficiently. The additional work required for separate compilation should stay within reasonable limits, since one of the goals is to save overall compilation and recompilation time.

          in [ACM] Proceedings of the first international symposium on Architectural support for programming languages and operating systems Palo Alto, California, United States March 1982 view details
  • Sweet, Richard E. "The Mesa programming environment" view details Abstract: People everywhere are developing multi-window, integrated programming environments for their favorite computers and languages. This paper describes the Mesa programming facilities of the Xerox Development Environment (XDE). It is interesting for several reasons. It has existed in something similar to its current form for about 5 years. It has more than 500 users, many interacting with it 8 or more hours a day. Several million lines of code have been written by these users, including large, multi-author systems. Previous papers have dealt with the Mesa language, the operating system [Redell79, Lampson80] and the processor architecture on which it runs. This paper describes the programming environment: the user illusion, the set of programming tools, and the facilities available for augmenting the environment. Section 2 gives a short history of the environment, including some of our original design goals. Section 3 describes the current state of the user interface and discusses a few of the schemes that were tried and discarded. Section 4 describes some of the program development tools available and discusses how features of the language have influenced their design, and indeed influenced what tools are in the set. Section 5 describes other tools that, although valuable to the programming task, are largely language independent. Section 6 talks about how easy it is to make additions to the system, and gives examples of user additions—some that modify the environment and some that simply provide new tools. Section 7 discusses what we feel are major successes and what we feel needs to be done in the future.
          in SIGPLAN Notices 20(07) July 1985 (Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments) view details
  • Dewan, Prasun AND Solomon, Marvin "An approach to support automatic generation of user interfaces" view details Abstract: In traditional interactive programming environments, each application individually manages its interaction with the human user. The result is duplication of effort in implementing user interface code and nonuniform—hence confusing—input conventions. This paper presents an approach to support automatic generation of user interfaces in environments based on algebraic languages. The approach supports the editing model of interaction, which allows a user to view all applications as data that can be edited. An application interacts with a user by submitting variables (of arbitrary types) to a dialogue manager, which displays their presentations to the user and offers type-directed editing of these presentations. Applications and dialogue managers communicate through a protocol that allows a presentation to be kept consistent with the variable it displays. A particular implementation of the approach, called Dost, has been constructed for the Xerox development environment and the Mesa programming language. Dost is used as a concrete example to describe the editing model, the primitives to support it, and our preliminary experience with these primitives. The approach is compared with related work, its shortcomings are discussed, and suggestions for future work are made. DOI
          in TOPLAS 12(4) October 1990 view details
    • Programming languages and compilers by Butler Lampson
      Mesa (1972-79): With Jim Mitchell, Chuck Geschke and Ed Satterthwaite, I designed this programming language [13, 23; Geschke et al., Early experience with Mesa, Comm. ACM 20, 8 (Aug. 1977), pp 540-553; Mitchell et al., Mesa Language Manual, Technical Report CSL-79-5, Xerox PARC, 1975]. It is based on Pascal, but has unified facilities for coroutines and parallel processes, and for specifying interfaces among many modules in a large system. I designed much of this.external link