What to do next

[Scott E. Fahlman <Fahlman@CMU-CS-C.ARPA>]

    Date: Thursday, 18 August 1983  11:54-EDT

    (1) Create a Common Lisp Virtual Machine specification, and gather a
    body of public domain Lisp code which, when loaded into a proto-Lisp
    that meets the spec, produces a complete Common Lisp interpreter that
    meets the full language spec.  (This doesn't address the portable
    compiler problem.)

Our Spice Lisp implementation is currently serving exactly this need for
about 6 implementation efforts.  Instead of specifying a little Lisp kernel
that has to be implemented, we specify a byte-coded instruction set,
then provide Common Lisp written in Common Lisp (with some of these
byte-coded primitives sprinkled in), plus a compiler written in Common
Lisp that produces these byte codes.  All a prospective user has to
supply are either microcode for the byte-codes or a post-processor from
byte codes to their machine's native instruction set, plus the byte-code
primitives, GC, I/O, and the system interface stuff.  Of course, once
that is done, it is worth putting about a man-year of tuning into any
given implementation to make it run as well as possible.

So our SLGUTS document, along with our public-domain Lisp code and
compiler, do most of what the blue pages are supposed to do.  We are
currently polishing our system up so that it is legal, and in the
process we are cleaning up our compiler so that it will be easier to
replace the whole code-generator, if people would rather do that than
work from byte-codes.  We also plan a substantial cleanup on our
byte-code set, which is by now quite obsolete and creaky.

The next obvious step is to take all of this and turn it into a cleanly
packaged "implementor's kit".  That would reduce the amount of
hand-holding we would have to do and make the whole thing look more
portable.  I don't have much interest in taking this additional (largely
cosmetic) step, but would cooperate with anyone else who wants to do it.
Of course, if someone wants to build a better compiler/kit (ours is more
stack-oriented than is optimal on conventional architectures and does
not have all those hairy optimizations in it that real compiler hackers
love), that would be a good thing to do.

So I guess I see this as a mostly-solved problem and therefore not a
high-priority issue.

    (2) Establish an official Common Lisp subset, suitable for
    implementation on 16-bit microcomputers such as the 68000 and the 8088.

I'm a little dubious about this subsetting business.  It is true that
one could get rid of maybe half the virtual core image by judicious
trimming, though including a compiler or Hemlockish editor would push
you back up there.  Rather than worry a lot about trimming the Lisp and
about going from a big core image to autoload, maybe the time should be
spent figuring out how to fake a decent virtual memory system on these
machines.  It would be nice to have things like Format lurking out on
the floppies but virtually there, rather than gone but autoloadable.

A whole generation of people learned to hate Lisp because they tried to
prehistoric implementations without good debugging tools,
pretty-printing editors,and the other things that make Lisp a decent
programming environment.  Let's not repeat this and expose high-school
kids to the result.

One thing we might do, if we want Common Lisp programs to be deliverable
on micros with the minimum of memory, is to work on a system that goes
over a set of compiled files and builds a Lisp core image with only
these things and the Lisp facilities that they call included.  You would
develop on your Vax or 3600, but the turnkey expert system might then
run on a 68000-based machine with minimal disk.

Anyway, to respond to your suggestions:

    Complex numbers can easily be omitted.
[ Yep.  Should ahve been omitted from the real thing, and may still be
if nobody works up the enthusiasm to implement them.]

    The requirement for all the floating point precisions can be
    omitted.  Of course, Common Lisp is flexiable in this regard anyway.
[ Yeah.  The high-school version could leave them out altogether, and
all the trascendental functions, for a big saving. ]

    Rational numbers could be left out.  They aren't hard, per se, but
    they're just another thing to do.  The "/" function on two integers
    would have to signal an error.
[ This wouldn't save much -- GCD is all you need and that's not too big.
Maybe leave out the Float/rational conversions.]

    Packages could be trimmed down to only be a feature that supplies
    keywords; most of the package system might be removable.
[ Yeah.  Again it doesn't save much. ]

    Lexical scoping might possibly be removable.  You could remove support
    for LABELS, FLET, and MACROLET.  You can't remove internal functions
    entirely (i.e. MAPCAR of a lambda-expression can't be removed) but they
    might have some restrictions on them.
[ Lexical scoping doesn't cost much in space, but it slows down the
interpreter and adds much hair to the compiler.  If you want to save on
compiler space, let GO and RETURN be confined in the traditional way
(only to a cleanly surrounding block and not from a position that leaves
crud on the stack) and eliminate lexical closures and the FLET stuff.]

    Adjustable arrays could be removed.  Fill pointers could go too,
    although it's not clear that it's worth it.  In the extreme, you could
    only have simple arrays.  You could even remove multi-D arrays
    entirely, or only 1-D and 2-D.
[ This would save a fair amound in dispatching hair.  Not trying to
super-optimize for speed would also save a lot of space -- whether
that's a good trade depends on the machine and the applications.]

    Several functions look like they might be big, and aren't really
    required.  Some candidates: COERCE, TYPE-OF, the hard version
    of DEFSETF (whatever you call it), LOOP, 
[Yup.]

    TYPEP and SUBTYPEP are hard to do, but it's hard to see how
    to get rid of the typing system!  SUBTYPEP itself might go.
[Got to have TYPEP, but not the hairy compund types and booleans.
Subtypep is needed by the compiler but not much by user code.]

    Multiple values would be a great thing to get rid of in the subset, but
    there are the Common Lisp primitives that use multiple values.  Perhaps
    we should add new primitives that return these second values only, for
    the benefit of the subset, or something.
[If you're willing to cons when passing back multiples, or to limit the
number to, say, 3 values, it becomes easy to do.  I believe that only
our unfortunate time functions return more than a few values.]

    Catch, throw, and unwind-protect could be removed, although they're
    sure hard to live without.
[No, you've got to keep these.  They become easy to do if you don't have
to pass multiple back on the stack.]

    Lots of numeric stuff is non-critical:  GCD, LCM, CONJUGATE, the
    exponentials and trascendentals, rationalize, byte manipulation, random
    numbers.
[Leave in hyperbolic arctan, though -- every language needs at least one
function that nobody has ever tried.]

    The sequence functions are a lot of work and take a lot of room in your
    machine.  It would be nice to do something about this.  Unfortunately,
    simply omitting all the sequence functions takes away valuable basic
    functionality such as MEMQ.  Perhaps the subset could leave out some of
    the keywords, like :test and :test-not and :from-end.
[Again, these are simple if you're willing to do everything with ELT and
FUNCALL and are not going for tenseness.  It is checking for 53 special
cases that blow things up.  If you don't have them in, people will write
DO's and their code will balloon.]

    Hash tables are not strictly necessary, although the system itself
    are likely to want to use some kind of hash tables somewhere,
    maybe not the user-visible ones.
[Again, if you want tiny but slow, an A-list can do anything a
hash-table can.]

    Maybe some of the defstruct options could be omitted, though I don't
    think that getting rid of defstruct entirely would be acceptable.

    Some of the make-xxx-stream functions are unnecessary.

    Some of the hairy reader syntax is not strictly necessary.  The circular
    structure stuff and load-time evaluation are the main candidates.

    The stuff to allow manipulation of readtables is not strictly necessary,
    or could be partially restricted.

    Some of the hairy format options could be omitted.  I won't go into
    detail on this.

    Some of the hairy OPEN options could go, although I'd hate to be the one
    to decide which options are the non-critical ones.  Also some of the
    file operations (rename, delete, attribute manipulation) could go.
[All of the above sounds OK.]

    The debugging tools might be optional although probably they just
    get autoloaded anyway.
[For an educational system on cheap machines, you don't skimp here.  For
a delivery vehicle, you don't need these.]