In last post, it was shown that in Lisp practice, the term "symbolic expression", shorter "sexpression", "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
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
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.
It is not obvious that symbolic expressions require infinitely many atoms; it could be only convenience. Perhaps Sexpressions 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.

The Similarities Between Axioms of Natural Numbers and Axioms of Sexpressions.
.
Subscribe to:
Post Comments (Atom)
The natural numbers can be easily understand by the graphs.Like if we have to represent set of positive and negative numbers simultaneously.Then we can make four quadrants and represent them.
ReplyDelete