Order dependence [in symbolic systems]
The operation expr /. lhsrhs in Mathematica has the effect of scanning the functional representation of expr from left to right, and applying rules whenever possible while avoiding overlaps. (Standard evaluation in Mathematica is equivalent to expr //. rules and uses the same ordering, while Map uses a different order.) One can have a rule be applied only once using
Module[{i = 1}, expr /. lhs rhs /; i++ 1]
Many symbolic systems (including the one on page 103) have the so-called Church–Rosser property (see page 1036) which implies that if a fixed point is reached in the evolution of the system, this fixed point will be the same regardless of the order in which rules are applied.