Re: Re: Problem with evaluation of delayed rules

*To*: mathgroup at smc.vnet.net*Subject*: [mg21858] Re: [mg21758] Re: Problem with evaluation of delayed rules*From*: Hartmut Wolf <hwolf at debis.com>*Date*: Wed, 2 Feb 2000 22:54:16 -0500 (EST)*References*: <85mkef$1og@smc.vnet.net> <86bkpr$b3o@smc.vnet.net> <200001280356.WAA10760@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

To add more thoughts and solutions, I'd like to unwind this thread in part The problem was posed by Eckhard Hennig schrieb: > > > Assume that we have a list of symbols, e.g. > > In[1]:= symbols = {a, b, c, d}; > > and that we have the following expression that involves a function (here > "If") with HoldXXX attribute (HoldAll, HoldRest, ...). > > In[2]:= expr = If[x > 0, Difference[1, 2], Difference[3, 4]]; > > In the above expression, I want to replace all objects of the form > Difference[i, j] by differences of the two entries i and j from the list > "symbols". If I use a delayed rule as follows > > In[3]:= expr /. Difference[x_, y_] :> symbols[[x]] - symbols[[y]] > > then this is what I get: > > Out[3]= If[x > 0, symbols[[1]] - symbols[[2]], symbols[[3]] - symbols[[4]]] > > Due to the HoldXXX attribute of the "If" function, the right-hand side of > the delayed rule remains unevaluated. However, I need the result of the rule > to be evaluated BEFORE it is inserted into expr, i.e. the result I want for > In[3] is: > > Out[3new]= If[x > 0, a - b, c - d] > > Does there exist any (simple) approach to forcing Mathematica 3.0/4.0 to > simplify the result of a delayed rule as soon as the rule applies to a > subexpression of a held expression (please note the conditions below)? One > may argue that it doesn't make a difference in the end whether result of > rewriting expr is given in the form of Out[3] or Out[3new]. Well, the > difference comes in as soon as you clear the value of "symbols" with > Clear[symbols] and then evaluate Out[3] for some x. > There was a remarkable simple answer from Andrzej Koslowski, namely Off[Part::pspec] expr /. Difference[x_, y_] -> symbols[[x]] - symbols[[y]] If[x > 0, {a, b, c, d}[[1]] - {a, b, c, d}[[2]], {a, b, c, d}[[3]] - {a, b, c, d}[[4]]] You see, the current value of symbols is put in, although there was no further evaluation of the substituted expression. But this is not essential as I pointed out, time will come, and when the decision can be made and If evaluates, then the intended result will show up. Yet to protect the rule against possible values of y and x(!), it should be wrapped with Block: expr /. Block[{x, y}, Difference[x_, y_] :> Evaluate[symbols[[x]] - symbols[[y]]]] RuleDelayed is needed such that values of (the global variables) x or y don't creap in before the pattern variables x and y are substituted, Evaluate is needed to bind the value of symbols before substitution occurs. After some other replies, which didn't please because of their use of resources, I proposed upEvaluate /: f_[x___, upEvaluate[y_], z___] /; f =!= RuleDelayed := f[x, Evaluate[y], z] expr /. Difference[x_, y_] :> upEvaluate[symbols[[x]] - symbols[[y]]] If[x > 0, a - b, c - d] This is a solution for the problem posed, yet it only works at level 1: eval := Evaluate If[x > 0, eval[Difference[1, 2]], eval[Difference[3, 4]]] /. Difference[x_, y_] :> upEvaluate[symbols[[x]] - symbols[[y]]] If[x > 0, eval[upEvaluate[symbols[[1]] - symbols[[2]]]], eval[upEvaluate[symbols[[3]] - symbols[[4]]]]] Since it didn't produce the desired closure, it's of no use except for the case at level 1. Now... Allan Hayes schrieb: > > Eckhard, > > More thoughts > > Investigating the Trott-Strzebonski method for In-Place Evaluation (see > Robby Villegas: > http://library.wolfram.com/conferences/devconf99/villegas/UnevaluatedExpress > ions.nb) > Lead me to > > If[x > 0, Difference[1, 2], Difference[3, 4]] /. Difference[x_, y_] :> > Block[{}, symbols[[x]] - symbols[[y]] /; True] > > If[x > 0, a - b, c - d] > > And tracing the evaluation of this shows that the main work is done by the > internal function RuleCondition. > > If[x > 0, Difference[1, 2], Difference[3, 4]] /. Difference[x_, y_] :> > RuleCondition[symbols[[x]] - symbols[[y]], True] > > If[x > 0, a - b, c - d] > That's it! Boiled down to the essentials. As Allan indicates, it's very interesting to Trace different cases. In a way the original Trott-Strzebonski method If[x > 0, Difference[1, 2], Difference[3, 4]] /. Difference[x_, y_] :> With[{xx = symbols[[x]] - symbols[[y]]}, xx /; True] If[x > 0, a - b, c - d] distracts from the essential. The evaluation of symbols (with substituted pattern variables) is forced by Condition; yet the result shows only up because xx is replaced _textually_ in the (partially evaluated but held body) when With is executed. You clearly see this, when you substitute Module for With: If[x > 0, Difference[1, 2], Difference[3, 4]] /. Difference[x_, y_] :> Module[{xx = symbols[[x]] - symbols[[y]]}, xx /; True] If[x > 0, xx$7, xx$8] Where the variables xx$n (though having the desired values) cannot be evaluated in the held body. With Block interestingly the body is not held If[x > 0, Difference[1, 2], Difference[3, 4]] /. Difference[x_, y_] :> Block[{xx = symbols[[x]] - symbols[[y]]}, xx /; True] If[x > 0, a - b, c - d] and the values can be transferred to substitution. Now since the body of Block is not held, the variable xx is no longer needed and you arrive at Allan's first form. The second form, the essential form can be deduced from judicious observation of the Trace. So now we have the Trott-Strzebonski-Hayes method for In-Place-Evaluation lhs :> RuleCondition[lhs] You even don't need True as the second argument, it seems to be default (of course it doesn't work with False). So for the example from Robby Villegas, with In[131]:= heldTable Out[131]= Hold[Hold[1 + 4 + 4 + 0, 2 + 0 + 1, 1 + 1, 5 + 5 + 2 + 2], Hold[0 + 5 + 5], Hold[5 + 1 + 3, 4 + 1], Hold[3 + 3 + 4 + 0, 5 + 2, 4 + 2 + 0, 2 + 5]] you get In[132]:= heldTable /. p_Plus :> RuleCondition[p] Out[132]= Hold[Hold[9, 3, 2, 14], Hold[10], Hold[9, 5], Hold[10, 7, 6, 7]] Its RuleCondition which forces the evaluation of rhs of the rule (with inserted values of the pattern variables) *before* substitution in the expression (at the lhs of Replace...). I began to read Robby's notebook on Friday. When I reached at Trott-Strzebonski, I asked myself "how can you get at such an idea?". At the same time I was already sharpened with new ideas, so I tried again, and after some jiggling arrived at SetAttributes[replaceAllEvaluated, HoldAll] replaceAllEvaluated[expr_, patt_ -> subs_, cond_:True] := Module[{substitutions = {}, raw, X}, Fold[ReplacePart[#1, Sequence @@ #2] & , raw = expr /. patt /; (If[cond, AppendTo[substitutions, subs]]; cond) :> X, Transpose[{substitutions, Position[raw, X]}]]] replaceAllEvaluated[expr, Difference[x_, y_] -> symbols[[x]] - symbols[[y]]] If[x > 0, a - b, c - d] In[139]:= SetAttributes[h1, HoldAll] In[140]:= SetAttributes[h2, HoldAll] In[141]:= SetAttributes[h3, HoldAll] In[142]:= replaceAllEvaluated[ If[x > 0, h1[h2[Difference[1, 2]]], h3[Difference[3, 4]]], Difference[x_, y_] -> symbols[[x]] - symbols[[y]] ] Out[142]= If[x > 0, h1[h2[a - b]], h3[c - d]] Then I continued to read Robby's paper only get at the next sentence: "You can also do this with ReplacePart, but it's harder to code, and has a worse time and space complexity for a large number of substitutions (and using Fold with ReplacePart would be O(n^2))." ... hm, yet Robby it can be done better ... ClearAll[replaceAllEvaluated] Attributes[replaceAllEvaluated] = HoldAll; replaceAllEvaluated[express_, patt_ -> subst_] := Module[{expr = express, pos}, pos = Position[expr, patt]; Apply[(expr[[##]] = Replace[expr[[##]], patt :> subst]) & , pos, {1}]; expr] replaceAllEvaluated[expr, Difference[x_, y_] -> symbols[[x]] - symbols[[y]]] If[x > 0, a - b, c - d] ... this should be O[n] I finally came up with still another solution. After working with positions upEvaluate wasn't needed any longer, instead Evaluate can be mapped in: pos = Position[expr, Difference[x_, y_]]; replaced = expr /. Difference[x_, y_] :> symbols[[x]] - symbols[[y]]; MapAt[Evaluate, replaced, pos] If[x > 0, a - b, c - d] of course this solution has the same drawback as upEvaluated, namely working only at level 1. But we can enforce deep evaluation when we drill down, and insert a chain of Evaluate-s : expr = If[x > 0, h1[h2[Difference[1, 2]]], h3[Difference[3, 4]]]; pos = Position[expr, Difference[x_, y_]] {{2, 1, 1}, {3, 1}} thrupos = Union[Join @@ Function[{list}, MapIndexed[Take[list, Sequence @@ #2] &, list]] /@ pos] {{2}, {3}, {2, 1}, {3, 1}, {2, 1, 1}} MapAt[Evaluate, expr /. Difference[x_, y_] :> symbols[[x]] - symbols[[y]], thrupos] If[x > 0, h1[h2[a - b]], h3[c - d]] Of course here the total order of the evaluation is not as controlled as with the splendid Trott-Strzebonski-Hayes method, however I might refer to my comment on Andrzej Kozlowski's solution. Kind regards, Hartmut

**Re: Fitting a function to a list (newbie)**

**Re: A question about pattern matching**

**Re: Problem with evaluation of delayed rules**

**Re: A question about pattern matching**