Tracing Evaluation:
Chains, Trees and Graphs

Ian Ford, Wolfram

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

ABSTRACT

Wolfram Language models computation as the repeated evaluation of symbolic expressions. Symbolic expressions can represent not only data and programs, but also the execution history of programs. This talk demonstrates how to trace every step in the evaluation of an expression, including generating symbolic execution histories, filtering with various criteria, and tools for display, manipulation and analysis.

Topics

Trace

TraceDialog

TracePrint

TraceScan

ResourceFunction["TraceTree"]

ResourceFunction["TraceGraph"]

Expressions

Everything in the Wolfram Language is an expression. Here is an expression whose head is the symbol f and whose arguments are the symbols x, y and z:

f[x, y, z]

Expressions are essentially trees constructed from symbols, numbers and other atomic data types. Here is what the expression above looks like as a tree:

ExpressionTree[f[x,y,z]]

Evaluation

Even computations are represented using expressions. Here is the expression that computes the sum of the numbers 2 and 3:

2 + 3

Despite being written using special notation for addition, this is still a symbolic expression with a head and arguments:

Plus[2, 3]

Here is the tree form of that expression:

ExpressionTree[Unevaluated[2+3]]

Standard Evaluation Sequence

From tutorial/Evaluation:

If the expression is a raw object (e.g., Integer, String, etc.), leave it unchanged.

Evaluate the head h of the expression.

Evaluate each element (Subscript[e, i]) of the expression in turn. If h is a symbol with attributes HoldFirst, HoldRest, HoldAll, or HoldAllComplete, then skip evaluation of certain elements.

…

Use any applicable transformation rules that you have defined for h[f[e1,e2,…],…] or for h[…][…].

Use any built-in transformation rules for h[e1,e2,…] or for h[…][…].

Definitions

Transformation rules are defined by associating a pattern to a replacement value. Here are the rules defining the Fibonacci function that we will use throughout this talk:

fib[1]=fib[2]=1;

fib[n_]:=fib[n-1]+fib[n-2]

If we now evaluate an expression of the form fib[n], these rules are automatically applied until the expression no longer changes:

fib[5]

So how can we follow each step in the execution history of this computation to see what is happening?

Trace

The function Trace evaluates an expression and generates a list of all expression used in its evaluation. Here is what we get when we trace fib[5]:

Trace[fib[5]]

Evaluation Chains

Let’s break this down with a simpler example. Here is what we get when we trace a simple addition:

Trace[2+3]

The expressions 2+3 and 5 form an evaluation chain, where 2+3 is replaced with 5 by the built-in transformation rules for Plus. Let’s look at a longer chain:

Trace[fib[1]+fib[2]]

Here we see that the first two elements of the chain are themselves evaluation chains, represented using nested lists.

Evaluation Trees

Let’s take a closer look at the nested evaluation chain above. In order to compute fib[1]+fib[2], we must first compute the values of fib[1] and fib[2]. We can visualize the nested evaluation chains using ResourceFunction["TraceTree"]:

[fib[1]+fib[2]]

This is how we defined fib[3], so let’s see how that looks:

[fib[3]]

Evaluation Graphs

We saw above that we can visualize execution histories as a tree of nested evaluation chains. It is often helpful to instead visualize the connections between the expressions themselves. For this, there is ResourceFunction["TraceGraph"]:

[fib[3]]

Options

There are several options for filtering the execution history by various criteria. For example, only the expressions after evaluation are included by default, but the original expressions can be included using the option TraceOriginal:

[fib[3],TraceOriginal->True]

Patterns

Patterns can also be used if only expressions of certain forms are to be included:

[fib[6],_fib]

Printing and Scanning

TracePrint and TraceScan can be used to specify functions to apply during evaluation:

TracePrint[fib[4],_fib]

TraceScan[Echo,fib[4],_fib]

Interactivity

TraceDialog can be used to step through an evaluation:

TraceDialog[fib[4],_fib]

Return[]

Tracing Evaluation:
Chains, Trees and Graphs

Ian Ford, Wolfram

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf