[_CD8_]<cedardocs>PE2>Report>pe2.3b2!1

Foundations: basic, low-level facilities needed to match the functionality of Lisp: atoms, variable syntax analysis, dynamic variable binding, a safe language subset, and automatic storage deallocation.

Features: equivalents for the Lisp Masterscope, file package, programmer’s assistant, Helpsys and similar features, in a more general setting, together with improvements to the debugger and editor, facilities for specifying the construction of complex systems, and other "environmental" capabilities.

We propose to provide a few of these facilities, which we lump under Preliminaries, by initially constructing an interim integrated Mesa environment (IME) which provides quick edit-compile-run turnaround for the existing Mesa language and system, as well as rudimentary access to the Dorado’s large virtual memory. This system serves as a base for later developments.

(A1) Automatic storage deallocation
(A5) Fast turnaround for minor program changes
(B3) Run-time type system, self-typing data
(B10) Run-time availability of all source program information
(C3) Compiler/interpreter available with low overhead at run time
(C6) Program-manipulable representation of programs

Of all these facilities, we will deal with (A5) under Preliminaries, and we think (C3) is covered by our proposals for (A5) and (B10); the rest are Foundations. We will deal with Features separately.

This section describes the steps required to obtain an interim integrated Mesa programming environment (IME). The intended user community for this environment is a small corps of experts who will use it to construct a more lasting integrated Mesa world.

Phase I represents the bulk of the effort. When completed, it will have produced an environment in which a text editor, the compiler, the binder, the debugger, and the user’s program(s) are all simultaneously available. The facilities provided in Phase I are:

Microcode and system extensions to support a 24-bit address space and virtual memory, with some crude protection between major entities (compiler, debugger, editor, user programs). Some of this work has already been done for Extended Memory Alto/Mesa.

A window-based display interface for interaction with the debugger, editor, and other tools. Such an interface already exists in the Mesa debugger and in the Mesa Tools Environment, and one is planned for Chameleon, a package for market probes being developed by AOS.

A packaged text editor of about the functionality of the Laurel editor. The Tools group already have such an editor. Chameleon will have a similar editor. Alternatively, it wouldn’t be much work to write our own.

Replacing an existing module by a new version without losing execution state. This involves changing the compiler to remember the decisions it made the last time it compiled the module, and is only possible if the structure of the module (global variables and entry procedures) has not changed. The loader must detect and invalidate extant frames that point into the global frame being replaced.

A dependency analyzer that determines what modules might (logically) require recompilation as a result of a change. SDD already has a version of this program called the Include checker.

The ability to treat programs as data requires three major facilities within the Mesa environment: (a) an S-expression-like representation of source programs, (b) a means of using atoms (in the LISP sense) uniformly throughout the environment, and (c) a universal pointer mechanism.

S-expression representation. We propose to define a representation other than parse trees, so that the representation of parse trees can change as the compiler/language evolve.

Atoms. The Mesa compiler currently builds symbol tables that include a mapping between source identifiers and internal unique IDs (atoms) for an individual module. The Lisp atom capability requires a global map, into which the individual map would be merged when a compilation unit "enters the environment". This is very similar to the merge now done by the compiler for included modules.

Universal Pointers. We will need pointers that carry the type of their referent with them. This in turn requires a scheme for universal type IDs, which do not currently exist in Mesa. We also intend to add a facility for coercing a universal pointer to a pointer of more specific type; the coercion must be accompanied by a run-time check.

LISP provides three opportunities for the programmer to affect the parsing/interpretation of input text: (a) at scanning time, (b) at compile time, and (c) at function call time. (a) may be accomplished by providing scanner escapes to user-written code, which will replace some appropriate substring of the current parsing context (i.e., the as-yet unclosed lists) with an S-expression. It appears straightforward to provide a facility comparable in power to LISP’s readtables -- a more elegant mechanism might be desirable. (b) may be accomplished by more-or-less conventional macro expansion along the lines of the Mesa mechanisms for in-line procedures. (c) is deemed undesirable and will not be provided.

Lisp allows free mixing of code and (structured) data, and parses both in essentially the same way; programs frequently read in both at run time. Consequently, the scanner and parser must be packaged for run time use.

Mesa, at present, only supports static binding of identifiers. To be able to bind a name to a variable in an enclosing dynamic context, we need to know what variables are to be found in each frame. Instead of the LISP default, we propose that variables to which dynamic binding may occur be declared as such at compile time. The compiler can then produce a table of entries of the form

By a safe language we mean here one in which a pointer value of a given type POINTER TO T is guaranteed to point to a region of storage containing a value of type T.

There are three ways in which a pointer variable may acquire an improper value: lack of initialization, incorrect computation (e.g. by pointer arithmetic), or premature deallocation of the object pointed to. Array and string descriptors require the same treatment as pointers. In addition, it is necessary to do bounds checking on array references, since otherwise every array index is as dangerous as a pointer.

