Utah Symbolic Computation Group December 1981
Operating Note 60
A PASCAL Based Standard LISP for the Wicat 100
A PASCAL Based Standard LISP for the Wicat 100
A PASCAL Based Standard LISP for the Wicat 100
by
M. L. Griss and R. Ottenheimer
Department of Computer Science
University of Utah
Salt Lake City, Utah 84112
Preliminary Version
Preliminary Version
Preliminary Version
Last Revision: 1 March 1982
ABSTRACT
ABSTRACT
ABSTRACT
This report describes an interim implementation of Standard LISP
for the Wicat 100. 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 Wicat 100 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.
Work supported in part by the National Science Foundation under
Grant No. MCS80-07034.
Wicat Pascal LISP 1 March 1982 1
1. Introduction
1. Introduction
1. 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 Wicat 100
implementation. This report is to be read in conjunction with the
Standard LISP report [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 [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.
1.1. History of PASLSP
1.1. History of PASLSP
1.1. 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 [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 [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
Wicat Pascal LISP 1 March 1982 2
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, Apollo and a Wicat, 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.
1.2. Acknowledgement
1.2. Acknowledgement
1.2. Acknowledgement
We would like to acknowledge the contributions and support of
Eric Benson, Dick Brandt, Will Galway, and Paul Milazo.
2. Features of PASLSP and relation to Standard LISP
2. Features of PASLSP and relation to Standard LISP
2. 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:
a. VECTORS (only a simple garbage collector is used).
b. Strings are implemented as identifiers (not garbage
collected).
c. Integers are limited in size (INTs and FIXNUMs, no
BIGNUMs).
d. FLOATING Point is not implemented.
e. IDs can not be REMOB'ed or INTERN'd.
f. 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
Wicat Pascal LISP 1 March 1982 3
files.
g. Line, Page and Character counting (POSN, LPOSN, etc)
are not implemented.
PASLSP-V2 provides some extensions over Standard LISP:
a. (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.
b. Implicit PROGN in COND, and LAMBDA expressions.
c. (WHILE pred action-1 action-2 ... action-n).
d. (DSKIN 'filename) or (DSKIN "filename")
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 Wicat, 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.
3. Using PASLSP on the Wicat 100
3. Using PASLSP on the Wicat 100
3. Using PASLSP on the Wicat 100
Initializing the system from the floppy looks like this:
Create a directory (call it pl):
Mount the floppy:
Copy the files of interest:
The files copied will be: paslsp (executable file)
paslsp.ini (initialization file)
paslsp.tst (a test file)
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,
(DSKIN 'Paslsp!.tst) or (DSKIN "Paslsp.tst")
Wicat Pascal LISP 1 March 1982 4
would load the paslsp test file. The 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 if
the filename is given as an ID, that special characters should be
prefaced by an "escape character", ! . This is also the case for
filenames in OPEN. Alternately the string form may be used, in
that case special characters need not be escaped.]
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
'paslsp!.tst) 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 Wicat 100
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:
(ON !*RAISE) equivalent to (SETQ !*RAISE T)
(OFF !*RAISE) equivalent to (SETQ !*RAISE NIL)
Any Wicat 100 filename (60 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: !*RAISE goforit!! paslsp!.test
!/login!/smith!/foo!.sl .
If the global !*ECHO is not NIL (default is NIL), input will be
echoed to the selected output channel. It is sometimes
convienient to put:
(SETQ !*ECHO T)
at the beginning of a file to be read by DSKIN, and:
(SETQ !*ECHO NIL)
at the end. This will echo the file to the screen (or to a file)
as it is read.
Certain low level errors do not display any explanatory message
Wicat Pascal LISP 1 March 1982 5
but instead display a numeric code (such as *** # 2), below is a
summary of these codes and their meanings:
(* error codes. corresponding to tag = errtag. *)
noprspace = 1; (* no more "pair space"--can't cons. *)
notpair = 2; (* a pair operation attempted on non-pair.*)
noidspace = 3; (* no more free identifiers *)
undefined = 4; (* used to mark undefined function cells *)
noint = 5; (* no free integer space after gc. *)
notid = 6; (* id was expected *)
4. Implementation of PASLSP
4. Implementation of PASLSP
4. Implementation of PASLSP
4.1. Building PASLSP
4.1. Building PASLSP
4.1. Building PASLSP
PASLSP is built in the following steps:
______ _____
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 Wicat 100 (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.
____ __ ____
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) [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.
Wicat Pascal LISP 1 March 1982 6
______________
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
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 kernel 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.
4.2. Internal data structures
4.2. Internal data structures
4.2. Internal data structures
The data spaces (or heaps) in PASLSP are divided into 4
sections: the pair space, id space (the oblist), string space and
large integer (fixnum) space. These are all arrays of objects of
the appropriate type (see declarations below). The system is
fully tagged, that is, every LISP item has associated with it a
tag field which denotes the type of the item and an 'info' field
which either points to the item in an array (in the case of
pairs, identifiers and fixnums), or contains the information
itself (in the case of inums, character codes and error
conditions). The info field of a code pointer contains the index
into a case staement (see procedure 'execute') by means of which
any LISP callable function may be invoked.
itemref = RECORD
tag: integer; (* Small integer denoting type. *)
info: integer; (* 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;
Wicat Pascal LISP 1 March 1982 7
4.3. Adding user functions to the kernel
4.3. Adding user functions to the kernel
4.3. Adding user functions to the kernel
It is fairly easy to add handcoded Pascal functions to the
kernel so that they can be called from LISP. For example,
consider adding the function SQR(x), that squares its integer
argument. Since SQR is already the name of an existing PASCAL
function, we will call it "Xsqr" in PASCAL, and SQR in LISP.
The function Xsqr has to take its argument from R[1], check
that it is an integer, square the information part, and retag as
integer:
PROCEDURE Xsqr;
VAR i1 : longint;
BEGIN
int_val(r[1], i1); (* Test type and extract Info *)
mkint(i1 * i1, 1) (* Square, retag, and put in R[1] *)
END;
Now procedure Xsqr needs be to be installed into the EXECUTE
table, so that it can be found as the N'th code item. The number
of defined procedures will have to be increased by 1 in the 3'rd
line of procedure EXECUTE, (currently 201 defined), and an
additional case added:
202: Xsqr;
Note also that this table gives the Internal names of each
available procedure, should one of these be required in your
handcoded procedure. Finally, the Identifier SQR needs to be
associated with case 202 in PASLSP.INI. Note that PASLAP.INI has
3 tables of objects, each prefixed by a count and terminated by a
0. The first is the Random ID table, consisting of special ID's
used for messages etc. The second block is for S-expression
constants, which get loaded into the base of the stack as
Globals. The next batch are the names of LISP callable functions
in the order corresponding to the EXECUTE procedure. Simply
modify the count form 201 to 202 (or whatever), and add SQR at
the end, just before the 0.
In general, look for a sample procedure in the kernel if
possible, or in the compiled part (although these are hard to
follow), and adapt to the specific needs. Note the use of the
ALLOC(n) and DEALLOC(n) procedures to allocate a block of
temporaries on the stack. These should be used, rather than
Wicat Pascal LISP 1 March 1982 8
PASCAL VAR's, since the garbage collector may need to trace from
one of the saved objects.
5. Future work on PASLSP
5. Future work on PASLSP
5. 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.
5.1. Goals of the Utah PSL Project
5.1. Goals of the Utah PSL Project
5.1. 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:
a. Experimentally explore a variety of LISP
implementation issues (storage management, binding,
environments, etc.).
b. Effectively support the REDUCE computer algebra
system [hearn73] on a number of machines.
c. Provide the same, uniform, modern LISP programming
environment on all of the machines that we use
(DEC-20, VAX/750, PDP-11/45, PERQ, Wicat 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.
entire
entire
The approach we have been using is to write the entire LISP
system in PSL (using LISP extensions for dealing with machine
words and operations), and to bootstrap it to the desired target
machine in two steps:
a. Cross compile an appropriate kernel to the assembly
language of the target machine;
b. Once the kernel is running, use a resident compiler
and loader, or fast-loader, to build the rest of the
system.
Wicat Pascal LISP 1 March 1982 9
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 LISP level, incorporating all
of the features that make PSL into a modern LISP. Both modes of
PSL are 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 [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.
6. References
6. References
6. References
[1] Benson, E. and Griss, M. L.
_______ _ ________ ____ _____ _______ ______________
SYSLISP: A portable LISP based systems implementation
________
language.
Utah Symbolic Computation Group, Report UCP-81, University
of Utah, February, 1981.
[2] Brandt, R. C. and Knapp, B. H.
The University of Utah Video Computer Authoring System.
___________ __ ___ _________ __ ________ __________
In Proceedings of the Symposium on Learning Technology,
pages 18-23. Orlando, Florida, Feb, 1981.
Wicat Pascal LISP 1 March 1982 10
[3] Griss, M. L.; Kessler, R. R.; and Maguire, G. Q. Jr.
TLISP - A Portable LISP Implemented in P-code.
___________ __ _______ __
In Proceedings of EUROSAM 79, pages 490-502. ACM, June,
1979.
[4] Griss, M. L. and Morrison, B.
___ ________ ________ ____ _____ ______
The Portable Standard LISP Users Manual.
Utah Symbolic Computation Group, TR-10, University of
Utah, March, 1981.
[5] Griss, M. L.
________ ________ ____ _ _____ ________
Portable Standard LISP: A Brief Overview.
Utah Symbolic Computation Group, Operating Note 58,
University of Utah, October, 1981.
[6] Hearn, A. C.
______ _ _____ ______
REDUCE 2 Users Manual.
Utah Symbolic Computation Group UCP-19, University of Utah,
1973.
[7] Marti, J. B., et al.
Standard LISP Report.
_______ _______
SIGPLAN Notices 14(10):48-68, October, 1979.
APPENDIX A: A List of Current PASLSP Functions and Globals
APPENDIX A: A List of Current PASLSP Functions and Globals
APPENDIX A: A List of Current PASLSP Functions and Globals
____ ________ __________ ___ ________ ____ ______
Lisp Callable Functions, see Standard LISP Report
!*FIRST!-PROCEDURE The top loop LISP reader
ABS
ADD1
AND
APPEND
APPLY
APPLY1 (APPLY f (LIST u))
ASSOC
ATOM
ATSOC
CAAAAR
CAAADR
CAAAR
CAADAR
CAADDR
CAADR
CAAR
CADAAR
CADADR
CADAR
CADDAR
CADDDR
Wicat Pascal LISP 1 March 1982 11
CADDR
CADR
CAR
CATCH
CDAAAR
CDAADR
CDAAR
CDADAR
CDADDR
CDADR
CDAR
CDDAAR
CDDADR
CDDAR
CDDDAR
CDDDDR
CDDDR
CDDR
CDR
CLOSE
CODEP
COMPRESS
COND
CONS
CONSTANTP
DE
DEFLIST
DELATQ (DELATQ 'X alist) deletes (X . any) from alist
DELETE
DELQ Efficient DELETE (using EQ)
DF
DIFFERENCE
DIGIT
DIVIDE
DM
DN
DSKIN (DSKIN file-id)
EOFP (EOFP channel)
EQ
EQCAR
EQN
EQUAL
ERROR
ERRORSET
ERRPRT Prints message with *'s
EVAL
EVLAM Evaluates a LAMBDA expression
EVLIS
EXPAND
EXPLODE
EXPT
FASTSTAT Prints RECLAIM message
Wicat Pascal LISP 1 March 1982 12
FIX
FIXP
FLAG
FLAG1 (FLAG (LIST x) y)
FLAGP
FLOAT
FLOATP
FLUID
FLUIDP
FUNCELL Accesses function cell
FUNCTION
GENSYM
GET
GETD
GETV
GLOBAL
GLOBALP
GO
GREATERP
IDP
INTERN
LBIND1 Binds a single ID in LAMBDA
LBINDN
LENGTH
LESSP
LIST2 For efficent LIST compilation
LIST3
LIST4
LIST5
LITER
MAP
MAPC
MAPCAN
MAPCAR
MAPCON
MAPLIST
MAX
MAX2
MEMBER
MEMQ
MIN
MIN2
MINUS
MINUSP
MKVECT
MSGPRT
NCONC
NCONS
NOT
NULL
NUMBERP
ONEP
Wicat Pascal LISP 1 March 1982 13
OPEN
OR
ORDERP
P!.N Evaluates Implicit PROGNs
PAIR
PAIRP
PBIND1 PROG binding
PBINDN
PLIST Access full property list
PLUS
PLUS2
PRIN1
PRIN2
PRIN2T
PRIN2TL
PRINC
PRINT
PROG
PROG2
PROGG0131
PROGN
PUT
PUTC
PUTD
PUTL
PUTV
QUOTIENT
RDEVPR A read-eval-print loop
RDS
RDTOK
READ
READCH
RECLAIM
REMAINDER
REMD
REMFLAG
REMFLAG1
REMOB
REMPROP
RETURN
REV
REVERSE
REVX
RLIST
RPLACA
RPLACD
SASSOC
SET
SETFUNCELL
SETPLIST
SETVALUE
STRINGP Equivalent to IDP
Wicat Pascal LISP 1 March 1982 14
SUB1
SUBLIS
SUBST
TCATCH
TERPRI
THROW
TIMES
TIMES2
TOKEN
TTHROW
UNBIND1
UNBINDN
UNBINDTO
UNFLUID
UPBV
VALUE
VECTORP
WHILE
WRS
WRTOK
XAPPLY
XCONS
ZEROP
___________ _______
Interesting Globals
!*RAISE Raise lower case typing to upper case if not NIL
!*ECHO Selected input to selected output if not NIL.
BSTK!* Holds old values of rebound IDS
EMSG!* Error message in most recent call on ERROR
ENUM!* Error number in most recent call on ERROR.
INITFORM!* First Expression EVAL'ed
THROWING!* Indicates if throwing
THROWTAG!* Indicates TAG in TTHROW
TOK!* Holds last token scanned
TOKTYPE Indicates type of token scanned:
1: integer
2: id
3: character
Wicat Pascal LISP 1 March 1982 i
Table of Contents
Table of Contents
Table of Contents
1. Introduction 1
1.1. History of PASLSP 1
1.2. Acknowledgement 2
2. Features of PASLSP and relation to Standard LISP 2
3. Using PASLSP on the Wicat 100 3
4. Implementation of PASLSP 5
4.1. Building PASLSP 5
4.2. Internal data structures 6
4.3. Adding user functions to the kernel 7
5. Future work on PASLSP 8
5.1. Goals of the Utah PSL Project 8
6. References 9
APPENDIX A: A List of Current PASLSP Functions and Globals 10