Structure of a LISP system using two-level storage

ABSTRACT

In an ideal list-processing system there would be enough core memory to contain all the data and programs. Described in this paper are a number of techniques that have been used to build a LISP system utilizing a drum for its principal storage medium, with a surprisingly low time penalty for use of this slow storage device. The techniques include careful segmentation of system programs, allocation of virtual memory to allow address arithmetic for type determination, and a special algorithm for building reasonably linearized lists. A scheme for binding variables is described which is good in this environment and allows for complete compatibility between compiled and interpreted programs with no special declarations.

REFERENCES

• 1: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 2: BERKELEY, E. G., AND BOBROW, D. G. (EDs.) The Programming Language LISP, Its Operation and Applications. MIT Press, Cambridge, Mass., 1966.
• 3: CORBATO, F., AND GLASER, E. ET AL. The MULTICS system. Proc. AFIPS 1965 Fall Joint Comput. Conf., Nov. 1965, Vol. 27, pp. 185-196.
• 4: BOBROW, D. G. Storage management in LISP. Proc. IFIP Conf. on Symbol Manipulation Languages. North-Holland, Amsterdam (in press).
• 5: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 6: Jacques Cohen, A use of fast and slow memories in list-processing languages, Communications of the ACM, v.10 n.2, p.82-86, Feb. 1967 [doi>10.1145/363067.363092]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Documentation, Languages, Theory