Preventing uninitialized pointers is straightforward, by generating code to initialize all pointers in procedure frames when they are allocated, and in dynamic variables of record and array types when they are allocated. Mesa 5 will have language constructs for allocating dynamic variables, so it is known where to do the initialization.

Preventing premature deallocation has two aspects: dynamic (explicitly allocated) variables and stack variables. For the latter, we propose to eliminate the ability to obtain an explicit pointer to a local variable, and as partial compensation introduce var parameters (call by reference). For dynamic variables some support from an automatic deallocation mechanism seems essential. We see three possibilities, discussed in the appendix: the one that comes closest to Lisp is fully automatic deallocation based on an incremental garbage collector.

Mesa currently has primitive and unsafe facilities for relative pointers, which there is a design to strengthen and improve. Misuse of a relative pointer can only damage data in the region it refers to; if none of the storage in this region contains any external pointers, then no global damage can occur. Embedded external pointers are still possible if they are treated as array indices, i.e. go through fingers. The advantage is that the programmer can forgo the safety precautions for such relative pointers without risking the integrity of the entire system. Of course a bounds check is still required (analogous to an array bounds check), but in many cases of interest it can be provided by storing the pointers in n-bit fields and making the size of the region 2n.

Our proposal is to have automatically deallocated (AD) types, and to use the Deutsch-Bobrow scheme for incremental garbage collection. This requires knowledge of the location and type of every pointer to an AD type, but the techniques are well-known and straightforward.

This section attempts to characterize the "programmer’s assistant" facilities of a Mesa-based EPE, in terms of a more or less direct replacement for existing Interlisp functions. However, we must bear in mind that we have the opportunity to redesign the user’s interface to the system, taking the high bandwidth display into account. The goal will be to provide a consistent, integrated default interface for program development and for control of user applications that do not have exotic interactive requirements. The right facilities for such an environment will look substantially different from previous ones, as environments like the Smalltalk browser, DLisp, and the Mesa Tools are beginning to show us. These issues deserve a great deal of additional design work once the project is underway.

We advocate extending the compiler to provide the equivalent of incremental compilation for single statements in specified contexts. An evaluator within the debugger would generate the appropriate linkages to get the statements executed. Sufficient information would be saved to provide the History List features (below.) An appropriate default global context could be made available for the execution of statements corresponding to the Lisp "top level".

Only modest extensions to the current conditional breakpoint code, using the incremental compiler invented just above, are necessary to obtain a break/advise facility the equal of Interlisp’s. The standard breakpoint handler could take care of providing the linkage to the system-produced procedures containing the advice.

A history list that records top-level user actions in external (text) form, along with an indication of the contexts in which they were executed, are sufficient to implement the Redo command and the function-composition capabilities that it enables. To provide Undo, however, requires internal information as well. Once automatically allocated lists, programs as S-expressions, atoms and data with attached types, and the other Fundamentals are available, implementation of both commands should be straightforward. Probably both would be done, as in Lisp, by retaining S-expression representations of the original statements and their reversing functions.

In Mesa even simple programs consist of several independent global contexts. Virtually every user action will have to be interpreted with respect to a specific environment. History list entries will have to include the corresponding environmental information, and the commands will have to know when the corresponding environments no longer exist, or will have to arrange, as Interlisp can, to retain the context frames as long as they are referenced (requires garbage collector to operate on frames.) Contexts running as concurrent processes could also cause trouble if more than one of the processes becomes involved in user history activity. The history provisions would want to be more fully integrated with the complex context structures than are the Interlisp models.

Implementating the equivalent of the TESTMODE(T) facility in Interlisp -- saving the old contents for every store other than into local variables -- could cause both time and space problems, because Mesa is much more an assignment-based language than Lisp.

Given Mesa’s complex syntax, it is not clear how best to provide undoable versions of each language primitive that can produce a storage modification (e.g., a /← b ?). Languages like Alphard provide a model for how this might be done, by regarding infix operators as abbreviations for function application, but this also requires eliminating the special role of primitive generic functions in Mesa. More generally, the maintenance of a syntax that is acceptable to both people and LALR machines will present problems throughout the system that are not encountered in the pure Lisp implementation.

If the editor chosen for the Preliminaries implements an undo/redo capability, integration with the more general version should be straightforward. Otherwise, these commands would have to be built from scratch, possibly at considerable cost (depending on the editor design.)

In a display-based editor, structure-oriented operations can be largely implemented as part of the selection mechanism. To the extent that the text files are in communion with the underlying S-expression representation, it will be easy to produce the needed hierarchical selections.

Some spelling correction and the repair of minor typographically induced syntax errors could be incorporated into the compiler. The user interface to these tools are likely to be quite different in a system based on compilation and display editing.

The structures needed for the Fundamentals implementations are adequate for the development of a Masterscope-style database. An extension of the interface used for the other tools would provide user access. The compiler, binder, or an intermediate agent, would notice change and update the data base.