Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
S-expression
Summary
In computer programming, an S-expression (or symbolic expression, abbreviated as sexpr or sexp) is an expression in a like-named notation for nested list (tree-structured) data. S-expressions were 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 as
an atom of the form x, or
an expression of the form (x . y) 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 list. 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 cases 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 and Scheme 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
#n=(x y . #n#)
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 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
(x y z)
stands for
(x . (y . (z .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (32)