The Similarities Between Axioms of Natural Numbers and Axioms of S-expressions.

.

The Similarities Between Axioms of Natural Numbers and Axioms of S-expressions In last post, it was shown that in Lisp practice, the term "symbolic expression", shorter "s-expression", "sepxr", "sexp" is used on few different, although similar meanings. It is not unusual. Other terms, even mathematical ones, like "lines" or "numbers" are not uniquely defined as well. Ambiguity usually motivates the search for the essence of the discussed entities; the result of the search is axiomatic theory. For example, the axioms of natural numbers are developed in late 1880's by R. Dedekind and G. Peano. Axioms of Natural Numbers There is a set N ("numbers"), distinctive element of the N denoted with 1 ("base", "initial number") and mapping successor: N → N such that all numbers, except 1, are successors of some numbers, i.e. { successor(n) | n ∈ N } = N \ {1}; the successor function is injection, or successor(n) = successor(m) => n = m; if S is a set of numbers such that S contains all initial numbers (i.e. 1); if S contains n, then S contains successor(n); then S contains all numbers. Search for axioms of symbolic expressions might be equally justified. I designed following axioms (version in which lists are only shorter way of writing "dotted pairs") to emphasize the similarities to axioms of natural numbers. Axioms of Symbolic Expressions There is a set SEXPR ("symbolic expressions"), infinite set of distinct elements of the SEXPR denoted with A ("atoms") and mapping cons: SEXPR × SEXPR → SEXPR such that all symbolic expressions, except atoms, are conses, i.e. { cons(x, y) | x, y ∈ SEXPR } = SEXPR \ A; the function cons is injection, i.e. cons(n, p) = cons(m, q) => n = m and p = q; if S is a set of symbolic expressions such that S contains all atoms; if S contains n and p then S contains cons(n, p); then S contains all symbolic expressions. Symbolic expressions in all three meanings satisfy the axioms; cons structures satisfy axiom (3) only if cyclic structures are not allowed, like in original, McCarthy's Lisp. I'm not aware of unintended, perverse models that satisfy given axioms; but I am not sure that such models do not exist. There are only two differences between these axiom systems. There is one "base element" for numbers and infinitely many for S-expressions. The function "successor" is function of a single variable; the function "cons" is function of two variables. It is not obvious that symbolic expressions require infinitely many atoms; it could be only convenience. Perhaps S-expressions like (A . (B . (C . D))) can be used instead of symbols like ABCD, eliminating need for infinitely many atoms. It remains unclear why these two systems of axioms are so similar.

Three Meanings of The Term 'S-expression.'

.

Three meanings of the term 'S-expression' "Symbolic expressions" or "S-expressions" are the basic data type in Lisp. Particularly, Lisp programs are S-expressions as well. The notion has immense importance in Lisp community. Surprisingly, designers of recent Lisp dialects avoid the term "symbolic expression" or "S-expression". It is used once in Picolisp documentation; only twice, almost accidentally, in CLtL2, and it isn't used in CL Hyperspec or recent Scheme standards. Clojure, according to its web site "extends the code-as-data system beyond parenthesized lists (s-expressions) to vectors and maps." Only Newlisp documentation appear to regularly uses the term. However, the term S-expression is still extensively used in daily communication and literature. Unfortunately, there is no universal, unique meaning. Inconsistent use is sometimes noted; for instance, in P. Siebel's "Practical Common Lisp." More frequently, it is ignored. For J. McCarthy, S-expression is finite sequence consisting of dots and parentheses and symbols. The symbols, truly atomic, cannot be analysed on characters. For instance, S-expression (left.right) is sequence of five elements: (, left, ., right and ). More often1, S-expression is seen as sequence of characters. In that meaning, S-expression (left . right) is sequence consisting of 14 elements. The most usually2, S-expression is data structure, perhaps tree consisting of cons cells and symbols. In that meaning S-expression (left . right) is cons cell, containing adresses of symbols left and right in memory. 1  For instance, in E. Shaphiro, "Common Lisp - an interactive approach"; F. Turbak and D. Gifford, "Design concept of programming languages." 2  For instance, in J. and G. Sussman and H. Abelson, "SICP"; D. Touretsky, "Common Lisp - A gentle introduction to symbolic computation"; R. Finkel, "Advanced programming languages design".