Editing S-expression (section)

== Characteristics ==

In the usual parenthesized [[Syntax (programming languages)|syntax]] of Lisp, an S-expression is classically defined<ref name="McCarthy1960">John McCarthy (1960/2006). [http://www-formal.stanford.edu/jmc/recursive/recursive.html Recursive functions of symbolic expressions] {{webarchive|url=https://web.archive.org/web/20040202215021/http://www-formal.stanford.edu/jmc/recursive/recursive.html |date=2004-02-02 }}. Originally published in [[Communications of the ACM]].</ref> as

# an atom of the form <code>''x''</code>, or
# an [[Expression (computer science)|expression]] of the form <code>(''x'' . ''y'')</code> where ''x'' and ''y'' are S-expressions.

This definition reflects LISP's representation of a list as a series of "cells", each one an [[ordered pair]]. In plain lists, ''y'' points to the next cell (if any), thus forming a [[Linked list|list]]. The [[Recursion|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 reference]]s, 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 key]]s, [[SGML]]/[[XML]] IDREFs, etc.). Modern Lisp dialects such as [[Common Lisp]]<ref>{{cite web|title=Common Lisp HyperSpec: 22.4 - The Printer Dictionary: *PRINT-CIRCLE*|url=http://clhs.lisp.se/Body/v_pr_cir.htm|date=2018-12-28}}</ref> and [[Scheme (programming language)|Scheme]]<ref>{{cite web|title=Revised<sup>7</sup> Report on the Algorithmic Language‌ Scheme: Section 2.4: Datum Labels|url=https://small.r7rs.org/attachment/r7rs.pdf#section.2.4|date=2013-07-06}}</ref> 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 [[Lisp reader|reader]] or [[Format (Common Lisp)|printer]] to detect and thus trigger evaluation or display of cycles without infinitely recursing

: <code>#n=(''x'' ''y'' . #n#)</code>

The definition of an atom varies per context; in the original definition by [[John McCarthy (computer scientist)|John McCarthy]],<ref name="McCarthy1960"/> it was assumed that there existed "an infinite set of distinguishable [[Symbol (programming)|atomic symbols]]" represented as "strings of capital [[Latin script|Latin letter]]s and digits with single embedded blanks" (a subset of [[String (computing)|character string]] and numeric [[Literal (computer programming)|literal]]s).

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

: <code>(''x'' ''y'' ''z'')</code>

stands for

: <code>(''x'' . (''y'' . (''z'' . NIL)))</code>

<code>NIL</code> is the special end-of-list [[Object (computer science)|object]] (alternatively written <code>()</code>, which is the only representation in [[Scheme (programming language)|Scheme]]<ref>{{Cite web|url=https://schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html|title=Revised^5 Report on the Algorithmic Language Scheme|website=schemers.org}}</ref>).

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 [[Document Style Semantics and Specification Language|DSSSL]], and as [[Markup language|mark-up]] in [[communication protocol]]s like [[Internet Message Access Protocol|IMAP]] and [[John McCarthy (computer scientist)|John McCarthy]]'s [[Common Business Communication Language|CBCL]]. It is also used as text representation of [[WebAssembly]]. The details of the syntax and supported [[data type]]s vary in the different languages, but the most common feature among these languages is the use of S-expressions and prefix notation.