Unexpected behavior of Unevaluated

Question

This question of mine got a bit ruined by the fact that I got a bit confused. I hope this separate question will take away this confusion. My confusion was that I found it strange that we have, for

x = 3;
g[_Symbol] := "yay"

that as expected

g[Unevaluated[x]]

"yay"

but

g[_Symbol] := "yay"
g[Sequence[Unevaluated[x]]]

g[Unevaluated[x]]

and even

With[
    {yyyy = g[Sequence[Unevaluated[x]]]}
  , Identity[yyyy]
]

g[Unevaluated[x]]

The strange thing here is that even though g[Unevaluated[x]] is not in its "final form" (at a fixed point), in the sense that a rule can be applied to this as we can see above, Mathematica stops evaluating. I show the third example in which With occurs, because one might have thought that the behavior occurs because Mathematica assumes that rules for g have already been applied or something. But even when we use With (or in fact, Identity, With is really not necessary) to start a "clean evaluation", Mathematica refuses to do the last step.

For a little while, I had the following question/hypothesis about this: "Does Mathematica remember if an expression has been fully evaluated?". Using that I found another similar example. We have

Clear[h, somethingElse, something]
h[something, something = somethingElse]

h[something, somethingElse]

even though, if we evaluate the resulting expression again, we have

h[something, somethingElse]

h[somethingElse,somethingElse]

But this time, we have

Clear[h, somethingElse, something]
Identity[h[something, something = somethingElse]]

h[somethingElse, somethingElse]

So that Mathematica does continue evaluation in this case. The same happens for a user-defined Identity. Note that the following does not result in a "fixed point" (expression that is left unchanged by the rules).

Clear[h, somethingElse, something]
List[h[something, something = somethingElse]]

{h[something, somethingElse]}

Which probably makes sense. I guess Identity is defined in terms of a rule, and after a rule we have to evaluate again. However, if we put something in a list, we can assume that the thing inside the list was evaluated correctly so we don't have to evaluate again.

Little tentative conclusion: It is not true that Mathematica repeatedly evaluates an expression until it does not change anymore. It seems to be a little more subtle than that.

The question is: Is it a bug that

g[_Symbol] := "yay"
Identity[g[Sequence[Unevaluated[x]]]]

Evaluates to

 g[Unevaluated[x]]

?

Answer 1

Jacob, allow me to suggest a presentation that I think you will find relevant and informative:

Working with Unevaluated Expressions - Robby Villegas

Some excerpts:

Unevaluated is a wrapper on arguments that is simply a signal to the evaluator to avoid evaluating the argument. ... It is transparent to the function receiving the argument. You can think of it as a shuttle giving the argument safe transport to the function's code, keeping the evaluator away. Unevaluated vanishes before the argument is fed to the function, since its purpose is fulfilled.

Crucially:

Unevaluated must be wrapper before argument evaluation, not after, else it isn't stripped.

Recall our discussion of the over-arching evaluator, and the fact that your inputs and commands have two stages: their original form, and the reduced form with arguments all evaluated.

Unevaluated is not meant to be a function or stable data type. It is to be used as a wrapper on an argument in stage 1, before argument evaluation. It is a signal to the evaluator to suppress the usual evaluation of that argument. ...

Those of you who have experimented with Unevaluated have found that in some situations it doesn't vanish. This makes it seem confusing and inconsistent, like Sequence. ...

The subtle and confusing situation where Unevaluated persists is when an argument did not originally have a head of Unevaluated, but became Unevaluated[whatever] after argument evaluation finished.

Answer 2

No, this is not a bug. The hypothesis that Mathematica remembers if an expression has been evaluated turns out to be true. To see this, compare

Trace[{1, 2, oki}, TraceOriginal -> True] 

{{1,2,oki},{List},{1},{2},{oki},{1,2,oki}} 

and

