S-expression

An S-expression (S stands for symbolic) is a convention for representing data or an expression in a computer program in a text form. S-expressions are used in the Lisp programming language and Lisp-derived languages such as Scheme and DSSSL, and as mark-up in communications protocols like IMAP and John McCarthy's CBCL. The details of the syntax and supported data types vary in the different languages, but the most common feature is the extensive use of prefix notation with explicit use of brackets (affectionately known as Cambridge Polish notation).

S-expressions are used for both code and data in Lisp (see McCarthy Recursive Functions of Symbolic Expressions at http://www-formal.stanford.edu/jmc/recursive/recursive.html ). S-expressions were originally intended only as machine representations of human-readable M-expressions, but Lisp programmers soon started using S-expressions as the default notation.

S-expressions can either be single objects such as numbers, LISP atoms including the special atoms nil and t, or cons pairs, written as (x . y). Longer lists are made up of nested cons pairs, for example (1 . (2 . (3 . nil))) which can also be written more intelligibly as (1 2 3).

Program code can be written in S-expressions, using prefix notation. An extra piece of syntactic sugar for writing Lisp programs is that the common expression (quote x) can be written with the abbreviation 'x.

Example in Common Lisp:

(defun factorial (x)
   (cond ((zerop x)  1)
          (t (* x (factorial (- x 1))))))

Example in Scheme:

(define (factorial x)
    (if (zero? x) 1
        (* x (factorial (- x 1)))))