S-expression

The recursive clause of the definition means that both this representation and the S-expression notation can represent any binary tree.

However, the representation can in principle allow circular references, in which case the structure is not a tree at all, but a cyclic graph, and cannot be represented in classical S-expression notation unless a convention for cross-reference is provided (analogous to SQL foreign keys, SGML/XML IDREFs, etc.).

Modern Lisp dialects such as Common Lisp[2] and Scheme[3] provide such syntax via datum labels, with which objects can be marked, which can then recur elsewhere, indicating shared rather than duplicated structure, enabling the reader or printer to detect and thus trigger evaluation or display of cycles without infinitely recursing The definition of an atom varies per context; in the original definition by John McCarthy,[1] it was assumed that there existed "an infinite set of distinguishable atomic symbols" represented as "strings of capital Latin letters and digits with single embedded blanks" (a subset of character string and numeric literals).

Most modern sexpr notations allow more general quoted strings (for example including punctuation or full Unicode), and use an abbreviated notation to represent lists with more than 2 members, so that stands for NIL is the special end-of-list object (alternatively written (), which is the only representation in Scheme[4]).

Other uses of S-expressions are in Lisp-derived languages such as DSSSL, and as mark-up in communication protocols like IMAP and John McCarthy's CBCL.

This means that Lisp is homoiconic; that is, the primary representation of programs is also a data structure in a primitive type of the language itself.

Program code can be formatted as pretty printed S-expressions using the function PPRINT (note: with two Ps, short for pretty-print).

The draft defined a syntax based on Lisp S-expressions but intended for general-purpose data storage and exchange (similar to XML) rather than specifically for programming.

One is the "advanced transport", which is very flexible in terms of formatting, and is syntactically similar to Lisp-style expressions, but they are not identical.

This format has not been widely adapted for use outside of SPKI (some of the users being GnuPG, libgcrypt, Nettle, and GNU lsh).

Rivest's S-expressions web page provides C source code for a parser and generator (available under the MIT license), which could be adapted and embedded into other programs.