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: NN
such that
  1. all numbers, except 1, are successors of some numbers, i.e.
    { successor(n) | nN } = N \ {1};
  2. the successor function is injection, or
    successor(n) = successor(m) => n = m;
  3. if S is a set of numbers such that
    1. S contains all initial numbers (i.e. 1);
    2. 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
such that
  1. all symbolic expressions, except atoms, are conses, i.e.
    { cons(x, y) | x, ySEXPR } = SEXPR \ A;
  2. the function cons is injection, i.e.
    cons(n, p) = cons(m, q) => n = m and p = q;
  3. if S is a set of symbolic expressions such that
    1. S contains all atoms;
    2. 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.
  1. There is one "base element" for numbers and infinitely many for S-expressions.
  2. 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".

Implementing Data Structures with Symbols.


Implementing Data Structures with Symbols

Original Lisp had only symbols as atoms. Symbol names, if used on the same way variables are used in mathematics, are flexible enough to support wide variety (all?) data structures.

For instance, matrices 2 x 2 can be implemented with symbols as a11 instead of a[1,1] in some other language, or (a 1 1) in Lisp and names could be created as needed.

The code will be more complicated and less efficient than if matrices are directly supported by language, but neither one is essential problem - complexity of the code can be "abstracted away" with functions, and computational complexity is increased only for factor of constant * log n where n is the number of used symbols (if symbol reaching in Lisp is implemented efficiently.) Newlisp code follows.

(define (matrix-element m i j)
  (sym (append (string m) (string i) (string j))))

(define (set-matrix m m11 m12 m21 m22)
  (for(i 1 2)
    (for(j 1 2)
      (set (matrix-element m i j)
           (nth (+ (* 2 (- i 1)) (- j 1))
                (list m11 m12 m21 m22))))))
(define (println-matrix m)
  (for(i 1 2)
    (for(j 1 2)
       (println m "[" i "," j "]=" 
          (eval (matrix-element m i j))))))
(define (multiply-matrix a b c)
  (for(i 1 2)
    (for(j 1 2)
      (set (matrix-element c i j) 0)
      (for(k 1 2)
         (set (matrix-element c i j)
              (+ (eval (matrix-element c i j))
                 (* (eval (matrix-element a i k))
                    (eval (matrix-element b k j)))))))))

(set-matrix (quote X) 1 2 3 4)
(set-matrix (quote Y) 2 3 4 5)
(multiply-matrix (quote X) (quote Y) (quote Z))
(println-matrix (quote Z))

Program output


More on Another Encoding of S-expressions in Symbols.


More on Another Encoding of S-expressions in Symbols

In previous post, I have shown another interesting method for encoding of S-expressions into symbols. In this post, I'll show how it can be implemented in Lisp dialects that print symbols on different way from S-expressions, i.e. encapsulated in vertical bars or other symbols (Common Lisp, ISLisp, Picolisp, some implementations of Scheme). This is, normally, good feature. However, repeated encoding of the symbols results in exponential growth. So, we must get rid of those vertical bars inside our symbols.

The code, here in Common Lisp, is sort of trickier than it is in Newlisp or it would be in Clojure.
(defun decode-deep (r)
  (cond ((symbolp r) (let((result (read-from-string (string r))))
                        (if (symbolp result)
                            (decode-deep result))))
        ((listp r) (mapcar (quote decode-deep) r))))

