S-expression

The term S-expression or sexp (where S stands for symbolic) refers to a convention for representing semi-structured data in human-readable textual form. S-expressions are probably best known for their use in the Lisp family of programming languages. 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 as parenthesized prefix notation (sometimes known as Cambridge Polish notation).

S-expressions are used for both code and data in Lisp (see McCarthy Recursive Functions of Symbolic Expressions [http://www-formal.stanford.edu/jmc/recursive/recursive.html] ). S-expressions were originally intended only for data to be manipulated by M-expressions, but the first implementation of Lisp was an interpreter of S-expression encodings of M-expressions, and Lisp programmers soon became accustomed to using S-expressions for both code and data.

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) (if (zerop x) 1 (* x (factorial (- x 1)))))Example in Scheme:(define (factorial x) (if (zero? x) 1 (* x (factorial (- x 1)))))

Standardization

In May of 1997, Ron Rivest submitted an Internet-Draft [http://theory.lcs.mit.edu/~rivest/sexp.txt] to be considered for publication as an RFC. 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. It was never approved as an RFC, but it has since been cited and used by other RFCs (e.g. RFC 2693) and several other publications [http://scholar.google.com/scholar?hl=en&lr=&safe=off&q=rivest+sexp&btnG=Search] . It was originally intended for use in SPKI.

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. It describes three interchange formats for expressing this structure. 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. The advanced transport, for example, allows octet-strings to be represented verbatim (the string's length followed by a colon and the entire raw string), a quoted form allowing escape characters, hexadecimal, Base64, or placed directly as a "token" if it meets certain conditions. (Rivest's tokens differ from Lisp tokens in that the former are just for convenience and aesthetics, and treated exactly like other strings, while the latter have specific syntactical meaning.) Another interchange format, intended to be more compact, easier to parse, and unique for any abstract S-expression, is the "canonical representation" which only allows verbatim strings, and prohibits whitespace as formatting outside strings. Finally there is the "basic transport representation", which is either the canonical form or the same encoded as Base64 and surrounded by braces, the latter intended to safely transport a canonically-encoded S-expression in a system which might change spacing (e.g. an email system which has 80-character-wide lines and wraps anything longer than that).

This format has not been widely adapted for use outside of SPKI. Rivest's [http://theory.lcs.mit.edu/~rivest/sexp.html S-expressions web page] provides C source code for a parser and generator, which could theoretically be adapted and embedded into other programs, though licensing on these programs is unclear. However, there are no restrictions on independently implementing the format. Another implementation can be located [http://sexpr.sourceforge.net/ here]

See also

* M-expression
* car and cdr
* cons


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Expression Studio — Desarrollador Microsoft Sitio oficial Español Información general Última versión estable Expres …   Wikipedia Español

  • Expression Web — Desarrollador Microsoft Microsoft Expression Web Información general Última versión estable …   Wikipedia Español

  • Expression Blend — Desarrollador Microsoft Sitio Oficial Español Información general Última versión estable …   Wikipedia Español

  • Expression Media — Desarrollador Phase One Sitio Oficial Inglés Información general Última versión estable Expression Media 2 Service Pack 1 …   Wikipedia Español

  • Expression Rationnelle — Pour les articles homonymes, voir régulier et rationnel. Une expression rationnelle ou expression régulière[1] est en informatique une chaîne de caractères que l’on appelle parfois un motif et qui décrit un ensemble de chaînes de caractères… …   Wikipédia en Français

  • Expression régulière — Expression rationnelle Pour les articles homonymes, voir régulier et rationnel. Une expression rationnelle ou expression régulière[1] est en informatique une chaîne de caractères que l’on appelle parfois un motif et qui décrit un ensemble de… …   Wikipédia en Français

  • Expression Design — Desarrollador Microsoft Sitio Oficial Español Información general Última versión estable …   Wikipedia Español

  • Expression Encoder — Desarrollador Microsoft Sitio Oficial Español Información general Última versión estable …   Wikipedia Español

  • Expression — Ex*pres sion ([e^]ks*pr[e^]sh [u^]n), n. [L. expressio: cf. F. expression.] 1. The act of expressing; the act of forcing out by pressure; as, the expression of juices or oils; also, of extorting or eliciting; as, a forcible expression of truth.… …   The Collaborative International Dictionary of English

  • Expression Ou Néologisme Politique — Comme dans la langue française en général, le vocabulaire politique évolue de façon constante et voit régulièrement apparaître des nouvelles expressions et des néologismes. Parfois créés sans but partisan, ces expressions nouvelles et néologismes …   Wikipédia en Français

  • Expression Systémique — L expression systémique désigne les formes d expression artistique apparaissant dans un système, identifiées par l ensemble de ses caractéristiques, établies ou en évolution : sujet, règles, réactions et résultats . À rapprocher de l… …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.