ReplaceThen and ReplaceAt - Cross between ReplacePart, Replace, and Extract -- Request for Comment

Question

REWRITE: Multiple edits were hurting clarity

Overview:

I'm doing some work involving injecting code into held expressions, and found that I was repeating myself in a couple areas related to the available Replace and ReplacePart syntaxes. I'll call the two patterns I found myself repeating "ReplaceThen" and "ReplaceAt".

Below, I define ReplaceThen and ReplaceAt, including:

• Definition
• Minimal example
• Constraints
• Motivation (why do I want this?)

After that, I've included the code for my first versions of ReplaceThen and ReplaceAt.

Request:

I'm looking for some feedback (this post is a request-for-comment) on my first versions of ReplaceThen and ReplaceAt. I'm a bit of a newbie, and I want to make sure that:

1. I considered all the edge-cases, and my code is "functionally correct" in the general case
2. Performance is reasonably-close to optimal, for code written in native WFL.
3. Pattern guards are effective without being overly-onerous
4. Flexibility is sufficient enough for functions intended to cover general-case use -- do you have any use-cases you run into yourself that aren't currently solved, but could be with reasonable modifications? Do you have any use-cases that might motivate me to create a 3rd/N'th function within this family of Replace extensions?
5. Forget about the "..., for code written in native WFL" restriction above. Might these warrant being written in C? My guess is that since Replace, ReplacePart, Extract, and Dispatch are all heavily-optimized already, it's probably not worth writing everything from scratch.

This post is a request-for-comment (RFC) on these two functions in-general, with a specific emphasis on the above questions.

---

Function 1: ReplaceThen

Definition:

Perform a normal Replace, but allow wrapping the result in an arbitrary head after replacement, but before any subsequent evaluation.

Minimal example - input:

ReplaceThen[Unevaluated[1+1],1->2,{-1},Hold]

Minimal example - desired output:

Hold[2+2]

c.f.: Replace[Unevaluated[1+1], 1->2, {-1}] would return 4

Constraints

1. Any techniques used to implement ReplaceThen (such as additions of Holds) should be transparent to the end-user. For example, if I call ReplaceThen[Unevaluated[1+1],Plus->Times,{1},Hold,Heads->True], my level specification of {1} should be interpreted exactly the same way that regular Replace interprets its level specifications.

2. Any techniques used to implement ReplaceThen (such as addition of Holds) should be "bulletproof" in that no rules supplied by the end-user should be capable of "breaking" the function. Specifically, ReplaceThen must support edge-cases where the end-user deliberately supplies rules which transform Hold, HoldComplete, or an arbitrary head such as Blank[].

Motivation:

Conveniently, Extract offers us an optional third parameter where we can wrap the extracted contents in an arbitrary head before evaluation. From the documentation:

Extract[expr,pos,h] 
extracts parts of expr, wrapping each of them with head h before evaluation.

Unfortunately, Replace does not offer the same convenience argument out-of-the-box. The reason for creating ReplaceThen which supports a "wrap in head h" argument is the same as the reason for supporting a "wrap in head h" argument for Extract: passing the value returned from Replace to a downstream function is not the same as performing a replacement, then wrapping the replaced expression in an arbitrary head prior to evaluation. It only makes a difference if the replaced expression would evaluate to something else in the first place, but that is the entire subject of this post.

Bottom line:

This is not a complicated function, and instead of:

ReplaceThen[Unevaluated[1+1],Plus->Times,{1},Hold,Heads->True]

If you were only performing a one-off case, you could certainly directly perform:

Replace[Hold[1+1], Plus->Times, {2}, Heads->True]

(just adjust level specification from {1} to {2} in this example)

To re-emphasize: the entire point of this function is to handle the general-case correctly (with respect to the above constraints) and conveniently for arbitrary user-provided rules, so that you don't have to choose between technical correctness and verbosity.

---

Function 2: ReplaceAt

Definition:

Perform a normal Replace (including arbitrary pattern rules, not just substitution of one part with a verbatim-substituted replacement part like ReplacePart does), but only on a portion of an expression specified by an arbitrary part specification (not just a level specification like Replace takes).

Minimal example - input:

ReplaceAt[Hold[1+1,1+1],1->2,{2},{-1}]

