Wilfred J. Hansen
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.
- 1 GRAY, J. C. Compound data structure for computer aided design; a survey. Proc. ACM 22nd. Nat. Conf. 1967, Thompson Book Co., Washington, D. C., pp. 355-365. Google Scholar
Digital Library
- 2 HANSEN, W. J. The impact of storage management on the implementation of plex processing languages. Tech. Rep. No. 113, Computer Science Dep., Stanford U., Stanford, Calif., 1969. Google ScholarDigital Library
- 3 KNUTH, D. E. The Art of Computer Programming, Vol. 1, Addison-Wesley, Menlo Park, Calif., 1968. Google ScholarDigital Library
- 4 LANG, C. A., AND GRAY, J. C. ASP-A ring implemented associative structure package. Comm. ACM 11, 8 (Aug. 1968), 550-555. Google ScholarDigital Library
- 5 MCCARTHY, J., ET AL. LISP 1.5 Programmer's Manual. MIT Press, Cambridge, Mass., 1962. Google ScholarDigital Library
- 6 MINSKY, M. L. A LISP garbage collector using serial secondary storage. MIT Artificial Intelligence Memo. No. 58, MIT, Cambridge, Mass., Oct. 1963. Google ScholarDigital Library
- 7 Ross, D.T. A generalized technique for symbol manipulation and numerical calculation. Comm. ACM 5, 3 (Mar. 1961), 147-150. Google ScholarDigital Library
- 8 The AED free storage package. Comm. ACM 10, 8 (Aug. 1967), 481-492. Google ScholarDigital Library
- 9 REYNOLDS, J. C. Cogent programming manual. Argonne Nat. Lab. Rep. No. ANL-7022, Argonne, Illinois, Mar. 1965.Google Scholar
- 10 SCHORR, H., AND WAITE, W.M. An efficient machine-independent procedure for garbage collection in various list structures. Comm. ACM 10, 8 (Aug. 1967), 501-506. Google ScholarDigital Library
- 11 STYGAR, P. LISP 2 garbage collector specifications. TM- 3417/500/00, System Development Corp., Santa Monica, Calif., Apr. 1967.Google Scholar
- 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.Google Scholar
Index Terms
- Compact list representation: definition, garbage collection, and system implementation
Recommendations
A nonrecursive list compacting algorithm
A simple nonrecursive list structure compacting scheme or garbage collector suitable for both compact and LISP-like list structures is presented. The algorithm avoids the need for recursion by using the partial structure as it is built up to keep track ...
Multiprocessing compactifying garbage collection
Algorithms for a multiprocessing compactifying garbage collector are presented and discussed. The simple case of two processors, one performing LISP-like list operations and the other performing garbage collection continuously, is thoroughly examined. ...
A time- and space-efficient garbage compaction algorithm
Given an area of storage containing scattered, marked nodes of differing sizes, one may wish to rearrange them into a compact mass at one end of the area while revising all pointers to marked nodes to show their new locations. An algorithm is described ...
Comments