Fwd: quantifications, and tuple patterns
Sorry, should have replied on list. On 14 January 2012 05:25, Annie Liu <liu@cs.stonybrook.edu> wrote:
I'm confused as to why any(pred for x in s) is unacceptable here?
all(x > y for x in s) seems to me both idiomatic and correct. I'm not sure quite what you're proposing here - it seems like you're asking for new syntax to do the same job as any and all, which already do exactly what's needed. New syntax has to provide something much, much better if it's likely to be accepted. Please explain more clearly. Paul.
Hi! For those two simplest examples, yes, "any" and "all" can be used. However, there are two general problems. 1. The order of coding using "any/all" is the opposite order of thinking in one's head. In our experience, those kinds of simple examples are coded much more often using "len" than "any/all". The ordering problem gets worse when quantifications are needed in more complex conditions or are nested. 2. The much worse problem is when a witness is needed from existential quantification. In my last/third example from a distributed algorithm, this is the desired code (recall that ! indicates a bound variable): while some (!slot_num,p1) in decisions: if some (!slot_num,p2) in proposals has p2 != p1: propose(p2) perform(p1) "any" is not sufficient to code this easily and clearly. Such witnesses are needed in all worklist algorithms. Thanks, Annie
On 14 January 2012 13:57, Annie Liu <liu@cs.stonybrook.edu> wrote:
To be honest, that's a matter of opinion. I find any/all with a generator expression more readable than your syntax, because I am used to generator expressions as they are common in Python.
Wow, I find that unreadable!. The ! doesn't read as any sort of assignment to me. Don't forget that in Python, assignments are statements and don't get embedded in expressions. There is no way you're going to get new syntax that creates an expression which embeds a hidden assignment accepted into Python. I'd offer to re write this in idiomatic Python, but looking at it closer, I've no idea how to. I don't know what slot_num is meant to be, at first I thought p1 and p2 were predicates, but then I notice you are comparing them later. 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 :-) Paul.
On Sat, Jan 14, 2012 at 8:19 AM, Paul Moore <p.f.moore@gmail.com> wrote:
On 14 January 2012 13:57, Annie Liu <liu@cs.stonybrook.edu> wrote:
Hi Annie! (*)
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.
I think she's well aware of that, and proposing to change it. :-) There is no way
you're going to get new syntax that creates an expression which embeds a hidden assignment accepted into Python.
That's your opinion. But this is python-ideas. :-) I'd offer to re write this in idiomatic Python, but looking at it
Actually she gave one in her first post. Here it is again: 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. 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: 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> 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. 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). __________ (*) See http://neopythonic.blogspot.com/2011/06/depth-and-breadth-of-python.html -- --Guido van Rossum (python.org/~guido)
On 14 January 2012 19:24, Guido van Rossum <guido@python.org> wrote:
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.
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.
Agreed, that's inefficient, and it also violates DRY - I can easily imagine those two lines getting out of sync after a while...
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.
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.
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
One day, I really must read up on ABC. Paul.
On Sat, Jan 14, 2012 at 1:38 PM, Paul Moore <p.f.moore@gmail.com> wrote:
Actually it's worse. neither expression needs to compute the full set -- they only need to iterate until the first match.
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...
Yeah, and it also avoids computing the elements of the set beyond the first.
And thanks for the link with logic languages, that's an area I know even less about...
I'm not sure we need a new construct for tuple matching. Witness capturing seems the most important missing feature here.
Eew. :-(
Just follow the above link and scroll to the top. :-) -- --Guido van Rossum (python.org/~guido)
On 14 January 2012 23:07, Guido van Rossum <guido@python.org> wrote:
Agreed. Assignment-as-expression is nicer. But I have to say I've never really missed it in Python until this discussion started. Question. Do you object to assignment-as-expression per se, or merely as the default way of looking at assignment? Or to put it another way, would something like my x := val (or maybe x <- val or something else) be acceptable? Paul.
On Sun, Jan 15, 2012 at 9:27 AM, Paul Moore <p.f.moore@gmail.com> wrote:
Just to make sure I have the example right, I believe this is what the original example looks like without using comprehensions at all: for dec_slot, p1 in decisions: if dec_slot == slot_num: for prop_slot, p2 in proposals: if prop_slot == slot_num and p2 != p1: # Do something! You can merge the for loops and the if statements, and hence avoid the naming conflict for the slot variables with a couple of generator expressions (there's apparently no need to waste memory realising the set for this example). You can also trivially adopt a mathematics style ordering for any() and all() by using "True" as the body and moving the predicate to the comprehension's if clause. That means, the example can already be written as: 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! The tricks are: 1. Use generator expressions in order to get at the values as they're produced, rather than realising the sets in memory 2. Use a for loop instead of a while loop in order to capture those values 3. Use "True" with any()/all() to get a mathematical style quantification ordering of expressions Cheers, Nick. P.S. My reply appears in this part of the thread because it started out as a reference to my previous suite expressions concept [1] that supports embedded assignment statements in a way that allows the value saved and the value used as a predicate to differ. As I wrote it up though, I realised that the specific example given could be translated fairly neatly into *existing* Python constructs, as shown above. [1] http://ncoghlan_devs-python-notes.readthedocs.org/en/latest/pep_ideas/suite_... -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 15 January 2012 02:27, Nick Coghlan <ncoghlan@gmail.com> wrote:
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. 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. Paul.
Guido van Rossum wrote:
If I recall correctly, there have been occasional discussions about changing any() and all() to return the item found rather than a flag. Given the need for backwards compatibility, I don't think we can or should do this, but a hypothetical quant module, or a few new built-ins, could possibly help here. I'm not sure that quantifications are quite important enough to justify new syntax. For lack of better names: def all2(iterable, pred=bool): """Like all(pred(obj) for obj in iterable), returning True if it is true, otherwise obj, the first witness that it false. """ for obj in iterable: if not pred(obj): return obj return True def any2(iterable, pred=bool): """Like any(pred(x) for x in iterable), returning False if it is false, otherwise obj, the first witness that it is true. """ for obj in iterable: if pred(obj): return obj # I look forward to the bike-shedding about returning None # vs returning False ;) return False One disadvantage of returning a single value to represent both the success or failure of the quantification *and* the witness is that it leaves the caller vulnerable to this sort of bug: py> witness = any2([3, 0, 2, 4], lambda n: n%2==0) # get first even number py> if witness: ... print("first even number is,", witness) ... else: ... print("everything is odd") ... everything is odd I don't have a good solution for this. -- Steven
On Sun, Jan 15, 2012 at 12:01 PM, Steven D'Aprano <steve@pearwood.info> wrote:
The way around it is to always return a tuple: empty if no answer was found, a singleton-tuple if it was. That way truth-testing will always give the right found/not-found answer, but in the found case you can access the original object. def any2(iterable, pred=bool): """Like any(pred(x) for x in iterable), but returns () if nothing matches the predicate, otherwise (obj,), a singleton-tuple holding the first value that matched it. """ for obj in iterable: if pred(obj): return (obj,) return () py> found = any2([3, 0, 2, 4], lambda n: n%2==0) # get first even number py> if found: ... print("first even number is,", found[0]) ... else: ... print("everything is odd") ... first even number is 0 Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
Le 15/01/2012 03:01, Steven D'Aprano a écrit :
Hi, If the point is to get some value that matches a predicate, how about this? next(value for value in iterable if predicate(value)) If a "no value" marker is desired instead of StopIteration: next((value for value in iterable if predicate(value)), None) But yes, assignment-expression is still required to avoid the while True/if/break dance. Regards, -- Simon Sapin
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. :-)
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".
Right! Thank you!
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.
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
On 15 January 2012 17:01, Annie Liu <liu@cs.stonybrook.edu> wrote:
Hmm, while I'm coming to like the concept, I still think that "clearer" might be a bit strong. For simple uses where all() and any() work as replacements, those builtins are already pretty clear. For cases where they won't do, then quantifiers as you propose are certainly no worse than some of the other proposed alternatives, but I'm not sure how much better they are, either. But never mind, clarity is a matter of perspective at best :-)
Yes, I see your point here - in this case "while some x in s" reads nicely, and does what I'd expect.
OK, I'm willing to concede that the all/any formulation isn't as "clean looking" as the alternatives you propose. But I did understand it instantly, whereas I found that I couldn't work out the meaning of your form straight off, but had to "cheat" by looking at the all/any formulation, and work back from that. How much of that is simply because I'm more familiar with the conventional form, I'm not sure (it's certainly a reasonably substantial part of it - and if each/some become part of the language, they will become familiar too). But what I want to do is break things down into individual constructs - that's how my mind works (so sue me! :-)) With the all/any form, it goes: all(...) - function call, with a generator expression as argument ... for x in s - generator expression, argument to all any(...) - function call again pred for y in t - generator expression So we have 2 fundamental constructs, both used in many contexts throughout Python, and hence both familiar, combined in simple ways. For your each/some formulation we have: each x in s has ... - a new type of construct, and each expression some y in t has pred - another new type of construct, a some expression each and some expressions feel like they have structure in common with generator expressions, but they look slightly different. Actually, isn't it true that "each x in s has pred" is basically "all(x for x in s if pred)" except that no witness is captured? So syntactically the differences are: - you avoid the repetition of "x for x" (which is a known wart of generator expressions) - you're using has instead of if (it reads better, but otherwise is a bit of a spurious difference - you did propose if as an alternative) - you avoid the parentheses There are some subtler differences (you use "pred for x..." in the all/any version, whereas I'm equating each/some forms with "x for x" variations, for example). But basically this is my real concern - your proposed constructs are special case syntax that is close to, but subtly different from, existing forms. That "nearly but not quite the same" aspect is where I have concerns about readability (and teachability). The problem is that each/some can't build on generators, because if they do you need to explicitly specify the variable to use to capture the witness. And then if you use a generator expression, you end up with something like "some VAR GENERATOR", which becomes a monstrosity like "some x (x for x in ...)". So they have to build on generator *expressions* which are a subset of general generators. And we get to special case synax straight off. The advantage of any/all is that they work on any generator - whether it's a generator expression or some other form of generator).
In summary, again, I think we should support proper quantifications.
I'm getting more comfortable with the idea, but I think it needs a bit more discussion to come up with something that fits in cleanly with the rest of Python, while still adding the value you want. Paul.
On Mon, Jan 16, 2012 at 5:46 AM, Paul Moore <p.f.moore@gmail.com> wrote:
Indeed. With the clarification that my original "long form" expansion was incorrect (since it only looped over the outer set once), I'll put forward a slightly shorter variant of Guido's expansion (as someone else already noted, next() can be a useful alternative to pop() if you aren't keeping the original set around) _sentinel = object() while True: p1 = next((p for (s0,p1) in decisions if s0==slot_num), _sentinel) if p1 is _sentinel: break for p2 in {p2 for (s0,p2) in proposals if s0==slot_num and p2 != p1}: ... So, let's consider this proposal: "some VAR in ITERABLE if COND" would be an expression that: 1. *deliberately* leaks the variable into the surrounding scope (embedded assignment ahoy) 2. Defines the expression value roughly as follows: _itr = (VAR for VAR in ITERABLE if COND) # i.e. it's an implicit generator expression try: VAR = next(_itr) except StopIteration: _expr_result = False else: _expr_result = True And, further suppose, that we finally cave on allowing a filter clause in for statements Then Annie's original example would look like this: while some s0, p1 in decisions if s0==slot_num: for s0, p2 in proposals if s0==slot_num and p2 != p1: ... And, since we *know* anything even vaguely resembling an embedded assignment syntax would almost immediately be adopted for any-and-all of the various embedded assignment requests we've seen over the years, here's how it would look for the regex use case: if some m in [pattern.search(data)] if m is not None: ... Hmm, still doesn't feel right to me - trying to shove a square peg (mathematical quantification) into a round hole (Python's syntax). In particular, the any()/all() way of doing things avoids the double-if problem when used in an if statement, whereas the version that captures the variable (and hence moves the predicate to the end) reads very strangely in that case. Removing the if clause doesn't help, since you can easily add it back by using a generator expression as your iterable. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Mon, Jan 16, 2012 at 9:15 AM, Nick Coghlan <ncoghlan@gmail.com> wrote:
You can always add a full-on assignment-as-expression, if you're concerned about that. if (m := pat.search(data)) is not None: Also, the keyword doesn't have to be "if". I've always read the bar as "such that" or "where". -- Devin
On Tue, Jan 17, 2012 at 3:39 PM, Ethan Furman <ethan@stoneleaf.us> wrote:
Assignments as expressions aren't all that easy to use in the "some" case that started the thread, and the reason is the same as the reason iteration variables in comprehensions don't leak into the surrounding scope any more: generator expressions and comprehensions create their own scope, separate from that of the containing function. If Python ever did get assignment expressions, the most likely candidate would actually be based on the existing use of "as" for naming (or renaming) things: if (pat.search(data) as m) is not None: ... while (next(p1 for (s0, p1) in decisions if s0==slot_num, None) as p1) is not None: ... However, assignments as expressions are still a long way from being shown to ever improve clarity enough to be worth the additional language complexity. Getting back specifically to the quantification question, I wonder if being able to explicitly export an iteration variable from a comprehension might work: while any(s0 == slot_num for (s0, some p1) in decisions): ... Abusing it for embedded assignments is still ugly, but at least vaguely comprehensible once you're familiar with the meaning of 'some': if any(m is not None for some m in [pattern.search(data)]): ... (As far as how that could actually work goes, with the bindings limited to simple names, as they are for iteration variables, you could probably just make the relevant mapping available inside the comprehension for class and module namespaces and make use of the nonlocal machinery for function namespaces) I still can't honestly say I like the idea, but I at least dislike it less than anything else I've seen in the thread so far :) Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 17 January 2012 11:16, Nick Coghlan <ncoghlan@gmail.com> wrote:
Ah. I tested the idea by setting an attribute of an existing object, which *does* work (but is ugly). I'd forgotten that scoping comes into the picture when you switch to assignment. I'll refrain from proposing "nonlocal x := var"... :-) Paul.
On Tue, Jan 17, 2012 at 11:34 PM, Paul Moore <p.f.moore@gmail.com> wrote:
I'll refrain from proposing "nonlocal x := var"... :-)
That idea (or rather the "(var as nonlocal x)" equivalent) was actually the starting point for my train of thought that led to the suggestion of just using "some" as a marker for iteration variable export :) Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Sun, Jan 15, 2012 at 12:01 PM, Annie Liu <liu@cs.stonybrook.edu> wrote:
I hadn't been _really_ paying attention, [no active reading] but the "if" had confused me until I read this -- I didn't know what it meant. I'm so much more used to "|" and "s.t. (such that)". If reads like implication, which is something else. Of course, the same complaint applies to list comprehensions, so I expect I'll get used to it, but... with list comprehensions it seemed obvious because it replaced an idiom that literally used the if statement. Is the same true here? -- Devin
On Sat, Jan 14, 2012 at 9:01 PM, Steven D'Aprano <steve@pearwood.info> wrote:
On Sat, Jan 14, 2012 at 1:38 PM, Paul Moore <p.f.moore@gmail.com> wrote:
Capturing a (quantification) "witness", which can be done using assignment-as-expression
If I recall correctly, there have been occasional discussions about changing any() and all() to return the item found rather than a flag.
Even in this thread, there have been multiple posts that would shown bugs when the witness itself had a boolean evaluation of False. What if any and all started to return a Witness object that evaluated to True/False, but made the value available? I could see an object like this being useful in other code as well. class Witness(object): def __bool__(self): return self.truth def __init__(self, truth, value): self.truth=truth self.value=value Of course, it might be nicer to inherit from type(True), and it still doesn't quite solve the laziness problem with for, or the assign-in-the-right-place problem with while. -jJ
Hi! For those two simplest examples, yes, "any" and "all" can be used. However, there are two general problems. 1. The order of coding using "any/all" is the opposite order of thinking in one's head. In our experience, those kinds of simple examples are coded much more often using "len" than "any/all". The ordering problem gets worse when quantifications are needed in more complex conditions or are nested. 2. The much worse problem is when a witness is needed from existential quantification. In my last/third example from a distributed algorithm, this is the desired code (recall that ! indicates a bound variable): while some (!slot_num,p1) in decisions: if some (!slot_num,p2) in proposals has p2 != p1: propose(p2) perform(p1) "any" is not sufficient to code this easily and clearly. Such witnesses are needed in all worklist algorithms. Thanks, Annie
On 14 January 2012 13:57, Annie Liu <liu@cs.stonybrook.edu> wrote:
To be honest, that's a matter of opinion. I find any/all with a generator expression more readable than your syntax, because I am used to generator expressions as they are common in Python.
Wow, I find that unreadable!. The ! doesn't read as any sort of assignment to me. Don't forget that in Python, assignments are statements and don't get embedded in expressions. There is no way you're going to get new syntax that creates an expression which embeds a hidden assignment accepted into Python. I'd offer to re write this in idiomatic Python, but looking at it closer, I've no idea how to. I don't know what slot_num is meant to be, at first I thought p1 and p2 were predicates, but then I notice you are comparing them later. 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 :-) Paul.
On Sat, Jan 14, 2012 at 8:19 AM, Paul Moore <p.f.moore@gmail.com> wrote:
On 14 January 2012 13:57, Annie Liu <liu@cs.stonybrook.edu> wrote:
Hi Annie! (*)
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.
I think she's well aware of that, and proposing to change it. :-) There is no way
you're going to get new syntax that creates an expression which embeds a hidden assignment accepted into Python.
That's your opinion. But this is python-ideas. :-) I'd offer to re write this in idiomatic Python, but looking at it
Actually she gave one in her first post. Here it is again: 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. 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: 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> 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. 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). __________ (*) See http://neopythonic.blogspot.com/2011/06/depth-and-breadth-of-python.html -- --Guido van Rossum (python.org/~guido)
On 14 January 2012 19:24, Guido van Rossum <guido@python.org> wrote:
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.
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.
Agreed, that's inefficient, and it also violates DRY - I can easily imagine those two lines getting out of sync after a while...
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.
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.
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
One day, I really must read up on ABC. Paul.
On Sat, Jan 14, 2012 at 1:38 PM, Paul Moore <p.f.moore@gmail.com> wrote:
Actually it's worse. neither expression needs to compute the full set -- they only need to iterate until the first match.
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...
Yeah, and it also avoids computing the elements of the set beyond the first.
And thanks for the link with logic languages, that's an area I know even less about...
I'm not sure we need a new construct for tuple matching. Witness capturing seems the most important missing feature here.
Eew. :-(
Just follow the above link and scroll to the top. :-) -- --Guido van Rossum (python.org/~guido)
On 14 January 2012 23:07, Guido van Rossum <guido@python.org> wrote:
Agreed. Assignment-as-expression is nicer. But I have to say I've never really missed it in Python until this discussion started. Question. Do you object to assignment-as-expression per se, or merely as the default way of looking at assignment? Or to put it another way, would something like my x := val (or maybe x <- val or something else) be acceptable? Paul.
On Sun, Jan 15, 2012 at 9:27 AM, Paul Moore <p.f.moore@gmail.com> wrote:
Just to make sure I have the example right, I believe this is what the original example looks like without using comprehensions at all: for dec_slot, p1 in decisions: if dec_slot == slot_num: for prop_slot, p2 in proposals: if prop_slot == slot_num and p2 != p1: # Do something! You can merge the for loops and the if statements, and hence avoid the naming conflict for the slot variables with a couple of generator expressions (there's apparently no need to waste memory realising the set for this example). You can also trivially adopt a mathematics style ordering for any() and all() by using "True" as the body and moving the predicate to the comprehension's if clause. That means, the example can already be written as: 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! The tricks are: 1. Use generator expressions in order to get at the values as they're produced, rather than realising the sets in memory 2. Use a for loop instead of a while loop in order to capture those values 3. Use "True" with any()/all() to get a mathematical style quantification ordering of expressions Cheers, Nick. P.S. My reply appears in this part of the thread because it started out as a reference to my previous suite expressions concept [1] that supports embedded assignment statements in a way that allows the value saved and the value used as a predicate to differ. As I wrote it up though, I realised that the specific example given could be translated fairly neatly into *existing* Python constructs, as shown above. [1] http://ncoghlan_devs-python-notes.readthedocs.org/en/latest/pep_ideas/suite_... -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 15 January 2012 02:27, Nick Coghlan <ncoghlan@gmail.com> wrote:
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. 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. Paul.
Guido van Rossum wrote:
If I recall correctly, there have been occasional discussions about changing any() and all() to return the item found rather than a flag. Given the need for backwards compatibility, I don't think we can or should do this, but a hypothetical quant module, or a few new built-ins, could possibly help here. I'm not sure that quantifications are quite important enough to justify new syntax. For lack of better names: def all2(iterable, pred=bool): """Like all(pred(obj) for obj in iterable), returning True if it is true, otherwise obj, the first witness that it false. """ for obj in iterable: if not pred(obj): return obj return True def any2(iterable, pred=bool): """Like any(pred(x) for x in iterable), returning False if it is false, otherwise obj, the first witness that it is true. """ for obj in iterable: if pred(obj): return obj # I look forward to the bike-shedding about returning None # vs returning False ;) return False One disadvantage of returning a single value to represent both the success or failure of the quantification *and* the witness is that it leaves the caller vulnerable to this sort of bug: py> witness = any2([3, 0, 2, 4], lambda n: n%2==0) # get first even number py> if witness: ... print("first even number is,", witness) ... else: ... print("everything is odd") ... everything is odd I don't have a good solution for this. -- Steven
On Sun, Jan 15, 2012 at 12:01 PM, Steven D'Aprano <steve@pearwood.info> wrote:
The way around it is to always return a tuple: empty if no answer was found, a singleton-tuple if it was. That way truth-testing will always give the right found/not-found answer, but in the found case you can access the original object. def any2(iterable, pred=bool): """Like any(pred(x) for x in iterable), but returns () if nothing matches the predicate, otherwise (obj,), a singleton-tuple holding the first value that matched it. """ for obj in iterable: if pred(obj): return (obj,) return () py> found = any2([3, 0, 2, 4], lambda n: n%2==0) # get first even number py> if found: ... print("first even number is,", found[0]) ... else: ... print("everything is odd") ... first even number is 0 Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
Le 15/01/2012 03:01, Steven D'Aprano a écrit :
Hi, If the point is to get some value that matches a predicate, how about this? next(value for value in iterable if predicate(value)) If a "no value" marker is desired instead of StopIteration: next((value for value in iterable if predicate(value)), None) But yes, assignment-expression is still required to avoid the while True/if/break dance. Regards, -- Simon Sapin
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. :-)
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".
Right! Thank you!
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.
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
On 15 January 2012 17:01, Annie Liu <liu@cs.stonybrook.edu> wrote:
Hmm, while I'm coming to like the concept, I still think that "clearer" might be a bit strong. For simple uses where all() and any() work as replacements, those builtins are already pretty clear. For cases where they won't do, then quantifiers as you propose are certainly no worse than some of the other proposed alternatives, but I'm not sure how much better they are, either. But never mind, clarity is a matter of perspective at best :-)
Yes, I see your point here - in this case "while some x in s" reads nicely, and does what I'd expect.
OK, I'm willing to concede that the all/any formulation isn't as "clean looking" as the alternatives you propose. But I did understand it instantly, whereas I found that I couldn't work out the meaning of your form straight off, but had to "cheat" by looking at the all/any formulation, and work back from that. How much of that is simply because I'm more familiar with the conventional form, I'm not sure (it's certainly a reasonably substantial part of it - and if each/some become part of the language, they will become familiar too). But what I want to do is break things down into individual constructs - that's how my mind works (so sue me! :-)) With the all/any form, it goes: all(...) - function call, with a generator expression as argument ... for x in s - generator expression, argument to all any(...) - function call again pred for y in t - generator expression So we have 2 fundamental constructs, both used in many contexts throughout Python, and hence both familiar, combined in simple ways. For your each/some formulation we have: each x in s has ... - a new type of construct, and each expression some y in t has pred - another new type of construct, a some expression each and some expressions feel like they have structure in common with generator expressions, but they look slightly different. Actually, isn't it true that "each x in s has pred" is basically "all(x for x in s if pred)" except that no witness is captured? So syntactically the differences are: - you avoid the repetition of "x for x" (which is a known wart of generator expressions) - you're using has instead of if (it reads better, but otherwise is a bit of a spurious difference - you did propose if as an alternative) - you avoid the parentheses There are some subtler differences (you use "pred for x..." in the all/any version, whereas I'm equating each/some forms with "x for x" variations, for example). But basically this is my real concern - your proposed constructs are special case syntax that is close to, but subtly different from, existing forms. That "nearly but not quite the same" aspect is where I have concerns about readability (and teachability). The problem is that each/some can't build on generators, because if they do you need to explicitly specify the variable to use to capture the witness. And then if you use a generator expression, you end up with something like "some VAR GENERATOR", which becomes a monstrosity like "some x (x for x in ...)". So they have to build on generator *expressions* which are a subset of general generators. And we get to special case synax straight off. The advantage of any/all is that they work on any generator - whether it's a generator expression or some other form of generator).
In summary, again, I think we should support proper quantifications.
I'm getting more comfortable with the idea, but I think it needs a bit more discussion to come up with something that fits in cleanly with the rest of Python, while still adding the value you want. Paul.
On Mon, Jan 16, 2012 at 5:46 AM, Paul Moore <p.f.moore@gmail.com> wrote:
Indeed. With the clarification that my original "long form" expansion was incorrect (since it only looped over the outer set once), I'll put forward a slightly shorter variant of Guido's expansion (as someone else already noted, next() can be a useful alternative to pop() if you aren't keeping the original set around) _sentinel = object() while True: p1 = next((p for (s0,p1) in decisions if s0==slot_num), _sentinel) if p1 is _sentinel: break for p2 in {p2 for (s0,p2) in proposals if s0==slot_num and p2 != p1}: ... So, let's consider this proposal: "some VAR in ITERABLE if COND" would be an expression that: 1. *deliberately* leaks the variable into the surrounding scope (embedded assignment ahoy) 2. Defines the expression value roughly as follows: _itr = (VAR for VAR in ITERABLE if COND) # i.e. it's an implicit generator expression try: VAR = next(_itr) except StopIteration: _expr_result = False else: _expr_result = True And, further suppose, that we finally cave on allowing a filter clause in for statements Then Annie's original example would look like this: while some s0, p1 in decisions if s0==slot_num: for s0, p2 in proposals if s0==slot_num and p2 != p1: ... And, since we *know* anything even vaguely resembling an embedded assignment syntax would almost immediately be adopted for any-and-all of the various embedded assignment requests we've seen over the years, here's how it would look for the regex use case: if some m in [pattern.search(data)] if m is not None: ... Hmm, still doesn't feel right to me - trying to shove a square peg (mathematical quantification) into a round hole (Python's syntax). In particular, the any()/all() way of doing things avoids the double-if problem when used in an if statement, whereas the version that captures the variable (and hence moves the predicate to the end) reads very strangely in that case. Removing the if clause doesn't help, since you can easily add it back by using a generator expression as your iterable. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Mon, Jan 16, 2012 at 9:15 AM, Nick Coghlan <ncoghlan@gmail.com> wrote:
You can always add a full-on assignment-as-expression, if you're concerned about that. if (m := pat.search(data)) is not None: Also, the keyword doesn't have to be "if". I've always read the bar as "such that" or "where". -- Devin
On Tue, Jan 17, 2012 at 3:39 PM, Ethan Furman <ethan@stoneleaf.us> wrote:
Assignments as expressions aren't all that easy to use in the "some" case that started the thread, and the reason is the same as the reason iteration variables in comprehensions don't leak into the surrounding scope any more: generator expressions and comprehensions create their own scope, separate from that of the containing function. If Python ever did get assignment expressions, the most likely candidate would actually be based on the existing use of "as" for naming (or renaming) things: if (pat.search(data) as m) is not None: ... while (next(p1 for (s0, p1) in decisions if s0==slot_num, None) as p1) is not None: ... However, assignments as expressions are still a long way from being shown to ever improve clarity enough to be worth the additional language complexity. Getting back specifically to the quantification question, I wonder if being able to explicitly export an iteration variable from a comprehension might work: while any(s0 == slot_num for (s0, some p1) in decisions): ... Abusing it for embedded assignments is still ugly, but at least vaguely comprehensible once you're familiar with the meaning of 'some': if any(m is not None for some m in [pattern.search(data)]): ... (As far as how that could actually work goes, with the bindings limited to simple names, as they are for iteration variables, you could probably just make the relevant mapping available inside the comprehension for class and module namespaces and make use of the nonlocal machinery for function namespaces) I still can't honestly say I like the idea, but I at least dislike it less than anything else I've seen in the thread so far :) Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On 17 January 2012 11:16, Nick Coghlan <ncoghlan@gmail.com> wrote:
Ah. I tested the idea by setting an attribute of an existing object, which *does* work (but is ugly). I'd forgotten that scoping comes into the picture when you switch to assignment. I'll refrain from proposing "nonlocal x := var"... :-) Paul.
On Tue, Jan 17, 2012 at 11:34 PM, Paul Moore <p.f.moore@gmail.com> wrote:
I'll refrain from proposing "nonlocal x := var"... :-)
That idea (or rather the "(var as nonlocal x)" equivalent) was actually the starting point for my train of thought that led to the suggestion of just using "some" as a marker for iteration variable export :) Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Sun, Jan 15, 2012 at 12:01 PM, Annie Liu <liu@cs.stonybrook.edu> wrote:
I hadn't been _really_ paying attention, [no active reading] but the "if" had confused me until I read this -- I didn't know what it meant. I'm so much more used to "|" and "s.t. (such that)". If reads like implication, which is something else. Of course, the same complaint applies to list comprehensions, so I expect I'll get used to it, but... with list comprehensions it seemed obvious because it replaced an idiom that literally used the if statement. Is the same true here? -- Devin
On Sat, Jan 14, 2012 at 9:01 PM, Steven D'Aprano <steve@pearwood.info> wrote:
On Sat, Jan 14, 2012 at 1:38 PM, Paul Moore <p.f.moore@gmail.com> wrote:
Capturing a (quantification) "witness", which can be done using assignment-as-expression
If I recall correctly, there have been occasional discussions about changing any() and all() to return the item found rather than a flag.
Even in this thread, there have been multiple posts that would shown bugs when the witness itself had a boolean evaluation of False. What if any and all started to return a Witness object that evaluated to True/False, but made the value available? I could see an object like this being useful in other code as well. class Witness(object): def __bool__(self): return self.truth def __init__(self, truth, value): self.truth=truth self.value=value Of course, it might be nicer to inherit from type(True), and it still doesn't quite solve the laziness problem with for, or the assign-in-the-right-place problem with while. -jJ
participants (10)
-
Annie Liu -
Devin Jeanpierre -
Ethan Furman -
Guido van Rossum -
Jim Jewett -
MRAB -
Nick Coghlan -
Paul Moore -
Simon Sapin -
Steven D'Aprano