THE MESA PROGRAMMING ENVIRONMENT
THE MESA PROGRAMMING ENVIRONMENT
THE MESA PROGRAMMING ENVIRONMENT
The Mesa Programming Environment
Richard E. Sweet
1.    Introduction
People everywhere are developing multi-window, integrated programming environments for their favorite computers and languages.  
This paper describes the Mesa programming environment, also known as the Xerox Development Environment (XDE).  It is interesting 
for several reasons. It has existed in something similar to its current form for about 4 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 [2] [12], the operating system [13] [9] and the processor architecture on which 
it runs [4] [15].  This paper describes the programming environment: the user illusion, the set of programming tools, and the 
facilities available for augmenting the environment.
2.    History
Much of the early history and design motivation behind the Mesa project was reported earlier [2].  Below is a list of language 
features and design goals that have enabled or directed our development:
·    Mesa supports modular programming with strong compile-time type checking.
·    In 1977, we introduced strong intermodule type checking by means of interfaces.
·    Procedures are first class values; they can be passed as parameters or stored in data structures.
·    We have a commitment to source level debugging.
·    There is sufficient runtime efficiency and access to underlying architecture that all levels of the system may be written in a 
high level language.
Mesa was first implemented on the Alto [17] in 1976.  Around 1978, a "Tools" project was started to design a software development 
environment.  This project was later merged into the Mesa project, and the user interface portion was named Tajo (pronounced 
TAH-hoe).  Its design was influenced significantly by previous work of Kay [5] [6] and of Swinehart [16].  Several basic precepts 
from the 1980 Tajo Functional Specification were:
·    Client programs shall not preempt the user.  The user should never be forced into a situation where the only thing he can do 
is interact with only one tool.
·    Don't call us, we'll call you.  A tool should arrange for Tajo to notify it when the user wishes to communicate some event to 
the tool, rather than adopt an "ask the user for a command and execute it" model.
·    The user owns the window layout.   Individual tools should make minimal assumptions about the size and position of any windows 
that they own.  The procedural interface to writing on windows should make such concerns largely invisible to the client code.
There is another important point.  By this time, the Mesa project had moved from corporate research into a development 
organization.  While some of the same designers worked on it in both places, there was now a definite engineering orientation to 
the effort.  Several times a 90% solution was implemented since it could be done today, rather than wait until we understood how to 
solve the problem completely.
3.    User Illusion 
For the use of multiple tools in multiple windows to be most effective (for changing activities quickly and easily), the user 
interface should be consistent across all tools.  The perceptions, model, and conjectures that a user accumulates about a system 
are referred to as the "user illusion."  Tajo strives to create a consistent user illusion that enables the user to predict how to 
use any tool, regardless of previous exposure to it.
The hardware environment has a bitmap display and a mouse.  The display is large enough, 17-inch display with 1024 by 808 pixels, 
to support multiple activities at once.  The mouse has either two or three buttons.  In the two-button case, the software simulates 
a push of the middle button when the other two buttons are "chorded."
This section describes the current (Mesa 11.0) version of Tajo.
3.1    Windows
Interaction with the user is through windows on the screen.  A window is a rectangular area of the screen, and may be covered with 
subwindows, resulting in a window tree.  Each window has a position relative to its parent and a size.  Windows at the "top level" 
are subwindows of a system supplied full-screen root window.  Windows can overlap arbitrarily; the rules for visibility of windows 
are determined by the tree structure.  
Each window has an associated window object which is accessed by a pointer called a window handle.  The object contains information 
about the tree structure, this window's relative location, and procedure variables, such as a repaint procedure that is called 
whenever a portion of the window has invalid contents.  Mesa's opaque type mechanism is used so client programs need not know the 
actual representation of a window object. 
Client programs can attach additional information to windows by means of named contexts, similar to property lists of LISP.  Tools 
can be written to have multiple instances, obtaining their data from the context associated with the particular window that Tajo is 
notifying (passed as a parameter to the notify procedure).  See §3.4 for further details.
To simplify the task of the tool writer, there are several system-provided subwindow types, each with its own runtime management 
routines.   The three most popular types for incorporating in tools are the following:
·    A message subwindow is used for limited feedback to the user, such as error conditions.  It typically has only a few lines, 
and as information scrolls off the top it is discarded.
·    A file subwindow is used by tools that want to create a log of their operations.  The client program writes to the log with 
stream operations.  As characters are written to the log, they appear on the screen and also go into the file.  Built-in management 
routines take care of line breaking, scrolling, window splitting, and selection.
·    A form subwindow is the major work horse for the interactive portion of a tool's user interface.  These windows can contain 
form fields to be filled in (with either text or numbers), choices to be made (either by menus or one-of-many selection on the 
screen), and command buttons to be invoked with the mouse.
3.2    Tool state
When a tool has its full-sized window open on the screen, it is said to be in an active state.  Tools that will not be needed for a 
while can be shrunk to an iconic form on the screen; such tiny window typically retain all window state, such as parameters that 
the user has given the tool, options selected, or messages posted by the program.  The third state for tools is inactive.  When 
tools are inactive, they disappear from the screen entirely.  By convention, they free up any system resources that they are using.
The tool data contains a client supplied transition procedure that gets called whenever the tool changes state.  System-defined 
subwindow types such as form subwindows have system supplied transition strategies that "do the right thing."
3.3    Selection
Two mouse buttons are used for selection.  The left button, called point, is used to begin the selection.  When point is depressed, 
the closest character is selected (video inverted), and the selection tracks the mouse until the button is released.  Units larger 
than a single character are selected by multiple clicking. If the left button is pressed twice in rapid succession, the selection 
mode becomes word-selection.  Three clicks get lines, and four clicks selects the entire document.  Multiple clicks cycle through 
the selection modes, so a 5-click is equivalent to a single click. 
The right mouse button, called adjust, is used to extend or contract the selection.  Pressing adjust causes the closest end of the 
current selection to move to the cursor position, subject to selection mode constraints (e.g., to the end of the current word if in 
word mode).  As with point, the selection tracks the cursor and "commits" on the up transition.
Other selection schemes have been tried and discarded.  They include draw-through selection and separate character and word select 
buttons.  Other indications of selection were tried as well, including underline and box-around.
3.4    Keyboard
The keyboard of the Dandelion is non-encoded; there is a region of memory from which a program can read the current up/down state 
of each key.  Very few applications deal with the keyboard at this level; they use a facility called TIP (for terminal interface 
package).  At the heart of this package is a collection of TIP tables, user editable descriptions of desired operations for 
specified user actions.  These tables are associated with windows in a tree structure.  Every time a user action (key transition, 
button transition, or mouse movement) occurs, the TIP software determines which window that event "is for" and looks up the event 
in the chain of tables associated with that window.  If it finds the event, it passes the corresponding operations to that window's 
associated notify procedure.
3.5    Menus
Another means for user interaction is via menus.  Rather than have a single large menu, there are several menus available at any 
time, determined by the subwindow that contains the cursor.  System supplied subwindow types have their own sets of menus, such as 
a text operations menu for a typescript subwindow.  The set of available menus is obtained by depressing the middle mouse button. 
Menus are stacked in such a way that the user can either invoke a menu item from the top menu or cause another menu to come on top. 
From the programmer's standpoint, menus are easy to construct.  A system procedure is given a window handle and an array of 
<STRING, PROCEDURE> pairs.  The strings become the menu items, and the corresponding procedure is called whenever the user selects 
that item.
Menus can provide many commands without requiring the user to remember the exact command names.  For frequently used operations, it 
is cumbersome to remember which menu contains the desired command, bring it to the front, and select the item.  One solution to 
this problem is symbiote subwindows.  They appear at the top of other windows and contain a list of identifiers, typically command 
names.  When the user clicks the mouse button on one of these identifiers, the symbiote's notify procedure searches through all the 
item names from the collection of menus on the other subwindows of their window.  If it finds a match, it calls the corresponding 
procedure. 
4.    Programming Tools
The previous section described the user illusion of XDE; this section describes some of the Mesa program development tools that 
made it possible to develop such an environment.  The major thrust of this section is that the various tools are highly 
interrelated; each one either produces extra information for use by others or makes use of such information.
4.1    Runtime loader
The runtime loader is technically not a programming tool, but rather a part of the Pilot operating system kernel.  Nevertheless, in 
order to understand the other programming tools, some knowledge of the runtime loader is needed.
A Mesa object program has, in addition to code, a header that specifies a list of interfaces that are imported or exported.  These 
interfaces are the "glue" that holds modules together into larger programs, as described in detail elsewhere [12] [10].  The 
runtime loader maintains a database of all interfaces imported and exported by programs now loaded (either part of the original 
boot file or previously runtime-loaded).  Loading a new module is a three step process:
1.    Move the code from the object file into virtual memory.
2.    For all interfaces imported by this program, see if there is something already loaded that exports the desired items.
3.    For all interfaces exported by this program, see if there is something already loaded that wishes to import any items 
exported.
Note that the loader is capable of many of the tasks typically associated with the linkage editor of a more batch oriented system.
When run, most programs either create windows for interaction or register commands with the Executive (or both) and then simply 
return.  Once a program is loaded, it usually stays around forever (or until the next boot, which may be a week or two away).  
There is, however, an unloader that goes through the three steps in the reverse order.  Thus is it possible to load two highly 
interconnected modules, decide that one is buggy, unload it, make repairs, load the new one, and have the interconnections now 
properly made to the new module. 
4.2    Compiler
The Mesa compiler generates code for a stack architecture [4] that is emulated in microcode on the Dandelion.  There is no separate 
assembler; all portions of the system, down to the 512 byte bootstrap loader, are written in Mesa.
The unit of compilation is the Mesa MODULE.  This is typically a collection of procedure declarations, together with global 
variable declarations, and sometimes a small amount of mainline code.  At the beginning of the source program, there is a 
declaration of those interfaces that are imported or exported by this module.  As mentioned in §4.1, the compiler must produce a 
header on the object file that provides this import/export information to the loader. 
The code and the binding information are all that are really needed for execution of a module.  However, additional information is 
needed to support source-level debugging.  The compiler writes out most of the compile-time symbol table for use by the debugger 
and performance tools.  Unlike some symbol table structures [3], Mesa symbol tables are organized in such a way that no information 
useful to debugging is destroyed in the compilation process.
The compiler also provides a source-to-object mapping facility used by the debugger and various performance measuring tools.
What about optimization?  In a nutshell, the Mesa compiler doesn't do a lot of optimization that rearranges the order of execution; 
when it does destroy the ability to do source/object mapping, it tries to arrange things so that the debugger can give the user 
feedback that this has happened.   This is an example of a "90% solution."
4.3    Binder
The output of the compiler is an object file containing the code for a single module.  For many reasons, interesting programs are 
made up of more than one module.   While the runtime loader is capable of linking together separately loaded modules, most medium 
to large systems are distributed as a single object file put together by a separate program called the Binder.  This is done for 
several reasons:
·    It is easier to keep track of one file instead of 50.
·    Resolving the linkage between modules is a time consuming process; with a bound configuration, the loader need only take time 
to resolve external linkage requirements.
·    Interfaces can be obscured from other programs by binding the programs exporting them into a configuration that does not 
export that interface.
·    The symbol table and debugging information produced by the compiler occupy a lot of space.  The Binder need not copy this into 
the new object file, but need only change the header of the new object file to point to the file or files containing this 
information.
The input to the binder is a configuration description that contains a list of object file names, a list of interfaces to be 
imported and exported, and optional information directing how the internal bindings are to be done.  Experience has shown that 
elaborate schemes for programmer directed binding are almost never used.
4.4    Debugger
Mesa has a full-function source-level debugger that is used for debugging all levels of the system, including the operating system 
kernel.  The debugger uses the symbol table and statement mapping information produced by the compiler.  Its features include the 
following:
·    The ability to set breakpoints.  To set a breakpoint, the user loads the source file into a window, selects a place in the 
file, and executes a SetBreak menu command.  As feedback, the debugger changes the selection to be the first character of the 
statement where the breakpoint is set.
·    The ability to interrupt a running program and find the execution state of any process.  Equally important, it is possible to 
resume execution of a program interrupted in this fashion.
·    The ability to walk up the links of the dynamic call chain, answering the question "Who called whom."
·    The ability to examine and modify data in the client program.  Since Mesa is strongly typed, the debugger can use type 
information to print out the values in a more understandable fashion.  Numeric types print as numbers, enumerated ones as the 
proper named value, and records print out as a list of field names, each with its value printed according to type.
·    The ability to call procedures in the client program, type checking the actual arguments against the types of the formal 
parameters.
The Mesa debugger evolved from the Alto implementation and still uses the world swap principle [8] for insulating the debugger from 
the client code.  As the size of physical memory has grown, the time necessary for the disk transfer has become annoyingly long; 
one solution to this problem is teledebugging.   The routines that read the memory from the world "swapped" on the disk can be 
replaced with ones that talk to other machines on the Ethernet.  The debugee computer need not be geographically nearby, either; an 
implementor in Palo Alto can debug a program running on a machine in London.
4.5    Packager
The Pilot operating system supports a demand paged virtual memory.  It also allows the programmer to specify swap units so that 
when a particular page must be swapped in, an effort is made to bring in its entire swap unit.
When the compiler generates code for a module, it puts the code for the various procedures into a contiguous set of pages in the 
output file (interspersed with readonly constants).  When the program is loaded by the runtime loader, these file pages are mapped 
into virtual memory.  The default swap unit for code is to swap the entire module as a unit.
Procedures are often collected in the same module because they work on the same abstraction, or because they share common private 
definitions and data.  It is often the case that some of the procedures are used only for initialization, or that some procedure in 
module A is tightly coupled with another procedure in module B.  The Packager is a tool that allows the programmer to associate 
procedures of a collection of modules into explicit swap units.  It corresponds very much to the Chinese restaurant stereotype of 
"one from column A, two from column B."
4.6    Performance Tools
The packager discussed above is the easier half of an important problem, that of reducing working set size; the more difficult half 
is to determine what the swap units should be.  We have a number of tools in XDE to aid in answering this and other interesting 
questions.  Indeed, the principal conclusion of Knuth's FORTRAN study [7] was that programmers should have and use more data about 
the runtime performance of their programs. The set of performance tools includes the following:
·    Spya program that wakes up periodically (at interrupt level) and records the execution context of a given process (or set of 
processes). [11]
·    PerfPackagea tool that allows the programmer to define a set of nodes in a running program, using the standard machinery for 
setting breakpoints.  A set of legs, defined by pairs of nodes can also be defined.  The PerfPackage replaces the breakpoint 
handler with one that counts the number of times that each node is visited, as well as the average time spent on each of the legs.
·    Transfer counting toolsseveral tools to note all interesting control transfers (procedure calls and returns), and present 
various statistics about them.
·    Page fault analysis toolstools to record and present data about page fault behavior.
These tools use the source-level debugging information produced by the compiler to present their results in the most usable format. 
 The Spy is an interesting example.  One can first see in which modules a program is spending its time.  Then for a set of modules, 
