# Is this a bug in Replace?

Consider the following minimal examples. This one works as expected, replacing trees starting from the inside with a numerical value.

ClearAll[tree];
x = tree["A", {tree["B", {1, 2}], 3}];
Replace[x, t_tree :> (Print[t]; 0), {0, Infinity}]

During evaluation of In:= tree[B,{1,2}]
During evaluation of In:= tree[A,{0,3}]
Out= 0


This one however introduces an unexpected intermediate step.

Replace[x, t_tree :> (Print[t, t]; 0), {0, Infinity}]

During evaluation of In:= tree[B,{1,2}]tree[B,{1,2}]
During evaluation of In:= tree[B,{1,2}]tree[B,{1,2}]
During evaluation of In:= tree[A,{0,3}]tree[A,{0,3}]
Out= 0


While the results are the same, anything more complicated than Print[t] causes extra stages to appear. Hence I cannot reliably use Replace to collect replaced parts (instead of printing them), as there would be excess entries at the end, see next example:

y = {}; Replace[x, t_tree :> (AppendTo[y, t]; 0), {0, Infinity}]; y

{tree["B", {1, 2}], tree["A", {0, 3}]}

y = {}; Replace[x, t_tree :> (AppendTo[y, t -> Mean@Last@t]; 0), {0, Infinity}]; y

{tree["B", {1, 2}] -> 3/2, tree["B", {1, 2}] -> 3/2, tree["A", {0, 3}] -> 3/2}


There are three replacements instead of two.

• I hit this problem multiple times, every time having forgotten about the earlier one, and taking a while to understand what was going on. – Szabolcs Sep 7 '16 at 12:05
• – Kuba Sep 7 '16 at 12:09
• @Kuba Yes, it seems to be a duplicate. – István Zachar Sep 7 '16 at 12:18

This is not a bug. However, this is a great opportunity to shed some light on the inner workings of Replace. What happens, in short, is that it first fully processes the expression, without calling main evaluator on any of its replaced parts, and only then the entire transformed expression is given to the evaluator.

Basically, we can visualize what happens using this:

held = Replace[Hold[Evaluate[x]],t_tree :> (Print[t, t]; 0), {0, Infinity}]

(*
Hold[
Print[tree["A", {Print[tree["B", {1, 2}], tree["B", {1, 2}]]; 0, 3}],
tree["A", {Print[tree["B", {1, 2}], tree["B", {1, 2}]]; 0, 3}]]; 0
]
*)


which shows the origin of extra Print.

What you were assuming was that the evaluation of replaced parts happens right after they were replaced, which would mean that Replace would have to call main evaluator after replacement at each level. Instead, the action of Replace is semantically equivalent to

ReleaseHold[Replace[Hold[expr], rules, spec]]


which may produce different result if side effects are injected by replacement rules.

• Well, I had the suspicion, that there shouldn't be a bug in a core function, and I'm glad I was cautious with the tagging. Thanks for the explanation! Do you also have a suggestion how to robustly solve what I want to do: depth-first sequential replacement from inside-out with storing actual replacements by AppendTo or Sow? – István Zachar Sep 7 '16 at 12:14
• @IstvánZachar You could write your own expression parser, that would do expression traversal. Or use something like Fold[Replace[#, rules, {#2}]&, expr, Reverse[Range[Length[Depth[expr]]]]] (pseudocode, untested). – Leonid Shifrin Sep 7 '16 at 13:14
• @IstvánZachar Another possibility might be to force early evaluation using one of the techniques described in Replacement inside held expression. For example: Replace[x, t_tree :> With[{}, Print[t, t]; 0 /; True], {0, Infinity}]. – WReach Sep 8 '16 at 11:52
• Thanks @Leonid, I ended up using the reversed-level-scan method, which I already used in other cases but forgot about. Somewhat hoped maybe there is a new function capable of this natively in v11 that I missed. Just for the record, the level specification should rather be Range[Depth[expr], 0, -1] if I'm not mistaken. – István Zachar Sep 8 '16 at 18:40
• @WReach I think that the applicability of the Trott-Strzebonski trick to Replace is so unobvious that it is worth to post this as a separate answer. Also this example (along with Leonid's explanation) is very enlightening for understanding the essence of the trick itself. – Alexey Popkov Sep 17 '16 at 11:07