Is it possible to construct a fullform trace function

Question

Is it possible to construct a FullFormTrace function that takes an arbitrary expression and prints a sequence (or returns a list) of the evaluation steps in full form. For instance

FullFormTrace[(1+2*3)^2]

would output

Power[Plus[1,Times[2,3]],2] 
Power[Plus[1,6],2] 
Power[7,2] 
49

The same output would come if the expression is entered in full form to begin with so

FullFormTrace[Power[Plus[1,Times[2,3]],Plus[1,1]]]

would give the same output

I tried the Trace function

Trace[Power[Plus[1,Times[2,3]],2]]

but I get as output

{{{2 3,6},1+6,7},7^2,49}

which is not of the above form.

Answer 1

You may use Inactivate to step through the calculation while evaluating in place. Then convert these results into FullForm with HoldForm to prevent evaluation.

First a helper function to evaluate in place.

ClearAll[traceInPlace];
SetAttributes[traceInPlace, {HoldFirst}];
traceInPlace[expr_] :=
 With[{ex = Inactivate[expr]},
  FoldList[
   MapAt[Replace[Inactive -> Identity], #2]@#1 &,
   ex,
   Reverse@Position[ex, Inactive]
   ]]

traceInPlace works like so

traceInPlace[(1 + 2*3)^2] // Column

Then it is only a matter of converting these to FullForm and removing the Inactive heads created by Inactivate.

Activate@HoldForm@FullForm@# & /@ traceInPlace[(1 + 2*3)^2] // Column

Power[Plus[1,Times[2,3]],2]
Power[Plus[1,6],2]
Power[7,2]
49

Each item is wrapped in Hold but if it were not then it would evaluate.

You can also use different forms. For example:

Activate@HoldForm@TraditionalForm@# & /@ traceInPlace[(1 + 2*3)^2] // Column

Hope this helps.

Update: Thanks to @jjc385 for suggesting HoldForm instead of Hold. Change made above.

Answer 2

ff = FullForm /@ Trace[Power[Plus[1, Times[2, 3]], 2], TraceOriginal -> True];

sf = ToString /@ ff;

Fold[StringDelete[#1, #2] &, sf, {"HoldForm[", "]," ~~ EndOfString}]

{Power[Plus[1, Times[2, 3]], 2]],
 List[Power]], List[Plus[1, Times[2, 3]]], List[Plus]],
   List[1]], List[Times[2, 3]], List[Times]], List[2]], List[3]],
   Times[2, 3]], 6]], Plus[1, 6]], 7]], List[2]], Power[7, 2]], 49]}

Still a lot of junk in there, and no clear way to parse it to get the OP's requirement ...

Power[Plus[1,Times[2,3]],2] 
Power[Plus[1,6],2] 
Power[7,2] 
49

Answer 3

Here's one way.

Find the depth of the expression and evaluate parts level by level.

