@Device(lpt)
@style(justification yes)
@style(spacing 1)
@use(Bibliography "<griss.docs>mtlisp.bib")
@make(article)
@modify(enumerate,numbered=<@a. @,@i. >, spread 1)
@modify(appendix,numbered=<APPENDIX @A: >)
@modify(itemize,spread 1)
@modify(description,leftmargin +2.0 inch,indent -2.0 inch)
@define(up,use text,capitalized on, break off)
@define(mac,use text, underline off, break off)
@define(LISPmac,use text, underline alphanumerics, break off)
@pageheading(Left "Utah Symbolic Computation Group",
Right "December 1981",
Line "Operating Note 60"
)
@set(page=1)
@newpage()
@begin(titlepage)
@begin(titlebox)
@b(A PASCAL Based Standard LISP for the Apollo Domain)
@center[
by
M. L. Griss and R. Ottenheimer
Department of Computer Science
University of Utah
Salt Lake City, Utah 84112
@b(Preliminary Version)
Last Revision: @value(date)]
@end(titlebox)
@begin(abstract)
This report describes an interim implementation of Standard LISP for the
Apollo DOMAIN. This LISP is based upon the Standard LISP report, and a newly
developing Portable Standard LISP. This interim implementation is designed
to explore LISP implementations in PASCAL on the Apollo DOMAIN and similar
machines.
The system consists of a kernel, handcoded in PASCAL, with the rest of the
system written in LISP and compiled to PASCAL.
@End(abstract)
@begin(Researchcredit)
Work supported in part by the National Science Foundation
under Grant No. MCS80-07034.
@end(Researchcredit)
@end(titlepage)
@pageheading(Left "Apollo Pascal LISP",Center "@value(date)",
Right "@value(Page)"
)
@set(page=1)
@newpage
@section(Introduction)
In this preliminary report, we describe an implementation of Standard LISP
in PASCAL, PASLSP. Versions of PASLSP have been run on a number of
machines, ranging from an LSI-11 based TERAK to Apollo and PERQ. This report
concentrates on the Apollo DOMAIN implementation. This report is to be read in
conjunction with the Standard LISP report@cite(Marti79); we will
highlight the differences from the functions documented in the Standard
LISP, describe the implementation strategy, and discuss future work.
PASLSP is based on a series of small and medium sized LISP interpreters
that have been developed at the University of Utah to explore LISP
implementations in higher level languages. Each of these LISP systems
consists of a small kernel handcoded in some language, with the rest of the
system written in LISP and compiled to the target language. We have used
FORTRAN, PASCAL and assembly language as targets. The PASLSP series use
PASCAL for the kernel, and have a LISP to PASCAL compiler for the rest of
the system.
Recent work has concentrated on reducing the size of the hand-coded kernel,
and extending the compiler to handle systems level constructs. This has
resulted in a new Portable Standard LISP, PSL, running on the DEC-20 and
VAX-11/750@cite(Benson81,Griss81). An implementation of PSL for MC68000 is
underway. The PSL system is a modern, efficient LISP, written entirely in
itself; it uses an efficient LISP to machine code compiler to produce the
kernel, and then the rest of LISP is loaded. In the future we hope to
produce a complete PSL targeted at a higher level languages, such as
PASCAL, C or ADA, and this will replace the current PASLSP.
@subsection(History of PASLSP)
The system now called PASLSP was originally developed (by M. Griss and W.
Galway), as a small LISP like kernel to support a small computer algebra
system on an LSI-11 TERAK; this was to be used as an answer analysis module
within a CAI system@cite(Brandt81), written entirely in PASCAL. It was
decided to hand-code a very small kernel, and compile additional functions
written in LISP (LISP support functions, parser and
simplifier) to PASCAL,
using a modified Portable LISP compiler@cite(griss79). This version (call
it V0) did not even have user defined functions, since space on the TERAK
was at a premium.
About June 1981, PASLSP came to the attention of a number people evaluating
Apollo's and PERQ's, and it was suggested that we enhance V0 PASLSP for
this purpose. During the space of a few days, features taken
from the Standard LISP Report and newly developing
PSL files were added to
produce PASLSP-V1, running on a DEC-20 and Terak. This
was a fairly complete LISP (including Catch and Throw), but lacked a few
features (OPEN, CLOSE, RDS, WRS, PROG, GO, RETURN, COMPRESS, EXPLODE,
Vectors and Strings, etc.). V1 PASLSP was adapted to a PERQ, VAX and
Apollo by Paul Milazo of Schlumberge in the space of a few weeks (we did
not have a PERQ or Apollo at that time).
We subsequently obtained a PERQ and an Apollo, and recent work has been
aimed at producing an enhanced PASLSP for these machines, maintaining all
versions in one set of source files. The current system, PASLSP-V2, is
produced from a single PASCAL kernel and set of LISP support files; the
machine specific features are handled by a simple Source Code
Conditionalizer, changing the definition of certain constants and data
types. Only a few features of the Standard LISP report are missing,
and there are a number of additions.
@subsection(Acknowledgement)
We would like to acknowledge the contributions and support of
Eric Benson, Dick Brandt, Will Galway, and Paul Milazo.
@section(Features of PASLSP and relation to Standard LISP)
PASLSP as far as possible provides all the functions mentioned
in the attached Standard LISP Report (note the hand-written
comments added to this appendix); some of the functions are simply
stubs, so that a Standard LISP Test-file can be run without major
modification.
PASLSP-V2 does not implement the following features of Standard LISP:
@begin(enumeration,spread 0)
VECTORS (only a simple garbage collector is used).
String space is not garbage collected.
Integers are limited in size (INTs and FIXNUMs, no BIGNUMs).
FLOATING Point is not implemented.
IDs can not be REMOB'ed or INTERN'd.
Only 3 Input Channels and 2 Output Channels are available to OPEN,
RDS, WRS, and CLOSE. Thus file input statements can not be nested
very deeply in files.
Line, Page and Character counting (POSN, LPOSN, etc) are not implemented.
@end(enumeration)
PASLSP-V2 provides some extensions over Standard LISP:
@begin(enumerate,spread 0)
(CATCH form) and (THROW form) and the tagged versions: (TCATCH tag form)
and (TTHROW tag form) are used to implement error and errorset,
and higher level control functions.
Implicit PROGN in COND, and LAMBDA expressions.
(WHILE pred action-1 action-2 ... action-n).
(DSKIN 'filename)
@end(enumerate)
PASLSP-V2 has not been extensively tested, and there may still be a number
of bugs. While some effort has been spent in adjusting PASLSP to the Apollo
DOMAIN, it is clear that the various heap sizes are not yet optimal.
See appendix A for current list of functions, and appendix B for a copy
of the Standard LISP Report annotated to reflect the current status of
PASLSP.
@section(Using PASLSP on the Apollo DOMAIN)
Initializing the system from the floppy looks like this:
@begin(verbatim)
Create a directory (call it pl):
crd /pl
Mount the floppy:
mtvol f 1 /f
Copy the files of interest:
cpt /f/pascallisp /pl
The files copied will be: paslsp (executable file)
paslsp.ini (initialization file)
paslsp.tst (a test file)
@end(verbatim)
Run paslsp as you would any other file. If you
get an error it is most likely because the paslsp.ini file couldn't be found.
If this happens, locate paslsp.ini and try again. If it still hangs,
try calling Ralph Ottenheimer at (801) 355-0226 or M. Griss at (801) 581-6542.
Previously prepared files of LISP (e.g., library procedures)
can be input by
using the function "DSKIN". For Example,
@begin(verbatim)
(DSKIN 'Paslsptst)
(DSKIN '!/p!/foo!.sl)
@end
would load the paslsp test file. Paslsp test is adapted from an extensive
test of Standard LISP (avoiding features not yet implemented). This is a
good excercise, try it. [Note that the filename must be given as an ID,
and that special characters should be prefaced by an "escape character",
! . This is also the case for filenames in OPEN.]
Paslsp is "case-sensitive" with regard to identifiers. All of the
kernel procedures have upper-case identifiers associated with them. This
means that ordinarily the expression (dskin 'paslsptst) would not be
recognized since "dskin" is in lowercase. However, there is a global flag
!*RAISE which if true will convert all lower-case typin to upper-case.
This Apollo DOMAIN paslsp implementation sets !*RAISE to T as a default by
having (SETQ !*RAISE T) in the paslsp.ini file. You may put any special
initialization code you like at the end of paslsp.ini as indicated by the
comments in the file.
Toggling would be accomplished by typing the following lisp-expressions:
@begin(verbatim)
(SETQ !*RAISE T)
(SETQ !*RAISE NIL)
@end(verbatim)
Any Apollo DOMAIN filename (25 characters maximum)is allowable
as a paslsp filename.
Remember to prefix all special characters with an exclamation-mark: "!".
Special characters include all non-alphanumerics. For example: fof!.ksjd
!*RAISE goforit!! paslsp!.test .
@section(Implementation of PASLSP)
@subsection(Building PASLSP)
PASLSP is built in the following steps:
@u(Kernel files), PAS0.PRE, and trailer file (main program) PASN.PRE
are run through a filter program to produce PAS0.PAS and PASN.PAS,
tailored to the Apollo DOMAIN (appropriate Include files, Consts, etc).
This kernel provides the Basic I/O (Token reading and printing),
handcoded storage allocator and garbage collector, lowlevel arithmetic
primitives, lowlevel calls (via Case statement) from LISP to kernel, etc.
@u(Rest of LISP), currently files PAS1.RED, PAS2.RED and PAS3.RED are
compiled to PASCAL using a version of the Portable LISP Compiler
(PLC)@cite(griss79). During compilation, a Symbol Table file, PASn.SYM is
read in and written out. These files record (for "incremental" compilation)
the names and ID table locations of each ID encountered, so that the compiler
can refer to an ID by its offset in the ID table. LISP constants are also
recorded in the PASn.SYM files. PAS0.SYM is modified by hand as the kernel
is changed.
The compilation model used is that of a Register Machine: Arguments to LISP
functions are passed in registers (a PASCAL array), and the result returned
in Register 1. Space is allocated on a software stack (not the PASCAL
recursion stack), for any temporaries or save arguments required. Short
functions usually do not require any stack. The reason for this choice was
the existence of the PLC (targeted at comventional machines), and the fact
that inline access to the register array compiles quite well, while a
"PUSH/POP" stack would be much less efficient.
@u(Initialization).
After the PAS0.PAS,..PASN.PAS are produced,
the symbol table file (pas3.sym) is converted into a file
PASLSP.INI, which contains the names of all ID's, the LISP constants
used, and also ID's for all kernel functions that should be known to the
user LISP level. Also produced is a file, EXEC.PAS, that contains a case
statement associating each user callable kernel function with an integer.
The PAS0.PAS ... PASN.PAS and EXEC.PAS are compiled and linked into an
executable .RUN file. When this file is executed, PASLSP.INI is read in:
each id is read and stored in the appropriate location in the symbol-table,
the kernal function names have the associated Case index put into
a function cell, and the LISP s-expressions are READ in. Finally,
some s-expressions will be executed (with care, the user can add his own
expressions, including requests to (DSKIN 'library), etc.
@subsection(Internal data structures)
[To be written, see the PAS0.PRE files regarding data-types,
function calling conventions, etc]
itemref = RECORD
tag: integer; (* Small integer denoting the type. *)
info: integer; (* Either the item or a pointer to it *)
(* depending upon the type. *)
END;
pair = PACKED RECORD
prcar: itemref;
prcdr: itemref;
END;
ident = PACKED RECORD (* identifier *)
idname: stringp;
val: itemref; (* value *)
plist: itemref; (* property list *)
funcell: itemref; (* function cell *)
idhlink: id_ptr; (* hash link *)
END;
@subsection(Adding user functions to the kernel)
[To be written, describe format of EXEC.PAS, PASLSP.INI and major functions
that are needed to add new Arithmetic extensions,
or more complex operations].
@Section(Future work on PASLSP)
PASLSP V2 is based on a fairly old model of a portable LISP, and
has been used mainly to explore the capbilities of PASCAL as a
target language. In particular, V2 PASCAL is not yet powerful enough to
run the PLC compiler itself;
instead, the PLC is run on our PSL system on the DEC-20. In order for the
full benefits of PASLSP (or PSL) to be realized, the user should be able to
compile his own LISP modules into PASCAL and link them with the kernel.
In order to make the system even more adapatable, we would like to write
even less of the kernel in PASCAL by hand. This goal has lead us to the
development of PSL.
@subsection(Goals of the Utah PSL Project)
The goal of the PSL project is to produce an efficient and transportable
Standard LISP system that may be used to:
@begin(enumeration)
Experimentally explore
a variety of LISP implementation issues (storage management, binding,
environments, etc.).
Effectively support the REDUCE computer algebra system@cite(hearn73)
on a number of machines.
Provide the same, uniform, modern LISP programming environment on all of
the machines that we use (DEC-20, VAX/750, PDP-11/45, PERQ, and Apollo), of
the power and complexity of UCI-LISP, FranzLISP or MACLISP, with some
extensions and enhancements derived from LISP Machine LISP or CommonLISP.
@end(enumeration)
The approach we have been using is to write the @b(entire) LISP system in
Standard LISP (with extensions for dealing with
machine words and operations), and to bootstrap it to the desired target
machine
in two steps:
@begin(enumeration)
Cross compile an appropriate kernel to the assembly language of the
target machine;
Once the kernel is running, use a resident compiler and loader, or
fast-loader, to build the rest of the system.
@end(enumeration)
The PASLSP system, and other early implementations, have the problem that
the implementation language (PASCAL) is a distinct language from LISP, so
that communication between "system" code and "LISP" code was difficult. We
have incorporated all of the good features of the earlier work into a new
efficient LISP-like systems language, SYSLISP, recoded all useful modules
into SYSLISP, and proceeded from there. SYSLISP currently produces
targeted assembly code; earlier verisions were targeted at high-level
languages such as FORTRAN, PASCAL, C or ADA. The goal is a portability
strategy that leads to an efficient enough system for a production quality,
yet portable system. We currently think of the extensions to Standard LISP
as having two levels: the SYSLISP level, dealing with words and bytes and
machine operations, enabling us to write essentially all of the kernel in
Standard LISP; and, the STDLISP level, incorporating all of the features
that make Standard LISP into a modern LISP, PSL. SYSLISP and LISP are both
compiled by an improved version of the Portable Standard LISP Compiler. The
SYSLISP mode of the PSL compiler does compile-time folding of constants,
and more comprehensive register allocation than the previous LISP-only
version of the compiler.
The current state of PSL is fully described in an "overview" document
obtainable from the authors @cite(griss81e). Currently PSL runs on the
DEC-20 under TOPS-20, and on the DEC VAX-11/750 under Unix. We are now
concentrating on the MC68000 PSL for the Apollo. All of the code-generators
and assembler support is complete, and a number of large files have been
compiled from LISP to assembly code, and correctly assembled and executed
on the Apollo, testing basic I/O and arithmetic. We are now in the process
of writing the PSL support code (small functions in LAP), and testing that
various decisions about register and memory usage are correct. Based on the
development history on the VAX, we are about 1-2 months away from a
preliminary PSL on the Apollo.
@section(References)
@Bibliography