Data representations

If you forget for a moment that it's used as syntax in LISP, S-expressions are pretty neat.

Most programming languages use a mix of arrays, structures, vectors, lists, tuples, tables and/or objects to represent and handle data structures. Each of them are similar yet different aggregate structures. With S-expressions, however, there are only pairs or atomic data (doesn't contain a reference to any other value). What are lists? Ordered pairs. What are tuples? Lists. What are vectors? Lists. What are structs? Tuples with compile-time field-labels (implicit accessor procedures).

Now, some of you are complaining ``lists have linear complexity''! Well, ordered pairs only have to behave as linked pairs. They can be allocated in sequential memory locations for constant lookup. CDR-coding makes this automatic and the job of the GC (and CDR-coding is simple if cdrs aren't writable (like arrays or tuple suffixes)).

Good languages only need one tool for creating composite structures: ordered pairs.

Source: Anatomy of Lisp

>>1

Real Lisp S-expressions also contain data types other than pairs: symbols, strings, numbers, vectors, structs, ...

Vector example: #(1 2 3 4 ..).  When this is read, it constructs an array in memory which is indexable in O(1) time.

I think you best skip this Anatomy of Lisp bullshit.

Ordered pairs are no silver bullet data structure but they're good as a very cheap glue in garbage collected environment for small pieces of data. Big nearly-static homogenous arrays are implemented as native arrays on most Common Lisps and they're my favourite. Many programs can be reduced to destructive transformations on such arrays and it's easy to debug and parallelise (as >>3 said) and performs extremely well with current cache architectures. I think some call it ``data-oriented design''.
Back on topic, Lisp is great not because it uses lists as its only representation of data (it doesn't); it's because it uses them for code and provides the programmer with all the necessary glue for meta-programming: explicit progns and fully programmable hooks into the reader. Abstracting lists as lists in the way described in >>1 is a gross underuse of Lisp's abilities.

Summary: abstract code instead of data whenever possible.