Aucbvax.4907 fa.editor-p utzoo!decvax!ucbvax!editor-people Mon Nov 2 10:32:06 1981 Re: hairy data structures in LISP >From Griss@UTAH-20 Mon Nov 2 10:16:35 1981 Re a question about Standard LISP: PSL Interest Group A number of people have expressed interest in the progress of the Portable Standard LISP (PSL) system being developed at Utah. I have created a mailing list ([Utah-20]PIG.Mailer) for this "Psl Interest Group", to which I will send periodic messages. I will briefly summarize the goal and status of the PSL work, and will shortly have a complete progress report which can be FTP'ed or USMail'ed. Please send a message if you wish to be removed from this mailing LIST, wish other names to be added, and whether you want a USMail copy of the progress report. Martin L. Griss, CS Dept., 3160 MEB, University of Utah, Salt Lake City, Utah 84112. (801)-581-6542 -------------------------------------------------------------------------- Goals and Status of PSL PSL is an Extended Standard LISP, written entirely in itself, compiled with the Griss and Hearn Portable LISP Compiler (with machine oriented extensions). It is to be used as a transportable replacement for the variety of Standard LISP Interpreters that we use to support the REDUCE Algebra system, and other LISP based tools. The extensions are to make it a more efficient and pleasant LISP for our programming activities, and to maintain a high degree of compatability with Standard LISP so that existing software can run without (much) change. By writing the entire LISP in LISP, we are able to more rapidly experiment with changes to produce a range of LISP-like systems for other purposes. We have a short-term plan to fully implement PSL on DEC-20 (possibly with Extended Addressing option), VAX-750 and 68000 based personal machine with integrated bit-map display, The LISP extensions to Standard LISP include: String Operations; User definable Special I/O Streams, Read-Tables, Read-Macros; Break Loop, Continuable and Non-continuable Errors; Hooks for Multi-Package System; Resident Window Package and EMACS-like Editor interface; Catch and Throw used to Implement Error/Errorset, etc; Bignum's interfaced at lowest level; Resident Compiler with LAP and FastLoader; No FAST-LINKs - all calls go via a dispatch table; PSL is written in LISP and a systems level, SYSLISP, both compiled by an improved version of the Portable LISP Compiler. SYSLISP deals with Words and Bytes, Machine Addresses, Bit-Fields, Allocation of Memory blocks; the SYSLISP mode of the Compiler does efficient compile-time folding of constants, and more compehensive register allocation. A complete PSL runs on our DEC-20, and is comparable in speed to the existing LISP 1.6 based Standard LISP Interpreter (speed somewhat faster than SlowLinks, and slightly bigger kernel); it currently supports a new version of RLISP (our Algol-like surface language, using a table driven Pratt parser); a resident LISP/SYSLISP compiler with LAP (no Fast Loader yet), tagged 36-bit objects rather than 18 bit (for easy of movement to extended addressing and VAX or 68000); compacting garbage collector; the Emacs like screen editor and Window system are operational, but have not yet been fully integrated into system (i.e. Errors should go to a BREAK window, user should be able to switch back and forth from window to window using the editor, edit and resubmit pieces of LISP and RLISP, etc.) We have a JSYS interface, native mode I/O (no PA-1050!), and quite usable interrupt interface. Some peices of the REDUCE algerbra system have been run compiled, and the rest intepreted. The current system is still being built by cross-compiling the kernel modules written in RLISP/SYSLISP to DEC-20 FAIL, using a SYSLISP compiler running on our existing LISP 1.6 based Standard LISP. The FAIL modules are linked together to produce the kernel system, and additional modules are then loaded as LAP or recompiled with the resident compiler. We expect very shortly to be using the resident compiler to do this cross-compilation, taking advantage of the newer features to produce better code. As soon as a Fast Loader is operational, the kernel will be made much smaller, and much more of the system will be Fast Loaded together. An earlier version of PSL also ran in FORTRAN, using a LISP->FORTRAN compiler; this is currently lagging behind, now that the machine coded version of PSL is quite stable and easy to use with the resident compiler. This FORTRAN version will be brought up to date later this summer, though it can not provide all the features of the machine code version. It will be used to provide a more efficient version of REDUCE on the CRAY-1 (now running on the previous P-code Standard LISP done by this group), and as a reasonable portability base. We have also produced a LISP->PASCAL compiler, and LISP kernel written in PASCAL; this has been used to run a very small LISP on a TERAK, under UCSD PASCAL, supporting a small algebra system for CAI purposes. This kernel and sources compiled has recently been upgraded into an almost complete Standard LISP (including some PSL extensions, such as Catch and Throw), to be used to rapidly produce a LISP for machines such as Apollo and PERQ. This PASCAL-LISP system is also a model for future ADA implementations. ----------------------------------------------------------------------- Future Plans We have just taken delivery of a VAX/750 and hope shortly to obtain an Apollo (Motorola 68000 based personal computer with bit-map display, network and virtual memory). Once all PSL building can be accomplished on the DEC-20 PSL, rather than the older LISP 1.6 based system we will: a) Begin the VAX implementation, and plan the 68000 implementation; b) Implement the Package (Multi-name space system); c) Prepare an initial DEC-20 release for experimentation; d) Perhaps do the Extended DEC-20 version (using some of Rutger's ELISP experiments as a base); Once the VAX version is quite stable (we hope about 6 months), we will: a) Complete the 68000 implementation; b) Prepare the "Portable" Release - we still have to decide if this can be done economically in a full-bootstrap, using the FORTRAN system as base, or whether only cross-compilation from an existing PSL is reasonable. ________________________________________________________________________ Short PSL bibliography of papers that will be available on request. a) Paper on SYSLISP approach to implementing PSL - 14 pages, written about January, slight editing February, March, for conference on LISP and Algebra systems. Describes SYSLISP as a BCPL-like language, couched in LISP form, for LISP implementations, and as an Efficient "mode" of LISP (sort of "beyond" fast-arithmetic compilers). Also summarized some of goals of PSL project: All code in LISP or SYSLISP; Studies of EFFICIENT retargetable compilation methods; Base for experiments with new LISP-like languages. b) Paper on PSL "tools", mentioning some of what we have or hope to have; 14 Pages, written about March, for ARPA Lisp meeting at SRI. A number of the tools now exist, and have been run on PSL, or tested on older Standard LISP (these are tools for LISP programmers, language experimenters, and Algebra users). Most notable are the EMODE customisable screen editor for use as general purpose interface, META/LISP-META/REDUCE Translator writing system, and some source control tools c) Progress Report: This is a moving target, meant to describe what we have, and how it runs; system still progressing faster than I can report on it; want to mail this to NSF sponsor. 19 pages, written end of May, continuously being updated, so may be a bit ragged, or self-contradictory. ________________________________________________________________________ PSL Interest Group 28 October 1981 Since my last message early in the summer, we have made significant progress on the development of PSL on the DEC-20, and on related projects. This note will summarize the last few months activities. I now have a more detailed progress report which can be FTP'ed or USMail'ed. Please send a message if you wish to be removed from this mailing LIST, wish other names to be added, and whether you want a USMail copy of the progress report. Martin L. Griss, CS Dept., 3160 MEB, University of Utah, Salt Lake City, Utah 84112. (801)-581-6542 -------------------------------------------------------------------------- DEC-20 PSL: Around mid-summer, version 1 of PSL (V1) on the DEC-20 became stable and efficient enough to be used in place of the LISP 1.6 based Standard LISP (currently distributed as the DEC-20 Standard LISP supporting REDUCE). This PSL system was a bit faster than the Slow-link debugging mode of LISP 1.6. PSL has a number of features that make it more desirable than the previous 1.6 based system (BREAK interrupt key, full JSYS I/O, uniform channel driven I/O, overlapping window system and screen editor, continuable errors, resident SYSLISP compiler, entire source compiled from LISP and SYSLISP, all functions dynamically alterable and traceable). This PSL is somewhat larger than the LISP 1.6 based system (since it uses tagged full-word rather than half-word pointers, and compiled rather than hand-coded kernel). Not all useful modules have yet been fully implemented (such as Fast Loader). We were able to demonstrate a full PSL, with Emacs-like editor, window package, and preliminary REDUCE algebraic structure editor at SYMSAC 81, held here in Salt Lake City, August 5-7, 1981. The V1 system is built by cross-compiling the kernel modules written in RLISP/SYSLISP to DEC-20 FAIL, using a SYSLISP compiler running on our existing LISP 1.6 based Standard LISP. The FAIL modules are linked together to produce the kernel system, and additional modules are then loaded as LAP or recompiled with the resident compiler. After the SYMSAC demonstration, major effort went into a cleanup of the sources in preparation to use the resident compiler V1 to do the cross-compilation, taking advantage of the newer PSL/SYSLISP features to produce better code. A number of functions were improved, or totally rewritten, and many clumsy constructs removed. SYSLISP was extended with better declarations for EXTERNAL and INTERNAL word and byte arrays and variables, with initialization of constants, etc. The functions were regrouped into modules in a more meaningful fashion (taking advantage of the full DEC-20 file names that V1 PSL now permits). A number of constructs were changed in preparation for the VAX and 68000 version, and the code more carefully parameterized. Some interface constructs in SYSLISP were renamed (e.g., ' now means the same thing in LISP and SYSLISP, IDLOC and LISPVAR macros were added to improve access to LISP variables from SYSLISP, etc.), and new features added to the new Pratt parser version of RLISP (such as [] for vector indexing and other left and right hand operators) to make the SYSLISP code more readable and closer to the RLISP level. The new DEC-20 version of SYSLISP was targeted at MIDAS, and the bootstrap of V2 PSL, using the V1 system completed. One major improvement was to completely remove the initialization files that were read in by V1; rather, all ID strings are compiled into their locations in the heap, and random executable LISP expressions gathered into an "init" procedure which is compiled, and then is run by the first procedure. This means that bare V2 PSL is simply assembled, linked and executed, and it reaches the LISP level with minor delay. The kernel PSL is now smaller and faster than before (almost twice as fast). V2 PSL has just successfully rebuilt itself, and we are now ready to archive the V1 PSL; almost all the existing modules (such as the EMODE screen editor, resident LISP/SYSLISP compiler) and some new modules (Top-Loop with history and Lisp-DDT features) are now operational. There are a few minor pieces to add. V2 is now at least 35-40% faster than V1, so that it is significantly faster than the LISP 1.6 based Standard LISP in Slow-link mode (we use Slow-links for all experimental code, so that TRACE etc can be used); we still are not as fast as the Fast-Link mode. The SYSLISP level now generates code of comparable quality to PASCAL or FORTRAN, so that a few simple declarations can result in dramatic speed up of simple routines such as Factorial, etc. VAX and 68000 systems: We now have a VAX-750 and two Apollo DOMAIN systems. We have also just received a WICAT-100 system on loan (another fairly powerful 68000 based system). In the last few weeks, serious work has started on the VAX LAP and SYSLISP compiler, using the PSL-20 V2 sources and PSL to MIDAS compiler c-macros and tables as a guide. The LAP to Unix assembler works, and has been used to produce a few small executable procedures to test our register model on the VAX. Preliminary VAX compiler tables work, and a few small procedures have been compiled from RLISP. Another few weeks should result in a fair amount of executing code. The VAX is connected to the DEC-20 by a shared disk so that rapid transfer of files is now painless. The Apollo's have only been stable for a few weeks, and we are still engaged in getting basic utility software up (an FTP to the DEC-20, a BCPL based DEC-20 68000 cross assembler, etc). We have obtained a copy of a previous attempt (by Arthur Norman, Cambridge) at emitting 68000 code using the Portable LISP compiler, and have this running on PSL. It will be used as a guide to writing the initial macros, but will soon be replaced by suitably modifying the VAX programs based on the new PSL/SYSLISP compiler. PASCAL systems: We have also produced a LISP->PASCAL compiler, and LISP kernel written in PASCAL; this has been used to run a very small LISP on a TERAK, under UCSD PASCAL, supporting a small algebra system for CAI purposes. This kernel and sources compiled has recently been upgraded into an almost complete Standard LISP (including some PSL extensions, such as Catch and Throw), to be used to rapidly produce a LISP for machines such as Apollo and PERQ. It has in fact been run on our Apollo's, and on a PERQ being used by another group in the department. Future Work: We are now going full bore at the VAX version, and will track a few weeks behind on the Apollo. We expect to find some problems with the sources, as the code develops, but so far no major problems are expected. We will change the garbage collector, to either use a bit-table, or more likely go to a copying 2 space model. The Apollo currently permits a 5Mb address space, and the next OS release (in a few weeks) should give us 9Mb. Now that V2 PSL is reasonably stable, we can in parallel implement a few of the missing features, notably the package system. Sample SYSLISP: The following is a small piece of the file OBLIST.RED, defining some parts of INTERN. We are currently changing this to introduce a preliminary package system. The example uses the RLISP based syntax. Remember that in SYSLISP mode, "generic +" becomes WPLUS2, etc. ----------------------------------------------------------------------- % OBLIST.RED - Intern, RemOb and friends % Author: Eric Benson, Computer Science Dept. % CopyString and CopyStringToFrom are found in COPIERS.RED on SysLisp; internal WConst MaxObArray = 8209, % first prime above 8192 DeletedSlotValue = -1, EmptySlotValue = 0; internal WArray HashTable[MaxObArray]; % ObArray is a linearly allocated hash table containing ID numbers of entries % maintained as a circular buffer. It is referenced only via these macros % because we may decide to change to some other representation. CompileTime << OCCUPIEDSLOT EMPTYSLOT :="X;" HASHTABLE[I]; U DELETEDSLOT HASHTABLE[I] OBARRAY SYSLSP PUTOBARRAY(I, PROCEDURE U; EQ EMPTYSLOTVALUE; ASSIGN!-OP, DELETEDSLOTVALUE; SMACRO I; PUTOBARRAY); PUT('OBARRAY, X);> 0; syslsp smacro procedure NextSlot H; if H eq MaxObArray then 0 else H + 1; % StringEqual found in EQUAL.RED syslsp smacro procedure EqualObArrayEntry(ObArrayIndex, S); StringEqual(SymNam ObArray ObArrayIndex, S); >>; syslsp procedure AddToObList U; % % U is a String, which is NOT copied if it is not found on the ObList % The interned ID with U as print name is returned % begin scalar V, W, X, Y; U := StrInf U; Y := StrLen U; if Y >; end; syslsp procedure LookupOrAddToObList U; % % U is a String, which IS copied if it is not found on the ObList % The interned ID with U as print name is returned % begin scalar V, W, X, Y; U := StrInf U; Y := StrLen U; if Y >; end; syslsp procedure NewID S; %. Allocate un-interned ID with print name S InitNewID(GtID(), S); % Doesn't copy S syslsp procedure InitNewID(U, V); %. Initialize cells of an ID << SETPROP(U, MAKEUNBOUND :="MkID" U SYMNAM U; MAKEFUNBOUND NIL);>>; %syslsp procedure HashFunction S; %. Compute hash function of string %begin scalar Len, HashVal; % Fold together a bunch of bits % HashVal := 0; % from the first 28 characters of the % Len := StrLen S; % string. % if Len > 28 then Len := 28; % for I := 0 step 1 until Len do % HashVal := LXOR(HashVal, LSH(StrByt(S, I), 28 - I)); % return MOD(HashVal, MaxObArray); %end; lap '((!*entry HashFunction expr 1) %. Compute hash function of string (hrre r4 0 r1) % pick up length - 1 (caile r4 28) % only use the first 28 chars (movei r4 28) (movei r5 28) % r5 := shift value (aos 0 r1) % move to first char of string (hrli r1 8#440700) % make a byte pointer (setz t1 0) % clear result register Loop (ildb r3 r1) % load next char (lsh r3 0 r5) % shift left by 28 - I (xor t1 r3) % stuff into result register (sos 0 r5) % decrement shift value (sojge r3 Loop) % decrement count, quit if <= ID OR STRING FATALERROR GOTO % 0 EMPTYSLOT :="NextSlot" ; A REMOB, INOBLIST H EQUALOBARRAYENTRY(WALKOBARRAY, NOT U 0) DELETEDSLOT ELSE OBARRAY DSLOT, STRING OR SCALAR RETURN AN SYMNAM REMAINDER R1 (MOVM SYSLSP AND LOOP: LOOP; UNINTERNED POINTER MAXOBARRAY)) NONIDERROR(U, REMOVE END; %. RETURNS NEQ T1 ST PROCEDURE U) WALKOBARRAY (POPJ TO BEGIN U; LOOKUPORADDTOOBLIST TYPEERROR(U, EQ ADDTOOBLIST WALKOBARRAY; INTERN, OBLIST THEN V; OBLIST OVERFLOW (WCONST IDINF INTERN H, REMOB ); STRING. DSLOT REMOB); V := IDINF U; IF V < 128 THEN RETURN TYPEERROR(U, ADD (IDIVI IDP STRINGP ID IF "NON-CHAR"); V := SYMNAM V; RETURN << IF OCCUPIEDSLOT(V := INOBLIST V) THEN OBARRAY V := DELETEDSLOTVALUE; U IS FROM T2) -1>> end; internal WString GenSymPName = "G0000"; syslsp procedure GenSym(); %. GENerate unique, uninterned SYMbol GenSym1 4; syslsp procedure GenSym1 N; %. Auxiliary function for GenSym begin scalar Ch; return if N > 0 then if (Ch := StrByt(GenSymPName, N)) > else << - N) :="char" STRBYT(GENSYMPNAME, 1) !0; GENSYM1(N>> else << + :="StrByt(GenSymPName," STRBYT(GENSYMPNAME, 0) 1; GENSYM()>>; end; syslsp procedure MapObl F; %. Apply F to every interned ID << I); OCCUPIEDSLOT 1 :="0" FOR I LIST OBARRAY DO 127 APPLY(F, THEN UNTIL I) IF MKID MAXOBARRAY STEP>>; syslsp procedure InitObList(); begin scalar Tmp; Tmp := NextSymbol - 1; for I := 128 step 1 until Tmp do ObArray InObList SymNam I := I; end; off SysLisp; LoadTime InitObList(); ---------------------------------------------------------------------------- ------- ----------------------------------------------------------------- gopher://quux.org/ conversion by John Goerzen of http://communication.ucsd.edu/A-News/ This Usenet Oldnews Archive article may be copied and distributed freely, provided: 1. There is no money collected for the text(s) of the articles. 2. The following notice remains appended to each copy: The Usenet Oldnews Archive: Compilation Copyright (C) 1981, 1996 Bruce Jones, Henry Spencer, David Wiseman.