Why are we so sure about Map results?

I do abuse it often but when I have faced this feature first time I was really suprised:

i = 0;
(i++; # - i) & /@ Range[5]


{0, 0, 0, 0, 0}

What am I asking about is how do we know Map will do 'mapping' position after position? Of course it might look logical but it is not stated, and then, since I know nothing about memory allocation etc., I could expect strange results. To be more precise, I could expect them only in cases where mapping funcion is changing during mapping.

I have failed to find a word in documentation, only related but not important in this case:

Leaves are visited before roots

Have I missed something?

-
You don't know, but does it matter? –  rcollyer Jun 25 '13 at 12:43
There is a difference between the manner in which it is implemented and a guarantee by specification. I think there is nothing except compatibility constraints that forces Map to behave this way. However, I highly doubt that this will change as long as the evaluator remains single-threaded. One can imagine other implementations of the Mathematica language in which this might not apply. –  Oleksandr R. Jun 25 '13 at 12:54
There is no formal specification for the Mathematica language, so indeed all we have to rely on is common practice and personal experience. If WRI succeeds in formalizing the language and reimplementing it outside of Mathematica, things will be different since we will know with certainty whether this is considered a legitimate assumption. Until then, I would suggest that if it works, you can use it. –  Oleksandr R. Jun 25 '13 at 13:16
Of course, I agree with you that this might be a problem. What we can be reasonably certain of is that the evaluator was never designed with concurrency in mind and that multi-threaded term rewriting is difficult to implement in general, so it's unlikely that this will change before a formal language specification appears. –  Oleksandr R. Jun 25 '13 at 13:24
I would say that one can rely on this behavior, because Map first creates a resulting list, and only then passes it to the top-level evaluator. There are many ways to see that, here is one:Trace@Catch[Map[Throw["Done"] &, Range[4]]]. Now, for evaluation process, it is known that it always goes from left to right for elements at the same level in an expression. These observations taken together mean that the above behavior is robust (at least as far as I can tell). –  Leonid Shifrin Jun 25 '13 at 15:36

I'm afraid my comment was too obscure to be noticed. Further, I disagree with one premise somewhere in the commentary, and I wish to make a fuller explanation to see if I understand correctly or incorrectly. Finally, I think the question is answered in the documentation on the Standard Evaluation Procedure:

• Evaluate the head of the expression.
• Evaluate each element in turn.
• Apply transformations associated with the attributes Orderless, Listable, and Flat.
• Apply any definitions that you have given.
• Apply any built-in definitions.
• Evaluate the result.

The first two implies that parts 0, 1, 2,... will be evaluated in order (unless one cavils that "in turn" does not imply order).

When Map[f, {1, 2, 3}] is evaluated, we get, after Map, f, and {1, 2, 3} are evaluated,

{f[1], f[2], f[3]}


Next this List is evaluated, with f[1], f[2], f[3] being evaluated in turn. Thus with the OP's function, the side effect on i is defined. Trace will show that what happens conforms to standard evaluation (of course).

Note that the mapping part (applying f to each element of {1, 2, 3}) might be done in any order. What matters is that the intermediate list {f[1], f[2], f[3]} is then evaluated in a defined order (left-to-right).

So, I think this behavior is defined by the documentation.

In the tutorial on Evaluation, it states in "an expression like h[Subscript[e, 1], Subscript[e, 2]\[Ellipsis]], Mathematica evaluates "each element Subscript[e, i] in turn." I think the "in turn" with the reference to the subscript i must mean in the natural order of 1, 2,.... There always seem to be questions of interpretation in documentation, but if writers did not mean that, I think they could be fairly criticized for misleading users, which I doubt they are.

-
You are correct, I don't read "in turn" as "in order." "In order" is the simplest interpretation, but not necessarily the only one. That said, even with the out-of-order execution done by processors, a dependency analysis must be performed to ensure that re-ordering is even possible. It is simpler, but not necessarily faster, if no reordering is done. –  rcollyer Jun 25 '13 at 15:59
@rcollyer Yours is a more cautious interpretation, but I will probably stick to mine. :) On the other hand, as a matter style, we might be in agreement that such side effects as in the OP's example should be avoided unless impractical. I would probably use MapIndexed or perhaps FoldList for that kind of thing. –  Michael E2 Jun 25 '13 at 17:56
To each their own. :) And, yes we are in agreement that the OP's implementation is impractical and that MapIndexed is the right tool for the job. –  rcollyer Jun 25 '13 at 18:26

On my installation of Mathematica 9.01 (Windows 7 x64), with the lightweight grid enabled

ii=0;
(#-ii++)& /@ Range[1,10]

out[1]= {1,1,1,1,1,1,1,1,1,1}


and

ii=0;
Parallelize[(#-ii++)& /@ Range[1,10]]

out[2] = {-3, -3, -1, -1, 3, 4, 5, 6 ,7, 8}


In fact, I get a different result each time I run the latter variant.

One of the delights of functional programing is that, in principle, pure functional programs are much easier to analyse to identify how they may safely be parallelized than are programs written in the imperative style. Clearly, Parallelize makes some (generally reasonable) assumptions about the nature of the functional code it is being asked to execute in parallel that are violated in the above simple expression. For that reason, I always try to keep resolutely within the functional idiom when writing Mathematica (or Wolfram Language if you must). I found that learning Haskell (which is rigorously functional) helped me a lot with writing better Mathematica code.

-