21
$\begingroup$

How exactly does Mathematica determine that evaluation of particular expression should be finished and the result should be returned?

Here are some examples of unclear behavior which have arisen, when I tried to understand deeper Todd Gayley's Block trick:

x := Block[{tried = True}, x + 1] /; ! TrueQ[tried]    
x + y    
(* 1 + x + y *)

x + 1

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

(* Hold[4096 + x] *)

Why did the evaluation stop at 1 + x + y in the first case and the second go into an infinite loop?

The other interesting side of the trick is that when we evaluate just x, the infinite loop does not begin. The reason is that evaluation in this case does not go outside of the Block scope:

Clear[x];
x := Block[{tried = True}, x + 1] /; ! TrueQ[tried]
x /; ! TrueQ[tried] := x + 1
x
x /; TrueQ[tried] := x + 1
x

(* 1 + x *)

During evaluation of In[1]:= $RecursionLimit::reclim: Recursion depth of 256 exceeded. >>

(* 254 + Hold[RuleCondition[$ConditionHold[$ConditionHold[
     Block[{tried = True}, x + 1]]], ! TrueQ[tried]]] *)

But if we try to use Set instead of SetDelayed we get a couple of infinite loops:

x = Block[{tried = True}, x + 1] /; ! TrueQ[tried];

What happens in this case?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ See also: Evaluation $\endgroup$
    – Michael Pilat
    Mar 17, 2011 at 14:02
  • $\begingroup$ @Michael One sentence on that page I do not understand: "Use any applicable transformation rules that you have defined for h[f[e1,e2,...],...] or for h[...][...]." The symbol f comes from nowhere on that page. What does it mean? How such rules could be defined? $\endgroup$
    – Alexey Popkov
    Mar 19, 2011 at 5:05
  • $\begingroup$ No one seems to have mentioned 'FixedPoint', and I of course don't know whether the 'FixedPoint' function that is provided to the user is the same 'FixedPoint' that is used internally, but I believe the concept, at least, is the same. Mathematica applies FixedPoint to every expression in a depthfirst fashion until it returns. $\endgroup$
    – berniethejet
    Jun 2, 2022 at 18:30

2 Answers 2

Reset to default
30
$\begingroup$

Evaluation stops when there is no definition in place whose pattern matches the expression being evaluated.

Conversely, evaluation will continue as long as there is a matching definition. Thus, if I have this definition:

zot[x_] := zot[x]

and I evaluate zot[1], the evaluation will never terminate even though the expression never changes. (Well, in principle it will never terminate but Mathematica will give up after $IterationLimit evaluations.)

Conditions (/;) count when making the determination about whether a pattern matches. So the following definition of zot is overwhelmingly likely to cause the evaluation of zot[1] to terminate:

zot[x_] := zot[x] /; RandomInteger[100] < 10

The Case At Hand

To see what is happening with the case at hand, it is instructive to look at the trace. Unfortunately, the output of Trace can be hard to read. The following function can help when used in conjunction with TraceOriginal -> True:

show[{expr_, steps___}] := OpenerView[{expr, Column[show /@ {steps}]}]
show[x_] := x

Now, consider the modified output of Trace when evaluating x + y:

Trace[Block[{$IterationLimit=20}, x+y], TraceOriginal->True] // show

terminating trace

In this trace, we can see the evaluation of x. It is apparent that the Block in the definition of x is entered and exited.

Note particularly the last three steps of the overall evaluation. First we see the action of the Flat attribute on Plus, converting (1 + x) + y to 1 + x + y. Next, we see the (non-)action of the Orderless attribute which, in this case, does nothing. At this point, the evaluator is looking for a rule that matches the pattern Plus[_Integer, _Symbol, _Symbol]. There isn't one, so the evaluation stops. x has already been evaluated, so it won't be evaluated again since there is no further rule to apply.

Now contrast this with the nonterminating case of evaluating x + y + 1.

Trace[Block[{$IterationLimit=20}, x+y+1], TraceOriginal->True] // show

non-terminating trace

