Common Lisp Implementation
A description of:
the early part of an effort at Rutgers
features of the current AIS in house effort
comparison of Rutgers and local projects
the major features of Common Lisp
some issues bearing on inhouse vs. contract work
by Ron Fischer, 21-Nov-85
file: {ERIS}<FISCHER>CML>CL-IMPLEMENTATION.TEDIT
A description of the Common Lisp effort at Rutgers may help us understand the resource requirments for implementing Common Lisp based on the CMU Spice Lisp sources.  It appears this is what an in-house effort at AIS would need to do to implement a Xerox Common Lisp within the deadline we've been given.  Some of the major features of Common Lisp are described, indicating their difficulty of implementation and performance.  A few comments have been gathered on the merits of in-house vs. external implementation.  A broadly based estimation of the manpower required to implement Xerox Common Lisp is included.
The effort at Rutgers, a condensed history
Sometime in 1980 the Rutgers University Lab for CS Research was given a grant by DEC to produce an extended addressing version of Lisp for TOPS-20.  The choice between the, then emerging, Common Lisp or, established Interlisp dialects was resolved in favor of Common Lisp.  I was working part-time for Dr. Charles L. Hedrick, director of the  lab, doing minor bits of Lisp work at that time.  After my graduation the position became full time and we began implementing Common Lisp.
Dr. Hedrick and JoSH Hall had just completed implementing an "extended addressing" version of Rutgers/UCI lisp, done to indicate feasability for the grant.  UCI Lisp is based on Lisp 1.6; Rick Lafaivre (as Rutgers undergraduate) improved the user interface to create "Rutgers Lisp."
The group which was to implement the  system:
Dr. Hedrick, occasionally lending a hand
JoSH Hall, working on it about 25% of the time
myself, full time
In 1981 Common Lisp's specifications were not entirely clear.  The design group was still arguing interminably via mail on the arpanet.  It was unclear whether there was any "ground to stand on" in the early spec, such that we would not have to throw away code due to the near furor among the Common Lisp designers.
Fortunately the group coordinating the Common Lisp effort at Carnegie-Mellon University was simultaneously implementing a public domain version of extended Common Lisp, written in itself.  The software was initially written using MacLisp extended to look like Common Lisp.  The CMU system was called  "Spice Lisp" and produced bytecodes for an instruction set microcoded on PERQ machines.
It was clear to us the quickest route to a working system with minimal wasted effort was to buld on the code availible from CMU; to convert the compiled Spice bytecodes into something that Rutgers Lisp could load and run.  The task of writing the convertor, following the changes being made to Spice, and twisting both the  Spice and Rutgers Lisp sources into line fell to me.
The majority of my work was in designing the stack machine bytecode to register machine instruction converter.  Simultaneously, suitable mechanisms for function calling and multiple value return had to be implemented.  Making the effort a bit harder was the problem of new versions of Spice.  Approximately every two months I would FTP corrected and extended sources from CMU.  Reintegrating local changes to this code was a time consuming task, as we were working below what anyone could consider a "standard progamming interface."  Chuck Hedrick covered major structural changes to the Rutgers Lisp MIDAS assembly code.  JoSH Hall contributed ideas primarily.  The effort resulted in a  release in late 1982 with a corrected version in early 1983.
Current Common Lisp implementation strategy at AIS
As I understand it, a simple plan had evolved among the technical  staff which would gradually make Common Lisp available over the course of a few releases.  Use of the Spice code was to be avoided as much as possible.  However, the announcement of 2Q86 as a deadline for the release of Xerox Common Lisp seemed to preclude an easily paced development effort.
In light of the deadline a reasonable modification of the plan, assuming about  4 people working on it, would be to import as much of the Spice code as possible.  This could bring us to a release with a complete Common Lisp, but one whose performance was rather low.  I believe that contracting out the work at this time would return about the same result, plus additional disadvantages (see below).
Given additional resources the plan might be modified to first bring over much of the Spice code and then replace parts of it on the basis of performance measurements.  This would give us a fallback position and allow additional people to be used to improve the implementation as possible.
Rutgers experience vs. our plans
Similarities in both projects include:
Starting with an exisiting lisp
Using the CMU Spice Lisp code
Few resources
Positive differences include:
Common Lisp is a fixed spec, thus there is no need to reintegrate new releases.
Three years of improvement inthe quality of Spice Lisp.
Negative differences:
Rutgers quality constraint was lower than ours; it did not  include testing and documentation.
Rutgers focussed effort mainly on a code translator / generator.
Estimation of the time it takes to do coding is, at best, an inexact and somewhat mystical science.  In an organization with easily quantifiable past effort to measure against this might be be possible to some degree of accuracy.  Intuitively, I believe that it would take us approximately the same effort that Rutgers put out, plus "a wee bit more," balancing four full time people here against additional time at Rutgers, and accounting for the overhead of documentation.
Common Lisp: the primary features
Common Lisp differs from Interlisp in several major and many minor ways.  If a more detailed plan of progress charting is to be developed this information may be of help.  Some subsystems of Common Lisp are not mentioned below, such as the Structure system, characters, etc. because they are either already implemented or have a trivial implementation (we hope).
Common LOOPS and structures
It appears that Common LOOPS will become a standard.  A portable version has been implemented at PARC and performance tuning of an Interlisp-D version is now underway.  The structure feature requires extensive cleanup.
Arrays
Common Lisp style arrays support unusual features and are a center of attention in the performance arena.  We currently have an implementation of Common Lisp arrays, which is complete in itself but not fully integrated with older Interlisp array-like structures.  This feature is completed and awaits implementation of microcode to improve performance.  When possible, better integration with Interlisp will be attempted.
Packages
This is an enabling feature of Common Lisp, as it allows a flexible division of Interlisp and Common Lisp name spaces (oblists).  Functions of the same name in Interlisp-D and Xerox Common Lisp will be different and can be specified by a prefix, eg INTERLISP:ERROR or COMMON-LISP:ERROR.  This software has been started.  Difficulty in its implementation  lies in integrating it with the File Package and existing Interlisp Reader and Printer.
Multiple values
Common Lisp allows functions to return more than one value.  The troublesome aspect of this is that  if the receiving function expected a single value the additional ones are discarded.  There is currently a low performance simulation of this behavior.  However, because the Common Lisp system functions use multiple values themselves, overall system performance would be severly impacted.  This is an important feature but might be delayed if further analysis shows the schedule is too tight.
Lexical closures
Common Lisp requires the creation of lexical closure objects in the FUNCTION quoting convention.  This requires a short analysis of a Common Lisp function to determine what free variables within it need to be "closed over."  There are some general techniques for creating closure objects, but the analysis of code will be slightly tricky and take some time to implement.  There is currently support in Interlisp-D for creating a closure-like object given that one knows which free variables which need to be closed over.
Lexical scoping
Common Lisp is lexically scoped, meaning that local variables are only accessable when their references are visibly and textually nested within a defining form.  To implement this requires a somewhat clever modification to the variable binding search mechanism.  This will require some of a wizard's time to implement properly.  It is required for our version to be called  a real Common Lisp.
File system interface and Streams
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, a new type of stream, called a "synonym stream" needs to be created.  I am not familiar with the Interlisp stream code, but I believe this would require largely original code.
Reader/Printer
Common Lisp's reader and printer have many features not implemented in Interlisp.  These can be brought in directly from the Spice code at first.  However, performance will probably not be very good for such a reader; this is a critical piece of the system.  While not neccessary it is highly desiable for us to have a high performance version.
Common Lisp style LAMBDAs
These are currently implemented in a simple way using LAMBDATRAN, but whose performance and integration level is low.  The debugger for instance, does not know enough about the format of the arguments of these function to display them in a break.  The Common Lisp function entry mechanism needs to be differently handled, CDR coding stack &REST for instance, and be made known tothe Interlisp compiler to gain reasonable performance.  The compiler work is serious but could be delayed since there is a workable version now.
New primitive data number types
Certain primitive datatypes, such as complex numbers and ratios, need to be integrated at a low level into the arithmetic code.  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.  Transport of the Spice code in the interim would be a better idea.
Common Lisp style macros
The compiler and interpreter may have to understand Common Lisp vs Interlisp context to handle the MacLisp style macro definitions.  Common Lisp does not allow a symbol to have both a function definition and macro definition, which is used throughout Interlisp to optimize functions during compilation.
Overall integration with the Interlisp Programming environment
This is needed  for us to claim Interlisp's strongest selling point as an advantage of Xerox Common Lisp over its competitors.  A fair amount of time will need to be spent insuring that all parts of a Spice based implemenation do the needed bookkeeping for the File Package, etc.
In-house vs external contractor
From a software implementor's viewpoint the major  factors are:
The constraints on an outside organization are almost exactly the same as on us.
Poor integration, external contractor can't "hook in" as easily as we can.
Support for externally implemented software will be neccessarily more difficult.
and...
It will be very expensive.
The Quintus experience may shed considerable light on these aspects.
Closing comment
Of course, I offer my help to the detailed planning and operation of this effort in any way possible.  I remain conservative because of my newness in the organization and a desire to draw in as much aid as as possible.  I believe that if we give about 4 programmers the task of writing Common Lisp that it can be done before the deadline using Spice code for the majority of it.  Additional effort, or early completion would allow us to significantly debug or performance tune the implemenation.  There are a number of reasons not to use an outside organization for the work, the most important of which are cost (high) and  maintainability of the resulting product (difficult and low). 
Effort speculation
The following is an estimation of the amount of time required to implement Xerox Common Lisp.  It is  based on effort to feature difficulty based on my implementation of the Common Lisp Array code and the Rutgers experience implementing Common Lisp.
Basis
Transport of as much Spice code as possible, use Interlisp evaluator, compiler, environment, etc.  Need complete implemenation more than high performance.  Given: deadline of end of 2Q86.
Effort needed (per feature)
These numbers are based on the size of the existing Spice code and the amount of effort put into the CMLARRAY package.  Behind those estimates I'm very unsure of is placed a "?"
Reader: extending Interlisp reader: about 4mm
Printer: transport code 1mm
Sequences: transport Spice 1mm
Lexical scoping: stack format change, internal Interlisp structure change 2mm (?)
Closures: code analysis and integration 1mm
Multiple values: stack format change, microcode 4mm
Packages: deep change to atoms, integrate with Interlisp 4mm
Arith: transport Spice 1.5mm
Low level number types (ratios and complex): 1mm
Macros: 0.5mm
File system and streams: 4mm
Documentation: 4mm
Timeline
Release end of July.  June/July beta, June alpha, begin January leaving 5 months.
Totals
Rutgers effort had, in 18 months, 1 fulltime for 18mm, 1 megawizard for 2mm, and 1 wizard for 5mm, making  approximately 25mm for a similar effort.
Given about 4 people over 5 months and adding an average expertise factor of an additional 1.5 people gives 5.5 x 5 = 27.5mm as a non-conservative estimate.
Above feature list indicates 28mm of effort needed, including documentation.
Estimating a confidence level of plus or minus 25%, gives no saftey margin to complete on time.  Upper end overrun at + 1.5 months with 5.5 person effort.  Sounds similar to Koto release effect.
Desirable addtions
Once the first draft of Xerox Common Lisp is done the following will be desirable to produce an implementation which we will be able to benchmark without shame:
Improved handling and integration of lambdas; stack format change, microcode 3mm
Initial performance tuning; microcode and compiler support 6mm
($$
(
(
(MODERNMODERN
MODERNMODERNMODERN
MODERNÏKd*


â
.
)
/

<
…
yî2


h
�
" 

'
 


P
8
_
A
Ú!


k
§
2


¦

»

î	
Š"
\

Y


q

/?


@
Q
K
Q
E

°
ú
¼²
.


R
,
4
=

1



R
”�Má
Q
?
8i×zº