Function Repository Resource:

TraceGraph

Source Notebook

Generate a graph of all expressions in an evaluation chain

Contributed by: Ian Ford (Wolfram Research)

ResourceFunction["TraceGraph"][expr]

generates a graph of all expressions used in the evaluation of expr.

ResourceFunction["TraceGraph"][expr,form]

includes only those expressions that match form.

ResourceFunction["TraceGraph"][expr,s]

includes all evaluations that use transformation rules associated with the symbol s.

Details and Options

In general, form in ResourceFunction["TraceGraph"][expr,form] is compared both with each complete expression that is evaluated and with the tag associated with an transformation rule used in the evaluation.
ResourceFunction["TraceGraph"][expr,lhsrhs] picks out expressions that match lhs, then replaces them with rhs in the graph returned.
All expressions in the graph returned by ResourceFunction["TraceGraph"] are wrapped in HoldForm.
ResourceFunction["TraceGraph"] returns a rooted directed acyclic graph. Each branch corresponds to a single evaluation chain, which contains the sequence of forms found for a particular expression. Vertices have branches that give histories of subsidiary evaluations.
A round node is used for the first form in an evaluation chain. An unlabeled circular node is used as a placeholder when the first form is not included. Solid edges connect such a node to the first node in each of its subsidiary evaluation chains.
Rectangular nodes are used for all forms in an evaluation chain after the first form. An unlabeled square node is used as a placeholder when the last form is not included. A dashed edge connects the last node in a subsidiary evaluation chain to the following node in its parent evaluation chain.
Highlighted dashed edges are used for transformation rules.
ResourceFunction["TraceGraph"] takes the same options as Graph, with the following changes:
Additional options for ResourceFunction["TraceGraph"] include:
MatchLocalNamesTruewhether to allow x to stand for x$nnn
TraceAboveFalsewhether to show evaluation chains that contain the chain containing form
TraceBackwardFalsewhether to show expressions preceding form in the evaluation chain
TraceDepthInfinityhow many levels of nested evaluations to include
TraceForwardFalsewhether to show expressions following form in the evaluation chain
TraceOffNoneforms within which to switch off tracing
TraceOn_forms within which to switch on tracing
TraceOriginalFalsewhether to look at expressions before their heads and arguments are evaluated
During the execution of ResourceFunction["TraceGraph"], the settings for the form argument, and for the options TraceOn and TraceOff, can be modified by resetting the values of the global variables $TracePattern, $TraceOn, and $TraceOff, respectively.

Examples

Basic Examples (2) 

Trace each step in an evaluation:

In[1]:=
ResourceFunction["TraceGraph"][u = 2; Do[u = u*u, {3}]; u]
Out[1]=

Trace only the computations with head Times:

In[2]:=
ResourceFunction["TraceGraph"][u = 2; Do[u = u*u, {3}]; u, Times]
Out[2]=

Scope (10) 

Trace an empty evaluation chain:

In[3]:=
ResourceFunction["TraceGraph"][1]
Out[3]=

Trace a single step evaluation:

In[4]:=
ResourceFunction["TraceGraph"][1 + 2]
Out[4]=

Trace each branch in an evaluation:

In[5]:=
ResourceFunction["TraceGraph"][2*3 + 4*5 + 6*7]
Out[5]=

Trace evaluations given by definitions:

In[6]:=
a = 1; b = 2; f[x_, y_] := x + y;
In[7]:=
ResourceFunction["TraceGraph"][f[a, b]]
Out[7]=

Trace each step in an evaluation:

In[8]:=
ResourceFunction["TraceGraph"][a = 2; b = 3; a + b]
Out[8]=

Trace the operation of FoldList:

In[9]:=
ResourceFunction["TraceGraph"][FoldList[Plus, 0, {3, 2, 1}]]
Out[9]=

Trace the steps in a non-standard evaluation:

In[10]:=
ResourceFunction["TraceGraph"][List @@ Join[Hold[1 + 1], Hold[2 + 2]]]
Out[10]=

Trace each step in an evaluation:

In[11]:=
ResourceFunction["TraceGraph"][(2 + 3)^(2 + 3) + (4 + 5)^(4 + 5)]
Out[11]=

Include only those expressions that match _Plus:

In[12]:=
ResourceFunction[
 "TraceGraph"][(2 + 3)^(2 + 3) + (4 + 5)^(4 + 5), _Plus]
Out[12]=

Trace the computations with head Plus:

In[13]:=
ResourceFunction[
 "TraceGraph"][(2 + 3)^(2 + 3) + (4 + 5)^(4 + 5), Plus]
Out[13]=

Apply a transformation rule to expressions that match a pattern:

In[14]:=
fib[1] = fib[2] = 1; fib[n_] := fib[n - 1] + fib[n - 2];
In[15]:=
ResourceFunction["TraceGraph"][fib[5], fib[n_] :> n]
Out[15]=