The steps that correspond to the last steps in the first trace are indicated. Once again we see the action of Flat, transforming (1 + x) + y + 1 into 1 + x + y + 1. Then we see the action of Orderless, except this time it actually does something by changing 1 + x + y + 1 into 1 + 1 + x + y. Now the crux of the matter: this time around the evaluator is looking for a rule that matches Plus[_Integer, _Integer, _Symbol, _Symbol] -- and it finds one! 1 + 1 + x + y is transformed to 2 + x + y, which is re-evaluated. We are now stuck in the endless loop, with the trace for subsequent evaluation cycles following the same pattern.

Alas, the details of the rules and evaluation policy within Plus are built-in to Mathematica and not accessible to us outsiders. This precise sequence could in theory change in a future release. On the other hand, it would be hard to change the behaviour of Plus, putting thousands (millions?) of man-years worth of existing code at risk.

No Black Magic Necessary

Notwithstanding the built-in nature of Plus, the exhibited behaviour can be reproduced purely within the bounds of standard evaluation. Consider the following definitions of myPlus and myX:

ClearAll@myX
myX := Block[{tried = True}, myPlus[myX, 1]] /; !TrueQ[tried]

ClearAll@myPlus
myPlus[a_Integer, b_Integer, rest___] := myPlus[a + b, rest]
SetAttributes[myPlus, {Flat, Orderless}]

Evaluations of the analogs to x + y and x + y + 1 exhibit exactly the same terminating and non-terminating behaviour:

myPlus[myX, y]
(* myPlus[1, myX, y] *)

myPlus[myX, y, 1]

$IterationLimit::itlim: Iteration limit of 4096 exceeded. >>

(* Hold[myPlus[1 + 4096, myX, y]] *)

Note the absence of held expressions, C code and other black magic -- this is pure standard evaluation.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The idea to use OpenerView is very good! The common rule that I could draw from your explanation is that in the first case only attributes of Plus work and it is taken in Mathematica to consider their work as not changing the expression. But in the second case some built-in rewriting rule for Plus works and because of this Mathematica thinks that the expression is changed and it should be evaluated again. Is it right? Are you sure that Plus has hidden rules that work in the same way as ordinary rewriting rules that user could define by himself? $\endgroup$
    – Alexey Popkov
    Mar 19, 2011 at 7:45
  • 1
    $\begingroup$ The application of attributes will not trigger an evaluation in itself. The internal workings of Plus are hidden. It might be implemented in C++. Bear in mind that any definition can take explicit control over the evalulation process (so-called "non-standard evaluation"). The rules and patterns to which I refer to in my description are notional, reconstructed from the trace: they could be implemented in MMA using standard facilities like Hold and Evaluate, using definitions on Plus, helper functions, or even up-values on Integer or Symbol. I hope that analysis is useful. $\endgroup$
    – WReach
    Mar 19, 2011 at 11:47
  • $\begingroup$ The analysis is very enlightening, thank you. I just tried to formulate the exact reason why in the first case infinite evaluation takes no place. So the reason is that application of attributes don't trigger an evaluation in itself. But application of any definition works as trigger. Am I right? $\endgroup$
    – Alexey Popkov
    Mar 19, 2011 at 13:31
  • 1
    $\begingroup$ @Alexey Yes, if the evaluator finds a definition, it applies the transformation and then re-evaluates the result. The exact sequence of events are hard to determine in this case because the definitions related to Plus are inaccessible. However, the trace can be explained completely in terms of standard evaluation. See the newly added section 'No Black Magic Necessary' in my response. $\endgroup$
    – WReach
    Mar 19, 2011 at 15:37
  • $\begingroup$ +1 for OpenerView - a very nice trick. Also, a very clear discussion. $\endgroup$
    – Leonid Shifrin
    Mar 20, 2011 at 19:55
7
$\begingroup$

The input x + 1 results in infinite iteration because the result of the first call is (1+x)+1 which evaluates to 2+x and then the process starts over etc. This does not happen with symbolic y because no further evaluation happens after the first step. You can see for yourself by using Block[{$IterationLimit = 20}, x + 1] // Trace. For your code

