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]<GRISS>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 <
[email protected]>
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.
