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

[Annie Liu]

Hi!  Thanks for all the ideas and discussions!

Here is a summary of my thinking, followed by some specific comments.

1. I think we should support proper quantifications, because there are
no conceptual or technical difficulties, and it is win-win-win to do.

   No conceptual difficulties:
   . They are first-order logic, used in people's day-to-day reasoning.
   . They are in one of the first two CS courses, the other being programming.
   . They are used commonly in pseudocode.
   They are very far from requiring mathematicians or infinity. :-)
   It would be wonderful if students taking the first two CS courses
   can actually write quantifications in programs at the drop of a hat!

   No technical difficulties:
   . A straightforward implementation suffices, stopping at the first witness.
   . Alternatives/workarounds have many different kinds of difficulties.
   . They are in SETL, the first language that used sets for programming,
     developed over 40 years ago.
   They don't break any Python rules, as far as I know. :-)
   In fact, "some x in s" is better than "s.pop()" in terms of side effect,
   and it gives the programmer a test and a choice of not changing s.
   (not to mention that computing a comprehension to get s followed by
   a pop is less efficient than doing "some x in s" directly)

   It is win-win-win to do, because they help
   . make programming easier
   . make programs clearer
   . make programs more efficient
   This is a dream situation, considering the usual conflicts among these!

2. OK, I think we can ignore tuple patterns for now (they were why I
used "!" for bound variables, for pattern matching).  They are a much
smaller conceptual and technical help.


 > Don't forget that in Python, assignments are
 > statements and don't get embedded in expressions.

I like this principle dearly, but sometimes breaking it is better. :-)
In fact, the alternative I had to use, s.pop(), is a good example of a
statement that does get used in expressions.

In general, any time we have a statement that also returns a value, it
is the same as an expression that has side effect.  There are plenty
of those in Python. :-)

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

Right!(with a little indentation in front of the "for")  Thank you!

In fact, as I mentioned, it happens that using "for" in place of "if"
is ok here (in Robbert's algorithm), but in general, to capture the
original "if" correctly, one would need another temp variable and some
more tedious lines.

 >      """Like all(pred(obj) for obj in iterable), returning True if it is true,
 >      otherwise obj, the first witness that it false.

Thanks for the idea of witness for "all"!  I have actually not needed
to use it, but I can see that the symmetry helps general uses, and
we'd get it for free just like for "any".

 > >    for p1 in (p for slot, p in decisions if slot == slot_num):
 > >        if any(True for slot, p2 in proposals if slot == slot_num and p2 != p1):
 > >            # Do something!
 > 
 > Actually, that may not work - the original requirement was to scan
 > decisions on each iterations, and pick one item that satisfied the
 > condition each time. If decisions is changing each iteration, you need
 > to rescan each time, which your for loop doesn't do.

Right!  Thank you!

 > I think that's why the (otherwise odd) "while there are any, pick one"
 > construct is used. Of course, for an algorithm like that, I'd
 > probably tend to choose a different data structure, maybe something
 > like a work queue.

In fact, "while some x in s" is exactly a best way to write a work
list algorithm, where either a queue or stack could be used (in graph
algorithms, a queue corresponds to breadth-first-search, and a stack
corresponds to depth-first-search), but when the order of picking
elements doesn't matter, "while some x in s" is easier and clearer.

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

I hope new keywords are not the stopping factor.  I remember some
of my programs used "as" a lot (for many nouns starting with a, like
arguments), and I avoided running them with py3 for several years,
until I had to one day, and they were so easy to fix that I regretted
not doing it sooner.

I wonder what the best keywords (and separator) are to use:

   SETL:     forall, exists       e.g., exists x in s | pred
   html:     &forall, &exist 
   latex:    \forall, \exists
   ABC:      each, some           e.g., some x in s has pred
   Ada 2012: for all, for some    e.g., for some x in s => pred

I had used "forall" and "exists", but quite liked "each" and "some"
after I learned them from Lambert Meertens two years ago: besides being
shorter, "each" gives the right grammar (singular) when read out.

But I also feel conflicted, since "all" and "exist" are used for so
long in history, to justify the reversed "A" and "E" in symbols.

BTW, one could use "all" and "any", even shorter and has a reversed
"A":-), but "any" is ambiguous when read out.  For example, we say
"some apple in the bag is red", not "any apple in the bag is red".

For separator, I had used "if" (not "has") because it is consistent
with uses of conditions in general in Python, and with uses of "|" in
SETL.  SETL has:

   comprehension        {ret_exp: x in s | pred}
   quantification       exists x in s | pred
                        forall x in s | pred
   for loop             for x in s | pred loop ... end loop

   and you get "while exists x in s | pred" for free.

   "| pred" can be omitted when "pred" is true.

Interestingly, I noticed that Guido used "if" in his code (after the
"5 tedious lines").

I feel that "has" reads well for single quantification, but not as
well for nested (though "if" sounds a bit weird also, and I'd really
like to use "|" if it doesn't break Python rules :-)).  Compare:

   each x in s has (some y in t has pred)

   each x in s if (some y in t if pred)

   each x in s | (some y in t | pred)

BTW, functions "all" and "any" are much harder to read here:

   all(any(pred for y in t) for x in s)

and it is even harder when you have some real contents for pred, s,
and t, not just the template here.

This reminds me that Guy Steele had a popular lecture making fun of
languages that have features that require people to swing their
eyeballs back and forth on a line to read it. :-)

In summary, again, I think we should support proper quantifications.
BTW, some of the workarounds proposed here are looking like what a
Haskell genius was trying to show me yesterday how to get around. :-)

Thanks,
Annie