Clear[x];
x := Block[{tried = True}, x + 1] /; ! TrueQ[tried]
x /; ! TrueQ[tried] := x + 1

You effectively create 2 OwnValues for x:

In[54]:= OwnValues[x]

Out[54]= {HoldPattern[x] :>  Block[{tried = True}, x + 1] /; ! TrueQ[tried], 
  HoldPattern[x /; ! TrueQ[tried]] :> x + 1}

But only the first (old) one will be effective since tried is first False and then True inside Block. Regarding the question whether or not the Block scope is left, the answer seems to be yes:

Clear[x];
x := Module[{result},
  result = Block[{tried = True}, x + 1]] /; ! TrueQ[tried]

In[63]:= x

Out[63]= 1 + x

This behavior has to do with the semantics of shared local variables. If the condition is violated, the evaluator goes on to the next rule (if there is one), or stops, deciding that the evaluation has completed. It does not attempt to re-evaluate the expression in this case. When you add the rule x /; TrueQ[tried] := x + 1, the infinite loop starts inside the Block, since now the second OwnValue becomes effective (tried becomes True). Finally, when you use Set instead of SetDelayed, this is entirely equivalent to defining 

x = 1 + x /; ! TrueQ[tried]

where, since the Block is now gone, ! TrueQ[tried] will always be True, thus an infinite loop.

From all this, the really non-trivial part for me seems the interplay of the Block and the semantics of shared local variables, and the effect it has on evaluation.

Improve this answer
$\endgroup$
11
  • $\begingroup$ I don not understand why with symbolic y "no further evaluation happens after the first step". On[Plus]; x + y shows that there is (1+x)+y --> 1+x+y transformation. Isn't it an evaluation step? $\endgroup$
    – Alexey Popkov
    Mar 17, 2011 at 10:20
  • $\begingroup$ @Alexey What you see when you turn on Plus tracking, is the final stage of evaluation ("on the way up"). The line (1+x)+y --> 1+x+y is just the evaluation of Plus (it is Flat), after which the resulting 1+x+y can not be further simplified, so the process stops. With (1+x)+1 it is apparenty different, because a new expression 2+x is produced. This may have to do with optimizations that Mathematica employs to not re-evaluate expressions that it thinks have not changed since the last evaluation. But, admittedly, I don't have a definitive answer here. $\endgroup$
    – Leonid Shifrin
    Mar 17, 2011 at 10:34
  • $\begingroup$ @Leonid Do you mean that two last transformations both correspond to the one (last) step of evaluation? If so is there a way to check at which transformation a particular step of evaluation starts and at which it ends? $\endgroup$
    – Alexey Popkov
    Mar 17, 2011 at 11:26
  • $\begingroup$ @Alexey I mean that in the standard evaluation, first arguments are evaluated (in this case, x is evaluated non-trivially), and then the head (Plus in this case) is evaluated, with the corresponding Attributes actions (Flat here) and associated with the head global rules. You can use Clear[x];(1 + x) + y // Trace // FullForm to see that what happens is due to Flat. The same last two steps happen when x is defined non-trivially as above. In either case, the value of x has been computed already,and Mathematica considers it unnecessary to re-evaluate it - perhaps due to optimization $\endgroup$
    – Leonid Shifrin
    Mar 17, 2011 at 13:35
  • 1
    $\begingroup$ @Alexey Continuing with the analysis: now when you enter Clear[x]; (1 + x) + 1 // Trace // FullForm, you see that after the Flat attribute applies, and we get HoldForm[Plus[1, 1, x]], this expression is found amenable to further evaluation, Then, the new evaluation round starts, and since it is a new evaluation, x is re-evaluated again, which ultimately leads to an infinite loop. Regarding the evaluation steps, I think Trace can give a pretty clear picture of what is happening. When unsure, you can construct minimal examples, taking out all but what you want to inspect. $\endgroup$
    – Leonid Shifrin
    Mar 17, 2011 at 13:42

Your Answer

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

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