With[ 
    {expr = {1, 2, oki}}
  , (*ClearSystemCache[];*)
    Trace[expr, TraceOriginal -> True] 
]

{1, 2, oki}

Note that this is not the result of caching in the sense of ClearSystemCache.

Mathematica seems to remember which symbols occur in expressions. It also remembers the last time an expression changed. Normally if a change is made to a symbol occurring in the expression, Mathematica will reevaluate this expression. This is why

Clear[h, somethingElse, something]

Identity[h[something, something = somethingElse]]

evaluates to h[somethingElse, somethingElse]. I do not know exactly what Mathematica stores and when. This is definitely something I'd like to learn more about.

One could now think that if we update x, using Update or assignment, we might cause such an update and the expression g[Unevaluated[x]] will still evaluate. It could be expected that

With[
    {expr = g[Sequence@Unevaluated@x]}
  , x = 4
  ; Identity[expr]
]

evaluates to "yay" (but it doesn't!). This is in fact also what I tried when I was answering this question, only I failed to mention it as I thought that was irrelevant.

However, the attribute HoldAllComplete of Unevaluated in the expression g[Sequence @ Unevaluated @ x] shields x from such the tracking of symbols. Mathematica does not store that x is present in Unevaluated[x]. It has no way to infer that x is present in g[Unevaluated[x]]. Therefore the expression above simply evaluates to g[Unevaluated[x]]. To see that it is really the attribute HoldAllComplete causing this, we can do

(*warning! Changes funtamental system definitions!*)

ClearAttributes[Unevaluated, HoldAllComplete]

SetAttributes[Unevaluated, HoldAll]

With[
    {expr = g[Sequence@Unevaluated@x]}
  , x = 4
  ; expr
]

"yay"

Also consider, with a fresh kernel

gggg[y_Symbol, x_Symbol] := "yay";
Clear[x, y]

With[
    {expr = gggg[Sequence[y, Unevaluated[x]]]}
  , Update[y]
  ; expr
]

With[
    {expr = gggg[Sequence[y, Unevaluated[x]]]}
  , Update[x]
  ; expr
]

"yay"

gggg[y, Unevaluated[x]]

Where we see that x is not tracked but y is.

For more information (that I really should have included in this answer), see this chat transcript

Answer 3

Following the discussion in Wagner's book pages 192-3 with regards to Evaluation, I think one can figure out why this happens. The references to steps below refer to the steps in Wagner's book.

You start from g[Sequence[Unevaluated[x]] which is of the form head0[part1]. And where part1 is of the form head1[part2].

So in the first evaluation sequence: we start to evaluate head0[part1]. Now, head0 is g, and it has no own-values, so we then move to evaluate part1 which is Sequence[Unevaluated[x]]. This starts another evaluation sequence.

For this second evaluation sequence, note that the head is Sequence. Then, the head Unevaluated is removed from part2. So by the end of step 7 of this second evaluation sequence, we have the expression Sequence[x]. There are no rules that apply here, so the evaluator restores the head Unevaluated (Step 16). So part1 has now evaluated to Sequence[Unevaluated[x]]. Then, we go back to continue the first evaluation sequence.

Now we have finished step 7 of the first evaluation sequence and ended up with the following expression: g[Sequence[Unevaluated[x]]. Next, Sequence is spliced (Step 9), and we now have the expression g[Unevaluated[x]]. There are no other rules attached to this, and hence we are done.

EDIT: Actually, the link in Mr.Wizard's answer makes the point quite clear:

The subtle and confusing situation where Unevaluated persists is when an argument did not originally have a head of Unevaluated, but became Unevaluated[whatever] after argument evaluation finished.

which is what happens in this case. Another way to see it:

ClearAll[h, g]
h = Function[z, Unevaluated[z], HoldAll];
g[_Symbol] := "yay";
x = 2;
g[h[x]]

returns

(* =>  g[Unevaluated[x]] *)

which is consistent with the description of the evaluation procedure above.