Is this a bug in Replace?

Question

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[1]:= tree[B,{1,2}]  
During evaluation of In[1]:= tree[A,{0,3}]  
Out[1]= 0

This one however introduces an unexpected intermediate step.

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

During evaluation of In[3]:= tree[B,{1,2}]tree[B,{1,2}]
During evaluation of In[3]:= tree[B,{1,2}]tree[B,{1,2}]
During evaluation of In[3]:= tree[A,{0,3}]tree[A,{0,3}]
Out[3]= 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.

Answer 1

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.