In computing, s-expressions, sexprs or sexps (for "symbolic expression") are a notation for nested list (tree-structured) data, invented for and popularized by the programming language Lisp, which uses them for source code as well as data. In the usual parenthesized syntax of Lisp, an s-expression is classically defined inductively as
- an atom, or
- an expression of the form
(x . y)where x and y are s-expressions.
The second, recursive part of the definition represents an ordered pair so that s-exprs are effectively binary trees.
The definition of an atom varies per context; in the original definition by John McCarthy, it was assumed that there existed "an infinite set of distinguishable atomic symbols" represented as "strings of capital Latin letters and digits with single imbedded blanks" (i.e., character string and numeric literals). Most modern sexpr notations in addition use an abbreviated notation to represent lists in s-expressions, so that
(x y z)
(x . (y . (z . NIL)))
NIL is the special end-of-list symbol (written
' in Scheme).
In the Lisp family of programming languages, s-expressions are used to represent both source code and data. Other uses of S-expressions are in Lisp-derived languages such as 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 among these languages is the use of S-expressions and prefix notation.
Other related articles:
... some Lisp-derived programming languages include a specification for their S-expression syntax ... 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 ... Rivest's format defines an S-expression as being either an octet-string (a series of bytes) or a finite list of other S-expressions ...