Modify the setting for the form argument during the execution of TraceGraph[expr,form] by resetting the value of the global variable $TracePattern:

In[16]:=
ResourceFunction[
 "TraceGraph"][(1 + 1)^(2 + 2); $TracePattern = Power; (1 + 1)^(2 + 2), _]
Out[16]=

Options (23) 

MatchLocalNames (2) 

By default, symbols such as x match symbols with local names of the form x$nnn:

In[17]:=
f[x_] := 1/(1 + x^2)
In[18]:=
ResourceFunction["TraceGraph"][f[x] + Module[{x}, f[x]], f[x]]
Out[18]=

With MatchLocalNamesFalse, only an explicit match of x will show up:

In[19]:=
ResourceFunction["TraceGraph"][f[x] + Module[{x}, f[x]], f[x], MatchLocalNames -> False]
Out[19]=

TraceAbove (4) 

A recursive definition for finding Fibonacci numbers:

In[20]:=
fib[1] = fib[2] = 1; fib[n_] := fib[n - 1] + fib[n - 2];

Show only what sums of fib are encountered:

In[21]:=
ResourceFunction["TraceGraph"][fib[4], fib[x_] + fib[y_]]
Out[21]=

Show the beginning of the evaluation chain that leads to each sum of fib:

In[22]:=
ResourceFunction["TraceGraph"][fib[4], fib[x_] + fib[y_], TraceAbove -> True]
Out[22]=

Show the entire evaluation chain that leads to each sum of fib:

In[23]:=
ResourceFunction["TraceGraph"][fib[4], fib[x_] + fib[y_], TraceAbove -> All]
Out[23]=

TraceBackward (4) 

A recursive definition for finding Fibonacci numbers:

In[24]:=
fib[1] = fib[2] = 1; fib[n_] := fib[n - 1] + fib[n - 2];

Show only what additions of positive integers are required:

In[25]:=
ResourceFunction["TraceGraph"][fib[4], Plus[__Integer?Positive]]
Out[25]=

Show the beginning of the evaluation chain that leads to each addition:

In[26]:=
ResourceFunction["TraceGraph"][fib[3], Plus[__Integer?Positive], TraceBackward -> True]
Out[26]=

Show all intermediate evaluations that led to each addition:

In[27]:=
ResourceFunction["TraceGraph"][fib[3], Plus[__Integer?Positive], TraceBackward -> All]
Out[27]=

TraceDepth (3) 

A recursive definition for finding Fibonacci numbers:

In[28]:=
fib[1] = fib[2] = 1; fib[n_] := fib[n - 1] + fib[n - 2];

Trace only evaluations through depth 3:

In[29]:=
ResourceFunction["TraceGraph"][fib[4], TraceDepth -> 2]
Out[29]=

Trace all evaluations:

In[30]:=
ResourceFunction["TraceGraph"][fib[4]]
Out[30]=

TraceForward (4) 

A recursive definition for finding Fibonacci numbers:

In[31]:=
fib[1] = fib[2] = 1; fib[n_] := fib[n - 1] + fib[n - 2];

Show only what evaluations of fib are encountered:

In[32]:=
ResourceFunction["TraceGraph"][fib[4], _fib]
Out[32]=

Show only the evaluations of fib and the results:

In[33]:=
ResourceFunction["TraceGraph"][fib[4], _fib, TraceForward -> True]
Out[33]=

Show all intermediate evaluations between calls of fib and the result:

In[34]:=
ResourceFunction["TraceGraph"][fib[4], _fib, TraceForward -> All]
Out[34]=

TraceOff (2) 

Trace evaluation of an expression that evaluates a function g:

In[35]:=
g[x_] := x^2 + 1;
In[36]:=
ResourceFunction["TraceGraph"][(1 + g[1] + g[2])^3]
Out[36]=

Omit evaluations required to get the values of g:

In[37]:=
ResourceFunction["TraceGraph"][(1 + g[1] + g[2])^3, TraceOff -> _g]
Out[37]=

TraceOn (2) 

Trace evaluation of an expression that evaluates a function g:

In[38]:=
g[x_] := x^2 + 1;
In[39]:=
ResourceFunction["TraceGraph"][(1 + g[1] + g[2])^3]
Out[39]=

Trace only evaluation inside of g:

In[40]:=
ResourceFunction["TraceGraph"][(1 + g[1] + g[2])^3, TraceOn -> _g]
Out[40]=

TraceOriginal (2) 

Trace evaluation of an expression showing evaluation chains for expressions that change:

In[41]:=
ResourceFunction["TraceGraph"][f[1, 2 + 3]]
Out[41]=

Show evaluation chains even for expressions that do not change:

