f.y.i., to appear in SIGART

[Masinter.PA]

Interlisp-D: Further steps in the flight from time-sharing

The Interlisp-D Group
Cognitive and Instructional Sciences
Xerox Palo Alto Research Center

The Interlisp-D project was formed to develop a personal machine implementation
of Interlisp for use as an environment for research in artificial intelligence and
cognitive science [Burton et al., 80b].  This note describes the principal
developments since our last report almost a year ago [Burton et al., 80a].

Principal characteristics of Interlisp-D

Interlisp-D is an implementation of the Interlisp programming environment
[Teitelman & Masinter, 81] for the Dolphin and Dorado personal computers.  Both
the Dolphin and Dorado are microprogrammed personal computers, with 16-bit
data paths and relatively large main memories (~1 megabyte) and virtual address
spaces (4M-16M 16 bit words).  Both machines have a medium sized local disk,
Ethernet controller, a large raster scanned display and a standard Alto keyboard
and "mouse" pointing device.  

Both the internal structure of Interlisp-D and an account of its development are
presented in [Burton et al, 80b].  Briefly, Interlisp-D uses a byte-coded
instruction set, deep binding, CDR encoding (in a 32 bit CONS cell) and
incremental, reference counted garbage collection.  The use of deep binding,
together with a complete implementation of spaghetti stacks, allows very rapid
context switching for both system and user processes.  Virtually all of the
Interlisp-D system is written in Lisp.  A relatively small amount of microcode
implements the Interlisp-D instruction set and provides support for a small set of
other performance critical operations.  The at one time quite large Bcpl kernel has
been all but completely absorbed into Lisp, for the reasons outlined in [Burton et
al, 80b].

Interlisp-D is completely upward compatible with the widely used PDP-10
version.  All the Interlisp system software documented in the Interlisp Reference
Manual [Teitelman et al., 78] runs under Interlisp-D, excepting only a few
capabilities explicitly indicated in that manual as applicable only to Interlisp-10. 
The completeness of the implementation has been demonstrated by the fact that
several very large, independently developed, application systems, such as the
KLONE knowledge representation language [Brachman, 78], have been brought
up in Interlisp-D with little or no modification.  Interlisp-D is in active use by
researchers (other than its implementors) at both Xerox PARC and Stanford
University and is now approaching the level of stability and reliability of
Interlisp-10.

Current performance

The performance engineering of a large Lisp system is distinctly non-trivial.  We
have invested considerable effort, including the development of several
performance analysis tools, on the performance of Interlisp-D and, as a result,
seen its performance improve by nearly a factor of five over the last year. 
Although relative performance estimates can be misleading, because of variation
due to choice of benchmarks and compilation strategy, the overall performance of
Interlisp-D on the Dolphin currently seems to be about twice that of Interlisp-10
on an otherwise unloaded PDP KA-10.  Although this level of performance
makes the Dolphin a comfortable personal working environment, we have
identified a number of improvements which we anticipate will further improve
execution speed by between 20% and 100%.

Machine independence

Another major thrust has been to reduce the dependencies on specific features of
the present environment, so as to facilitate Interlisp-D's implementation on other
hardware.  Dependencies on the operating system have been removed by
absorbing most of the higher (generally machine independent) facilities provided
by the operating system into Lisp code.  Gratuitous dependencies on attributes of
the hardware, such as the 16-bit word size, have been removed and inherent
ones isolated.  In addition to an abstract desire for transportability, our sharing of
code with other Interlisp implementation projects provides a on-going motivation
for this effort.

Extended functionality

The principal innovations in Interlisp-D, with respect to previous
implementations of Interlisp, involve the extensions required to allow the
Interlisp user access to a personal machine computing environment.

Network facilities

While network access is a valuable facility in any computing environment, it is
of particular importance to the user of a personal machine, as it is the means by
which the shared resources of the community are accessed.  Over the last year,
Interlisp-D has incorporated both low level Ethernet access and a collection of
various higher level protocols used to communicate with the printing and file
servers in use at PARC.  It is now straightforward to conduct all file operations
directly with remote file servers.  This both allows the sharing of common files
(e.g., for multi-person projects, such as the construction of Interlisp-D itself),
permits a user to move easily from one machine to another, and eliminates any
constraints of local disk size.  We have also begun to investigate the possibility
of paging from a remote virtual memory elsewhere on the network.  This would
not only allow completely transparent relocation of a user's environment from
one machine to another, but would open up a variety of interesting schemes for
distributing a computation across a set of machines.

High level graphics facilities

Interlisp-D has always had a complete set of raster scan graphics operations
(documented in [Burton, 80b]).  More recent developments include a collection of
higher level user graphics facilities, akin to those found in other personal
computing environments.  The most important of these is the Interlisp-D window
package.  This facility differs in spirit from most other window systems in that,
rather than imposing an elaborate structure on programs that use it, it is a self
consciously minimal collection of facilities which allow multiple programs to
share the same display.  Although some mechanism is necessary to adjudicate a
harmonious sharing of the display, we feel that higher level display structuring
conventions are still an open research question and therefore should not yet be
incorporated into a mandatory system facility.  The window package does provide
both interactive and programatic constructs for creating, moving, reshaping,
overlapping and destroying windows, in such a way that a program can be
embedded in a window in a completely transparent (to that program) fashion. 
This allows existing programs to continue to be used without change, while
providing a base for experimentation with more complex window semantics in the
context of individual applications.

One such existing application is a display based, structural program editor.  This
editor, in contrast to the character orientation of most modern display based
program editors, is the result of marrying display techniques (selection and
command specification by pointing, incremental reprinting, etc) with the
structure orientation of the existing Interlisp editor.  Indeed, the two editors are
interfaced so that the considerable symbolic editing power of the existing editor
remains available under the display based one.  Although our initial experience
has been positive, the user interface is under continued revision as we gain
further experience with this style of editing.

Future plans

The area in which we anticipate most future development of Interlisp-D is the
personal computing facilities, such as graphics and networking, and their
integration into Interlisp's rich collection of programming support tools.  While
radical changes to the underlying language structures are made difficult by our
desire to preserve exact Interlisp compatibility, we also expect some language
extensions, including some form of object oriented procedure invocation.

One of the great strengths of Interlisp has been the many contributions made by
its active, critical user community.  We are hopeful that the recent commercial
availability of Interlisp-D to other sites, and the consequent growth of its user
community, will be a similar source of long term strength and, in the short term,
significantly accelerate the pace with which Interlisp evolves away from its
time-shared origins into a personal computing environment.

REFERENCES

Brachman, R. et al.
KLONE Reference Manual.  BBN Report No. 3848, 1978.

Burton, R. et al.
Overview and status of DoradoLisp.  Proceedings of the 1980 Lisp Conference,
Stanford, 1980a.

Burton, R. et al.
Papers on Interlisp-D. Xerox PARC report, SSL-80-4, 1980b.

Teitelman, W. et al.
The Interlisp reference manual.  Xerox PARC, 1978.

Teitelman, W. and Masinter, L.
The Interlisp programming environment.  IEEE Computer, 14:4 April 1981, pp.
25-34.

The members of the Interlisp-D group are Beau Sheil, Bill van Melle, Alan Bell,
Richard Burton, Ron Kaplan and Larry Masinter.