1 History
1.1 Origins in Lisp
S-expressions originated with the Lisp programming language in the late 1950s. Lisp (List Processing) was designed by John McCarthy at the Massachusetts Institute of Technology. The notation was created as a simple, uniform way to represent both the program code and the data manipulated by the program. Early Lisp implementations used S-expressions as the primary input format for the interpreter.
1.2 John McCarthy's 1960 paper
McCarthy's seminal 1960 paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" formally introduced S-expressions. The paper defined atoms (symbols and numbers) and lists as the building blocks. It showed how S-expressions could represent both data structures and the primitive operations of Lisp itself, establishing the foundation for the language's homoiconic nature.
1.3 Adoption in early AI research
During the 1960s and 1970s, S-expressions became a standard notation in artificial intelligence research. Lisp was the dominant language for AI work, and S-expressions facilitated the manipulation of symbolic knowledge, rule-based systems, and natural language processing. The simplicity of S-expressions made them ideal for representing complex tree-structured data and for implementing metaprogramming techniques.
2 Syntax
2.1 Atoms
Atoms are the primitive, indivisible elements of an S-expression. They include identifiers (symbols), numbers, strings, and characters. Their representation is case-sensitive by convention, though some Lisp dialects treat symbols as case-insensitive.
2.1.1 Identifiers (symbols)
Symbols are sequences of characters (letters, digits, and certain punctuation) that name variables, functions, or constants. Examples: x, list, *global-counter*. Symbols can include hyphens, colons, and other special characters, but not parentheses or whitespace.
2.1.2 Numbers (integers, floating point)
Numbers in S-expressions follow conventional decimal notation. Integers can be written in bases other than ten using a prefix (e.g., #x1F for hexadecimal). Floating-point numbers use a decimal point and optional exponent (e.g., 3.14, 1.0e-2). Some Lisp dialects also support rational and complex numbers.
2.1.3 Strings and characters
Strings are enclosed in double quotation marks (e.g., "hello"). They may contain escape sequences for special characters. Characters are denoted with a backslash and an optional name (e.g., \a, \space). The exact syntax varies across Lisp dialects.
2.2 Lists
Lists are the compound data structures of S-expressions. They are created by enclosing a sequence of S-expressions within parentheses, separated by whitespace. A list can contain atoms, other lists, or a mixture.
2.2.1 Proper lists and dotted pairs
A proper list (fully parenthesized list) ends with the empty list, denoted by nil or (). A dotted pair is a cons cell whose second element is not a list, written as (a . b). Dotted pairs are used for association lists and other data structures where the cdr is not necessarily a list.
2.2.2 Nested list structures
Lists can be arbitrarily nested, allowing the representation of trees and hierarchical data. For example, ((1 2) (3 (4 5))) represents a tree with two branches. This nesting is fundamental to the representation of Lisp program expressions (e.g., (+ (* 2 3) 4)).
2.3 Whitespace and comments
Whitespace (spaces, tabs, newlines) separates S-expression elements and is generally ignored within lists. Comments are introduced with a semicolon (;) and extend to the end of the line. Some dialects also support block comments (e.g., `# | ... | #` in Common Lisp). Comments are not part of the data structure. |
|---|
3 Data Representation
3.1 Parsing and tokenization
Parsing an S-expression involves tokenizing the input stream into atoms and parentheses. Tokens are separated by whitespace. Parentheses determine list boundaries. The parser builds a tree of nested lists and atoms, which corresponds directly to the abstract syntax tree (AST) of Lisp programs. The process is unambiguous and typically does not require a symbol table for basic parsing.
3.2 Abstract syntax tree equivalence
An S-expression is itself a representation of its own abstract syntax tree. Because Lisp source code is expressed as S-expressions, the parsed form of a program is identical to the data structure it manipulates. This property—homoiconicity—enables powerful metaprogramming techniques such as macros, which transform S-expressions at compile time.
3.3 Comparison with XML and JSON
3.3.1 Advantages in simplicity
S-expressions use only parentheses, atoms, and basic whitespace—no closing tags, no braces, no key-value delimiters. This simplicity reduces parsing overhead and makes the notation uniformly parseable. The minimal syntax also makes S-expressions easy to generate and process programmatically.
3.3.2 Disadvantages in readability
For large or deeply nested data, S-expressions can be difficult for humans to read due to the heavy use of parentheses. Unlike XML or JSON, they lack named tags (element names) and often rely on conventions for structure meaning. The absence of explicit key-value marking can make the data less self-describing compared to JSON.
4 Use in Programming Languages
4.1 Homoiconicity and macros
Homoiconicity means that the primary representation of code (S-expressions) is the same as the representation of data. This enables macros: functions that manipulate S-expressions at compile time, rewriting them before evaluation. Macros allow users to extend the language’s syntax in a syntactically safe way, without needing to modify the parser.
4.2 S-expressions in Lisp dialects
4.2.1 Common Lisp
Common Lisp uses S-expressions for all code and data. The language includes a rich set of built-in data types and a standard macro facility. The Common Lisp Object System (CLOS) is also expressed via S-expressions.
4.2.2 Scheme
Scheme is a minimalist Lisp dialect that relies heavily on S-expressions. Scheme’s macros (e.g., define-syntax) are more hygienic than Common Lisp’s but still operate on S-expression representations.
4.2.3 Clojure
Clojure extends S-expressions with additional data structures like vectors and maps, but the core syntax remains parenthesized lists. Clojure also introduces tagged literals and metadata, allowing richer data representation while preserving S-expression principles.
4.3 Non-Lisp languages using S-expressions
4.3.1 Tcl (syntax equivalence)
Tcl (Tool Command Language) has a syntax that is structurally similar to S-expressions, though it uses braces for grouping and quotes for strings. Some Tcl dialects and interpreters have been adapted to read Lisp-like syntax.
4.3.2 Kernel language by John Shutt
John Shutt’s Kernel language uses S-expressions as its base notation. It is designed as a minimal, formal foundation for programming languages, emphasizing first-class macros and a simple evaluation model.
5 Extensions and Variants
5.1 Quoting and quasiquoting
Quoting prevents evaluation of an S-expression: '(a b c) returns the list (a b c) without evaluating a, b, or c. Quasiquoting (using the backtick character) allows partial evaluation with unquoting (, ) and splicing (,@). This is essential for macro templates.
5.2 Reader macros
Reader macros are user-defined extensions to the S-expression parser. They allow custom syntax for specific use cases, such as regex patterns or dictionary literals. Common Lisp provides hooks for defining reader macros, and many implementations include built-in reader macros for abbreviations (e.g., #’ for function references).
5.3 S-expression with metadata (e.g., Clojure tags)
Clojure attaches metadata to data structures (like maps and vectors) using a caret ^ prefix. This allows associating type hints, documentation strings, or arbitrary data without breaking the S-expression syntax. Tagged literals (e.g., #uuid "...") extend the set of literal data types.
5.4 Canonical S-expressions (for signing and hashing)
Canonical S-expressions (also called “csexps”) are a restricted form of S-expressions designed to produce unique byte-level representations. They are used in cryptographic applications for signing and hashing, as they avoid ambiguities caused by whitespace, quoting, or formatting.
6 Practical Applications
6.1 Configuration files (Emacs init, Guile scripts)
Emacs uses S-expressions (often called "dot-emacs" files) for user configuration. The Emacs Lisp interpreter reads these files, allowing users to set variables, define custom functions, and load packages. Similarly, Guile (GNU Ubiquitous Intelligent Language for Extensions) uses S-expressions for scripting and configuration within GNU tools.
6.2 Data interchange (EDN, sXML)
EDN (Extensible Data Notation) is a subset of Clojure’s S-expression syntax used for data interchange. It supports numbers, symbols, keywords, strings, vectors, maps, and sets, and is often used in web APIs and configuration. sXML (S-expression XML) uses S-expressions to represent XML structure, providing a more compact and lispy alternative for markup.
6.3 Machine learning (Jupyter kernels, Lisp-based compilers)
Machine learning frameworks occasionally use S-expressions for internal representations. The Jupyter kernel for Hy (a Lisp that compiles to Python AST) allows interactive development with S-expression code. Lisp-based compilers for deep learning (e.g., Lisp-inference libraries) use S-expressions as an intermediate representation for optimizing neural network graphs.