Page Numbers: Yes X: 552 Y: 10.5" First Page: 19
Columns: 2 Edge Margin: 60 Between Columns: 25
Margins: Top: 75 Bottom: 60
Line Numbers: No Modulus: 5 Page-relative
Even Heading:

REQUIREMENTS FOR AN EXPERIMENTAL PROGRAMMING ENVIRONMENT

Odd Heading: Not-on-first-page

PRIORITY RANKING AND INTERRELATION OF CAPABILITIES

3. Priority ranking and interrelation of capabilities

We arrived at a priority ranking for capabilities by giving each member of the working group 100 votes to be divided among the capabilities on the list. The vote total below is simply the sum of the votes of the 5 members who actually voted, identified by their initials: Deutsch, Horning, Lampson, Morris, and Satterthwaite. (As a check, we also ranked the capabilities according to the median rather than the total, and the results were essentially the same.) We found that a natural division into 5 priority groups emerged from the ranking. The reader should be aware that we were ranking capabilities on their utility if present in some reasonable form, not on the value of doing research into how to improve what we now know about providing them.

We were able to reach a consensus about how fundamental each capability was, in the sense of how difficult it would be to add that capability if it were not allowed for in the initial system design. In doing this we drew heavily on the experience gained from the three existing language systems. This consensus is expressed below according to the following code:

FFundamental, much harder if not allowed for originally

IIntermediate, somewhat harder if not allowed for

AAdd-on, difficulty does not depend significantly on pre-planning (although it may be intrinsically hard anyway)

<==<EPEFig1.press<

We identified an enabling relation between certain pairs of capabilities, in the sense that capability x is almost certainly required to provide capability y. So many things depend on item (L1) that we have omitted mention of this.

Finally, we estimated the difficulty of providing each capability in each of the three presently existing environments (Lisp, Mesa, and Smalltalk). Each capability has a 3-digit difficulty code referring to the effort required to provide the capability in Lisp, Mesa, and Smalltalk in that order. The difficulty codes have the following meanings:

0—available

1—easy

2—straightforward but takes time

3—hard

4—impossible (we found we didn’t need to use this)

3.1. Priority ranking

In the tabulation of votes, ‘‘x’’ means zero votes, while ‘‘*’’ means that the person gave no votes to this item because he assumed it would be provided anyway. Votes of the form ‘‘3/4’’ mean 3 votes if we are primarily interested in E(PE), i.e., investi-gation of programming environments per se, but 4 votes if we are concentrating on (EP)E, i.e., production of experimental programs.

<==<EPEFig2.press<

<==<EPEFig3.press<

Priority E (no votes at all)

VIRTUAL MACHINE / PROGRAMMING LANGUAGE

(L2b)?222An enormous virtual address space (>48 bits)

(L22)A100User access to the machine’s capability for multi-precision arithmetic

(L23)I202Good facilities for processes, monitors, interrupts

enabled by (L6) Some support for interrupts

enabled by (A15) Abstraction mechanisms

(L24)F120Simple, unambiguous syntax (including infix notation)

(L25)F302Control over importation of names

enabled by (A15) Abstraction mechanisms

(L26)F331User packages as ‘‘first-class citizens’’

(L28)F333Full-scale inter-language communication

enabled by (L17) Inter-language communication

(L29)A222User microprogramming

(L30)?333Clean data and control trapping mechanisms

enabled by (L6) Some support for interrupts

enabled by (L23) Good facilities for processes, monitors, interrupts

enabled by (L31) ‘‘Good’’ exceptional condition handling

(L31)?333‘‘Good’’ exceptional condition handling

enabled by (L7) Adequate exceptional condition handling

enabled by (L13) Encapsulation/protection mechanisms

enabled by (L14) Abstraction mechanisms

enabled by (L15) Non-hierarchical control structures

TOOLS

(T14)A222Aids for incremental development (stubs, outstanding task list)

enabled by (L9) Program-manipulable representation of programs

(T15)A222Regression testing system

enabled by (L9) Program-manipulable representation of programs

(T16)A333Random testing aids

(T17)F022(High capability) Masterscope

(T19)A333Static analyzers: verifier, performance predictor

enabled by (L9) Program-manipulable representation of programs

PACKAGES

(P5)A022More elaborate screen management

(P7)A221Small data base manager

(P11)F323Background processing

(P16)A011History lists

(P17)I111User access to full bandwidth of disk

(P18)A222(English) dictionary service

