{S-expression Postulates and Notation} Pages 4, 41
S-expressions form a number system analogous to that for the natural numbers. Each can be used to encode arbitrary strings of symbols by means of "Gödelization", but the S-expression encoding is usually far more convenient than the numerical encoding.
We repeat here the informal characterization of Peano's postulates and the analogous postulates for S-expressions from [Levin]:
The Postulates of Arithmetic
1. Zero is a number.
2. The successor of a number is a number.
3. Zero is not the successor of any number.
4. No two numbers have the same successor.
5. (Induction Principle) Any property which is true for zero, and is such that if it is true for some number it is also true for the successor of that number, it is true for all numbers.
Zero is notated as 0, and the successor of any number N is notated as N'. As a convenience we define alternative notations for numbers other than zero, such as decimal place-value notation. Thus for 0''''''''''''' we often write 13.
The Postulates for S-expressions
1. Atoms are S-expressions.
2. The cons of any two S-expressions is an S-expression.
3. An atom is not the cons of any two S-expressionss.
4. If α differs from β, or if γ differs from δ, then cons of α and γ differs from cons of β and δ.
5. (Induction Principle) Any property which is true of all atoms, and is such that if it is true for two S-expressions it is also true for their cons, is true for all S-expressions.
Atoms are notated as strings of letters and digits. The cons of two S-expressions α and β is notated (α . β). As a convenience, we define alternative notations for some commonly used forms of S-expression, such as list notation. The atom NIL is called the "empty list"; we write it as (). If (α β γ ... δ) is (the notation for) a list π (where the "..." is meant as a meta-syntactic ellipsis), then the cons of ε and π is written (ε α β γ ... δ). We also define quotation notation, in which (QUOTE α) is written as 'α.
(This definition of S-expressions applies to pure LISP, which has no side effects. In Part Two, when the RPLACA and RPLACD operators are introduced, the phrase "the cons of" will not be well-defined.)