In[42]:=
ResourceFunction["TraceGraph"][f[1, 2 + 3], TraceOriginal -> True]
Out[42]=

Applications (5) 

Trace the evaluation of control structures such as CompoundExpression:

In[43]:=
ResourceFunction["TraceGraph"][1 + 1; 2 + 2; 3 + 3, TraceOriginal -> True]
Out[43]=

Trace the evaluation of conditionals such as If:

In[44]:=
ResourceFunction["TraceGraph"][If[EvenQ[2], 1 + 1, 2 + 2], TraceOriginal -> True]
Out[44]=

Trace the evaluation of logical operations such as And:

In[45]:=
ResourceFunction["TraceGraph"][OddQ[2] && OddQ[3], TraceOriginal -> True]
Out[45]=

Trace the evaluation of iteration functions such as Do:

In[46]:=
ResourceFunction["TraceGraph"][Do[n^2, {n, 1 + 1, 2 + 2}], TraceOriginal -> True]
Out[46]=

Trace the evaluation of assignments such as SetDelayed:

In[47]:=
ResourceFunction["TraceGraph"][f[x_] := x^2, TraceOriginal -> True]
Out[47]=

Properties and Relations (8) 

TraceGraph[expr] traces each step in the evaluation of expr:

In[48]:=
fib[1] = fib[2] = 1; fib[n_] := fib[n - 1] + fib[n - 2];
In[49]:=
ResourceFunction["TraceGraph"][fib[4]]
Out[49]=

TraceGraph[expr,form] includes only those expressions that match form:

In[50]:=
ResourceFunction["TraceGraph"][fib[4], _fib]
Out[50]=

This corresponds to deleting all expressions that do not match form, then deleting empty evaluation chains:

In[51]:=
Trace[fib[4]]
Out[51]=
In[52]:=
DeleteCases[%, HoldForm[Except[_fib]], Infinity]
Out[52]=
In[53]:=
ReplaceAll[{} -> Nothing] /@ %
Out[53]=
In[54]:=
% === Trace[fib[4], _fib]
Out[54]=

TraceGraph gives a graph with vertices of the form Trees`TraceNode[HoldForm[expr],pos]:

In[55]:=
ResourceFunction["TraceGraph"][2^3 + 4]
Out[55]=
In[56]:=
InputForm[VertexList[%]]
Out[56]=

TraceGraph uses highlighted dashed edges for iteration:

In[57]:=
f[x_] := g[x]; g[x_] := x^2
In[58]:=
ResourceFunction["TraceGraph"][f[2]]
Out[58]=

The children given by TraceTree correspond to subsequent iterations in the reevaluation of expressions:

In[59]:=
ResourceFunction["TraceTree"][f[2]]
Out[10]=

TraceGraph uses solid and dashed edges for increasing and decreasing recursion levels, respectively:

In[60]:=
ResourceFunction["TraceGraph"][1 + 2 3, TraceOriginal -> True]
Out[60]=

The levels given by TraceTree correspond to the recursion levels of subsidiary evaluations:

In[61]:=
ResourceFunction["TraceTree"][1 + 2 3, TraceOriginal -> True]
Out[11]=

Each iteration in the reevaluation of an expression at recursion level n is represented as Trees`TraceNode[expr,{i1,,in}]:

In[62]:=
f[x_] := g[x]; g[x_] := x^2
In[63]:=
ResourceFunction["TraceGraph"][f[2]]
Out[63]=
In[64]:=
InputForm[VertexList[%]]
Out[64]=
In[65]:=
Trace[f[2]]
Out[65]=

The result of recursion at level n is represented as Trees`TraceNode[expr,{i1,,in-1}]:

In[66]:=
ResourceFunction["TraceGraph"][f[x, y], TraceOriginal -> True]
Out[66]=
In[67]:=
InputForm[VertexList[%]]
Out[67]=
In[68]:=
Trace[f[x, y], TraceOriginal -> True]
Out[68]=

Trees`TraceNode[Null,{,1}] represents the first node in an evaluation chain when the first expression is not included:

In[69]:=
ResourceFunction["TraceGraph"][1 + 2 3]
Out[69]=
In[70]:=
InputForm[VertexList[%]]
Out[70]=
In[71]:=
Trace[1 + 2 3]
Out[71]=

Trees`TraceNode[Null,{,-1}] represents the last node in evaluation chain when the last expression is not included:

In[72]:=
ResourceFunction["TraceGraph"][u = 2; Do[u = u u, {3}]; u, Times]
Out[72]=
In[73]:=
InputForm[VertexList[%]]
Out[73]=
In[74]:=
Trace[u = 2; Do[u = u u, {3}]; u, Times]
Out[74]=

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 2.0.1 – 28 June 2024
  • 2.0.0 – 06 September 2023
  • 1.0.0 – 15 July 2022

Related Resources

License Information