Artifact 29008314be231ac6833683608bef0b1b7fb89fc0f08a4d7f93189d473b0460e4:
- File
psl-1983/doc/psl-projects.doc
— 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: 31029) [annotate] [blame] [check-ins using] [more...]
Utah Symbolic Computation Group May 1981 Operating Note No. 56 Portable Standard LISP Project List by M. L. Griss University of Utah Salt Lake City, UT 84112 Last Revision: 2 November 1981 ABSTRACT This note lists "projects" that need to be done to complete or enhance the developing Portable Standard LISP System. This includes additions or modifications to the basic sources, applications of the system and tools, and primitive facility development on newer target machines. Work supported in part by the National Science Foundation under Grant No. MCS80-07034. PSL Projects 2 1. Introduction This note is a guide to the current set of Projects that need to be completed to enhance the developing versions of Portable Standard LISP (PSL); the current versions are referred to as F-STDLSP and 20-STDLSP. For convenience, F-STDLSP is referred to as FSL and 20-STDLSP is referred to as 20SL, and these are names used in files. The projects divide into 3 major areas: Basic PSL development and portability; PSL Applications and Tools; Support of PSL development on newer machines. 2. Miscellaneous Small Enhancements and "Bugs" a. We need a way of accessing LISP function with same name as SYSLISP name [eg PLUS2] from SYSLISP, or causing better SYSLISP/LISP renaming (cf SYSNAME); should use MODE-REDUCE (similar to LISPVAR usage in SYSLISP) [Morrison?]; b. Document ERRORFORM!* and BREAKRETRY, make more ERRORs use ERRORFORM!*; make ERRORFORM!* a fluid in appropriate places; c. Have allocator functions call ERROR mechanism when no heap or GC left, so that maybe unwind can release space; also maybe have %RECLAIM have user hook per type so that user can monitor individual type usage. How do we handle problem that ERROR uses some heap?; d. Tighten BUILDING sequence, isolate a SYSLISP that can be run as a stand-alone language, with a minimum number of support functions; document CLEARLY, with a more formal specification of SYSLISP; e. Isolate machine dependant code in earliest files, reorder rest of functions with an eye to having just allocator, I/O and Fast-load in base files, rest of LISP loaded onto this kernel by FASL [mostly done, needs a FAP before further effort]; f. Add BIGNUM hooks, and rework BIGNUMs to use more effective storage model; [Standard LISP source exists and has been tested interpretively and compiled in the current STDLISP environment; low- level hooks not yet in; probably should use WORD vectors in place of lists]; add some of the BIGBIT operations that were used in Minor work; g. Permit Compiled and Interp NEXPRs. Consider LEXPRs. Perhaps a macro package for N-ary functions. Perhaps examine an argument number checking technique suggested by C. Griss: each call or definition of a function with N-args, leans to use of a generated name, Foo-N; this is really of the same level as treatment of FEXPR and MACRO types in Standard Lisp: intead of FEXPRs, MACROs, and EXPRs, we have FEXPRs, MACROs, EXPR0s, EXPR1s, EXPR2s...EXPRns; h. Try to SYSLISP with primitives so that EVAL-APPLY-LAP support code can be written in SYSLISP. Probably need LEXPR or stack local PSL Projects 3 arrays. May involve "hard" compiler additons; i. Optimize ARITHMETIC package, use SMACROs in place of PROCEDUREs to get better speed on small INTs. Examine re-assigment of TAG bits to optimize arithmetic dispatch; j. Use macros to make certain calls of ARITH in system functions more efficient; interface to Type'ing of MODE-RLISP. 3. I/O a. Arbitray long input strings; b. Bignum Parse/Print; c. BINARY I/O for .FAP/.REL; d. Packages (multi-symbol tables) interfaced as tree structured HASH tables for Intern, invoked by Hook in I/O; e. Implement Multi-Window Package (FRAMER), hooks to I/O; f. Provide primitives for READ-TABLE switching; g. Implement super PARENs (see NUREAD.RED by MLG, not in current system); 3.1. Interrupts Design better Interrupt Mechanism, decide how much control user should have; perhaps only available to terminate various kinds of run-ways. Implement a semi-portable interrupt machanism. We should probably look at what's available on the most likely targets (Tops-20, Unix, VMS?, perhaps bare hardware on some micros), and try to extract some common denominator (not necessarily the LCD though -- if an OS doesn't offer anything reasonable, then just bag interrupts for that implementation and be done with it). The current implementation does not allow arbitrary lisp code to be run from an interrupt, and then resumption, as a GC will lose anything pointed at only from registers. There are two ways to rectify this "defect": a. Go to a stack model for compiled code. I believe this would be a mistake. One of the major virtues of the current model is the excellent speed of compiled code. This is in large part due to the register model used. For my applications, at least, I would prefer the availability of raw speed, when desired, over arbitrary interrupts. As noted below, I believe we still have sufficient power in the interrupts available in the current model. b. Partition the registers into tagged and untagged registers, and modify the compiler so that any tagged object WHICH LIVES ONLY IN A PSL Projects 4 REGISTER is in a tagged register. Note that the compiler may leave tagged objects in an untagged register, which is OK so long as it knows that another pointer to the same object lives on the stack or in a value cell; however, the relocating GC can have problems, and we need to go to a 2 stack model. A problem this may introduce in the SysLisp version is parameter passing -- we may need two different function linkage mechanisms -- one for tagged and one for untagged objects. It may be possible to have the number of registers of each type vary dynamically. Because of the tremendous increase in complexity introduced by register partitioning, this would be difficult, but probably should be faced. I think we can live with a restricted interrupt mechanism. A fixed set of conditions would exist, together with a collection of possible actions. The user would be able to assign one of these (limited) actions to a condition. The set of conditions would of necessity be somewhat machine dependent. Hopefully a somewhat machine-independent subset could be made common to most inplementations. This subset might include a number of terminal keys, various "standard" error conditions such as I/O errors, and an alarm clock. The set of actions would include: a. Various carefully coded SysLisp routines intended for specific sorts of conditions, such as an arithmetic overflow causing a bignum package to be entered. These would be carefully coded so as to allow resumption of the computation. This could also include things such as a Tops-20 style ^T, or a quit back to the Exec. b. Execute a given, arbitrary piece of Lisp code, and then throw to a given tag. This could be used to generate an Error, enter a breakloop to examine an infinite loop (and then return to top- level), abort a computation and return to top-level (the code run on top of the stack could set a hook to be run upon return to top-level or whatever, as well), etc. This depends on the implementation of Catch and Throw causing everything needed for the surrounding context to be saved on the stack, and will require Throw to do some of its work with interrupts disabled, before returning to CATCH. Need to consider ARMING/DISARMING. c. Set a flag for the interpreter, and then resume the computation. Then, when the interpreter is next entered, an arbitrary piece of Lisp code is run, and the interpreter can resume after this "delayed" interrupt is handled. Should be able to do this kind of delayed interrupt in general. Note that the interrupt status must be altered upon entering the GC. We cannot run Lisp code during a GC, so actions of the second sort, above, must be deferred until after the GC. A number of those in class (1), above, may also need to be deferred. Note that it is the actions which must change during a GC, not the conditions. PSL Projects 5 A possible collection of Lisp functions as user entry points to such a mechanism are: (InitializeInterrupts) I'm not sure if this is needed at the user level, or if it should just always happen as part of the Lisp startup procedure. (EnableInterrupts) (DisableInterrupts) (SetInterrupt <condition> <action>) where <condition> is some appropriate keyword (an ID) such as 'ControlT, or 'StackOverflow, and <action> is either an appropriate keyword such as 'QuitToExec, 'QuitToTopLevel, or 'PrintStatistics, or is a list such as '(InterpreterInterupt (print "This is an interpreter interupt")) or '(ThrownInterupt (print "Now we'll throw to ErrorSet") '!$Error!$). Note that the function SetInterrupt is responsible for checking its arguments. (RemoveInterrupt <condition>) 4. Storage Management a. Explore a variety of alternative Storage Management schemes: BIBOP, COPYING; b. Consider improved garbage collector/allocator, using AREAS, BIBOP or some such; at least get SYSLISP items on non-traced stack (or stack region); maybe have SYSLISP stack group; use bit-table rather than RELOC fields, to permit extended addressing code to be run, use more of word. Look at ELISP copying GC. c. Consider collecting or relocating compiled code blocks, IDs and/or GENSYMs; 5. New Machine Implementations a. Bring up an extended addressing DEC-20 Standard LISP, using essentially the same c-macros, and some additional kernel code (developed at Rutgers for an extended addressing R/UCI LISP on the DEC-20 by C. Hedrick). b. Small Pointer DEC-20 with BIBOP and/or Bit-table for 18 bit pointers; c. Implement SYSLISP and PSL on PDP-11/45, as support for some of CAGD tools - probably obselete ?; d. Implement SYSLISP and PSL on VAX-750; PSL Projects 6 e. Implement SYSLISP and PSL on M68000 [Apollo and Wicat]; f. Implement SYSLISP and PSL for Z80; g. Re-implement FORTRAN version to check validity; move to CRAY; try more "genuine" FORTRAN version; consider FORTRAN bootstrap; consider PASLSP or KISLSP as bootstrap aid; 6. PASCAL like languages ADA, C and PASCAL versions, continuing from TERAK experiments; do some LILITH experiments [MODULA]. Major effort is current PASLSP on PERQ, Apollo and Wicat. Later move PASLSP more into a SYSLISP to PASCAL. a. Continue parameterizing (using # filter) 20, Terak, PERQ and Apollo features; tighten source code, improve I/O; look at other PASCAL LISPs; b. Modularize so can be come "Library" for embedded systems (INS file on Apollo, or MODULE for PERQ); c. Extend GC for FIXNUM's, Strings and maybe vectors; 7. Support work on Apollo 7.1. Initial Experiments a. Test LTNET. b. Finish implementation of FTP (stream-IO back to 20, ratfor I/O on 20); c. Should WICAT ftp to/from DOMAIN-net for shared printer? d. Establish back-up command files, and save system on floppies. e. Print and duplicate interesting HELP, DOC and INS files. f. Test some simple assembly code; g. Try BCPL and C cross assemblers; 7.2. Graphics Idea is to explore Apollo graphics, provide library of Graphics and Window routines for other utilities, eg VT52 emulator, Tek-like graphics terminal, etc. a. Borrow Summagraphics bit-pad from Brandt, and attach to one of SIO's (via patch panel ?), and add to STROKES for test, or perhaps attach PSL Projects 7 an SIO process to it, to send commands to DM input window (how?); b. Perhaps adapt TERAK FONT and Graphics editors; c. Test primitives (why didn't Scroll work); d. try Bit-blt e. try some of illegal "bits" (ie <-> MM, interlace, etc) f. Faster Line drawing g. RasterOp h. Try Inverse Video Fonts i. Reimplement own Window package. j. Work on FONT editor: find font format's in one of INS files; Decode STD and NONIE; Try create a font (see Terak Font Editor); 7.3. PSL work a. Study ASM and architecture, develop notes on OS funnies (talk MDL, Harvard, etc); b. Modify PSL compiler (look at VAX work and Normans' 68000 stuff) c. Try some codings and Boot it. 8. Impact of Other LISPs a. Look at IMSSS additions (Utilities); b. Study FRANZ-LISP, UCI-LISP and MACLISP for new features (also some extensions and enhancements motivated by the work on InterLISP, NIL, SPICE LISP and the LISP Machine); c. Look at COMMON-LISP effort at CMU; d. Develop macro package to permit FRANZ-LISP, MACLISP and InterLISP code to be directly loaded. VERY important, see InterLISP utility; e. Implement/examine CMU-Top-Level facilities (using MACLISP/FRANZLISP sources); f. Study VLISP Portability; PSL Projects 8 9. Editor and Editor Interface a. Implement EMID/EMODE multi-window, multi-buffer EMACS-like screen editor [1]. This is planned to be the major interface to the PSL system, and will have convenient commands (MODES) to edit LISP and RLISP, examine documentation and convert LISP and RLISP to and from other convenient forms. There are "autoparen" modes in which an expression typed into a buffer automatically EVALs as soon as the expression is complete. EMID has also been used to experimentally develop a VLSI SLA editor (SLATE) [4] and will be used to do algebraic expression "surgery". The new version of EMDOE should concentrate on: i. Good window/package interface; ii. Interface to PSL (interactive editing of functions and expressions); iii. True "modes". Implement EMACS fork call, using fixed page to pass text; b. Implement the simple EDIT-like line-oriented editor based on SOS/EDIT for editing RLISP/REDUCE and some LISP input; mostly for people familiar with these editors. c. Add a simple History mechanism [Cf CMU-LISP toplevel ]; d. Implement the InterLISP-like/UCI-Lisp like structure EDITOR (using Nordtsrom source, UCI source, or IMSSS modified source); 10. Compiler and Loader a. Need to implement 2 stacks for W-arith, etc. b. Implement a FAP (fast loader); Currently, the c-macro loader (LAP), and binary loader (FAP), are based on a variety of ad-hoc loaders that have been written for the various machines and adapted for new machines. Frick [5] has written a general purpose LAP and FAP in a much more portable fashion (using a set of configuring parameters to describe the kind of target machine), and it is planned to adopt this as the basic LAP/FAP package when the STDLISP kernel is stable. c. Make FAP and dynamic code space allocation part of kernel; d. Implement DEC-20 .REL file loader; e. Enhance resident compiler to accept SYSLISP; PSL Projects 9 11. Language Extensions a. Convert SYSLISP [3] from a BCPL-like language to a C-like language; basic idea is to make use of some type information for more effective compilation; Modes, Mode analysis and structure definitions should be obtained from MODE system, but code-generation for new SPECIFIC functions must be addressed; b. Mode Analyzing RLISP/REDUCE [MODE-REDUCE] is an ALGOL-68 or PASCAL like interface to Standard LISP, which provides an additional MODE analysis pass after parsing, to rebind "generic" function names to "specific" functions, based on the declared or analysed MODEs of arguments. The system includes a variety of MODE generators (STRUCT, UNION, etc) [10, 7, 9]. We plan to reimplement this system to use SYSLISP/STDLISP more effectively. We will also make the MODE- ANALYSIS phase part of SYSLISP, so that words, bytes, items etc. can co-exist more naturally. Note that parsing from RLISP is into MODE- STDLISP or MODE-SYSLISP [which now become same language]; c. Implement better RLISP parser and top loop "generating" functions; d. Rename JUMPON to CASE or SWITCH; extend to include SELECTx constructs; e. Iteration and progs should be made more compatible. A single iteration construct, equivalent to LISPM's DoNamed should be implemented, and all other iteration and Prog contructs made macros which map into it. I propose that Iterate is a better name than Do or DoNamed. It may contain labels and Go's as a prog, and also ReturnFrom's and a Next construct. A simple Return should simply macro into a ReturnFrom the nearest Iterate, and similarly a next which does not specify an Iterate tag. Go's should be allowed to jump out to LEXICALLY surrounding Iterate's, but not across true function calls. All this will be quite simple to implement so long as all the nasty constructs such as WHILE and PROG and the like are macros into a single construct such as Iterate. Prog's should possibly also be extended to allow initial values to be specified as for example (PROG (A B (N 0) (Flg T) X) ...) which would initialize A, B, and X to nil, N to zero, and Flg to true. This is trivial to do using Iterate as the target of the Prog macro. The map functions would also be macros into an appropriate Iterate function. The FOR macro (which has basically been implemented) would allow very general sorts of loops and mapping functions, and would allow returns and the like to pass through. Another excellent function to have would be a ReturnTop or some such which returns from the lexically outermost Iterate -- thus in general will return from the function begin defined. Quite useful, I believe, though I don't think it exists in any other lisps. PSL Projects 10 12. Error Handler and Break Package a. Modifications to Error handler(s), and BREAK/TRACE/BACKTRACE to provide error "severity" level or classification so we can pick up ALL error messages(templates), and BREAK can decide if it can start a new (debugging) STDLSP or MUST strip stack. b. Add more tools to BREAKLOOP, ie walk BSTACK to see OLD fluid values; perhaps devise scheme to relate BSTACK sections with current Proc; perhaps have PROCNAME pushed on BSTACK [only if has FLUIDS] (see the DDT program by BENSON); c. Design better Error Recovery mechanism, particular for error correction and retry. An interface to EMODE would help, also an interface to the "single" stepper (CMU-TOPLEVEL). d. Examine the notion of Stack groups, and introduce an ERROR stack group, since we run SYSLISP code using initial [STKLO,STKHI,ST], in order to define a new [STKLO',STKHI',ST']; this stack group stuff may help improve error handler. e. Improve BREAK package (combine with EMBED, rename current BREAK to BREAKLOOP, let BREAK be used to instrument a function: (BREAK FOO condition action); f. Add Error Severity classification; g. Make some errors continuable: Undefined function, Unbound variable, etc; Idea is perhaps to have CERROR(n,msg,errorform) for continuable errors, FERROR(n,msg) for FATAL errors that cant use BREAK lOOP, and ERROR(n,msg) for the most common case; h. Implement the portable DEBUG package of functions for tracing, breaking and embedding functions [11]. Facilities include the (conditional) tracing of function calls and interpreted SETQs; selective backtrace; embedding functions to selectively insert pre- and post- actions, and conditions; primitive statistics gathering; generation of simple stubs (print their name and argument, and read a value to return); and, a PRINT for circular and re-entrant lists. This will replace the simple TRACE package in the current kernel, and interact more effectively with the BREAK package. i. Timing Hooks; j. Expand Macros in PUTDs (under flag control?); 13. Source Code Checking a. IMSSS "syntax" checker; b. Implement version of CREF for SYSLISP and STDLISP. CREF processes a number of source files, cross-referencing the functions and Global PSL Projects 11 variables used; gives an indication of where each function is defined or redefined, its type (EXPR, FEXPR, etc), the functions and variables it uses, various undefined functions and variables, and other statistics that can be selected or deselected under flag control [8]. 14. Manual and Help Facility a. Improve HELP, combine with other HELP mechanism. It will display short text descriptions for major functions on request; by reading a documentation data base, and should also display an activity based HELP-TEXT (e.g. in response to ? at appropriate points). b. The MANUAL is now fleshed out, but consists of a motley collection of chapters and paragraphs. Both HELP and MANUAL require a considerable amount of work in the conversion and writing of pieces of text; we also need to co-ordinate with the SCRIBE sources for the various documents already written. A model for a multi-chapter scribe document has been tested, in which an index and table of contents data-base are being built similarly to the usual AUX file; at any time, an uptodate INDEX and TABLE of CONTENTS can be produced; c. A documentation mode of EMODE (ala INFO tree in EMACS). 15. Funarg, Closures and Stack Groups Improve the binding scheme. Use a Baker-like scheme for fluid bindings, and have locals in interpreted code. To handle locals in interpreted code will require having those special forms which know about locals to have special interpreter functions which are passed an extra argument -- the lexical environment (probably as an a-list). These will be essentially those f-exprs which are open-compiled: COND, AND, OR, SETQ, PROG, various looping constructs (which I think should, together with PROG, all be macros to a single DO-like special form), CATCH, THROW (these last two are currently exprs, but I think should be made special), GO, RETURN. Note that this would allow a somewhat more general use of things like return, which I believe is all the the better. This is discussed a little bit more, below. The fluid scheme I propose is essentially that of Baker, with rerooting after EVERY binding and unbinding operation enforced. This allows us to still always look for fluid values in the value cell. For further efficiency we can still do our binding on the binding stack, which is now viewed as a binding tree cache, so long as whenever we capture an environment (as with a Closure or Catch) we write it out into the heap. This will substantially speed up binding and unbinding in those cases where there is no intervening environment capture. Also, use of STACK as cache to avoid much rebinding in list. The capturing of an environment for a closure should be done not with FUNCTION, which simply quotes its argument in such a manner that it is known to be intended for execution, and should be compiled to code, but rather with a third form of quote, probably called CLOSURE. There should also be a mechanism PSL Projects 12 for grabbing the current environment, without including a function to be run therein, though of course (CLOSURE EVAL) can always be used to give this effect. Currently we are implementing a variant of Baker's [2] re-rooting scheme to work well in the shallow binding environment; we expect that non-funarg compiled code will run essentially as fast as in LISP 1.6. Context switches will be more expensive. We may also implement some form of Stack Group, as done by the LISP machine group [6, 12], to provide faster large context switch. Perhaps implement some form of LOCAL in interpreted code; Consider ramifications of package system, funargs and stack groups as some sort of static/dynamic environment methods; 16. Applications a. Implement the REDUCE algebra system; b. Get and Implement the VOCAL CAI language; c. Bring up MINI and META, improve their use of I/O; d. Implement Picture RLISP for TekTronix, HP, APOLLO, etc. e. Implement extended SLATE on PSL and maybe combine with other VLSI projects (ABLE->RLISP...). f. FORTRAN (RATFOR?) to SYSLISP compilers for tools. 17. References [1] Armantrout, R.; Benson, E.; Galway, W.; and Griss, M. L. EMID: A Multi-Window Screen Editor Written in Standard LISP. Utah Symbolic Computation Group Opnote No. 54, University of Utah, Computer Science Department, Jan, 1981. [2] Baker, H. G. Shallow Binding in LISP 1.5. CACM 21(7):565, July, 1978. [3] 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. [4] Carter, T.; Galway, W.; Goates, G.; Griss, M. L.; and Haslam, R. SLATE: A Lisp Based EMACS Like Text Editor for SLA Design. Utah Symbolic Computation Group Opnote No. 55, University of Utah, Computer Science Department, Jan, 1981. PSL Projects 13 [5] Frick, I. B. A Portable Lap and Binary Loader. Utah Symbolic Computation Group Operating Note Opnote No. 52, University of Utah, November, 1979. [6] Greenblatt, R. The LISP Machine. Technical Report ?, MIT, August, 1975. [7] Griss, M. L. The Definition and Use of Data-Structures in Reduce. In Proceedings of SYMSAC 76, pages 53-59. SYMSAC, August, 1976. [8] Griss, M. L. RCREF: An Efficient REDUCE and LISP Cross-Reference Program. Utah Symbolic Computation Group, Operating Note Opnote No. 30, Univerisity of Utah, ??, 1977. [9] Griss, Martin L.; Hearn, A. C; and Maguire, G. Q., Jr. Using The MODE Analyzing version of REDUCE. Utah Symbolic Computation Group Opnote No. 48, Dept of CS, U of U, Jun, 1980. [10] Hearn, A. C. A Mode Analyzing Algebraic Manipulation Program. In Proceedings of ACM 74, pages 722-724. ACM, New York, New York, 1974. [11] Norman, A.C. and Morrison, D. F. The REDUCE Debugging Package. Utah Symbolic Computation Group, Operating Note Opnote No. 49, Dept of CS, U of U, Feb, 1981. [12] Weinreb, D. and Moon, D. LISP Machine Manual. Manual , M. I. T., January, 1979. second preliminary version. PSL Projects i Table of Contents 1. Introduction 2 2. Miscellaneous Small Enhancements and "Bugs" 2 3. I/O 3 3.1. Interrupts 3 4. Storage Management 5 5. New Machine Implementations 5 6. PASCAL like languages 6 7. Support work on Apollo 6 7.1. Initial Experiments 6 7.2. Graphics 6 7.3. PSL work 7 8. Impact of Other LISPs 7 9. Editor and Editor Interface 8 10. Compiler and Loader 8 11. Language Extensions 9 12. Error Handler and Break Package 10 13. Source Code Checking 10 14. Manual and Help Facility 11 15. Funarg, Closures and Stack Groups 11 16. Applications 12 17. References 12