Tracing Evaluation

The standard way in which the Wolfram System works is to take any expression you give as input, evaluate the expression completely, and then return the result. When you are trying to understand what the Wolfram System is doing, however, it is often worthwhile to look not just at the final result of evaluation, but also at intermediate steps in the evaluation process.

Tracing the evaluation of expressions.

The expression 1+1 is evaluated immediately to 2:

Trace[1+1]

The 2^3 is evaluated before the addition is done:

Trace[2^3+4]

The evaluation of each subexpression is shown in a separate sublist:

Trace[2^3+4^2+1]

(RefLink[Trace, paclet:ref/Trace])[expr] gives a list that includes all the intermediate expressions involved in the evaluation of expr. Except in rather simple cases, however, the number of intermediate expressions generated in this way is typically very large, and the list returned by (RefLink[Trace, paclet:ref/Trace]) is difficult to understand.

(RefLink[Trace, paclet:ref/Trace])[expr,form] allows you to "filter" the expressions that (RefLink[Trace, paclet:ref/Trace]) records, keeping only those that match the pattern form.

Here is a recursive definition of a factorial function:

fac[n_]:=n fac[n-1];fac[1]=1

This gives all the intermediate expressions generated in the evaluation of fac[3]. The result is quite complicated:

Trace[fac[3]]

This shows only intermediate expressions of the form fac[n_]:

Trace[fac[3],fac[n_]]

You can specify any pattern in (RefLink[Trace, paclet:ref/Trace]):

Trace[fac[10],fac[n_/;n>5]]

(RefLink[Trace, paclet:ref/Trace])[expr,form] effectively works by intercepting every expression that is about to be evaluated during the evaluation of expr, and picking out those that match the pattern form.

If you want to trace "calls" to a function like fac, you can do so simply by telling (RefLink[Trace, paclet:ref/Trace]) to pick out expressions of the form fac[n_]. You can also use patterns like f[n_,2] to pick out calls with particular argument structure.

A typical Wolfram System program, however, consists not only of "function calls" like fac[n], but also of other elements, such as assignments to variables, control structures, and so on. All of these elements are represented as expressions. As a result, you can use patterns in (RefLink[Trace, paclet:ref/Trace]) to pick out any kind of Wolfram System program element. Thus, for example, you can use a pattern like k=_ to pick out all assignments to the symbol k.

This shows the sequence of assignments made for k:

Trace[(k=2;For[i=1,i<4,i++,k=i/k];k),k=_]

(RefLink[Trace, paclet:ref/Trace])[expr,form] can pick out expressions that occur at any time in the evaluation of expr. The expressions need not, for example, appear directly in the form of expr that you give. They may instead occur, say, during the evaluation of functions that are called as part of the evaluation of expr.

Here is a function definition:

h[n_]:=(k=n/2;Do[k=i/k,{i,n}];k)

You can look for expressions generated during the evaluation of h:

Trace[h[3],k=_]

(RefLink[Trace, paclet:ref/Trace]) allows you to monitor intermediate steps in the evaluation not only of functions that you define, but also of some functions that are built into the Wolfram System. You should realize, however, that the specific sequence of intermediate steps followed by built-in Wolfram System functions depends in detail on their implementation and optimization in a particular version of the Wolfram System.

Some ways to use (RefLink[Trace, paclet:ref/Trace]).

The function (RefLink[Trace, paclet:ref/Trace]) returns a list that represents the "history" of a Wolfram System computation. The expressions in the list are given in the order that they were generated during the computation. In most cases, the list returned by (RefLink[Trace, paclet:ref/Trace]) has a nested structure, which represents the "structure" of the computation.

The basic idea is that each sublist in the list returned by (RefLink[Trace, paclet:ref/Trace]) represents the "evaluation chain" for a particular Wolfram System expression. The elements of this chain correspond to different forms of the same expression. Usually, however, the evaluation of one expression requires the evaluation of a number of other expressions, often subexpressions. Each subsidiary evaluation is represented by a sublist in the structure returned by (RefLink[Trace, paclet:ref/Trace]).

Here is a sequence of assignments:

