Artifact 125b5cc6b717d81fb5afc39108aa9d5477d5b1f8b38010e2be0459910245d969:
- File
perq-pascal-lisp-project/wicat-paslsp.lpt
— part of check-in
[eb17ceb7f6]
at
2020-04-21 19:40:01
on branch master
— Add Reduce 3.0 to the historical section of the archive, and some more
files relating to version sof PSL from the early 1980s. Thanks are due to
Paul McJones and Nelson Beebe for these, as well as to all the original
authors.git-svn-id: https://svn.code.sf.net/p/reduce-algebra/code/historical@5328 2bfe0521-f11c-4a00-b80e-6202646ff360 (user: arthurcnorman@users.sourceforge.net, size: 27726) [annotate] [blame] [check-ins using] [more...]
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