H. Schorr
Abstract
A method for returning registers to the free list is an essential part of any list processing system. In this paper, past solutions of the recovery problem are reviewed and compared. A new algorithm is presented which offers significant advantages of speed and storage utilization. The routine for implementing this algorithm can be written in the list language with which it is to be used, thus insuring a degree of machine independence. Finally, the application of the algorithm to a number of different list structures appearing in the literature is indicated.
- 1 NEWELL, A. (ED.) Information Processing Language-W Manual, 2nd ed. Prentice Hall, Englewood N. J., 1964.Google Scholar
- 2 McCARTHY, J. Recursive functions of symbolic expressions and their computation by machine, part I. Comm. ACM 3 (April, 1960), 184. Google ScholarDigital Library
- 3 GERLERNTER, H., ET AL. A FORTRAN-compiled list-processing language. J. ACM 7 (April 1960), 87. Google ScholarDigital Library
- 4 COLLINS, G. E. A method for overlapping and erasure of lists. Comm. ACM 8 (Dec. 1960), 655. Google ScholarDigital Library
- 5 WEIZENBAUM, J. Knotted list structures. Comm. ACM 5 (Mar. 1962), 161. Google ScholarDigital Library
- 6 WEIZENBAUM, J. Symmetric list processor. Comm. ACM 6 (Sept. 1963), 524. Google ScholarDigital Library
- 7 WILKES, M. V. An experiment with a self-compiling compiler for a simple list-processing language. Annual Review in Automatic Programming, Vol. 4. Pergamon Press, N.Y. 1964, pp. 1-48.Google ScholarCross Ref
- 8 WILKES, M. V. Lists and why they are useful. Proc. ACM 19th Nat. Conf., August 1964, ACM Publ. P-64, F1-1. Google ScholarDigital Library
- 9 COMFORT, W. T. Multiword list items. Comm. ACM 7 (June 1964), 357. Google ScholarDigital Library
- 10 EVANS, A., PERLIS, A. J., AND VAN ZOEREN, H. Use of threaded lists in constructing a combined ALGOL and machine-like assembly processor. Comm. ACM 4 (Jan. 1961), 36. Google ScholarDigital Library
- 11 WAITE, W., AND SCHORR, H. A note on the formation of a free list. Comm. ACM 8 (Aug. 1964), 478. Google ScholarDigital Library
- 12 HALSTEAD, M. H. Machine-Independent Computer Programming. Spartan Books, Washington D. C., 1962. Google ScholarDigital Library
- 13 McBETH, J. M. On the reference counter method. Comm. ACM 6 (Sept. 1963), 575. Google ScholarDigital Library
Index Terms
- An efficient machine-independent procedure for garbage collection in various list structures
Recommendations
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. ...
Knotted list structures
ACM '61: Proceedings of the 1961 16th ACM national meetingIn (3) Perlis and Thornton describe a list structure language the central innovation of which is that the last word of each list specifies the location of the head of the list of which it is the terminal word. They call such list structures threaded ...
Age-based garbage collection
Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Comments