perm filename ARPA.TEX[COM,LSP] blob sn#695972 filedate 1983-01-18 generic text, type C, neo UTF8
C00001 00001
C00002 00002	\varunit 1truein
C00003 00003	\sect Introduction.
C00007 00004	\sect History.
C00013 00005	\sect Documentation for Common Lisp.
C00018 00006	\sect The Proposal.
C00022 00007	\sect Compiler.
C00026 00008	\eat
C00028 00009	\sect Attachment.
C00031 ENDMK
\varunit 1truein
\input macros[can,rpg
\jpar 1000
\def\InterLisp{I{\sc NTERLISP}}
\varunit 1truein
\paper:Proposal for Common Lisp

\sect Introduction.

Common Lisp is the combined effort of eight different Lisp implementation
groups\footnote{These groups are: Spice Lisp at CMU, DEC Common Lisp on
Vax at CMU, DEC Common Lisp on DEC-20 at Rutgers, S-1 Lisp at LLNL,
Symbolics Common Lisp, LMI Common Lisp, Portable Standard Lisp at Utah,
and Vax NIL.}  aimed at producing a common dialect of Lisp while allowing
each group to exploit its own hardware. Common Lisp is a set of documents,
a language design, and a common body of code.

The main goal of Common Lisp is to unify the experiences of the
Lisp implementations that are descended, either historically or
philosophically, from MacLisp. MacLisp is a dialect of Lisp that
emphasizes ease of system-building and efficient execution of numeric

Other goals of Common Lisp are to provide a workbench programming
language for artificial intelligence, symbolic algebra, robotics,
and education for the next decade. With such a commonly available
and commonly used Lisp it would be possible for researchers to
exchange programs with a minimum of effort, even though the host
computers could be very different. Such a Lisp would be powerful enough
to write a sophisticated operating system sufficient to support its
own use and would, thereby, prove to be a useful systems research tool
as well as a tool for creating Lisp machine environments.

With a powerful Lisp widely available, research centers might not have
to consider the language features of the Lisp(s) available on various
computers as part of the decision regarding what hardware to purchase.
In this way a more intelligent and effective choice could be made.

Common Lisp should support an easily-understood, portable programming style.
By making a large number of packages written in Lisp available it is hoped 
that not only would the amount of work needed to get a system running be
low, but the overall programming style and methodology would be improved
through exposure to the code written by expert programmers.

\sect History.

After the usefulness of the PDP-10 as a Lisp engine declined because its
address space was limited to 18 bits, several implementation groups
started to implement Lisps for computers with larger address spaces, and
these implementors tried to improve and extend MacLisp, both to take
advantage of lessons learned from MacLisp and the various languages built
on top of it (Scheme, for example) and to also exploit the architectures
the implementors were using.

It soon became clear to several of the implementors\footnote{These people
were: Richard Gabriel of Stanford and Lawrence Livermore National
Laboratory, Guy L. Steele Jr. of Carnegie-Mellon University, Jon L. White
then of the Massachusetts Institute of Technology, and Scott Fahlman of
Carnegie-Mellon University.} that the situation of four different Lisps
\footnote{Vax NIL, SPICE Lisp, Lisp Machine Lisp, and Franz Lisp.}  all
descended from MacLisp, all used by ARPA-sponsored institution, and each
different from the others in subtle, yet important, ways, was intolerable
to the research community. Several key meetings among the implementors
resulted in an initial commitment to unify the approaches in the form of a
large, common subset, which was to be called `Common Lisp.' Of the four
major Lisp implementations, only Franz Lisp did not appear interested in
joining the Common Lisp group, and for financial rather than philosophical

Since this informal group got together, the language, Common Lisp,
has been largely designed and a manual written that describes the
language at user-level.  The original informal group has expanded into a
larger, formal committee which is collaborating on the language design and
documentation in a loose fashion. This group, called the `Common Lisp
Group', maintains a mailing list and an archive of working messages at
SAIL (Stanford Artificial Intelligence Laboratory).
Many decisions have been made about the political organization of Common
Lisp and about what the manual does and does not require of an

To be most useful, Common Lisp must support a large body of packages and
routines, so that a tradition of code, so to speak, is maintained. For
example, pattern matchers, object-oriented programming packages, and
indexing routines should be available so that projects requiring these
tools can use existing, well-tested code. In addition, these packages
ought to be of certified quality of functionality and documentation.

If Common Lisp is to be widely used it must be available on hardware not
currently supporting Common Lisp dialects. Since Common Lisp is a large
language, producing a working Common Lisp simply from the manual would
require several man-years of effort. One of the next tasks to be
undertaken is to define Common Lisp in terms of a {\sl virtual machine}

Such a description is a formal definition of a number of primitives that
must be defined on the hardware in question. Then the remainder of Common
Lisp is defined as a body of Common Lisp code written with the assumption
that these primitives exist. Once these primitives are defined on a piece
of hardware, a Common Lisp interpreter is gained by `loading' the body of
Common Lisp code.

\sect Documentation for Common Lisp.

Currently Common Lisp is nothing more than an orgranization for
documentation along with some of that documentation. To be complete
as envisioned by the Common Lisp Group, the rest of the documentation
must be brought into existence.

The Common Lisp documentation is divided into four parts, known as the
{\sl white pages}, the {\sl yellow pages}, the {\sl red pages}, 
and the {\sl blue pages}.

The {\sl white pages} is a language specification rather than an implementation
specification.  It defines a set of standard language concepts and
constructs that may be used for communication of data structures and
algorithms in the Common Lisp dialect.  This is sometimes referred to as
the ``core Common Lisp language,'' because it contains conceptually
necessary or important features.  It is not necessarily implementationally
minimal.  While some features could be defined in terms of others by
writing Lisp code (and indeed may be implemented that way), it was felt
that these features should be conceptually primitive so that there might
be agreement among all users as to their usage.  (For example, bignums and
rational numbers could be implemented as Lisp code given operations on
fixnums.  However, it is important to the conceptual integrity of the
language that they be regarded by the user as primitive, and they are
useful enough to warrant a standard definition.)

The {\sl yellow pages} is a program library document, containing documentation
for assorted and relatively independent packages of code.  While the white
pages are to be relatively stable, the yellow pages are extensible; new
programs of sufficient usefulness and quality will routinely be added from
time to time.  The primary advantage of the division into white and yellow
pages is this relative stability; a package written solely in the
white-pages language should not break if changes are made to the
yellow-pages library.

The {\sl red pages} is implementation-dependent documentation; there will
be one set for each implementation.  Here are specified such
implementation-dependent parameters as word size, maximum array size,
sizes of floating-point exponents and fractions, and so on, as well as
implementation-dependent functions such as input/output primitives.

The {\sl blue pages} constitutes an implementation guide in the spirit of the
Interlisp virtual machine specification.  It specifies a subset of the
white pages that an implementor must construct, and indicates a quantity
of Lisp code written in that subset that implements the remainder of the
white pages.  In principle there could be more than one set of blue pages,
each with a companion file of Lisp code.  (For example, one might assume
{\sc IF} to be primitive and define {\sc COND} as a macro in terms of IF, while
another might do it the other way around.)

\sect The Proposal.

At present the white pages portion of Common Lisp is nearly complete, that
document being edited by Guy Steele Jr. at CMU. Since Guy Steele is
taking a leave-of-absence from CMU to work at Tartan Labs, and since Scott
Fahlman, the head of the Spice Lisp project and a major contributor to
Common Lisp, wants to return to his AI research, the administrative
control of the Common Lisp effort is in question with several important
parts left undone. Stanford University proposes to complete those parts.

In particular we propose to do three things.  We will complete the white
pages: though Guy Steele will be able to work several hours a week on that
task while at Tartan Labs, it may prove impractical for him to spend all
the time needed for the job. We will help him finish the writing and
editing, arrange and direct the Common Lisp Group meetings, and perform
the administrative work necessary to complete the language specification
and documentation.

We will produce the first version of the yellow pages. This task consists
of gathering proposed packages, validating the documentation, insuring the
portability, and doing some testing of the code before it is included in
the yellow pages. All code will be uniformly housed at Stanford with
access to all ARPA contractors.  This document and library is to be
completed by the end of December 1984.

Finally, and most importantly, we will produce the first version of the
blue pages. This requires producing a detailed specification of the subset
of the white pages that must be implemented by an implementation group to
support Common Lisp, expanding on the white pages description where
necessary. We will also write, test, and document an implementation of
Common Lisp in that subset and make that code available to anyone wanting
to implement a Common Lisp. Thus, for any group to implement a Common
Lisp, all that will need to be done is to write the specified language
subset in whatever other language their hardware supports and to then take
a copy of the Lisp code we will have produced which will complete the
implementation of the white pages language.  This document and code is to
be completed by the end of December 1985.

\sect Compiler.

Of course, the blue pages is not complete without a portable compiler.
Such a compiler could be of the form of a machine-independent portion and
a machine-dependent portion. The machine-independent portion can perform
source-to-source transformations, flow analysis, data-structure analysis,
tail-recursion analysis, and environment analysis. The machine-dependent
portion can perform target annotation, register allocation, and code
generation. The S-1 compiler for Common Lisp is largely structured this
way. Many of the machine-dependent parts are table-driven. This compiler
could be adapted for use as a portable Common Lisp compiler.

The generation of a complete Common Lisp can be made relatively simple using
a compiler which compiles {\sl sub-primitives} such as those necessary for
doing storage allocation and performing garbage collection. The S-1 Common Lisp
system is built this way, and only about 400 lines of assembly language code
is required to build the Lisp system.

We propose to investigate the feasibility of a portable compiler by doing a
preliminary restructuring of the S-1 Lisp compiler and by examining the
structure of the Utah Portable Standard Lisp compiler. 

We would like to do the machine-independent compiler, but it may be impossible
to find the personnel to help with this task. Without doing the compiler
we will require a full-time staff member and a half-time graduate student.
A second full-time staff member would be required for the compiler work,
and there simply is a shortage of qualified people in the area at present.

A collaborative effort with the University of Utah could be productive
since they have considerable expertise in portable systems and have expressed
an interest in the task.

We would like to explore the issue of producing a portable compiler and
would wish to reserve the right to request additional funding for this
project if personnel are located.

\sect Equipment.

The cost of computer time to research personnel in the Computer
Science Department has risen dramatically recently. 
Not only has the cost of SAIL risen, but the feature of being able
to control the scheduler to guarantee service at a reasonable
level has been administratively removed, and the amount of
usable service available on SAIL has dropped below the tolerance

Since the work required to test the Yellow pages code and to develope the
Blue pages system require considerable computer time, the best way to
achieve the level of service needed is with a personal computer.
Therefore, we are requesting funds for one personal Lisp machine for the
computing portion of the work proposed and some funds for timesharing on
the SAIL computer for the documentation portion of the work.

\sect Attachment.

Attached to this report is  a budget projection.

\ssect Salaries.

$$\vcenter{\halign to size{#\hfill\tabskip 0pt plus 100pt
⊗\hfill #⊗\hfill #⊗\hfill #\tabskip 0pt\cr
Item⊗1983⊗1984⊗1985\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Research Associate⊗30,000⊗33,000⊗36,300\cr
Support⊗1,000⊗1,100⊗1,250\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Total Salaries⊗31,000⊗34,100⊗37,510\cr

\ssect Direct Costs.

$$\vcenter{\halign to size{#\hfill\tabskip 0pt plus 100pt
⊗\hfill #⊗\hfill #⊗\hfill #\tabskip 0pt\cr
Item⊗1983⊗1984⊗1985\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Four Trips per Year⊗2,000⊗2,300⊗2,645\cr
Computer Use⊗12,000⊗14,400⊗17,280\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Total Direct Costs⊗53,260⊗59,926⊗67,562\cr
Total Indirect Costs⊗36,750⊗41,349⊗46,618\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Total Costs⊗$\$$90,009⊗$\$$10,1275⊗$\$$11,4180\cr}}$$

The second budget includes money for a graduate student. This brings the
first-year total to over $\$$100,000.  With this budget a much better
Blue pages can be done. In particular such things as the interrupt system
can be well-thought out. Still a portable compiler will not be done.

The final budget includes money for a Lisp machine and two students.
If two students are not available, a programmer could be  hired with the
money. With this budget the portable compiler will be done. This increases
the value of the Blue pages tremendously, lightening the burden on the
implementors of a Common Lisp for a new machine.