An Empirical Study of List Structure in Lisp 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 poin ters to atoms and especially among poin ters to lists. Pointers to atoms are found to obey, roughly, Zipf's law, which governs word frequencies in natural languages; poin ters to lists usually poin t 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. CACM February, 1977 Clark, D. W. Green, C. C. list structure measurement, Lisp, list structure regularity, poin ter compression, Zipf's law, list linearization, poin ter entropy 3.69 4.29 4.34 4.6 5.6 CA770202 JB December 30, 1977 2:55 AM 2855 5 2998 2944 5 2998 2998 5 2998 2998 5 2998 2998 5 2998 3106 5 2998 1549 6 2998 1549 6 2998 1826 6 2998 210 6 2998 210 6 2998 1972 6 2998 1972 6 2998 2513 6 2998 2665 6 2998 2766 6 2998 2766 6 2998 2833 6 2998 2833 6 2998 2855 6 2998 2954 6 2998 2998 6 2998 2998 6 2998 2998 6 2998