how does mathematica determine which rule to use first in substitution

Question

I am wondering if given multiple substitution rules, how does mma determine which to apply first in case of collision. An example is:

x^3 + x^2*s + x^3*s^2 + s x /. {x -> 0, x^_?OddQ -> 2}

Thanks.

Answer 1

Mathematica has a mechanism which is able to determine the relative generality of the rules in simple cases, for example it understands that ___ (BlankNullSequence) is more general than __ (BlankSequence). So, when it can, it reorders global definitions according to it. It is important to realize though that such analysis is necessarily mostly syntactic. Therefore, while PatternTest (?) and Condition (/;) with some simple built-in predicates like EvenQ can sometimes be analyzed, using them with user-defined predicates will necessarily make such reordering impossible with respect to similarly defined rules, so that Mathematica will keep such rules in the order they were entered. This is because, PatternTest and Condition force the pattern-matcher to call evaluator to determine the fact of the match, and this makes it impossible to answer the question of relative generality of rules at definition - time. Even for purely syntactic rules it is not always possible to determine their relative generality. So, when this can not be done, or Mathematica can not do it, it keeps the rules in the order they were entered.

This all was about global rules, created by Set or SetDelayed or other assignment operators. For local rules, like in your example, there is no reordering whatsoever, they are applied in the order they have in the list of rules. All the rules in the list of rules beyond the first one that applied to a given (sub)expression, are ignored for that subexpression and that particular rule-application process - the (sub)expression gets rewritten according to the first matching rule, and then the rule-application process continues with other sub-expressions. Even if the new form of the rewritten (sub) expression matches some rules further down the rule list, they are not applied in this rule-application process. In other words, for a single rule-application process, for any particular (sub) expression, either no rule or just one rule is applied. But here also there are a few subtleties. For example, ReplaceAll (/.) applies rules from larger expressions to sub-expressions, while Replace with explicit level specification does it in the opposite way. This may matter in cases like this:

In[1]:= h[f[x, y]] /. {h[x_f] :> a, f[args__] :> b}

Out[0]= a

In[2]:= Replace[h[f[x, y]], {h[x_f] :> a, f[args__] :> b}, {0, Infinity}]

Out[2]= h[b]

I mentioned rule reordering in a few places in my book:here, here, and here. In rare cases when Mathematica does reorder rules in a way that is not satisfactory, you can change the order manually by direct manipulations with DownValues (or other ...Values), for example like DownValues[f] = Reverse[DownValues[f]]. Such cases do occur sometimes, but rather rarely, and if they happen, make sure there is a good reason to keep the existing design and go for manual rule reordering.