[Python-ideas] Fwd: quantifications, and tuple patterns

[Paul Moore]

On 14 January 2012 19:24, Guido van Rossum <guido at python.org> wrote:
> But Paul, aren't you missing the fact that for the algorithms that Annie and
> her students want to write, the "witness" concept is essential? I.e. they
> can't just use any(P(x) for x in xs) because if it returns True, they want
> to know the x that made P(x) be true. Her ! notation is a (perhaps
> unpythonic) attempt at exporting this witness from the quantification.

Fair point. I was thinking that common cases worked with any(), and
more complex cases that needed a witness would be sufficiently rare
that the extra verbosity would (a) not be a huge burden, and (b) help
to make the intent clearer.

>> >  while some (!slot_num,p1) in decisions:
>> >     if some (!slot_num,p2) in proposals has p2 != p1:
>> >        propose(p2)
>> >     perform(p1)
[...]
>> Can I suggest you write your example out in Python that works today,
>> and then show how it looks with your proposed syntax alongside? If you
>> can't find the "best" way of writing it in existing Python, just write
>> it however works, no need to try to make it compact, or elegant.
>> There'll be plenty of people here who will show you how to write
>> idiomatic Python versions of what you post :-)
>
> Actually she gave one in her first post. Here it is again:

I'm sorry about that! I got confused part-way through the original
post and skimmed from there, and then didn't go back and reread it in
the context of the follow-up, so I missed the example. My mistake.

>        while {p1 for (s0,p1) in decisions if s0==slot_num}:
>           p1 = {p1 for (s0,p1) in decisions if s0==slot_num}.pop()
>           for p2 in {p2 for (s0,p2) in proposals if s0==slot_num if p2 !=
> p1}:
>
> Note that the set {p1 for (s0,p1) in decisions if s0==slot_num} is computed
> twice, once to decide whether to stop, and then again to compute the witness
> (p1). Obviously this is inefficient, and that's what she's after.

Agreed, that's inefficient, and it also violates DRY - I can easily
imagine those two lines getting out of sync after a while...

> To make
> this same code more efficient in Python, you'd have to do the following,
> which is natural for us programmers (since we're so used to working around
> limitations and inefficiencies in the systems we work with) but unnatural
> for mathematicians, who count to infinity at the drop of a hat:

Hmm, I have an aversion to languages (or constructs) based around
theoretical principles. Blame a couple of encounters with Haskell a
few years ago. I lost. :-) But it tends to be the over-compressed
syntax rather than the ideas that I'm particularly allergic to.

> while True:
>   temp = {p1 for (s0,p1) in decisions if s0==slot_num}
>   if not temp:
>     break
>   p1 = temp.pop()
>
>   for p2 in {p2 for (s0,p2) in proposals if s0==slot_num if p2 != p1}:
>     <whatever>

Point taken. On the other hand, if (x := val) was an expression form
of assignment, like C's assignment, you could write

while temp := {p1 for (s0,p1) in decisions if s0==slot_num}:
  p1 = temp.pop()

  for s2 ...

which is to my mind as succinct, and clearer to a non-mathematician,
as your proposal below (and Annie's proposal). It also builds off a
much more commonly requested feature :-)

Actually,

while any(p1 := p for (s,p) in decisions if s == slot_num):
  for s2 ...

works, and is just as short as your proposal or Annie's.

> The 5 tedious lines from "while" through "pop()" would be collapsed into a
> single line if you could write
>
>   while some s0, p1 in decisions if s0 == slot_num:
>
>   for p2 in {p2 for (s0,p2) in proposals if s0==slot_num if p2 != p1}:
>     <whatever>
>
> TBH I'm not sure what the !slot_num notation is for -- it appears that
>
>   while some (!slot_num, p1) in decisions:
>
> is equivalent in Annie's proposal to
>
>   while some s0, p1 in decisions if s0 == slot_num:
>
> but I'm not sure and it doesn't feel necessary to me.

Yes, I think that's right. It looks like the idea comes from the
concept of unification in logic languages (and the ! notation means
"don't unify this value, but rather treat it as a fixed value that
must match"). Thanks for your analysis, by the way, I think understand
the proposal a lot better now.

So, going back to what Annie was referring to, there seem to be three
key concepts:

Quantifications, which are covered in Python by any() and all()
Capturing a "witness", which can be done using assignment-as-expression
Tuple matching, which you have shown can be handled using tuple
unpacking plus the generator expression if clause, but could probably
gain from a more compact notation.

BTW, as I'm sure everyone knows, you can simulate assignment-as-expression with

def asgn(o, val):
  o.ans = val
  return val

>>> any(asgn(c,x) for x in (1,2,3) if x%2 == 0)
True
>>> c.ans
2

> Also note that SOME and EACH quantifiers were present in ABC (Python's
> predecessor: http://homepages.cwi.nl/~steven/abc/qr.html#TESTS); I dropped
> them for simplicity, not because I didn't like them. If we wanted to we
> could have them back (except for the problems of introducing new keywords).

One day, I really must read up on ABC.

Paul.