one can get statistics about the most time-consuming procedures.  Finally, statistics can be collected at the statement level.  
Since the Spy works on a sampling principle, it is sometimes useful to switch to the PerfPackage to obtain exact statistics at the 
statement level.
4.7    Consistent Compilation Tools
If procedures in program modules X and Y both reference a record type from interface A, then X and Y need to be recompiled whenever 
A is.  This leads to compilation dependencies determined by the include relationships of a collection of programs.  A tool called 
the IncludeChecker can be pointed at the current version of a program and told to create the sequence of Compiler and Binder 
command lines necessary to make a new one.  It is similar to the UNIXTM program Make [1], but differs in at least two ways: it only 
cares about compilation and binding dependencies, and it determines these dependencies automatically from information in the object 
file. 
Other tools have been built to approach this problem, with varying degrees of success.
5.    Other useful tools
The tools described in §4 are a representative sample of those that are heavily integrated with the Mesa language.  There are a 
number of other tools that run in the environment that are valuable for program development, but are not as language specific.  A 
sample collection of these tools follows:
·    Program Librarianto eliminate conflicts from multiple implementors of a system.
·    DF software, like Schmidt's work [14] but with librarian extensions.
·    Adobea system for tracking action requests.
·    built-ins: File Tool, abbreviation expansion, etc.
·    Chatfor TTY access to other systems.
·    Mail reading programs.
·    Tool driverto batch operations on window interfaces.
6.    User supplied "Hacks"
There is a definite positive feedback effect from having the developers of a system rely on it for their day-to-day existence, 
particularly in a system as open and extensible as XDE.  In the early days, there was a natural tendency to share small programs 
that enhanced programmer productivity.  Such "neat hacks" often were included in the next official release of the system.  The 
symbiote package described in §3.5 started life this way.
The producers and users of this ancillary software were eventually no longer housed in the same corner of a single building, but 
were spread across the continent.  In this situation, a degree of order was called for.  The directory <Hacks> on one of the file 
servers was changed from a private Mesa group directory into a public one, and a set of rules was established to govern the use of 
this directory.  At last count there were over 200 programs stored on the <Hacks> directory.  The programs can be roughly divided 
into four categories:
·    Modified versions of official tools, with added functionality.  These new features are often incorporated into the official 
versions at the next release.
·    Extensions to the environment.  These include adding new keyboard commands (made easier by the TIP mechanism), changing the 
appearance of tiny windows, and changing the semantics of scrollbars.  
·    Generally useful tools.  For example, there is a calendar program, several graphics editors, a spreadsheet, a tool for 
browsing files on remote directories, etc.  Perhaps the most useful is a form subwindow editor for designing user interfaces of 
other tools.
·    Fun and games.  This includes a program to play music on the tone generator of the keyboard, several arcade-like games, and 
MazeWar, a multi-player seek-and-destroy game played over the network.
7.    Conclusions
This section discusses the major successes and the areas where we fell short of our goals and desires.
Good points
·    Consistent user interface (by seduction, not fiat)
·    Balance of novice/expert usability (accelerators & 2D vs. 1D)
·    Source level debugging
·    "personal timesharing" (file system sophistication necessary)
·    homogeneous environment (selection between tools)
·    Adequate performance (cycles of add features/tune performance)
·    Extensibility (TIP, procedural interface to tools)
Bad points
·    Thinking small, trying to squeeze too much into limited resources
·    Limited ability to incorporate code from outside (little existed when we started)
Needed
·    Same world debugger
·    Other language capabilities
References
[1]    Feldman, S. I., MakeA Program for Maintaining Computer Programs, Software Practices & Experience 9 4 (April 1979) 255-265
[2]    Geschke, C. M., Morris, J. H., and Satterthwaite, E.H., Early experience with Mesa, Communications of the ACM 20 8 (August 
1977) 540-553.
[3]    Graham, S. L., Joy, W. N., and Roubine, O., Hashed Symbol Tables for Languages with Explicit Scope Control, Proceedings of 
the Symbosium on Compiler Construction, SIGPLAN Notices 14 8 (August 1979) 50-57.
[4]    Johnsson, R. K. and Wick, J. D., An Overview of the Mesa Processor Architecture, Proceedings of the Symbosium on 
Architectural Support for Programming Languages and Operating Systems, SIGPLAN Notices 17 4 (March 1982) 20-29.
[5]    Kay, A. C., The Reactive Engine (thesis), University of Utah, Department of Computer Science, Salt Lake City (August 1969).
[6]    Kay, A. C. and the Learning Research Group, Personal Dynamic Media, Xerox Palo Alto Research Center Report SSL-76-1 (1976).
[7]    Knuth, D. E., An Empirical Study of FORTRAN Programs, SoftwarePractice and Experience 1 (1971) 105-133.
[8]    Lampson, B. W. and Sproull, R. F., An Open Operating System for a Single-User Machine, Seventh Symposium on Operating 
Systems Principles, Operating Systems Review 13 5 (December 1979) 98-105.
[9]    Lampson, B. W. and Redell, D. D., Experience with Processes and Monitors in Mesa, Communications of the ACM 23 2 (February 
1980) 105-117.
[10]    Lauer, H. C., Satterthwaite, E. H., The Impact of Mesa on System Design, Proceeding of the Fourth International Conference 
on Software Engineering, Munich  (September 1979) 174-182
[11]    McDaniel, G., The Mesa Spy: An Interactive Tool for Performance Debugging, Performance Evaluation Review 11 4 (Winter 
1982-83) 68-76.
[12]    Mitchell, J. G., Maybury W., and Sweet, R. E., Mesa Language Manual, Xerox Palo Alto Research Center Report CSL-79-3 (April 
1979).
[13]    Redell, D. D., Dalal, Y. K., Horsley, T. R., Lauer, H. C., Lynch, W. C., McJones, P. R., Murray, H. G., Purcell, S. C., 
Pilot: An Operating System for a Personal Computer, Communications of the ACM 23 2 (February 1980) 81-92.
[14]     Schmidt, E. E., Controlling Large Software Development in a Distributed Environment, Xerox Palo Alto Research Center 
Report CSL-82-7 (December 1982).
[15]     Sweet, R. E. and Sandman, J. G., Empirical Analysis of the Mesa Instruction Set, Proceedings of the Symbosium on 
Architectural Support for Programming Languages and Operating Systems, SigPLAN Notices 17 4 (March 1982) 158-166.
[16]    Swinehart, D. C., Copilot: A Multiple Process Approach to Interactive Programming Systems, Stanford Artificial Intelligence 
Laboratory Memo AIM-230 (July 1974).
[17]    Thacker, C. P., Alto: a personal computer, in Computer Structures: Readings and Examples, Second Edition, Sieworek, Bell, 
and Newell Eds., McGraw-Hill (1981).