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

[Guido van Rossum]

On Sat, Jan 14, 2012 at 1:38 PM, Paul Moore <p.f.moore at gmail.com> wrote:

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

Actually it's worse. neither expression needs to compute the full set --
they only need to iterate until the first match.


> > 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. :-)


In my case the jury is still out, but I'm not worried about Haskell ever
overtaking Python. :-)

FWIW, comprehensions also come from these theoretical principles, so it's
not all bad...


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

Yeah, and it also avoids computing the elements of the set beyond the first.


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

And thanks for the link with logic languages, that's an area I know even
less about...


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

I'm not sure we need a new construct for tuple matching. Witness capturing
seems the most important missing feature here.


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

Eew. :-(


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

Just follow the above link and scroll to the top. :-)

-- 
--Guido van Rossum (python.org/~guido)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20120114/8e6c25b4/attachment.html>