(P19)A222Teleconferencing

(P20)A222Audio

(P21)A111User access to full bandwidth of networks

OTHER

(X4)F222‘‘Self-teaching’’ interface for beginners

(X5)I222‘‘Good’’ introductory documentation

3.2 Discussion of difficulty estimates

In this section we discuss the difficulty estimates for the highest-priority features. Nearly all these features fall into one of three difficulty patterns:

Considerably easier in Mesa than in either Lisp or Smalltalk (e.g., L11, L13, T5).

Considerably easier in either Lisp or Smalltalk than in Mesa (e.g., L5, T1, L12).

Comparable in difficulty in all three systems (e.g., L4, L3, T8).

This is not terribly surprising, given the underlying philosophical similarities between Lisp and Smalltalk.

Priority A

(L5)030Object management—garbage collection, reference counting

Reference counting, which relies almost entirely on local information, and garbage collection, which needs a global map of all potentially traceable data, present quite different problems for Mesa. For reference counting, it might be adequate to add an attribute to the Mesa type system so that reference counting or transaction queuing can occur when the program stores into a pointer that might point to an automatically managed object, and arrange for a user-supplied finalization procedure to be called when a count becomes zero. A further refinement might be automatic generation of the procedure by the compiler based on declarations. All this would be difficulty level 2.

Garbage collection in Mesa is more difficult, for two reasons:

The type information needed to locate all pointers is not present in the actual data, but must be derived from the symbol table produced by the compiler.

The presence of LOOPHOLEs, pointer arithmetic, overlaid variants, and relative pointers makes it impossible for a garbage collector to find or trace all pointers to structure to be saved.

The former problem is only one of efficiency: one way around it might be to arrange for the compiler to generate a tracing procedure for each structure that might participate in garbage collection. The latter, however, is a fundamental difficulty. We believe that the proper approach to overcoming it is to discover a subset of the Mesa language that does not use any of the LOOPHOLE-like features mentioned above, and find a way to draw a protection boundary around a program written in this subset so that it can have automatically managed data. This is a hard problem.

(L11)203Statically checked type system

The basic problem with static type checking in both Lisp and Smalltalk is that very little is known at compile time about the referents of names.

Lisp currently has a facility called DeclTran, which uses embedded declarations (both of types and of arbitrary predicates) to check the types of operands at runtime and to generate more efficient code within an individual function. This facility applies to both interpreted and compiled code, but is somewhat machine-dependent and does not exist for the Alto/Dorado Lisp system. Also, it has no ability to deal with static checking of interfaces between user-defined functions (as opposed to the interface from user-defined functions to built-in operations like arithmetic). If mechanisms, such as those of (L13) and (L14), were added to Lisp to control exporting and linkage of names, it is likely that DeclTran could be extended to inter-function type checking. We are inclined to think that this is not a good approach in the long run and that the type system should be more tightly integrated with the underlying language system, but it seems like a workable way to obtain the desired result.

Smalltalk has no facilities at all for static declaration of types. Furthermore, because every operation is decoded at execution time by the object that is its first operand (even elementary operations such as ‘‘+’’), there is in principle no way of knowing what code will actually get executed in advance of execution time without some combi-nation of type declarations and searching the entire system to discover what classes implement what operations. The situation is complicated by Smalltalk’s subclass structure, which makes it very desirable that, for example, a method requiring an argument of type Number should accept values of type Integer (a subclass of Number). Smalltalk has a fairly simple compiler and name structure, but a lot of new machinery would have to be built, some of which would require careful thought about what ‘‘type’’ means in the Smalltalk environment.

(L4)000Memory management—object/page swapping

Lisp and Mesa already use a straightforward paging scheme, and Smalltalk an object-swapping scheme.

(L14)302Abstraction mechanisms; explicit notion of ‘‘interface’’

As discussed under (L13) below, Lisp currently has only a very weak mechanism for explicitly dealing with interfaces between a package and its clients. In addition, Lisp has no mechanism for taking a group of functions and controlling how its imported names are to be linked: such a facility is necessary if interfaces are to be separated from their implementations.

Smalltalk is somewhat better off since its invocation mechanism does hide the implementation from the caller. A type system for Smalltalk, as discussed under (L11) above, would also go far towards providing an explicit notion of interface, since the current Smalltalk notion of ‘‘abstract class’’ can be viewed as either a type or an interface description.

(T1)020Fast turnaround for minor program changes (less than 5 seconds)

