# How to prevent substitution in a part of an expression?

Background: I am trying to write a program that can execute scheme in Mathematica.

Now I have things like {"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}. The syntax converting function I have now is:

convertlist[expr_] :=
Hold[expr] //. {a_, b___} :> scmfun[a][b] // ReleaseHold


Which works fine with expressions without '. ' in scheme means hold all the expression inside, but none of the non-standard evaluation function can stop the substitution, and lots of small changes won't work because ReplaceRepeated will eventually get to the inside expression . and the workaround I currently have seems to be very strange and complex (have to give up this simple design).

My question is that can this function be modified so that everything inside ' is unchanged, i.e.:convertlist[{"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}] will return

scmfun["+"][3, scmfun["-"][2, {"*", 1, 3}]]


scmfun["+"][3, scmfun["-"][2, scmfun["'"][scmfun["*"][1, 3]]]]

• maybe convertlist2[expr_] := Hold[expr] /. {{"'", {x__}} :> foo[x]} //. {a_, b___} :> scmfun[a][b] /. foo -> List // ReleaseHold?
– kglr
Apr 3, 2016 at 9:39
• @kglr thanks for your idea, but this function can only hold one level of the expression, i.e. convertlist2[{"+", 3, {"-", 2, {"'", {1, {"+", 2, 3}}}}}] should be scmfun["+"][3, scmfun["-"][2, {1, {"+", 2, 3}}]], instead of scmfun["+"][3, scmfun["-"][2, {1, scmfun["+"][2, 3]}]] Apr 3, 2016 at 9:51

This is IMO one of the cases where local rules are not a good match for the problem, and one is better off using custom expression parsers. The problem with rules is that the whole expression is transparent to them, and it is hard to make certain parts of it immune to their application. Nevertheless, I will show both approaches below, so that one can compare them.

## An approach based on expression parsers

Assuming that your scmfun is an inert symbol that doesn't have non-trivial evaluation rules attached, we can ignore the evaluation leaks problem, and then have simply this:

ClearAll[convertlist];
convertlist[{"'", inner_List}] := inner;
convertlist[elem_?AtomQ] := elem;
convertlist[{f_, args___}] := scmfun[f] @@ Map[convertlist, {args}];


which works as you requested:

convertlist[{"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}]

(* scmfun["+"][3, scmfun["-"][2, {"*", 1, 3}]] *)


## A rule-based approach

For completeness, let me show a possible approach based on rules. This will do literally what you requested. Since there isn't a built-in function that would shield expression's parts from rules application, we will have to develop it. It may be useful in its own right also more generally.

### Shielding parts of expression from rule application

We will need a helper function, shieldExpression. It will shield specific parts of an expression, matching a given pattern, from rule application, by temporarily replacing them with a certain inert dummy expression (I will use the form symbol[i], for i-th shielded part). It will return the transformed expression wrapped in Hold, together with the rules to perform back-substitutions, in an association. Here is a possible implementation:

ClearAll[shieldExpression];
SetAttributes[shieldExpression, HoldAll];
shieldExpression[expr_, shieldPattern_, shieldSymbol_] :=
Module[{result, rules, i = 0},
{result, rules} =
Reap[Hold[ expr] /. (p : shieldPattern) :>
RuleCondition[
With[{ind = ++i},
Sow[shieldSymbol[ind] :> p]; shieldSymbol[ind]
]]];
If[rules =!= {}, rules = Dispatch @ First @ rules];
<|"HeldExpression" -> result, "ShieldingRules" -> rules|>
]


Here is an example:

shieldExpression[{"+",3,{"-",2,{"'",{"*",1,3}}}},{"'",___}, dummy]

(*
<|
HeldExpression->Hold[{+,3,{-,2,dummy[1]}}],
ShieldingRules->Dispatch[Length: 1]
|>
*)


Based on this function, we can now write a version of ReplaceRepeated, that would shield certain parts of an expression from the "main rule" application, and apply some different transformation rule to those parts after the main rule has been applied:

ClearAll[replaceRepeatedShielded];
replaceRepeatedShielded[
expr_, sr : (Rule | RuleDelayed)[shieldPattern_, _], mainRule_
] :=
Module[{shielded, dummy},
shielded = shieldExpression[expr, shieldPattern, dummy];
Fold[
ReplaceRepeated,
ReleaseHold @ shielded["HeldExpression"],
{ mainRule, shielded["ShieldingRules"], sr}
]
]


As is clear from the code, it first shields the parts of the original expression that match the pattern shieldPattern from the application of the mainRule, then performs main rule substitution, then reconstructs the shielded pieces in the transformed expression, and finally applies a special transformation rule to them.

Here is an example:

replaceRepeatedShielded[
f[a, b, {c, d}, g[{i, j}], h[{k, l}]],
p_g :> newHead @@ p,
l_List :> Total[l]
]

(* f[a, b, c + d, newHead[{i, j}], h[k + l]] *)


where expressions with the head g are shielded from the main rule application, and treated specially.

### The case at hand

Here is the main function then:

ClearAll[convertlistRB];
convertlistRB[expr_] :=
replaceRepeatedShielded[
expr, {"'", inner_List} :> inner, {a_, b___} :> scmfun[a][b]
]


Of course, it returns the same result, as in the first method:

convertlistRB[{"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}]

(* scmfun["+"][3, scmfun["-"][2, {"*", 1, 3}]] *)


### Summary

I presented two different ways to solve this problem. The way I personally prefer is based on the construction of a custom expression parser, that performs a specific traversal through the expression. I prefer it because, in my view, it is easier to write, control, understand and extend. The method based on rule application required additional rather complicated machinery to shield parts of expression from rule substitution. While here it is probably an overkill, I can imagine cases where such approach would be beneficial, which is the main reason why I included this method in my answer.

• This is really awesome! Apr 3, 2016 at 16:42
• @Felix Was glad to help. Thanks for the accept. Apr 3, 2016 at 17:36

A slight modification in @kglr proposition in the comments:

expr = {"+", 3, {"-", 2, {"'", {1, {"+", 2, 3}}}}}

expr /. {"'", x__} :> (x /. List -> f) //. {a_, b__} -> scmfun[a][b] /. f -> List


scmfun["+"][3, scmfun["-"][2, {1, {"+", 2, 3}}]]

When I want to shield expression parts during a ReplaceAll, I just include a null rule for the pattern I want to shield. For instance:

convertList[expr_] := ReplaceRepeated[
Hold[expr],
{{"'", b_} :> {"'", b}, {a_, b___} :> scmfun[a][b]}
] /. {"'", b_} :> b //ReleaseHold


convertList[{"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}]


scmfun["+"][3, scmfun["-"][2, {"*", 1, 3}]]

• Can't remember now why I didn't suggest this method (which I have also been using for a long time), and instead went with the more complex suggestion. But it is clearly very relevant here, big +1. Nov 15, 2017 at 10:34

(* For fun *) you can undo the action of ReplaceRepeated selectively:

convertlistF[expr_] := Hold[expr] //. {a_, b___} :> scmfun[a][b] //.
scmfun["'"][b__] :> (b //. scmfun[a_][c__] :> {a, c}) // ReleaseHold


Examples:

convertlistF[{"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}]


scmfun["+"][3, scmfun["-"][2, {"*", 1, 3}]]

convertlistF[{"+", 3, {"-", 2, {"'", {1, {"+", 2, 3}}}}}]


scmfun["+"][3, scmfun["-"][2, {1, {"+", 2, 3}}]]