# Is it possible to specify a context-sensitive, “depth-agnostic” rewrite rule?

I'm using the term "depth-agnostic" in this post to describe structural patterns featuring a "target" sub-pattern that can occur "at any depth" relative to one or more "context" sub-patterns.

As a simple example of a "depth-agnostic" pattern, consider the following rewrite rule:

RR1

replace with the expression WRAP[X] any expression X_TGT contained somewhere within some expression _CTX.1

Here the target and context sub-patterns are X_TGT and _CTX, respectively. The depth-agnostic bit comes in as the phrase "somewhere within".

In other words, RR1 says to find expressions that look like

… CTX[ … y0[ … y1[ … … yk[ … TGT[ … ] … ] … … ] … ] … ] …


...(where the number of nested subexpressions y0, y1, ..., yk is indeterminate), and rewrite them as

… CTX[ … y0[ … y1[ … … yk[ … WRAP[TGT[ … ]] … ] … … ] … ] … ] …


Thus, if we defined

ping = foo[{1, CTX[bar[2,  3, {TGT[0], 4} ]]}];
ding = foo[{1, CTX[bar[2, {3, {TGT[0], 4}}]]}];
pong = foo[{1, baz[bar[2,  3, {TGT[0], 4} ]]}];


then, according to RR1, ping would be changed to

foo[{1, CTX[bar[2,  3, {WRAP[TGT[0]], 4} ]]}]


...and ding would be changed to

foo[{1, CTX[bar[2, {3, {WRAP[TGT[0]], 4}}]]}]


On the other hand, pong would be unaffected by RR1, even though it contains an expression _TGT, because this expression does not occur "somewhere within an expression _CTX".

The problem is

how to implement a rewrite rule that features such a "depth-agnostic" pattern in Mathematica?

To see why "depth-agnosticity" is an issue, consider rewrite rule RR2 below, identical in every way to RR1, except that it specifies a single, unambiguous depth for the target relative to the context sub-pattern (IOW, it is not "depth-agnostic"):

RR2

replace with the expression WRAP[X] any expression X_TGT contained at a depth of 3 within some expression _CTX.

As shown below, implementing RR2 in Mathematica is straightforward (though, admittedly, a bit tedious), but unfortunately, it is nowhere as general as RR1 (e.g. RR2 affects only ping, not ding).

Here's one (rather uninspired) implementation of RR2 in action:

{ping, ding, pong} /.
CTX[a1___, h1_[a2___, h2_[a3___, X_TGT, z3___], z2___], z1___] ->
CTX[a1, h1[a2, h2[a3, WRAP[X], z3], z2], z1] // TableForm

foo[{1, CTX[bar[2, 3, {WRAP[TGT[0]], 4}]]}]
foo[{1, CTX[bar[2, {3, {TGT[0], 4}}]]}]
foo[{1, baz[bar[2, 3, {TGT[0], 4}]]}]


This implementation fulfills the earlier assertions about RR2: it like RR1 with respect to ping (affects it) and pong (does not affect it), but not with respect to ding (RR1 affects ding but RR2 doesn't).

There are at least two important generalizations of the ideas described above. The first one is the situation in which there are multiple context sub-patterns that are themselves at indeterminate depths relative to each other. For example:

RR3

replace with the expression WRAP[X] any expression X_TGT and being contained somewhere within some expression _CTX that is itself contained somewhere within some expression _List.

The second generalization could be expressed as allowing "negative depths", or in other words, patterns in which the context sub-pattern is contained within the target subpattern. For example:

RR4

replace with the expression WRAP[X] any expression X_TGT containing somewhere within it some expression _CTX.

1In this post I will resort to Mathematica's notation for patterns. Namely, _H denotes a pattern matching any expression having head H, and X_H denotes a pattern matching any expression (henceforth referred to as X) having head H. I will abuse this notation slightly, writing "an expression _H" as shorthand for "an expression matching the pattern _H", and "an expression X_H" as shorthand for "an expression (henceforth referred to as X) matching the pattern _H.)

-
I think you want something similar to what was discussed here. – Leonid Shifrin Sep 30 '12 at 19:30

ReplaceAll or /., which is what you used, replaces at all levels (or depths). If you need to target a particular level/depth, then use Replace. To target expressions that contain/don't contain a particular term, use FreeQ Here's how you can write your replacement rules for each of the cases (replace expr with whatever you have):

RR1: replace with the expression WRAP[X] any expression X_TGT contained somewhere within some expression _CTX

expr /. x_CTX :>  (x /. TGT :> Composition[WRAP, TGT])


or

expr /. x_CTX :> (x /. y_TGT :> WRAP[y])


RR2: replace with the expression WRAP[X] any expression X_TGT contained at a depth of 3 within some expression _CTX.

expr /. x_CTX :> Replace[x, y_TGT :> WRAP[y], {3}]


and similarly using Composition.

RR3: replace with the expression WRAP[X] any expression X_TGT and being contained somewhere within some expression _CTX that is itself contained somewhere within some expression _List.

expr /. l_List :> (l /. x_CTX :> (x /. y_TGT :> WRAP[y]))


RR4: replace with the expression WRAP[X] any expression X_TGT containing somewhere within it some expression _CTX.

expr /. y_TGT :> WRAP[y] /; ! FreeQ[y, CTX]

-
++Thanks! This goes a long way. Minor follow-up comment/question: for RR1-RR3, it looks to me like, for the innermost replacement, Rule may be used instead of RuleDelayed... I haven't yet come up with a case that would distinguish a clear preference for one (of Rule vs RuleDelayed) over the other. – kjo Sep 30 '12 at 20:01
@kjo I would not use Rule except in rather special circumstances, since Rule does not properly scope pattern variables. – Leonid Shifrin Sep 30 '12 at 20:12
@LeonidShifrin: Thanks! – kjo Sep 30 '12 at 21:49