Name
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. |
Year | DOI | Venue |
|---|---|---|
1977 | 10.1145/359423.359427 | Commun. ACM |
Keywords | Field | DocType |
pointer entropy,zipf's law,consecutive memory location,space-efficient representation,substantial regularity,car-cdr pair,reasonable assumption,natural language,empirical study,lisp,large lisp program,list linearization,list structure,list structure measurement,information content,observed regularity,list structure regularity,pointer compression,word frequency,zipf s law | Association list,Pointer (computer programming),Programming language,List,Linked list,List update problem,Computer science,Lisp,Theoretical computer science,Self-organizing list,Difference list | Journal |
Volume | Issue | ISSN |
20 | 2 | 0001-0782 |
Citations | PageRank | References |
61 | 40.82 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Douglas W. Clark | 1 | 1009 | 266.88 |
| Cordell Green | 2 | 431 | 677.34 |