Artifact 8909ccf58841234ec28d721d911b88f9bb64e18dcb52f7c773ba28739ee157e1:
- File
psl-1983/3-1/lpt/21-implementation.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: 26406) [annotate] [blame] [check-ins using] [more...]
- File
psl-1983/lpt/21-implementation.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: 26406) [annotate] [blame] [check-ins using]
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.