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