MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Fitting a function to a list (newbie)
  • Next by Date: Re: A question about pattern matching
  • Previous by thread: Re: Problem with evaluation of delayed rules
  • Next by thread: Re: A question about pattern matching