Lisp has an interpreter, and a fully integrated editor. (We have discussed replacing the interpreter with a high-speed, low-code-quality compiler, which already exists for the Alto.) Smalltalk has a compiler which we believe will run fast enough on the Dorado, and an integrated editor.

Mesa offers several medium-size obstacles to fast turnaround for changes:

Since the present editor is not integrated or even properly packaged, considerable machine and human overhead is involved in getting in and out of it. We recommend replacing it by a packaged editor available in the programming environ-ment.

The compiler is not designed to compile anything smaller than an entire module. We recommend some work to modularize the compiler (it is already broken up quite well) and to make sure enough information is available for it to be able to compile single procedures.

The current Mesa system does not provide for safe, incremental replacement of modules or procedures by new versions without losing execution state. This feature must be provided.

(L16)?0?Adequate runtime efficiency

The Lisp instruction set is actually quite similar to that of Mesa: for example, it can use the Dorado instruction fetch unit. Sources of additional overhead include the fact that all data are doublewords, and considerable runtime type-checking is required. We believe that even the present Lisp system will perform adequately on the Dorado. Further significant gains in efficiency would be possible with some redesign that would use the Dorado processor stack, and with the extensions required for (L11), static type checking.

The Smalltalk instruction set, in principle, is also similar to that of Lisp and Mesa. In addition to doubleword data and runtime type-checking, Smalltalk also suffers somewhat from substantially less ability to compile things like arithmetic and structure access in-line, and the requirement for doing some kind of hash lookup on each invocation. We believe that Smalltalk could also be brought up to acceptable efficiency through a high-performance design.

(L1)002Large virtual address space (>24 bits)

Lisp and Mesa already provide 24-bit address spaces. The difficulty code for Smalltalk reflects Dan Ingalls’ estimate that the current system could be modified (without changing its basic structure) in 3 to 6 months.

Priority B

(L13)302Encapsulation/protection mechanisms—export control

Lisp already has one mechanism for controlling the export of names from a group of functions: the block compiler. However, this mechanism has many disadvantages:

Using it requires giving up a good deal of debugging capability, since non-exported function and variable names are completely lost.

It is not compatible with either the interpreter or the normal compiler.

Its application is limited to a single level, e.g., a package cannot use this mechanism to have subfunctions local to an individual interior function or group of functions.

We believe that adding export control to Lisp would require introducing notions of nested or otherwise controlled lexical name scopes similar to those of Mesa; we would expect this to have ramifications throughout the system, and some impact on user programs that take advantage of the fact that there is a single space of names that encompasses both all of the system, their own programs, and their own data. (We note that in the past, the lack of export control has often been seen as an advantage, since it made it easy for a somewhat knowledgeable user to extend or modify the system as desired, but we believe this is outweighed by the problems it causes.)

Smalltalk has two different export control mechanisms. For variables, there is a dual lexical hierarchy based on lifetime (method variables, instance variables, and static class variables) and on specialization (subclassing). For operations, each class defines the names of operations it will accept. However, Smalltalk is deficient in several respects:

There is a loophole, fairly easy to use, that allows access from outside to any variable of any object.

A class cannot restrict purely internal operations to internal use—all operations within the class are accessible to all clients.

Subclasses have access to all operations and data of their superclass.

We believe that remedying these defects would require significant additions to Smalltalk but no changes in its basic structure.

(L3)333Well-integrated access to large, robust data bases

This is an area requiring considerable thought. No general-purpose programming language currently offers this capability as we intend it to be interpreted. We have no a priori reason to think it would be harder to implement in one language than in another—it will be a challenge in any of them.

(L12)020 Self-typing data (a la Lisp and Smalltalk), run-time type system

Mesa, unlike Lisp and Smalltalk, segregates type information from data at runtime by relegating the former to symbol table structures put out by the compiler, which are normally not part of the runtime environment. Extending the type system into the runtime environment in a reasonable way seems to require adding types as a type in the language, and arranging things so that the runtime representation of types can match up properly with the information in the symbol table. Some of the design for this already exists, since the debugger must manipulate types internally. It is worth noting that Mesa’s facilities for variant records already address a small part of this problem.

(T5)203Consistent compilation

Mesa ensures consistent compilation by placing time stamps on source and object files, and by recording in each object file the complete list of time stamps for the files that produced it. For Lisp and Smalltalk, the basic problem is that identified in (L13) and (L14) above, namely, lack of mechanisms for identifying the dependencies between modules.

