A method for overlapping and erasure of lists

ABSTRACT

An important property of the Newell Shaw-Simon scheme for computer storage of lists is that data having multiple occurrences need not be stored at more than one place in the computer. That is, lists may be “overlapped.” Unfortunately, overlapping poses a problem for subsequent erasure. Given a list that is no longer needed, it is desired to erase just those parts that do not overlap other lists. In LISP, McCarthy employs an elegant but inefficient solution to the problem. The present paper describes a general method which enables efficient erasure. The method employs interspersed reference counts to describe the extent of the overlapping.

REFERENCES

• 1: COLLINS, G. E. Tarski's decision method for elementary algebra. Proc. of the Summer Institute of Symbolic Logic, 1957, pp. 64-70.
• 2: H. Gelernter , J. R. Hansen , C. L. Gerberich, A Fortran-Compiled List-Processing Language, Journal of the ACM (JACM), v.7 n.2, p.87-101, April 1960 [doi>10.1145/321021.321022]
• 3: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 4: NEWELL, A.; SHAW, J. C.; AND SIMON, H. A. Empirical ex plorations of the logic theory machine. Proc. of the 1957 Western Joint Computer Conference, pp. 218-230.
• 5: TARSKI, A. A Decision Method for Elementary Algebra and Geometry. University of California Press, 1951.