[FOM] Arithmetic-free theory of formal systems?

[John McCarthy]

Lisp lists are better for expressing symbolic information than
strings.

Consider x + yz, represented in Lisp by (+ (* y z)) and represented in
a computer by a pointer structure.  In a string language, one must
parse to discover that x + yz is primarily a sum, whereas in Lisp a
sum is identified by (car exp) = (quote +).  More generally, one can
use an abstract syntax, with predicates for identifying what kind an
expression is and analytic abstract functions for finding the
constitutents of an expression and synthetic abstract functions for
building them out of parts.

These matters, including abstract syntax, are discussed in my 1963
paper "Towards a mathematical science of computation" given at the
1962 IFIPS meeting and on the web as
http://www-formal.stanford.edu/jmc/towards.html.