Replacing parts of a held expression with held parts of another expression

Question

I'm applying the Trott-Strzebonski technique in order to replace inside a held expression.

x = Hold[1 + 1, 2 + 2, 3 + 3];
y = Hold[foo@bar[2]];
y /. bar[j_] :> With[{eval = x[[j]]}, eval /; True]
(* Hold[foo[4]] *)

However, I'd like the replacing expression to remain held during substitution:

(* Hold[foo[2 + 2]] *)

The unwanted evaluation of 2 + 2 seemed to be occurring during the Part statement, x[[j]]. So, I tried using Extract instead:

y /. bar[j_] :> With[{eval = Extract[x, {j}, Unevaluated]}, eval /; True]
(* Hold[foo[Unevaluated[2 + 2]]] *)

I thought Unevaluated would disappear as an argument of the Set function, but this was not so. (Perhaps I still don't quite understand Unevaluated.)

I then thought of removing that head, Unevaluated, through another replacement, but that seems rather convoluted.

Succinctly, how does one replace parts of a held expression with held parts of another expression?

Answer 1

One way to achieve this is to use a "vanishing" wrapper. The idea is to temporarily wrap the substituted expression with a holding symbolic head, and then remove that head in a second replacement:

Module[{h}
, SetAttributes[h, HoldAll]
; y /. bar[j_] :> RuleCondition[Extract[x, {j}, h]] /. h[x_] :> x
]

(* Hold[foo[2+2]] *)

Module is used to ensure that the vanishing symbol does not conflict with any of the symbols in the target expression. This solution is essentially equivalent to the exhibited use of Unevaluated, but forcibly removes the wrapper explicitly instead of relying upon the evaluator to do it.

This trick can be especially handy in more complex substitutions and can be scaled to use multiple wrappers, each with more elaborate semantics than simple vanishing.

The single-wrapper idiom can be made more convenient with a helper macro:

SetAttributes[vanishing, HoldAll]
vanishing[{h_}, body_] :=
  Module[{h}
  , SetAttributes[h, HoldAll]
  ; body /. h[x_] :> x
  ]

It is used thus:

vanishing[{h}, y /. bar[j_] :> RuleCondition[Extract[x, {j}, h]]]

(* Hold[foo[2+2]] *)

Answer 2

x = Hold[1 + 1, 2 + 2, 3 + 3];
y = Hold[foo @ bar[2]];

If you don't mind using undocumented functions, you can do

y /. bar[j_] :> RuleCondition @ Extract[x, j, $ConditionHold]

or $ConditionHold @@ x[[{j}]] instead of Extract[x, j, $ConditionHold]

$ConditionHold works like Hold except that it gets released (up to 2 of them) after the rhs condition has matched

Answer 3

Here is an alternative solution based on expression parsers:

ClearAll[ev];
ev[expr_, rules : {__RuleDelayed}] :=
  Block[{ev},
     SetAttributes[ev, HoldAll];
     Replace[rules, (lhs_ :> rhs_) :> (ev[lhs] := rhs), {1}];
     ev[f_[args___]] := 
        Join @@ Map[ev, Unevaluated[{args}]] /. Hold[x___] :> Hold[f[x]];
     ev[x_] := Hold[x];
     ReleaseHold@ev[expr]
  ]

It accepts an expression where replacements are to be made, and a list of replacement rules. From these rules, it generates a custom expression parser / evaluator ev, inside Block. The replacements then happen as a part of the parsing / evaluation procedure for a given input. The prerequisite for the rules is that they return their r.h.s. wrapped in Hold. Here is how you can use this for your case:

ev[y, {bar[j_] :> x[[{j}]]}]

(* Hold[foo[2 + 2]] *)

Or, making wrapping in Hold more explicit:

ev[y, {bar[j_] :> Extract[x, j, Hold]}]

(* Hold[foo[2 + 2]] *)

Expression parsers / custom evaluators work by evaluating an expression in a restricted way, using the main evaluator, rather than replacing parts using replacement rules. Restricted evaluation is generally a more powerful approach than rule replacements, although may be slower.

The advantage of expression parsers over rule replacements is that generally, within the expression parsers approach, it is much easier to control more complex evaluation (in cases where rule replacements would require nested Trott-Strzebonski tricks, injector patterns, etc). See this post for an example of what I mean.

Answer 4

Although I cannot offer anything as robust and elegant as Rojo's single pass method I find this an interesting problem, and I present a limited alternative for the interest of others. For the sake of the examples I will use a modified y expression:

x = Hold[1 + 1, 2 + 2, 3 + 3];
y = Hold[foo @ bar[2], bar[1], foo[1, bar[3]]];

If our parts are always at the first level of x we can use a rather direct substitution with Slot like this:

Evaluate[y /. bar[j_] :> Slot[j]] & @@ Unevaluated /@ x

Hold[foo[2 + 2], 1 + 1, foo[1, 3 + 3]]

I find this pleasingly concise. :-)