Understanding Trace*

Good day,

When trying to understand the Mathematica's evaluation sequence by using standard Trace and TraceScan commands and their nice visual representations developed in the recent thread, I faced some ambiguities in their behavior.

First of all, when I evaluate

In[1]:= Trace[a+1,TraceOriginal->True]

I get

Out[1]= {a+1,{Plus},{a},{1},a+1,1+a,{Plus},{1},{a},1+a}

All sublists correspond to sub-evaluations (as it is stated in the Documentation). The last expression 1+a probably corresponds to the result of the evaluation although it is not clearly stated in the Documentation. But what exactly mean expressions a+1 and 1+a in the middle of the list? To which evaluation steps of the standard evaluation sequence they correspond?

The second oddity is with TraceScan. Consider the following:

In[1]:= list={}; TraceScan[AppendTo[list,StyleForm[#,"Input"]]&,(a+1),_,AppendTo[list,#]&]; list

Out[1]= {a+1, Plus, Plus, a, a, 1, 1, 1+a, Plus, Plus, 1, 1, a, a, 1+a, a+1}

You can see that the last two expressions in the list are 1+a and a+1. Both are results of (sub)evaluations. But the real output is 1+a and so I do not understand why a+1 is at the end of the evaluation chain? And why is no there a+1 in the middle of the eva开发者_Go百科luation chain as it was in the case of Trace? Is it a bug?

P.S. These results are reproduced with Mathematica 7.0.1 and 5.2.

The fp argument to TraceScan is called with two arguments. The first is the original unevaluated expression. The second is the result of the evaluation. In your example, the second AppendTo is using the first argument so you are seeing the unevaluated expression. Change # to #2 and then you will see the results you expect.

Also note that the second argument is not wrapped in HoldForm (documentation notwithstanding), so in general one must take care to use a function that holds its arguments for the fp argument to avoid generating spurious evaluations.

Comparing Trace and TraceScan

The behaviour of Trace is described in considerable detail in the Mathematica 8 documentation. It states that, by default, Trace only shows expressions after the head and arguments have been evaluated. Thus, we see a sequence like this:

In[28]:= SetAttributes[f, Orderless]
         Trace[f[a, 1]]
Out[29]= {f[a,1],f[1,a]}

Only the input expression and its result is shown. The TraceOriginal options controls (quote) "whether to look at expressions before their heads and arguments are evaluated". When this option is True then the output is supplemented with the head and argument expressions:

In[30]:= Trace[f[a,1], TraceOriginal->True]
Out[30]= {f[a,1],{f},{a},{1},f[a,1],f[1,a]}

The first element of the new list is the original expression before the head and arguments are evaluated. Then we see the head and arguments being evaluated. Finally, we see the top-level expressions again, after the head and arguments have been evaluated. The last two elements of the list match the two elements of the original trace output.

As the linked documentation states, Trace is very selective about what expressions it returns. For example, it omits trivial evaluation chains completely. TraceScan is comprehensive and calls the supplied functions for every evaluation, trivial or not. You can see the comprehensive set of evaluations using the following TraceScan expression:

TraceScan[Print, f[a,1], _, Print[{##}]&]

The following table matches the output produced by Trace with and without TraceOriginal, along with the output of the TraceScan expression:

Trace   Trace    TraceScan
        Original

        f[a,1]   f[a,1]
                 f
        {f}      {f
                 ,f}
                 a
        {a}      {a
                 ,a}
                 1
        {1}      {1
                 ,1}
                 f[1,a]
                 {f[1,a]
                 ,f[1,a]}
f[a,1]  f[a,1]   {f[a,1]
f[1,a]  f[1,a]   ,f[1,a]}

There is certain amount of speculation in this table about which entry matches against which, given that the internals of Trace are inaccessible. Further experiments might give information that adjusts the alignment. However, the key point is that all of the information generated by Trace is available using TraceScan -- and TraceScan provides more.

The first part of the question is easy. The expressions a+1 and 1+a in the middle of the list are where the Orderless attribute of Plus fires and the terms are arranged in the default order. This is point number 8 in the standard evaluation sequence tute.

The "strangeness" in TraceScan also occurs in version 8. Because, it's a rare command, here's the documentation for TraceScan

TraceScan[f, expr, form, fp] applies f before evaluation and fp after evaluation to expressions used in the evaluation of expr.

Note that if you apply it to the expression a + 1 + b you get

In[32]:= TraceScan[Print["f \t",#]&, a+1+b, _, Print["fp\t",#]&]
During evaluation of In[32]:= f     a+1+b
During evaluation of In[32]:= f     Plus
During evaluation of In[32]:= fp    Plus
During evaluation of In[32]:= f     a
During evaluation of In[32]:= fp    a
During evaluation of In[32]:= f     1
During evaluation of In[32]:= fp    1
During evaluation of In[32]:= f     b
During evaluation of In[32]:= fp    b
During evaluation of In[32]:= f     1+a+b
During evaluation of In[32]:= fp    1+a+b
During evaluation of In[32]:= fp    a+1+b
Out[32]= 1+a+b

From here, it's clear what's happening. fp applies after the evaluation - so the final fp actually corresponds to the first f. It doesn't print until the very end because the subexpressions need to be evaluated first.