(defun sexpr->symbol (r) 
  (make-symbol (write-to-string (list 'q (decode-deep r)))))

(defun encode-deep (r)
  (cond ((symbolp r) r)
        ((listp r)(if (eq (first r) (quote q))
                      (make-symbol (write-to-string r))
                      (mapcar (quote encode-deep) r)))))

(defun strip-q (r) (first (rest r)))

(defun symbol->sexpr (r) 
  (encode-deep (strip-q (read-from-string (string r)))))


[43]> (setq q0 (sexpr->symbol (list (quote b) (quote c))))
#:|(Q (B C))|
[44]> (setq s (sexpr->symbol (list (quote a) q0)))
#:|(Q (A (Q (B C))))|
[45]> (setq s0 (symbol->sexpr s))
(A #:|(Q (B C))|)

Another Encoding of S-expressions in Symbols.


Another Encoding of S-expressions in Symbols.
Unlike encoding from the last post, this one maintains form of S-expression. If e is S-expression, then its code is symbol (Q e).

Encoding is relatively simple, because built in functions for conversion of symbols and strings into symbols can be used; especially if symbols converted to strings are not encapsulated within vertical bars or quotation marks. Decoding is slightly more complicated. For instance, symbol

(Q (a (Q b)))

should be decoded into list (a (Q b)) where (Q b) isn't list, but symbol. Hence, built in conversion functions are not enough, but one must define his own "code walker." The code in Newlisp follows.

(define (sexpr->symbol r) (sym (string (list (quote Q) r))))

(define (qlist? r)
    (and (list? r)
         (not (empty? r))
         (= (first r) (quote Q))))
(define (symbol->sexpr r)
           (cond ((symbol? r) r)
                 ((qlist? r) (sym (string r)))
                 ((not (qlist? r)) (map codewalker r))))))
     (codewalker (last (read-expr (string r))))))

> (setq s (sexpr->symbol (quote (a b))))
(Q (a b))
> (symbol? s)
> (setq q0 (sexpr->symbol (quote b)))
(Q b)
> (setq s (sexpr->symbol (list (quote a) q0)))
(Q (a (Q b)))
> (symbol? s)
> (setq s0 (symbol->sexpr s))
(a (Q b))
> (symbol? s0)
> (symbol? (last s0))

Behaviour of Q strongly reminds on QUOTE.

More Sophisticated Encoding of S-exprs into Symbols.

More Sophisticated Encoding of S-exprs into Symbols
Encoding of S-expressions into symbols is frequent topic of discussion in this blog. It is motivated by the idea that names should be equally flexible as S-expressions. (Actually, it might be the best if not only every symbol is S-expression, but also every S-expression is the symbol. OK, it is almost mystical statement.)

Trivial encoding was demonstrated in last post: S-expression is encoded in symbol which has exactly same characters as printed representation of S-expression. For instance, S-expression (+ a b) is encoded into symbol (+ a b). This trivial encoding has some limitations. For instance, if we look at symbol

((+ a b) c)

and try to decode it, we'll find that it cannot be determined whether (+ a b) is S-expression, or it is symbol. In some Lisp dialects (Common Lisp, Picolisp, ISLisp) there is no such problem. Symbol (+ a b) is written as |(+ a b)| so difference between S-expression and symbol is obvious. However, in these dialects, repeated encoding results in the symbols that grow exponentially.

In this post more sophisticated encoding, without that problem, is presented. Let us define encoding k, such that for every S-expression e, k(e) is defined as follows.
  1. If e is symbol, then k(e) = e;
  2. if e = (e1 ... en) then k(e) = [k(e1) k(e2) ... k(en)];
Semi-colon is part of the symbol. For instance

k(a) = a;
k((a b)) = [k(a) k(b)]; = [a;b;];

If only codes of the S-expressions contain characters [, ] and ;, then encoding k is injection, i.e. for two S-expressions e and f,

k( e ) = k( f ) => e = f.

Furthermore, there is no exponential explosion in case of multiple encoding. For instance,

k((a b)) = [a;b;];
k(k((a b))) = [a;b;];;
k(k(k((a b)))) = [a;b];;;

Here is implementation of encoding and decoding in R5RS Scheme.
(define (sexpr->string L)
     (if (symbol? L) (symbol->string L)
                        (apply string-append
                               (map sexpr->string L))
(define (sexpr->symbol L)
  (string->symbol (sexpr->string L)))
(define (string->sexpr S)
  (let((S1 (substring S 0 (- (string-length S) 1))))
    (if (equal? (string-ref  S1 (- (string-length S1) 1)) #\])
      (let((substring-begin 1)
           (level 0)
           (result (list)))
        (do ((i 1 (+ i 1)))
            ((= i (string-length S1)) result)
          (if (and (= level 0)
                   (equal? (string-ref S1 i) #\;)
                   (not (equal? (string-ref S1 (+ i 1)) #\;)))
              (set! result
                    (append result
                            (list (string->sexpr
                                    (substring S1
                                               (+ i 1))))))
              (set! substring-begin (+ i 1))))
          (cond ((equal? (string-ref S1 i) #\[)
                 (set! level (+ level 1)))
                ((equal? (string-ref S1 i) #\])
                 (set! level (- level 1))))))
      (string->symbol (substring S 0 (- (string-length S) 1))))))
(define (symbol->sexpr s)
  (string->sexpr (symbol->string s)))


> (sexpr->symbol (quote (a b)))
> (define s2 (sexpr->symbol (quote (|[a;b;];| c))))
> s2
> (symbol->sexpr s2)
(|[a;b;];| c)

Exponential Explosion of Escape Characters.

Exponential Explosion of Escape Characters

This time, Common Lisp:

? (setf q nil)


? (setf q (make-symbol (write-to-string q)))


? (setf q (make-symbol (write-to-string q)))


? (setf q (make-symbol (write-to-string q)))


? (setf q (make-symbol (write-to-string q)))


? (setf q (make-symbol (write-to-string q)))


? (setf q (make-symbol (write-to-string q)))


? (setf q (make-symbol (write-to-string q)))


? (setf q (make-symbol (write-to-string q)))


? (setf q (make-symbol (write-to-string q)))


? (setf q (make-symbol (write-to-string q)))





The specificity of Lisp is, maybe, best visible on problems that require processing of data naturally represented as S-expressions. An example of such problem is "Probability that random propositional formula is tautology." In this post, the variation of classical example - symbolic differentiation - is presented: newLISP (and it is very similar in other Lisps) program that computes the tangent of the graph of the function f of single variable, defined as composition of elementary functions (+, -, sin, cos ...) in given point x0. The tangent of the function f in x0 is defined as linear function

y(x) = a·(x - x0) + b,

where a = f '(x0) and b = f(x0). The program consists of:

  • The function tangent that accepts two arguments: the function f in form of lambda list and the floating point number x0. The function tangent analyzes the code of the function f, calculates the values a and b according to mathematical definition of tangent (see above) and constructs the code of the function

    (lambda(x)(+. (*. a (-. x x0)) b))

    where symbols a, b and x0 are replaced with their respective values; that function is then returned as result of the function tangent. The implementation is very short, but it delegates main part of the work to the function d.
  • The function d accepts two arguments: formula and variable. It returns the expression obtained by symbolic differentiation of the formula for given variable. It is main function in this program, typical recursive "code walking" through formula. Simple "domain specific language" is used for descriptions of the rules  for symbolic differentiation that should be applied, for example

    (+. (*. df g) (*. f dg))

    for multiplication. The application of  rules for symbolic differentiation frequently give result that can be simplified. For instance, derivation of (*. 2 x) is

    (+. (*. 0 x) (*. 2 1))

    so function simplify is called when appropriate.
  • The function simplify accepts only one argument: symbolic expression formula. It analyzes and simplify formula, again, using typical recursive "code walking". For instance, S-expression (- x x) is simplified to 0. There are infinitely many possible rules for simplification; the function performs only few of these. The function uses eval at one place: if some expression contains only operators and constants, but not variables then the easisest way to simplify it is to eval it. (One might speculate that simplify is generalized eval.) Simplification is, actually, not necessary for computation of the tangent. However, its use in the context of symbolic differentiation is reasonable.
Few operators from my library are used; function expand// i.e. parallel expand, fexpr println= for convenient printing and floating point arithmetic operators +., -., *. and /., synonymous for built-in add, sub, mul and div. These functions are not essential.

The graph of the complicated function and tangent on the curve suggests that program, generally, works.

(setf f0 (lambda(x)
           (+. (sin (*. 12 x))
               (cos (*. 32 x))
               (tan (*. x 1.4))
               (asin x)
               (acos  x)
               (atan x)
               (*. x (cos (/. 7 x)))
               (sqrt (/. 9 x))
               (pow x x)
               (*. x (sinh x))
               (*. x (cosh x))
               (asinh x)
               (sin (acosh (+. x 1)))
               (atanh x))))
(setf x0 0.4)
(println= (tangent f0 x0))
; (tangent f0 x0)=(lambda (x) (+. (*. -21.491 (-. x 0.4)) 10.252))


Finally, the code:
(setf [print.supressed] true [println.supressed] true)
(load "")
(setf [print.supressed] nil [println.supressed] nil)

(define (tangent f x0)
   (letn((variable           (first (first f)))
         (expression         (last f))
         (derived-expression (d expression variable))
         (a                  (eval (expand derived-expression
                                           (list (list variable x0)))))
         (b                  (f x0)))
       (expand// '(lambda(x)(+. (*. a (-. x x0)) b))
                  'a 'b 'x0)))

(define (d formula variable)
      ((= formula variable) 1)
      ((atom? formula) 0)
      ((list? formula)
       (letn((operator (first formula))
             (operands (rest formula))
                 (letn((flatexpr (flat expr))
                       (f  (if (find 'f  flatexpr)(operands 0)))
                       (df (if (find 'df flatexpr)(d f variable)))
                       (g  (if (find 'g  flatexpr)(operands 1)))
                       (dg (if (find 'dg flatexpr)(d g variable))))
                   (expand// expr 'f 'df 'g 'dg)))))

         (case operator 

           (+. (cons '+. (map (lambda(op)(d op variable)) operands)))
           (-. (cons '-. (map (lambda(op)(d op variable)) operands)))

           (*. (case (length operands)
                 (1    (lexpand 'df))
                 (2    (lexpand '(+. (*. df g) (*. f dg))))
                 (true (d (list '*. (first operands)
                                    (cons '*. (rest operands)))

           (/. (case (length operands)
                 (1    (d (list '/. 1 (first operands)) variable)) 
                 (2    (lexpand '(/. (-. (*. df g) (*. f dg)) (*. g g))))
                 (true (d (list '/.  (first operands)
                                     (cons '*. (rest operands)))

           (pow (d (lexpand '(exp (*. g (log f)))) variable))
           (exp (lexpand '(*. f df)))
           (log (if (= (length operands) 1)
                    (lexpand '(/. df f))
                    (d (lexpand '(/. (log f) (log g))) variable)))

           (sqrt  (lexpand '(*. 0.5 df (/. 1 (sqrt f)))))
           (sin   (lexpand '(*. (cos f) df)))
           (cos   (lexpand '(*. (-. (sin f)) df)))
           (tan   (lexpand '(/. df (pow (cos f) 2))))
            (asin (lexpand '(/. df (sqrt (-. 1 (*. f f))))))
           (acos  (lexpand '(-. (/. df (sqrt (-. 1 (*. f f)))))))
           (atan  (lexpand '(/. df (+. 1 (*. f f)))))
           (sinh  (lexpand '(*. (cosh f) df)))
           (cosh  (lexpand '(*. (sinh f) df)))
           (tanh  (lexpand '(*. (-. 1 (pow (tanh f) 2)) df)))
           (asinh (lexpand '(/. df (sqrt (+.(*. f f) 1)))))
           (acosh (lexpand '(/. df (sqrt (-. (*. f f) 1)))))
           (atanh (lexpand '(/. df (-. 1 (*. f f)))))


(define (simplify formula)
    ((atom? formula) formula)
    ((list? formula)
     (letn((operator (first formula))
           (operands (map simplify (rest formula)))
           (formula (cons operator operands)))

         ; if all operands are constants, then 
         ; simplified formula is evaluated formula
         ((for-all number? operands)(eval formula))
         ; (*. x), (+. x) => x
         ((and (or (= operator '*.) (= operator '+.)) 
               (= (length operands) 1))
           (first operands))
         ; (*. ... 0 ...) => 0  
         ((and (= operator '*.) (find 0 operands)) 0)
         ; (*. ... 1 ...) => (*. ...)
         ((and (= operator '*.) (find 1 operands))
          (simplify (clean (curry = 1) formula)))
         ; (+. ... 0 ...) => 0
         ((and (= operator '+.) (find 0 operands))
          (simplify (clean zero? formula)))
         ; (-. (-. ...)) => ...
         ((match '(-. (-. ?)) formula)
           (last (last formula)))
         ; (-. minuend ...)
         ((and (= operator '-.) (> (length operands) 1))
          (letn((minuend (first operands))
                (subtrahends (rest operands))
                (subtrahend  (simplify (cons '+. subtrahends))))
            (cond ((zero? minuend)        (simplify (list '-. 
                  ((zero? subtrahend)     minuend)
                  ((= minuend subtrahend) 0)
                  (true                   (list '-. minuend 
         ; (/. (/. ...))
         ((match '(/. (/. ?)) formula) (last (last formula)))
         ; (/. dividend ...)
         ((and (= operator '/.) (> (length operands) 1))
          (letn((dividend (first operands))
                (divisors (rest operands))
                (divisor  (simplify (cons '*. divisors))))
            (cond ((zero? dividend)     0)
                  ((= divisor 1)        dividend)
                  ((= divisor -1)       (simplify (list '-. dividend)))
                  ((= dividend divisor) 1)
                  (true                 (list '/. dividend divisor)))))
         (true formula))))))