An empirical study of list structure in Lisp

ABSTRACT

Static measurements of the list structure of five large Lisp programs are reported and analyzed in this paper. These measurements reveal substantial regularity, or predictability, among pointers to atoms and especially among pointers to lists. Pointers to atoms are found to obey, roughly, Zipf's law, which governs word frequencies in natural languages; pointers to lists usually point to a location physically nearby in memory. The use of such regularities in the space-efficient representation of list structure is discussed. Linearization of lists, whereby successive cdrs (or cars) are placed in consecutive memory locations whenever possible, greatly strengthens the observed regularity of list structure. It is shown that under some reasonable assumptions, the entropy or information content of a car-cdr pair in the programs measured is about 10 to 15 bits before linearization, and about 7 to 12 bits after.

REFERENCES

• 1: Barnett, J.A., and Long, R.E. The SDC LISP 1.5 system for IBM 360 computers. System Development Corp., Santa Monica, Calif., Jan. 1968.
• 2: Bates, M. The use of syntax in a speech understanding system. IEEE Trans. Acoustics, Speech, and Signal Processing 23, 1 (Feb. 1975), 112-117.
• 3: Daniel G. Bobrow, A note on hash linking, Communications of the ACM, v.18 n.7, p.413-415, July 1975 [doi>10.1145/360881.360920]
• 4: Daniel G. Bobrow , Jerry D. Burchfiel , Daniel L. Murphy , Raymond S. Tomlinson, TENEX, a paged time sharing system for the PDP - 10, Communications of the ACM, v.15 n.3, p.135-143, March 1972 [doi>10.1145/361268.361271]
• 5: Daniel G. Bobrow , Daniel L. Murphy, Structure of a LISP system using two-level storage, Communications of the ACM, v.10 n.3, p.155-159, March 1967 [doi>10.1145/363162.363185]
• 6: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 7: Deutsch, L.P. An interactive program verifier. Ph.D. Th., Comptr. Sci. Dep., U. of California, Berkeley, Calif., May 1973.
• 8: Deutsch, L.P. A LISP machine with very compact programs. Third Int. Joint Conf. on Artificial Intelligence, Stanford, Calif., 1973, pp. 697-703.
• 9: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 10: Wilfred J. Hansen, Compact list representation: definition, garbage collection, and system implementation, Communications of the ACM, v.12 n.9, p.499-507, Sept. 1969 [doi>10.1145/363219.363225]
• 11: Eric Charles Roy Hehner, Matching program and data representations to a computing environment., 1974
• 12: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 13: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 14: Quam, L.H. Stanford LISP 1.6 manual. Artificial Intelligence Proj., Stanford University, Stanford, Calif., Sept. 1969.
• 15: Reboh, R., and Sacerdoti, E. A preliminary QLISP manual. Tech. Note 81, Stanford Res. Inst. AI Center, Menlo Park, Calif., Aug. 1973.
• 16: Sacerdoti, E. The nonlinear nature of plans. Fourth Int. Joint Conf. on Artificial Intelligence, Tbilisi, Georgia, U.S.S.R., 1975, pp. 206-214.
• 17: Shannon, C.E. A mathematic theory of communication. Bell System Tech. J. 27 (July 1948), 379-423.
• 18: Smith, D.H., Masinter, L.M., and Sridharan, N.S. Heuristic DENDRAL: Analysis of molecular structure. In Computer Representation and Manipulation of Chemical Information, W.T. Wipke, S. Heller, R. Feldman, and E. Hyde, Eds., Wiley, New York, 1974.
• 19: Teitelman, W. INTERLISP Reference manual. Xerox Palo Alto Res. Center, Palo Alto, Calif., 1974.
• 20: Van der Poel, W.L. A Manual of HISP for the PDP-9. Technical U., Delft, Netherlands.
• 21: Weissman, C. LISP 1.5 Primer. Dickenson Pub. Co., Belmont, Calif., 1967.
• 22: Wilner, W.T. Design of the BI700. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 579-586.
• 23: Zipf, G.K. Human Behavior and the Prhwiple of Least Effort. Addison-Wesley, Reading, Mass., 1949.

INDEX TERMS

Keywords:
Lisp, Zipf's law, list linearization, list structure measurement, list structure regularity, pointer compression, pointer entropy