a[1]=a[2];a[2]=a[3];a[3]=a[4]

This yields an evaluation chain reflecting the sequence of transformations for a[i] used:

Trace[a[1]]

The successive forms generated in the simplification of y+x+y show up as successive elements in its evaluation chain:

Trace[y+x+y]

Each argument of the function f has a separate evaluation chain, given in a sublist:

Trace[f[1+1,2+3,4+5]]

The evaluation chain for each subexpression is given in a separate sublist:

Trace[x x+y y]

Tracing the evaluation of a nested expression yields a nested list:

Trace[f[f[f[1+1]]]]

There are two basic ways that subsidiary evaluations can be required during the evaluation of a Wolfram System expression. The first way is that the expression may contain subexpressions, each of which has to be evaluated. The second way is that there may be rules for the evaluation of the expression that involve other expressions that themselves must be evaluated. Both kinds of subsidiary evaluations are represented by sublists in the structure returned by (RefLink[Trace, paclet:ref/Trace]).

The subsidiary evaluations here come from evaluation of the arguments of f and g:

Trace[f[g[1+1],2+3]]

Here is a function with a condition attached:

fe[n_]:=n+1/;EvenQ[n]

The evaluation of fe[6] involves a subsidiary evaluation associated with the condition:

Trace[fe[6]]

You often get nested lists when you trace the evaluation of functions that are defined "recursively" in terms of other instances of themselves. The reason is typically that each new instance of the function appears as a subexpression in the expressions obtained by evaluating previous instances of the function.

Thus, for example, with the definition fac[n_]:=n fac[n-1], the evaluation of fac[6] yields the expression 6 fac[5], which contains fac[5] as a subexpression.

The successive instances of fac generated appear in successively nested sublists:

Trace[fac[6],fac[_]]

With this definition, fp[n-1] is obtained directly as the value of fp[n]:

fp[n_]:=fp[n-1]/;n>1

fp[n] never appears in a subexpression, so no sublists are generated:

Trace[fp[6],fp[_]]

Here is the recursive definition of the Fibonacci numbers:

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

Here are the end conditions for the recursion:

fib[0]=fib[1]=1

This shows all the steps in the recursive evaluation of fib[5]:

Trace[fib[5],fib[_]]

Each step in the evaluation of any Wolfram System expression can be thought of as the result of applying a particular transformation rule. As discussed in "Associating Definitions with Different Symbols", all the rules that the Wolfram System knows are associated with specific symbols or "tags". You can use (RefLink[Trace, paclet:ref/Trace])[expr,f] to see all the steps in the evaluation of expr that are performed using transformation rules associated with the symbol f. In this case, (RefLink[Trace, paclet:ref/Trace]) gives not only the expressions to which each rule is applied, but also the results of applying the rules.

In general, (RefLink[Trace, paclet:ref/Trace])[expr,form] picks out all the steps in the evaluation of expr where form matches either the expression about to be evaluated, or the tag associated with the rule used.

Tracing evaluations associated with particular tags.

This shows only intermediate expressions that match fac[_]:

Trace[fac[3],fac[_]]

This shows all evaluations that use transformation rules associated with the symbol fac:

Trace[fac[3],fac]

Here is a rule for the log function:

log[x_ y_]:=log[x]+log[y]

This traces the evaluation of log[abcd], showing all transformations associated with log:

Trace[log[a b c d],log]

Switching off tracing inside certain forms.

(RefLink[Trace, paclet:ref/Trace])[expr,form] allows you to trace expressions matching form generated at any point in the evaluation of expr. Sometimes, you may want to trace only expressions generated during certain parts of the evaluation of expr.

By setting the option (RefLink[TraceOn, paclet:ref/TraceOn])->oform, you can specify that tracing should be done only during the evaluation of forms that match oform. Similarly, by setting (RefLink[TraceOff, paclet:ref/TraceOff])->oform, you can specify that tracing should be switched off during the evaluation of forms that match oform.

This shows all steps in the evaluation:

Trace[log[fac[2] x]]

This shows only those steps that occur during the evaluation of fac:

