S-expressions: The most powerful data structure available

Which is the most powerful data structure?

S-expressions are the most powerful data structure currently available, suitable for representing arbitrary complex data structures, and that basically means absolutely any kind of information.

S-expressions, or S-exps (S stands for symbolic), are best known for their use in the Lisp programming language. The most apparent feature of LISP to a non-initiated is the use of S-expressions as parenthesized prefix notation (sometimes known as Cambridge Polish notation).

Why S-expressions?

The most powerful/general information representation (or data structure or concept) is the graph. A graph allows arbitrary information to be associated with one or more other arbitrary information (nodes). Considering a graph can also have directed , labeled edges, any information (including code, any kind of n-dimensional data, SQL database, etc) can be represented using S-expressions.

Since S-expressions can represent general directed graphs, not just trees, they are the most powerful data structure available -- at least until somebody discovers something better.

And what about LISP?

That is one of the reasons why LISP is considered to be the most powerful, or expressive, language available -- even now, 50 years after its discovery. As a matter of fact, LISP is based directly on S-expressions. More than that, in LISP, S-expressions are evaluatable units.

An example of LISP

(defun fib-trec (n)
  "Tail-recursive Fibonacci number function"
  (labels ((calc-fib (n a b)
                     (if (= n 0)
                       a
                       (calc-fib (- n 1) b (+ a b)))))
    (calc-fib n 0 1)))

"Once you get S-expressions, you get Lisp. All of it. All that remains is to read a doc and find out how construct X modifies the sexps you give it. Conceptually, S-expression evaluation is all that you need to understand.

Along the way you realise how so much of the power of the language comes from this S-expression manipulation, how transparent it is, what all those people meant by 'writing in the parse tree' (PG) and why they raved about it.

Once you get it, you can never go back. To do so would be wilfully turning away from the truth and in doing so you have broken the hacker ethic. You are (and I have) allowed to temporarily forget, so long as at the back of your mind you remember that 'there is a better way', or that you have yet to find the path."

[from ALU Wiki: The Road to Lisp Survey]