Function Repository Resource:

TraceCausalGraph

Source Notebook

Build a causal graph from an expression evaluation trace

Contributed by: Nik Murzin

ResourceFunction["TraceCausalGraph"][expr]

evaluate an expression and return a causal graph of its trace.

ResourceFunction["TraceCausalGraph"][expr,n]

trace only up-to n steps of evaluation.

ResourceFunction["TraceCausalGraph"][expr,n,patt]

prune trace by a specifying a pattern of expressions to include.

ResourceFunction["TraceCausalGraph"][expr,…,prop]

returns the specified property prop.

Details and Options

Tracing functions with Flat, Orderless, OneIdentity attributes and other things that lead to non-standard evaluation (like Sequence) is not properly supported.

Supported properties for prop include:

"CausalGraph" (default)

causal graph of the trace

"Path"

path as an interspersed list of HoldComplete expressions and positions

"PathGraph"

path as a PathGraph

"PathEventsGraph"

intersperse a path graph with corresponding event vertices

"PathCausalGraph"

add causal dependency edges to the "PathEventsGraph"

TraceCausalGraph takes the following options:

"IncludeInitialEvent"

False

whether to include an additional event that produces original expression

"ShowIndices"

False

show event indices

"ShowEventOrder"

False

show evaluation order with a path between events

"ShowPositions"

False

show event position with negative position indicating internal evaluations

"ShowExpressions"

True

show complete or partial expressions

"PruneIdentities"

True

prune events that evaluate expression to itself

"PruneSideEvents"

False

prune expressions that do not correspond to any part of original expression

"PruneTerminatedEvaluation"

True

prune expression with TerminatedEvaluation

ResourceFunction["TraceCausalGraph"] also takes Graph options.

Examples

Basic Examples (5)

Make a causal graph from a standard evaluation of an expression:

In[1]:=

Out[1]=

Make a path consisting of intermediate expressions together with subexpression positions being evaluated:

In[2]:=

Out[2]=

Make a path graph of expressions in a trace:

In[3]:=

Out[3]=

Make a path with interspersed events between expressions:

In[4]:=

Out[4]=

Add dependency edges between events:

In[5]:=

Out[5]=

Scope (2)

Trace a more complicated expression:

In[6]:=

ClearAll[fib]
fib[n_] := fib[n - 1] + fib[n - 2]
fib[0 | 1] = 1;

ResourceFunction["TraceCausalGraph"][fib[3]]

Out[7]=

Tracing internal functions would result in side-events (indicated by a dashed boundary):

In[8]:=

Out[8]=

In[9]:=

$ResourceFunction["TraceCausalGraph"][Table[i^2 + i, {i, 2}], GraphLayout -> {"LayeredDigraphEmbedding", "Orientation" -> Left}]$

Out[9]=

Options (9)

IncludeInitialEvent (1)

Include an additional event that all events causally depend on:

In[10]:=

Out[10]=

ShowIndices (1)

Show indices of events in evaluation order:

In[11]:=

Out[11]=

ShowEventOrder (1)

Indicate an actual order of events during evaluation:

In[12]:=

Out[12]=

ShowPositions (2)

Show positions of subexpressions being evaluated:

In[13]:=

Out[13]=

With side-events having decreasing negative part numbers:

In[14]:=

Out[14]=

ShowExpressions (1)

Instead of the whole expression show only subexpressions under evaluation:

In[15]:=

Out[15]=

In[16]:=

Out[16]=

PruneIdentities (1)

Trivial identity events are pruned by default:

In[17]:=

Out[17]=

In[18]:=

Out[18]=

PruneSideEvents (1)

Prune side-events from a trace PathGraph and corresponding events:

In[19]:=

In[20]:=

Out[20]=

In[21]:=

Out[21]=

In[22]:=

Out[22]=

PruneTerminatedEvaluation (1)

Terminating after non-terminal amount of steps results in TerminatedEvaluation inside of the last event, which is pruned by default:

In[23]:=

$GraphicsRow[ Table[ResourceFunction["TraceCausalGraph"][(1 + 2)^3, n, "PruneTerminatedEvaluation" -> False, PlotLabel -> Row[{n, If[n == 1, "step", "steps"]}, " "], GraphLayout -> "SpiralEmbedding"], {n, 4, 12, 2}], Frame -> All]$