Trace[log[fac[2] x],TraceOn->fac]

This shows only those steps that do not occur during the evaluation of fac:

Trace[log[fac[2] x],TraceOff->fac]

Applying rules to expressions encountered during evaluation.

This tells (RefLink[Trace, paclet:ref/Trace]) to return only the arguments of fib used in the evaluation of fib[5]:

Trace[fib[5],fib[n_]->n]

A powerful aspect of the Wolfram System (RefLink[Trace, paclet:ref/Trace]) function is that the object it returns is basically a standard Wolfram System expression that you can manipulate using other Wolfram System functions. One important point to realize, however, is that (RefLink[Trace, paclet:ref/Trace]) wraps all expressions that appear in the list it produces with (RefLink[HoldForm, paclet:ref/HoldForm]) to prevent them from being evaluated. The (RefLink[HoldForm, paclet:ref/HoldForm]) is not displayed in standard Wolfram System output format, but it is still present in the internal structure of the expression.

This shows the expressions generated at intermediate stages in the evaluation process:

Trace[1+3^2]

The expressions are wrapped with (RefLink[HoldForm, paclet:ref/HoldForm]) to prevent them from evaluating:

Trace[1+3^2]//InputForm

In standard Wolfram System output format, it is sometimes difficult to tell which lists are associated with the structure returned by (RefLink[Trace, paclet:ref/Trace]), and which are expressions being evaluated:

Trace[{1+1,2+3}]

Looking at the input form resolves any ambiguities:

InputForm[%]

When you use a transformation rule in (RefLink[Trace, paclet:ref/Trace]), the result is evaluated before being wrapped with (RefLink[HoldForm, paclet:ref/HoldForm]):

Trace[fac[4],fac[n_]->n+1]

For sophisticated computations, the list structures returned by (RefLink[Trace, paclet:ref/Trace]) can be quite complicated. When you use (RefLink[Trace, paclet:ref/Trace])[expr,form], (RefLink[Trace, paclet:ref/Trace]) will include as elements in the lists only those expressions that match the pattern form. But whatever pattern you give, the nesting structure of the lists remains the same.

This shows all occurrences of fib[_] in the evaluation of fib[3]:

Trace[fib[3],fib[_]]

This shows only occurrences of fib[1], but the nesting of the lists is the same as for fib[_]:

Trace[fib[3],fib[1]]

You can set the option (RefLink[TraceDepth, paclet:ref/TraceDepth])->n to tell (RefLink[Trace, paclet:ref/Trace]) to include only lists nested at most n levels deep. In this way, you can often pick out the "big steps" in a computation, without seeing the details. Note that by setting (RefLink[TraceDepth, paclet:ref/TraceDepth]) or (RefLink[TraceOff, paclet:ref/TraceOff]) you can avoid looking at many of the steps in a computation, and thereby significantly speed up the operation of (RefLink[Trace, paclet:ref/Trace]) for that computation.

This shows only steps that appear in lists nested at most two levels deep:

Trace[fib[3],fib[_],TraceDepth->2]

Restricting the depth of tracing.

When you use (RefLink[Trace, paclet:ref/Trace])[expr,form], you get a list of all the expressions that match form produced during the evaluation of expr. Sometimes it is useful to see not only these expressions, but also the results that were obtained by evaluating them. You can do this by setting the option (RefLink[TraceForward, paclet:ref/TraceForward])->(RefLink[True, paclet:ref/True]) in (RefLink[Trace, paclet:ref/Trace]).

This shows not only expressions that match fac[_], but also the results of evaluating those expressions:

Trace[fac[4],fac[_],TraceForward->True]

Expressions picked out using (RefLink[Trace, paclet:ref/Trace])[expr,form] typically lie in the middle of an evaluation chain. By setting (RefLink[TraceForward, paclet:ref/TraceForward])->(RefLink[True, paclet:ref/True]), you tell (RefLink[Trace, paclet:ref/Trace]) to include also the expression obtained at the end of the evaluation chain. If you set (RefLink[TraceForward, paclet:ref/TraceForward])->(RefLink[All, paclet:ref/All]), (RefLink[Trace, paclet:ref/Trace]) will include all the expressions that occur after the expression matching form on the evaluation chain.

