Xerox Common Lisp A Development Plan Date: 21-Jan-86 9:52pm Authors: Ron Fischer, Bill vanMelle, Steve Purcell, John Sybalsky, Larry Masinter, and Beau Sheil Introduction This document presents a plan to develop a version of Common Lisp for the Xerox 1100 series of machines (i.e., principally for the 1186, but also usable on the 1108, 1132 or any machine of that basic architecture). The key element of this plan is to implement Common Lisp as an integrated extension of the present Interlisp based software, by extending the Interlisp kernel software to provide support for Common Lisp, in addition to Interlisp, and then porting a significant fraction of some existing, available implementation of Common Lisp, such as Spice Lisp, onto this extended kernel. The resulting integrated system would provide a smooth, coherent transition path for both our present customers and Xerox's internal code assets, both within and outside of XAIS (e.g., in PARC/ISL). This document focuses on the basic engineering and development that is required. It does not cover issues such as documentation, training or support, which would be essentially the same for any such product. 1. Requirements This plan was required to satisfy the following five requirements. 1. The implementation must be complete enough to be released to beta test no later than August 1, 1986. The motivation for this is that the product must be in customers' hands by AAAI 1986, in order to deliver on our promises from IJCAI 1985. 2. The product must be as complete a coverage of the Common Lisp language as possible. In particular, it must be as complete an implementation of Common Lisp as any of our competitors. It must support easy importing of "vanilla" Common Lisp code, and must be missing none of the language's "major features" (in particular, lexical scoping, multiple values, packages, lambda lists and Common Lisp style errors and macros). The completeness benchmark for this product is considered to be Lucid Common Lisp as implemented for the Sun. 3. It must support unrestricted intermixing of Common Lisp code and data objects with those of the existing Interlisp-D system, so that facilities implemented in either language are accessible to code developed in the other. The motivation for this requirement is to allow the new Common Lisp system to make use of the vast range of facilities already available in Interlisp-D and also to facilitate the conversion to Common Lisp of new code developed both by Xerox and its customers. For example, it must be possible to implement a mouse button handler for the Interlisp-D window system within Common Lisp and have that function use other existing Interlisp-D functions and facilities freely. This requirement has major consequences. For example, it forecloses the kind of isolated, separate implementation that was used to bring Prolog into Interlisp, since Prolog has limited ability to access the Interlisp environment around it. It mandates that Interlisp and Common Lisp functions and data structures be merged (so that data can be passed easily from one world to the other) and strongly suggests that the stacks be common also. Luckily, many of these situations are simply cases of providing different ways of describing the same, common, runtime environment (the languages are, after all, dialects of each other). There are, of course, some situations where the two languages cannot be freely integrated, e.g., when they ascribe different meanings to the same things. However, wherever it is reasonable to provide access from one to the other, it is to be provided. 4. There is to be a program development environment for Common Lisp consisting of at least a simple compiler, program editor and debugger. This requirement forecloses the option of providing simply a non-1100 resident cross-compiler and ensures that it will be possible to develop Common Lisp code within the resulting system. However, it is not a requirement, and this proposal does not provide, that the product contain an integrated set of programming tools for Common Lisp of the complexity and range of Interlisp-D. Neither is there any requirement to merge the two languages' representations of programs (so that, for example, the Interlisp editor could be or would have to be, used on Common Lisp programs). Instead, this requirement can be satisfied (as this proposal chooses to) by providing a simple text based editing and filing representation of Common Lisp programs (similar to that currently provided by Lucid) and defers the issue of a unified programming environment for later study. 5. It is required that the performance of the eventual system, running in either Interlisp or Common Lisp mode, should be at least 80% of the current performance of Interlisp-D on the 1186, i.e. Common Lisp performance is not to be allowed to degrade arbitrarily far beneath our existing product. Demonstration of this is to be via the Gabriel benchmark suite. 6. The implementation is to facilitate as much as possible the adoption of Common Loops. This is not seen as a problem for any full Common Lisp implementation. These requirements forcibly restrict the range of acceptable implementations. However, we believe that they can all be achieved by the plan described below. 2. Product description This plan proposes an implementation of Common Lisp as an integrated extension of the present Interlisp based software. From the user's point of view, this would appear as a new release of "Xerox Lisp" that was nearly (perhaps totally) backward compatible for existing code, but that was extended in a variety of ways. One such extension would be the ability to use Common Lisp constructs in existing code when it is modified or extended. In many cases, we would encourage the Common Lisp constructs to be used in place of existing Interlisp equivalents and, over time, we would retire the latter. [There is a significant documentation task required to stage this gradual transition, which must be separately estimated.] By using Common Lisp forms in their ongoing development, users could easily start converting their code (including Xerox' in-house system and application code) into Common Lisp. Another extension would be the ability to write new Common Lisp code that could be freely intermingled with Interlisp code in existing applications. Thus, users would have the choice of writing new code and applications entirely within Common Lisp (so that it could be ported to other systems) while maintaining their existing application code (if any) and continuing to use the existing Interlisp base of system tools (all of which would be callable directly from Common Lisp code). Alternatively, the user would be able to read standard Common Lisp code that had been developed on other machines and compile and use it freely within the Xerox environment. Note that we expect that, for the immediate future, most users will be programming in extended supersets of Common Lisp (such as ZetaLisp or CommonInterlisp), so we do not expect such ports to be entirely automatic between any two systems. However, to the extent that code porting is possible in general, it would be possible here. In places where the two languages have the same constructs defined to have different behavior (e.g., EVAL and many others), we will use the package system of Common Lisp to allow the user to specify which behavior is required. In most cases, we expect code to be written primarily in one of the two dialects or in the growing common subset, in which case no dialect discrimination would be required. However, for the user maintaining a truly mixed-dialect application, this mechanism would provide a workable solution. Primary among these users would be the XAIS development staff itself, who will rely on this facility heavily. One area in which the two languages will not converge immediately is programming tools. Not only are the two languages "native styles" rather different, but some features of Common Lisp are awkward to treat in the style of Interlisp-D's residential tools. Thus, this product will not initially contain an integrated set of programming tools for Common Lisp of the complexity and range of those for Interlisp-D. In particular, the user will not be required to merge the two languages' representations of programs (so that, for example, the Interlisp editor would have to be used on Common Lisp programs). Instead, we will provide a simple text based editing and filing representation of Common Lisp programs (similar to that currently provided by Lucid). Thus, users operating with "pure" Common Lisp code can choose to edit and file it the way they are used to (reading it through a separate reader and maybe choosing to control it from a separate Exec, optimized for Common Lisp, as the existing one is for Interlisp). On the other hand, they could choose to program in the CommonInterlisp joint subset and use the Interlisp programming tools (as we expect most internal users to). This defers the issue of a uniform programming environment for both languages for later development as experience with using Common Lisp in the Interlisp tool set is accumulated, while still providing as full a set of Common Lisp programming tools as will be provided by most of our competitors. The resulting integrated system would provide two different faces to the user for the same (extended) set of basic facilities. Users could use it to program "purely" in either dialect, through different window based interfaces, or "together" in a merged CommonInterlisp dialect that takes advantage of most of the features of both. In either event, the code and data that results would be freely interchangeable between and among developing applications so that the system would provide a smooth, coherent transition path for both our present customers and Xerox's internal code assets, both within and outside of XAIS. 3. Plan 3.1 Strategy The first key element of this plan is to extend the existing Interlisp kernel software to provide support for the semantics of Common Lisp, in addition to those of Interlisp. At a basic level, Interlisp and Common Lisp program and data structures are to be merged, so that they can freely call and use each other as elements of running systems. This provides a target run time which can support programs written in either dialect or any hybrid. We would then port a significant fraction of some existing, available Common Lisp implementation, such as Spice Lisp, onto this extended kernel. This would provide both some of the language features required to accept Common Lisp programs which are missing from Interlisp (e.g., extended LAMBDA-list processing, lexical scoping) and a variety of utility code (e.g. rational arithmetic) which are dialect neutral but defined to be available to a Common Lisp program. It is important to recognize that, although the bulk of the work is the latter, the most difficult aspect of the job is the former (the kernel), both in time, expertise required, and the impact of the implementation's quality on the overall quality of the system. It should also be recognized that a high quality job on the kernel is a prerequisite of any implementation that satisfies the interoperability requirement in its present, strong form. The second key element is to expedite achieving complete coverage of the Common Lisp language as much as possible, and to optimize the performance and packaging secondarily, as time permits. Not only is this a direct reflection of the primary requirement, but it allows us to obtain early experience with a complete hybrid system so that we know where to direct our later efforts. It also provides a complete implementation early on. This will allow porting of both application code and the fringes of the Common Lisp language itself (e.g. format statements) to proceed as early as possible and in parallel with kernel performance engineering. Thus, we will patch together a workable kernel and key language constructs as quickly as possible and then iteratively reimplement the worst performance offenders until adequate overall performance is achieved. Thus, we hope to be in a position to give a fairly complete demonstration of Common Lisp (and thus recoup our marketing position) as early as mid-May, although a reasonably habitable system is unlikely to be available until much later in the summer. 3.2 Tactics Given that one has an existing Lisp system, Common Lisp can be thought of as a set of additional language features to be brought into that system. By thinking of laying one language atop the other, it can be seen that many of their features will overlap. Those features in the new dialect that do not overlap any of the existing ones are completely new additions. Overlapping features can be either identical or non-identical (similar but not the same). Identical overlap allows us to use an existing Interlisp feature to implement a Common Lisp feature. This requires only the effort of identifying the feature and (possibly) providing an alternate name or interface to it. Examples of this are all of the primitive list operations like CAR, CDR, CONS, etc. An identical feature may also have to be modified if its performance is critical in Common Lisp and was not in Interlisp-D. Non-identical features must either be newly implemented or the Interlisp feature may have to be extended to "cover" the Common Lisp behavior. The choice of which option to take depends primarily on the performance impact. An example of this would be the addition of package functionality to the Interlisp reader and printer. Modifying Interlisp both adds the value of a Common Lisp feature to Interlisp and provides the new feature at lower cost. We can identify two major aids in implementing both new and non-identical features of Common Lisp. First, is the availability of existing implementations of Common Lisp features written in Common Lisp subsets. These greatly simplify the porting of much of the language, given a Common Lisp supporting kernel, and we plan to use one of these to obtain much of the bulk of the language. The most easily available is the public domain Spice Lisp code from Carnegie-Mellon University. This has been the basis for most existing Common Lisp implementations (including Lucid's), has undergone four years of publicly available debugging and is an accepted standard within the Common Lisp community. In this proposal, we have planned on using the Spice Lisp sources to expedite our port, although other high quality sources would also be fine if they were cost effective to obtain. Second, many new features (e.g., the mapping and sequence functions) have already been implemented for the existing kernel within the Interlisp-D CML Lisp Library package. While the quality of these varies widely, they provide the needed early coverage and a good base from which to proceed. 3.3 Overview The analysis which follows divides the task into three categories: critical functionality or performance-oriented code required to form the kernel of the implementation, medium scale integration requiring simple changes to Interlisp or Common Lisp code, and the straightforward import of features from external Common Lisp sources. Development effort is phased in that order so that it can be spent optimally on time-critical parts of the system. Outside of direct software development time there lies testing and debugging, which is estimated later, using rough estimation techniques based on the size of the development effort. Finally, outside this proposal entirely, lies engineering testing, release and documentation, which should be estimated by the appropriate functional groups, but do not significantly interact with the choice of development strategy addressed here. 3.4 Critical features Packages This is not only a key feature of Common Lisp, but is an enabling feature of a non-interfering Common Lisp/Interlisp development, as it allows a division of Interlisp and Common Lisp name spaces. Functions of the same name in Interlisp-D and Xerox Common Lisp will be different and can be specified in either dialect by a prefix, e.g., INTERLISP:ERROR is distinguished from the Common Lisp function of the same name, LISP:ERROR. There are several parts to this item: 1. Implement the package functions INTERN et al. If we were willing to accept a maximum of 255 packages in the first implementation, we could keep the current representation of symbols essentially unchanged, merely inserting a byte field in a spare symbol location to serve as a symbol's package index. The code that maintains packages can be imported wholesale from Spice, except for the symbol hashing code itself. Some performance tuning will be needed. 2. Fix the Interlisp litatom (symbol) reader and printer. Reader needs to intern symbols in the current package and recognize explicit package prefixes. The Interlisp litatom printer needs to print a package prefix if the symbol is not in the current package. 3. Fix major incompatibilities. The most significant change is to the file package software, which needs to recognize the package environment in which to read or write a file. This need not be done immediately, but something should be in place relatively soon to help development. The INTERLISP package should be set up to inherit all compatible symbols of the Common Lisp package LISP. The Common Lisp package should not inherit from the INTERLISP package by default. Multiple values Common Lisp allows functions to return more than one value. The difficult aspect of this feature is that if a receiving function expects a single value, then the additional ones are invisibly discarded. Thus, any good design requires that the performance of ordinary single-valued functions not be affected. Because the Common Lisp language functions use multiple values themselves, overall system performance would be severely impacted if the performance of this feature were poor. A high performance design for this feature exists within CMU's Spice microcode. However, a slightly lower performance but simpler to implement version has been designed locally, which puts most of the work in lisp for multiple-value function return, though it is assisted by some simple microcode. Some compiler work will be needed. Performance tuning or a reimplementation of this feature at some point may be appropriate. This item, too, has integration issues. Changes will be needed to environmental tools which display or save the values (previously a single value) returned by function calls, such as the debugger's stack display mechanism, to show functions that expect to receive multiple values, and history lists. Specifically, extensions to BREAK, ADVISE and others will be needed. Lexical scoping and closures This is by far the most difficult language feature to implement. Common Lisp is by default lexically scoped. In practical terms, this means that variables, blocks and tags that are lexically apparent to some piece of code are accessible to it, even if the code and the variable are dynamically separated by virtue of, for example, the code being inside a FUNCTION construct passed to another function. Lexically scoped FUNCTIONs are sometimes called "lexical closures." We have a preliminary design that will require expansion in several areas. The completed design will have to cover three areas in this features: compilation, interpretation and runtime support. Compilation will need to specially treat variables, GOs and the creation of closures. The interpreter's support for lexical scoping, and its interface to low level support will have a basis in the existing Spice interpreter. Runtime support will include dispatching on FUNCALL of a closure object, RETURN-FROM call frames with closure pointers, etc. Interpreter The interpreter needs to handle Common Lisp style lambdas and special forms, and obey lexicality. Initially we will import the interpreter available in Spice Lisp, which implements lexical environments in a slow but safe manner. This interpreter will benefit from performance tuning at some point. Later, we will investigate compiler based solutions, such as having EVAL compile functions as they're defined, and in a manner that leaves program state accessible for debugging. Control constructs As a consequence of free intercalling, errors incurred under Interlisp and Common Lisp must respect each other's error catching mechanisms. Although Spice code exists, the control constructs are performance-critical and the higher level features must be built atop a set of performance oriented changes to the Interlisp error mechanism. These changes will allow improved versions of the Interlisp error functions to be constructed as well. A preliminary (but flawed) implementation of a low level error mechanism has been done by Henry Thompson. 3.5 Features requiring integration or small modifications These features allow the Spice sources to be used for part of their implementation, but some system-dependent care needs to be applied. File system interface and pathnames Interlisp has a rich set of file system and stream operations. The Common Lisp functions can largely be implemented with calls into the existing Interlisp code. However, the function OPEN has no direct analogue; hence, we should extend Interlisp's OPENSTREAM. The pathname functions themselves will be imported from the external Common Lisp sources. There are no difficult design decisions or hard issues in the implementation of this feature. Streams Common Lisp has several kinds of streams not found in Interlisp (synonym, broadcast, concatenated); they can largely be implemented in terms of Interlisp streams. Performance of any of these fancy streams is unlikely to be good. But the important kinds of ordinary character streams (display, file) are essentially unchanged from Interlisp streams. Integration issues will arise in the global Common Lisp streams such as *terminal-io*, but these are not especially difficult. We plan to build on Stan Lanning's preliminary implementation of Common Lisp streams, which currently contains about 60% of the Common Lisp extended stream functionality. Reader/Printer Common Lisp's reader and printer behave differently from Interlisp's, and in particular support a large set of reader macros. There are also performance issues involved in the existence of dynamically bound variables *read-base*, *package* and others that affect the semantics of the reader. We will import and adapt the reader and printer from external Common Lisp sources. 16 bit NS character codes will need to be integrated with the reader and printer at their lowest levels. A switch will be installed in the Interlisp reader and printer, which will cause them to use the Common Lisp reader or printer when given a Common Lisp style read table as an argument. At some point in future, the Common Lisp reader semantics will cause us to face an integration issue: in order to include the concept of "read-time" macros and evaluation a residential editing environment requires a mechanism for actually reading or installing a definition while preserving the syntactic form of the source for editing and presentation. Hash tables The necessary functionality mostly exists in Interlisp already, except that it requires a small modification to allow NIL as a value. The major unimplemented item is the function SXHASH, needed as a function in its own right and in order to implement EQUAL hash tables. An implementation from Spice code exists, and will be imported for the initial release. A good implementation of the SXHASH function would be quite machine-dependent (for speed), and thus some minor performance tuning at a later date is called for. Type system There is a nearly complete implementation of the Common Lisp type system in CML now. The final features of this system can be imported from other Common Lisp sources. SETF This is a large and complex system to implement in its entirety. An implementation of it with good performance, or one which produces good code, causes integration issues to arise. We will import and adapt the implementation in the external Common Lisp sources. 3.6 New features Many Common Lisp features are high level enough that they are independent of the rest of the system. These can be imported fairly easily from an external set of Common Lisp sources. Certain primitive datatypes, such as complex numbers and ratios, should be integrated into the arithmetic code at a low level. Transcendental functions such as SIN, COS, etc. must be made to work for complex numbers. Integration of these features into Interlisp would take a fair amount of effort. Instead, transport of another Common Lisp system's high level arithmetic code is recommended. At its lower levels this code will call into Interlisp's primitive arithmetic operators. 3.7 Completed features These features have already been substantially implemented in the CML library package. This section describes them and indicates where performance improvement may be possible. Our experience here can be used as a check on the estimates of development effort for the rest of the project. Arrays Common Lisp style arrays support unusual features and are a center of attention in the performance arena. We currently have an implementation which is complete, but needs microcode to improve performance. Characters We have a complete implementation of the character datatype. Bignums These were implemented last year by Larry Masinter. Defstruct There is currently a version of DEFSTRUCT which is integrated with the Interlisp RECORD package. In future, an improved version of this feature could be imported from external Common Lisp sources. The bottom end of this DEFSTRUCT code would need to be interfaced to the DECLAREDATATYPE and array access mechanisms in Interlisp. Strings and sequences The complete set of string and sequence functions were transported into the CML package by Kelly Roach and debugged by Ron Fischer. They could use compiler support of some sort, but this can wait. Macros DEFMACRO et al. are largely complete, except that Common Lisp does not allow a symbol to have both a function definition and macro definition, a feature typically used in Interlisp for optimization (though used more heavily in Interlisp-10 than -D). This is an integration issue which can, for the most part, be avoided by causing the Common Lisp versions of DEFMACRO and DEFUN to destroy existing definitions on the symbol before installing their own. Appropriate warnings can be issued. The Interlisp version of DEFMACRO, which already exists, can continue to place macro definitions onto litatoms additively. Function call and LAMBDA lists These are currently implemented in a simple way using LAMBDATRAN, but the performance and integration levels are low. The debugger for instance, does not know enough about the format of the arguments of these functions to display them in a break. We will initially improve the performance of this simple scheme, leaving a fully microcoded complex function entry for later. Such a mechanism would need to be differently handled and be made known to the Interlisp compiler to gain high performance. The compiler work would be serious. Symbol functions A simple set of symbol slot functions, including a simulation of the package slot, currently exists as part of the work on symbol packages. List functions The primitive list operations, often identical in functionality, if not name, to Interlisp's, have already been transported into the CML package from Spice. 4. Detailed estimates We now turn to an evaluation of the amount of time required to implement a Xerox Common Lisp product following this plan. In each of the three categories, the estimated time does not include formal testing beyond that required for development. We expect that an engineering, documentation and release schedule will be prepared by the appropriate functional groups to complement this proposal. The following estimates are based on both a lines of code per hour figure, and, for those parts of the system where no example code exists, expert opinion based on analysis of the problem. The size estimates for the various features come from analysis of the relevant Spice Lisp sources. In several cases, specific people are committed to specific projects where their skills are uniquely appropriate. The code transport estimates begin with the industry standard of 30 minutes per line of (new) code. Using a standard life cycle division into 3 minutes to design, 6 minutes to code, 6 minutes to integrate and 15 minutes to tune and maintain, we arrive at a figure of about 15 minutes to create a line of code (i.e., design, code and integrate) or a rate of 4 lines / hour. We will vary this "baseline" rate for some of the subtasks, if they are of unusually (high or low) difficulty. Thus, if a task is a clearly independent, simple port for which considerable structure already exists in the Interlisp system, we may estimate that as many as 8 lines / hour could be achieved, whereas a detailed low-level reimplementation may limit us to no more than 2 lines / hour. 4.1 Critical features These features will require considerable coordination with Interlisp internals. Most of them will require Interlisp experts for their design and implementation. Packages This feature will require both transporting the source code for an existing package, and a few changes to Interlisp's reader and printer and file package. The Spice Lisp sources devote 744 lines of code to this feature, thus requiring 93 hours (2.3 weeks) of a non-expert to transport the unintegrated functionality (at 8 lines / hour), plus an additional 3 weeks of an expert programmer to integrate it into the Interlisp reader/printer and file package. 2.3 weeks of a lisp programmer, to transport the code. 3 weeks of one expert lisp programmer, to integrate with Interlisp. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 5 0 2 35 961 217 package 1 Total of 744 lines of code (excluding comments). Multiple values Since the primary effort associated with handling multiple values is integration with the Interlisp run-time, this task has been estimated from an existing design. It will require 6 expert weeks, with microcode support required for the last 2 weeks of both design and implementation. 3 weeks of two expert lisp programmers, to design and build lisp code. 2 weeks of one microcoder, to finalize design and build microcode. Lexicality and closures Effort in this area falls into the following areas: compiler, interpreter, and runtime. The compiler needs to analyze GOs, free variable lookup, and the context of closure creation. The interpreter requires an interface to the lexical lookup mechanisms, plus calling into it and calling out of it. Runtime support needed will be: FUNCALL of a closure, and RETURN-FROM. Assigning about one week of a 2 person expert programming team to each of the above 6 features, we arrive at 12 man weeks. The major part of the design phase will be in the first half of this task, and we will need a microcoder in the latter 3 weeks. 12 man weeks of expert lisp programming to design and build lisp code. 3 weeks of one microcoder (last 3 weeks of above) to design and build microcode. Interpreter The interpreter requires the transport of an existing Common Lisp interpreter with some integration to allow for complete intercalling. The Spice Lisp sources devote 1313 lines of code to the interpreter, which requires 164 man hours of non-expert time to transport it (4.1 man weeks at 8 lines / hour, as integration is not comprised), plus an additional 4 man weeks of experts' time to integrate it fully. One week of expert team time is held after the freeze against the contingency of performance improvement. 4.1 weeks of one lisp programmer, to transport Spice code. 4 man weeks of expert programming to integrate with Interlisp. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 11 4 1 68 1487 174 eval 1 Total of 1313 lines of code (excluding comments). Control constructs Andy Daniels is currently working on a new design and implementation of the error system, as he has experience in this area. His software will initially use low performance routines to emulate low level support within the microcode. Once his software is complete, issues raised in its production will guide Larry Masinter, Bill vanMelle and (probably) Don Charnley in the design of its microcode support. As a basis for estimation, the Spice sources for the error and control system contains 557 lines of code. Using an coding rate of 2 lines / hour to reflect the project's complexity, it should require Andy Daniels 7 weeks to design and build the high level lisp code for the Common Lisp side of the error system. In addition, 2 weeks of an expert team, plus an expert microcoder, will be needed to finalize the design and build the lower levels of the error system. 7 weeks of Andy Daniels, to design and build higher levels of error mechanism. 4 man weeks of expert programmers. 2 weeks of one expert microcoder, to design and build lower levels of error mechanism. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 3 3 0 18 524 137 error 7 0 0 2 236 66 errorm 1 Total of 557 lines of code (excluding comments). 4.2 Features requiring integration or small changes These features will require some integration with Interlisp, or slight modifications of existing Interlisp facilities to implement them. Major pieces of each of these already exist in Interlisp, which will expedite the port. However, it will also be slowed by the need to integrate the new code with the existing facilities. These effects will offset each other to different degrees in the different subtasks, so the implementation rate will vary correspondingly, as noted. File System, Pathnames These features require both the importing of Common Lisp source code, the implementation of a specific type of file name (pathname) parsing, and interfacing of that code to the file system functions that already exist in Interlisp (i.e., directory functions, file deletion, etc.) In the Spice pathnames code, we find 839 lines of code, which would require 210 man hours or 5 man weeks. There is also a necessary extension to OPENSTREAM, which John Sybalsky has estimated would require 1 week of his time. 5 weeks of a lisp programmer, to import code. 1 week of John Sybalsky, to modify Interlisp's OPENSTREAM function. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 6 3 1 44 1040 201 filesys 1 Total of 839 lines of code (excluding comments). Streams A number of Common Lisp stream features have been implemented by Stan Lanning. Given the Spice example of 832 lines of code we arrive at a figure of 208 man hours, of which 60% is already completed, leaving 83 man hours or 2 man weeks of effort. This task could be done by either John Sybalsky or Stan Lanning. 2 weeks of either John Sybalsky or Stan Lanning, to finish building streams. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 8 1 1 7 204 113 defstream 12 1 9 58 922 181 stream 1 Total of 832 lines of code (excluding comments). Reader/Printer There is a large amount of code to be imported for this part of the system. The task will require two non-expert lisp programmers. The low levels of the imported reader code will need to integrate with Interlisp data structures for efficiency. Much of this is a pure port, but given the complexity, size and performance demands on this code, we choose to use the baseline estimate of 4 lines/hour. Thus, using the Spice statistics of 2527 lines of code, we have 631 hours or 15 weeks of lisp programming. 15 man weeks of lisp programming, to import and integrate lisp code. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 22 14 1 45 1063 171 reader 6 1 0 44 954 290 print 8 0 0 62 1184 213 format 1 Total of 2527 lines of code (excluding comments). Hash tables This feature is almost completely implemented by an existing Interlisp facility, requiring only allowing NIL to be stored into a hashtable slot and an implementation of the SXHASH function. Using the Spice sources for reference, at 335 lines and 8 lines / hour, it will require about 42 man hours or 1 man week to transport. 1 week of a lisp programmer, to modify Interlisp's hashtable datatype. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 14 1 1 11 368 33 hash 1 Total of 335 lines of code (excluding comments). Type system We have an implementation of the type feature now, which still needs SUBTYPEP and integration with whatever internal interface will be needed by the imported Common Lisp sources. The higher level parts of this feature (nearly all of it) can be imported from the Common Lisp sources, but the performance requirements augur for a careful integration and thus a conservative (4 line/hour) estimate. The Spice sources have 730 lines of code for these features, requiring 182.5 man hours (4.5 man weeks). 4.5 weeks of a lisp programmer, to transport code. 1 man week of a microcoder for low level support. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 3 1 1 6 348 37 defsubobject 3 0 0 9 557 138 subtypep 1 Total of 730 lines of code (excluding comments). SETF This requires importing some complex code and its integration with Interlisp. Using the baseline estimating rate, the Spice sources, which contain 811 lines of code, would require 202 man hours or 5 weeks of a non-expert's time to import. 5 weeks of a lisp programmer, to import and integrate lisp code. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 27 0 0 5 870 59 macros 1 Total of 811 lines of code (without comments). 4.3 New features These are mainly high level features and require little integration for our first product release. Thus, progress is assumed to be at the relatively rapid rate of 8 lines per hour. Because these features require little integration we can draw on many of our on-board Interlisp programmers to aid in importing this code into our system. The areas covered here include arithmetic, low level list functions (often requiring nothing more than renaming), basic macro functions, the pretty printer, the sequence sorting functions, etc. Spice's 3785 lines of code imply 16 man weeks of lisp programming, to import code. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 1 16 0 59 445 45 arith 3 0 0 0 116 22 constants 6 8 0 21 710 145 initializatn 1 112 0 0 176 23 lfloat-consts 1 0 0 2 54 22 macromemo 2 3 0 30 426 48 misc 6 1 1 15 207 30 objects 4 2 1 22 498 83 pprint 0 1 0 52 461 52 pred 0 0 0 3 55 24 query 0 4 1 6 116 23 rand 3 0 0 12 387 89 sort 13 77 0 28 735 79 spirrat 1 5 0 7 128 44 time 1 Total of 3785 lines of code (without comments). 4.4 Completed features These are features that have already been completed. This represents a measure of time already invested in importing the Spice Common Lisp sources which would have to be reinvested if another set of Common Lisp system sources were used. The estimate for and our experience importing these features was also used to confirm the accuracy of our basis for estimation. Some of these features may still benefit from tuning to gain performance. Expertise required for tuning varies by feature and is indicated in the separate sections. Function Call and Lambda-lists Since an implementation exists, we can postpone this work beyond the initial development. If performance is impacted, performance tuning may be required. This would require changes to the basic function calling mechanism and special encoding for &REST arguments. 6 man weeks of expert programming, to design, build and modify interpreter. 2 weeks of one microcoder, to design and build microcode. Defstruct The DEFSTRUCT feature should be interfaced with the low level Interlisp DECLAREDATATYPE feature and Interlisp arrays. The higher level section of this feature (nearly all of it) can be transported from the Common Lisp sources. The Spice sources have 1673 lines of code for this feature, requiring (at 4 lines / hour) 418 man hours (10 man weeks) of effort. 10 weeks of a lisp programmer, to import and integrate code. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 1 0 0 1 38 14 defrecord 4 1 2 20 504 65 defstruct 3 1 1 6 348 37 defsubobj 1 Total of 1673 lines of code (excluding comments). Macros The simple compatibility feature of having the Common Lisp versions of DEFMACRO and DEFUN remove each other's definitions before installing new ones is trivial to implement. However, Interlisp does not currently compile macro definitions, causing macro expansion to take up a significant percentage of compile time. Because this is such a widely known feature of other lisps, it would be of value to implement this for our system. Other The following features were described previously and have been substantially imported from the Spice sources. Because many of these features required low level integration, the baseline (4 line/hour) estimate would be appropriate. Spice's 5009 lines of code suggests 1252 man hours (31 man weeks) of effort. Note that this estimate agrees well with the approximately 1150 man hours actually expended by Larry Masinter (200), Ron Fischer (850) and others (100) in the construction of the CML library package. 31 man weeks (estimated; actually took 29) of mixed expertise lisp programming, already spent to import, design, build, and integrate. Spice source statistics: Macros Constants Structures Functions Source Comment Filename 1 1 3 0 45 553 28 array 0 0 0 6 153 44 backq 3 7 0 36 341 41 char 0 0 0 8 397 63 defmacro 1 1 0 23 433 38 debug 4 0 0 104 705 52 list 1 0 0 0 42 31 keyword 93 0 0 87 1793 73 seq 2 0 0 22 400 47 sharpm 5 0 0 33 496 40 string 0 0 0 21 171 18 symbol 1 Total of 5009 lines of code (excluding comments). 4.5 Summary of required effort All figures given are in man weeks of effort. Expertise Lisp Expert Microcode 2 Criticals (4.1) Packages 2.3 3.0 Multiple values 6.0 2.0 Lexical scoping 12.0 3.0 Interpreter 4.1 4.0 Control 7.0 4.0 2.0 1 subtotal 13.4 29.0 7.0 2 Integration and minor changes (4.2) File sys & paths 6.0 Streams 2.0 Reader/Printer 15.0 Hash tables 1.0 Type system 4.5 1.0 SETF 5.0 1 subtotal 33.5 1.0 2 New features (4.3) subtotal 16.0 2 Initial implementation 62.9 29.0 8.0 10% contingency 6.3 2.9 0.8 1 subtotal 69.2 31.9 8.8 2 Performance tuning Funcall & lambdas 6.0 2.0 Structures 10.0 1 subtotal 10.0 6.0 2.0 2 Tuned implementation 72.9 35.0 10.0 10% contingency 7.3 3.5 1.0 1 total 80.2 38.9 11.0 2 Persons, which is the final head count needed, given 15 weeks of implementation time until the code is internally frozen (assuming no overlap or dependencies). Critical Medium New Totals Persons Tuning 1 Expert Prog. 29.0 29.0 2 6.0 Lisp Prog. 13.4 33.5 16.0 62.9 5 10.0 Microcoder 7.0 1.0 8.0 1 2.0 1 Subtotals 49.4 34.5 16.0 99.9 6 18.0 10% contingency 4.9 3.5 1.6 10.0 1 1.8 1 Totals 54.3 38.0 17.6 109.9 8 19.8 1 Expert programmers: Larry Masinter and Bill van Melle. Lisp programmers: Ron Fischer, Herb Jellinek, Greg Nuyens, Andy Daniels, Pavel Curtis and John Bane, with contributions by John Sybalsky and Stan Lanning. Microcoder: Don Charnley. 4.6 Timeline Week Date Event 1 0 Feb. 3 Implementation begins. 15 May 19 All critical, low level support in place. Implementation complete, internal code freeze. Begin validation, testing and performance tuning. 21 June 30 Begin alpha test release. 26 August 4 Begin beta test release. 1 5. Resource and project impacts Timeliness is perhaps the principal requirement for this development. Therefore, in scheduling this work, we have assumed that all other plans and projects will cede resources to this activity where they conflict. The principal impact of this will be to the ongoing support that Product Development provides to other functional groups. In particular, it would require an almost total hold on bug fixes, RQI support, field and sales support visits, etc. Currently, between 20-30% of the time of several of the principals is devoted to this kind of activity and virtually all of it would have to be halted to permit the intense, focused effort we have described here. Since even the disruption caused by the preparation of this plan has caused some pain for the impacted groups, the impact of four months of this should not be taken lightly. Further, central to achieving the desired schedule is the diversion of most of our experienced Lisp talent from existing projects to this one. In addition, to eliminate the startup delays associated with hiring, we are proposing to divert incoming hires who can contribute from other projects (principally Tamarin) to this activity. This will have a dramatic, immediate negative impact on these other activities. If incremental hiring is approved to backfill this diversion, the impact would be limited to a delay in the diverted projects, but even this will be painful to these projects' constituencies. The short time fuse of much of this development mitigates against hoping to do much of it with new hires recruited for the purpose. There are two exceptions to this, however. First would be to try to recruit one or two experienced Common Lisp programmers simply to increase the number of people within the project who are fluent users of that dialect to serve as a sounding board and reality check for the implementation. These individuals are not shown on the above project charts, as it is likely that they would not arrive in time to contribute greatly to the port, but their presence here would be a great help during the later stages of testing and final integration. Finally, in addition to the technical contributors we have identified, this project would need both secretarial support (one FTE) and one junior technician to provide loadups, gather and run validation suites and performance measures, maintain file server support, etc. Several additional machines to support intensive debugging, off-site work, etc. would also be a wise investment. A complete analysis of the 1986 allocations of Product Development manpower is beyond this document. However, a brief summary of the impact of this proposal is not out of place. Partitioned by person, the effects of this project on other scheduled activities would be: Person Need Impacted activities Masinter 100% CommonLoops; troubleshooting van Melle 100% Networking; OS and VMem bug fixes Fischer 100% No impact; already assigned Purcell 25% Tamarin; 1186; Prolog Sybalsky 50% Text editor and graphics extensions Nuyens 100% Text and graphics Jellinek 100% Graphics; Prolog Charnley 50% 1186 extensions; Prolog Bane 100% Tamarin Pavel 100% Tamarin Daniels 50% Tamarin; installation utilities Failing explicit plans to backfill these people by additional hiring, their projects will slip directly in proportion to the percentage and duration of their involvement. Thus, for example, there would be no networking support at all for the four months that Bill van Melle is unavailable, unless other arrangements are made. This should be understood clearly in advance. Partitioned by project, the effects would be Color Windows Halted 4045 printing improvements Halted DIG, Keyboard rework Halted New garbage collector Halted TEdit improvements Halted Apex special requests Halted New installation utility Halted Application installation utility Halted BusMaster (1186) Halted Pre-emptive scheduling Halted Multiple streams / file Halted NS Random access Halted Other services upgrades Halted 1186 8K performance ucode 3 month delay Prolog 1186 Delayed unless easy Prolog performance tuning Halted Tamarin 6 month delay It is important that this impact is clearly understood throughout the business unit before this project schedule is committed to. 6. To close The implementation of a Common Lisp product within the allowed time frame would require a tremendous, concerted effort by all of XAIS. This plan tries to stretch this time to obtain the most comprehensive, integrated implementation possible within the need to get it to market quickly. Much of this work and planning is germane to any strongly Interlisp coupled implementation of Common Lisp. Within that class of implementations, we believe that this proposal would provide a high quality Common Lisp system that would also preserve and transition our existing customers' code assets. We request your support in facing the sacrifices that would be necessary to make it a reality. (LIST ((PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC )) (0 0 612 792) ((TEXT NIL NIL (72 72 468 648) NIL))) (PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC )) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD RIGHT) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY GACHA OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO (ARABIC )) (252 744 288 36) NIL) (TEXT NIL NIL (72 72 468 648) NIL))) (PAGE NIL (PAPERSIZE Letter FOLIOINFO (ARABIC )) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD RIGHT) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY GACHA OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO (ARABIC )) (252 744 288 36) NIL) (TEXT NIL NIL (72 72 468 648) NIL)))))=P708708@T \=P(; l2tT) T7 08= P1$$.$$4x 0x.HH.HH: l2t:l2t: l2t( @Z,h@T \( ( ( GACHA  TIMESROMAN  TIMESROMAN  TIMESROMAN TIMESROMAN TIMESROMAN b CuYk@Heo !U l% pQB )$  W7 JA#9+ ) bm$:$= s1   b v;B} <! =4   ( )*ZZ6 {> HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN 1Uw  z> HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN 2)> HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN 14'  .]  > HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN 19M> HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN 1E> HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN 2 iAG> HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN 1 E32> HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN 1A> HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN /RS> HRULE.GETFN TIMESROMAN  ! HRULE.GETFN TIMESROMAN 0o   ;=> HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN 2> HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN 2.  HRULE.GETFN TIMESROMAN  s HRULE.GETFN  HRULE.GETFN TIMESROMAN  $o HRULE.GETFN   HRULE.GETFN TIMESROMAN     HRULE.GETFN TIMESROMAN    HRULE.GETFN  HRULE.GETFN TIMESROMAN  / HRULE.GETFN  HRULE.GETFN TIMESROMAN   HRULE.GETFN HRULE.GETFN TIMESROMAN   HRULE.GETFN TIMESROMAN  HRULE.GETFN TIMESROMAN  HRULE.GETFN HRULE.GETFN TIMESROMAN 7   HRULE.GETFN TIMESROMAN  !  & &  HRULE.GETFN TIMESROMAN  I`#  + 1 ) # 2   &   ,  "      (      (  !  z