S-expressions

Also known as 'symbolic expressions' are a type of notation used to represent structured data.

An S-expression can be defined recursively as one of the following:

1. An atom (described below) -or-
2. An ordered pair of S-expressions

Atoms

An atom can represent any valid object other than an ordered pair. Although valid atoms differ by context, they generally comprise numbers and symbols.

Ordered Pairs

An ordered pair can be represented by its two members separated by a whitespace delimited '.' enclosed by a pair of parenthesis. For example, an ordered pair of atoms x and y can be represented as:

(x . y)

Lists

Lists are a special kind of S-expression defined recursively as either:

1. An empty list -or-
2. An ordered pair where the second member is also a list

An empty list can be represented as an empty pair of parenthesis:

()

A non-empty list can be represented as a chain of nested pairs. For example, a list containing the atoms x, y and z can be represented as:

(x . (y . (z . ())))

A list can also be represented by its members delimited by whitespace and enclosed by a single pair of parenthesis. For example, the same list from the previous example can be represented as:

(x y z)

Association Lists

Lists of ordered pairs can be used to associate keys with values. For example the association of keys A, B and C with values 1, 2 and 3 can be represented as follows:

Trees

Nested lists can be used to represent the nodes of a tree structure of arbitrary complexity. For example, a simple binary tree can be represented as follows:

Cycles

In some contexts, a label may be assigned to an S-expression which can be referenced by other S-expressions. If an S-expression contains a reference to itself, it is said to comprise a 'cycle'. For example, a cycle containing the repeating symbols: o u r o b o r u s, can be represented as:

#0=(o u r o b o r u s . #0#)

List Processing (LISP)

Lists can be used to express a universal method of computation that invokes a function referenced by the first member of a list and supplies any remaining members as arguments to the function. For example, three factorial may be expressed as:

(* 3 2 1)

-or-

(factorial 3)