# StringReplace, ReplaceAll and Rule interact in a bizarre way

I have the following pair of things:

ClearAll[foo, labeledFoo];

labeledFoo = {"FooBarBazQuux", foo};


This works like you'd expect:

labeledFoo /. hdr_String :>
StringReplace[hdr, l_?LowerCaseQ ~~ U_?UpperCaseQ :> l <> " " <> U]

(* {"Foo Bar Baz Quux", foo} *)


So does this:

labeledFoo /. hdr_String :>
StringReplace[hdr, l_?LowerCaseQ ~~ U_?UpperCaseQ :> l <> " " <> U] /.
{hdr_String, x_} :> (hdr -> x)

(* "Foo Bar Baz Quux" -> foo *)


Heck, even this works:

labeledFoo /. {hdr_String, x_} :> (Rule @@ {StringReplace[hdr,
l_?LowerCaseQ ~~ U_?UpperCaseQ :> l <> " " <> U], x})

(* "Foo Bar Baz Quux" -> foo *)


This, though, doesn't work at all:

labeledFoo /. {hdr_String, x_} :> (StringReplace[hdr,
l_?LowerCaseQ ~~ U_?UpperCaseQ :> l <> " " <> U] -> x)

(* "Fo" ~~ l <> " " <> U ~~ "a" ~~ l <> " " <> U ~~ "a" ~~
l <> " " <> U ~~ "uux" -> foo *)


I really have no idea what's going on. This is so weird that I feel like I must be missing a simple syntax error, but all the other things that do work make me doubt that.

-
In fact, this behavior was discussed before, in this thread. It only took me 4.5 years to find a decent explanation (I completely forgot about that thread when answering, found this rather accidentally just now). –  Leonid Shifrin May 26 '14 at 21:48

### Preamble

What happens can be understood when we recall that Rule is a scoping construct. The general issues related to variable renamings in scoping constructs have been considered in more details in this answer.

### General

Now, to this particular case. When the code runs, the external RuleDelayed considers the situation "dangerous" and performs variable renamings for your l and U variables.You end up with the code like this:

StringReplace["FooBarBazQuux",l$_?LowerCaseQ~~U$_?UpperCaseQ:>l<>" "<>U]


which can be seen using Trace. This means that the l and U on the r.h.s. are no longer coupled to the patterns on the l.h.s., thus the result.

In the first 3 cases, this doesn't happen, because the outer RuleDelayed can not "sense" the inner scoping construct (Rule in this case) - which is true even in the case Rule @@ {...}. Therefore, it does not perform the renamings. The reason why it does not care about the inner RuleDelayed is that they are completely decoupled, since no pattern variable from the outer RuleDelayed is used in the inner RuleDelayed.

This is not the case in the last example, where the more external Rule becomes coupled to the outermost RuleDelayed via the x variable. And, presumably because the system is acting rather silly in this case and considers the pattern variables l and U to belong to the Rule rather than the inner RuleDelayed (see also below for a bit more on that), we get a problem.

### Simpler example, and a possible explanation

Exactly the same situation happens in this, somewhat simpler example:

{{1, 2}, 3} /. {x_List, y_Integer} :>
Rule[
Replace[x, {l_Integer, u_Integer} :> l + u],
y
]

(* l + u -> 3 *)


But what I think is really happening, is that in doing these renamings, the system acts rather silly. It interprets l_ and u_ not as parts of inner RuleDelayed, but as parts of the outer Rule. This is why it breaks the scoping / binding of inner RuleDelayed - because it is not clever enough to see that those pattern variables are localized by that inner RuleDelayed - it rather thinks that they belong to a more external Rule. And it only renames the variables inside patterns, because if you have

{x_, x+1} -> x^2


then x in x+1 will of course be taken from enclosing environment, and thus there is no need to localize / rename it.

### Removing the lexical coupling

The final thing here: let us prove that the problem we have is due to a lexical coupling, in that external Rule is coupling the inner patterns with outer RuleDelayed via the y variable (in my example, and x in yours):

{{1, 2}, 3} /. {x_List, y_Integer} :>
Block[{yy = y},
Rule[
Replace[x, {l_Integer, u_Integer} :> l + u],
yy]
]

(* 3 -> 3 *)


Now, all is fine and dandy, since Block is not a lexical scoping construct, and we decouple the outer and inner RuleDelayed, even though Rule is present. Try using y in Rule[Replace[...], y] instead, and remove the Block - and we are back to the same code as before. If you use With or Module in place of Block, the problem is still there - since they are both lexical scoping constructs, they will do the renamings in the same way as RuleDelayed.

-
Requisite link to our co-authored answer: (20776) –  Mr.Wizard Apr 22 '14 at 21:55
@Mr.Wizard Thanks! Indeed, very relevant. –  Leonid Shifrin Apr 22 '14 at 21:56
Accepted. I've been burned by the perfidy of RuleDelayed rewriting stuff before, but it never occurred to me it would do the same thing to the LHS of a plain old Rule. –  Pillsy Apr 23 '14 at 13:59
@Pillsy [1/2] Thanks for the accept! Yep, I did not see this one before either. But it is clear that it would rename the variables inside patterns for l.h.s. of either inner Rule or RuleDelayed, as long as they are syntactically coupled via some common variable (as in the last example of yours). The problem here is that the external RuleDelayed does not recognize the correct localization of land U variables - it thinks they belong to Rule. –  Leonid Shifrin Apr 23 '14 at 14:36
@Pillsy [2/2] Then, it does renamings for all variables inside patterns on the l.h.s. of the rule, which, in my simpler example, is Replace[x, {l_Integer, u_Integer} :> l + u]. And it does not care about the non-pattern occurences of l and u (r.h.s. of inner RuleDelayed here), inside the l.h.s. of Rule, because, as I said, it thinks that l_ and u_ patterns belong to Rule. So, it messes up the bindings of inner RuleDelayed. Perhaps, this may be called a bug. Also, not that it is only happens when outer and inner rules are "lexically coupled" by some common variable. –  Leonid Shifrin Apr 23 '14 at 14:38