Why doesn't RuleDelayed hold Unevaluated?

The Mathematica's evaluator generally holds (or restores?) Heads Unevaluated of expressions supplied as arguments for Symbols:

In[1]:= f[s, Unevaluated[1 + 1]]

Out[2]= f[s, Unevaluated[1 + 1]]

In[5]:= Trace[f[s,Unevaluated[1+1]],TraceOriginal->True]

Out[5]= {f[s,Unevaluated[1+1]],{f},{s},f[s,1+1],f[s,Unevaluated[1+1]]}

But it is not true for RuleDelayed. Moreover, any number of Unevaluated wrappers are stripped in the case of RuleDelayed:

In[1]:= Attributes@RuleDelayed
RuleDelayed[s, Unevaluated[1 + 1]]
RuleDelayed[s, Unevaluated@Unevaluated[1 + 1]]
RuleDelayed[s, Unevaluated@Unevaluated@Unevaluated[1 + 1]]
RuleDelayed[Unevaluated@Unevaluated@Unevaluated[1 + 1], 1 + 1]

Out[1]= {HoldRest, Protected, SequenceHold}

Out[2]= s :> 1 + 1

Out[3]= s :> 1 + 1

Out[4]= s :> 1 + 1

Out[5]= 2 :> 1 + 1

Why does the evaluator strip any number of Unevaluated wrappers in the case of RuleDelayed? For which purposes is it useful? Is it possible to simulate such behavior for an arbitrary Symbol (f, for example)?

---

It is also not clear why the Trace shows more complicated picture for RuleDelayed than for f:

In[2]:= Trace[RuleDelayed[s,1+1],开发者_C百科TraceOriginal->True]
Out[2]= {s:>1+1,{RuleDelayed},{s},s:>1+1,s:>1+1,{RuleDelayed},{s},s:>1+1}

It looks like RuleDelayed is evaluated twice...

---

This answer should be considered as complementary to @Sasha's answer. I believe that this is a subtle topic that can benefit from explanations from several viewpoints.

Why the question is non-trivial

I want to stress that the behavior in question is not typical, in the sense that it is not how most heads behave in Mathematica, and it can not be explained based just on the general principles of evaluation (in particular mechanics of Unevaluated stripping), without resorting to implementation details of a particular head with such behavior (RuleDelayed here). Consider some general head with a HoldRest attribute:

In[185]:= SetAttributes[h, HoldRest];
h[1, Unevaluated[Unevaluated[Unevaluated[1 + 1]]]]

Out[186]= h[1, Unevaluated[Unevaluated[Unevaluated[1 + 1]]]]

while

In[209]:= 1:>Unevaluated@Unevaluated@Unevaluated[1+1]

Out[209]= 1:>1+1

Some details on stripping off the Unevaluated wrapers

This is based on discussions in the book of David Wagner "Power programming in Mathematica - the kernel", the WRI technical report by David Withoff named "Mathematica internals", and my own experiences.

Here is a very simplified picture of evaluation. Mathematica evaluates expressions recursively, first going "down" from "branches" (expressions) to "sub-branches" (sub-expressions) and leaves (atoms), and then going "up". On the way "down", heads of (sub) expressions are evaluated, and then parts. Those parts that have the head Unevaluated, are not evaluated further (in the sense that the evaluator is not called recursively on them), while Unevaluated gets stripped and it is marked that this has been done. On the way "up", it is considered that parts have been already evaluated. There are a number of steps including sequences splicing, evaluations related to attributes like Flat, Orderless etc. Then, rules for the head where evaluation is currently, are applied, user-defined and built-in (UpValues, DownValues, SubValues). Finally, and this is what is important for this discussion, the Unevaluated wrappers are restored for those parts of expression where no applicable rules were found. This is why, for an undefined function f, we have:

In[188]:= ClearAll[f];
f[Unevaluated[1+1]]

Out[189]= f[Unevaluated[1+1]]

One can confirm that Unevaluated wrappers were stripped and then restored, by using Trace with the TraceOriginal option set to True:

In[190]:= Trace[f[Unevaluated[1+1]],TraceOriginal->True]

Out[190]= {f[Unevaluated[1+1]],{f},f[1+1],f[Unevaluated[1+1]]} 

What happens when there are some rules defined for f? The answer is that each rule application strips off one layer of Unevaluated. Here is an example:

In[204]:= 
f[x_]:=Hold[x]; 
g[x_]:=f[x];
{f[Unevaluated[1+1]],g[Unevaluated[1+1]]}
{f[Unevaluated@Unevaluated[1+1]],g[Unevaluated@Unevaluated[1+1]]}
{f[Unevaluated@Unevaluated@Unevaluated[1+1]], g[Unevaluated@Unevaluated@Unevaluated[1+1]]}