(T6)323Version control

Mesa contains most of the mechanisms for the history part of version control (knowing exactly how to reconstruct any object file). Some things are missing, such as a record of the compiler switches, and also the Binder does not provide this infor-mation in the files it constructs. For Lisp and Smalltalk, the problem is that objects do not carry any kind of identifying stamp, nor do compilation processes record the information they used. In the present Lisp system, the problem is almost insoluble, because compilation takes place in the context of whatever random collection of macros, flags, and other declarations happens to be lying around at the time of compilation. (The problem is not the large amount of state on which compilation depends, but the fact that there is no mechanism for recording the relevant parts of it with the compiled file.)

Aside from C/Mesa and the Binder, none of the three systems has any mechanism for describing how parts are put together to form a whole. C/Mesa fails to cover certain crucial aspects of initialization and parameterization—there is no way to pass parameters from a C/Mesa program to initialization code, for example, in lieu of supplying them directly when the program initializes itself. Lisp allows programs to load other programs as part of their initialization, and several large systems have more elaborate mechanisms of their own for doing this, but there is no system-wide machinery of this kind.

(T8)000Source-language debugger

All three systems have adequate source-language debuggers. All of them could profit from additional work, since there are ideas in each one that are not present in the others: for example, the REVERT feature in Lisp, the ability to point directly to the source text on the screen in Mesa, and the Smalltalk method for displaying local variables.

(P1)121Text objects and images

Lisp already has a package (TXDT) for manipulating documents with formatting on individual characters (font, bold/italic, etc.). However, TXDT has no provisions for paragraph-level formatting or tables or for conversion to or from standard document file formats. These defects are minor. Facilities for manipulating text images as images are provided within DLisp. Documentation for the formatting aspects of TXDT, and for all of DLisp, does not currently exist, although the latter is being worked on.

No comparable package exists in Mesa, although several application systems have had to provide some of these functions.

Smalltalk provides the notion of a formatted paragraph, and facilities for editing, displaying, and selecting within it, in the standard system. Smalltalk also provides conversion to and from document file formats. Smalltalk does not provide paragraph-level formatting or tables, and its facilities for handling text images in any but the most straightforward way are poor. Again, these defects are relatively minor.

(L18)021Uniform screen management

Lisp already possesses an elaborate and functionally rich screen management package, DLisp. As noted above, DLisp is still being documented. It does seem to satisfy our principal desire, namely that programs access the display only through an interface that makes sharing and allocation of the physical screen invisible to them; we are not certain whether it imposes too much structure on the user’s view of the display, to the extent that some kinds of experiments might be difficult or impossible (no such difficulties have arisen in the few applications attempted thus far).

Several attempts have been made at creating a screen management package in Mesa; all have failed to gain acceptance, for a variety of reasons. We believe that it will be necessary to start from scratch, taking into account the experience with the failed models and with the more successful ones of Lisp and Smalltalk.

Smalltalk has the opposite problem: accessing the screen in an anarchic way has been too easy. Some moderately successful interfaces have emerged—one for windows, one for documents, and one under development for graphics—but there is still a substantial need for unification of what has been learned.

(L8)202User access to the machine’s capability for packed data

Lisp and Smalltalk, unlike Mesa, take the view that all data accessible to the programmer are pointers. Intrinsically non-pointer data, such as string characters, are handled with various subter-fuges. To obtain the benefits of packed data within these two systems would require extending the storage management system to be able to allocate and deallocate such objects, and extending the compiler to generate instructions to access them under safe conditions. The Lisp ‘‘record package’’ accomplishes some of this, but in a way that is poorly integrated with the rest of the storage management system and makes use of what we consider impermissible loopholes in the compiler. Smalltalk has no such facility at all, although the Smalltalk implementors have discussed it and believe they understand in principle how to do it without structural changes in the system.

(L10)111Run-time availability of all information derivable from source program (e.g., names, types, scopes)

All three systems make most of the source information available in some form at runtime. In Lisp, the facilities for retrieving source information are very good, but they do not handle declarations and variables with the same ease as functions. In Mesa, the relevant data structures (in the symbol tables produced by the compiler) are not currently documented for public use. In Smalltalk, the information required to correlate the dynamic environment with the names used in the program exists but not in convenient form. Mesa’s facilities for correlating the program counter with a point in the source program are much better than either Lisp’s or Smalltalk’s.