Adding a Par construct to Python?

[Terry Reedy]

Lawrence D'Oliveiro wrote:
> In message <77as23F1fhj3uU1 at mid.uni-berlin.de>, Diez B. Roggisch wrote:
> 
>>> But reduce()? I can't see how you can parallelize reduce(). By its
>>> nature, it has to run sequentially: it can't operate on the nth item
>>> until it is operated on the (n-1)th item.
>> That depends on the operation in question. Addition for example would
>> work. My math-skills are a bit too rusty to qualify the exact nature of
>> the operation, commutativity springs to my mind.
> 
> Associativity:
> 
>     ((A op B) op C) = (A op (B op C))
> 
> So for example
> 
>    A op B op C op D
> 
> could be grouped into
> 
>   (A op B) op (C op D)
> 
> and the two parenthesized subexpressions evaluated concurrently. But this 
> would only give you a speedup that was logarithmic in the number of op's.

It is worth noting, I think, that many realistic operations are not 
associative.  If op combines a summary and an item to create an updated 
summary, it will probably croak or give a wrong answer when given a 
summary and a summary.  Combining two summaries might be possible, but 
would be a different operation.

For a specific example, consider list.append(some_list, some_item) 
versus list.extend(some_list, another_list).  Imagine for that moment 
that these methods returned some_list.  Then

[].append(a).append(b).append(c).append(d) # parentheses left out

would have to be conceptually converted to the associative

[].extend([a]).extend([b]).extend([c]).extend([d])

before being grouped something like

(([].extend([a])).extend([b].extend([c]))).extend([d])

Of course, one would not do the conversion to the slower associative 
operation unless one knew that there would be a compensating speedup due 
to the grouping.

Terry Jan Reedy