Minimal example - desired output:

Hold[1+1,2+2]

c.f.: Replace[Hold[1+1,1+1],1->2,{-1}] would return Hold[2+2,2+2], and Hold[1+1,Evaluate@Replace[Unevaluated[1+1],1->2,{-1}]] would return Hold[1+1,4]

Constraints

Same as ReplaceThen:

1. Interpret a level specification of e.g. {1} exactly the same way that Replace does, regardless of whether the implementation includes e.g. an internal Hold. Interpret a part specification of e.g. {1} exactly the same way that Extract does.

2. Be bulletproof to arbitrary user-supplied rules, including the edge-cases noted for ReplaceThen.

Motivation:

The reason for creating an extension of Replace accepting a part specification argument, versus just using MapAt on Replace (or a closure containing it) is the same reason ReplacePart exists, versus just mapping newExpr& to some part of an expression: it performs the replacement prior to evaluation or without evaluation of the larger expression.. Remember, the semantics of Replace are that replacements are performed "...even when parts have Hold or related wrappers" (including HoldComplete or functions with HoldAllComplete attributes), so even using MapAt[ReplaceAll[rules], ... followed by MapAt[Evaluate, ...] would not provide these semantics.

---

The code follows below...:

First, some boilerplate: setup a HoldComplete-like wrapper, and some dispatch tables for modifying user-provided rules and level specifications:

ClearAll[ReplaceAt`HoldComplete, partSpecPatt, replaceRulePatt, 
levelSpecPattern, ReplaceThen, ReplaceAt]

(* Surrogate for HoldComplete: in case rules themselves transform HoldComplete *)
SetAttributes[ReplaceAt`HoldComplete, HoldAllComplete]

(* Boilerplate pattern guards *)

partSpecPatt = _Integer | _Span | 
   All | {partSpecElements___ /; (And @@ 
       Thread@Unevaluated@MatchQ[{partSpecElements}, partSpecPatt])};
replaceRulePatt = _Rule | _RuleDelayed | {(_Rule | _RuleDelayed) ..};
levelSpecPattern = _Integer | All | 
   Infinity | -Infinity | {Repeated[_Integer | 
      Infinity | -Infinity, {1, 2}]};

(* Translate arbitrary rule(s) to never modify ReplaceAt`HoldComplete *)
(* e.g. if the rule was _[x_]:>Identity[x] *)

ruleExceptTransform = 
  Dispatch[(h : Rule | RuleDelayed)[l_, r_] :> 
    h[Except[ReplaceAt`HoldComplete | _ReplaceAt`HoldComplete, l], r]];

(* Translate level spec to account for ReplaceAt`HoldComplete *)

levelSpecTransform = 
  Dispatch[{{n1_, n2_Integer?Positive} :> {n1, n2 + 1}, 
    n_Integer?Positive :> n + 1, {n_Integer?Positive} :> {n + 1}}];

(* Sugar: make user calls to Options[...] return something *)
(* Allow specifying attributes, e.g. HoldFirst, for Operator forms*)

Options[ReplaceThen] = 
  Join[Options[Replace], {OperatorHold -> {SequenceHold}}];
Options[ReplaceAt] = 
  Join[Options[Replace], {OperatorHold -> {SequenceHold}}];
SetAttributes[ReplaceThen, SequenceHold]
SetAttributes[ReplaceAt, SequenceHold]

Next, here are ReplaceThen and ReplaceAt:

With[{ruleExceptTransform = ruleExceptTransform, 
  levelSpecTransform = levelSpecTransform},
 
 ReplaceThen[expr_, rules : replaceRulePatt, 
   levelSpec : levelSpecPattern : {0}, 
   wrap_Symbol : Function[x, x, SequenceHold], 
   opts : OptionsPattern[ReplaceThen]] := wrap @@ Replace[
    ReplaceAt`HoldComplete[expr],
    Replace[rules, ruleExceptTransform, {0, 1}],
    Replace[levelSpec, levelSpecTransform],
    FilterRules[{opts}, Options[Replace]]
    ];
 
 ReplaceAt[expr_, rules : replaceRulePatt, partSpec : partSpecPatt, 
   levelSpec : levelSpecPattern : {0}, 
   opts : OptionsPattern[ReplaceAt]] :=
  ReplacePart[
   Unevaluated@expr,
   Replace[
    Replace[
     Extract[Unevaluated@expr, partSpec, ReplaceAt`HoldComplete],
     Replace[rules, ruleExceptTransform, {0, 1}],
     Replace[levelSpec, levelSpecTransform],
     FilterRules[{opts}, Options[Replace]]
     ],
    ReplaceAt`HoldComplete[x_] :> RuleDelayed[partSpec, x]
    ]
   ];
 
 ]

We might as well support Operator forms of the above, while we're at it:

ReplaceThen[rules : replaceRulePatt, 
   levelSpec_ : levelSpecPattern : {0}, 
   wrap_Symbol : Function[x, x, SequenceHold], 
   opts : OptionsPattern[ReplaceThen]] := 
  Function[expr, ReplaceThen[expr, rules, levelSpec, wrap, opts], 
     Evaluate@OptionValue@OperatorHold] /. DownValues@ReplaceThen /. 
   Verbatim[FilterRules][x_, y__] :> RuleCondition@FilterRules[x, y];

(* Remember Unevaluated if not inlining with DownValues *)

ReplaceAt[rules : replaceRulePatt, partSpec : partSpecPatt, 
   levelSpec : levelSpecPattern : {0}, 
   opts : OptionsPattern[ReplaceAt]] := 
  Function[expr, ReplaceAt[expr, rules, partSpec, levelSpec, opts], 
     Evaluate@OptionValue@OperatorHold] /. DownValues@ReplaceAt /. 
   Verbatim[FilterRules][x_, y__] :> RuleCondition@FilterRules[x, y];

Alternatively, I could have written ReplaceAt in terms of ReplaceThen. The below alternative relies upon the fact that RuleDelayed consumes Unevaluated from any expression which starts with Unevaluated:

ClearAll[ReplaceAt]
Options[ReplaceAt] = 
  Join[Options[Replace], {OperatorHold -> {SequenceHold}}];
SetAttributes[ReplaceAt, SequenceHold]

ReplaceAt[expr_, rules : replaceRulePatt, partSpec : partSpecPatt, 
  levelSpec : levelSpecPattern : {0}, opts : OptionsPattern[]] := 
 With[{subExpr = 
    Extract[Unevaluated@expr, partSpec, 
     ReplaceThen[rules, levelSpec, Unevaluated, opts, 
      OperatorHold -> {SequenceHold, HoldFirst}]]},
  ReplacePart[Unevaluated@expr, partSpec :> subExpr]]

ReplaceAt[rules : replaceRulePatt, partSpec : partSpecPatt, 
  levelSpec : levelSpecPattern : {0}, opts : OptionsPattern[]
  ] := With[{replaceThenOp = 
    ReplaceThen[rules, levelSpec, Unevaluated, opts, 
     OperatorHold -> {SequenceHold, HoldFirst}]},
  Function[expr, 
   With[{subExpr = Extract[Unevaluated@expr, partSpec, replaceThenOp]},
    ReplacePart[Unevaluated@expr, partSpec :> subExpr]], 
   Evaluate@OptionValue@OperatorHold]]

That concludes the function definitions. Now, let's test the functions against the minimal examples I posted earlier (I've of course done a bit more testing than this, which I won't include, for brevity):

Input:

ReplaceThen[Unevaluated[1 + 1], 1 -> 2, {-1}, Hold]
ReplaceAt[Hold[1 + 1, 1 + 1], 1 -> 2, {2}, {-1}]

Output:

Hold[2 + 2]
Hold[1 + 1, 2 + 2]

The results are what I would expect. That said, perhaps there are some edge-cases that I haven't thought through, or performance/flexibility could be increased. Or perhaps you can think of an alternative way to perform the same tasks, written in WFL, which is simply more elegant.

Thanks in advance for feedback / critiques!

Answer 1

Well, I give my first shot a "C-". Here is an updated self-corrected version, for posterity. Maybe some unlucky shmuck who is working with held expressions can make use of this someplace in the future.

Changes:

• Change pattern guard to permit replacement rules which use nested lists of rules (an allowed syntax of regular Replace)
• Use NonNegative vs Positive when adjusting level specifications to account for ReplaceAt`HoldComplete
• Based on empirical performance testing, use of recursive pattern guards has terrible performance -- switch to a Flatten-based method for testing part specification patterns
• Operator forms were not fully "inlined" -- more computation was occurring at runtime (i.e. when the Operator was invoked) than was strictly necessary. The new version performs more computation at creation-time (i.e. when the Operator is defined).
• Removed one variable (the replaced sub-part) from the With expression of ReplaceAt by using Evaluate on the RHS of the ReplacePart rule -- just a little cleaner
• Switched to using a giant TemplateWith to define all functions. It suites my coding style better to be able to build everything in small steps, but without leaving behind a trail of side-effects.
• Note: Also included a TemplateSubstitute definition that is like TemplateSlot, but "actually works" when you're transforming one TemplateExpression into another TemplateExpression. I find this handy.

ClearAll[ReplaceAt`HoldComplete, ReplaceThen, ReplaceAt]

TemplateSubstitute = 
  TemplateApply@*TemplateEvaluate@*
   TemplateVerbatim[TemplateExpression]@*TemplateExpression@*
   TemplateSlot;

TemplateApply@TemplateWith[
  {
   (* Boilerplate pattern guards *)
   
   "partSpecPattern" -> 
    PatternTest[_, 
     MatchQ[List@RepeatedNull[_Integer | _Span | All]]@*Flatten@*List],
   "replaceRulePattern" -> 
    PatternTest[_, 
     MatchQ[List@
        RepeatedNull[_Rule | _RuleDelayed]]@*(Flatten[#, 2] &)@*
      List],
   "levelSpecPattern" -> 
    PatternTest[_, 
     MatchQ[List@
        Repeated[_Integer | -Infinity | Infinity | All, {0, 
          2}]]@*(Flatten[#, 1] &)@*List],
   
   (* Guard ReplaceAt`HoldComplete from arbitrary rules *)
   (* e.g. if the rule was _[x_]:>Identity[x] *)
   
   "ruleExceptTransform" -> 
    Dispatch[(h : Rule | RuleDelayed)[l_, r_] :> 
      h[Except[ReplaceAt`HoldComplete | _ReplaceAt`HoldComplete, l], 
       r]],
   "MakeSafeRules" :> TemplateEvaluate@Replace[Dispatch@{
        TemplateSlot@"ruleExceptTransform",
        ll : {___List} :> 
         Replace[ll, TemplateSlot@"ruleExceptTransform", {2}],
        l___List :> 
         Replace[l, TemplateSlot@"ruleExceptTransform", {1}]
        }],
   
   (* Shift level spec for ReplaceAt`HoldComplete *)
   
   "ShiftLevelSpec" -> Replace@Dispatch@
      {{n1_, n2_Integer?NonNegative} :> {n1, n2 + 1}, 
       n_Integer?NonNegative :> 
        n + 1, {n_Integer?NonNegative} :> {n + 1}},
   
   (* Default options and attributes *)
   
   "ReplaceOptions" -> Options[Replace],
   "DefaultOptions" :> 
    TemplateEvaluate@
     Unevaluated@
      Append[OperatorHold -> {SequenceHold}]@
       TemplateSlot@"ReplaceOptions",
   "DefaultAttributes" -> SequenceHold,
   
   (* DownValue LHS *)
   
   "ReplaceThenLHS" :> 
    ReplaceThen[repThenExpr_, 
     rules : TemplateSlot@"replaceRulePattern", 
     levelSpec : TemplateSlot@"levelSpecPattern" : {0}, 
     wrap : _Symbol | _Function : Function[x, x, SequenceHold], 
     opts : OptionsPattern[ReplaceThen]],
   
   "ReplaceThenOperatorLHS" :> 
    TemplateEvaluate@Unevaluated@Rest@TemplateSlot@"ReplaceThenLHS",
   
   "ReplaceAtLHS" :> 
    ReplaceAt[repAtExpr_, rules : TemplateSlot@"replaceRulePattern", 
     partSpec : TemplateSlot@"partSpecPattern", 
     levelSpec : TemplateSlot@"levelSpecPattern" : {0}, 
     opts : OptionsPattern[ReplaceAt]],
   
   "ReplaceAtOperatorLHS" :> 
    TemplateEvaluate@Unevaluated@Rest@TemplateSlot@"ReplaceAtLHS",
   
   (* Main body *)
   
   "ProcessArgsTemplate" :> With[
     {
      safeRules = TemplateSlot["MakeSafeRules"]@rules,
      shiftedLevelSpec = TemplateSlot["ShiftLevelSpec"]@levelSpec,
      replaceOpts = FilterRules[{opts}, TemplateSlot@"ReplaceOptions"] 
      },
     TemplateSlot@1
     ],
   
   "ReplaceThenDirect" :> 
    Apply[wrap]@
     Replace[ReplaceAt`HoldComplete@repThenExpr, safeRules, 
      shiftedLevelSpec, replaceOpts],
   
   "ReplaceThenOperator" :> 
    Function[repThenExpr, TemplateSlot@"ReplaceThenDirect", 
     Evaluate@OptionValue@OperatorHold],
   
   "ReplaceAtHelper" :> 
    TemplateEvaluate[
     Apply[Unevaluated] @@@ TemplateSubstitute@"ReplaceThenDirect"],
   
   "ReplaceAtDirect" :> 
    ReplacePart[Unevaluated@repAtExpr, partSpec :> Evaluate@
       Extract[Unevaluated@repAtExpr, partSpec, 
        Function[repThenExpr, 
         TemplateSlot@"ReplaceAtHelper", {HoldAll, SequenceHold}]]],
   
   "ReplaceAtOperator" :> 
    Function[repAtExpr, TemplateSlot@"ReplaceAtDirect", 
     Evaluate@OptionValue@OperatorHold]
   
   },
  TemplateExpression[
   (* Surrogate for HoldComplete: 
   in case rules themselves transform HoldComplete *)
   
   SetAttributes[ReplaceAt`HoldComplete, HoldAllComplete];
   
   (* Sugar: make user calls to Options[...] return something *)
   
   Options@ReplaceThen = TemplateSlot@"DefaultOptions";
   Attributes@ReplaceThen = TemplateSlot@"DefaultAttributes";
   Options@ReplaceAt = TemplateSlot@"DefaultOptions";
   Attributes@ReplaceAt = TemplateSlot@"DefaultAttributes";
   
   TemplateSlot@"ReplaceThenLHS" := 
    TemplateObject[TemplateSlot@"ProcessArgsTemplate", 
     TemplateSlot@"ReplaceThenDirect"];
   TemplateSlot@"ReplaceThenOperatorLHS" := 
    TemplateObject[TemplateSlot@"ProcessArgsTemplate", 
     TemplateSlot@"ReplaceThenOperator"];
   
   TemplateSlot@"ReplaceAtLHS" := 
    TemplateObject[TemplateSlot@"ProcessArgsTemplate", 
     TemplateSlot@"ReplaceAtDirect"];
   TemplateSlot@"ReplaceAtOperatorLHS" := 
    TemplateObject[TemplateSlot@"ProcessArgsTemplate", 
     TemplateSlot@"ReplaceAtOperator"];
   Null
   
   ]
  ]

Finally, since my stated purpose for these functions ("injecting code into held expressions") is rather nebulous, I'll include a PREVIEW of what my real end-goal is. I'm building out some utility functions related to general-purpose evaluation control -- the first one, EvaluateSome would be something like the below. Please note that the below is NOT mature yet:

EvaluateSome /: 
 HoldPattern[
   mainExpr : (callHead : Except[HoldPattern | Verbatim])[callLeft___,
      eval : EvaluateSome[func_Symbol][expr__], 
     callRight___]] /;
  (FreeQ[Unevaluated@mainExpr, MakeBoxes]) := 
 ReplaceAt[Unevaluated@callHead[callLeft, expr, callRight], 
  f_func :> RuleCondition@f, {1 + Length@List@Unevaluated@callLeft}, {0, 
   Infinity}]

Test input:

F[x_] := x^2 + Integrate[Cos[y], {y, 0, 2}] //EvaluateSome[Integrate]
Definition@F

Output:

F[x_]:=x^2 + Sin[2]

The above simple example could be done using a With clause, or simply pre-defining the Integrate portion of the expression in a separate variable, but sometimes when you are making factory functions, things like this are just plain convenient...