PSL Manual 7 February 1983 Implementation
section 21.0 page 21.1
CHAPTER 21
CHAPTER 21
CHAPTER 21
IMPLEMENTATION
IMPLEMENTATION
IMPLEMENTATION
21.1. Overview of the Implementation . . . . . . . . . 21.1
21.2. Files of Interest . . . . . . . . . . . . . 21.1
21.3. Building PSL on the DEC-20 . . . . . . . . . . 21.2
21.4. Building the LAP to Assembly Translator . . . . . . 21.5
21.5. The Garbage Collectors and Allocators. . . . . . . 21.5
21.5.1. Compacting Garbage Collector on DEC-20 . . . . 21.5
21.5.2. Two-Space Stop and Copy Collector on VAX . . . 21.6
21.6. The HEAPs . . . . . . . . . . . . . . . . 21.6
21.7. Allocation Functions . . . . . . . . . . . . 21.8
This chapter is very out of date and will be replaced as soon as
possible. Refer to the release notes for your machine and the forthcoming
implementation guide.
21.1. Overview of the Implementation
21.1. Overview of the Implementation
21.1. Overview of the Implementation
In this Chapter we give a guide to the sources, although they are still
rapidly changing. With these notes in mind, and an understanding of
SYSLISP and the compiler at the level of Chapters 18 and 20, it is hoped
the user will be able to understand and change most of the system. Much of
the current information is contained in comments in the source files, and
cannot be reproduced here.
[??? This Section needs a LOT of work ???]
[??? This Section needs a LOT of work ???]
[??? This Section needs a LOT of work ???]
21.2. Files of Interest
21.2. Files of Interest
21.2. Files of Interest
The complete sources are divided up into a fairly large number of files,
spread over a number of sub-directories of <PSL>. This is so that files
representing a common machine-independent kernel are in a single directory,
and additional machine specific files in others. Furthermore, we have
separated the compiler and LAP files from the rest of the files, since they
are looked at first when doing a new implementation, but are not actually
important to understanding the working of PSL.
Some convenient logical device names are defined in <psl>logical-
names.cmd. This file should have been TAKEn in your LOGIN.CMD. Current
definitions are:
;Officially recognized logical names for PSL subdirectories on UTAH-20
define psl: <psl> ! Executable files and miscellaneous
Implementation 7 February 1983 PSL Manual
page 21.2 section 21.2
define ploc: <psl.local> ! Non-distributed miscellaneous
define pi: <psl.interp> ! Interpreter sources
define pc: <psl.comp> ! Compiler sources
define pu: <psl.util> ! Utility program sources
define plocu: <psl.local.util> ! Non-distributed utility sources
define pd: <psl.doc> ! Documentation to TYPE
define pe: <psl.emode> ! Emode sources and build files
define plpt: <psl.lpt> ! Printer version of Documentation
define ph: <psl.help> ! Help files
define plap: <psl.lap> ! LAP and B files
define ploclap: <psl.local.lap> ! Non-distributed LAP and B files
define pred: <reduce.psl-reduce>! Temporary home of Reduce built upon
! PSL
define p20: <psl.20-interp> ! Dec-20 specific interpreter sources
define p20c: <psl.20-comp> ! Dec-20 specific compiler sources
define p20d: <psl.20-dist> ! Dec-20 distribution files
define pv: <psl.vax-interp> ! Vax specific interpreter sources
define pvc: <psl.vax-comp> ! Vax specific compiler sources
define pvd: <psl.vax-dist> ! Vax distribution files
define p68: <psl.68000-interp> ! M68000 specific interpreter sources
define p68c: <psl.68000-comp> ! M68000 specific compiler sources
define pcr: <psl.cray-interp> ! Cray-1 interpreter sources
define pcrc: <psl.cray-comp> ! Cray-1 compiler sources
define pcrd: <psl.cray-dist> ! Cray-1 distribution files
define pl: plap:,ploclap: ! Search list for LOAD
Sources mostly live on PI:. DEC-20 build files and very machine specific
files live on P20:.
21.3. Building PSL on the DEC-20
21.3. Building PSL on the DEC-20
21.3. Building PSL on the DEC-20
[??? fix as FASL works ???]
[??? fix as FASL works ???]
[??? fix as FASL works ???]
Building proceeds in number of steps. First the kernel files are
compiled to MIDAS, using a LAP-to-MIDAS translator, which follows the
normal LISP/SYSLISP compilation to LAP. This phase also includes the
conversion of constants (atoms names, strings, etc) into structures in the
heap, and initialization code into an INIT procedure. The resulting module
is assembled, linked, and saved as BARE-PSL.EXE. If executed, it reads in
a batch of LAP files, previously compiled, representing those functions
that should be in a minimal PSL, but in fact are not needed to implement
LAP.
[??? When FAP is implemented, these LAP files will become FAP files,
[??? When FAP is implemented, these LAP files will become FAP files,
[??? When FAP is implemented, these LAP files will become FAP files,
and the kernel will get smaller ???]
and the kernel will get smaller ???]
and the kernel will get smaller ???]
.
The BARE-PSL kernel build file is P20:PSL-KERNEL.CTL, and is reproduced
PSL Manual 7 February 1983 Implementation
section 21.3 page 21.3
here, slightly edited:
; This requires PL:PSL-NON-KERNEL.LAP and P20C:PSLDEF.MID
copy BARE-PSL.SYM PSL.SYM
PSL:MIDASCMP ! previously saved with LAPtoMIDAS
in "PSL-KERNEL.RED"; % Files for kernel
quit;
MIDAS ! assemble kernel data
dpsl
MIDAS ! assemble kernel init code
spsl
MIDAS ! assemble kernel code
psl
load DPSL.REL, SPSL.REL, PSL.REL ! link into one module
save BARE-PSL.EXE ! save executable
The kernel files mentioned in PSL-KERNEL.RED are:
MIDASOUT "PSL";
IN "BINDING.RED"$ % binding from the interpreter
IN "FAST-BINDER.RED"$ % for binding in compiled code,
% in LAP
IN "SYMBOL-VALUES.RED"$ % SET, and support for Eval
IN "FUNCTION-PRIMITIVES.RED"$ % used by PutD, GetD and Eval
IN "OBLIST.RED"$ % Intern, RemOb and GenSym
IN "CATCH-THROW.RED"$ % non-local GOTO mechanism
IN "ALLOCATORS.RED"$ % heap, symbol and code space alloc
IN "COPIERS.RED"$ % copying functions
IN "CONS-MKVECT.RED"$ % SL constructor functions
IN "GC.RED"$ % the garbage collector
IN "APPLY-LAP.RED"$ % low-level function linkage, in LAP
IN "EQUAL.RED"$ % equality predicates
IN "EVAL-APPLY.RED"$ % interpreter functions
IN "PROPERTY-LIST.RED"$ % PUT and FLAG and friends
IN "FLUID-GLOBAL.RED"$ % variable declarations
IN "PUTD-GETD.RED"$ % function defining functions
IN "KNOWN-TO-COMP-SL.RED"$ % SL functions performed online
% in code
IN "OTHERS-SL.RED"$ % DIGIT, LITER and LENGTH
IN "CARCDR.RED"$ % CDDDDR, etc.
IN "EASY-SL.RED"$ % highly portable SL function defns
IN "EASY-NON-SL.RED"$ % simple, ubiquitous SL extensions
IN "COMP-SUPPORT.RED"$ % optimized CONS and LIST compilation
IN "ERROR-HANDLERS.RED"$ % low level error handlers
IN "TYPE-CONVERSIONS.RED"$ % convert from one type to another
IN "ARITH.RED"$ % Lisp arithmetic functions
IN "IO-DATA.RED"$ % Data structures used by IO
Implementation 7 February 1983 PSL Manual
page 21.4 section 21.3
IN "SYSTEM-IO.RED"$ % system dependent IO functions
IN "CHAR-IO.RED"$ % bottom level IO primitives
IN "OPEN-CLOSE.RED"$ % file primitives
IN "RDS-WRS.RED"$ % IO channel switching functions
IN "OTHER-IO.RED"$ % random SL IO functions
IN "READ.RED"$ % S-expression parser
IN "TOKEN-SCANNER.RED"$ % table-driven token scanner
IN "PRINTERS.RED"$ % Printing functions
IN "WRITE-FLOAT.RED"$ % Floating point printer
IN "PRINTF.RED"$ % formatted print routines
IN "IO-ERRORS.RED"$ % I/O error handlers
IN "IO-EXTENSIONS.RED"$ % Random non-SL IO functions
IN "VECTORS.RED"$ % GetV, PutV, UpbV
IN "STRING-OPS.RED"$ % Indx, SetIndx, Sub, SetSub, Concat
IN "EXPLODE-COMPRESS.RED"$ % Access to characters of atoms
IN "BACKTRACE.RED"$ % Stack backtrace
IN "DEC-20-EXTRAS.RED"$ % Dec-20 specific routines
IN "LAP.RED"$ % Compiled code loader
IN "INTERESTING-SYMBOLS.RED"$ % to access important WCONSTs
IN "MAIN-START.RED"$ % first routine called
MIDASEND;
InitSymTab();
END;
The current non-kernel files are defined in PSL-NON-KERNEL.RED:
LapOut "PL:PSL-NON-KERNEL.LAP";
in "EVAL-WHEN.RED"$ % control evaluation time(load first)
in "CONT-ERROR.RED"$ % macro for ContinuableError
in "MINI-TRACE.RED"$ % simple function tracing
in "TOP-LOOP.RED"$ % generalized top loop function
in "PROG-AND-FRIENDS.RED"$ % Prog, Go and Return
in "ERROR-ERRORSET.RED"$ % most basic error handling
in "TYPE-ERRORS.RED"$ % type mismatch error calls
in "SETS.RED"$ % Set manipulation functions
in "DSKIN.RED"$ % Read/Eval/Print from files
in "LISP-MACROS.RED"$ % If, SetF
in "LOOP-MACROS.RED"$ % While, Repeat, ForEach
in "CHAR.RED"$ % Character constant macro
in "LOAD.RED"$ % Standard module LAP loader
in "PSL-MAIN.RED"$ % SaveSystem and Version stuff
LapEnd;
The model on the VAX is similar.
The file GLOBAL-DATA.RED is automatically loaded by the compiler in the
LAP-to-Assembly phase. It defines most important external symbols.
PSL Manual 7 February 1983 Implementation
section 21.3 page 21.5
A symbol table file, PSL.SYM is produced, and is meant to be used to aid
in independent recompilation of modules. It records assigned ID numbers,
locations of WVARS, WARRAYS, and WSTRINGs, etc. It is not currently used.
The file P20C:DATA-MACHINE.RED defines important macros and constants,
allocating fields within a DEC-20 word (the TAGs, etc). It is used only
with compiled code, and is so associated with the P20C: (20 compiler
specific code); other files on this directory include the code-generator
tables and compiler customization files. More information on the compiler
and its support can be found in Chapter 18.
21.4. Building the LAP to Assembly Translator
21.4. Building the LAP to Assembly Translator
21.4. Building the LAP to Assembly Translator
[??? Write after new table-driven LAP and LAP-to-ASM is stable ???]
[??? Write after new table-driven LAP and LAP-to-ASM is stable ???]
[??? Write after new table-driven LAP and LAP-to-ASM is stable ???]
21.5. The Garbage Collectors and Allocators
21.5. The Garbage Collectors and Allocators
21.5. The Garbage Collectors and Allocators
21.5.1. Compacting Garbage Collector on DEC-20
21.5.1. Compacting Garbage Collector on DEC-20
21.5.1. Compacting Garbage Collector on DEC-20
DEC-20 PSL uses essentially the same compacting garbage collector
developed for the previous MTLISP systems: a single heap with all objects
tagged in the heap in such a way that a linear scan from the low end
permits objects to be identified; they are either tagged as normal objects,
and are thus in a PAIR, or are tagged with a "pseudo-tag", indicating a
header item for some sort of BYTE, WORD or ITEM array. Tracing of objects
is done using a small stack, and relocation via a segment table and extra
bits in the item. The extra bits in the item can be replaced by a
bit-table, and this may become the default method.
During compaction, objects are "tamped" to the low end of the heap,
permitting "genetic" ordering for algebraic operations, and rapid
stack-like allocation.
Since the MTLISP systems included a number of variable sized data-types
______ ______
(e.g. vectors and strings), we had to reduce the working set, and ease the
addition of new data-types, by using a single heap with explicitly tagged
objects, and compacting garbage collector. In some versions, a bit-table
was used both for marking and for compaction. To preserve locality,
structures are "tamped" to one end of the heap, maintaining relative
(creation time or "Genetic" [Terashima 78]) ordering. The order
preservation was rather useful for an inexpensive canonical ordering
required in the REDUCE algebra system (simply compare heap positions, which
are "naturally" related to object creation). The single heap, with
explicit tags made the addition of new data-types rather easy. The virtual
memory was implemented as a low level "memory" extension, invisible to the
allocator and garbage collector.
Implementation 7 February 1983 PSL Manual
page 21.6 section 21.5
This garbage collector has been rewritten a number of times; it is fairly
easy to extend, but does waste lot of space in each DEC-20 word. Among
possible alternative allocators/GC is a bit-table version, which is
semantically equivalent to that described above but has the Dmov field
replaced by a procedure to count ones in a segment of the bit-table. At
some point, the separate heap model (tried on Z-80 and PDP-11 MTLISP's) may
be implemented, but the separate page-per-type method (BIBOP:="big bag of
pages") might also be tried; this permits user definition of new types.
Allocation proceeds as from a stack, permitting rapid allocation, and
preserving creation time ordering. The current implementation uses a
recursive mark phase with a small stack (G stack) of about 500 entries.
Relocation is accomplished with aid the of the SEGMENT table (overlays G
stack), and a small field (Dmov) in each item (header) that gives
additional motion of this item relative to the relocation of its segment.
21.5.2. Two-Space Stop and Copy Collector on VAX
21.5.2. Two-Space Stop and Copy Collector on VAX
21.5.2. Two-Space Stop and Copy Collector on VAX
Another alternative is a copying, 2-space GC, which is fast and good for
large address space (e.g. extended addressing DEC-20 or VAX).
21.6. The HEAPs
21.6. The HEAPs
21.6. The HEAPs
The HEAP is used to store variable sized objects. Since one of the
possible implementations is to have a separate heap for each of the data
types PAIR, STR, CODE, and VECT (or for the groupings PAIR, CODE+STR,
VECT), the heap is accessed in type specific fashion only. The current
implementation of the allocator and garbage collector maps these
type-specific operations onto a single array of item sized blocks, the
first of which is a normal tagged item (CAR of a PAIR), or a pseudo-item
(header of CODE, STR or VECT). The following blocks are either tagged
items or packed bytes. The header item contains a "length" in items, or
bytes, as appropriate. Using item sized blocks results in a slight wastage
at the end of strings and code-vectors.
Reclamation:
h:=INF(x) For garbage collection, compaction and relocation. The heap is
viewed as a set of ITEM sized blocks
PUTINF(x,h)
PUTTYPE(x,t)
MARK(h)
UNMARK(h) Modify the garbage collector mark
MARKED(h) Test the mark (in a bit-table, ITEM header, or ITEM itself).
Other Garbage collector primitives include:
PSL Manual 7 February 1983 Implementation
section 21.6 page 21.7
GCPUSH(x) Push an ITEM onto GCSTACK for later trace
x:=GCPOP()
Retrieve ITEM for tracing
x:=GCTOP()
Examine top of GCSTACK
The Garbage collector uses a GCSTACK for saving pointers still to be
traced. The compaction and relocation takes place by "tamping", without
structure reorganization, so that any structure is relocated by the same or
more than a neighboring structure, lower in the heap. This "monotonicity"
means that the heap can be divided into "segments", and the relocation of
any structure computed as the relocation of its segment, plus an additional
movement within the segment. The segment table is an additional structure,
while the "offset" is computed from the bits in the bit-table, or from a
small field (if available) in the ITEM. This garbage collector is similar
to that described in [Terashima 78].
RELOC(h):=SEGKNT(SEG(h))+DMOV(h)
SEGKNT(SEG(h)) is the segment relocation of the segment in which
h is, and DMOV is the incremental move within this segment.
i:=SEG(h) Computes the segment number
i:=DSEG(h)
The "offset" in the segment
Note that DMOV may actually be a small field in an ITEM header, if there
is space, or can be computed from the bits in a segment of the BIT-table,
or may map to some other construct. The segment table may actually overlay
the GCSTACK space, since these are active in different passes of the
garbage collection. The garbage collector used in the MTLISP system is an
extension of that attributed to S. Brown in [Harrison 73, Harrison 74].
See also [Terashima 78].
__________ ______
!*GC [Initially: NIL] switch
!*GC controls the printing of garbage collector messages. If NIL
no indication of garbage collection occurs. If non-NIL various
system dependent messages may be displayed.
__________ ______
GCKNT!* [Initially: 0] global
Reclaim
Reclaim
Records the number of times that Reclaim has been called to this
point. GCKNT!* may be reset to another value to record counts
incrementally, as desired.
Implementation 7 February 1983 PSL Manual
page 21.8 section 21.6
Reclaim
Reclaim _______ ____
(Reclaim ): integer expr
User call on GC; does a mark-trace and compaction of HEAP.
Returns size of current Heap top. If !*GC is T, prints some
Reclaim
Reclaim
statistics. Increments GCKNT!*. Reclaim(); is the user level
call to the garbage collector.
!%Reclaim
!%Reclaim ___ _______ ____
(!%Reclaim ): Not Defined expr
!%Reclaim
!%Reclaim
!%Reclaim(); is the system level call to the garbage collector.
Active data in the heap is made contiguous and all tagged
pointers into the heap from active local stack frames, the
binding stack and the symbol table are relocated.
21.7. Allocation Functions
21.7. Allocation Functions
21.7. Allocation Functions
GtHEAP
GtHEAP _____ ____ ____ ____
(GtHEAP NWRDS:word): word expr
_____
Return address in HEAP of a block of NWRDS item sized pieces.
GtHeap
GtHeap
Generates HeapOverflow Message if can't satisfy. GtHeap NIL;
returns the number of words (Lisp items) left in the heap.
GtHeap
GtHeap
GtHeap 0; returns a pointer to the top of the active heap.
GtHeap
GtHeap
GtHeap N; returns a pointer to N words (items).
GtStr
GtStr _____ ____ ____ ____
(GtStr UPLIM:word): word expr
______ _____
Address of string, 0..UPLIM bytes. (Allocate space for a string
_____
UPLIM characters.)
GtConstStr
GtConstStr _ ______ ____
(GtConstStr N:string): expr
GtStr
GtStr
(Allocate un-collected string for print name. Same as GtStr, but
uses BPS, not heap.)
GtWrds
GtWrds _____ ____ ____ ____
(GtWrds UPLIM:word): word expr
_____ _____
Address of WRD, 0..UPLIM WORDS. (Allocate space for UPLIM
untraced words.)
GtVect
GtVect _____ ____ ____ ____
(GtVect UPLIM:word): word expr
______ _____
Address of vector, UPLIM items. (Allocate space for a vector
_____
UPLIM items.)
PSL Manual 7 February 1983 Implementation
section 21.7 page 21.9
GtFixN
GtFixN _ _______ ____
(GtFixN ): s-integer expr
Allocate space for a fixnum.
GtFltN
GtFltN _ _______ ____
(GtFltN ): s-integer expr
_____
Allocate space for a float.
GtID
GtID __ ____
(GtID ): id expr
__
Allocate a new id.
GtBps
GtBps _ _ _______ _ _______ ____
(GtBps N:s-integer): s-integer expr
_
Allocate N words for binary code.
GtWArray
GtWArray _ _ _______ _ _______ ____
(GtWArray N:s-integer): s-integer expr
_
Allocate N words for WVar/WArray/WString.
DelBps
DelBps ____
(DelBps ): expr
DelWArray
DelWArray ____
(DelWArray ): expr
GtBps GtWArray
GtBps GtWArray
GtBps NIL; returns the number of words left in BPS. GtWArray NIL returns
the same quantity.
GtBps
GtBps
GtBps 0; returns a pointer to the bottom of BPS, that is, the current
GtWArray
GtWArray
value of NextBPS. GtWArray 0; returns a pointer to the top of BPS, the
DelBps
DelBps
current value of LastBPS. This is sometimes convenient for use with DelBps
DelWArray
DelWArray
and DelWArray.
GtBps
GtBps
GtBps N; returns a pointer to N words in BPS, moving NextBPS up by that
GtWArray
GtWArray
amount. GtWArray returns a pointer to (the bottom of) N words at the top
of BPS, pushing LastBPS down by that amount. Remember that the arguments
are number of WORDS to allocate, that is, 1/4 the number of bytes on the
VAX or 68000.
DelBps
DelBps
DelBps(Lo, Hi) returns a block to BPS, if it is contiguous with the
current free space. In other words, if Hi is equal to NextBPS, then
NextBPS is set to Lo. Otherwise, NIL is returned and no space is added to
DelHeap DelBps
DelHeap DelBps
BPS. DelHeap(Lo, Hi) is similar in action to DelBps.
DelWArray
DelWArray
DelWArray(Lo, Hi) returns a block to the top of BPS, if it is contiguous
with the current free space. In other words, if Lo is equal to LastBPS,
then LastBPS is set to Hi. Otherwise, NIL is returned and no space is
Implementation 7 February 1983 PSL Manual
page 21.10 section 21.7
added to BPS.
The storage management routines above are intended for either very long
term or very short term use. BPS is not examined by the garbage collector
at all. The routines below should be used with great care, as they deal
with the heap which must be kept in a consistent state for the garbage
collector. All blocks of memory allocated in the heap must have header
words describing the size and type of data contained, and all pointers into
the heap must have type tags consistent with the data they refer to.