# Adding a Par construct to Python?

Terry Reedy tjreedy at udel.edu
Fri Jun 5 17:38:19 EDT 2009

```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

```