With (RefLink[TraceForward, paclet:ref/TraceForward])->(RefLink[All, paclet:ref/All]), all elements on the evaluation chain after the one that matches fac[_] are included:

Trace[fac[4],fac[_],TraceForward->All]

By setting the option (RefLink[TraceForward, paclet:ref/TraceForward]), you can effectively see what happens to a particular form of expression during an evaluation. Sometimes, however, you want to find out not what happens to a particular expression, but instead how that expression was generated. You can do this by setting the option (RefLink[TraceBackward, paclet:ref/TraceBackward]). What (RefLink[TraceBackward, paclet:ref/TraceBackward]) does is to show you what preceded a particular form of expression on an evaluation chain.

This shows that the number 120 came from the evaluation of fac[5] during the evaluation of fac[10]:

Trace[fac[10],120,TraceBackward->True]

Here is the whole evaluation chain associated with the generation of the number 120:

Trace[fac[10],120,TraceBackward->All]

(RefLink[TraceForward, paclet:ref/TraceForward]) and (RefLink[TraceBackward, paclet:ref/TraceBackward]) allow you to look forward and backward in a particular evaluation chain. Sometimes, you may also want to look at the evaluation chains within which the particular evaluation chain occurs. You can do this using (RefLink[TraceAbove, paclet:ref/TraceAbove]). If you set the option (RefLink[TraceAbove, paclet:ref/TraceAbove])->(RefLink[True, paclet:ref/True]), then (RefLink[Trace, paclet:ref/Trace]) will include the initial and final expressions in all the relevant evaluation chains. With (RefLink[TraceAbove, paclet:ref/TraceAbove])->(RefLink[All, paclet:ref/All]), (RefLink[Trace, paclet:ref/Trace]) includes all the expressions in all these evaluation chains.

This includes the initial and final expressions in all evaluation chains that contain the chain that contains 120:

Trace[fac[7],120,TraceAbove->True]

This shows all the ways that fib[2] is generated during the evaluation of fib[5]:

Trace[fib[5],fib[2],TraceAbove->True]

Option settings for including extra steps in trace lists.

The basic way that (RefLink[Trace, paclet:ref/Trace])[expr,…] works is to intercept each expression encountered during the evaluation of expr, and then to use various criteria to determine whether this expression should be recorded. Normally, however, (RefLink[Trace, paclet:ref/Trace]) intercepts expressions only after function arguments have been evaluated. By setting (RefLink[TraceOriginal, paclet:ref/TraceOriginal])->(RefLink[True, paclet:ref/True]), you can get (RefLink[Trace, paclet:ref/Trace]) also to look at expressions before function arguments have been evaluated.

This includes expressions that match fac[_] both before and after argument evaluation:

Trace[fac[3],fac[_],TraceOriginal->True]

The list structure produced by (RefLink[Trace, paclet:ref/Trace]) normally includes only expressions that constitute steps in non-trivial evaluation chains. Thus, for example, individual symbols that evaluate to themselves are not normally included. Nevertheless, if you set (RefLink[TraceOriginal, paclet:ref/TraceOriginal])->(RefLink[True, paclet:ref/True]), then (RefLink[Trace, paclet:ref/Trace]) looks at absolutely every expression involved in the evaluation process, including those that have trivial evaluation chains.

In this case, (RefLink[Trace, paclet:ref/Trace]) includes absolutely all expressions, even those with trivial evaluation chains:

Trace[fac[1],TraceOriginal->True]

Additional options for (RefLink[Trace, paclet:ref/Trace]).

When you use (RefLink[Trace, paclet:ref/Trace]) to study the execution of a program, there is an issue about how local variables in the program should be treated. As discussed in "How Modules Work", Wolfram System scoping constructs such as (RefLink[Module, paclet:ref/Module]) create symbols with new names to represent local variables. Thus, even if you called a variable x in the original code for your program, the variable may effectively be renamed x$nnn when the program is executed.

