Inter-Office MemorandumToDistributionDateDecember 13, 1978FromSecond EPE working groupLocationPalo Alto(names on next page)SubjectReport from second ProgrammingOrganizationCSLEnvironment Working GroupXEROX Filed on: Ivy pe2>pe2.press - the report propermemos.press - technical memos submitted to the working group (the appendix to the report)minutes.press - the minutes of the working group's meetingsDistribution:CSLSSL: LRG, A. HendersonSDD Palo Alto: Irby, Liddle, Lynch, Metcalfe, Satterthwaite, Dave Smith, Wallace, Weaver, White, WickASD Palo Alto: Brotz, Elkind, Spitzen, WegbreitNon-CSL recipients may distribute further copies as neededTable of Contents1. Summary2. Introduction, charter and history3. Technical issuesa. Global issuesb. Facilities to be providedc. Character of resulting system4. Organizational and resource issuesa. Effort and scheduleb. Participating peoplec. Project organization5. Foreign affairsa. Importationb. Exportationc. ImageAppendix - technical memos submitted to the working group]gp c8q]r -q7Br ^Bq]r-q7Br]\ Wq]r-q 7Br]VBSsr Pqj`O``N#Y`L; J `H`G`FJe`E /`B:#9{p 6Or 3#% /-+G(! %&#k! 7 [9 72[`Second EPE report (section 1)SummaryThe first CSL Programming Environment working group met intensively for a month last summer,and concluded that CSL should launch a project on the scale of the Dorado to develop aprogramming environment for the entire laboratory, starting from either Lisp or Mesa. A secondworking group has met weekly for nearly three months, exploring in more detail the probableconsequences of the alternative starting points. This report presents those consequences in what wehope is sufficient detail for CSL to choose a starting point, and begin the actual construction of anExperimental Programming Environment.Although the members of the working group are not in complete agreement about the choice of astarting point, there is almost no disagreement about technical issues or long-term goals. The factsand conclusions presented in this report are not in dispute; we have attempted to identify the (few)sources of unresolved disagreements.As later sections of this report will make clear, the choice between Lisp and Mesa cannot be madesolely on the basis of technical considerations. To within the uncertainty of estimation, both startingpoints present challenges of comparable difficulty, and would lead to systems of comparable utility,with comparable investments, over comparable time spans (two to three years). We are agreed thatit is necessary and feasible for an EPE based on either system to support comfortably theprogramming styles currently associated with Lisp and Mesa. Some differences would remain in thecharacter of the result; the value judgements placed on these differences generated most of the heatin our discussions. Social and political factors -- including the availability of people to fill key rolesin the project, and our relations with the rest of the corporation -- are secondary (but possiblydecisive) concerns.Technical issues: Our further investigation of both the Lisp and Mesa alternatives led to twoplausible development plans for producing a rudimentary environment on the Dorado (primarily foruse by the EPE developers) in about six months, a widely-usable environment in a year and a half,and one superior to either of our present environments in about three years. The final systemwould provide all the facilities that present Lisp and Mesa users value highly: from Lisp, toolssimilar to the existing array of tools in the current Interlisp, and the ability to support integratedsublanguages and to delay bindings; from Mesa, the provisions for modularization with explicitinterfaces, and the amenability to static checking. However, the system would probably retain someof the "flavor" of its starting point.Organizational issues: Although the efforts required are about the same, a somewhat larger numberof qualified people are available to work on a Mesa-based EPE. This report also discusses apossible structure for the project; after the language choice is made it should be possible to developan internal operating plan quickly.External affairs: The rest of Xerox has a fairly large and growing commitment to Mesa, and noneto Lisp. Remaining largely compatible with the rest of the corporation has both advantages anddisadvantages, but the advantages predominate. Either choice will reduce communication withimportant (but different) research communities in the outside world: Lisp favors the AI community,Mesa favors the programming language community.Your working group respectfully asks CSL as a whole to:endorse the immediate establishment of a large-scale EPE project;based on the information contained in this report, and such other informationas it considers relevant, choose the starting point for the project; andagree to relegate further pro-and-con language discussions to the status of"printing discussions" for at least a year. 2 fr ap ^r-/ ]&V [Ltr Z? X6. W$A U% RaQ PV OWH M$ JA I!R GH FR D= C 5, A[ @e >~I < 9tr#* 8HC 6P 5>E 3 S 24)= 0^ /*M -& *ytr > (\ 'of %# "trN !9/0 J /b / 8u7A;/H. + ~=ZQLg0pSecond EPE report (section 2)Charter and HistoryThe purpose of this report is to set forth the discussions and conclusions of the second CSLProgramming Environment working group. The most active members of this group (those whoattended meetings regularly and produced memos or other substantial input for the group'sdeliberations) were:Dan BobrowPeter DeutschJim HorningButler LampsonRoy LevinLarry MasinterGene McDanielJim MitchellEd Satterthwaite (SDD)Nori SuzukiDan SwinehartWarren TeitelmanMany other members of CSL also attended some or most of the meetings and/or provided writtenmaterial for the group.We began with the conclusions of the first working group, reproduced here from their report:We think that CSL can support only one major PE, and that it can be evolved from eitherLisp or Mesa; Smalltalk is farther from our goals, though certainly not out of sight. If anew PE is to be developed from Lisp or Mesa, then other work on the existing systemsmust be kept to a minimum during this development (unless we want half the lab's effort tobe devoted to PEs), and they must be phased out as the new environment becomes viable.There doesn't seem to be any reason to attempt a multi-language PE, since an environmentwith all our ABC features would support any existing style of programming, while a two-language system would require more work, reduce synergy, and create artificial barriers.Our problem, then, is to decide whether we want to pay the price for a new programmingenvironment:agreement on what the starting point should be;manpower to build the ABC features which are missing;willingness of users to suffer substantial inconvenience in changing over.We are clearly talking about a project on the scale of the Dorado, and we should give itjust as much careful thought as we did the Dorado project. Lab-wide discussion, andwritten feedback, seem like appropriate ways to carry out this process.Our discussions focused on a number of areas in which we felt clearer understanding was neededbefore we could make a proposal to the lab as a whole about what to do in the PE area:What are the key technical issues which arise from each of the possible starting points?What differences in the ultimate system would necessarily follow from each choice ofstarting point?How much effort would be required to reach various levels of result from each startingpoint? What people would be available to do the work?What other non-technical and external considerations should play a significant role in ourdecision about what to do? 3 gp cq `vp\ ^W ]l: [X W6 U T, RQ" O N LK I H DC CS @'D< J;v2)9E8lF665b?3:2XX0@/N ,/*5(FJ%:#8"G ,2 _"43!7-'V!56 4&  =\ULg0p Second EPE report (section 2)The group has been meeting once a week for approximately 3 months. We did not begin with afixed idea of how long it would take us to reach satisfactory answers to the questions above.However, we feel that we now have sufficiently good answers to consider this phase of EPE activityfinished: the next step is to make a final decision about the starting point, which will requirediscussion by the lab as a whole, and then get down to work on the EPE itself.IntroductionWhy does CSL need a new Experimental Programming Environment?CSL's impressive productivity over the last few years can largely be attributed to its continuinginvestment in tools for itself. Dorado is a good recent example. It provides new opportunities forresearch in many areas by removing hardware capability (speed, memory, address space) as themajor bottleneck. For the next few years, our ability to conduct computer system experiments willbe largely limited by our programming capabilities.CSL currently has two major programming environments, Interlisp on Maxc and Mesa/Bravo onthe Alto. Each of these has major limitations deriving from its history and hardware base that makeit less than ideal for at least some CSL applications. The arrival of Dorados provides anopportunity to remove many of these limitations and provide a single programming environment forthe entire laboratory.We have focussed our attention on the foreseeable needs within CSL in the next few years, withparticular attention to "experimental programming." We have taken experimental programming tomean the production of moderate-sized systems that are usable by moderate numbers of people inorder to test ideas about such systems; Bravo, Laurel, and KRL (the implementation part) weretaken as typical of such experiments, but we believe that it will be important to conduct futureexperiments more quickly and at lower cost.A programming environment is more than just a programming language. It is the entire systemthat is used by the programmer in the process of developing programs. As such, it will certainlycontain such tools as text editors, debuggers, prettyprinters, etc. The underlying design principle isthat the purpose of a programming environment is to facilitate programming:A good programming environment will reduce the cost of solving a problem by software.The cost will include the time of programmers and others in design, coding, testing,debugging, system integration, documentation, etc., as well as of any mechanical support(computer time, etc.). Since our human costs continue to be dominant, one of the mostconvincing arguments in favor of a particular programming environment feature is that itspeeds up some time-consuming task or reduces the need for that task (e.g., it might eitherspeed up debugging or reduce the amount of debugging needed). Software bottleneckremoval is the implicit justification for many features.A good programming environment will also improve the quality of solutions to problems.Measures of quality include the time and space efficiency of the programs, as well as theirusability, reliability, maintainability, and generality. Arguments relevant to this categorytend to be of the form "this feature reduces the severity of a known source of problems," or"this feature makes it easier to improve an important aspect of programs." Thus a featuremight be good because it reduces the frequency of crashes in programs or because it makesit convenient to optimize programs' performance.We don't know how to quantify quality, but we did think about how much more productivity wemight expect for sizable projects (e.g., Laurel, Bravo or the travel planner), as compared to thecurrent state of affairs in either Lisp or Mesa. We guess that a factor of four is possible, about halffrom relaxing current space and time constraints by moving to the Dorado, and half from a PEwhich has the high-priority features on which we have agreed. 4 fp bB `> _F ]*6 \ N Xq Ulr= R@p/2 P'= O6> MQ L,3 IY G{.6 EH Dq#rp B ?W >;<" <I ;1:# 99' 8'+ 4 O 3v;& 1D# 0lK-@/rp"+ G*6-+(Q',U%D$"4"8q5rp 9"gTY]P SS0 '> 9( S W = >[>dLg0pSecond EPE report (section 2)How will all this productivity be applied? We anticipate three major effects.First, many more interesting things will be within the scope of a single person's efforts.Hence, the number of Laurel-sized projects can be expected to increase dramatically; notonly are they much less work to do, but it is much easier to organize a one-person that afour-person project.Second, much more elaborate things will be feasible, and hence will be attempted.Third, the evolution of good packages that can be easily used without disastrous time, spaceor naming conflicts will cause a qualitative change in the nature of system-building: thecurrent Interlisp system gives us our few hints of what this change will be like. 5 fp bN_H^A!7\9[7XQV8$UAS}Q S69KLg0pSecond PE report (section 3a)Global technical issuesConsensus principlesIn the course of our discussions, a few principles emerged which were not captured as "features" inthe original report, or were so fundamental that we thought they needed to be singled out for specialmention. These principles included:Automatic storage deallocation is an absolute necessity. It produces a qualitativeimprovement in the ease of programming and the reliability of the results. This need notpreclude another class of variables with programmer-managed allocation, but the latter mustnot be able to destroy the data structures necessary for the former.Easy use of programs as data underlies many other facilities in the system. Implementingthis seems to require having Lisp-style atoms, a run-time type system, and universal pointers(pointers that carry a type with them).Editing facilities closely coupled with the compiler and the executive interface to the systemare essential, both to reduce the turnaround time for minor changes, and to allow easyconstruction of tools that interact with these facilities.Capabilities for precisely defining interfaces, and restricting the communication betweenmodules to those interfaces, are essential to reliable and readable programming. Thisincludes, as a special case, the ability to restrict the use of types and names to a local lexicalcontext.The ability to perform static checking (including, but not necessarily limited to, typechecking) over designated program regions is necessary for both security and efficiencyreasons.The present Lisp, Mesa, and Smalltalk programming styles must all be supported in asatisfactory way. The same packages, and tools of equivalent power, must be available in allstyles. In particular, the Lisp capabilities for embedded variant languages and forprogramming entirely without type declarations must be supported.Both large, multi-person and small, single-person styles must be supported well. Bringing awider range of experiments within the scope of a single person's effort is an important EPEgoal.The EPE must support a wide range of binding times, including the Mesa and Smalltalkextremes, in a way that allows changes in binding time without structural changes in theprogram. Different choices of binding time by the programmer may lead to differentturnaround times for apparently minor changes, and to different execution efficiencies, butthe functional behavior of programs must not depend on such choices.SmalltalkFairly early in our discussion we decided that either Lisp or Mesa would be preferable to Smalltalkas a candidate for the EPE base system -- sufficiently preferable that we did not need to considerSmalltalk further. This decision was based on the following observations:The present Smalltalk implementation is written in Alto assembly language and intrinsicallycannot support more than 128K of real memory or 64K addressable objects. A majorredesign and reimplementation of the lowest level of the system would be required to makeit suitable as an EPE base. Neither Lisp nor Mesa has this problem.There is no evidence that large systems can be written in Smalltalk; the Smalltalk view ofthe world is enough different from that of either Lisp or Mesa that fundamental problems 6 gp cq `vr ]Jp:) [U Z@$W.SUJT O RDOY<M PLO'I#+3G HF:B#6Ah:?I>^;2 L9!68(4>sp3wY1T0mA-A=+J*7' ,(%&2$S"|? s p6 r pP A! Ji2)I_?D H ) L >Q]L9Lg0pSecond PE report (section 3a)may be revealed if we try to apply it to our larger projects. Large systems have beensuccessfully written in both Lisp and Mesa.Significant groups in CSL are familiar with either Lisp or Mesa; there is no CSL usercommunity familiar with the Smalltalk view of the world.The present direction of Smalltalk evolution is towards smaller machines (NoteTaker), whileEPE should take significant advantage of the Dorado's capabilities.However, there are a number of ideas in Smalltalk, not present in either Lisp or Mesa, which webelieve are important to provide in the EPE:The notion of class-structured behavior, and the ability of more specialized classes to inheritbehavior from more general classes.The user interface style.The lack of structural distinction between user- and system-defined objects.The working group spent essentially no time discussing these questions: it is up to the eventualproject participants to make sure they receive proper attention.(EP)E vs. E(PE)At the beginning of our discussions, we assumed that the facilities required for E(PE), i.e. work onprogramming environments per se, were a subset of those required for (EP)E, i.e. construction ofexperimental systems in general. Consequently, we did not discuss the E(PE) parsing separately.However, it should be noted that the plan for a Lisp-based environment was strongly influenced bya desire to facilitate further work in language and system construction, since in the Lispprogramming style, every medium- to large-scale project develops some language and systemextensions; such considerations were much weaker in the Mesa-based plan. Several members of theworking group with strong interests in programming languages and systems feel that neitherproposed plan is likely to lead to a system that supports their interests for at least a couple of years. 7 fpbQ`+]m<[8X?W7C T V R,OZAM#JG}L DQJ B@ ?r 24 bits)Priority B(B1)F3302Encapsulation/protection mechanisms (scopes, classes, import/exportrules) 8 gp cq `vp22 ^N[LZ@BW&4U-Rc:O74L &+J!GZUE BA$?>:M9i@6= 433"1 . , +x ) (n & #r !ep:   ) ]6 2  U2_44U )r p5  L >Q\)2Lg0pSecond PE report (section 3b)(B2)F1333Well-integrated access to large, robust data bases(B3)I3020Self-typing data (a la Lisp and Smalltalk), run-time type system(B4)A2203Consistent compilation(B5)I1323Version control(B6)F2000Source-language debugger(B7)A1121Text objects and images(B8)I1021Uniform screen management(B9)A3202User access to the machine's capability for packed data (see A6)(B10)F3111Run-time availability of all information derivable from sourceprogram (e.g. names, types, scopes)(B11)F2222CSL control over the system's futurePriority C(C1)A0102Direct addressing for files (segmenting)(C2)I0000Some support for interrupts(C3)I3021Compiler/interpreter available with low overhead at run time(C4)I0012Adequate reference documentation(C5)A1222Librarian, program-oriented filing system (incl. Browser)(C6)I3012Program-manipulable representation of programs(C7)I1011Dynamic measurement facilities(C8)A0222Scanned (bitmap) objects and images(C9)A0120Press files(C10)F0010?"Efficient" interface for experts(C11)A0222Line objects and images(C12)A1001Remote file storageThe two following subsections of this report cover all the topics identified as "major issues" in theabove list, as appropriate for the individual language. 9 fp b2 _0 ]n [ X Vf T Q2 O^&M# K$ HUr Ep( C AM< > <9 :E. 7 5# 3= 0! . ,5 ) E '7 '=>Q@7Lg0pSecond EPE report (section 3b, Lisp)Mesa facilities needed in LispThe following facilities from the ABC list are present in Mesa but not adequately available in Lisp:(A2) Statically checked type system(A4) Abstraction mechanisms, explicit notion of "interface"(A6) Adequate run-time efficiency(B1) Encapsulation/protection mechanisms(B4) Consistent compilation(B9) (in some contexts) User ability to pack dataIn the Lisp tradition, we propose to add these facilities by defining new objects to represent types,name scopes, etc. and associated functions for manipulating them. These objects are accessible tothe programmer at run time; however, greater efficiency can be obtained by compiling programswith respect to a particular state of these objects, and paying the price of recompilation (or, moretypically, reversion to interpreted or less fully compiled status) if a change is made. A similarcomment applies to static checking -- a change in a type or scope requires re-checking the affectedparts of the program.The remainder of this section describes the principal features of a Lisp dialect we have been callingXLisp, which we propose as the EPE base. XLisp includes the current Interlisp facilities as aspecial case, but it is based primarily on SCHEME, a lexically-scoped Lisp dialect developed atMIT, with additions motivated by the Mesa type and scope system. We intend XLisp not only as aresponse to the EPE challenge, but as a conceptual framework for thinking about scope and typeissues which has some room for future exploration of capabilities not present in either Lisp or Mesa.To summarize how we propose to provide each of the six facilities listed above:Static type checking -- by making types be objects, and (as needed) checking that all usersof a declared variable refer to identical (EQ) type objects.Explicit interfaces -- by defining an object called a dictionary that generalizes the notions ofparameter list, record, and interface, and by requiring that such an object be associated withevery defined or imported function.Greater run-time efficiency, packed data -- by making the internal representation of aquantity be one of its attributes in the type system, and extending the instruction set toallow more efficient execution when more tightly bound representations are used.Encapsulation/protection -- by associating protection information with entries indictionaries.Consistent compilation -- by extending the notion of type identity and compatibility intothe permanent filing system, through an object called a permanent pointer which somewhatresembles Mesa's time stamps.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 ("function" or "variable") and specifies the interpretation of a set ofnames in that context. Each entry in a name table consists of a name (atom) and an associatedproperty list. Dictionaries implement function argument and result lists, record types, andinterfaces: the latter uses are discussed more fully under Types below.Dictionaries are the building blocks for scopes. Conceptually, a scope is an area of a programwithin which the interpretation of names does not change; implementationally, it is an object whichspecifies how to determine the meanings of names. (We will freely confuse the concept and 10 gp$ cq `vpF]J#[;Z@!X(W6U1 R^ QH O{ O MZ LqZ JJ Ig F;P D)5 C1'8 AD @'<" >U ;vO8JG6<3@2K0#-c+++D*YP'-pq6% "|1( $4r Fr p  %7 E0J>67 *9 @ X G U/%W )U. S K@ ~ =]*WLg0pSecond EPE report (section 3b, Lisp)implementation in the discussion that follows.) A scope is made up of components, each of whichgives the meaning of some names, and a rule for deciding how to resolve conflicts and what to dowith undefined names. Each component may be a scope itself, or it may be a dictionary, whichactually associates names and meanings.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. In principle, every dynamicname eventually reduces through macro-expansion 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. These elementary operations areavailable as functions in the system, since they are needed for the interpreter and compiler, buttheir use is deliberately rendered inconvenient since it can lead to violations of scope rules on whichnot only compiler optimizations but the correct working of programs may depend. For ordinaryuse, we provide, instead of these primitives, a set of higher-level constructs for use in name tables:these constructs lend themselves better to static analysis and permit enforceable protectionboundaries. These constructs are the following:(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.(SCRATCH value) -- the value is present in the name table, but is not read-only. One canthink 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 atom but an object local to the dictionary, so that the binder and the user of a fluidname 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. LOCAL names are also used for fields inrecords: in this case, location-in-frame defines the location of the field within the recordinstance.(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: aname, 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, so 11 fp$ b18a?-b `Q _<! ]' Zc= X XX$: WYM7W !>$;A:657 C5N4J 2{=0[/q-&-@,g);--'Q&1:#$!TAGJ-sp,$sp*@=U 18I {H (4 q KH *=]Lg0pSecond EPE report (section 3b, Lisp)cascading 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.TypesFrameworkTypes 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"X satisfies type T" are interchangeable -- I- and D-types are predicates.I-types are built up from elementary types like INTEGER and ATOM by (possibly recursive)applications of the following operators (the syntax is for expository purposes only):SATISFIES[p:FUNCTION[[t:Type],[Boolean]]] is a type for objects x of type t such thatp[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".FUNCTION[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.)Structuring -- read on.The other kind of definable I-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. 12 fp$b1$`*._ [r Xs Up%55\ 8Gk=\ $;%& U9uS  K }>]yLg0p Second EPE report (section 3b, Lisp)(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.DeclarationsA D-type declaration just establishes an invariant for a variable -- checked whenever the variable isstored into, can be assumed whenever the variable is used. D-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.)Conformity and coercionsType checking depends only on the I- and D-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 I-type and R-type levels. I-type coercions up or down thetype lattice are mostly either no-ops or type checks, and can be supplied automatically. Other I-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.ProtectionWe implement compile time checking by providing information in a dictionary that specifies theexternal accessibility on a name-by-name basis. The actual access rights are determined by afunction of the originator, the path used to arrive at the dictionary entry, and the information in theentry itself.Mesa 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). 13 fp$b%6 ^"B ]m* ZA9' XB U8, T S R$ OZR MW LPH J Z IF& Fs BpD! Aic ?A >_c < 9s 6p\ 4O 3x8 0L+4 .=% -B$? +K (r %ep// #[ "[`  N~ N)P(0$ Z k4$  =]kLg0pSecond EPE report (section 3b, Lisp)In Mesa, all of these are based on intra-module checking by the compiler, and inter-moduleenforcement based on (2). This, in turn, is accomplished by creating a unique name for an interfacewhen it is compiled, and copying that unique name into both the client and the implementor whenthey are compiled.In XLisp, the privacy information in dictionaries and scopes provides (1), since the only way toaccess a non-local variable is by going from a frame or other object to the dictionary that describesit, and the operations to access objects in general are implemented within dictionaries and check theprivacy information.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 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,and 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.MiscellaneousFilingXLisp programs contain inter-program references (to dictionaries, in particular) that must berepresentable on external files, so that a program knows it will have the same environment whenrun subsequently, rather than some environment made up of objects that happen to have the samestrings 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 that maps PIDs to textrepresentations of objects in the file. 14 fp$ bM `,8 _ U ] Zc S X] WY[ U RW Q#E OJ NH J&9 Ih] GL D:+ C2A A AV#A> @(d >U =9$ ;a :T 8)8 7 H 5A$ 4) 0O /OP - S ,EI *#A );.1 'Z $r !^s 2p3* ? ("<  w , /*[w1 3,(4 mJ c cJ ] Y1, ': =\}Lg0pSecond EPE report (section 3b, Lisp)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. 15 fp$ b&B `F _Z ]8 Zc^ X30 WY:& UK TOE R4 R=YLg0pSecond EPE report (section 3b, Mesa)Lisp facilities needed in MesaWe distinguish two kinds of facilities presently available in Lisp and absent from Mesa which areneeded in an EPE Mesa: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.We propose to provide a few of these facilities, which we lump under Preliminaries, by initiallyconstructing an interim integrated Mesa environment (IME) which provides quick edit-compile-runturnaround for the existing Mesa language and system, as well as rudimentary access to theDorado's large virtual memory. This system serves as a base for later developments.The following facilities from the ABC list are present in Lisp but not currently available in Mesa:(A1) Automatic storage deallocation(A5) Fast turnaround for minor program changes(B3) Run-time type system, self-typing data(B10) Run-time availability of all source program information(C3) Compiler/interpreter available with low overhead at run time(C6) Program-manipulable representation of programsTwo other Foundation facilities emerged from our discussions as being extremely important to theLisp way of doing business:Dynamic variable bindingProgrammable syntax analysis (for both programs and data)Of all these facilities, we will deal with (A5) under Preliminaries, and we think (C3) is covered byour proposals for (A5) and (B10); the rest are Foundations. We will deal with Features separately.PreliminariesThis section describes the steps required to obtain an interim integrated Mesa programmingenvironment (IME). The intended user community for this environment is a small corps of expertswho will use it to construct a more lasting integrated Mesa world.Phase IPhase 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 facilities provided in Phase I are:Microcode and system extensions to support a 24-bit address space and virtual memory,with some crude protection between major entities (compiler, debugger, editor, userprograms). Some of this work has already been done for Extended Memory Alto/Mesa.A window-based display interface for interaction with the debugger, editor, and other tools.Such an interface already exists in the Mesa debugger and in the Mesa Tools Environment,and one is planned for Chameleon, a package for market probes being developed by AOS. 16 gp$ cq `vp01 ^\r p'([O YW7rp;U PT- IR O|$!r p M"= Lr)1 JT G VD#C.A+@=>A<3 9A 8K539 0nH .?$ +wq ((p: &D $B s fpH F B6 9w@(\5# N P =[Lg0p Second EPE report (section 3b, Mesa)A packaged text editor of about the functionality of the Laurel editor. The Tools groupalready have such an editor. Chameleon will have a similar editor. Alternatively, itwouldn't be much work to write our own.Changes to the compiler and debugger to allow the symbol tables and program beingdebugged to reside in the address space for fast access.Additional commands in the debugger to allow it to assume the role of the Alto Executive.Phase IIPhase II will provide two extensions to the Phase I system:Replacing an existing module by a new version without losing execution state. Thisinvolves changing the compiler to remember the decisions it made the last time it compiledthe module, and is only possible if the structure of the module (global variables and entryprocedures) has not changed. The loader must detect and invalidate extant frames thatpoint into the global frame being replaced.A dependency analyzer that determines what modules might (logically) requirerecompilation as a result of a change. SDD already has a version of this program called theInclude checker.Foundations1)Programs as dataThe 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. We propose to define a representation other than parse trees, so thatthe representation of parse trees can change as the compiler/language evolve.Atoms. The Mesa compiler currently builds symbol tables that include a mapping between sourceidentifiers and internal unique IDs (atoms) for an individual module. The Lisp atom capabilityrequires a global map, into which the individual map would be merged when a compilation unit"enters the environment". This is very similar to the merge now done by the compiler for includedmodules. 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. We also intendto add a facility for coercing a universal pointer to a pointer of more specific type; the coercionmust be accompanied by a run-time check.2)Programmable syntax analysisLISP 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 an S-expression. It appears straightforward to provide a facility comparable in power to LISP'sreadtables -- a more elegant mechanism might be desirable. (b) may be accomplished by more-or-less conventional macro expansion along the lines of the Mesa mechanisms for in-line procedures. 17 fp$b4$`vS^'['*Y8V= Res Op;KF JIHw?F-)E'+Ajk7@07%> 9nq 6Bs 3pE 1K 0 S ,rp@ +[M (/rpJ &2- %%D #'; " rpQ j\ Z `( 4s p U 5' (W yV 4' oF ` >]g'Lg0p Second EPE report (section 3b, Mesa)(c) is deemed undesirable and will not be provided.Lisp allows free mixing of code and (structured) data, and parses both in essentially the same way;programs frequently read in both at run time. Consequently, the scanner and parser must bepackaged for run time use.3)Dynamic variable bindingMesa, at present, only supports 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. Dynamic binding would then occur much in the same 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.There are three ways in which a pointer variable may acquire an improper value: lack ofinitialization, incorrect computation (e.g. by pointer arithmetic), or premature deallocation of theobject pointed to. Array and string descriptors require the same treatment as pointers. In addition,it is necessary to do bounds checking on array references, since otherwise every array index is asdangerous as a pointer.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 and stackvariables. For the latter, we propose to eliminate the ability to obtain an explicit pointer to a localvariable, and as partial compensation introduce var parameters (call by reference). For dynamicvariables some support from an automatic deallocation mechanism seems essential. We see threepossibilities, discussed in the appendix: the one that comes closest to Lisp is fully automaticdeallocation based on an incremental garbage collector.Mesa currently has primitive and unsafe facilities for relative pointers, which there is a design tostrengthen and improve. Misuse of a relative pointer can only damage data in the region it refersto; if none of the storage in this region contains any external pointers, then no global damage canoccur. 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 for suchrelative pointers without risking the integrity of the entire system. Of course a bounds check is stillrequired (analogous to an array bounds check), but in many cases of interest it can be provided bystoring the pointers in n-bit fields and making the size of the region 2n. 18 fp$ b3 ^Y ]m@ [ Xs UpJ T rp' R/2 QV N LQ#= J3 Gs Dtp.t p BH ?O >>.6 <X ;4P 9 6c 4C 3y.6 1% .b2,pI2*=2'2%ht p72# )< _Y sp- U(6 1. K7 I K c S  +5 b S 6rp/ u 6p =^KLg0pSecond EPE report (section 3b, Mesa)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. FeaturesThis section attempts to characterize the "programmer's assistant" facilities of a Mesa-based EPE, interms of a more or less direct replacement for existing Interlisp functions. However, we must bear inmind that we have the opportunity to redesign the user's interface to the system, taking the highbandwidth display into account. The goal will be to provide a consistent, integrated default interfacefor program development and for control of user applications that do not have exotic interactiverequirements. The right facilities for such an environment will look substantially different fromprevious ones, as environments like the Smalltalk browser, DLisp, and the Mesa Tools are beginning toshow us. These issues deserve a great deal of additional design work once the project is underway.InterpreterWe advocate extending the compiler to provide the equivalent of incremental compilation for singlestatements in specified contexts. An evaluator within the debugger would generate the appropriatelinkages to get the statements executed. Sufficient information would be saved to provide the HistoryList features (below.) An appropriate default global context could be made available for the executionof statements corresponding to the Lisp "top level".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. Thestandard breakpoint handler could take care of providing the linkage to the system-producedprocedures containing the advice.History Lists and their UseA history list that records top-level user actions in external (text) form, along with an indication of thecontexts in which they were executed, are sufficient to implement the Redo command and thefunction-composition capabilities that it enables. To provide Undo, however, requires internalinformation as well. Once automatically allocated lists, programs as S-expressions, atoms and datawith 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.In Mesa even simple programs consist of several independent global contexts. Virtually every useraction will have to be interpreted with respect to a specific environment. History list entries will haveto include the corresponding environmental information, and the commands will have to know whenthe corresponding environments no longer exist, or will have to arrange, as Interlisp can, to retain thecontext frames as long as they are referenced (requires garbage collector to operate on frames.)Contexts running as concurrent processes could also cause trouble if more than one of the processesbecomes involved in user history activity. The history provisions would want to be more fullyintegrated with the complex context structures than are the Interlisp models.Implementating the equivalent of the TESTMODE(T) facility in Interlisp -- saving the old contents forevery store other than into local variables -- could cause both time and space problems, because Mesais much more an assignment-based language than Lisp.Given Mesa's complex syntax, it is not clear how best to provide undoable versions of each language 19 fp$ bs ^pD ]m_ [T Vq SpM Rf PX O\ MH L E JX HZ Er Bp?# A"C ?I ><* <4 9gr 6;pD 4J 31  H 1! .r +Tpb ))rp (J&rp rp &B" %@"r p/ #;# "6I  B W  Q {J I qA" M gM ;S rp` 14 &= @]LHLg0pSecond EPE report (section 3b, Mesa)primitive that can produce a storage modification (e.g., a /_ b ?). Languages like Alphard provide amodel for how this might be done, by regarding infix operators as abbreviations for functionapplication, but this also requires eliminating the special role of primitive generic functions in Mesa.More generally, the maintenance of a syntax that is acceptable to both people and LALR machineswill present problems throughout the system that are not encountered in the pure Lispimplementation.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, possibly at considerable cost (depending on the editor design.)In a display-based editor, structure-oriented operations can be largely implemented as part of theselection mechanism. To the extent that the text files are in communion with the underlying S-expression representation, it will be easy to produce the needed hierarchical selections.DwimSome spelling correction and the repair of minor typographically induced syntax errors could beincorporated into the compiler. The user interface to these tools are likely to be quite different in asystem based on compilation and display editing.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. 20 fp$ bK ` O _b ]F \ HGI Z WYr T-pr p0 RA Q#M MV LrM JY Gr Dp\ CY A0 >_r ;3pr p! 9G 8)Pt 7@0(Lg0pSecond EPE report (section 3c)Character of resultWe have agreed that very similar results could be obtained starting from either Lisp or Mesa. Wealso agree that the EPE must accommodate a range of styles including the present Lisp, Mesa, andSmalltalk styles, and our goal is to support these styles without prejudice. However, we expect thata variety of influences will cause both the intermediate and final results to differ depending on thestarting point, primarily in terms of the efficiency with which they support early versus late binding.The following two sections set forth what we think the "flavor" of a Lisp- or a Mesa-based EPEwould be -- the strengths (and weaknesses) that would result from starting with each of the twopossible base languages.Lisp-basedAside from the AI effort, a number of other projects in the lab (such as the original wirelister, theDorado timing analyzer, the PARCHIVE program) have been implemented in Lisp. Perhaps thesingle most important observation about the use of Lisp is that as users become more experienced,they start building tools within the system to help them. These tools may span many projects, orthey may be very specialized; they range from complete languages (KRL) to minor extensions(automatic checking for undefined functions when one leaves the editor). The AI group in particularhas made heavy use of this ability to extend the Lisp system: Lisp has been uniquely suited to theirapproach, which is to solve problems by first building a new language in which to express significantparts of the solution, and then building the solution (simultaneously extending the language). TheHumus effort within Mesa offers a contrasting example of an attempt to build an extension on asystem that did not support it well: Juniper, for example, probably could have benefitedsubstantially from some extensions of this kind.It is important that an EPE support the working style which builds tools and even languages as partof the problem-solving effort. Lisp supports this style well in part because it is:Incremental: Small changes require only a small amount of work (both mental effort andreal time). This is true for both ordinary Lisp programs and programs written in embeddedlanguages. (Current implementations, unfortunately, have relatively weak tools fordiscovering whether one's changes are consistent.)Open: The basic facilities of Lisp are open to change at a very low level: one can modifythe operation of the entire system from a user program. There is no distinction betweensystem and user code, variables, name spaces, etc. (This is also a weakness, in that it is notuncommon to find that parts of the system make assumptions about each other that casualmodifications violate.)Integrated: The user can slip relatively gracefully from procedures written in an embeddedlanguage back to procedures written in Lisp itself, and vice versa. Since the parser andinterpreter are packages, code (in a variety of languages) can be stored in data structures andexecuted when retrieved.Aware of user activities: Standard packages in Lisp keep track of new objects added to thesystem by the user on-line, and changed objects, and help the user keep track of hiscomplex environment. Because all transactions with system objects (such as editing, creatingnew variables, etc.) are handled through an active intermediary and a set of functionalinterfaces, it is easy to provide all the "hooks" for complex assistants like Masterscope. .Abstraction-based: The user is completely freed from concern with basic questions like therepresentation of integers and symbols, and management of storage. (Most Lispimplementations, including the present Interlisp, have a related weakness, in that theyprovide few mechanisms for attaining better efficiency even when the user knows fullgenerality is not needed.) 21 gp cq `vpA ^00 ]lA$ [\ Zb^ X@ WXW U Rr O{p+: MF LqL JN Ig@ G40 F]B" DY CSD AC @I$4 >0 ;[ :T6/'5bN 35D62X2/,5$-7!,"?*"5)%C$g&3"P!]1W4'!<CLQl454J b+) >YdLg0pSecond EPE report (section 3c)Mesa-basedThe "Mesa style" tends to place greater emphasis on structure than on unconstrained flexibility.Probably its two most important aspects for an EPE are its emphasis on static checkability and itsprovision for explicit interfaces. Both are important in speeding up the programming process andin improving the quality of the result; they become even more so if the units that programmersmanipulate are large (packages or subsystems), rather than small (statements or functions); theadvantages will be small for programs whose "characteristic times" (design, programming, checkout,existence, total execution) are all measured in minutes, large if they are measured in weeks ormonths. In an environment where programs are undergoing rapid change, however, mandatorychecking mechanisms tend to introduce unnecessary overhead by requiring complete internalconsistency at every step of the development process.Static checking: The present Mesa style encourages (and often requires) relatively early binding ofmany aspects of programs that in Lisp are typically bound during execution. Mesa alsoincorporates redundant information (e.g., declarations) that can be checked for consistency. Theseproperties make it possible to routinely check statically for program faults that in Lisp wouldnormally only be detected at run time. (A good example is Mesa's type-checking.) It is generallybetter to locate faults by static checking, becauseMany faults can be identified in a single run of the checker, rather than surfacing one at atime in debugging runs.There is experimental -- as well as anecdotal -- evidence for the proposition that programfaults located statically are diagnosed and removed more quickly than those locateddynamically.Passing the static test ensures that all faults in a given class have been removed; in general,no finite set of test cases gives such assurance with dynamic checking."Correctness" is a static property of the program text; it is hard to ensure that a programthat relies heavily on dynamic properties actually does what is intended.A Mesa-based EPE would make provision for binding at a variety of times, but delayed or dynamicbindings would occur at the programmer's request, rather than by default. Tools would also beavailable to exploit program redundancy to infer suitable declarations for programs written withoutthem, and otherwise make it easy to convert programs originally written in a delayed-binding styleto earlier bindings. (It should be noted that such tools have already been developed,experimentally, in a Lisp-like environment.)The belief that this style actually speeds programming (measured as problem solutions per unittime) is intimately tied to the observation that most programmers spend more time worrying aboutthe possibility of programming errors -- and coping with their consequences -- than they actuallyspend writing new code. This style does require more planning before a running program iscreated -- some would consider this a disadvantage. A definite weakness of this approach is that itwill be relatively difficult to add flexibility that was not anticipated in the program design, thusrestricting the range of experiments that can be performed easily.Explicit interfaces: Much of the effort in the design of Mesa went into the development of facilitiesfor a modular style of programming. Definition modules are program components used to specifyinterfaces between clients and implementors of abstractions -- permitting them to workindependently, and make changes independently, as long as they respect the interface. (Ideally,they would completely liberate each side from any knowledge of the internals of the other, butMesa has not quite attained this ideal.)It seems quite clear that one of the major thrusts of our future research must be building systemsout of standard components, and decoupling the implementors and users of such components; Mesaprovides our best effort so far in this abstraction-based direction. The need to specify interfaces inadvance may be cited as either a strength or weakness of the Mesa approach, depending oncircumstances and prejudices. The present need for vast recompilations whenever a fundamental 22 fp br ^pW ]m+7 [ T Zc? XK WYK U>! TO8! R%4 QE5 NspB L 6 KM IL HI F3D( QB@KM >',=A :sp79dG7 1*5I 3/_ 1(6 0%+sp* .G -,>- +, (j*4 &` %`%< # ## "Va <( LB  sp"0 // CD8 6*  #; ( [@" M Q9. )/ G@ >] Lg0pSecond EPE report (section 3c)interface is changed is a weakness that can certainly be reduced, and probably eliminated byincremental recompilation on demand.Other notes:A Mesa EPE would allow programming to be, in a very real sense, incremental, becausemuch more of the burden of propagating the consequences of any change to a programcould be assumed by the compiler and other EPE tools; conceptually small changes wouldnot generally require large amounts of reprogramming. One happy consequence of relatively early binding is that decisions made statically aregenerally much less expensive than those made (repeatedly) dynamically. This consequenceshould not be interpreted as the motivation for encouraging early binding in the EPE. Someof the present efficiency of Mesa would definitely be sacrificed in those situations wheregreater flexibility and later bindings are introduced. However, it should not be hard toretain an "efficient subset" (roughly SDD Mesa). 23 fp b'5 `$ ]ms [pTYBX $2V7T.WRIs Q$UpO LN@L0 LN=iLg0pSecond EPE report (section 4a, Lisp)Effort and schedule -- Lisp baseA Lisp-based EPE (here called XLisp) can evolve from our current systems in a series of steps, witha working (although not stable) system after each step. The steps listed below need not be done inexactly the order given, although we believe this order leads to the least total work. We also believelittle parallelism is possible between any two of the steps, although, as the assignments of peopleindicate, a lot of parallelism occurs within a single step.The names attached to steps other than the first should not be taken too literally -- the namedpeople have not been consulted. We have assumed the worst, namely, that almost no volunteersfrom outside the current Lisp community will participate in this work.The total of the figures below is: 87 work months, 27 1/2 elapsed months. This total does notinclude work on Masterscope, but we assume that this work will be done eventually by LarryMasinter, who is not currently available. At the end of this period, we have a system which includesall the present Lisp facilities plus the critical Mesa-like facilities discussed earlier in the Facilitiessection.The memo on which this section is based, which contains a fuller discussion of the sequencing andrationale for the various steps, appears in the appendix to this report.PreliminariesDorado InterlispThe first step is to get Alto Lisp running on the Dorado. This work began in early November andis well underway. For more details see a memo by Bobrow, [Ivy]dlisp-status.memo.After this step we have a usable Interlisp system running on the Dorado.Work months: 18Elapsed months: 6?People: Bobrow, Deutsch, Haugeland, Teitelman; Fikes, Goldstein, Kaplan, M. Kay; Laaser,Masinter, ThompsonMain effortShallow bindingChange the system to use shallow binding and have invisible indirection for variables.This step produces no externally visible changes in the system, except that GLOBALVARdeclarations are no longer necessary.Work months: 3Elapsed months: 1People: Bobrow (stack fns & interpreter), Deutsch (compiler & loader), Haugeland (microcode)Clean up macrosChange the way macros and special syntactic forms are handled, to eliminate "error-driveninterpretation". In particular, eliminate DWIM corrections that require altering or examining thestate of the interpreter. 24 gp$ cq `vpT ^<' ]lV [rp= Zb&rp W6_ U= T,F Q"< O{4& M*; Lq19 J GK F;H Cs ?r QYLg0p Second EPE report (section 4a, Lisp)We can arrange things so that after this step the system will still run existing Interlisp programs, butMACRO properties and NLAMBDAs will produce warning messages. On the other hand, packageslike the iteration and pattern match statements will fit into the system much more cleanly.Work months: 6Elapsed months: 1People: Bobrow (interpreter), Deutsch (compiler), Teitelman (DWIM/CLisp), any 3 Lispprogrammers (scan the system); defer work on MasterscopeDictionariesAdd dictionaries to the system, but not lexically-scoped closures. The hardest part of this step isprobably designing the proper interfaces to dictionaries-as-virtual-objects.After this step we have a system which supports localization of names. Individual packages can berewritten to take advantage of this at any time. Some lame-duck code must remain in the filepackage to be able to dump and load individual definitions in a global dictionary so that existingprograms will run.Work months: 15Elapsed months: 2 (design), 3 (implementation)People (design): Bobrow, Deutsch, Masinter, Horning/LampsonPeople (implementation): Bobrow (stack & interpreter), Deutsch (compiler), Fikes (recordpackage), Kaplan (dictionary objects), Teitelman (file package & miscellaneous); defer work onMasterscopeClosuresImplement closures. This includes lexically scoped FUNARGs, and arbitrary closures like Mesamodule instances. Careful design is needed here to produce reasonably efficient results.After this step the system will support instantiable packages and Smalltalk-style object-orientedprogramming. Old programs are not affected; however, some existing packages should be recast ininstantiable form, and there will be a period of confusion and trauma while this happens.Work months: 9Elapsed months: 1 (design), 2 (implementation)People (design): Bobrow, Deutsch, LevinPeople (implementation): Bobrow (stack functions), Deutsch (compiler), Haugeland(microcode), Teitelman (BREAK et al)Type calculusImplement the type calculus (types as objects, type checking), but entirely on a dynamic basis -- novariant representations, and no compile-time checking.The result of this step is to make the type system a first-class citizen, rather than an intermittentvisitor as in the Decl package. Programmers can start writing type declarations in the knowledgethat they will reap the benefits after the next step.Work months: 9Elapsed months: 1 1/2 (design), 2 (implementation) 25 fp$ bd `Y _R[r ZcWYI U8 R O|pa ML J/3 IFX G.4 F<CrA.>;;w(09V8m 5A 2pJ 0Y -dR +"> *ZY'.r %."':$  pR 36 I B 5 r  L2 >Q]Lg0p Second EPE report (section 4a, Lisp)People (design): Bobrow, Deutsch, Horning/Lampson, Morris, Scott?People (implementation): Bobrow (interpreter), Deutsch (compiler), Kaplan (type objects)Compile-time type checkingImplement compile-time type checking.This step gives us a system that has nearly all the functional capability of a "safe" Mesa, although itis considerably less efficient in its representation of some kinds of objects, e.g. bounded integers andset elements. It is not clear what to do about the Binder.Work months: 12Elapsed months: 3People: Deutsch, Levin, Satterthwaite (compiler), Kaplan (PUTD, APPLY*, etc.)Variant representationsImplement variant representations, such as unboxed numbers.This system should be competitive with Mesa, aside from the questions of LOOPHOLEs, pointerarithmetic, etc., and of course it has a lot of capabilities not in current Mesa.Work months: 6Elapsed months: 1 (design), 1 (implementation)People (design): Deutsch, SatterthwaitePeople (implementation): Bobrow (stack functions), Deutsch (compiler), Fikes (recordpackage), Haugeland (microcode)Further workInfix front endImplement an infix front end, i.e. an infix parser and prettyprinter.Work months: 3Elapsed months: 1People: Goldstein (prettyprinter), Swinehart (editor), Teitelman (integration)Permanent pointersImplement permanent pointers. Permanent pointers, as part of a programming system, require someresearch. Integrating them into the system will be an ongoing project.Work months: 6?Elapsed months: 2?People (design): Deutsch, Horning, SturgisPeople (implementation): Sturgis (primitives), Teitelman (file package) 26 fp$`rA]I Zc W7p% T U Rh Q;MrLPIFM F Bp; ?I >=Q;r 9.6'3x>T1 .s +r (opE%Cr # N  \p=# Gr&*G` >QZ?Lg0pSecond EPE report (section 4a, Mesa)Effort and schedule -- Mesa baseAs discussed under Facilities above, the plan for a Mesa-based EPE has three major stages:Preliminaries, Foundations, and Features. The stages must be done in approximately the indicatedorder, although some overlap is possible. An important property of the plan is that growth of thesystem is highly incremental: even within a stage, there are many points at which a stable systemwith improved function is available.This section of the report is a condensation of a memo submitted to the working group. For moredetail, see the full memo in the appendix to this report, and the earlier discussion under Facilities.Preliminaries (IME)Phase IPhase I represents the bulk of the IME effort. When completed, it will have produced anenvironment in which a text editor, the compiler, the binder, the debugger, and the user'sprogram(s) are all simultaneously available. The components of the Phase I system are listed belowwith estimates of the effort required to produce them.Approximate Effort to Construct Phase I System: 9.5 work-monthsMicrocodeExtend the microcode to handle long pointers and page faulting. Approximate effort: 1 work-month. (Note that this work will be done regardless of IME plans.)SystemChange the Alto/Mesa runtime environment to handle page faults and support (code) segmentallocation in the 24-bit address space. Nearly all of this work has already been done for theExtended Memory Alto version of Alto/Mesa. Approximate effort: 1 work-months.Provide rudimentary protection through separate MDSs for major entities. Approximate effort: 2work-months.Interactive BaseAcquire a window-oriented display manipulation package, from either the Mesa debugger or theTools Environment. Approximate effort: 0 work-months (That is, we'll take what they give us.)Alternatively, acquire the Chameleon package from AOS; this would supply a data base packageand 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 EditorOne possible source for an adequate text editor (i.e. about as good as the Laurel editor) is anexisting editor that runs in the Tools environment. Approximate effort: 1 work-month.Chameleon is an alternative source for a comparable editor. 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 in 27 gp$ cq `vpR ^E ]l7+ [S Zb$ W6,4 UZ R?q Mlr Jp.* HuA FI E%6 As0p >s ;8pAsp 9C 6As 2p7" 1JF /,sp ,S/sp * '\s $ p.. "esp: T n sp' V ws (p S 5sp 1;sp E :(7 ( =]; Lg0p Second EPE report (section 4a, Mesa)some other package.)CompilerMaintain a cache of symbol tables in the virtual memory space. Approximate effort: 2 work-months.DebuggerExtend the debugger command language to include editing, compilation, binding, etc. Also changethe debugger to use the common symbol table cache. Approximate effort: 1.5 work-months.BinderWe intend to make no functional changes to the binder. Approximate effort: 0.5 work-months.Phase IIPhase II will provide two extensions to the Phase I system. These extensions are independent andcould be performed in either order.Approximate Effort to Construct Phase II System: 4 work-monthsReplacing an Existing ModuleMake the compiler retain more information about the structure of a compiled module, so that aslightly changed module can often (almost) be slipped into the system as a replacement for the oldversion without altering the current state. Approximate effort: 2 work-months.Change the loader to find and alter extant frames affected by loading a new version of a module.Approximate effort: 1 work-month. Understanding Module DependenciesImplement the DeSoto dependency analyzer, which ensures that all modules that must berecompiled will actually be recompiled. Approximate effort: 1 work-month. 28 fp$ b ^s [p!sp Y Vs S:pE Q4sp NCs Jp$sp Fr Cp] A# >s1p ;ELg0pSecond EPE report (section 4a, Mesa)FoundationsAs discussed under Facilities above, there are five major basic language/system facilities which needto be added to existing Mesa. These facilities comprise the Foundations stage of the Mesa-basedEPE work.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 dataS-expression representation. Approximate effort: 1 work-month.Atoms. Approximate effort: 1 work-month.Universal Pointers. Approximate effort: 4 work-months.2) Variable syntax analysisImplement programmer-controlled parsing at input time, using the existing Lisp read-table design.Approximate effort: 3 work-months.Implement programmer-controlled extension at compile time, using macro expansion, based onMesa in-line procedures. Approximate effort: 1 work-month.3) Dynamic variable bindingMake the compiler produce a table of entries of the formatom -> for each compilation unit, and use this to implement Lisp-style dynamic variable binding.Approximate effort: 1 work-month.4) Safe languagePrevent uninitialized pointers and array descriptors. Do bounds checking on arrays. Excludedangerous constructs (e.g. LOOPHOLE) from the language. Replace @ on local variables by varparameters. Replace explicit freeing by deferred freeing or automatic deallocation. Make relativepointers safe. Approximate effort: 2 work-months.5) Automatic deallocationImplement the Deutsch-Bobrow scheme for incremental garbage collection. This requiresknowledge of the location and type of every pointer to an automatically deallocated type.Approximate effort: 3 work-months, including necessary compiler changes. 29 fp$ aq ^p32 ]&C [ Xus/p, V I Uk031% S Pr Mspsp Jbspsp G6spsp D r @pI ?Ysp <-; :sp 7|r 4Pp81 .G -Gsp *r &p? %j8!r #p W "`sp `r 4p*G+ G  *sp6L >SSLg0pSecond EPE report (section 4a, Mesa)FeaturesThis section attempts to estimate the cost of the "programmer's assistant" facilities of a Mesa-basedEPE. Here we consider the activities required to provide a more or less direct replacement for existingInterlisp functions. As discussed in the Facilities section above, we do not believe that this is the bestapproach to providing these facilities in the EPE.We assume that the work described under Preliminaries and Fundamentals has been completed. Thetext editor and debugger described in those sections, perhaps augmented by Mesa Tools, wouldcertainly provide an adequate interface. The time estimates are presented in the same spirit ofoptimism that pervades the rest of this document.InterpreterExtend the compiler to handle single non-declarative statements in specified contexts. An evaluatorwithin the debugger would generate the appropriate linkages to get the statements executed. Savesufficient information to provide the History List features (below). Approximate effort: compilerextension: 2-4 work months; evaluator, top-level environment: .5-1.0 work months. If all or part ofthis work is implicit in providing the "programs as S-expressions" fundamental capability, the estimatescan be reduced accordingly.Break and AdviseExtend the Mesa debugger's current conditional breakpoint code to obtain a break/advise facility atleast as good as Interlisp's. Approximate effort: 1-3 work months.History ListsImplement Undoing, as in Lisp, by retaining S-expression representations of the original statementsand their reversing functions. Integrate history facilities with Mesa's more complex environmentstructure. Add language syntax for undoable operations. Approximate effort: 2-4 work months toimplement the mechanism; development of primitives and system procedures with undoable versionsas 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 monthor ? work months.Implement structure-oriented operations in the editor. Approximate effort: 1 work month.DwimIncorporate some correction of minor spelling and typographically induced syntax errors into thecompiler. No estimate.MasterscopeExtend the interface used for the other tools to provide user access to a Masterscope-like data base.Put code in the compiler, binder, or an intermediate agent to notice changes and update the data base.Approximate effort: the data base facilities, no estimate; the interface, 2 work months. 30 fp$ aq ]p%@ [;- Y)B Xu2 UI(s ps p SG R?)rp' P1 Ms K6p?% IH H,Fsp FQsp E"P C @qs =Ep9* ;sp 8s 5hpH 3U 2^8sp 0M /T ,(s (ps p0 'wA %"$sp $m !A8sp s p1/ d s p 8s  pL '? spD @XO Lg0p Second EPE report (section 4b)Participating peopleAll the people listed at the beginning of the report are candidates for participation in the actual EPEeffort, and most of them have indicated a willingness to contribute in some way regardless ofwhether a Lisp or Mesa base is chosen. However, nearly all of these people have substantially moreexperience in one of the two languages than in the other. To achieve our goals, it is essential thatpeople with both kinds of experience participate in the project in a major way: we are veryconcerned that if a Mesa base is chosen, people with Lisp backgrounds might not feel highlymotivated to contribute their unique experiences and insights to the project, and conversely if Lisp ischosen.The following are individual responses to a message we sent out to everyone who had indicated aninterest in the programming environment area by putting themselves on an on-line distribution list.The absence of someone from the following list does not mean they are not interested in working onEPE.BirrellI would probably be interested in low-level work in EPE (i.e. the parts which might be considered asan operating system), and in at least keeping track of language design.BobrowIf it is a Mesa based EPE, I expect to put about a third of my time in on it. If it is a Lisp basedEPE I expect to put in about 2/3.DaveSmithI cannot participate in actual implementation design or coding. I guess that puts me in the class ofkibitzers. However I have several ideas on programming languages and programming environmentsthat I would like to share. (Most of these ideas came out of the LISP70 project that Enea, Teslerand I did at Stanford.) I am anxious for EPE to succeed because PARC is not currently at the state-of-the-art in programming environments. In the short term, some simple extensions would benefitus all (such as Lampson's and Levin's intermediate Mesa PE ideas). But in the longer term, I hopeEPE turns out to be a laboratory for basic research into programming languages and techniques. Ithink there's at least a 5-10 year project waiting there.DeutschI expect to spend about half my time on EPE through mid-1979. What happens after that dependsa lot on how well we are doing at genuinely incorporating the strengths of all three languages into asingle system. If things are going well, I expect EPE to continue as my largest single interest for atleast another year after that.GiffordI am interested in the tradeoffs between protection mechanisms and type systems for builing layeredsystems; I am especially interested in the design of a flexible protection scheme for the D*machines that would enable the construction and debugging of large systems. This interest alsoencompasses hardware/microcode support for a run time type system. I strongly favor Mesa overLisp as the EPE base.I plan to spend the first part of January reviewing the EPE material in detail. It may be possbile toview part of my work in the comming year as EPE related, or my work as part of the EPE project,or both; it depends on the intersection of my thesis interests with EPE needs. Guibas 31 gp cq `vp Y ^K ]l&= [` ZbV XC WX@' U R S Q" X OE N Jr Gp31 F;G Cr ?pF >^! ;2r 8pb 6D 411 3w] 1;% 0m7+ .8) -c9 *7r ' pB %` $)> "| Pr $pB! '6 Q F  c _+4 P r : g?Q[1Lg0pSecond EPE report (section 4b)Here is a very selfish reply. At this late hour it is perhaps best to paint matters as black or white,rather than gray.An (incomplete) list of epe areas that interest me is:arithmetic, text formatting, graphics, pattern matching, and searching.My motivation is twofold: to have a friendly environment in which to do my own research, and tomake sure certain fundamental facilities are provided at an acceptable level of quality.My time commitment would depend heavily on my research interests and the congeniality of epe tomy working style. For example, a very important attribute for me is consciseness of notation. Has itbeen a serious epe desideratum?With regard to base language choice, my deep-down feeling is that a lisp based environment wouldbe infinitely more appealing to me than a mesa based one. Then again, don't underestimate the power of persuasion...HorningI consider myself committed to EPE as my major technical effort for the next couple of years,independent of starting point. My background implies that my contribution to early phases of theproject will depend on the starting point: with Lisp, I would expect to contribute to requirementsdefinition; with Mesa, I could get involved in the system programming.LampsonI expect the EPE to be my major research interest for the next 18 months. There is some chancethat I will change my mind about this if Lisp is the base. I expect to be able to spend a lot of timeon design, but am less optimistic about begin able to do any substantial programming jobs.LevinI consider that, if EPE is Mesa-based, I will consider it my second-priority project (after thedistributed transport mechanism). That translates to about 30% of my time over the next year.After that, I can't say. I would expect my involvement with EPE to be greatest during the earlierphases, when fundamental structures are being built. I probably couldn't contribute much to a Lisp-based EPE.MasinterI plan (if I am hired by CSL) to devote full time to EPE starting July 1 working on those pieces ofsystem which are prerequisite to building Masterscope-like facilities for Mesa. I imagine that actuallygetting to actual Masterscope facilities will be in the rather distant future: working on either an S-expression representation (easier to analyze), data base facilities (shared data base server), access toremote files, etc. will take first priority.MorrisI might sign up to work on the design and implementation of a more powerful static checker for thelanguage. I guess about half-time would be my level of commitment.Satterthwaite 32 fp b%A ` ]m6 ZAG WX UX RdH Pd OZ L. R J: G}: DQr A%pL ?C >R <F 9jr 6>pI 4%A 34'3 0r ,p<# +W^ ) W (MT & #r ppH G fF K \, 0r pB C Sr  (  ?QXLg0p Second EPE report (section 4b)If Mesa is chosen as the base for CSL's EPE, the implications for SD will be carefully considered.We have no current position on the numerous policy questions that would be raised by directparticipation, but contributions to subprojects of mutual interest seem likely to the extent that SD'sgoals and schedules permit.My principal interests re the EPE issues are (a) designing a "strong" but much more flexible typesystem, (b) (for Mesa) designing a safe language subset and storage reclamation techniques, (c)implementation of (a) and (b).SuzukiDatabase:There are two issues concerning database in EPE. One is the database for interaction,namely masterscope level thing. I would like my database system to be considered for the use inEPE system along ASD and masterscope. I will demonstrate the system tomorrow so many of youmay have a chance to evaluate. The other is the access from the programmers. This may be sometype extension and packages. If the previous line is chosen I will spend quite a few time of minedevoting bringing up the user interface. If not I will be interested in the latter subject which Iwould be interested in spending some of my time.Basic microcode:I am willing to support Dorado Mesa and its extension. Birrel may want to do this inconnection with Pilot. In that case I am willing to help him.Subrange checking, verification, etc.Probably not much to do for a while.Compiler, etc.:I have quite a few experience in writing compilers. But there are so many people whocan do it, so unless there is some urgent need I may not particularly want to do it.SwinehartI'm willing to play a substantial role in what you've called the Tools segment of the EPE project. Icannot in all honesty call it my primary activity, however, since it seems extremely important tofurther the voice communications work. Percentages are probably misleading, but I'd expect todevote 30-50% of my time to it. Goals: unified (default) approach to user interface for programdevelopment, control of applications.TaftI expect to spend a majority of my time on the Laurel transport project during the next 6 to 9months, so I can commit only a fraction (say, 25%) until that is done, but perhaps more later (50 to75%).As for what I might do: if the EPE is Lisp-based, one obvious task would be to implement a Puppackage. If it is Mesa, I am less certain what to do, though one possibility is to extend the filesystem to access IFS or Juniper remotely. I am also prepared to contribute effort in whatever otherways seem appropriate, e.g., writing Dorado microcode. Since I am not familiar with the insides ofeither Lisp or Mesa, and I am only superficially familiar with Lisp as a whole, it is probably notappropriate for me to work on the basic kernel of EPE.TeitelmanI expect significant portions of my time will be involved in epe, regardless of which base they startfrom. If mesa, then would be in implementing various user level packages not in mesa, such asprogrammer assistant, file package, dwim type stuff, etc. If starting from lisp, I have a less clear 33 fp b02 `J _#C ] Zc<% XO WY T-r QpO|< MH LrE JR IhQ GE F^1 C2A#3 @(> <%;w$ 8K6E 5AT 2r .pe -dD +6' *Z&9 (% %r "}pB '= s G[ 6- =T +8 302 6 r VpL P L:+ " ?Q]-Lg0pSecond EPE report (section 4b)picture of what I would be doing, at least initially, since a lot of things have to be changed down inthe guts of lisp, but I would think I would be fairly involved simply because I am currentlycustodian of so much of the system, and can also make inputs about how various changes will affectthe style of lisp programming. 34 fp bO `M _B ]` ]H>Q -Lg0pSecond EPE report (section 4c)Project organizationThe working group did not spend any time on organizational questions. However, we identified twoareas in which people would be needed almost immediately, and noted the possible relevance of thecurrent work on Dorado Lisp. In addition, a 3-person coordinating committee for the EPE projecthas been appointed by CSL management (Bob Taylor). This committee (Deutsch, Horning,Lampson) has met briefly and produced some organizational ideas described below.Coordination with SDDIf a Mesa base is chosen, we will need someone to function as a continuing liaison with SDD. Thisperson will need to be familiar with the language and system work being done in both places, tobring both potential divergences and opportunities for sharing code to the attention of theappropriate people doing the work. We believe that our goals and SDD's are similar enough, atleast at the language level, that such a liaison could be very helpful.IME (Integrated Mesa Environment)As mentioned in the earlier section on Effort, we believe it is worthwhile to make a short-terminvestment in improving certain gross aspects of the current Mesa environment, if a Mesa base ischosen. We view this as an initial phase of the EPE (even though much of the code is likely to besuperseded later) and hence it should be coordinated with the rest of the project.Dorado LispThe current project to produce an Interlisp system for the Dorado is independent of EPE. However,if a Lisp base is chosen, the starting system will be Dorado Interlisp. In this case it will be to ouradvantage for people with EPE interests to become involved in the Dorado Lisp project soonerrather than later. We also expect that in this case the current CSL Lisp community will be theinitial core of the EPE design and implementation effort.Proposal for EPE project organizationWe (the coordinating committee) believe the project should be organized into three areas:language/system, tools, and packages. Naturally these areas overlap; one of our functions is tofacilitate communication among them.In the language/system area, we believe the work will demand a fairly small, closely knit group of 3-4 people to work on the compiler and run-time system. At least one person from the coordinatingcommittee should be a member of this group.In the tools area, we believe that more autonomy of individual projects is possible, although certaindecisions with system-wide consequences (such as display management, low-level hooks forprogrammer assistance, and data base interfaces) must be made at a global level.In the packages area, we would like benevolent anarchy to prevail, subject to some planning forthings we know will be widely used throughout the system (e.g. network communications) or requirespecial expertise (e.g. high-quality mathematical routines). Our idea is to set up a standardscommittee, which would develop and publish a set of criteria that would be applied to all packagessubmitted for inclusion in the official library. Packages would be read by the committee foragreement with these standards, and by one other person (not the implementor) for appropriatenessof design and implementation. Since this procedure would introduce a certain amount of inertia intothe system, we envision the existence of an unofficial library, with the understanding that a packageis only allowed to exist in this library for a limited amount of time (say six months), and that anyonewho uses the package during that time may have to rewrite some code if the package's interfaceschange as a result of the approval process. 35 gp cq `vp V ^F ]l5+ [B ZbP W6r T pW RL Q Q O{[ MG Jr! Gp.1 FS DR CR ?r QYCLg0pSecond EPE report (section 5)Foreign affairsThe choice of Lisp or Mesa as the starting point for an EPE project within CSL has implications forother projects within CSL, for other organizations, and for CSL's relations with those organizations.Although we are agreed that "foreign affairs" should be given less weight than CSL's own needs,they are a legitimate concern in making the decision, and may prove to be one of the balancetippers. The following discussion enumerates many of the areas of concern and indicates the probable effectof either decision. To a high degree, the effects are "formally symmetric," i.e., for every advantageof one choice, a corresponding advantage of the other choice can be found. However, CSL maywish to give higher weight to relations with the rest of Xerox than to its relations with the worldoutside Xerox. For intra-company relations, somewhat more advantages follow from the choice ofMesa. Separate sections discuss the effect of the decision on the importation and exportation of people,ideas, and code, and on CSL's "image."ImportationImportation of ideasFrom within CSLIssue: There is a lot known about programming environments within the lab, and people who arenot directly involved in the project are still potential sources of good ideas.If Lisp is chosen: The people currently working in and on the Lisp environment will likely bewithin the EPE project. Some effort will be needed to ensure that Mesons concerned withinterfaces, static checking, verification, and optimization provide enough input to ensure that theycan profitably build on the EPE as it becomes available.If Mesa is chosen: The Mesons mentioned above will likely be within the EPE project. Someeffort will be needed to ensure that the Lispers concerned with programmer assistance, programs asdata bases, and integrated sublanguages provide enough input to ensure that they can profitablybuild on the EPE as it becomes available.From within XeroxIssue: Other parts of Xerox, most notably SDD, are also concerned with developing programmingenvironments (although with somewhat different characteristics than EPE requires). We should beprepared to shamelessly steal good ideas.If Lisp is chosen: The relationship to SDD efforts will be somewhat more distant, the application oftheir ideas somewhat less obvious.If Mesa is chosen: Much of what SDD does will be directly relevant; there will be continualpressures to remain compatible, and to import code, rather than just ideas.From the world at largeIssue: We would like to track the state of the art in the world at large.If Lisp is chosen: Much of the "automatic programming" and "programmer's assistant" type ofwork is done in various Lisp dialects, and should be easily applicable. This group of researchers iscurrently being encouraged to focus their attention on the development of a programmingenvironment for ADA (formerly DoD/1); however, much of their research work is likely to 36 gp cq `pR _8;* ]N \.F Z WD V?&@ T+1 S5'< Q,3 P+ MF7+ K&%Fq C5r ?|s <p: ;O 8-sp6 6,, 5#d 38 0sp = /4V -T ,*) (qs %p: $C ") sp> " 3s pH K s pB +sp = S !3$ J  U>\+Lg0p Second EPE report (section 5)continue to be in Lisp.If Mesa is chosen: Much of the specification and verification work is directed towards Pascaldialects, and should be easily applicable. ADA, like Mesa, is based on Pascal, and work on ADAenvironments should be highly relevant.Importation of peopleIssue: We want people to move into the project easily, and are even more concerned that it be easyfor users to convert to the use of the EPE.From within CSLLisp and Mesa have roughly comparable numbers of "hard core" users, and the issues of migrationseem roughly symmetric.From within XeroxMesa will be much more widely known and used within the corporation.From the world at largeGeneric Lisp is more widely known than Mesa; Generic Pascal is more widely known and usedthan Interlisp. If there is a systematic difference, it probably lies primarily in the communities fromwhich we expect to recruit.Importation of codeFrom within CSLIssue: Existing service packages should be made compatible with, or absorbed into, EPE to thegreatest extent feasible. We want to avoid fragmentation of both user and maintenance effort. (Inaddition, importing people implies importing their research systems.)If Lisp is chosen: The Interlisp packages come over almost intact. Will Bravo and Laurel usersaccept them as substitutes, or will functional equivalents of those systems be needed?If Mesa is chosen: Provision of functional equivalents of the Interlisp packages will be a majorchore. Laurel comes over, but something would still need to be done about Bravo.From within XeroxIssue: We want to stand on the shoulders of SDD and ASD wherever possible, both in terms ofservice packages/systems, and program development aids. CSL will want to experiment withprototypes and systems built elsewhere, and would benefit from the ability to incorporate outsidepackages and subsystems into our experimental systems.If Lisp is chosen: Nothing comes over.If Mesa is chosen: The amount of actual code that we can import depends both on the degree towhich we force our EPE Mesa to remain equivalent to SDD Mesa, and the extent to which thesolutions they choose to provide match the problems we need solved. Transferability will probablyrequire that EPE Mesa be a strict superset of SDD Mesa. 37 fp b _9spF ][ \/' Xvr Usp[ T sp PSs Mnp%: K H0s EKpD As >pJ =(P ; 7r 41s 1Lp9 /9* .BE +]sp6 )V &sp= %nQ !s p,( K%4 ># A6 \sp wsp9 > m;' 7 =XiLg0p Second EPE report (section 5)From the world at largeIssue: It would be nice not to have to replicate large system-building projects from elsewhere.If Lisp is chosen: There is significant precedent for Interlisp system facilities being imported fromelsewhere. The amount of actual code that we can import in the future depends both on the degreeto which we force our EPE Lisp to remain equivalent to Interlisp, and the extent to which thesystems built elsewhere solve the problems we have. There is apparently relatively little history ofimporting application-level code in Lisp.If Mesa is chosen: No code comes in.ExportationExportation of ideasTo the rest of CSLIssue: We want to "talk their language," even before conversion to EPE is complete.Again, the Lisp and Mesa situations seem quite symmetric; special efforts at communication will beneeded in either case to avoid alienation.To the rest of XeroxIssue: We would like to be able to demonstrate feasibility of ideas, and let the development groupstake them over and produce the production systems.If Lisp is chosen: The credibility gap will be somewhat larger, particularly if adequate performanceof a demonstration system depends on the full power of the Dorado.If Mesa is chosen: We will be under continual pressure to export not just ideas, but code, and thento maintain that code for the whole Xerox world.To the world at largeIssue: As part of the commerce of ideas, we must give as well as take. (See also the discussionunder importation of ideas.)If Lisp is chosen: We communicate easily with the AI and theorem-proving communities.If Mesa is chosen: We communicate easily with the programming language, system implementation,and structured programming communities.Exportation of peopleTo the rest of CSLIssue: None of us sees EPE as his life work.However, regardless of starting point, we expect EPE to be the major programming tool within CSLfor some time to come; there should be no major problem moving from EPE to any other CSLprogramming project. 38 fp bs _9pA \Ts pR ZZ YJD W32 V@) S[sp%Nq Jr Gs D1pL ALb ?* <s 9)p= 72 4spB 3:B 0Usp= .0 +s (2pB & #sp- sp1 ^' r s p% ";sp" J  =Y9Lg0pSecond EPE report (section 5)To the rest of XeroxIssue: One of the best ways to transfer ideas is often to transfer the people who carry them. Wewould like to make (temporary) transfers easy and productive.If Lisp is chosen: In addition to the problem of moving to a less powerful programmingenvironment, there will be a definite (but, one hopes, temporary) linguistic gap of the same order ofmagnitude as the effort required within CSL to convert a Lisper to a Mesa-based EPE. This willsignificantly increase "swapping overhead."If Mesa is chosen: The transfer may be almost too easy; we need to ensure that we get peopleback!To the world at largeIssue: Do we really want to encourage this, except on a temporary basis?As with importing people, this largely depends on the communities with which we want to interactmost strongly.Exportation of codeTo the rest of XeroxIssue: Some systems that we build primarily for our own use may prove to be so good that wewant them used widely within the corporation (e.g., Bravo); in other cases we may need a largecommunity of users to enable our own research (e.g., message transport system).If Lisp is chosen: This won't happen, unless provision is made for "severable" systems (analogousto Mesa image files) and programs can be tuned to run with acceptable efficiency on D0's.If Mesa is chosen: This depends on degree of source-language compatibility for packages andsubsystems. It is probably simpler at the system (image file) level, as with Laurel.To the world at largeIf Lisp is chosen: It probably won't happen, except for a few research sites whose interests includeboth Lisp and high-capability personal computing.If Mesa is chosen: It definitely won't happen.Effect on ImageIn the rest of XeroxIf Lisp is chosen: Software development groups throughout the corporation are likely to perceivethis as a CSL "abandonment" of Mesa just as it is being adopted elsewhere. This may tend tolessen our credibility, and somewhat reduce the morale of Mesa proponents and users.If Mesa is chosen: CSL would probably be perceived as doing research of greater relevance to thecorporation. There would be a greater chance of development organizations converting toenvironments similar to EPE as its advantages are demonstrated (and as more capable hardwarebecomes cheaper). 39 fp bs _9pZ ]= Zsp. YJS WB V@+ S[sp = Q Ns K8pA HS&: F Cr ?\s