Adding a Par construct to Python?

[Steven D'Aprano]

On Thu, 28 May 2009 10:53:17 -0700, Aaron Brady wrote:

> On May 27, 11:07 pm, Steven D'Aprano <st... at REMOVE-THIS-
> cybersource.com.au> wrote:
>> On Wed, 27 May 2009 12:58:02 +0000, Albert van der Horst wrote:
>>
>> >>And how is reduce() supposed to know whether or not some arbitrary
>> >>function is commutative?
>>
>> > Why would it or need it? A Python that understands the ``par''
>> > keyword is supposed to know it can play some tricks with optimizing
>> > reduce() if the specific function is commutative.
>>
>> Fine. Move the smarts out of reduce() into the compiler. How is the
>> compiler supposed to know if an arbitrary function is commutative?
> 
> Unit testing.

(Correction: the characteristic we really care about is associativity, 
not commutativity.)

I really shouldn't reply to this, because I fear this is just going to 
drag me down into a bottomless pit, but here goes...

I don't see how unit tests can possibly help. There's an infinite number 
of possible functions that could be passed to parallel reduce(), and you 
can't test them all. Even if you lower your sights and just aim to 
recognise a tiny subset of associative functions, you end up with code 
like this:

def par_reduce(func, *args):
    if func in (operator.add, operator.mul):
        if isinstance(args[0], (int, long)):
            return _associative_par_reduce(func, *args)
    return _nonassociative_par_reduce(func, *args)

You can't even recognise functions like lambda x,y: x+y. In case you're 
thinking you can, no, "if func == lambda x,y: x+y" won't work:

>>> (lambda x,y: x+y) == (lambda x,y: x+y)
False

I suppose if you're willing to special case a tiny handful of functions, 
that's a solution of sorts, but I did ask about arbitrary functions.

Perhaps you're thinking of another approach: put the unit tests inside 
the par_reduce() function, and use them to determine at runtime whether 
or not the argument func is associative.

def par_reduce(func, *args):
    try:
        # a mass of unittests
    except Exception:
        # are we catching too much? are we masking bugs in the tests?
        return _nonassociative_par_reduce(func, *args)
    return _associative_par_reduce(func, *args)


This would be impractical, because the cost would be enormous. But even 
putting that aside, it still wouldn't work. I don't see how you could 
know what is a valid unittest for an arbitrary function, but suppose you 
could, somehow. Then what? True enough, if you run lots of tests, and it 
fails one, then you know that func is not associative. But having passed 
all those tests, you can't know if your tests covered all the possible 
cases.

E.g. for floats, you can run some tests and decide that addition looks 
associative:

>>> 0.1 + (0.1 + 0.1) == (0.1 + 0.1) + 0.1
True
>>> 0.1 + (0.9 + 0.1) == (0.1 + 0.9) + 0.1
True
>>> 0.1e67 + (0.9 + 0.3) == (0.1e67 + 0.9) + 0.3
True
>>> 0.1e54 + (0.9 + 0.1) == (0.1e54 + 0.9) + 0.1
True

but you'd be wrong:

>>> 1e54 + (-1e54 + 0.1) == (1e54 + -1e54) + 0.1
False

No, you can't expect to discover experimentally whether an arbitrary 
function is associative. You would need to analyse what the function 
does, which means in practice the *programmer* needs to decide what to 
do, not reduce().



-- 
Steven