24
$\begingroup$

If I execute:

In[1] := x = x
Out[1] = x

and then I evaluate the symbol x:

In[2] := x
Out[2] = x

it simply returns x itself. I don't understand why this doesn't result in an infinite loop. Given that x references itself after the assignment x = x, I think that evaluating x should result in an infinite loop (x is replaced by x, which is replaced x, and so on). What am I missing?

Contrast this with what happens with the assignment:

f[x_] := f[x]

Evaluating f[x] after this assignment results in an infinite loop:

In[5]:= f[x]

During evaluation of In[5]:= $IterationLimit::itlim: Iteration limit of 4096 exceeded.

Out[5]= Hold[f[x]]

Edit: Using x := x instead of x = x does not cause an infinite loop. Using x = Identity[x] does not cause an infinite loop either. But using x := Identity[x] as suggested by Jacob Akkerboom in the comments results in an infinite loop. Why?

Improve this question
$\endgroup$
23
  • 1
    $\begingroup$ related to this answer: mathematica.stackexchange.com/a/39936/534 $\endgroup$
    – a06e
    Commented Jan 7, 2014 at 13:39
  • 1
    $\begingroup$ I guess Mathematica tries to be smart in some definitions with no patterns on the rhs and sometimes skips them after a couple of iterations in which the rhs didn't change upon evaluation. Let's see if someone digs in and shares a more exact mechanism as to when this happens and when it doesn't $\endgroup$
    – Rojo
    Commented Jan 7, 2014 at 14:23
  • 5
    $\begingroup$ The Standard Evaluation Procedure "continue[s] reevaluating results until it gets an expression which remains unchanged through the evaluation procedure." So x = x is applied only once (no change); x := Identity[x] leads to infinite recursion: Identity[Identity[…]] because the argument x is evaluated before Identity[x] and becomes Identity[x], in which x is evaluate before Identity[x], ad infinitum. (In other words, Jacob is basically right.) $\endgroup$
    – Michael E2
    Commented Jan 7, 2014 at 15:15
  • 4
    $\begingroup$ @Rojo As you know f[x_] := f[x] has nothing to do with Global`x, so let's use y in f[y]. I think difference is in how pattern replacements are handled. When f[y] is evaluated, M evaluates the head f first, finds the downvalue, applies it. Now, to apply it, M needs to evaluate the rhs, f of the pattern x. After it does the substitution, the result has not been evaluated yet. So even though the result is again f[y], f[y] has to be evaluated once more. Clearly you want this to happen for normal functions. Here you get infinite recursion. $\endgroup$
    – Michael E2
    Commented Jan 7, 2014 at 16:33
  • 2
    $\begingroup$ @JacobAkkerboom I think ReplaceRepeated examines the result of a replacement after evaluation is complete and continues until a fixed point is reached. After the first replacement, the expression is the same as the starting expression, so it stops. $\endgroup$
    – Michael E2
    Commented Jan 7, 2014 at 18:13

3 Answers 3

Reset to default
8
$\begingroup$

I am not sure there is a more factual answer to this kind of question than saying "it is what it is." Nevertheless it is more satisfying to have hypotheses for such things.

Daniel Lichtblau says in answer to my question: Mathematica execution-time bug: symbol names:

I can explain the optimization involved here in slightly more detail. First recall that Mathematica emulates "infinite evaluation", that is, expressions keep evaluating until they no longer change. This can be costly and hence requires careful short circuit optimizations to forestall it when possible.

A mechanism we use is a variant of hashing, that serves to indicate that symbols on which an expression might depend are unchanged and hence that expression is unchanged. It is here that collisions might occur, thus necessitating more work.

In a bad case, the Mathematica kernel might need to walk the entire expression in order to determine that it is unchanged. This walk can be as costly as reevaluation. An optimization, new to version 7 (noted above), is to record explicitly, for some types of expression, those symbols upon which it depends. Then the reevaluation check can be shortened by simply checking that none of these symbols has been changed since the last time the expression was evaluated.

The implementation details are a bit involved (and also a bit proprietary, though perhaps not so hard to guess). But that, in brief, is what is going on under the hood. Earlier versions sometimes did significant expression traversal just to discover that the expression needed no reevaluation. This can still happen, but it is a much more rare event now.

My hypothesis: one of these "short circuit optimizations" is to recognize certain definitions without side effects ... and halt the infinite evaluation. The specific optimizations are is not spelled out, and in fact are "also a bit proprietary." We are therefore left to observe behavior once again.

We can see that it is not a matter of the difference between Own Values and Down Values, and further that the mere existence of a pattern on the LHS does not prevent the halting:

f[___] := f[]
f[]                 (* no infinite recursion *)

I am still exploring this behavior in an attempt to form a more complete theory.

Improve this answer
$\endgroup$
8
  • $\begingroup$ How about this as a short circuit: InternalComparePatterns[Hold[f[]], Hold[f[___]]]. If result is Identity, Equivalence` or Specificity, and no other definition exists, assume that rhs does not need further evaluation. Internal`ComparePatterns $\endgroup$
    – István Zachar
    Commented Jan 8, 2014 at 9:45
  • $\begingroup$ @István Interesting hypothesis. Do you intend to test it? $\endgroup$
    – Mr.Wizard
    Commented Jan 8, 2014 at 9:47
  • $\begingroup$ Yes, I have some promising test results, but also have some issues with named patterns. For example, pattern-variable-replacement (local to the definition, as in Jacob's p:f1[x_] := p;) should happen before testing, otherwise result is Incomparable. $\endgroup$
    – István Zachar
    Commented Jan 8, 2014 at 10:21
  • $\begingroup$ I'm not sure if I can really agree that these effects are just optimizations; rather it seems to be fundamental behavior of the evaluation process. I couldn't observe any difference between version 5.2 and version 9 for any of @JacobAkkerboom's long list of examples, for instance. $\endgroup$
    – Oleksandr R.
    Commented Jan 9, 2014 at 20:56
  • $\begingroup$ @Oleksandr That's a good point. As you can see I have yet to update my answer because I don't have a better explanation. Nevertheless I presume the mechanisms are related in that infinite recursion must be prevented in either case. What is your hypothesis? $\endgroup$
    – Mr.Wizard
    Commented Jan 10, 2014 at 1:47
5
$\begingroup$

Extended comment

First of all, I think there is no easy answer to this question.

Let me collect my examples in an answer, in order to provide some structure in them as well as not to flood the comments. Throughout the answer, the lines of text describing the code refer to the code below it.

You will find that the examples which reach $IterationLimit are much harder to understand. If there is nothing mysterious about x:={x} creating infinitely much work for the kernel, then there is also nothing mysterious about x:=Identity[x] causing infinitely much work. 

Clear[f1, f2, f3, f4, f5, f6, f7, f8, f9, f10, f11, f12, x, x2, x3, x4, x5]

The following reaches $RecursionLimit

x2:=Identity@x2;x2

No infiniteness

x=x;x
y //. y :> y

Infinite iteration

x3:=Identity[Unevaluated[x3]]; x3

No infiniteness

y//.HoldPattern[y]:>Identity[Unevaluated[y]]
a[y] //. HoldPattern[y] :> Identity[Unevaluated[y]]

Infinite iterations

Hold[y] //. HoldPattern[y] :> Identity[Unevaluated[y]]
SetAttributes[b, HoldFirst]; SetAttributes[c,HoldRest]
b[y] //. HoldPattern[y] :> Identity[Unevaluated[y]]
b[y, 1] //. HoldPattern[y] :> Identity[Unevaluated[y]]
c[1, y] //. HoldPattern[y] :> Identity[Unevaluated[y]]

No infiniteness

b[1, y] //. HoldPattern[y] :> Identity[Unevaluated[y]]
c[y, 1] //. HoldPattern[y] :> Identity[Unevaluated[y]]

No infiniteness

p : f1[x_] := p; f1[1]
p : f2[x_] /; True := p; f2[1]
p : f3[x_] := p /; True; f3[1]

Infinite iterations

p : f4[x_] := Identity@Unevaluated@p; f4[1]

f5[g_] := g[g]; f5[f5]
f6[x_] := f6[x]; f6[1]
(p : f7)[x_] := p[x]; f7[1]

No infiniteness

f8[_] := f8[1]; f8[1]
f9[] := f9[]; f9[]
f10[___] := f10[]; f10[]

Infinite iteration

Combining the previous definitions, we do get an infinite iteration.

f11[] := f11[];
f11[___] := f11[];
f11[]

Set vs SetDelayed

II

f[x_] = f[x]

Shortcut in action

We can do

p : f12[_] /; (x5 = True) := p
f12[x5]

which outputs

f17[x5]

and does set x5. So we see that x5 that after the replacement the expression is not properly evaluated.

Related, but not understandable: Unexpected behaviour of Unevaluated

Improve this answer
$\endgroup$
6
  • $\begingroup$ @IstvánZachar well, not precisely that, but maybe something similar? I will try to give an example $\endgroup$
    – Jacob Akkerboom
    Commented Jan 7, 2014 at 16:36
  • $\begingroup$ @MichaelE2 this is not entirely true, I also thought this for a long time, but rm-rf pointed out a difference. { x1 := {1}; x1[[1]] = 2; x1, x2 = {1}; x2[[1]] = 2; x2} $\endgroup$
    – Jacob Akkerboom
    Commented Jan 7, 2014 at 18:22
  • $\begingroup$ @MichaelE2 I guess I meant x1 := Evaluate[{1}] $\endgroup$
    – Jacob Akkerboom
    Commented Jan 7, 2014 at 18:45
  • $\begingroup$ @IstvánZachar Jacob popped my balloon a little, but (1;y) is CompoundExpression[1, y]. It leads to y being evaluated again just like y:=f[y], because the new expression is not the same as y. But for x:=x, evaluating x results in x, which is the same as x and doesn't lead to further evaluation. $\endgroup$
    – Michael E2
    Commented Jan 7, 2014 at 18:58
  • $\begingroup$ @MichaelE2 indeed. Perfectionism is a dangerous enemy :P $\endgroup$
    – Jacob Akkerboom
    Commented Jan 7, 2014 at 19:00
0
$\begingroup$

When you define a function you are defining a rule. This is covered in Ch. 4.1 of Paul Wellin's book Programming with Mathematica. For example, when you define 

f[x_] := x^3

what this says is whenever f is given an argument, it should be replaced with that argument cubed. Here f[x_] is a pattern a that basically matches anything. Whatever goes in gets cubed.

So when f[x_] := f[x] is defined a rule is created that says: take anything and call f[anything] which says take anything and call f[anything] which says take anything and call f[anything] ... and so on. Maybe "call" is more appropriately "replace with" but the point should be clear.

On the other hand, x = x is just an assignment. This is covered in Ch. 2.2

Improve this answer
$\endgroup$
14
  • 3
    $\begingroup$ This does not explain why x:=x;x does not cause infinite recursion while y:=(1;y);y does. $\endgroup$
    – István Zachar
    Commented Jan 7, 2014 at 16:04
  • 1
    $\begingroup$ @Jacob But is it important that the definition is tail-recursive or center-embedded? I mean: it must be the same lhs=?=rhs test used for both cases by Mathematica that allows for the simple non-recursive/non-iterative outcome. Nevertheless, this post does not answer the original question. $\endgroup$
    – István Zachar
    Commented Jan 7, 2014 at 16:12
  • 1
    $\begingroup$ @JacobAkkerboom I agree. I think that x:={x} and x:=Identity[x] are explained by @MichaelE2's comment above (referencing reference.wolfram.com/mathematica/tutorial/…). Your point is that @MichaelE2's explanation works for all the examples that reach $RecursionLimit? If yes, you should add that to your answer (Extended comment)... It could be helpful to reach a complete answer. $\endgroup$
    – a06e
    Commented Jan 7, 2014 at 16:32
  • 8
    $\begingroup$ I find this explanation misleading. Both Set and SetDelayed create rules, so "just an assignment" is not really explaining anything, and moreover, is misleading, since it hints on a difference between Set and SetDelayed which is not really there. There are indeed differences in how Set and SetDelayed work, ranging from well-known ones (evaluation) to more subtle ones (e.g. availability of Part assignment, or memory used by the created rule, etc), but they are not what you claim they are, since rules are created in both cases. $\endgroup$
    – Leonid Shifrin
    Commented Jan 7, 2014 at 18:48
  • 3
    $\begingroup$ @brown.2179 "This behavior is not some special deep insight" - well, you never know. Such contradictions sometimes lead to new insights and / or techniques. For example, someone not familiar with Trott-Strzebonski in-place evaluation technique would probably think of such behavior as a contradiction, while it is a highly useful technique. Experienced users get used to trust their instincts rather than just follow the docs, so we need to understand the strange stuff - thus all this discussion. $\endgroup$
    – Leonid Shifrin
    Commented Jan 8, 2014 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.