Out[206]= {Hold[1+1],Hold[2]}
Out[207]= {Hold[Unevaluated[1+1]],Hold[1+1]}
Out[208]= {Hold[Unevaluated[Unevaluated[1+1]]],Hold[Unevaluated[1+1]]}

If one knew in exactly how many evaluations will a given part of expression particiapte, one could in principle wrap that part in that many layers of Unevaluated to prevent its evaluation. This information is however impossible to have generally, and Unevaluated should not be used as a persistent holding wrapper - this is what Hold is for. But this analysis may make it clearer that, in order to trip any number of evaluations, the head which does it must have non-trivial rules defined for it. In other words, normally, the part of evaluation process consisting of stripping off a layer of Unevaluated does not (by itself, "on the way down the expression"), induce its re-evaluation - this can happen only on the way "up", due to some rules defined for that head. The conclusion is that the observed behavior of RuleDelayed can only be explained by looking at the implementation details for RuleDelayed, general considerations are not enough.

An illustration: simulating the behavior of RuleDelayed

I will now illustrate this and also answer the part of the original question regarding the simulation of this behavior. As far as I can tell, the following code fully simulates the behavior of RuleDelayed regarding stripping off Unevaluated wrappers:

ClearAll[rd];
SetAttributes[rd, {HoldAllComplete, SequenceHold}];
rd[lhs_, Verbatim[Unevaluated][rhs_]] /;
   Head[Unevaluated[rhs]] =!= Unevaluated := Append[rd[lhs], Unevaluated[rhs]];
rd[lhs_, Verbatim[Unevaluated][rhs_]] := rd @@ {lhs, rhs};
rd[lhs_, rhs_] /; Hold[lhs] =!= Hold[Evaluate[lhs]] := Prepend[rd[rhs], lhs];

