PR #178 In-place modification of arrays in "each"

[toggledbits]

I'm moving the discussion on this out of the Mantis PR #178 for the benefit of all/documentation, and also because it's easier to type and format here.

@LibraSun wrote in that PR:

I'm 99% certain you'll explain this one away as "expected" but I naively believed it would yield different results:
In an expression defined by:
a=[1,2,3],
each i in a:
shift(a)
// result (array) [1,2] (unexpected
// expected [1,2,3]

This has me thinking that 'each' is leaving items on the table, as I tried unsuccessfully pointing out above.

The issue here is that your expression shift(a) is modifying the iteration subject array in place. Basically, here are the iteration steps that are run, starting with a=[1,2,3]

1. First iteration: a=[1,2,3]; the local i is assigned the first array element 1, but it is not used in the expression. The expression shift(a) results in 1 and causes a to be reduced to [2,3] (the first element is shifted off and becomes the result). Since this is the last value in the expression, 1 is added to the each result array.
2. Second iteration: a is now [2,3] because the previous iteration modified it. So i is assigned 3, because the iteration is on the second element/iteration through the array, but i is not used in the expression. The shift(a) causes a to be reduced to [3] and its return value is 2, so the value 2 is added to the iteration result array.
3. Third iteration: a is now [3], and we are on the third iteration, but the iteration index of 3 (third iteration) is now off the end of the array (only 1 element long), so iteration stops.

The result of this each is therefore [1,2] because those are two values that were shifted out, and a is left at [3] because there was no third run of shift() to remove it.

As I said in the PR, modifying an array you are iterating through can be dangerous and confusing in many languages, because iterators keep state during iteration, and some operations you can do inside the iteration can and will invalidate that state in some way. In Lua on Vera, this often leads to deadlocks and crashes so bad that the box reboots, not just a Luup reload. It's a Bad Idea, and programmers who know are very wary of doing this type of thing in any language unless they are certain of the side-effects/lack of side-effects.

Your additional example:

a=[1,2,3], // The array 'a' is [1,2,3]
a=unshift(a,0), // The array 'a' is [0,1,2,3]
a=push(a,4), // The array 'a' is [0,1,2,3,4]
each i in a: // Iterating over the 5 elements of 'a'
shift(a) // Take the first element of 'a' and append it to result array [ ]
// result [0,1,2] (unexpected)
// and array 'a' is now [3,4]! (also unexpected)

Also correct result. All of the gyrations before the each are not relevant to behavior here. At the start of the each, the array is [0,1,2,3,4] (5 elements). Iterations:

1. a=[0,1,2,3,4], i=0, shift(a) returns 0 and modifies a to [1,2,3,4]; the each result array is now [0]
2. a=[1,2,3,4], i=2, shift(a) returns 1 and modifies a to [2,3,4]; the each result array is now [0,1]
3. a=[2,3,4], i=4, shift(a) returns 2 and modifies a to [3,4]; the each result array is now [0,1,2]
4. Iteration stops because the iteration index/step is 4, but there remain only two elements in a=[3,4] (we're off the end of the array).

So the each result is [0,1,2] and a is left with [3,4] and this is correct operation.

Key points:

• each keeps state during the iteration (as most iterators do) about the subject of the iteration; if the subject changes in a way that affects the state, unexpected results may occur;
• The functions push(), pop(), shift() and unshift() modify the array in place. If you say b=shift(a) you get a value in b and a modified (shorter) a.

[LibraSun]

Thanks!
I've read and re-read "Step 4" above numerous times, and it's not sinking in.
No need to explain further, simply allow me to stew in these juices a while.
I'll also rig this up a number of other ways (using multiple variables, for starters) to watch intended behavior in action.
Still weirds me out.

EDIT: I believe I understand now; the each loop is foiled mid-stream because the array a keeps shrinking with each iteration, whereas each thinks it's still holding onto a 5-element array. It's not, therefore it aborts.

LESSON: It would make better sense to create an index array (=[0,1,2,...,N]) of the same length as a, and generate the result with:

a=["a","b","c","d","e"], index=[0,1,2,3,4],
each i in index: a[i]

for which the trivial result would be a copy of a as I had been expecting in the original example.

[toggledbits]

@librasun I'm not sure if this will help, but here's an example without arrays that demonstrates the common behavior of loop and iterator constructs often seen. Yes, there are variances across languages, but I think most programmers will agree that this is what they would expect from a new language, and then will be prepared (or surprised) by any differences from that norm:

int n = 10;
for ( int k = 0; k <= n; k = k + 1 ) {
    System.out.println( k );
    if ( k == 5 ) {
        n = 4;
    }
}

If you're not familiar with the for() loop construct (this is C/C++/Java-ish and a little different from Lua), the first expression is the initializer, the second is the continuation test, and the third is the post-effect. The initializer is run once before entering the loop, the continuation test is run before each iteration (and iteration stops if the test is false), and the post-effect is run at the end of each iteration. So in the absence of the if statement, this loop should output the numbers 0 through 10 inclusive.

But what would you expect the output of this loop to be with the if statatement? I would expect:

0
1
2
3
4
5

...and the reason is that each trip through the loop, the test expression k < n is evaluated using the then-current values of k and n. So if n changes, as it does in this case when k reaches 5, the next eval of the loop's test expression would see the new value of n (4), and since we're now in a new iteration, k has gone to 6, which is not less than 4, so the loop exits there.

What does not happen here is that the value of n is pre-determined at the start of the loop, and thus immune to a change within the loop. If that were the case, language consistency would demand that k also be pre-determined and not change in this expression, and this would be disastrous, because the loop could never operate properly (it would loop infinitely in most common applications of this form).

@librasun said in PR #178 In-place modification of arrays in "each":

LESSON: It would make better sense to create an index array (=[0,1,2,...,N]) of the same length as a, and generate the result with:

Well, I'm not really sure what problem you're trying to solve, or if you're just doing crazy things to see what breaks (which is fine, that's a perfectly valid way to test something). Based on what you said you expected in your first example above, all you need is:

a=[1,2,3];
b=each i in a: i;

This would produce your expected [1,2,3] in b. In other words, a copy of the array (a is unmodified here). It would thus follow:

a=["a","b","c","d","e"],
b=each i in a: i

Would produce b=["a","b","c","d","e"] in a bit shorter way than your follow-on example.

[LibraSun]

@toggledbits NOTE: Yes, it was just me trying to break stuff. I really don't have any outstanding needs at the moment in terms of my daily workflows. Thanks for the tutorial (which all makes sense)!