# 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:

 ( (A . 1) (B . 2) (C . 3) )

## 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:

 (root (branch (leaf) (leaf)) (branch (leaf) (leaf)))

## 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)