S-expressions: reading a tree as text

In this article

• Read the calculator tree directly
• Compare it with the representations we already used
• Change the structure as data
• What this has to do with Elixir

An S-expression, short for symbolic expression, is a way to represent symbolic structure. We will use a common nested-list notation: values such as numbers and symbols, with parentheses surrounding lists that can contain more lists.sexpr

Its purpose here is to make a distinction visible: reading a tree’s structure is one job; deciding what that tree means is another. We can then compare the result with the tuple trees from our calculator and the quoted code used by Elixir macros.

Read the calculator tree directly

Our calculator grouped 3 + 4 * 2 into an addition whose right input is a multiplication. We can write those relationships as:

(+ 3 (* 4 2))

For this arithmetic example, we choose the convention that the first item in a list names an operation and the remaining items are its inputs.

The outer list has three items: the symbol +, the number 3, and the inner list (* 4 2). That inner list also has three items: *, 4, and 2.

The parentheses make the nesting explicit. We do not need a multiplication-precedence rule to decide whether 4 belongs with 2 or with 3. The structure already groups it with 2.

A reader for this notation can turn atoms and nested lists into data. Here, an atom means an indivisible item such as a symbol or number; that is broader than Elixir’s specific :atom data type.

Reading the data does not establish that + means addition. Our arithmetic language supplies that rule. A different consumer could use a list to describe a query, a configuration record, or something else.

We still need to check allowed forms and provide their meaning. Parenthesizing the tree simplifies its written grouping; it does not eliminate language design.

Compare it with the representations we already used

These examples record the same arithmetic grouping, using different conventions:

Representation	Example
S-expression with operator-first lists	(+ 3 (* 4 2))
Our calculator’s Elixir tuples	{:plus, 3, {:times, 4, 2}}
Elixir’s quoted AST, with metadata abbreviated	{:+, metadata, [3, {:*, more_metadata, [4, 2]}]}

The operator names, containers and extra fields differ. An evaluator written for one format cannot simply assume the others use its conventions.

JSON can also encode nested structure:

["+", 3, ["*", 4, 2]]

In that JSON representation, "+" is a string. In the S-expression above, + is a symbol. A consumer must know which kind of value names an operation in its chosen format.

The encoding article takes this comparison further, including trees stored as records connected by array indices. S-expressions give us a compact textual view of the nested-list choice.

Change the structure as data

Return to the notebook order: delivery costs 3, and four notebooks cost 2 each. Suppose a template leaves the unit price to be supplied later:

(+ 3 (* 4 price))

In this small arithmetic template, price is a placeholder. Supplying 3 replaces that leaf while keeping the surrounding structure:

(+ 3 (* 4 3))

An arithmetic evaluator would now calculate 15. Building the new expression did not require calculating it first. A program can inspect and construct symbolic structure, then pass that structure to another stage.

That is the practical connection to code generation. Work on the tree rather than hoping a text replacement will identify the right occurrence. More complicated languages also need rules for names and bindings; this simple placeholder example has no function scopes to manage.

The evaluator article supplies the other half: how a consumer can calculate a result once it knows the representation and arithmetic rules.

What this has to do with Elixir

Elixir does not use the S-expression above as its quoted AST. Its calls, variables, literals and metadata follow Elixir’s own representation rules.elixir

The connection is the ability to treat code structure as data. In Elixir, quote supplies a quoted expression, and a macro can construct replacement quoted code. The compiler processes that result using Elixir’s rules.

So this article is a comparison tool: it makes nesting and symbolic transformation easy to see before we examine a richer AST. You can write Elixir without introducing an S-expression format into your application.

Continue with Metaprogramming in Elixir for the actual Elixir mechanism. The compiler overview places reading, checking, transformation and execution in the larger pipeline.