Compact list representation: definition, garbage collection, and system implementation

ABSTRACT

Compact lists are stored sequentially in memory, rather than chained with pointers. Since this is not always convenient, the Swym system permits a list to be chained, compact, or any combination of the two. A description is given of that list representation and the operators implemented (most are similar to those of LISP 1.5). The system garbage collector attempts to make all lists compact; it relocates and rearranges all of list storage using temporary storage. This unique list-compacting garbage collection algorithm is presented in detail. Several classes of the macros used to implement the system are described. Finally, consideration is given to those design factors essential to the success of a plex processing system implementation.

REFERENCES

• 1: J. C. Gray, Compound data structure for computer aided design; a survey, Proceedings of the 1967 22nd national conference, p.355-365, January 1967, Washington, D.C., United States [doi>10.1145/800196.806005]
• 2: Wildred J. Hansen, The impact of storage management on plex processing language implementation, Stanford University, Stanford, CA, 1969
• 3: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 4: C. A. Lang , J. C. Gray, Programming Techniques: ASP—a ring implemented associative structure package, Communications of the ACM, v.11 n.8, p.550-555, Aug. 1968 [doi>10.1145/363567.363576]
• 5: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 6: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 7: Douglas T. Ross, A generalized technique for symbol manipulation and numerical calculation, Communications of the ACM, v.4 n.3, p.147-150, March 1961 [doi>10.1145/366199.366256]
• 8: Douglas T. Ross, The AED free storage package, Communications of the ACM, v.10 n.8, p.481-492, Aug. 1967 [doi>10.1145/363534.363546]
• 9: REYNOLDS, J. C. Cogent programming manual. Argonne Nat. Lab. Rep. No. ANL-7022, Argonne, Illinois, Mar. 1965.
• 10: H. Schorr , W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM, v.10 n.8, p.501-506, Aug. 1967 [doi>10.1145/363534.363554]
• 11: STYGAR, P. LISP 2 garbage collector specifications. TM- 3417/500/00, System Development Corp., Santa Monica, Calif., Apr. 1967.
• 12: WISEMAN, N. E. A simple list processing package for the PDP-7. In DECUS Second European Seminar, Aachen, Germany, Oct. 1966, pp. 37-42.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

General Terms:
Algorithms, Languages

Keywords:
LISP, compact list, data representation, data structure, free storage, garbage collection, list, list processing system, list representation, list structure, macro, plex, plex processing, pointer, primitive list operations, relocation, storage reclamation