LISP-SP : A Portable INTERLISP Subset Interpreter for Mini-Computers

Abstract

This paper describes the implementation of LISP-SP, a decendant of LISPF3, an INTERLISP compatible LISP system originating from DATALOGILABORIET, Uppsala, Sweden 1978. Two data types have been added to LISPF3, namely floating point numbers and. arrays, and a swapping algorithm as been implemented for data arrays. Besides those new data types, a different method of storing lists internally has been adopted which is based on the idea that in LISPF3 each list cell consists of two memory cells, one for CAR and one for CDR, where in most cases, CDR contains only a pointer to the successor list element, and list space can be saved when keeping list elements 'physically' adjacent as much as possible. The CDR pointer is then available implicitly by incrementing the address to the internal structure carrying lists, except when the sequence of elements is broken through application of LISP functions. In those cases, special pointers are used which do not represent CDR values, but are only inspected to determine the location of the next element. This method was selected to avoid program addressing Space problems on mini-computers, resulting from the expansion of LISPF3's internal data structures from 16-bit to 32-bit width, as required by LISPF3 users asking for 'more user address space’. These enhancements of LISPF3 lead to a complete redesign of the system, where special attention was put on producing readable and self-documenting software. The resulting system differs enough from its predecessor to justify a different name, therefore, the name LISP-SP was selected, reflecting the fact that sublist structures are marked internally by (S)tored (P)arentheses. When handling lists in this way, examples show that the number of memory cells allocated for a given package of LISP functions is approximately the same as in LISPF3. If, however, LISPF3's data structures had been widened to 32-bit elements, then twice the amourt of program addressing space for lists would be neccessary to store the same package - too much for most of the mini-computers currently available. The system is available at a nominal charge from Prof. Dr. P. Raulefs Universität Kaiserslautern Fachbereich Informatik Postfach 3049 D-6750 Kaiserslautern West Germany