Inter-Office MemorandumToEPE GroupDateSeptember 12, 1978FromDaniel G. BobrowLocationPalo AltoSubjectSome Lisp features I would be loathOrganizationCSLto do without; or would you take afish without a bicycleXEROX Filed on: lispfeatures.memoI have been introspecting on how we have used Interlisp to implement and embed KRL, and thefollowing are my distillations of the features used which I would want to have in our EPIC(Experimental Programming Integrated Colossus). To make these next points more specific, hereare some fragments from a particular version of KRL-1.Here is a KRL unit taken from a cryptarithmetic problem as it appears on a file.# Column self:^11:Trigger(ToPrint,'(For x in '(top bottom sum)do (PRINT (SeekMy 'Pointer SomeSignalTable)))) top: An integer bottom: An Integer sum:^2 An Integer2: Trigger(ToFind, '(LispForSum INSTANCE))Here is a fragment from the middle of some Lisp code that might be run using some mixed KRL and Lisp syntax.(SETQ SUM (Seek 'Pointer \the summ fromA Column thatIs !Post (CAR columnList)// FullMatch)) 1. Variable Syntax Analysis: That is, procedural escapes in an available parser. The built in Lispparser (a structure parser that knows about parentheses, brackets, and lexical analysis) also allowsaccess to the basic reading routines (read a character or a symbol or a ...) and allows certaincharacters to signify procedural escapes.In the example above there are two different forms of variable syntactic analysis illustrated. In theunit there are examples of the embedding of Lisp expressions; thus a special parser for units mustbe able to call on the Lisp standard reader. Secondly, in the middle of the code fragment is a "\"indicating an escape to the KRL reader.2. Programmable Lexical Analysis: Another name for being able to read in atoms under somecontrol (I don't think Lisp's readtables are optimum). Reading results in a unique pointer associatedwith that string. The unique pointer must be able to be used in various kinds of symbol tables andprograms eg1) To access a procedure definition which can then be run; in the example LispForSum isa procedure to be run.2) To obtain a value (current under some scoping); In the unit, the variable INSTANCE isassumed bound in the interpretive context. ]gp c8q]r-q7Br ]q]r-q7Br Yq]r#-q 7Br]W"]USsr M# G; FiVq DrE C_6 @3qP =t ;<;q?; T =P ;) 8m"= 6%; 5c Q 2743 0R -*1 ,1 (uB 'P $Fr^ ", :$ A @" _`  d )A D _ L =]<Lisp features316. Performance analysis functions: I used breakdown (which rewrote my functions to monitortheir performance) to tune and understand my system.17. Programmable debugger: Conditional monitoring of function calls and returns, and firewallprotection (ERSETQ) was important in getting my large system up. fr G b-tr' `4 ]mQ [@ U P@ P=r7Inter-Office MemorandumToEPE Working GroupDateSeptember 14, 1978FromP. Deutsch (including comments byLocationPalo AltoMcDaniel and Swinehart)SubjectUnique Smalltalk capabilitiesOrganizationCSLXEROX Filed on: stcap.memo on Maxc1This memo is a first stab at listing in detail those capabilities of Smalltalk which are not present ineither Lisp or Mesa, and which are important for an EPE. Comments by Gene McDaniel and DanSwinehart have been incorporated in the memo without attribution.Language>>Syntax: Smalltalk has an infix syntax describable in less than 2 pages of equations, including thelexical syntax. It has no reserved words and only about a dozen reserved characters. Smalltalk'ssyntax provides the following advantages:(1) The syntax can be learned very quickly by anyone who knows any formal language, andthere is never any need to refer to the manual to decide whether a given syntactic constructis legal.(2) It is possible to design a very simple internal representation of parsed programs, whichcan be effectively manipulated by programs.(3) The syntax includes the capability for certain kinds of extension such as user-definedcontrol structures.(4) There is a uniform notion of "application" which encompasses all language constructsthat carry out operations: this means that a future macro-expansion capability will be veryeasy to add.(5) The use of punctuation for the common operations (statement grouping and conditionals)enhances compactness without sacrificing readability.One consequence of this simple syntax, of course, is that a lot of things which one thinks of as beingpart of the "language" in Mesa become "packages" in Smalltalk (just as in Lisp), but that is just amatter of how the documentation is arranged.Can the Mesa syntax be simplified to include the above advantages? Can the Lisp infix syntaxprovide (1)? Can the tangle of Lisp compile-time capabilities (macros, CLISP expansion, etc.) besimplified to provide (4) without giving up (3)?>>Object-oriented programming: in Smalltalk, all objects interpret the operations legal on them.There is no notion of a free-standing "procedure" or "data structure". This has the followingadvantages:]gp c8q]r-q7Br ]q]r!-q7Br]\w Wq]r-q 7BrSsr M& Gg Fi9" DA At >rB" =K ;)8V*-6R 5L2 E0+-oJ+(.*'9 M% "S!5 T RP , 6' P 0 kW V a ?QZUnique Smalltalk capabilities2(1) The space of operation names is local to each type -- there is no need to qualify names(as in Mesa), or invent names that include the object type in them somehow (as in Lisp).(2) There is no need to declare the type of the receiver of a message, or to qualify or"open" the names of its components as in Mesa.(3) All operations are automatically generic, with efficient support from the underlyingvirtual machine.A consequence of (1) is that Smalltalk syntax may be a reasonable model for certain applicationlanguages as well: in particular, there is no need to provide a command interpreter that looks up aspecial command set in a table, and eventually spelling correction and type checking could be doneby the language mechanisms as well.Can Lisp be modified to include appropriate mechanisms for name scoping and interpretation for (1)and (2)? Can either Lisp or Mesa provide (3)?>>Hand coding: Smalltalk provides no way for programmers to write code in any language lowerthan Smalltalk, and could easily do without the loophole which allows programmers to accessarbitrary memory words directly. In Lisp, by contrast, programmers constantly give in to thetemptation to write assembly code and/or direct data accesses for efficiency, which result in obscurebugs and machine dependencies.Can Lisp be modified to provide a sufficiently complete set of non-machine-level data accessmechanisms to make assembly code unnecessary? Can Mesa be modified to remove or greatlyconstrict the loophole mechanisms (including dangling pointers) that compromise programcorrectness in obscure ways?Can either Lisp or Smalltalk be upgraded to provide a compiler good enough to reduce thetemptation to hand-code to an infrequent, rather than a daily, level?>>Inheritance of operations through subclass mechanism: Smalltalk makes it relatively easy tocreate classes of objects which are specializations of more general classes (e.g. Atom specializingString specializing Array), or which supply the implementation for a generically defined class (e.g.Integer and Float implementing Number). Work is going on now to extend this to more complexways of combining behaviors into new ones. This inheritance idea includes at least some of theMitchell-Wegbreit "schemes" ideas, as a way to specify shared behaviors only once, and seems toreduce the amount of code one needs to write to make use of existing classes.Lisp has no class structure at all; can Mesa's notions of interfaces and modules be extended toprovide the flexibility of current and promised Smalltalk subclass mechanisms?>>No second-class citizens: Smalltalk makes absolutely no distinction between system- and user-defined types or operations, except that certain operations on system-defined types are provided inlower implementation layers.Can Lisp be extended to provide the benefits of allocation, access, printing, checking, and specialcompilation of user-defined types and their operations that now are the exclusive province of thebuilt-in types?>>Future directions: some experiments in future expansion of the notion of programming languageare being carried out in Smalltalk now. How hard would it be to do these experiments in Lisp orMesa?The proposed template style of two-dimensional object description. frGbB`*.]mN[.X$4W7 T 4+ R^ Q7+ O|# LPZ J. GV F/, D*3 C] A >_!; <F ;U@?A 9 6M 5E 1Z 0n30 .+9 -d\ +*5 *Z'8 (M %#< $$N %: sS  L =F  <# ] VB >QY5Unique Smalltalk capabilities3Constraints (Alan Borning's work). Dan Swinehart has been doing some display interfaces(e.g., audio board test program) using Keith Knox's package as a base, where user changesin one entry must cause changes in others -- and vice versa. When combined with thedesire to initialize these entries with default values and a few other things, he found theresulting ad hoc programs to be complex and cumbersome. A constraint language would beideal for specifying these relationships.The proposals to embed data base linkages as primitive notions in textual objects, such assource programs. (This might be a way to handle some of the linkages needed byMasterscope.)Tools>>Browser: all system and user source code is instantly available for browsing, includingdocumentation and table of contents per class, and class- and method-level categories.Lisp goes part-way towards this, in that it is relatively easy to view the source code of one's ownprograms. Can Lisp or Mesa make the system code equally accessible? Can Lisp or Mesaincorporate (and require use of) the category system, which greatly helps finding one's way aroundin one's own and others' programs?>>Integrated on-line documentation: the programmer can easily insert documentation in the codeas it is written or edited. (Off-line documentation is admittedly awful -- it could be improved evenby some simple automatic extraction of on-line stuff.)>>Immediate incremental compilation.Can the Mesa compiler be made "instantaneous"? (Smalltalk compilations, even on the Alto, arenot a major computational bottleneck.) Can the Lisp compilation process be made truly invisibleand automatic without giving up the fast turn-around from editing to execution?PackagesArbitrary-precision integers with smooth transitions.Paragraph formatting for display and Press output.Bitmap and display coordinate manipulation.Paragraph and picture (bitmap) editor.Windows with standard behavior -- used by interactive tools.Menus.OtherNon-preemptive window behavior (consistent model of interaction). Makes mutually non-interferingapplications easy. frGbM `L _=]@\ ;Z)WYJU5TO Q#t Mr %4 LrV IFZ G0& F<;' D" AY @J >6 ;U$ 8)T 64, 5O 1t .r5 +2 (o+ %C& "<  t rB J >QQC28-SEP-78 13:53:02-PDT,17821;000000000000Date: 28 Sep 1978 1:48 pm (Thursday)From: HorningSubject: Re: A reminderTo: DeutschSubject: DRAFT Mesa -> Lisp RequirementsTo: Programming Environment Interest: Bobrow, Deutsch, Horning, Lampson,Levin, McDaniel, Masinter, Mitchell, Morris, Satterthwaite, Suzuki, Swinehart,Taft, Teitelman;DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT[This is a draft, being circulated now for comment. Sept 28, 1978][We recognize the considerable merits of the Interlisp programmingenvironment. This document is intended to point out what we consider to be thecorrespondingly major advantages of the Mesa environment. We feel stronglythat these features should be preserved in any EPE. To sharpen the discussion,we have made our remarks quite pointed. We trust that in most cases our"challenges" can be met (with varying difficulty); the reason for posing them isto ensure that they are not overlooked.] [Items drafted by Horning:]>>Static CheckingISSUES: One of the major advantages of the Pascal family of languages (of whichMesa is a member) is the substantial amount of consistency checking that ispossible statically (i.e., independent of program execution). Examples of this aresyntax checking, which catches many transcription/input errors, and checkingfor declaration of all names used in a program, which catches both spellingerrors and misunderstandings of the environment. However, probably the mostimportant form of static checking is for type consistency, which is very effectiveat catching many forms of errors, including many "logical" errors.There are several reasons for preferring static to dynamic checking:-it occurs sooner, thereby giving quicker feedback;-errors are more easily related to their sources;-many errors can be detected in a single run, rather than beingidentified one at a time;-complete checking is not dependent on executing an exhaustive set oftest cases (once a program is accepted, one KNOWS that it hasno lurking bugs of this sort);-the overhead of checking can be paid once, rather than repeatedly atexecution time.If programs developed in the EPE are to achieve laboratory-wide usage (likeBravo and Laurel), then their robustness cannot depend on run-time interactionwith their developers. (Not only is there no debugger in Peoria, there generallyisn't one here, either!)Many Mesa programmers are willing to accept "long" turnaround times forprogram changes. Perhaps one reason is that they have much more confidencethat their programs will actually work once they are accepted by the Mesacompiler.CHALLENGE: How can the LISP system be modified to allow a comparable bp) `$ _ ] \ Y( W{H UN Tq Qg= N]C KSB IO HIK FO E?H CP B5( @ ?+ >Static ScopingISSUES: Mesa and LISP have quite different rules for accessing non-local("global") variables. In Mesa, the association between name and variable (or, ifyou prefer, access algorithm) is determinable statically, and is a function of theprocedure declaration and its environment. If this association cannot be fixed, itis difficult to develop robust procedures to manipulate data structures thatout-live particular procedure activations. It is completely unacceptable foraccidental re-use of some name in a calling environment to affect a procedure'saccess to its non-local data.Scope rules serve another very useful function. They provide two sorts of limits:-they limit the set of names accessible within the program at any givenpoint (the amount of "relevant environment" that theprogrammer need consider), and-they limit the range of text within which a name can be accessed,and hence the amount of text that need be considered whenconsidering a change or searching for a bug involving thenamed entity.CHALLENGE: How can LISP provide a satisfactory mechanism for staticallyassociating names and non-local variables? How can names be suitablylocalized?>>EncapsulationISSUES: Even packages that have a large amount of local state should havenarrow interfaces. Ideally, the user should know (and use) only the publishedinterface.In Mesa it is possible to declare items (data, functions, procedures, types, etc.) tobe PRIVATE to a module, and inaccessible outside. This is invaluable inbuilding packages, because it ensures that only the PUBLIC interface is used byclients; assumptions made by the implementation cannot be violated from theoutside through either inadvertance or malice.Mesa allows a program to create multiple instances of a module, supplying, ifdesired, different parameters to each instantiation. This supports an "objectoriented" style of programming, in which each object is referenced only throughits associated suite of functions and procedures.CHALLENGE: How can LISP provide an adequate encapsulation facility forpackages? Can LISP support multiple instances of package prototypes, andobject-oriented programming?>>Explicit InterfacesISSUES: Mesa provides a special type of module (a definitions module)specifically for the purpose of declaring interfaces. This makes it possible toseparate the development of implementing and client modules; with fewexceptions, the changes that don't affect the definitions module are invisible tothe client, and those that do require corresponding changes in the client.Explicit documentation of interfaces, of course, is good programming style, andmandatory for effective multi-programmer cooperation. Static checking thatNfp bM `< ] ZH YQ W{R US TqL RM QgO O LR2KSGI4HI2FBE?9C9B5 ?+G =E >Consistent Version CheckingISSUE: Programs are developed through many versions. The problems that resultfrom inconsistent versions can be extremely subtle, yet it is not always easy toensure that a set of components being run together are actually consistent. Thisprogram is alleviated (but not completely solved) in Mesa by enforcement of therule that the components must use the same versions of interfaces (definitionsmodules).CHALLENGE: How can LISP prevent the accidental execution of systems builtfrom inconsistent versions of components?>>EfficiencyISSUE: One of the key principles of Mesa is that the programmer shall haveeffective access to the full power of the machine, and that implicit run-timeoverheads imposed on all programs shall be kept to a minimum. It seems clearthat there will always be some experimental programs whose computationalrequirements will equal (or exceed) the power of the available hardware, andhence that it will always be necessary to avoid implicit overheads.One advantage of a (reasonably) optimizing compiler is that increased efficiencycan be obtained with little or no effect on the program form and semantics bysupplying tighter (or earlier) bindings (e.g., by replacing variables by constants).CHALLENGE: Is there a LISP subset within which the full power of the machineis available and implicit overheads such as garbage collection and indirection ondata reference are eliminated? Can the efficiency of some LISP programs bemade comparable to Mesa by simply accepting earlier bindings?>>Exportation of Programs from EnvironmentISSUE: Programs developed in the EPE must not be restricted to use within theEPE. Mesa provides a mechanism (image files) for producing essentiallystandalone systems that carry along with them only those parts of the Mesaworld on which they rely. This is important because users may not be Mesaprogrammers and may not be willing to pay the overhead of keeping the Mesaworld in their machine. (E.g., the typical Laurel user should neither know norcare that Laurel is written in Mesa.) Among other things, this means that itmust be possible for the program itself to intercept all error reports, and disposeof them appropriately.CHALLENGE: Can LISP programs be packaged for standalone use? Is it possibleto use systems written in LISP without either knowing anything about LISP orpaying the overhead of the LISP system? Can LISP programs be made to processall internal and system error reports?[Items drafted by Mitchell:]Nfp b% _J ]G \ L Z9 W{I Tq QgN OP N]Q LO KSN I FI E?) B5 ?+J =M >Exception HandlingISSUE: There are three situations in programs that correspond to exceptions:(a) impossible states from which recovery is unlikely (usually anindication of a bug),(b) low-frequency states from which the program should be able toextricate itself (e.g., difficulty in reading a page from a disk), and(c) in interactive systems, user-initiated exceptions (e.g., kill thisprocedure call and the two previous and then retry).In case (a), whatever mechanism is used to inform the programmer (assuming heis there) of the error must have the feature that it does not destroy any of thestate information that he needs to investigate the bug. In particular this meansthat the execution stack should not automatically be rolled back as part of raisingthe error.In case (b), the errors that a procedure may raise should be part of its interfacespecifications (they are not currently in Mesa). The program that is selected tohandle the exception must be able to receive information (parameters) along withthe exception notification, and it must be able to permanently acquire control inorder to terminate the action. This will require rolling back the execution state(note that I am very carefully avoiding the phrase "cutting back the stack" -that is not what is needed ina multi-process environment). Such executionunwinding must be done in such a way that each outstanding activation that isto be terminated have a chance to handle the fact that it is about to die; thismakes the decisions about what special actions are needed for termination a localone within the activation being killed. The order of cutback must also bereasonable; e.g., in a procedural environment, they must be done in a LIFOorder, sort of like backward execution.Case (c) raises no issues that (a) and (b) have not already proboked. It isincluded here only for completeness and because an integrated EPE will need todo this.CHALLENGE: Can Lisp provide an error-handling mechanism with localhandling of termination and with the state-preserving property for debuggingpurposes?>>Processes and MonitorsISSUES: Processes and monitors provide a well-engineered way for introducingparallelism in one's programs. I doubt that they are the ultimately best way fordoing so, but they represent the state of the art and there is much experiencewith using them and with proving properties of programs that use them.CHALLENGE: What does Lisp have?>>CoroutinesISSUES: Some form of coroutines are needed to handle situations such as textformatting. The Mesa control structures are built from a common underlyingprimitive that allows one to call another program in a uniform manner withoutbeing aware of its control regime. The called program could be implemented as aprocedure or as a coroutine (there is more than one flavor). This makes a controlabstraction facility that is useful for object-oriented programming, since the userof an object can treat all operations as if they are procedures no matter whattheir exact implementation is.Nfp b _L2]A2\ 2ZA2YF2W{F2U4 RM QgP OQ N]S L IR HIQ FP E?Q CR B5M @J ?+M =O >Records, Parameters, Constructors, and ExtractorsISSUES: Record constructors are most frequently used as parameter records toprocedures in Mesa. Keyword notation eliminates errors of ordering of two ormore parameters of the same type (e.g., COPY[from: x, to: y, nWords: 256], forwhich I could never remember the correct order of "to" and "from" in thepositional notation). Making records first-class values requires that one be ableto write record-valued expressions. Programs are clearer when an entire value isspecified at once, rather than by a number of assignment statements. Also,writing a constructor enables the compiler to check that one has specified somevalue (possibly "don't care") for each component and enables one to have defaultvalues for some componenets. This also provides a way of having defaultparameters for procedures as well.Procedures need to be able to return multi-part values and not be limited to asingle value returned in order to avoid some uses of "output parameters." Mesaextractors then allow the programmer to perform multiple assignments of thosemulti-part values to separate variables for further processing. This is heavilyused in Juniper.CHALLENGE: Can the Mesa record/parameter facilities be provided in Lisp?>>Efficient Random Access to Files>>Debugger Access to SourceISSUES: One of Mesa's strong points as a system programming language is thatthe programmer can debug at the source level. This requires the ability tospecify and set breakpoints by reference to the source program (either by contextor by pointing). If the Mesa compiler were to do more global optimization (suchas Fortran H's, for instance), the programmer would still need to be able tocompile his program in a mode permitting the correspondence between sourceand object probrams to be maintained.CHALLENGE: I presume that Lisp has these features normally. What about theblock compiler?[Items drafted by Suzuki:]>>Readable ProgramsISSUE: It is important that one can express his algorithms clearly so they can beeasily understood by others. This is a non-trivial aspect of language design.Mesa has some features that help people to write clear and understandableprograms.Mesa provides the generally accepted control and data structures in forms whosesyntax corresponds well with their semantics. It follows many acceptedconventions of mathematics and conventional programming languages. Infixoperators, precedence of operators, and structural keywords all eliminate the needfor many parentheses and reduce the parenthesis matching problems faced byLISP users.CHALLENGE: Can LISP get rid of the parentheses and enhance readability ofprograms without falling into ambiguity?>>Precise SyntaxNfp b3 _L ]M \ N ZH YR W{Q UK TqO RP QgH O" LN KSO IM HIP F CH @" = :L 9K 7Q 6 P 4L 3J 1~% .tK , ) & #Q "LN I B 8O G .I R $J  I (  :1\6ISSUE: One advantage of Mesa is that the syntax is rigorously defined so thatwhen one writes a program it is known a priori whether it is acceptable or notand how it is parsed and executed.In CLISP the syntax is tied to the error checking mechanism in order toimplement language extension. Therefore, it is not easy to know in advancewhether what one writes is acceptable and even accepted whether it will beparsed as the programer wishes. If the program is not accepted or misinterpreted,then it may be difficult to guess the style of writing which CLISP likes.CHALLENGE: Can LISP be liberated from error-driven syntax? Can a precise,yet reasonably compact, syntax for acceptable programs be given?>>Enumerated TypesISSUE: A very useful tool in programming is the ability to create a type whoseelements have programmer-defined names. One example is a parse tree in acompiler where each node belongs to one of a finite number of classes like"assignment" and "addition".Mesa enumerated types provide this facility. They offer the followingadvantages:-efficient use of storage,-usable as array indices and for iteration control,-safe when used as array indices (no subrange overflow),-compact notation for subsets,-combined with Case selection, we can attain an efficientimplementation of multiple-branch control mechanism.CHALLENGE: Provide an equivalent facility in LISP.>>Case SelectionISSUES: As noted above, Case selection in conjunction with enumerated andsubrange types can lead to efficient multiple branches utilizing the hardwaredispatch control mechanism.Another feature of Mesa SELECT statements is that one can write relation tails asselection criteria so that evaluation of the first operands can be saved.CHALLENGE: Provide an equivalent selection capability in LISP.>>Control of Storage StructuresISSUES: Mesa makes it possible to increase storage utilization (possibly at theexpense of access time) by using the PACKED option. Fields can be as small asone bit.Mesa also enables the precise control of the layout of fields within a record fordealing with externally-defined structures (e.g., interrupt words).CHALLENGE: Can LISP provide equivalent density and control where required? >>Constant declarationISSUE: Constant declaration is a mechanism to bind a name with a valuethroughout the execution of a program, so that no statements can overwrite theNfp bM `N _" \ G ZL YJ W{R UI RJ Qg@ N] KSN II HIJ F CF B5 2@2?+32=82 "L BO N 8 .Q C J   F N H :1\7value. The mechanism is very useful in constructing reliable software, sincethis property can be checked locally.There are two levels of constant declarations in Mesa. One is "module constant"by which a name is bound to a unique constant throughout the life of amodule. One cannot even overwrite the value. The other is "local constant" bywhich a name is bound to a value, which may be different for each procedureinvocation, but cannot be overwritten.CHALLENGE: How can LISP ensure the security of name-constant bindings?DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFTNfp bM `% ]P \ F ZO YK W{& TqF Qg=L N26Inter-Office MemorandumToEPE Working GroupDateSeptember 21, 1978FromP. Deutsch, D. BobrowLocationPalo AltoSubjectMesa -> Lisp replyOrganizationCSLXEROX Filed on: lispreply.memo on Maxc1This draft responds to the challenges offered in Jim Horning's memo "DRAFT Mesa -> LispRequirements" of 9/14/78 (including Jim Mitchell's addendum) and Peter Deutsch's memo "UniqueSmalltalk capabilities" of the same date.PremisesThere are certain modifications and additions which we agree must be made to Interlisp (for theDorado environment), and which impact several of the items in the lists below, so we will enumeratethem in advance.We agree that substantial work needs to be done on the compiler. The byte compiler is muchcleaner and simpler than the PDP-10 compiler, and we believe that the additions to handle typedeclarations (including variant representations) and name scopes are straightforward.We agree that the notions of interface and scope need to be made explicit in the Lisp system in theform of objects with well-defined behavior -- used by the compiler, Masterscope, the file facilities,etc. Larry Masinter believes that adding a Mesa-like notion of interface to Masterscope isstraightforward. In particular, we believe that the Mesa arrangement of separating interfacedeclarations from both client and implementor should be supported. Our current idea forsupporting both these notions and fluid variables (see next paragraph) is to introduce an objectcalled a dictionary, which associates interpretations with names in a given scope. (We have anumber of design memos that expand on this idea.)We believe that it is appropriate to replace the current Lisp notion of free variables with acombination of lexical scoping and declarations for fluid variables (variables dynamically bound byname as at present). The MIT SCHEME dialect of Lisp has done this successfully, and aninteresting and efficient compiler for this dialect exists. Our present implementation can support thischange, but at great cost in runtime efficiency. SCHEME shows one way to improve the efficiencyat the cost of a fairly radical implementation change; we do not yet know exactly how we will wantto change our implementation.Both for lexical scoping and for other reasons, we believe we need to provide an efficient mechanismfor FUNARGs, or, more generally, for objects which can be appliedas functions. Such objects are generalizations of current Mesa procedure objects.We agree it is necessary to support a precisely defined infix syntax in a clean way. Our intent is toprovide some general-purpose parsing and unparsing (prettyprinting) mechanisms to handle thesyntax, and to define all our semantics in terms of extensions to S-expressions. Depending on howmuch non-local declarative information is needed for the translation, we may defer translation untilcompilation, until the user requests it, or until the first attempt to execute the function, but in anycase the entire function will be translated at once in a precisely defined way that does not depend on]gp c8q]r-q7Br ]q]r-q7Br Yq]r-q 7BrSsr M* GA Fi] D) At >r_ =03 ; 8V@ 6-1 5LU 2 G 023 /L -E , ; *I )\ '}1 $Q8% "/4 !G: "F =1/ ] 3 &> U R 7/ LX P B40 F! 8f  >Q_-Mesa -> Lisp reply2the dynamic environment.Horning's items>>Static checking (for type errors and undeclared names)Lisp already has a type calculus approximately as rich as that of Mesa (the type system done byKaplan and Sheil for DECLTRAN), including an S-expression syntax for declaring argument, localvariable, and result types. Currently checking is only done within a single function. Adding cross-function checking to Masterscope should be straightforward logically.Masterscope already has the capability to check for undefined names, both undefined functions andvariables which might not be bound.>>Static scopingSee "Premises" above.>>EncapsulationThere are some hard issues here -- Lisp doesn't lend itself easily to the kind of total encapsulationthat Mesa does. To the extent that lexical scoping conceals internal names, we can do a reasonablejob of keeping clients out of implementations. Linked function calls are an existing mechanism forremoving external access to local functions.Multiple instances of modules can be accomplished using FUNARGs. See "Premises" above.For object-oriented programming, see the discussion below under the Smalltalk list.>>Explicit interfacesSee "Premises" above.>>Consistent version checkingWe can use the same time stamp scheme that Mesa does.>>EfficiencyGiven the existence of the type system, including the (already existing) provisions for packedrecords, the compiler can potentially do as well as Mesa for manipulating scalar data. (There aresome issues here about instruction set optimization, however.) We believe that a combination ofcompiler analysis and user declarations can make possible the Mesa-style stack allocation ofcomposite objects with direct addressing, without running the risk of dangling references; werecognize this is not a trivial problem, however.>>Exportation of programs from environmentWe believe that this issue is partly a red herring: after all, even a Mesa.Image file contains copies ofall the system modules needed by the program. The irreducible minimum amount of "system" for aLisp program is about the same as that for Mesa, except for the garbage collector. Given thatMasterscope can take a fully bound Lisp program and find all the functions that are callable in anyway, we can certainly produce a virtual memory image file that contains only the necessary functions(in fact, we should be able to do better than Mesa since we don't need to take entire "modules"). frG b ^t [r8 XA W@ U&? T E PD OZ# L. I E Be A%E ?c >, :$3 7S 4 1k .? +5 ' $D #602 !J ,G = "1 * h EY ? ;@# O 1F >QY Mesa -> Lisp reply3System overhead during execution is essentially limited to garbage collection and other storageallocation functions. The arguments under Efficiency above suggest that it is possible to incur thisoverhead relatively rarely, and of course if a program does no dynamic allocation, even the garbagecollector (a Lisp program) need not be included in the image file.Lisp programs can currently intercept all software errors including dynamic type errors, array boundserrors, arithmetic overflow, etc. Lisp programs are not currently able to intercept and recover fromhardware errors or running out of storage. Mechanisms to preallocate storage and to pin code anddata into real memory, which seem necessary to take care of these, could be added to Lisp with nofundamental change.Suzuki's itemsAll of these items are essentially syntactic. All are either already present or very easy to add.>>Readable programs; precise syntaxSee "Premises" above.>>Enumerated typesThe DECLTRAN type system already has this at a semantic level; extending it to the representationlevel should be easy.>>Case selectionThis is a modest generalization of the present SELECTQ function.>>Control of storage structuresLisp already allows tightly packed records. Adding explicit user control over the layout is trivial.>>Constant declarationThe compiler already provides for compile-time constants. Local constants (not changeable afterinitial binding) are trivial to add.Mitchell's items>>Exception handlingLisp already funnels all exceptional conditions through a single point (the ERRORX function).These conditions look like a normal function call, so no state is lost. ERRORX can easily bechanged to examine the execution environment and call cleanup handlers associated withintermediate frames, in any desired environment (the dynamic environment of the error and/or theenvironment of the intermediate frame).>>Processes and monitorsLisp currently has no process or monitor machinery. Processes are easy to implement with the samemechanism as coroutines (see below). Monitors can be done the same way as in Mesa, provided thatobject-oriented programming is enforced (see the discussion under Smalltalk below).>>Coroutines frG b:% `K _"A ]B ZcC" X41 WY] UH TO Q#t Mr=% J# G Ds AGP ? < 9j@ 6> 332 / ,` +5$ ( t $r !] ,#: .Q/ "H ' q E3/ J ;S   ?QYBMesa -> Lisp reply4Lisp currently has a notion of an "environment descriptor" which is essentially an indirect pointer toa stack frame. Functions exist which provide coroutines using a single environment descriptor thatgets switched between the participants. A more general coroutine mechanism, that allowedcoroutines to look like function calls and returns, could easily be built, and made efficient with alittle microcode assistance (similar to the microcode assistance we will want for FUNARGs).>>Records, parameters, constructors, and extractorsRecords already exist. Extractors are a pure syntactic extension. Keyword notation already exists forconstructors; adding it for procedure parameters is fairly straightforward, even if no declarationexists for the callee (the names must be matched up at link or call time in that case). Providingmultiple return parameters (as opposed to a heap-allocated return record) requires some tinkeringwith the instruction set.>>Efficient random access to filesThere is no reason why Lisp and Mesa should be any different in this respect -- in fact, it is plannedto provide microcode support in Lisp for I/O streams.>>Debugger access to sourceLisp already provides for access to the source program. There is no current provision for putting abreakpoint in the middle of compiled code: internal breakpoints cause the function to revert tointerpreted form. Converting a PC back to a location within the source can be difficult, becauseLisp functions often have no statement structure in the Mesa sense (when they do, we can easilyproduce something like the Mesa fine-grain table): for a non-optimizing compiler we could do it byrepeating the compilation and stopping when the PC matched.Currently, the debugger cannot show frames (either function names or variable values) within acompiled block. It is logically possible to retrieve this information, although about as messy as forthe Mesa debugger.Smalltalk items>>Simple, extensible, macro-expandable, infix syntaxSee "Premises" for syntax. Once we get rid of CLISP and introduce a single uniform way of dealingwith non-standard S-expression syntax (like SELECTQ, PRINTOUT, etc.), we will be doing as wellas Smalltalk. We believe it is extremely important to do away with the current notion of compilermacros, replacing it by a scheme in which one gets the choice between closed calls, open calls (usingthe same definition), and macro-expansion (an arbitrary user-supplied function, the same forinterpretation and compilation, computes the form to be executed).>>Object-oriented programming (operation names local to each type, all operations generic, noneed to declare types, instance state automatically available)Generic operations, decoded according to the receiver type, can certainly be provided in Lisp now,at considerable execution cost. The real issue is how efficient various degrees of binding must be.The current Lisp approach is to introduce one level of indirection for function names in the normalcase, removable by declaration (linked calls), and no discrimination on the receiver type. If anoperation is declared generic, we can certainly provide microcode assistance for getting to the rightpiece of code.Making the instance state automatically available comes for free with an efficient FUNARGmechanism. However, we believe that the right approach is to go down the Mesa path of trying toeliminate the distinction between variable binding records and other kinds of records. We do notyet know what this means in terms of implementation structures; at the S-expression level, it frG b.8 `S _(1 ]31 \ 5& X3 UB% T-K R T Q#W O Lr" IF?' G5 D Aid ?D >_<% <_ ;U_ 9; 6M 5_ 3 0nt -Br4 *4. (%9 ' 6, %#B $urT "}B QZ > ?# d B! Z X  @ VV J L] ?Q]=Mesa -> Lisp reply5certainly means the ability to "open" records for direct addressing exactly as in Mesa. This "open"for instance variables can be inserted automatically when one uses an object-oriented interface.The scope restrictions associated with object-oriented programming have already been covered underHorning's comments. Private record declarations are the key to this. We do not know exactly howwe will make it hard enough for ordinary clients to penetrate an implementation, while making iteasy enough to examine (and modify?) state with the debugger.A more serious question is whether there are benefits from the object-oriented style that one gainsonly if nearly all programming is done that way. We do not propose to rewrite the Lisp system inobject-oriented style, although we think that most new packages will be written this way, and someincremental rewriting will probably occur.>>Inheritance of behavior through subclass mechanismWe think this can be provided through the dictionary mechanism mentioned under "Premises".>>No distinction between user- and system-defined typesTo the extent that programs are written in object-oriented style, there is no reason why themechanism for handling operations on integers, say, should be different from that for user-definedtypes. There is, however, a serious question as to what the default behavior of the compiler shouldbe: should a call to an undeclared function (i.e. a function for which there is no correspondinginterface declaration) be treated as generic or not? Addition is presumably an example of such afunction, if the argument types are undeclared. Making addition work properly for integers, longintegers, floating point numbers, rationals, algebraic expressions, etc. requires generic treatment. Wedo not have a good answer for this.>>Future directions: template-style programming, constraints, data base links in text objectsGiven Lisp's hospitality to programs that construct and manipulate programs, template-style orconstraint-oriented programming should be even easier to implement than in Smalltalk. Data baselinks in text objects (such as source code) require careful planning of the interface to the textmanipulation system, but again Lisp has a better package for this purpose (TXDT) than either Mesaor Smalltalk.Tools>>BrowserThe Smalltalk Browser depends on having all the system sources and documentation available on-line, and on the 3-tiered classification system (class category, class, method category). Classcategories correspond essentially to chapters in the Lisp manual. Classes correspond roughly to thepresent Lisp "packages"; object-oriented organization of packages would help firm this up. Methodcategories do not exist and would have to be added (probably as comments in a standard form).The facilities of the Browser are simply another program, probably quite easy to write using DLISP.Note that Masterscope, with its more extended idea of "relatedness", could potentially enable amuch more powerful browsing facility.>>Integrated on-line documentationHELPSYS is the best on-line reference documentation system available anywhere that we know of.Its drawback is that maintenance of the documentation is a tedious, non-incremental process. It willalso need to be re-implemented for the Dorado.>>Immediate incremental compilation frG b13 `F ]m\ [E Zc` X= UI T- S R20 Q#* M4 JF G7 Ds:" B$> Ai] ?"> >_H <Q ;U,< 9# 60- 3x[ 1J 0na .)8 -d *8u ' r #// "[@ U QQ K GB! D =% " K `S . #  h?Q[0Mesa -> Lisp reply6A very fast, simple, non-optimizing version of the byte compiler already exists. Our first approachwill be to divide up the real compiler in a way that reduces the amount of optimization withoutsacrificing capability, and then explore other alternatives if this turns out to be too slow.Packages>>Arbitrary-precision integers with smooth transitionsThis can be done as a package, although it requires some modifications to the error handlingmachinery to field overflow properly, and potentially complicates in-line compilation of integerarithmetic.>>Paragraph formatting (display and Press)The existing TXDT package provides most of this for files, and DLISP provides it for the display.Press output is a modest-sized package.>>Bitmap and display coordinate objectsDLISP provides some facilities for manipulating these objects -- unclear how much, sincedocumentation doesn't exist yet.>>Paragraph and picture editorDLISP has some kind of paragraph editor. A picture editor will have to wait for a redesign of thedisplay facilities in the personal-computer environment.>>WindowsDLISP has them.>>MenusDLISP has them.Other>>Non-preemptive window behaviorThe DLISP scheduler is not documented yet. It clearly has some ability to keep track of severalwindows all waiting for input, but the cross-window selection capability suggests that it requiresmore cooperation between windows than Smalltalk does. frG b X `4+ _] [u Xr6 UI T X R OZ* L.H J' G}' DQH B ? mesaresponse.memoXEROX We culled five major (read "potentially difficult to implement") facilities from the memos byBobrow and Masinter:1)Programs as data2)Variable syntax analysis3)Dynamic variable binding4)Safe language (subset)5)Automatic storage allocationThis memo summarizes the analysis presented at the September 21st meeting.1)Programs as data.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 LISPsense) uniformly throughout the environment, and (c) a universal pointer mechanism.S-expression representation. This seems straightforward in principle, though we haven't looked atthe details. We think that a representation other than parse trees should be explicitly defined,permitting the representation of parse trees to change as the compiler/language evolve.Atoms. The symbol tables built by the Mesa compiler currently include a mapping between sourceidentifiers and internal unique ids (atoms). At present, these mappings exist only on a per-compilation unit basis, implying that they will need to be merged into a global map when thecompilation unit "enters the environment". A similar merge presently occurs inside the compilerwhen the source program accesses an included module (i.e., the symbol table for that module isopened and the identifiers (used by the source program) are remapped into the current atom table).A merge into a global atom table therefore seems feasible, at least in principle.Universal Pointers. We will need pointers that carry the type of their referent with them. This inturn requires a scheme for universal type IDs, which do not currently exist in Mesa. It seemspossible to extend the techniques used to ensure uniqueness of record types to accommodategeneral types. Run-time efficiency is vital, so the check that two type IDs are equivalent must befast. We anticipate using the LISP "spacing" technique, which places all data structures of the sametype within a well-defined region of the address space (e.g., each page allocated for such dynamicstructures can hold objects of precisely one type). This scheme avoids keeping any type ID bitswith the pointer, but makes it difficult to point inside a composite data structure with a universalpointer. Two possible remedies have been suggested: (1) an explicit type identifier immediatelypreceding the (sub)structure, or (2) an indirection mechanism in the data structure itself. In anyevent, access to statically allocated variables (i.e., those in local and global frames) via universalpointers will have to be prohibited, unless special steps are taken to prevent problems with garbagecollection.]gp c8q]r -q4 r ]q]r -q4 r Yq]r-q4 q r qSsr M O L H` G_` E` DU` B` ?J  %GH #Q urP N N  U I B xO S nX c d\ +9 Z \>Z+Mesa Response to Lisp Challenge22)Variable syntax analysis.LISP provides three opportunities for the programmer to affect the parsing/interpretation of inputtext: (a) at scanning time, (b) at compile time, and (c) at function call time. (a) may beaccomplished by providing scanner escapes to user-written code, which will replace someappropriate substring of the current parsing context (i.e., the as-yet unclosed lists) with a piece ofprogram in S-expression form. It appears straightforward to provide a facility comparable in powerto LISP's readtables -- a more elegant mechanism might be desirable. (b) may be accomplished bymore-or-less conventional macro expansion along the lines of the Mesa mechanisms for in-lineprocedures. (c) is deemed undesirable and will not be provided.3)Dynamic variable binding.Mesa, at present, can only support static binding of identifiers. To be able to bind a name to avariable in an enclosing dynamic context, we need to know what variables are to be found in eachframe. Instead of the LISP default, we propose that variables to which dynamic binding may occurbe declared as such at compile time. The compiler can then produce a table of entries of the formatom -> for each compilation unit. Such a table could reside in the code segment, with a bit in theassociated global frame(s) to indicate its existence. Dynamic binding would then occur much in thesame way the signal-to-catch phrase binding occurs (but more efficiently).4) Safe languageBy a safe language we mean here one in which a pointer value of a given type POINTER TO T isguaranteed to point to a region of storage containing a value of type T. We will also consider arelaxation of this condition in which certain regions of the storage may not be safe in this sense; aslong as values stored in such unsafe regions do not themselves contain pointers to safe regions, thedamage which can be caused is confined to the unsafe regions.There are three ways in which a pointer variable p may acquire an improper value1)Lack of initialization - in this case the value of p is just the random bit pattern whichhappens to be in the storage occupied by p when it is instantiated.2)Incorrect computation - in general a pointer value can only be the value of some pointervariable (which could of course be a record component) or the result returned by a storageallocation. If pointer values can be computed in other ways, e.g. with LOOPHOLEs or theirequivalents, or by arithmetic, then there is no guarantee that such values point to storagecontaining values of the proper type.3)Premature deallocation - in this case p is pointing at a region of storage which oncecontained a value of type T, but is now being used for some other purpose.If none of these bad things can happen, then induction tells us that the language is safe with respectto pointers. In addition, it is necessary to do bounds checking on array references, since otherwiseevery array index is as dangerous as a pointer. Finally, array descriptors require the same treatmentas pointers.Preventing uninitialized pointers is straightforward, by generating code to initialize all pointers inprocedure frames when they are allocated, and in dynamic variables of record and array types whenthey are allocated. Mesa 5 will have language constructs for allocating dynamic variables, so it isknown where to do the initialization. frG btu ^r\ ]mU [&9' Zc$B XE WYE U9# TO@ Q#tu MrG Lrur" J/2 Ih;'F< CQ Ac @J L2<,H:9#9"*/7C25E( 2N 0\ / U -# *^ V (E 'T%2$).#wJ2!=2B1,88XF.^^+ur.kvrYur Yt ?Y]Mesa Response to Lisp Challenge4Our proposal is to have automatically deallocated (AD) types, and to use the Deutsch-Bobrowscheme for incremental garbage collection. This requires knowledge of the location and type ofevery pointer to an AD type, but the techniques are well-known and straightforward. frG bD `W _T. ^= =(Inter-Office MemorandumToEPE working groupDateOctober 26, 1978FromP. DeutschLocationPalo AltoSubjectXLisp/EPE planOrganizationCSLXEROX Filed on: xlispplan1.memo on Maxc1As requested by the EPE working group, this memo contains a gross (~5 item) plan for how wewould get from where we are to an EPE XLisp, including preconditions, and a statement of how wewould use 'warm bodies' to help us get there.Since the overall XLisp design has only been presented orally, there may be steps in the plan whosemeaning is not clear. A memo is in preparation which summarizes the relevant features of thedesign.PlanXLisp can evolve from our current systems in a series of steps, with a working (although not stable)system at each step. Here are the major milestones:1) Get Alto Lisp running on the Dorado. Major work on XLisp is not possible on anyother hardware -- the Alto is too slow and Maxc is too small. In particular, we need aDorado Lisp that uses the IFU and hardware map, and all of the Dorado's real memory.This almost certainly means converting the kernel from Bcpl to Mesa. These issues areaddressed in separate memos.The next two steps can be done in either order, but not in parallel.2a) Change the system to use shallow binding and have invisible indirection for variables.These are necessary for the lexical scoping rules and closure capability of XLisp. This hassome impact on the compiler and a major impact on the functions that handle the stack.2b) Add dictionaries to the system, but not lexically-scoped closures. This replaces theLOCALVARS and LINKFNS capabilities of the current system. It has major impact on thecompiler, interpreter, and record and file packages, and minor impact in many places suchas the editor and stack functions. Changing the way macros and special syntactic forms arehandled can be done later, but we want to eliminate error-driven interpretation early. Thisstrongly affects CLisp and user-defined macros and NLAMBDAs.3) Implement closures. This includes lexically scoped FUNARGs, and arbitrary closures likeMesa module instances.4) Implement the type calculus (types as objects, type checking), but entirely on a dynamicbasis -- no variant representations, and no compile-time checking. A good deal of this is inthe Decl package already.]gp c8q]r-q7Br ]q]r -q7Br Yq]r -q 7BrSsr M+ G9" FiK D- AQ @3D > ;t 8Vr5/ 643',2 M 0T/D-*eD'9 L%A$/D!>~A8!t[Wj<>? OJ<>QZXLisp/EPE plan25) Implement compile-time type checking. This affects the compiler, interpreter, and ingeneral any function that manipulates function definitions (e.g. GETD/PUTD, APPLY*).6) Implement variant representations. This has major impact on the instruction set (andtherefore the compiler), and on all functions that manipulate records or the stack.The following steps are necessary eventually, but do not affect the basic functionalcapabilities of the system:7) Implement an infix front-end. This requires writing (or stealing) a text-oriented editorand a prettyprinter, and interfacing them to the Lisp editor and file package.8) Implement permanent pointers. This involves completely rewriting the file package.Using volunteersOur ability to use volunteers depends somewhat on the ordering of the above steps, and on thequalifications of the volunteers. In particular, doing step 7 early might mean we could get somevolunteers who only really felt at home in Mesa syntax. Here is how we could use people to helpwith each step:1) Converting the Alto Lisp kernel to Mesa is mostly a transcription job, and could be doneby anyone who knows both Bcpl and Mesa with relatively little briefing required. The otherpeople-resource issues in Alto Lisp are discussed elsewhere.2a) The shallow binding conversion requires people familiar with Lisp, with Lispimplementation, and with the Alto Lisp internal data structures. 'Warm bodies' are unlikelyto be useful.2b) Adding dictionaries is a tricky job; much of the work on the compiler and recordpackage could be done by anyone familiar with Lisp, but much of it could only be done bythe implementors of the programs in question.3) Lexically scoped closures are a small task if done in a straightforward way. Any PARCLisp programmer could do it. We know from SCHEME (and even from GEDANKEN)that Mesa-style instances can be built on top of lexically closed FUNARGs.4) Implementing the type calculus requires understanding it, but little else. Whether webuild on existing Decl code depends mostly on who does the work.5) Implementing pre-execution type checking requires access to global knowledge of theMasterscope variety. Getting it done right probably requires an experienced person with anongoing interest in type systems and Masterscope-like issues.6) Variant representations are also tricky enough to require an experienced and dedicatedperson.7) Anyone can write a decent parser and prettyprinter, and an adequate editor.8) Permanent pointers, as part of a programming system, require some research. Integratingthem into the system will be an ongoing project. The basic design, and an implementationof the lowest level operations for using them, can be done by anyone experienced. fr GbX`%/]m%3[SX 1 #W7T ERNOZ@ L.t Ir%8 G}># EM DsAG N?=>=<;#.9/-8 4-'3V3%1-.0)- @ +J(oJ&@#++"9L =*/N=&1(Q Z>QUXLisp: a Lisp answer to the EPE languagechallenge- What are our goals?- What technical methods will we use toachieve those goals?- How can we achieve the goal in a step-by-step way?- What do we need (in time and resources) toput this plan into effect? a'p( ^ U Q' O J+ H5 C, AQ =<%}02Goal: upgrade (Dorado, Inter-)Lisp to includeimportant EPE attributes as listed in the EPE reportWe need to retain:- Totally automatic storage management- Easy program manipulation of programs- "Instant" turnaround for program changes- Lists and symbols as primary objects- Runtime type systemWe aim to add:- Type system with static checking capability- Abstractable interfaces- Improved runtime efficiency- Scope-oriented protection- Consistent compilation, version bookkeeping- Uniform notion of calling, instantiating, closuresNeq a'p- ^r ZCpVs&S<'O*LX&H Dp A.s-=:J63f-/4 ,;~;U3Method:Define system entirely in terms of dynamic objects -- name scopes, types,etc. are objectsStatic checking & optimization come through added declarationsDictionaries for name interpretation -- unifies notions of argument list,record, interfaceMaps names to attributes such as type (abstract & representation),protection, manifest value, etc.Protection is associated jointly with the dictionary and the path fromthe accessorDictionaries describe how to create instances of recordsCalling = instantiating (the frame) + copying (the arguments) +runningClosure formation = instantiating + copyingCoroutine transfer = copying + runningType system includes ideas of record formation (via dictionaries),specialization by adding attributes, extension (subclassing), multiplerepresentationsCoercion between representations (e.g. tagged vs. untagged) ordegrees of specialization is automaticChecking is done with EQ (identity)Permanent pointers extend the EQ concept to the file systemNeq a'p]sI[XU>TISOBMJiFH E,8A??<}+9 &5B3F2.>,&)T#%; "o5Eg4Plan:1) ****** Get Alto Lisp running on the Dorado(more about this next week!)2) ***** Add dictionaries for scoping only, not generalized closures3) *** Add generalized closures(at least one implementation of this already exists)4) ** Add a type calculus, but do all checking at run time(existing Decl package does a lot of this)5) **** Add compile-time type checking6) *** Add variant representations (e.g. unboxed numbers)7) * Add an infix (Mesa-like) front end8) ?? Implement permanent pointersResources:Think of * = 3 person monthsAll but (7) and perhaps (8) requireexperienced people who understand thesystem implementationWe think critical mass is 4 essentiallyfull-time professionalsNeq a'p]s-[rXUsET"Sr4Os>Mr*Jis(F<C,@& 7p 3d/#,%)%'" "5EwjProviding Lisp strengths in MesaThere are two levelsUpper:Integrated editorMasterscopeProgrammer's assistantLower:Programs as dataVariable syntax analysisDynamic variable bindingSafe languageAutomatic storage deallocation a'p [W U  RiN# K H FI  C >1I$=52Programs as dataAtomsStandard S-expression representationUniversal pointersUnique type IDs"Spacing"Discrimination by CASE or byassignmentVariable syntax analysisAt READ (scanner) time (read tables)At compile time (syntax macros)At execution time -- not in MesaNeq a'p\X$TUPKGD >:$6l2& -v1:=3Dynamic bindingNeeds a table which mapsVariableID => (location in frame,type)Mesa already does this for signalsNeq a'p\X!UQ"p M-W%4Safe languagePointers into regions of storage whichcontain system data structures or othersuch pointers must be handled correctly.There are three problem areas:InitializationComputation -- no LOOPHOLE,UNSPECIFIED, computed or overlaidvariants involving pointers, or pointerarithmetic; bounds checks for arrayreferencesDangling reference -- forbiddeallocationRelative pointers to data which doesn'tcontain absolute pointers need not besafeNeq a'p \&ZC'W(S_O JH5!E'B#@[ <9w 51'2%/ +E6w<N5Automatic deallocationUse the Deutsch-Bobrow incrementalcollector, as in Alto/Dorado LispNeq a'p\"ZC!Z U25x6Symbol table informationAtoms -- print name <==> internal IDName => (location, type) map for framesUnique type identifiersType ==> (location, type) map forpointer-containing typesNeq a'p\$X'TUP!Mq H6J)Inter-Office MemorandumToEPE working groupDateNovember 7, 1978FromP. DeutschLocationPalo AltoSubjectXLisp/EPE plan, revisedOrganizationCSLXEROX Filed on: xlispplan2.memo on Maxc1As requested by the EPE working group, this memo contains a copy of the 8-step plan presented inlast week's Dealer for how we would get from where we are to an EPE XLisp, includingpreconditions, time estimates, and a statement of what we would have at each step. This memosupersedes the previous memo xlispplan1.memo of October 26.PlanXLisp can evolve from our current systems in a series of steps, with a working (although not stable)system after each step. The steps listed below need not be done in exactly the order given, althoughI believe this order leads to the least total work. I also believe little parallelism is possible betweenany two of the steps, although, as my assignments of people indicate, a lot of parallelism occurswithin a single step. The names attached to steps other than the first should not be taken tooliterally -- the named people have not been consulted.The total of the figures below is: 87 work months, 27 1/2 elapsed months.1) Dorado InterlispWork months: 18Elapsed months: 6?People: Bobrow, Deutsch, Haugeland, Teitelman; Birrell, Fikes, Goldstein,Kaplan, M. Kay; Laaser, Masinter, ThompsonGet Alto Lisp running on the Dorado. Major work on XLisp is not possible on any otherhardware -- the Alto is too slow and Maxc is too small. In particular, we need a DoradoLisp that uses the hardware map, and all of the Dorado's real memory. Danny Bobrow haswritten a detailed memo on the subject of getting a Dorado Lisp up, including assignment ofpeople to subtasks.After step 1 we have a usable Interlisp system running on the Dorado.1') Shallow bindingWork months: 3Elapsed months: 1People: Bobrow (stack fns & interpreter), Deutsch (compiler & loader),Haugeland (microcode)]gp c8q]r-q7Br ]q]r -q7Br Yq]r-q 7BrSsr M+ GS Fi I DJ C_D @3t =r5/ ;I 9V u 8xr"? 6urO 5n6 2BI .v2-2+:2'EF:2%*"r0&!( MNAmE v20 2e2fg12 x >Q\EXLisp/EPE plan, revised2Change the system to use shallow binding and have invisible indirection for variables. Inaddition to performance improvements, these changes help support the lexical scoping rulesand closure capability of XLisp. This has some impact on the compiler and a major impacton the functions that handle the stack.Step 1' produces no externally visible changes in the system, except that GLOBALVARdeclarations are no longer necessary.This step can actually be done at any time; it is easiest to do here, when less code will need tobe changed. It requires people familiar with Lisp, with Lisp implementation, and with the AltoLisp internal data structures.Step 1' may not be necessary at all if microcode support for dynamic binding proves fastenough. I am inclined to think this will not be the case, especially if GLOBALVARdeclarations are eliminated.1") Clean up macrosWork months: 6Elapsed months: 1People: Bobrow (interpreter), Deutsch (compiler), Teitelman (DWIM/CLisp), any3 Lisp programmers (scan the system); defer work on MasterscopeChange the way macros and special syntactic forms are handled, to eliminate "error-driveninterpretation". In particular, eliminate DWIM corrections that require altering orexamining the state of the interpreter. This strongly affects CLisp and user-defined macrosand NLAMBDAs. Relatively small changes are also required in the compiler, interpreter,and Masterscope.The current MACRO scheme does not fit into the scoped view of the world, and has causedmany obscure bugs; NLAMBDAs make separate MACRO definitions necessary, and requireinternal EVALs, which we would like to eliminate since they will require elaborate run-timechecking. We can arrange things so that after step 1" the system will still run existingInterlisp programs, but MACRO properties and NLAMBDAs will produce warningmessages. On the other hand, packages like the iteration and pattern match statements willfit into the system much more cleanly.This too could be done later, but it makes things a lot simpler if the system doesn't have tosupport run-time DWIM correction while dictionaries are being installed. Any good Lispprogrammer can go over all the system code to change NLAMBDAs and macros to conform tothe XLisp scheme; only Warren can make the necessary simplifications in DWIM and CLisp.2) DictionariesWork months: 15Elapsed months: 2 (design), 3 (implementation)People (design): Bobrow, Deutsch, Masinter, Horning/LampsonPeople (implementation): Bobrow (stack & interpreter), Deutsch (compiler), Fikes(record package), Kaplan (dictionary objects), Teitelman (file package &miscellaneous); defer work on MasterscopeAdd dictionaries to the system, but not lexically-scoped closures. This replaces theLOCALVARS and LINKFNS capabilities of the current system. It has major impact on thecompiler, interpreter, and record and file packages, and minor impact in many places such frGbV`+/_R]'Zc5X%UuaT-VRO|FM4Lr Iv2G5 2Ej2A ?2@ ?[=#N;P8ruO 6G5hL37+ 0qv2. 2,.2)E'2%-2#' rP3S7FVuWH rI   v2  h >Q\nXLisp/EPE plan, revised5Elapsed months: 1People: Goldstein (prettyprinter), Swinehart (editor), Teitelman (integration)Implement an infix front end. This requires writing (or stealing) a text-oriented editor and aprettyprinter, and interfacing them to the Lisp editor and file package.Anyone can write a decent parser and prettyprinter, and an adequate program editor. This stepcould be done much earlier, and might help us get people who like Mesa syntax to work onthe system.8) Permanent pointersWork months: 6?Elapsed months: 2?People (design): Deutsch, Horning, SturgisPeople (implementation): Sturgis (primitives), Teitelman (file package)Implement permanent pointers. This involves completely rewriting the file package.Permanent pointers, as part of a programming system, require some research. Integratingthem into the system will be an ongoing project. The basic design, and an implementation ofthe lowest level operations for using them, needs someone who understands the considerationsthat go into file systems like Juniper. frG2av2^AN[r#<YHVduLT9SZ Ov2N2LR2H*2E&GArS>u==IJ; R:?' 99.rDRAFT - DRAFT - DRAFT - DRAFTDRAFT - DRAFT - DRAFT - DRAFTInter-Office MemorandumToPE GroupDateNovember 9, 1978 1:09 PMFromDeutsch, BobrowLocationPalo AltoSubjectXLisp design -- a detailed response to theOrganizationCSLMesa challengesXEROX Filed on: xlisp1.memo on Maxc1****** Note: this is a document-in-progress. It is not stored in the PE file on pe2>.Always check the date and time in the "Date" field above to make sure you have the latest version.******IntroductionThis document describes part of the design for a system we are calling XLisp. It is a dialect ofLisp, based largely on SCHEME (a lexically-scoped Lisp dialect developed at MIT), and addingmany capabilities derived from Mesa and other modern statically typed languages. The goals ofXLisp are roughly the following:Keep the current ability of Lisp to manipulate programs and to carry out computations withno type or scope declarations required, at approximately current efficiency.Add the ability to achieve greater efficiency and statically checkable protection, by addingdeclarations.Develop a conceptual framework for thinking about scope and type issues which has someroom for future exploration of capabilities not present in either Lisp or Mesa.The purpose of this document is not to exhibit a design that we think we could start to implementtomorrow: a lot of details are missing. Our purpose is rather:To demonstrate to the Mesa-oriented community that we really know how to achieve thevaluable capabilities of Mesa within Lisp, and that our view is not only implementable butconceptually clean (hopefully, cleaner than current Mesa).To persuade the Lisp-oriented community that the changes they will have to make in theway they do things are a small price to pay for the new power they will obtain through thisdesign.This document needs, but currently lacks, a tremendous amount of motivational and explanatorymaterial (including examples). One kind of material is needed for Lisp-oriented readers to answerthe question, "Why is this changed?" Another kind is needed for Mesa-oriented readers to answerthe question, "What Mesa challenge does this respond to?" In this edition of the design, because oftime pressure, we have opted for a presentation of the end result with little indication of how wegot there.Organization of this documentepj]g~ cq]r-q7Br ]q]r-q7Br Yq]r*-q 7Br]WSsr M' GI Fi V D At >r*7 = Q ;^ 96.,5LL2 <0 -o;+O (T '9?$ <"E!:J R/, M [ @ d :(  t ,#>hXLisp design DRAFT - DRAFT - DRAFT - DRAFT2This document is not organized properly yet. The right order of presentation is probably:Types excluding recordsRecord types and their dictionariesInterface types and their dictionariesFunction objects and environmentsMiscellaneousTypes****** This section is still confused. I- and D- types have come and gone at least twice. There is asection on declarations, assertions, and invariants near the end of the memo which indicates some ofthe source of the confusion. ******FrameworkTypes are objects, just like integers or lists. There are three kinds of types: interface or I-types,which describe how objects behave in general; descriptive or D-types, which specify predicates thathold true of objects in particular situations; and representation or R-types, which describe the bitpatterns used to represent objects inside the machine. Conceptually every object carries its I-typewith it at execution time, but not its R-type (D-types are associated with variables, not with objects).The system provides a default representation for every I-type. The phrases "X is of type T" and "Xsatisfies type T" are interchangeable -- I- and D-types are predicates.I-types are built up using the following operators (the names and Mesa-like syntax are forexpository purposes only):ANY[] is a type which all objects belong to.FLOAT[] is a type for floating point numbers of one particular precision and range definedby the "hardware".ATOM[] is a type for atoms.INTEGER[i1,i2:IntegerOrNIL] is a type for objects which can take on integer values fromi1 through i2 inclusive. NIL means there is no limit on that end.CONSTANT[x] is a type for objects which can take on only the value x. This is not asuseless as it sounds: for example, NIL occupies a special place in the type space.SATISFIES[p:FUNCTION[[ANY[]],[Boolean]],t:Type] is a type for objects x of type t suchthat p[x] is true.ANYOF[t1 ... tn:Type] is a type for objects which can be of any of the types t1 ... tn.ALLOF[t1 ... tn:Type] is a type for objects which must be of types t1 ... tn simultaneously.READONLY[t:Type] is a type for objects which are of type t shorn of any operationswhich produce externally visible side-effects (more on side-effects below).UNIQUE[t:Type] is a type which is the same as t, except that objects of this type aredistinguishable from objects of type t and of any other type created by UNIQUE[t]. Thisoperation is sometimes called "painting". fr"pGr b@^[#X&Un!RB Ot Kr*< Jed H# Eu Br>A 41,.a,.,)&R$B!!4 NR"4"q;E1+@K h7 X ^) >]0XLisp design DRAFT - DRAFT - DRAFT - DRAFT3FUNCTION[argT,resultT:Type] is a type for functions which take arguments of type argTand return results of type resultT. ArgT and resultT must be structure types.VARID[t:Type] is a type for variable id's of type t. Variable id's are used to link togetherbinders and users of variables, leaving the identity of the variable unbound. (Same idea asthe Mesa SIGNAL linking mechanism.)Structure types are discussed in a following subsection.[How do variant R-types get defined??]DeclarationsAn S-type declaration just establishes an invariant for a variable -- checked whenever the variable isstored into, can be assumed whenever the variable is used. S-types can also be used as predicates,and wrapped around expressions. R-type declarations specify the representation of a quantity andhence are only meaningful for variables, as opposed to arbitrary expressions. ("Variables" includerecord fields, of course.)Structure typesThe other kind of definable S-type is a structure type. It has named components, each of whichmay have type declarations. There are two kinds of components: fields, which obey certain rules setforth below that make them act like variables, and operations.Every field component has two associated operations called fetching and replacing that field. Theseoperations obey the following rules:(1) Fetching a field has no externally visible side-effects (although it may have internal side-effects like caching or statistic-taking -- obviously "visible" can't be defined rigorously). Inparticular, it does not affect the contents of any field.(2) Replacing a field has no externally visible side-effects on any operation other thanfetching that same field.(3) Fetching a field always returns what was last replaced into that field.(4) No operation other than replacing a field affects what fetching that field will return.The default R-type for fields is a storage cell: if the programmer specifies a different R-type, itsadherence to the above rules is up to him.Fields in structure types may have names, or an ordering, or both. The ordering is for argumentand constructor lists -- it has nothing to do with storage format.Arrays are a structure type in which the fields, instead of having names, are indexed by a set whichmay be of any type. If the type is an integer range, the default representation is a traditional array;if not, the default is a hash array.An interface type, in the Mesa sense, is a structure type with fields which are of various functiontypes. A Mesa module is a group of functions which all agree to use the same instance(s) of theinterface types they import. Making an instance of a module consists of making an instance of theinterface type it implements, filling in the fields with closures of the exported functions in which theimported interface pointers get bound.****** Fields require an instance. Smalltalk operations require an instance. Interfaces don'tnecessarily require an instance. How to resolve this best? Mention "fetch", "replace", "perform" fr"pGrbH `N]mK[DZc#W78 T & Pu MrM L.4/ Ja I$c G Dsu AGr1$@3*.AG $ ?F3?k.6? >==//=%5T>= ;C0D:5 ; 8L:j=;  9$6`;%4J3V90*?.+yK(MC %!*: #* pP B X :&B $ Z F E W u& IJ 5-  }=]HXLisp design DRAFT - DRAFT - DRAFT - DRAFT4syntax for things that need an instance.Conformity and coercionsType checking depends only on the S-types of the objects. The conformity relation isstraightforward to compute, given the type composition primitives. The compiler does all it can,and then produces code to do the remainder of the check.Coercions are meaningful at both the S-type and R-type levels. S-type coercions up or down thetype lattice are mostly either no-ops or type checks, and can be supplied automatically. Other S-type coercions require user-supplied functions. R-type conversions require user-supplied functionsto convert to and from the default R-type, the familiar Lisp typed pointer.Here are the coercions available among S-types. The notation t1 -> t2 means that an attempt isbeing made to convert a quantity U of type t1 to a quantity V of type t2.t -> ANY[]: no checking requiredANY[] -> t: requires a type checkFLOAT[] -> INTEGER[i1,i2]: may require a range checkINTEGER[i1,i2] -> FLOAT[]: always allowedCONSTANT[x] -> t: requires checking that TYPEP[x,t]t -> CONSTANT[x]: requires checking EQUAL[U,x]INTEGER[i1,i2] -> INTEGER[j1,j2]:If i2j2, not allowed.If j1i2, allowed with no check required.Otherwise requires a range check on U.SATISFIES[p,t] -> t': use algorithm for t -> t't -> SATISFIES[p,t']: p[U] must be true, and t -> t' allowedANYOF[t1 ... tn] -> t: for some j, must have TYPEP[U,j] and tj -> t allowedt -> ANYOF[t1 ... tn]: for some j, must have t -> tj allowedFunctions, closures, bindings, and environmentsFunction and environment objectsCurrent Interlisp encourages the user to confuse function names, list structures representingfunctions, and function objects, but does not treat them uniformly: for example, the first argumentof APPLY* may be a function name or a list structure, while the second argument of PUTD maybe a list structure or a compiled or SUBR function object.In XLisp we distinguish between code objects, which are merely different forms of program text,and environment objects, which may contain values for some or all of the variables of the text.There are three kinds of code objects: primitive (representing SUBRs and microcoded functions),compiled, and interpreted functions. Conceptually, every code object contains a pointer back to thenaming environment (called "scope" below) in which it is embedded: an interpreted code object isthus not simply an S-expression, but rather a pair .In XLisp the only thing that can be executed is an environment object, or EO: EOs, and only EOs,are legal as function definitions. An EO is either a code object or (recursively) an EO plus bindingsfor some of its unbound variables. The state of an EO logically always contains two components:What kind of data the environment expects when control next arrives: none, a particular fr"pGr b( ^u [r"9# ZAP X8 UP T b RK QK MC LPII$G!Ds4B)?3>=.;!987`8 j7`!8#6&3V/1<.K- < )t/ &u #r0- "L #8  : , ~(W \ R\H P R9+ ,4 HI >"  Z I ; Z >]l)XLisp design DRAFT - DRAFT - DRAFT - DRAFT5argument list, or an operation id and associated arguments. Note in particular that thecontinuation, i.e. the identity of the calling EO, is an argument.Whether a new instance of something needs to be created when control arrives. (A newinstance is always created if the environment expects an pair.)Naturally, when an EO transfers control outside itself, it specifies what kind of data it is passing tothe new EO: none, an argument list, or . If the sender does not pass itselfas the continuation, then (in effect) it has lost one reference to itself, and if there are no morereferences it can be freed. An example of this is a function return.A traditional Lisp function is an EO which expects an argument list and creates a frame to hold it.A closure (more on these below) is an EO which already has one or more frames as part of it. ASmalltalk instance or Mesa module instance is an EO which expects andcreates an appropriate frame.Some kinds of EO cause errors if an attempt is made to execute them with any of their variablesunbound. For EOs that do allow such execution, then an error occurs if an attempt is made toactually reference an unbound variable. Clearly we will want several different representations ofEOs depending on how much and what kind of state information they include, corresponding todifferent kinds of functions, closures, and environments.Closures****** Need to talk here about local and fluid variables; how interfaces get hooked up; variouskinds of instantiation (Mesa & Smalltalk modes). How VARID types with the extra level ofindirection do SIGNAL binding and Lisp dynamic variables.Given the existence of fluid variables, there are two different kinds of state one might wish tocapture in a closure: the current bindings of the lexically enclosing variables, and the current fluidbinding environment. An XLisp closure always captures the first of these (but only the bindings forthose variables actually used free within the function being closed -- this is determinable statically);optionally, the programmer can specify whether the fluid binding environment is to be captured aswell. (Individual fluid bindings can be captured by rebinding them to local variables, and thenrebinding the fluid variables to the captured values inside the function -- of course this can be donewith a macro.)SyntaxIn current Interlisp, LAMBDA and NLAMBDA play an anomalous role as syntactic markers,different from any other syntactic context. XLisp follows the SCHEME convention: NLAMBDAdoes not exist, and LAMBDA is a function which takes an argument list and a body and returns afunction object. This leads to few changes from the user's point of view: the main one is that thestandard representation for a functional argument becomes simply (LAMBDA --), although(FUNCTION (LAMBDA --)) can still be acceptable by making FUNCTION a macro.The form (NLAMBDA var . forms) can be converted to a MACRO with the definition(LAMBDA (FORM) (SUBPAIR 'REST (CDR FORM) '((LAMBDA (var) . forms) (QUOTE REST)) )),and similarly for NLAMBDAs which spread their arguments, but this leads to very inefficientexecution. There is no way to duplicate Interlisp's handling of NLAMBDAs exactly, sinceMACROs are not functions and cannot be APPLY'ed or APPLY*'ed. We see nothing wrong withthis.****** Need to do something about multiple return values. Maybe (RESULTS form var-for-val2 ...var-for-valn)? fr"pGrbO`B]mM[O Xg W7B UQ T-E Q V O|\ M-/ Lr IF6) GG F<(: D[ C29 @u \<XLisp design DRAFT - DRAFT - DRAFT - DRAFT6ProtectionMesa provides four kinds of protection that are not checkable at compile time:1) Variables, unless otherwise declared, are not accessible at run time by programs outsidethe lexical scope where they are defined.2) A client and an implementor must use identical (EQ) versions of an interface.3) An implementor can define types whose contents are (partially) private, but which theclient can use to declare variables.4) The types of the arguments passed in a control transfer always agree, regardless of howthe environment receiving control was obtained (e.g. by binding, through a PORT, througha procedure variable).All of these are based on intra-module checking by the compiler, and inter-module enforcementbased on (2). This, in turn, is accomplished by creating a unique name for an interface when it iscompiled, and copying that unique name into both the client and the implementor when they arecompiled.Our type checker provides (2) by simply using EQ -- XLisp always keeps with any compiled objecta pointer to the dictionaries accessed during compilation, which include all imported and exportedinterfaces. The permanent pointer mechanism described under Miscellaneous below guarantees thatthe EQ relation is correct even when externally filed data are involved.(4) is also a type checking question. If the user declares procedure and environment variablesappropriately (which is automatic if an interface dictionary is involved), then the check can be madewhen the interface is bound rather than at the time of the control transfer.The privacy information in dictionaries and scopes provides (1), since the only way to access a non-local variable is by going from a frame or other object to the dictionary that describes it, and theoperations to access objects in general are implemented within dictionaries and check the privacyinformation. For programs like editors that must be able to make changes in dictionaries, weprovide a way to make a less-protected (but non-EQ) copy of a dictionary, and an operation thatreplaces the entire contents of a dictionary with that of another, rejecting it if it does not satisfyappropriate protection requirements. This operation also decides how much current state isinvalidated by the change.The heart of our protection system is (3). Something like (3) is required to be able to have virtualobjects, and objects accessible only through interface procedures (operations). In XLisp one candeclare a record type as having sealable instances. What this means is that the record has a piece ofcode associated with it, and a "sealed" flag. If the record is in unsealed state, anyone may access itfreely. If the record is in sealed state, only the associated code may access it. A record must besealed to be used as the local environment of a function: the operation of calling a functionlogically breaks down into the steps of creating an instance of its local frame type, filling theparameters into the instance, sealing the frame, and then running the function. Similarly, recordswhich define Smalltalk-like instances are sealed in a way that accepts incoming messages and thenexecutes the implementing function. Such functions can access the sealed record by having a linkin their scope structure that says they implement an operation on that record. (This is no less safethan the IMPLEMENTING construct in Mesa.)A sealable record and its underlying unsealable record are two different types. Coercing the formerto the latter (going into an implementor) requires that the sealed flag be set. Coercing the latter tothe former is always possible -- the result is always sealed. The implementor can specify anarbitrary error check to be applied to a sealable record in order for the seal to be set: the check andthe sealing take place atomically. This can be accomplished by copying the record, doing the check, fr"pGr bt ^rN[(3ZA)WPSSRd$O8AMPL. I/. G}[ EO Ds AG'8 ?Y >=,4 <H 9)6 814 6L 3VJ 1X 0LU .<! -B&9 +!E *8J ( % Y $M "}( "&#"}> ] s\ /. iL E _)8 H UH ) /5 O I 16 Gj I=\cXLisp design DRAFT - DRAFT - DRAFT - DRAFT7and then atomically copying the checked result back. Alternatively, the record can be accessedthrough a level of indirection, and the indirect pointer can be disabled at the start of the check.DictionariesA new kind of object called a dictionary is central to the interpretation of names (and, hence,programs) in XLisp. A dictionary consists of one or more name tables, each of which applies to adifferent syntactic context (currently, only "function" or "variable") and specifies the interpretationof a set of names in that context: each entry in a name table consists of a name (litatom) and anassociated property list. We have already discussed dictionaries above -- they are what defines astructure type. Every function has an associated dictionary whose fields are the function'sarguments (functions of an arbitrary number of arguments have numbered, rather than named,fields).****** What's on the property list?Names vs. atomsIn current Interlisp, global values and function definitions are associated with litatoms. In XLisp,they are associated with pairs, where the name is a litatom. For fluidvariables known globally, the distinction can be ignored, but the functions to manipulate values anddefinitions (GETD, GETATOMVAL, etc.) will all be redefined or extended to take an environment(scope plus execution environment) as argument.ScopesConceptually, a scope is an area of a program within which the interpretation of names does notchange; implementationally, it is an object which specifies how to determine the meanings of names.We will freely confuse the concept and implementation in the discussion that follows.A scope is made up of components, each of which gives the meaning of some names, and a rule fordeciding how to resolve conflicts and what to do with undefined names. Each component may be ascope itself, or it may be a dictionary, which actually associates names and meanings.Scopes are built up and modified in four ways: by declarative information that is part of theprogram text; as a side effect of certain program constructs such as LAMBDA and PROG; byediting or otherwise operating on the program; and by direct calls on the functions that operate onthe representation of scopes. [How do we confine the last of these to safe uses??] Scopes are not a"compile-time" phenomenon -- they apply equally to interpretation, analysis, and all modes ofcompilation -- but compilation can be viewed as a process of binding scope-derived information intothe code.Every name in a program must eventually resolve to a meaning of one of three basic kinds:manifest, in which the actual value is found in a dictionary (for example, local and system functions,record names, and what are now thought of as compile-time constants); dynamic, in which the valueis found in a run-time data structure (for example, most variables and non-local functions); orunbound, in which only declarative information (if that) is available. Unbound names must bebound before a function using them can be compiled, or before a reference to one can becompleted successfully during interpretive execution; however, editing, printing, analysis, andinterpretation of other parts of the function are possible even in the presence of unbound names.In principle, every dynamic name eventually reduces to a value obtained by applying elementaryoperations (at roughly the instruction set level) to constants and to pointers which form part of thevirtual machine's state, such as the current stack frame pointer. Thus, in principle we only needone kind of name table entry: a way to macro-expand a name into a form eventually containingonly constants (since ultimately the primitive operations are represented by constant functionobjects). An appropriate set of primitive operations would be: fr"pGr b.1 `D ]mt ZAr# Y%ZA7 XE0GXe27yX W7:- UK T-b R\ Q#S O Lr# IFu FrP D2( CK A$9 @/ ! UP )> &? 8* A 9% ? I>\XLisp design DRAFT - DRAFT - DRAFT - DRAFT8(FLUIDREF fluid-cell) -> field-reference(LOCALREF variable-number [frame-pointer]) -> field-reference(FIELDREF field-descriptor [base-pointer]) -> field-reference(FETCH field-reference) -> value(REPLACE field-reference value) -> value(ENCLOSING [frame-pointer]) -> frame-pointer (the lexical access link)(CLOSURE function-object var1 ... varn) -> function-object(APPLYFN function-object fluid-binding-link arg1 ... argn) -> value(A field-reference is a new kind of reference object which can be used for either fetching orstoring.) Indeed, these primitives are available in the system, since they are needed for theinterpreter and compiler, but their use is deliberately rendered inconvenient (except for APPLYFN)since it can lead to violations of scope rules on which not only compiler optimizations but thecorrect working of programs may depend. (The mechanism for isolating the use of these primitives,like the even lower-level primitives like CLOSER, is to install the corresponding primitive functionobjects, not in the global dictionary, but in a private dictionary. Scopes using these operations mustmention this dictionary explicitly.) As is usual in implementing protection systems, we provide,instead of these primitives, a set of higher-level constructs that cover all programming needs abovethe lowest level of system implementation, which lend themselves better to static analysis and permitmore enforceable protection boundaries.Here, then, are the constructs actually provided in the form of different kinds of name table entries:(MANIFEST value) -- the actual value is present in the name table. The value may be anyLisp object (data structure, function object, etc.). The value is treated as a constant:changing it may require recompiling any function that uses it. If it is a non-scalar value, itis only given out in read-only form, and editing requires copying the affected part and thenrecopying when installing in the name table.(SCRATCH value) -- the value is present in the name table, but it is not read-only. Onecan think of this as an OWN structure in the Algol sense.(MACRO function-object) -- the name table contains a function which is applied to theform (application or atom), and the result is taken in place of the original form. It is vitalthat macros produce consistent results, i.e. only depend on the form being expanded andthe scope in which it is being expanded. We assert that is sufficient to analyze the macrofunction and all functions it calls to make sure that they refer only to local and manifestvariables, and to pass the macro function its arguments in read-only form; then anyoperations with side effects, if applied to objects not created during this call of the macrofunction, will cause an error.(FLUID fluid-cell) -- this is the traditional Lisp binding method. Note that function andvariable names are different for fluid binding purposes, and that the name itself is not aglobal litatom but an object local to the dictionary, so that the binder and the user of afluid name must share the dictionary.(UNBOUND)(LOCAL location-in-frame) -- this is the SCHEME lexically bound variable. It differs froma fluid variable in that closures which use local variables free retain a shared pointer to thebinding in effect at the time the closure is created, while a free use of a fluid variable refersto the binding at the time the closure is applied. (See the discussion of Closures underFunctions, above, for more detail.) LOCAL names are also used for fields in records: inthis case, location-in-frame defines the location of the field within the record instance.(RELATIVE name scope base) -- this is used to refer to objects found in other scopes.Examples include argument or outer PROG variables referenced from within a PROG,instance variables and abstract operations in a record, and individual entries (usuallymanifest or fluid) imported from other scopes. A relative entry contains three parts: a fr"pGrb(`=_=]\ (ZFY:W{C U= Tq^ R'; QgN O;' N]K Lb KSA I=' HI@% F' C33@lQ>?=bU ;>:X,7,I592{C06)/qS-F,g>*9)]I'$M #'E!"8 %$6@'8-ur6&ur(>,>; {P W qO *=]hXLisp design DRAFT - DRAFT - DRAFT - DRAFT9name, a pointer to the scope in which to interpret the name, and, if the interpretation islocal, an expression (interpreted in the original scope) which gives the base pointer. Thisbase pointer becomes the default base pointer for the purpose of the interpretation, socascading of relative entries will work properly. The Mesa OPEN construct amounts tomaking appropriate RELATIVE entries in the current scope for all the names in the objectbeing opened.MiscellaneousPointersIn current Interlisp, the only way to protect a structured object which the system allows the user toaccess is to copy the object when it enters the protected area and copy it again on any request tosee it. We choose to provide a more efficient mechanism that has many other uses as well, namely,to introduce a read-only bit into pointers: this still requires copying going in, but not going out.The read-only bit is propagated, in that any pointer retrieved through a read-only pointer is maderead-only.The MIT Lisp machine uses a combination of shallow binding and "invisible indirection" to achieveits efficient implementation of lexical scoping and correct semantics of closures. We intend to usethe same technique. This requires being able to specify in a local variable binding in a stack framethat a fluid cell is to be used instead, which is a limited form of invisible indirection. We don'tcurrently plan to provide this in other contexts.SyntaxThe syntax for programs is ultimately an S-expression syntax. There are two ways that this syntaxgets extended:There will be a preprocessor that converts an infix notation into S-expressions, and aprettyprinter that inverts this process, so that corrections made to the S-expressions caneasily get reflected in the infix source. We don't have any prejudice about which notationprogrammers will prefer to use -- both will be supported for listings, editing, etc. Programs,however, will always operate on the S-expressions.Macros can produce alternative syntax at the S-expression level. AND/OR, PROG,SELECTQ, and CLisp constructs like the iterative statement are good examples of this.Some such constructs (like the iterative statement) are complex enough to be packages intheir own right. However, such alternative syntax is always introduced by a well-defined(macro) name in the function position. We may support the CLisp technique of cachingthe translation of such constructs, to speed up interpretation.We feel that CLisp-style "error-driven interpretation" is a mistake: the language should be definedin such a way that if an execution-time error occurs, it is the result of an erroneous computation orsource program, not of a construct that the user thinks of as valid but that just happens to getexecuted through the error machinery.Even in present Lisp, "program syntax" is more than the syntax of expressions -- it really includesDECL constructs, BLOCKS declarations, fileCOMS syntax, etc. ****** We haven't yet really dealtwith the question of syntaxes for defining linkage and dictionary construction.FilingExternal filing systems provide capabilities (e.g. backup, archiving, scavenging, sharing, largecapacity, very high reliability) that we do not understand how to provide entirely within aprogramming system. XLisp programs contain inter-program references (to dictionaries, inparticular) that must be representable on external files, so that a program knows it will have the fr"pGrbH`8$_5"] I\ XZ WYt T-u Qre O|G M=% Lr+9 JN Ih F<M D/5 C2Q A^ @(1 J % _T H UO )u rZ xH Y nM '>\FXLisp design DRAFT - DRAFT - DRAFT - DRAFT10same environment when run subsequently, rather than some environment made up of objects thathappen to have the same strings as their names.We define a new object called a permanent name (PN) which consists of two parts: a file name (astring), which is to be considered only a hint, and a permanent id (PID, an integer of roughly 64bits), which is the actual name of the object, and which is guaranteed different for every permanentobject. Potentially, many different kinds of objects have permanent names -- function definitions,dictionaries, maybe any object whatever. To find the object addressed by a permanent name, it isnecessary to hunt around in the file system, presumably starting at the file named in the PN, untilan object with the right PID is found. Each file contains a directory (like the Interlisp filemap) thatmaps PIDs to text representations of objects in the file.A PN is only needed for an object if a cross-file reference (or multiple reference within a single file)is made to it. PNs and PN directories are large, so we think it would be satisfactory to assign a PNonly when (1) an object was written on a file, and "potentially referenced via a PN" was a propertyof its type; (2) a program asked for a PN for an object.PNs are a basic mechanism for constructing permanent pointers. To make them useful, one needssuch things as the notion of versions of an object, directories mapping PNs of original versions toPNs of current versions, etc. The crucial question is one of overwriting: how can one change anobject without changing its PN? Fortunately most (all?) file storage systems provide some kind ofatomic operation which is guaranteed to execute either completely or not at all, and an atomicoverwriting operation can be constructed using this.Declarations, assertions, and invariantsThere seem to be two kinds of declarations/assertions:Those which are associated with control, i.e. which hold precisely when control reaches aparticular point in the program.Those which are associated with objects, i.e. which hold throughout an object's lifetimeindependent of the flow of control.Type declarations for fields are a kind of object assertion. They are easy to enforce, by simplychecking whenever one stores into the field that the value being stored is of the right type.However, more complex invariants relating various fields of an object cannot be enforced this way.What seems to be needed for this case is a way to make updating operations apparently atomic.The accepted way of implementing this is to use monitors. An alternative method with slightlydifferent consequences is an atomic multiple-store operation in the language. This avoids thenecessity of ever having the object in a programmer-visible state that contradicts the invariant, at thecost of some programming awkwardness.One place where this problem arises in particular is in the initialization of objects. Invariantscannot be guaranteed to hold until the object has been initialized properly. We first encounteredthis problem in the context of argument records: the function may have complex criteria forargument legality, which cannot be checked until all the arguments have been computed. In thiscase there is normally no problem, since the construction of the argument record and the storing ofthe argument values is an atomic operation from the programmer's viewpoint. The right way totake care of this seems to be the same as in Alphard, namely, to allow implementor-specifiedinitialization code.Topics not covered adequatelyHow do scopes get built out of dictionaries -- search rules. fr"pG?r b\ `/ ]m. -] )*V]m1 [",[%4[ Zc22 X:) WYI U7, TOI R9 O;- NV LJ K8 GE F^N D6* CT_ AN @J4 =u( 9r66ur5A2ur10# -dL +Q *ZL (B 'P^ %<" $F#E "% N b = *5 T P w)3  t r<T S>YXInter-Office MemorandumToEPE working groupDateNovember 15, 1978FromLampson, Levin, SatterthwaiteLocationPalo AltoSubjectPlan for an Interim IntegratedMesa EnvironmentOrganizationCSLXEROX Filed on: [Ivy]PE2>IME.bravoThis memo describes the steps required to obtain an interim integrated Mesa programmingenvironment. We establish the following ground rules:1)The intended user community for this environment is a small corps of experts who will useit to construct a more lasting integrated Mesa world. Consequently, the proposed system isnot idiot-proof and occasionally delivers its function in less-than-ideal ways.2)The primary purposes of this environment are to speed up the edit/compile/debug/editloop by removing the Alto Executive as the link between weakly-communicating programsand to exploit the large real and virtual memories of the Dorado.3)This system is only intended to work on the Dorado.We divide the development into two phases. Phase I will be concerned exclusively with theconstruction of the environment proper and a fast edit/compile/debug/edit loop. A change to amodule will require recompilation of that module and any other modules that depend upon it.Configurations whose constituent modules change will have to be rebound and reloaded, causingdata in their frames to be lost. Phase II will produce a system that relaxes these requirements incertain common situations, thereby eliminating unnecessary recompilations and loss of data in thesecases.Approximate Effort to Construct Phase I System: 9.5 work-monthsApproximate Effort to Construct Phase II System: 4 work-monthsPhase I DevelopmentPhase I represents the bulk of the effort. When completed, it will have produced an environmentin which a text editor, the compiler, the binder, the debugger, and the user's program(s) are allsimultaneously available. The components of the Phase I system are listed below with estimates ofthe effort required to produce them.MicrocodeThe present Dorado Mesa microcode supports Mesa 4.1 and precisely emulates the Alto behavior.It is therefore extremely inconvenient to access more than 64K of primary memory. The microcodewill have to be extended to be functionally compatible with the present D0 implementation, whichrequires the addition of instructions that manipulate long pointers (24 bit addresses) and page]gp c8q]r-q7Br ]q]r-q7Br Yq]r]W-q 7BrSsr N"q# Gr&1 F6BAA [?aO<<:jL8A5s3 2$< 0|1- .F -,G +` )M (4 $t0r #=t1r u r` #R {C $ t 5r7& &: B =Z 0 >^ Plan for an Interim Integrated Mesa Environment2faulting. Approximate effort: 1 work-month. (Note that this work will be done regardless of IMEplans.)SystemThe Alto/Mesa runtime environment will be carried over to the Dorado more-or-less intact. Theactual movement of code requires only recompilation (to take advantage of the microcode discussedabove). Functional changes are required to handle page faults and support (code) segmentallocation in the 24-bit address space. Nearly all of this work has already been done for XMesa(the version of Alto/Mesa that exploits the extended memory of a wide-bodied Alto). The onlyadditional substantive change is a virtual memory maintenance facility. We expect to implement asimple-minded scheme in which the virtual memory is mapped onto a contiguous region of the disk,thereby eliminating the need for paging tables. Approximate effort: 1 work-months.An rudimentary protection scheme is required to keep the various programs from clobbering eachother. We intend to give each major entity (compiler, debugger, editor, etc.) its own MDS (maindata space - a 64K region of the virtual address space that is implicitly addressed by short (16-bit)pointers). Code segments and symbol tables (see below under Compiler) will reside outside allMDSs and thus be accessible only via long pointers. Since any program can fabricate a longpointer and use it, we cannot prevent arbitrary access, but by using the write-protect facility of thehardware memory map, we can prevent arbitrary modification. When a particular MDS isexecuting, all other MDSs, all code segments, and all symbol tables will be write-protected.Switching control from one MDS to another requires changes to the map entries for all pages ineach MDS. Code segments and symbol tables remain write-protected except when the compiler anddebugger find it necessary to modify them (e.g., setting breakpoints, cache update). Approximateeffort: 2 work-months.Interactive BaseWe envision a window-oriented display manipulation facility as the basis for interaction with thevarious programs in the environment. The package presently used in the Mesa debugger suppliesadequate function, albeit in a somewhat awkward fashion. It is likely that this interface will bereplaced by the one used in the Tools Environment, possibly within the next few months. (Thisconversion would be done by the Mesa group and become part of the official, released debugger.)Approximate effort: 0 work-months (That is, we'll take what they give us.)An alternative package (called Chameleon) is being developed by AOS to support market probes.This interface will probably share many of the ideas of the Tools interface, but package themsomewhat differently. In particular, Chameleon expects to find a data base package (AOS calls itIliad) and understands a variety of scenarios for interacting with the data base. Chameleon willsupply a text editor as well (see below). Approximate effort: 0.5 work-months. (That is, we won'tadopt this package unless it appears stable and we can use it with only minor tweaks.)Text EditorThere are (at least) two sources for a text editor of adequate functionality (i.e., about what theLaurel editor provides). The Tools group have an editor that runs in the Tools environment.Obviously, if this environment becomes the interactive base of IME, we can adopt this editorvirtually intact. (Smokey believes we can alter the command set easily to provide globalsubstitution, etc., if we want.) The editor uses a quick-and-dirty form of piece tables (every piece isan integral number of lines), which means it is probably somewhat wasteful of disk space.Approximate effort: 1 work-month. fu/G br tr) `v ]'t Yr1- X0F V> T(8 S8'6 Q=$ O)7 N@1tr J4* II V GE E^ DQT BS A#2 ?Y5' =!= < 1- :a8t 8r 5jt 2rL 0sL .9) -#2, +{O )tr: &<! $4) #4a !F +tr! <V t r U O N O &3 H VM tr g>ZVPlan for an Interim Integrated Mesa Environment3Chameleon will also provide a text editor, whose functions will resemble those of the Laurel editor(but cleaned up a bit). Doug Brotz is slightly skeptical about unplugging the Chameleon editor andinserting our own, but agrees that there should be no problem "in principle". The Chameleoneditor will understand about data base records and manipulating fields of such records, a feature wemight want to play with, but don't really need. Approximate effort: 1 work-month.(The effort estimates above are intended to be upper bounds. Butler believes we can "hacktogether an editor in 2 work-months", so we probably shouldn't invest more than 1 work-month insome other package.)CompilerIn Mesa, every module has an associated symbol table. Both the compiler and the debuggermaintain a cache of the symbol tables they manipulate, though the limited memory space on theAlto tends to restrict the effective size of these caches. We propose to maintain this cache in thevirtual memory space and change the compiler and debugger to share a single cache, whose entriesare accessed by long pointers. Ed Satterthwaite believes this compiler change is nothing more thana recompilation with an altered definitions file. Once this separate cache exists, the compiler's"front-end" processing of the DIRECTORY statement (which maps symbol table names to Altofiles) has to be reworked in a straightforward manner. Approximate effort: 2 work-months.DebuggerIn IME, the debugger will be "in control". That is, the command language (such as it is) will beinterpreted in the debugger. Thus, the existing command processor will be extended to includecommands that trigger editing, compilation, binding, etc. This will require that the Alto/Mesadebugger's interface to the "debugee" (currently, Inload/Outload) be replaced by the MDS-switching mechanism described above. Data in the debugee will then be accessed by long pointersinstead of reading Swatee. The debugger will also be changed to use the common symbol tablecache. Approximate effort: 1.5 work-month.BinderThe Mesa binder combines configurations (of which the compiler output is a degenerate case) toform new configurations. In the Phase I system, when a configuration changes, all configurations inwhich it appears must be rebuilt. The binder will therefore be required as a part of the process thattakes a multi-module program from editing to execution. We intend to make no functional changesto the binder. In particular, since the binder does not read symbol tables (except in a unimportant,Alto-specific case), it doesn't have to be modified to use the shared symbol table cache.Approximate effort: 0.5 work-months.Phase II DevelopmentPhase II will actually provide two extensions to the Phase I system. These extensions areindependent and could be performed in either order.Replacing an Existing ModuleSmall changes to a module should not necessarily require recompilation and rebinding of allconfigurations in the dependency chain. In particular, if the compiler is able to honor the existingstructure of the module when recompiling it, the resulting new version can (almost) be slipped intothe system as a replacement for the old version without altering the current state. Specifically, thecompiler must retain the arrangement of variables in the global frame and the order of procedures fu/G br03 `vc ^5' ]&H [~1tr X/ O V+4 T Qt NAr K L6' JN IIH GD E7+ DQD Btr ?Zt < r^ :c0. 8_ 7D 5k1/ 3(4 2tr .t +}r> )R (-Q &M $/6 #5'2 !tr ju rV s3 $t rF -R ,7 '? 5 T N >]>Plan for an Interim Integrated Mesa Environment4in the module's entry vector. (Additional entries can be tolerated as long as they don't requireallocation of a larger global frame.) This ensures that links in other modules will not have to bechanged. Obviously, the compiler cannot always satisfy these constraints, but when the module hasbeen changed only slightly, the compiler has a good chance of doing so. Approximate effort: 2work-months.There are one complication in the loader, however. At the time that the (new version of the)module is loaded, the loader must locate all extant local frames that point to the global framebeing replaced. The saved program counters in these frames are now nonsense, since the code hasbeen recompiled. Therefore, these frames cannot be allowed to execute. Two options are available:(1) cut back the stack to the point of such a frame (i.e., simulate a RETURN from that frame), or(2) mark the frame so that a trap occurs when control returns to it. Both options are of equaldifficulty. Approximate effort: 1 work-month. Understanding Module DependenciesSDD has, in the past, worked on a system called DeSoto, whose purpose is to automate the processof maintaining a consistently compiled and bound set of modules. DeSoto actually consists of threeseparable parts: (1) a dependency analyzer, (2) a symbol table patcher, and (3) a file systemmaintainer. The dependency analyzer is a straightforward program that follows the graph ofmodule inclusions to determine what modules might (logically) require recompilation as a result of achange. The symbol table patcher has a detailed knowledge of symbol table structure and candetermine whether a particular change actually requires recompilation or whether it can beaccommodated by patching the symbol table (and associated .bcd). The file system maintainermakes sure that consistent source and object files are stored in designated places, and controls theother two parts of DeSoto.We propose to implement only the dependency analyzer as part of the Phase II system. (In fact,the Mesa group has a stand-alone version of this program, called the Include checker.) Thedependency analyzer by itself ensures that all modules that must be recompiled are in factrecompiled, though it will induce unnecessary recompilations. We consider the effort to implementthe symbol table patcher to be of marginal benefit for IME. Approximate effort: 1 work-month. fu/G br[ `vO ^^ ]&*tr [~ X/3* VZ TW S7c Q:' OW N? tr Jt! GrX E4/ DQL BK AE ?YI =P < @ :ad 8 5j<# 30+ 2@ 0rP .=tr +4><Inter-Office MemorandumToEPE working groupDateNovember 16, 1978FromP. DeutschLocationPalo AltoSubjectEPE consensus principlesOrganizationCSLXEROX Filed on: epe-consensus.memo on Maxc1At the request of the working group, here is a memo which sets down certain "consensus principles"which are implicit in the EPE Report, although not explicitly stated, and which were made moreexplicit in the presentations that Butler and I gave at Dealer on Nov. 1.Here are what both presentations mentioned as important strengths in Lisp (to be preserved inXLisp, and added to EPE Mesa):Automatic storage deallocationEasy use of programs as dataAtomsUniversal pointers / run-time type systemIntegrated editor / instant turnaroundThe remaining items on our lists did not coincide, although they all appear on the feature list in theEPE Report. My presentation mentioned Mesa strengths to be added to Lisp, but Butler's did notmention Mesa strengths to be preserved (presumably because EPE Mesa is meant to be upwardcompatible with present Mesa in a much more direct sense than XLisp is upward compatible withInterlisp).Here are some mechanisms we both viewed as appropriate for representing information aboutprograms:Tables mapping name to for framesAn atom table associating a print name (string) and internal IDTables for each pointer-containing type giving for each pointer fieldGlobally unique type identifiers"Spacing" tables mapping (fixed-size) ranges of virtual addresses to the type of objectsallocated in that range]gp c8q]r-q7Br ]q]r -q7Br Yq]r-q 7BrSsr M. G.4 FiY DI AP @3=963)0W& -+24 +;$ *!L (8% ' #9 "f:2?'/M >QXDInter-Office MemorandumToPE-InterestDateNovember 16, 1978FromLampson, LevinLocationCSL, Palo AltoSubjectMesa-based EPE planFile[Ivy]EpeMesaPlan.memoXEROX The plan for a Mesa-based EPE has three major stages:Preliminaries: an interim integrated Mesa environment (IME) which provides quick edit-compile-run turnaround for the existing Mesa language and system, as well as rudimentaryaccess to the Dorado's large virtual memory. This system serves as a base for laterdevelopments.Foundations: basic, low-level facilities needed to match the functionality of Lisp: atoms,variable syntax analysis, dynamic variable binding, a safe language subset, and automaticstorage deallocation.Features: equivalents for the Lisp Masterscope, file package, programmer's assistant, Helpsysand similar features, in a more general setting, together with improvements to the debuggerand editor, facilities for specifying the construction of complex systems, and other"environmental" capabilities.The stages must be done in approximately the indicated order, although some overlap is possible.An important property of the plan is that growth of the system is highly incremental: even within astage, there are many points at which a stable system with improved function is available.PreliminariesThis section describes the steps required to obtain an interim integrated Mesa programmingenvironment (IME). We establish the following ground rules:1)The intended user community for this environment is a small corps of experts who will useit to construct a more lasting integrated Mesa world. Consequently, the proposed system isnot idiot-proof and occasionally delivers its function in less-than-ideal ways.2)The primary purposes of this environment are to speed up the edit/compile/debug/editloop by removing the Alto Executive as the link between weakly-communicating programsand to exploit the large real and virtual memories of the Dorado.3)This system is only intended to work on the Dorado.We divide the development into two phases. Phase I will be concerned exclusively with theconstruction of the environment proper and a fast edit/compile/debug/edit loop. A change to amodule will require recompilation of that module and any other modules that depend upon it.Configurations whose constituent modules change will have to be rebound and reloaded, causingdata in their frames to be lost. Phase II will produce a system that relaxes these requirements incertain common situations, thereby eliminating unnecessary recompilations and loss of data in thesecases.]gp c8q]r -q4 r ]q]r -q4 r Yq]r-q4 q r qSsr M5K=t r2I9H3EF DVt r1BK AL>tr;=oC;J :e 79V 5K 4/O /p +r6$ *<&A%'[#O 0<LA3 B< 1- F JG ` M R  >\Mesa Response to Lisp Challenge2Approximate Effort to Construct Phase I System: 9.5 work-monthsApproximate Effort to Construct Phase II System: 4 work-monthsPhase I DevelopmentPhase I represents the bulk of the effort. When completed, it will have produced an environmentin which a text editor, the compiler, the binder, the debugger, and the user's program(s) are allsimultaneously available. The components of the Phase I system are listed below with estimates ofthe effort required to produce them.MicrocodeThe present Dorado Mesa microcode supports Mesa 4.1 and precisely emulates the Alto behavior.It is therefore extremely inconvenient to access more than 64K of primary memory. The microcodewill have to be extended to be functionally compatible with the present D0 implementation, whichrequires the addition of instructions that manipulate long pointers (24 bit addresses) and pagefaulting. Approximate effort: 1 work-month. (Note that this work will be done regardless of IMEplans.)SystemThe Alto/Mesa runtime environment will be carried over to the Dorado more-or-less intact. Theactual movement of code requires only recompilation (to take advantage of the microcode discussedabove). Functional changes are required to handle page faults and support (code) segmentallocation in the 24-bit address space. Nearly all of this work has already been done for XMesa(the version of Alto/Mesa that exploits the extended memory of a wide-bodied Alto). The onlyadditional substantive change is a virtual memory maintenance facility. We expect to implement asimple-minded scheme in which the virtual memory is mapped onto a contiguous region of the disk,thereby eliminating the need for paging tables. Approximate effort: 1 work-months.An rudimentary protection scheme is required to keep the various programs from clobbering eachother. We intend to give each major entity (compiler, debugger, editor, etc.) its own MDS (maindata space - a 64K region of the virtual address space that is implicitly addressed by short (16-bit)pointers). Code segments and symbol tables (see below under Compiler) will reside outside allMDSs and thus be accessible only via long pointers. Since any program can fabricate a longpointer and use it, we cannot prevent arbitrary access, but by using the write-protect facility of thehardware memory map, we can prevent arbitrary modification. When a particular MDS isexecuting, all other MDSs, all code segments, and all symbol tables will be write-protected.Switching control from one MDS to another requires changes to the map entries for all pages ineach MDS. Code segments and symbol tables remain write-protected except when the compiler anddebugger find it necessary to modify them (e.g., setting breakpoints, cache update). Approximateeffort: 2 work-months.Interactive BaseWe envision a window-oriented display manipulation facility as the basis for interaction with thevarious programs in the environment. The package presently used in the Mesa debugger suppliesadequate function, albeit in a somewhat awkward fashion. It is likely that this interface will bereplaced by the one used in the Tools Environment, possibly within the next few months. (Thisconversion would be done by the Mesa group and become part of the official, released debugger.)Approximate effort: 0 work-months (That is, we'll take what they give us.) frG bt0r `vt1r \Su Yr` W\R UC T $ Pt Mnr7& K&: JB HvZ F tr) E& At >r1- <F ;8> 9(8 7'6 6@=$ 4)7 21tr /4* - V ,QE *^ )T 'YS %#2 $ 5' "a!= 1- 8t ir t rL #L {9) 2, +O tr: 6 <>Y=Mesa Response to Lisp Challenge3An alternative package (called Chameleon) is being developed by AOS to support market probes.This interface will probably share many of the ideas of the Tools interface, but package themsomewhat differently. In particular, Chameleon expects to find a data base package (AOS calls itIliad) and understands a variety of scenarios for interacting with the data base. Chameleon willsupply a text editor as well (see below). Approximate effort: 0.5 work-months. (That is, we won'tadopt this package unless it appears stable and we can use it with only minor tweaks.)Text EditorThere are (at least) two sources for a text editor of adequate functionality (i.e., about what theLaurel editor provides). The Tools group have an editor that runs in the Tools environment.Obviously, if this environment becomes the interactive base of IME, we can adopt this editorvirtually intact. (Smokey believes we can alter the command set easily to provide globalsubstitution, etc., if we want.) The editor uses a quick-and-dirty form of piece tables (every piece isan integral number of lines), which means it is probably somewhat wasteful of disk space.Approximate effort: 1 work-month.Chameleon will also provide a text editor, whose functions will resemble those of the Laurel editor(but cleaned up a bit). Doug Brotz is slightly skeptical about unplugging the Chameleon editor andinserting our own, but agrees that there should be no problem "in principle". The Chameleoneditor will understand about data base records and manipulating fields of such records, a feature wemight want to play with, but don't really need. Approximate effort: 1 work-month.(The effort estimates above are intended to be upper bounds. Butler believes we can "hacktogether an editor in 2 work-months", so we probably shouldn't invest more than 1 work-month insome other package.)CompilerIn Mesa, every module has an associated symbol table. Both the compiler and the debuggermaintain a cache of the symbol tables they manipulate, though the limited memory space on theAlto tends to restrict the effective size of these caches. We propose to maintain this cache in thevirtual memory space and change the compiler and debugger to share a single cache, whose entriesare accessed by long pointers. Ed Satterthwaite believes this compiler change is nothing more thana recompilation with an altered definitions file. Once this separate cache exists, the compiler's"front-end" processing of the DIRECTORY statement (which maps symbol table names to Altofiles) has to be reworked in a straightforward manner. Approximate effort: 2 work-months.DebuggerIn IME, the debugger will be "in control". That is, the command language (such as it is) will beinterpreted in the debugger. Thus, the existing command processor will be extended to includecommands that trigger editing, compilation, binding, etc. This will require that the Alto/Mesadebugger's interface to the "debugee" (currently, Inload/Outload) be replaced by the MDS-switching mechanism described above. Data in the debugee will then be accessed by long pointersinstead of reading Swatee. The debugger will also be changed to use the common symbol tablecache. Approximate effort: 1.5 work-month.BinderThe Mesa binder combines configurations (of which the compiler output is a degenerate case) toform new configurations. In the Phase I system, when a configuration changes, all configurations inwhich it appears must be rebuilt. The binder will therefore be required as a part of the process thattakes a multi-module program from editing to execution. We intend to make no functional changes frG b<! `v4) ^a ]&F [~+tr! YV Vt S8r U QO O O N@&3 LH JM IHtr E03 DQc B5' AH ?Y1tr < O :b+4 8 5kt 2r K 0t6' .N -$H +|D )7+ (,D &tr #5t r^ >0. _ D F1/ (4 tr t Xr> R Q `ML >]OMesa Response to Lisp Challenge4to the binder. In particular, since the binder does not read symbol tables (except in a unimportant,Alto-specific case), it doesn't have to be modified to use the shared symbol table cache.Approximate effort: 0.5 work-months.Phase II DevelopmentPhase II will actually provide two extensions to the Phase I system. These extensions areindependent and could be performed in either order.Replacing an Existing ModuleSmall changes to a module should not necessarily require recompilation and rebinding of allconfigurations in the dependency chain. In particular, if the compiler is able to honor the existingstructure of the module when recompiling it, the resulting new version can (almost) be slipped intothe system as a replacement for the old version without altering the current state. Specifically, thecompiler must retain the arrangement of variables in the global frame and the order of proceduresin the module's entry vector. (Additional entries can be tolerated as long as they don't requireallocation of a larger global frame.) This ensures that links in other modules will not have to bechanged. Obviously, the compiler cannot always satisfy these constraints, but when the module hasbeen changed only slightly, the compiler has a good chance of doing so. Approximate effort: 2work-months.There are one complication in the loader, however. At the time that the (new version of the)module is loaded, the loader must locate all extant local frames that point to the global framebeing replaced. The saved program counters in these frames are now nonsense, since the code hasbeen recompiled. Therefore, these frames cannot be allowed to execute. Two options are available:(1) cut back the stack to the point of such a frame (i.e., simulate a RETURN from that frame), or(2) mark the frame so that a trap occurs when control returns to it. Both options are of equaldifficulty. Approximate effort: 1 work-month. Understanding Module DependenciesSDD has, in the past, worked on a system called DeSoto, whose purpose is to automate the processof maintaining a consistently compiled and bound set of modules. DeSoto actually consists of threeseparable parts: (1) a dependency analyzer, (2) a symbol table patcher, and (3) a file systemmaintainer. The dependency analyzer is a straightforward program that follows the graph ofmodule inclusions to determine what modules might (logically) require recompilation as a result of achange. The symbol table patcher has a detailed knowledge of symbol table structure and candetermine whether a particular change actually requires recompilation or whether it can beaccommodated by patching the symbol table (and associated .bcd). The file system maintainermakes sure that consistent source and object files are stored in designated places, and controls theother two parts of DeSoto.We propose to implement only the dependency analyzer as part of the Phase II system. (In fact,the Mesa group has a stand-alone version of this program, called the Include checker.) Thedependency analyzer by itself ensures that all modules that must be recompiled are in factrecompiled, though it will induce unnecessary recompilations. We consider the effort to implementthe symbol table patcher to be of marginal benefit for IME. Approximate effort: 1 work-month. frG b/6 `v'2 ^tr Zu W\rV U3 Ret OrF MnR K,7 J'? Hv T F[ E&O C~^ A*tr @. <3* ;7Z 9W 7c 6?:' 4W 2 tr /t! ,QrX *4/ )L 'YK %E $ I "aP @ d i <# r0+ @ "P z=tr  3>T0Mesa Response to Lisp Challenge5FoundationsWe culled five major (read "potentially difficult to implement") facilities from the memos byBobrow and Masinter, and discussions among the EPE group:1)Programs as data2)Variable syntax analysis3)Dynamic variable binding4)Safe language (subset)5)Automatic storage allocationThese seem to be the major basic language/system capabilities which must be added to Mesa tomake a Lisp-like programming style possible. Doubtless there are also a number of minor pointswhich will need to be improved, but we believe that these are in the moise for the current level ofplanning detail.Approximate total effort for Foundations stage: 20 work-months, including 4 work-months forcleanup of the current Mesa compiler. These estimates result from consultation with EdSatterthwaite for compiler-related things, and with Peter Deutsch for things copied fromAlto/Dorado Lisp.1)Programs as data.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 LISPsense) uniformly throughout the environment, and (c) a universal pointer mechanism.S-expression representation. This seems straightforward in principle, though we haven't looked atthe details. We think that a representation other than parse trees should be explicitly defined,permitting the representation of parse trees to change as the compiler/language evolve.Approximate effort: 1 work-month.Atoms. The symbol tables built by the Mesa compiler currently include a mapping between sourceidentifiers and internal unique ids (atoms). At present, these mappings exist only on a per-compilation unit basis, implying that they will need to be merged into a global map when thecompilation unit "enters the environment". A similar merge presently occurs inside the compilerwhen the source program accesses an included module (i.e., the symbol table for that module isopened and the identifiers (used by the source program) are remapped into the current atom table).A merge into a global atom table therefore seems feasible, at least in principle. Approximate effort: 1 work-month.Universal Pointers. We will need pointers that carry the type of their referent with them. This inturn requires a scheme for universal type IDs, which do not currently exist in Mesa. It seemspossible to extend the techniques used to ensure uniqueness of record types to accommodategeneral types. Run-time efficiency is vital, so the check that two type IDs are equivalent must befast. We anticipate using the LISP "spacing" technique, which places all data structures of the sametype within a well-defined region of the address space (e.g., each page allocated for such dynamicstructures can hold objects of precisely one type). This scheme avoids keeping any type ID bitswith the pointer, but makes it difficult to point inside a composite data structure with a universalpointer. Two possible remedies have been suggested: (1) an explicit type identifier immediatelypreceding the (sub)structure, or (2) an indirection mechanism in the data structure itself. In anyevent, access to statically allocated variables (i.e., those in local and global frames) via universalpointers will have to be prohibited, unless special steps are taken to prevent problems with garbagecollection. frG ap ^r O ]&9 Y` Xu` V` Uk` S` PH O5,3 M=& L+ Ht/r, GzA E0A1 Dp ADut >rP <] ;S 7tr@ 6]a 4W 1tr .tr@ ,-0 +vO )*6 (l> &H %bR "6tr  trP N N { U I qB O gS X ]c \ S+9  : >[GMesa Response to Lisp Challenge6It will be possible to discriminate universal pointers with the existing Mesa facilities fordiscriminating variant records. We also intend to add a facility for coercing a universal pointer to apointer of more specific type; the coercion must be acocmpanied by a run-time check. Theintended model is the Lisp IPLUS function, which coerces its arguments to integers. This coercion isapplied during assignment; since argument-passing in Mesa is treated exactly like assignment, thisseems to work out just fine.Approximate effort: 4 work-months.2)Variable syntax analysis.LISP provides three opportunities for the programmer to affect the parsing/interpretation of inputtext: (a) at scanning time, (b) at compile time, and (c) at function call time. (a) may beaccomplished by providing scanner escapes to user-written code, which will replace someappropriate substring of the current parsing context (i.e., the as-yet unclosed lists) with a piece ofprogram in S-expression form. It appears straightforward to provide a facility comparable in powerto LISP's readtables -- a more elegant mechanism might be desirable. (b) may be accomplished bymore-or-less conventional macro expansion along the lines of the Mesa mechanisms for in-lineprocedures. (c) is deemed undesirable and will not be provided.Approximate effort: 4 work-months (3 for (a), assuming the existing Lisp read-table design, and 1for (b)).3)Dynamic variable binding.Mesa, at present, can only support static binding of identifiers. To be able to bind a name to avariable in an enclosing dynamic context, we need to know what variables are to be found in eachframe. Instead of the LISP default, we propose that variables to which dynamic binding may occurbe declared as such at compile time. The compiler can then produce a table of entries of the formatom -> for each compilation unit. Such a table could reside in the code segment, with a bit in theassociated global frame(s) to indicate its existence. Dynamic binding would then occur much in thesame way the signal-to-catch phrase binding occurs (but more efficiently). It might be better to usesome other form of variable identifier than its atom; the existing machinery used to bind signalcodes should be suitable for binding such identifiers also.Approximate effort: 1 work-month.4) Safe languageBy a safe language we mean here one in which a pointer value of a given type POINTER TO T isguaranteed to point to a region of storage containing a value of type T. We will also consider arelaxation of this condition in which certain regions of the storage may not be safe in this sense; aslong as values stored in such unsafe regions do not themselves contain pointers to safe regions, thedamage which can be caused is confined to the unsafe regions.There are three ways in which a pointer variable p may acquire an improper value1)Lack of initialization - in this case the value of p is just the random bit pattern whichhappens to be in the storage occupied by p when it is instantiated.2)Incorrect computation - in general a pointer value can only be the value of some pointervariable (which could of course be a record component) or the result returned by a storageallocation. If pointer values can be computed in other ways, e.g. with LOOPHOLEs or theirequivalents, or by arithmetic, then there is no guarantee that such values point to storagecontaining values of the proper type. frG b;! `d _"7 ]vr) \ D Z WYtr T-ut Qr\ O|U M&9' Lr$B JE IhE G9# F^@ C2tr6 A >ut ;UrG 9tr" 8K/2 6;'4n 2Q 0c / e -Q ,; (tr %u "~rDq r a t.tr* L j= >1tr2/tr%)tr2a"69!WBqr  P  M% =]UMesa Response to Lisp Challenge73)Premature deallocation - in this case p is pointing at a region of storage which oncecontained a value of type T, but is now being used for some other purpose.If none of these bad things can happen, then induction tells us that the language is safe with respectto pointers. In addition, it is necessary to do bounds checking on array references, since otherwiseevery array index is as dangerous as a pointer. Finally, array descriptors require the same treatmentas pointers.Preventing uninitialized pointers is straightforward, by generating code to initialize all pointers inprocedure frames when they are allocated, and in dynamic variables of record and array types whenthey are allocated. Mesa 5 will have language constructs for allocating dynamic variables, so it isknown where to do the initialization.Preventing incorrect computation requires excluding all the dangerous constructs from the languagea)Loopholes into a pointer type or a pointer-containing type (PC for short)b)Computed or overlaid variants in which the variant part is PCc)Pointer arithmeticd)Use of UNSPECIFIED (this restriction is probably stronger than necessary)e)What is missing?Preventing premature deallocation has two aspects: dynamic (explicitly allocated) variables andstack variables. For the latter, a simple and reasonable rule seems to be to disallow the use of @on local variables. As partial compensation, it seems desirable to introduce var parameters (call byreference); these can be thought of as pointers to stack variables which are always dereferenced, sothat it is not possible for the called procedure to make a copy of the pointer which will outlive thecall. We also need to enforce a restriction that var parameters are not permitted across process andcoroutine calls, since in those cases there is no guarantee that the caller will live longer than thecalled procedure (again, this seems too strong, but it isn't clear how to weaken it).For dynamic variables some support from an automatic deallocation mechanism seems essential,since otherwise there is no way to tell when the programmer says Free(p) whether other pointers top^ still exist. We see three possibilitiesa)Reference counting. This could be added to Mesa easily enough, but the cost duringexecution is rather high, and it is probably not a good idea in view of the other alternatives.b)Deferred freeing. The idea is to make a list of all the storage freed by the programmer,and at suitable intervals to invoke the scanning phase of a garbage collector and check thatthere are no outstanding references to the storage queued to be freed. At the end of thescan any storage which has passed this check can be actually freed.c)Automatic deallocation, discussed below.Quite possibly deferred freeing will be worthwhile, since it is fairly easy to implement and hassubstantially lower running costs than fully automatic deallocation. With plenty of address spacethere should be no serious objection to a long interval between the programmer's call of Free andactual availability of the storage.Mesa currently has primitive and unsafe facilities for relative pointers, which there is a design tostrengthen and improve. Relative pointers have several appealing properties, one of which isparticularly relevant in this contexta)They allow an entire complex structure to be moved in storage, or between storage and afile, as long as all its contained pointers are relative to the structure. frG2b&tr.`J ]mV [I Zc9- X UC# T-01 RH Q#% M;'2KI2IG=2F2Dq r72B? ?3- =Z < 7ur :-tr 8F 7zur0 5F 4pU 1D*2 /1tr .:tr*2+4*]L2(H&9#$*/#vC2!( N m\  U c# 7 V E -%2).PJ  ?YTMesa Response to Lisp Challenge8b)They can save substantial amounts of space, especially as the address space grows andpointers become longer.c)Misuse of a relative pointer can only damage data in the region it refers to. If none of thestorage 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. gothrough fingers. The advantage is that the programmer can forgo the safety precautions forsuch relation pointers without risking the integrity of the entire system. Of course a boundscheck is still required (analogous to an array bounds check), but in many cases of interest itcan be provided by storing the pointers in n-bit fields and making the age of the region 2n;an especially nice value for n is 16.Approximate effort: 2 work-months.5) Automatic deallocationOur proposal is to have automatically deallocated (AD) types, and to use the Deutsch-Bobrowscheme for incremental garbage collection. This requires knowledge of the location and type ofevery pointer to an AD type, but the techniques are well-known and straightforward. Approximate effort: 3 work-months (for Lisp-style transaction garbage collection, including necessarycompiler changes).Featuresxxx frG2b=`2^A1,\8[7XYFX-^V^T+tr.UjwTrSXtr P,tr L,u IrD G{W ET BtrI AE <+p :r :_=-XEROXPALO ALTO RESEARCH CENTERComputer Science LaboratoryDecember 8, 1978ToPE-InterestFromDan SwinehartSubjectMesa-Based EPE Programmer's AssistantFiled as[Maxc and Ivy]Assistant.bravo, . . .Assistant.PressThis section attempts to characterize the "programmer's assistant" facilities of a Mesa-based EPE, andto estimate their cost. Here we consider the activities required to provide a more or less directreplacement for existing Interlisp functions.However, one must bear in mind that we have the opportunity to redesign the user's interface to thesystem, 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 nothave exotic interactive requirements. The right facilities for such an environment will look substantiallydifferent from previous ones, as environments like the Smalltalk browser, DLisp, and the Mesa Toolsare beginning to show us. These issues deserve a great deal of additional design work, once the projectis underway.PrerequisitesIt is assumed that the work described under Preliminaries and under Fundamentals has beencompleted. The text editor and debugger described in those sections, perhaps augmented by MesaTools, would certainly provide an adequate interface. The time estimates are presented in the samespirit of optimism that pervades the rest of this document.InterpreterBefore anything remotely resembling the Interlisp interactive flavor can be achieved, either the Mesadebugger's interpreter must be extended to encompass the entire language, or a compiler-basedstatement evaluator must be produced. In this latter, preferred, approach, the compiler would beextended to provide the equivalent of incremental compilation for single non-declarative statements inspecified contexts. An evaluator within the debugger would generate the appropriate linkages to get thestatements executed. Sufficient information would be saved to provide the History List features(below.) An appropriate default global context could be made available, if necessary, for the executionof statements corresponding to the Lisp "top level". Suggested implementation: enclose the statements in aprocedure body, compile and execute the procedure.Approximate effort: interpreter, 4-6 somewhat mythical work months; compiler extension, 2-4. Evaluator, top-levelenvironment, .5-1.0 work months. If all or part of this work is implicit in providing the "programs as S-expressions"fundamental capability, the estimates can be reduced accordingly.Break and AdviseOnly modest extensions to the current conditional breakpoint code, using the incremental compilerinvented just above, are necessary to obtain a break/advise facility the equal of Interlisp's -- morepowerful, in fact, when combined with the Mesa display-oriented methods for indicating points ofinterest. (In fairness, DLisp presumably restores the balance.) The standard breakpoint handler could take care%D`vp^q!?]&r$[s UIts R?ts O}ts% Lsts9 GB$ FJ D- AjE ?S >`a <%E ;V] 9_ 8L 5 r 1s,r s r s 0o@ .5qs# -e; *9r ' s14 %*3 $(8 "~O +< t4+ <+ j4t5 2 u tHs t ,utE @s r ss V ,9 iI t5s0 ?X82of providing the linkage to the system-produced procedures containing the advice.Approximate effort: 1-3 work months.History Lists and their UseThe top-level interpreter, a history list that records top-level user actions at the text level, along with anindication of the contexts in which they were executed, are sufficient to implement the Redo commandand the function-composition capabilities that it enables. But to provide Undo requires that internalinformation be used as well. Once automatically allocated lists, programs as S-expressions, atoms anddata with attached types, and the other fundamentals are available, implementation of both commandsshould be straightforward. Probably both would be done, as in Lisp, by retaining S-expressionrepresentations of the original statements and their reversing functions. The following points prevent aplacement in the easy category:In Mesa even simple programs consist of several independent global contexts. Virtually everyuser action will have to be interpreted with respect to a specific environment. History listentries will have to include the corresponding environmental information, and the commandswill have to know when the corresponding environments no longer exist, or will have toarrange, as Interlisp can, to retain the context frames as long as they are referenced (requiresgarbage collector to operate on frames.) Contexts running as concurrent processes could alsocause trouble if more than one of the processes becomes involved in user history activity. Thehistory provisions would want to be more fully integrated with the complex context structuresthan are the Interlisp models.Mesa programs, because Mesa is an assignment-based language, produce more temporary side-effects, on average, than Lisp programs. The information stored to provide undo capabilitiesmight be more extensive. Because of the large virtual memory, space problems will probablynot arise, but performance problems might. However, an implementation the equivalent of theTESTMODE(T) facility in Interlisp -- saving the old contents for every store into memory -- could cause both timeand space problems.Mesa, possessing a syntax, is susceptible to syntax abuse. Such could occur when trying toprovide the undoable versions of each language primitive that can produce a storagemodification (e.g., a /_ b ?) Some care will be required to integrate this basic capability intothe language. This is just an instance of the efforts that are needed anyway to eliminate thespecial role of primitive generic functions in Mesa. Languages like Alphard provide a modelfor how this might be done.(More generally, as mentioned elsewhere in this report, the maintenance of a syntax that isacceptable to both man and LALR machine will present problems throughout the system thatare not encountered in the pure Lisp implementation. It will be extremely difficult to producea set of interactive facilities in Mesa whose use is as natural and compelling as those in thecurrent Interlisp.)Approximate effort: 2-4 work months to implement the mechanism; development of primitives and system procedures withundoable versions as time goes on. EditorIf the editor chosen for the Preliminaries implements an undo/redo capability, integration with themore general version should be straightforward. Otherwise, these commands would have to be builtfrom scratch, at considerable cost (depending on the editor design.)Approximate effort: 1 work month or ? work months.In a display-based editor, the structure-specific stuff can be largely implemented as part of the selectionNfs bQ ^ut [r XsY W>rs U:rs T 9- R(r s+ Q1, O|Irs MJ'5IFAGIF< JDV C2(5A@@(K>;wC98$8m5%6+t5cAust3ut0s3'/-I -;%,#@*B)%[$hS"S !^? ut` o# Cr sr s9 T  D ut s>- n?\Y3mechanism. To the extent that the text files are in communion with the underlying parse tree or S-expression representations, it will be easy to produce the needed hierarchical selections.Approximate effort: 1 work month.DwimSome spelling correction and the repair of minor typographically induced syntax errors could beincorporated into the compiler. It would be useful, given room, in both interactive and standardversions of Mesa. The user interface to these tools are likely to be quite different in a system based oncompilation and display editing. No estimate.MasterScopeThe structures needed for the Fundamentals implementations are adequate for the development of aMasterscope-style database. An extension of the interface used for the other tools would provide useraccess. The compiler, binder, or an intermediate agent, would notice change and update the data base.Approximate Effort: the database facilities, no estimate; the interface, 2 work months.Nfs b=% `Z ]mut s ZAr Ws\ U?! T -< R!t s OZr L.sr s% Je I$H EutC E?"Yi TIMESROMAN  TIMESROMAN TIMESROMAN LOGO TIMESROMAN  TIMESROMAN  TIMESROMAN TIMESROMAN  TIMESROMAN TIMESROMAN LOGO TIMESROMAN  TIMESROMAN  HELVETICA TIMESROMAN TIMESROMAN  HELVETICA TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN TIMESROMAN LOGO TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN  HELVETICA TIMESROMAN LOGO TIMESROMAN  TIMESROMAN LOGO TIMESROMAN  TIMESROMAN  TIMESROMAN  TIMESROMAN TIMESROMAN  !%'8.;5A<7CBJLPS \bh r {]     k & / 9@ J S"Y<^f o y    j B!"!:;B""":+=i :#i<%:CZ!:#iN*!K:C%GiG:# *iCB%C:C%;:C%T=#:C5a7: Z%--HiH=G]G=G]G=G]G%E=\PEYiY: Z%-4i4iQ%0iB%,=#E+:;]*:;]):;]>i>R [o%=J#Z$)HJ%9Z&9DZ" iA] ]!i!~:C: #9. %:+i)  :; ]:; ] :;]:;] %: C%: C %: C%: C "!  p`K": C%: C%: C%: C%: C%: C" : C: : #:+iO :j/CIT foo.pressMortonP11-Dec-78 14:25:24 PST