S-expression (or sexp, for "symbolic expression") is a data structure introduced by John McCarthy in the programming language Lisp, which is also used in Scheme   and certain other programming languages.
There are essentially two different syntaxes for representing S-expressions: internal, so-called "dotted-pair notation", which mirrors the way the S-expressions are stored in computer's memory, and external notation, based on nested lists, which is usually used when S-expressions are either input or output from/to the file system or programmer's console. Below, context-free grammars are given for slightly restricted versions of both syntaxes.
First, for the internal "dotted pair"-syntax:
and for the external "nested list"-syntax:
Here may stand for any atomic item, e.g. for numbers and symbols, including also an empty list (which is called NIL in Lisp parlance).
The above definitions produce isomorphic structures. The isomorphism between the two variant syntaxes is realised by the function which maps from the dotted pair to list syntax as follows:
As an example, function maps the internal, dotted S-expression to an external, dotless list and the internal, dotted S-expression to an external, dotless list of two elements.
S-expressions with only ( )'s occurring as their terminals
If we restrict our attention to that subset of S-expressions where the only allowed atoms (i.e. terminal nodes) are 's, then the above grammars are reduced to:
for the internal syntax, and
for the external syntax.
Representing functions whose domains are S-expressions as integer sequences
To represent as an integer sequence a function whose domain (and possibly also its range) is a set of all S-expressions, and whose behaviour does not depend on the particular identity of the atomic elements of S-expression, it is sufficient to record how it acts on the subset defined above, which consists of S-expressions having only 's as their terminal nodes. For this, one should fix a total ordering for all such S-expressions (that is, plane binary trees or parenthesizations) so that each can be referred with an unique integer in range . The sequence A014486 provides us with a very natural ordering, where such structures are ordered in size-wise and lexicographic order.
Thus, to create an integer sequence from a function whose domain is a set of all S-expressions, and whose range is a set of integers or natural numbers, one applies the function to each S-expression constructed from A014486, and records the integer returned by the function as the th term of the sequence. See e.g. A057514, A057515, A126306, A126307 and A127284.
There are also several functions, whose range is also a subset of S-expressions, in which case the corresponding integer sequences record the positions of their results in A014486 after the same mapping.
- J. McCarthy, Recursive Functions of Symbolic Expressions. (Note the many differences from the modern Lisp-syntax!)
- Revised 6 Report on the Algorithmic Language Scheme, Chapter 4, Lexical syntax and datum syntax, "Pairs and lists."
- Ibid, Section 11.9, "Pairs and lists."
- MIT/GNU Scheme 9.1 Documentation, "Lists."