ex = Hold[(1 + 2*3)^2];
f[expr_] := 
 Replace[FullForm[expr], x_ :> With[{eval = x}, eval /; True], {#}] & /@ 
  Range[Depth[expr], 2, -1]

f[ex] // Column

Hold[Power[Plus[1,Times[2,3]],2]]
Hold[Power[Plus[1,6],2]]
Hold[Power[7,2]]
Hold[49]

For more information on the evaluation, please check this and this.

Answer 4

The following shows the output of Trace in FullForm, which is not exactly the desired output shown in the OP. But then the output shown does not correspond to the description of the problem exactly, so my guess is that this is what is desired.

Trace[(1 + 2*3)^2] /. HoldForm[e_] :> HoldForm[FullForm@e]

Possible alternatives, depending on how much of the evaluation sequence is desired:

TraceScan[Print[# /. HoldForm[e_] :> HoldForm[FullForm[e]]] &, (1 + 2*3)^2]

TraceScan[
 If[MatchQ[#, HoldForm[e_] /; ! AtomQ[Unevaluated@e]], 
   Print[# /. HoldForm[e_] :> HoldForm[FullForm[e]]]] &, (1 + 2*3)^2]

Answer 5

I'm late I know, but I tried a different approach that is related to what Micheal did. I used Trace in the following form

The structure of each list in the output is similar. Either it consists of only one element when the sub-expression is atomic or it consists of

• original sub-expression
• evaluation of head
• evaluation of all arguments
• expression with evaluated arguments
• final result

If you look at the inner 2^2 list, you see that it always follows this and indeed, this is roughly how the main evaluation works. My goal was to take only the output of trace and construct a sequence of lines, where each line shows the whole current expression and highlights which part is currently evaluated by Mathematica. This makes very clear, how sub-expressions are transformed and how the final result is achieved. It will work like this

To do the highlighting work, I didn't use expressions. Instead, I create an expression tree. This spares me the work of continually preventing expressions from evaluation, and I can quickly highlight specific subtrees.

SetAttributes[tree, {HoldAllComplete}];
tree[(h_)[args___]] := node[tree[h], Sequence @@ (tree /@ Unevaluated[{args}])];
tree[e_?AtomQ] := leaf[e]

tree[1 + 3^2] // TreeForm

Next step was to code a pretty-printer for such trees. This is basically walking the tree and creating low-level boxes for the nodes.

TreePrint[t_] := Print[DisplayForm[StyleBox[treePrint[t], FontFamily -> "Courier"]]];
bold[s_] := StyleBox[s, FontWeight -> Bold];
color[s_] := StyleBox[s, FontColor -> ColorData[3, 10]];
treePrint[hilit[arg_]] := color[treePrint[arg]];
treePrint[node[head_, childs___]] := RowBox[{treePrint[head], bold["["], 
    RowBox[Riffle[treePrint /@ {childs}, ", "]], bold["]"]}];
treePrint[leaf[l_]] := ToString[l];

Now I can get the full form very easily

tree[1 + 3^2] // TreePrint

(* Plus[1, Power[3, 2]] *)

If I like to highlight a subtree, I just have to wrap the node in hilit and the whole sub-tree is printed in red.

The algorithm for transforming a trace output is not really hard. I just need to go through the list and replace parts of the current tree. For instance, in my very first example: If I ignore the evaluation of the head and arguments for the moment, it is basically

• set the current tree to 1+2^2
• set the current tree to 1+4
• set the current tree to 5

As soon as you accept, that evaluating the arguments is the same thing, only on a sub-tree of the whole expression, it's easy to understand. To know on which sub-tree I'm working, I need to carefully store how often I dived into an argument list and at which position I am.

Module[{$currentTree = Null},
 SetAttributes[SimpleTrace, {HoldFirst}];
 SimpleTrace[expr_] := scan[Trace[expr, TraceOriginal -> True]];

 scan[elms_List, pos___] := Module[{count = 1},
   Do[
     Switch[e,
       _HoldForm,
       $currentTree[[pos]] = hilit@Apply[tree, e];
       TreePrint[$currentTree];
       $currentTree[[pos]] = $currentTree[[pos, 1]],
       _List,
       scan[e, pos, count++]
       ];
     , {e, elms}
     ];
   ]
 ]

After the _HoldForm in the switch, I'm temporarily adding hilit to the current sub-tree, print it and remove the hilit again. This all can be implemented properly, but it's only a showcase after all. Now, you are good to go to study the original question:

SimpleTrace[(1 + 2*3)^2]

And finally, it takes only some minor changes to check if the tree had changed and print the tree only if there was a structural replacement. This gives the output that was originally asked for:

SimpleTrace[(1 + 2*3)^2]

(*
Power[Plus[1, Times[2, 3]], 2]
Power[Plus[1, 6], 2]
Power[7, 2]    
49
*)

Restrictions

This approach only works, when trace follows the described pattern consistently. This is not always true when functions like Map or Fold are used that don't transform the current tree, but evaluate independent sub-expressions. One simple example is

Trace[FoldList[#1 + #2 &, 0, {10, 11}], TraceOriginal -> True] // Column

FoldList[#1+#2&,0,{10,11}]
{FoldList}
{#1+#2&,{Function},#1+#2&}
{0}
{{10,11}}
(* next is the final new sub tree *)
FoldList[#1+#2&,0,{10,11}]
(* here a new sub-evaluation is evaluated 
   that cannot be included into the last sub-tree *)
{(#1+#2&)[0,10],{#1+#2&},{0},{10},(#1+#2&)[0,10],0+10,{Plus},{0},{10},0+10,10}
{(#1+#2&)[10,11],{#1+#2&},{10},{11},(#1+#2&)[10,11],10+11,{Plus},{10},{11},10+11,21}
{0,10,21}