Yes. The recursion has a sound base case and a sound recursion rule.

• In the base case, a singleton array contains its scan sum, the sum of all the elements in the array, because the sum of one value is that value itself.

• In the recursive case, given sub-arrays H0 and H1 each of whose elements contain the sub-array-final scan sum, every element in the combined array can be made to contain the combined-array-final scan sum, by adding together those two scan sums. The other side's scan sum can be gotten from any element on the other side, thus correspondent communication (or mirror, or any other lockstep communication between two arrays) will do it.

To make this fully concrete, here are algorithm definitions and an example computation graph with discussion following. For the elements not here defined, \(:\ \#\ !\ d\ c\ lr\ corr\ atom?\ f_b\), see the Tutorial.

In case you are tracking with George's thesis, Mou 1990 p84, this presentation differs from his immaterially and for perhaps personal reasons. See Footnote below.

The invariant fact in this algorithm is that every level's output-side array, that is, both after \(f_b\) and after \(c_{lr}\), in every resulting pair \(a\ . b\), the value \(b\) is always the scan-sum of the whole array, even though it is separately calculated for each position. This miracle remains true because the scan sums on left and right arrays before combination, which are redundantly added in each position, themselves sum to the scan sum of the combined array.

At each of three levels, the array sizes divide in half until base arrays have only one element.

I like to use the H0 H1 naming convention. In general a division turns a full length array, call it F, into two half-length arrays, H0 (on the left) and H1 (on the right), and combination turns two half-length arrays, H0 (on the left) and H1 (on the right), into a full length array, F. Whether after dividing or before combining, any communication that occurs, when it occurs, occurs between H0 and H1. This pattern holds at every level of division and every level of combination, no matter what the size of the top level input array and how deep is the computation graph.

The 'last0' communication pattern says take the last element of H0 and send it to each and every element in H1. Since it is unidirectional there is no '!'; however if you wanted to also send from the last of H1 to all of H0, you could perhaps write the communication pattern as "# ! last" which reads as "communicate bidirectionally from the last of each half to all members of the other half".

Although this "scan with broadcast" version is easy to write and easy to understand unrolled, there is a hidden cost here in that "last 0" is not a task that can be done independently in all the positions at once, assuming a serial processor in each location. No, it has to send to the first, then to the second, then to the third, etc. so the total time cost is O(N) with N the size of the communicating sub-arrays, which halves at each level of division (in the case of pre-communication) and doubles at each level of combination (in the case of post-communication), so adding those all up using the applicable triangle area formula we get O(N*log(N)/2) which further reduces to O(N*log(N)) by the funny rules of Order-of-Magnitude reasoning. One would prefer it to be O(log(N)): Can we do it? Yes. See Scan W/O Broadcast.

Footnote

• (1) I replaced the \(h_{scan}\) function call in the 4th argument of PDC() with its expansion, to reduce the number of uncomprehended layers I need to consider in my mind at once.

• (2) I renamed his functions \(loc1 +\) and \(loc2 +\) as \(LO_0\) and \(LO_1\) because I couldn't tell whether \(loc\) was intended to refer to a \(location\) or a \(local\ operation\), both being consistent with the text and each leaving a mental question mark in the mind when reading it. I discovered the latter is correct when George did this as a pencil exercise with me in person. Anyway this function naming is unambiguous.

• (3) I renamed his variables \((x,sum) (x1,sum1),(x2,sum2)\) as \(a0.b0, a1.b1\) because \(sum\) is ambiguous between (1) the scan sum at the end of the array, (2) the scan sum for the whole array calculated redundantly at each point in the array, (3) the scan sum taken from the other array, and (4) the running sum that builds up from left to right as one does the scan operation in one's mind. Although these are related, the path through this thicket is clear if (2) is taken as correct. The \(a\ . b\) notation is less ambiguous to the learner, though also less evocative.

• (4) I expanded the output display to include additional output lines after \(\# ! corr\) and after \((!LO_0,!LO_1)\). While producing a much busier computation diagram, this helped me to see the concrete obviousness of every calculation, during the phase of getting the idea.

In the face of those four layers of nesting-complexity, uncertainty, possible misdirection, and information-hiding, I was unable to penetrate this without George's personal intervention with a watch-over-my-shoulder pencil exercise (for scan with broadcast), during which references became clear and the whole thing rather obvious.

My personal struggle with this sheds a bright and helpful light on the struggles of students learning literacy especially using letter names in English spelling (ABC's). Without concrete reliability of interpretation for the written elements of communication, whether letters in English or functions, variables, and operators in math, even a short sentence or equation rapidly becomes impenetrable to the multiple-ambiguity-limited human mind. What is the maximum number of placeholder question marks we can handle in our minds while trying out alternatives during the exploration of an expressed idea? I think one is already difficult, two or more are perhaps impossible without taking notes.