How to correctly implement in a new function the scoping behavior of Table, Sum and other commands that use Block to localize iterators?

Question

It is documented that "Block is automatically used to localize values of iterators in iteration constructs such as Do, Sum, and Table." Therefore the dummy index (iterator) in a Sum is shielded against a global variable with the same name, for example:

k = 123;
Sum[f[k] + f[k], {k, -Infinity, Infinity}]

gives the result:

Sum[2*f[k], {k, -Infinity, Infinity}]

I am creating my own version of the Sum command, this is the way I thought Block[] had to be used:

SetAttributes[mySum, HoldAll];
mySum[arg_, {index_Symbol, limits___}] :=
  Block[{index, evaluatedarg},
   Print["debug msg 1"];
   evaluatedarg = arg;
   With[{replaceevaluated = evaluatedarg},
            mySum[replaceevaluated, {index, limits}] /;
     HoldComplete[replaceevaluated] =!= HoldComplete[arg]] 
   ];

However the "index" variable inside Block[] becomes red, Mathematica showing a scoping conflict that I do not see. Now, it gives the correct result, but the problem is that the function gets called several times (instead of only two times, as I was expecting), as in this sample run:

k = 8;
mySum[f[k] + f[k], {k, -Infinity, Infinity}]

which gives the output:

debug msg 1
debug msg 1
debug msg 1
debug msg 1
debug msg 1
debug msg 1
mySum[2 f[k], {k, -\[Infinity], \[Infinity]}]

It is bad that the function gets called so many times, because when it is part of a large expression, with nested sums and other algebraic manipulations, the calculation becomes too slow to be useful. It seems this behavior is because of the scoping problem in the index variable, because if I rename the index inside Block to index2 (which of course destroys the scoping I wanted) and run in a fresh Mathematica session, the message is only printed twice (the first time when the rule is really applied, and the second time when it is determined that the rule does not apply for the new mySum). So my questions are a)How does the scoping problem make the function to be called more than twice?, but more important for me b)What is the correct way to implement the "Block" behavior in the command mySum so it works like the standard Sum command?

Answer 1

You can safely ignore the warning and red highlighting. It simply tells you that the variable will be injected into Block by the top-level rule (your function), rather than being the actual symbol originally present in Block's declaration list. Which is exactly what you want here.

In most cases, things like that happen due to a programmer's mistake, which is why there is a warning. But in your case, you do want to use Block exactly like that. Also, while there is a warning, in the case of Block the outer SetDelayed won't attempt to rename variables, since Block is a dynamic rather than lexical scoping construct - so you don't have to worry about that either.

As to the number of calls, one thing you can do to reduce them is to replace

mySum[arg_, {index_Symbol, limits___}] := ...

with

mySum[arg_, {index_Symbol, limits___}] /; ! ValueQ[evaluatedarg] := ...

This would cut the number of calls in half, for your example.

Answer 2

After one week of constant trial and error, I discovered that I only have to use the attribute HoldAllComplete instead of HoldAll:

SetAttributes[mySum, HoldAllComplete];
mySum[arg_, {index_Symbol, limits___}] := 
  Block[{index, evaluatedarg}, Print["debug msg 1"];
   evaluatedarg = arg;
   With[{replaceevaluated = evaluatedarg}, 
    mySum[replaceevaluated, {index, limits}] /; 
     HoldComplete[replaceevaluated] =!= HoldComplete[arg]]];

It gives the desired behavior, if we execute:

k = 8;
mySum[f[k] + f[k], {k, -Infinity, Infinity}]

we obtain:

debug msg 1
debug msg 1
mySum[2 f[k], {k, -\[Infinity], \[Infinity]}]

that is the correct answer with only two function calls. Even better, if we combine with the answer of Leonid, replacing:

mySum[arg_, {index_Symbol, limits___}] /; Not[ValueQ[evaluatedarg]] := ...

then we obtain the correct answer with a single function call. Exactly what I need.