What is an S-Expression?

First let’s look at the type signature:

type S = Nil | Atom(String) | Cons(S,S)

The data structure has three cases: Nothing, a String, or a Pair. For historical consistency these cases are called Nil, Atom, and Cons. This data structure has been used effectively to represent a large diversity of data with a very simple structure.

In C we might define a representation for this as follows:

struct S {
   void* head,
   void* tail,
}

Pretty simple right?

S-Expressions are powerful enough to represent the Abstract Syntax Tree of just about any language. However they are simple enough to be represented by just two pointers. In practice this makes things go very smoothly from an implementation perspective.