(RefLink[Trace, paclet:ref/Trace])[expr,form] is set up so that by default a symbol x that appears in form will match all symbols with names of the form x$nnn that arise in the execution of expr. As a result, you can for example use (RefLink[Trace, paclet:ref/Trace])[expr,x=_] to trace assignment to all variables, local and global, that were named x in your original program.

Preventing the matching of local variables.

In some cases, you may want to trace only the global variable x, and not any local variables that were originally named x. You can do this by setting the option (RefLink[MatchLocalNames, paclet:ref/MatchLocalNames])->(RefLink[False, paclet:ref/False]).

This traces assignments to all variables with names of the form x$nnn:

Trace[Module[{x},x=5],x=_]

This traces assignments only to the specific global variable x:

Trace[Module[{x},x=5],x=_,MatchLocalNames->False]

The function (RefLink[Trace, paclet:ref/Trace]) performs a complete computation, then returns a structure that represents the history of the computation. Particularly in very long computations, it is however sometimes useful to see traces of the computation as it proceeds. The function (RefLink[TracePrint, paclet:ref/TracePrint]) works essentially like (RefLink[Trace, paclet:ref/Trace]), except that it prints expressions when it encounters them, rather than saving up all of the expressions to create a list structure.

This prints expressions encountered in the evaluation of fib[3]:

TracePrint[fib[3],fib[_]]

The sequence of expressions printed by (RefLink[TracePrint, paclet:ref/TracePrint]) corresponds to the sequence of expressions given in the list structure returned by (RefLink[Trace, paclet:ref/Trace]). Indentation in the output from (RefLink[TracePrint, paclet:ref/TracePrint]) corresponds to nesting in the list structure from (RefLink[Trace, paclet:ref/Trace]). You can use the (RefLink[Trace, paclet:ref/Trace]) options (RefLink[TraceOn, paclet:ref/TraceOn]), (RefLink[TraceOff, paclet:ref/TraceOff]) and (RefLink[TraceForward, paclet:ref/TraceForward]) in (RefLink[TracePrint, paclet:ref/TracePrint]). However, since (RefLink[TracePrint, paclet:ref/TracePrint]) produces output as it goes, it cannot support the option (RefLink[TraceBackward, paclet:ref/TraceBackward]). In addition, (RefLink[TracePrint, paclet:ref/TracePrint]) is set up so that (RefLink[TraceOriginal, paclet:ref/TraceOriginal]) is effectively always set to (RefLink[True, paclet:ref/True]).

Functions for tracing evaluation.

This enters a dialog when fac[5] is encountered during the evaluation of fac[10]:

TraceDialog[fac[10],fac[5]]

Inside the dialog you can for example find out where you are by looking at the "stack":

Stack[]

This returns from the dialog, and gives the final result from the evaluation of fac[10]:

Return[]

The function (RefLink[TraceDialog, paclet:ref/TraceDialog]) effectively allows you to stop in the middle of a computation and interact with the Wolfram System environment that exists at that time. You can, for example, find values of intermediate variables in the computation, and even reset those values. There are, however, a number of subtleties, mostly associated with pattern and module variables.

What (RefLink[TraceDialog, paclet:ref/TraceDialog]) does is to call the function (RefLink[Dialog, paclet:ref/Dialog]) on a sequence of expressions. The (RefLink[Dialog, paclet:ref/Dialog]) function is discussed in detail in "Dialogs". When you call (RefLink[Dialog, paclet:ref/Dialog]), you are effectively starting a subsidiary Wolfram System session with its own sequence of input and output lines.

In general, you may need to apply arbitrary functions to the expressions you get while tracing an evaluation. (RefLink[TraceScan, paclet:ref/TraceScan])[f,expr,…] applies f to each expression that arises. The expression is wrapped with (RefLink[HoldForm, paclet:ref/HoldForm]) to prevent it from evaluating.

In (RefLink[TraceScan, paclet:ref/TraceScan])[f,expr,…], the function f is applied to expressions before they are evaluated. (RefLink[TraceScan, paclet:ref/TraceScan])[f,expr,patt,fp] applies f before evaluation, and fp after evaluation.