Multiword list items

ABSTRACT

The list concept as originally proposed by Newell, Simon and Shaw specified single computer words as elements of a list. This report describes the use of two or more consecutive words as one element. Such use results in a considerable saving in both the space required to hold a given amount of data, and in the execution time required to perform a given process on the data.Following a brief description of standard list structures with single-word items, the multiword items are introduced. Then variable-length items are described, along with the corresponding space-utilization problems. Finally, several examples are given to illustrate the use of multiword lists.This paper attempts to draw together various recent papers which have applied some of these concepts in different ways, and indicate how they relate to the more general problem.

REFERENCES

• 1: NEWELL, A., AND SHAW, J. C. Programming the logic theory machine. Proc. Western Joint Comput. Conf., 1957.
• 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: 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]
• 4: A. Evans, Jr. , A. J. Perlis , H. Van Zoeren, The use of threaded lists in constructing a combined ALGOL and machine-like assembly processor, Communications of the ACM, v.4 n.1, p.36-41, Jan. 1961 [doi>10.1145/366062.366081]
• 5: H. J. Gray, Jr. , N. S. Prywes, Outline for a multi-list organized system, Preprints of papers presented at the 14th national meeting of the Association for Computing Machinery, September 01-03, 1959, Cambridge, Massachusetts [doi>10.1145/612201.612251]
• 6: 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]
• 7: NEWELL, A. (Ed.) Information Processing Language---V Manual. Prentice-Hall, 1961.
• 8: H. D. Baecker, Mapped list structure, Communications of the ACM, v.6 n.8, p.435-438, Aug. 1963 [doi>10.1145/366707.367528]
• 9: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 10: Henry J. Bowlden, A list-type storage technique for alphanumeric information, Communications of the ACM, v.6 n.8, p.433-434, Aug. 1963 [doi>10.1145/366707.367527]
• 11: ILIFFE, J. K., AND JODEIT, J. G. A dynamic storage allocation scheme. Comput. J. (Oct. 1962).