(it may not be free of some evaluation leaks for other heads, but that's besides the point. Also, I was not able to make it HoldRest, like RuleDelayed - I had to use HoldAllComplete for this construction to work). You can check:

In[173]:= 
a=1;
rd[a,Unevaluated[1+1]]
rd[a,Unevaluated@Unevaluated[1+1]]
rd[a,Unevaluated@Unevaluated[1+1]]

Out[174]= rd[1,1+1]
Out[175]= rd[1,1+1]
Out[176]= rd[1,1+1]

This indirectly supports my arguments that it may be the RuleDelayed implementation, rather than the evaluator, responsible for this effect (although, not knowing for sure, I can only guess. Also, RuleDeleayed is fundamental enough that this exceptional behavior could have been wired into the evaluator)

EDIT

To further strengthen the analogy, here are the results of tracing:

In[183]:= 
DeleteCases[Trace[rd[s,Unevaluated[1+1]],TraceOriginal->True],
    x_/;!FreeQ[x,Head|Hold|Append|HoldPattern[rd[_]]]]

Out[183]= {rd[s,Unevaluated[1+1]],{rd},rd[s,Unevaluated[1+1]],
    rd[s,1+1],{rd},rd[s,1+1],rd[s,1+1]}

In[184]:= Trace[RuleDelayed[s,Unevaluated[1+1]],TraceOriginal->True]

Out[184]= {s:>Unevaluated[1+1],{RuleDelayed},{s},s:>1+1,s:>1+1,{RuleDelayed},{s},s:>1+1}    

The tracing results are very similar. I used DeleteCases to filter out intermediate evaluations for rd. The differences are due to the HoldAllComplete attribute of rd vs. HoldRest of RuleDelayed.

---

Unevaluated gets stripped when it occurs as the outermost wrapper in a rule. This is how Unevaluated works, i.e. Unevaluated is not a regular symbol which evaluates anything. It is a token. Compare

In[8]:= f[s_] := g[Unevaluated[1 + 1]]

In[9]:= DownValues[f]

Out[9]= {HoldPattern[f[s_]] :> g[Unevaluated[1 + 1]]}

And

In[10]:= f[s_] := Unevaluated[1 + 1]

In[11]:= DownValues[f]

Out[11]= {HoldPattern[f[s_]] :> 1 + 1}

Because evaluator is recursive, it suffices to get rid of Unevaluated eventually.

---

EDIT Expanding answer per Alexey's remark:

Unevaluated is an inert symbol, a token which is recognized by evaluator and acted upon within rules. For this reason Unevaluated[1+1] is unchanged, as well as f[1,Unevaluated[1+1]]. When RuleDelayed[s,Unevaluated[1+1]] is evaluated, Unevaluated is stripped, and then the entire RuleDelayed expression is reevaluated per evaluation principles.

---

EDIT 2 This is a condensed outcome of discussions on the cause for reevaluation

the implementation details of `RuleDelayed` cause repeated evaluations, which results in eventual stripping of the Unevaluated. In comments below my answer, I provided an example of another command which causes double evaluation for precisely the same reason. This happens because expression undergoes validation, and once validated, it is stamped with a certain valid flag. Setting the valid flag initiates reevaluation sequence. This is happening until expression no longer changes.

Similar effect occurs for other expression that require validation, like Root object:

In[41]:= Root[#1^6 + #1 - 1 & , 1]; Trace[Root[#1^6 + #1 - 1 & , 1], 
 TraceOriginal -> True]

Out[41]= {
 HoldForm[Root[#1^6 + #1 - 1 & , 1]], {HoldForm[Root]}, 
   {HoldForm[#1^6 + #1 - 1 & ], {HoldForm[Function]}, 
  HoldForm[#1^6 + #1 - 1 & ]}, 
   {HoldForm[1]}, 
  HoldForm[Root[#1^6 + #1 - 1 & , 1]],    <-- here the root had been 
                                              stamped valid, and reevaluated
   HoldForm[Root[-1 + #1 + #1^6 & , 1]]   <-- evaluation was trivial.

}

---

Reproducing the behavior of RuleDelayed with user-defined function "rd"

Here is straightforward way to reproduce RuleDelayed evaluation behavior based on Sasha's description:

<...> [Rule] expression undergoes validation, and once validated, it is stamped with a certain valid flag. Setting the valid flag initiates reevaluation sequence. This is happening until expression no longer changes.

ClearAll[rd];
SetAttributes[rd, {HoldRest, SequenceHold}];
Options[rd] = {"Validated" -> None};
expr : rd[args__] /; ("Validated" /. Options[Unevaluated[rd]]) =!= 
   Hold[expr] := (Options[
    Unevaluated[rd]] = {"Validated" -> Hold[expr]}; rd[args])

In[6]:= rd[Unevaluated@Unevaluated[1 + 1], 
 Unevaluated@Unevaluated[Unevaluated[1 + 1]]]

Out[6]= rd[2, 1 + 1]

We can compare the number of evaluations of the first argument for rd and RuleDelayed:

dummyFunction /; (++numberOfEvaluations; False) := Null;

In[36]:= numberOfEvaluations=0;
rd[dummyFunction,Unevaluated@Unevaluated[Unevaluated[1+1]]];
numberOfEvaluations
numberOfEvaluations=0;
RuleDelayed[dummyFunction,Unevaluated@Unevaluated[Unevaluated[1+1]]];
numberOfEvaluations
Out[38]= 4
Out[41]= 4

Tracing rd and RuleDelayed

The following demonstrates that this version replicates the behavior of RuleDelayed almost exactly. The only difference is the last additional evaluation of the final expression rd[2,1+1] which involves condition check and gives no match. With using rd as the second argument of Trace this last evaluation is excluded automatically. In the case of RuleDelayed this last check cannot be caught by Trace since it does not go through the evaluator.

The code:

ClearAll[rd];
SetAttributes[rd, {HoldRest, SequenceHold}];
SetAttributes[returnLast, {HoldRest}]
SetAttributes[{NotValidatedQ, setValidatedFlag}, HoldAllComplete];
Options[rd] = {"Validated" -> None};
NotValidatedQ[expr_] := ("Validated" /. Options[Unevaluated[rd]]) =!= 
   Hold[expr];
setValidatedFlag[expr_] := 
  Options[Unevaluated[rd]] = {"Validated" -> Hold[expr]};
returnLast[first_, last_] := last;
expr : rd[args__] /; NotValidatedQ[expr] := 
 returnLast[setValidatedFlag[expr], rd[args]]

Comparison:

rdList = DeleteCases[
   Trace[rd[Unevaluated@Unevaluated[1 + 1], 
     Unevaluated@Unevaluated[Unevaluated[1 + 1]]], 
    TraceOriginal -> 
     True], ({HoldForm[(validatedQ | setValidatedFlag)[_]], ___} | 
     HoldForm[_returnLast] | {HoldForm[returnLast]})] /. 
  rd -> RuleDelayed

RuleDelayedList = 
 Trace[RuleDelayed[Unevaluated@Unevaluated[1 + 1], 
   Unevaluated@Unevaluated[Unevaluated[1 + 1]]], 
  TraceOriginal -> True]

Tracing with using of the second argument of Trace shows exact match:

In[52]:= rdList = 
  Trace[rd[Unevaluated@Unevaluated[1 + 1], 
     Unevaluated@Unevaluated[Unevaluated[1 + 1]]], rd, 
    TraceOriginal -> True] /. {HoldForm[_returnLast] -> Sequence[], 
    rd -> RuleDelayed};
RuleDelayedList = 
  Trace[RuleDelayed[Unevaluated@Unevaluated[1 + 1], 
    Unevaluated@Unevaluated[Unevaluated[1 + 1]]], RuleDelayed, 
   TraceOriginal -> True];

rdList === RuleDelayedList

Out[54]= True