Why this upvalue doesn't escape from Sum?

Question

Probably a hard question, but I decide to cry out loud :).

This is actually another problem I encountered when answering this question. Consider the following transform rule stored as an upvalue:

(a : Except@If)[b___, f[c_, d_], e___] ^:= f[a[b, c, e], d]

See here to understand why I added the Except@If.

It can not escape from the index of Sum:

Sum[x, {x, 1, f[3, a]}]

Sum::vloc : The variable {x,1,3} cannot be localized so that it can be assigned to numerical values

Sum[x, {{x, 1, 3}}, a]

What's going on here?

I believe this is somewhat related to this behavior of Sum that no longer exists in v10, which is another unsolved mystery.

Answer 1

To experiment with UpValues let's define simple up-value on f, that gathers g and h heads, if f is used inside them.

ClearAll[f, g, h]
(head : g | h)[f[args___]] ^:= f[args, head]

We can use TracePrint to visualize steps of Standard Evaluation Sequence of h[f[]] expression.

h[f[]] // TracePrint
(* h[f[]]  Evaluation of h[f[]] expression starts.
    h      Head h evaluates to itself.
    f[]    Evaluation of f[], i.e. first argument of h[f[]], starts.
     f     Head f evaluates to itself,
           f[] has no arguments and no matching DownValues,
           so evaluation of f[] finishes, it evaluates to itself.
           Evaluation of arguments of h[f[]] expression finishes.
           UpValues associated with arguments of h[f[]] expression are used.
   f[h]    f's upvalue replaces h[f[]] with f[h].
           f[h] expression evaluation starts.
    f      Head f evaluates to itself.
    h      First argument h evaluates to itself. *)
(* Out[]= f[h] *)

If we nest f deeper in h:

h[g[f[]]] // TracePrint
 (* h[g[f[]]]
     h
     g[f[]]
      g
      f[]
       f
     f[g]      f's UpValues are used while evaluating g[f[]] expression.
      f
      g
    h[f[g]]    As a result of evaluation of g[f[]] argument we get f[g].
    f[g, h]    f's UpValues ere used while evaluating h[f[g]] expression.
     f
     g
     h *)
(* Out[]= f[g, h] *)

We see that UpValues are used only when they are associated with expression at first level of currently evaluated expression.

Now let's see what changes when we add HoldAll attribute to h.

ClearAll[h]
SetAttributes[h, HoldAll]

h[f[]] // TracePrint
(* h[f[]]
    h
   f[h]
    f
    h *)
(* Out[]= f[h] *)

We see that arguments of h are not evaluated, but UpValues of f are still used.

But what happens if f is deeper than at first level of h:

h[g[f[]]] // TracePrint
(* h[g[f[]]]
    h *)
(* Out[]= h[g[f[]]] *)

Since g[f[]] argument of h is not evaluated, f's UpValues are not used at all. Analogous thing happens in expression from question.

For completeness let's also check what happens when HoldAllComplete attribute is used.

ClearAll[h]
SetAttributes[h, HoldAllComplete]

h[f[]] // TracePrint
(* h[f[]]
    h *)
(* Out[]= h[f[]] *)

Now UpValues are not used even if f[] expression is at first level of h.

---

Going back to expression from question.

Sum has HoldAll attribute, so although this does not prevent usage of UpValues of expressions that are at first level in Sum, it does prevent evaluation of those expressions.

In Sum[x, {x, 1, f[3, a]}] expression, UpValues of x (first argument) and List (head of second argument) are tested, but since {x, 1, f[3, a]} expression is not evaluated (due to HoldAll attribute of Sum), UpValues of f are not tested, so standard evaluation of Sum proceeds.

Arguments of Sum are passed to "body" of Sum function and evaluated somewhere there. So UpValues of f are used in some unknown code inside body of Sum and they break it, they may also interfere with error reporting of Sum.

This is one of examples showing that such catch-all UpValues can be dangerous, and can lead to unpredictable behavior.

Answer 2

It looks like you might have to use holds to prevent the unwanted evaluation during the transformations: