Re: [Python-checkins] python/dist/src/Python bltinmodule.c, 2.292.10.1, 2.292.10.2
I think this ought to be reverted, both in 2.3 and 2.4. Consider this code: empty = [] for i in range(10): print sum([[x] for x in range(i)], empty) The output used to be: [] [0] [0, 1] [0, 1, 2] [0, 1, 2, 3] [0, 1, 2, 3, 4] [0, 1, 2, 3, 4, 5] [0, 1, 2, 3, 4, 5, 6] [0, 1, 2, 3, 4, 5, 6, 7] [0, 1, 2, 3, 4, 5, 6, 7, 8] But now it is: [] [0] [0, 0, 1] [0, 0, 1, 0, 1, 2] [0, 0, 1, 0, 1, 2, 0, 1, 2, 3] [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4] [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5] [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6] [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7] [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8] --Guido van Rossum (home page: http://www.python.org/~guido/)
On Saturday 25 October 2003 11:18 pm, Guido van Rossum wrote:
I have reverted it; it's obviously true that, by causing side effects on the 2nd argument, the fix as I had commited it could change semantics. I apologize for not thinking of this (and adding the missing unit-tests to catch this, see next paragraph). If it was up to me I would still pursue the possibility of using PyNumber_InPlaceAdd, for example by only doing so if the second argument could first be successfully copy.copy'ed into the result and falling back to PyNumber_Add otherwise. The alternative of leaving sum as a performance trap for the unwary -- an "attractive nuisance" in legal terms -- would appear to me to be such a bad situation, as to warrant such effort (including adding unit-tests to ensure sum does not alter its second argument, works correctly with a non-copyable 2nd argument, etc). However, it's YOUR decision, and you have already made it clear in another mail that your objections to remedying this performance bug are such that no possible solution will satisfy them. If a type gives different results for "a = a + b" vs "a += b", there is no way sum can find this out; and while, were it my decision, I would not care to support such weird cases at such a huge performance price, it's not my decision. Similarly for types which let you do "a = copy.copy(b)" but do NOT return a valid copy of b, or return b itself even though it's mutable, and so on weirdly. I'm just very sad that I didn't think of this performance-trap back when the specs of sum were first being defined. Oh well:-(. Can I at least add a warning about this performance trap to the docs at http://www.python.org/doc/current/lib/built-in-funcs.html ? Alex
Oh, but we all *did* think of it. For strings. :-)
Definitely. You know, I don't even think that I would consider using sum() if I wanted to concatenate a bunch of lists. Let's use sum() for numbers. Big deal. --Guido van Rossum (home page: http://www.python.org/~guido/)
On Sunday 26 October 2003 04:26, Guido van Rossum wrote: ...
Yeah, and your decision to forbid them (while my first prototype tried forwarding to ''.join) simplified sum's implementation a lot. Unfortunately we cannot easily distinguish numbers from sequences in the general case, when user-coded classes are in play; so we can't easily forbid sequences and allow numbers. Exactly the same underlying reason as a bug I just opened on SF: if x is an instance of a class X having __mul__ but not __rmul__, 3*x works (just like x*3) but 3.0*x raises TypeError (with a message that shows the problem -- x is being taken as a sequence). When X is intended as a number class, this asymmetry between multiplication and (e.g.) addition violates the principle of least surprise.
Currently the docs say that sum is mostly meant for numbers. By making that observation into a stronger warning, we can at least be somewhat helpful to those few Python users who read the manuals;-). If sum just couldn't be used for a list of lists it would indeed not be a big problem. The problem is that it can, it's just (unexpectedly for the naive user) dog-slow, just like a loop of += on a list of strings. And people WILL and DO consider and try and practice _any_ use for a language or library feature. The problem of the += loop on strings is essentially solved by psyco, which has tricks to catch that and make it almost as fast as ''.join; but psyco can't get into a built-in function such as sum, and thus can't help us with the performance trap there. As you've indicated that for 2.4 the risk of semantics changes to sum in weird cases _can_ be at least considered (you're still opposed but open to perhaps being convinced) I hope to get something for that (with a copy.copy of the "accumulator" and in-place addition if that succeeds, falling back to plain addition otherwise) and all the unit tests needed to show it makes sense. An aside...: One common subtheme of this and other recent threads here and on c.l.py is that, as we think of "accumulator functions" to consume iterators, we should not ignore the mutating methods (typically returning None) that are NOT appropriate for list comprehensions just as they weren't for map and friends. A substantial minority of intermediate Python users, knowing or feeling that loops coded in Python aren't as fast as those that happen inside C-coded funcs such as sum, those in itertools, etc, is NOT enthusiastic about coding e.g. "for x in stuff: tot += x". Most often their performance focus is of course inappropriate, but it's hard to uproot it. So, in a typical example, we might have: L = [ [x] for x in xrange(1000) ] def aloop(L=L): tot = [] for x in L: tot += x return tot def asum(L=L): return sum(L, []) def amap(L=L): tot = [] map(tot.extend, L) return tot With the now-regressed fix, this gave: [alex@lancelot bo]$ timeit.py -c -s'import d' 'd.aloop()' 1000 loops, best of 3: 640 usec per loop [alex@lancelot bo]$ timeit.py -c -s'import d' 'd.asum()' 1000 loops, best of 3: 480 usec per loop [alex@lancelot bo]$ timeit.py -c -s'import d' 'd.amap()' 1000 loops, best of 3: 790 usec per loop so sum could be touted as "the only obvious solution" -- shortest, neatest, fastest... IF it were indeed fast!-) Unfortunately, with the sum change regressed, d.asum times to 8.4e+03 usec per loop, so it clearly cannot be considered any more:-). So, there might be space for an accumulator function patterned on map but [a] which stops on the shortest sequence like zip and [b] does NOT build a list of results, meant to be called a bit like map is in the 'amap' example above. itertools is a great little collection of producers and manipulators of iterators, but the "accumulator functions" might provide the "one obvious way" to _consume_ iterators for common cases; and accumulating by calling an accumulator-object's mutator method, such as tot.extend above, on all items of an iterator, clearly is pretty common. Alex
Alex Martelli <aleaxit@yahoo.com> writes:
I *think* I see what you're getting at here, but I'm struggling to follow in the absence of concrete use cases. As we're talking about library functions, I'd suggest that your suggested "accumulator functions" start their life as an external module - maybe even in Python, although I take our point about the speed advantages of C. With a bit of "real life" use, migration into the standard library might be more of an obvious step. Paul. -- This signature intentionally left blank
On Sunday 26 October 2003 05:21 pm, Paul Moore wrote: ...
I *think* I see what you're getting at here, but I'm struggling to follow in the absence of concrete use cases. As we're talking about
Assuming the simplest definition, equivalent to: def loop(bound_method, it): for item in it: bound_method(item) typical simple use cases might be, e.g.: Merge a stream of dictionaries into one dict: merged_dict = {} loop(merged_dict.update, stream_of_dictionaries) rather than: merged_dict = {} for d in stream_of_dictionaries: merged_dict.update(d) Add a bunch of sequences into one list: all_the_seqs = [] loop(all_the_seqs.extend, bunch_of_seqs) rather than: all_the_seqs = [] for s in bunch_of_seqs: all_the_seqs.extend(s) Add two copies of each of a bunch of sequences ditto: all_the_seqs = [] loop(all_the_seqs.extend, s+s for s in bunch_of_seqs) ditto but only for sequences which have 23 somewhere in them: seqs_with_23 = [] loop(seqs_with_23.extend, s for s in bunch_of_seqs in 23 in s) and so on. There are no doubt possibly more elegant ways, e.g. def init_and_loop(initvalue, unboundmethod, it, *its): for items in itertools.izip(it, *its): unboundmethod(initvalue, *items) return initvalue which would allow, e.g., merged_dict = init_and_loop({}, dict.update, stream_of_dictionaries) or other variants yet, but the use cases are roughly the same. The gain of such tiny "accumulator functions" (consuming one or more iterators by just passing their items to some mutating-method and ignoring the latter's results) are essentially conceptual -- it's not a matter of saving a couple of lines at the point of use, nor of saving some "bananoseconds" if the accumulator functions are implemented in C, when compared to the coded-out loops. Rather, such functions would allow "more declarative style" presentation (of underlying functionality that remains imperative): expressions feel more "declarative", stylistically, to some, while spelling a few steps out feels more "imperative". We've had this preference explained recently on this group, and others over in c.l.py are breaking over the champagne at the news of list.sorted for essentially the same motivation.
Absolutely. It's not _my_ suggestion to have more accumulator functions -- it came up repeatedly on the threads started by Peter Norvig original proposal about accumulation, and Guido mentioned them in the 'product' thread I believe (where we also discussed 'any', 'all' etc, if I recall correctly). I don't think anybody's ever thought of making these built-ins. But if that external module[s] (one or more) is/are not part of the Python 2.4 library, if 2.4 does not come with a selection of accumulation functions [not necessarily including that 'loop' &c above mentioned, though I think something like that might help], I don't think we can have the "accumulation functionality" -- we only have great ways to make and express iterators but not many great ways to _consume_ them (and most particularly if sum, one of the few "good iterator consumers" we have, is practically unusable for iterators whose items are lists..).
With a bit of "real life" use, migration into the standard library might be more of an obvious step.
You could have said the same of itertools before 2.3, but I think it was a great decision to accept them into the standard library instead; 2.3 would be substantially poorer without them. With an even richer complement of iterator tools in itertools, and the new "generator expressions" to give us even more great ways to make iterators, I think a module of "iterator consumers", also known as accumulation functions, would be a good idea. Look at Peter Norvig's original ideas for some suggestions, for example. Which reminds me of an issue with Top(10), but, this is a long enough post, so I think I should write a separate one about that. Alex
Alex Martelli <aleaxit@yahoo.com> writes:
[...]
and so on.
None of which are, to me, particularly convincing. Then again, while I like a "declarative style" in some cases, I've got nothing against the sort of "idiom-based" style in which short code patterns just "mean something" as a whole, and aren't viewed as being comprised of their individual parts (much like the standard C idiom for walking a linked list).
OK. I'd bow out here, as I don't feel the need to push the declarative style that extra step. Let others champion the style.
I'm sorry - I'd got the impression that you were arguing the case. In which case, I'd have to say that I'm not at all clear who it is who's proposing anything here, or what specifically the proposals are. I suspect the original intention is getting lost in generalities, and it's time for those original posters to speak up and clarify exactly what they want. Maybe a PEP is in order, to get back to the core of the proposal.
Agreed. I was very conscious of itertools when I made that statement. But my gut feel is that in this case, there has been so much discussion that the key concept has been obscured. A PEP, or some prior art, would recapture that.
In principle, I don't have a problem with that. Let's get concrete, though, and see either a PEP or some code. Otherwise, the discussion isn't really going anywhere. And on that note, I really ought to bow out :-) Paul. -- This signature intentionally left blank
Hello, On Sun, Oct 26, 2003 at 11:09:56AM +0100, Alex Martelli wrote:
Oh, but we all *did* think of it. For strings. :-)
I must admit I was a bit surprized when I first tested sum(), without first reading its doc because I thought I knew what it should do. I expected it to be a fast equivalent to: def sum(seq, start=0): for item in seq: start = start + seq return start or: reduce(operator.add, seq, start) I immediately tried it with strings and lists. I immediately thought about lists because of their use of "+" for concatenation. So it seems that neither strings nor lists are properly supported, neither tuples by the way, and my opinion on this is that it strongly contradicts the principle of least surprize. I would not object to an implementation of sum() that special-case lists, tuples and strings for efficiency. (by which I mean I can contribute a patch)
Supporing sum() in Psyco is no big issue, and it could help the same way as it does for str.__add__. (It is not explicitely supported yet, but it could be added.) Still I believe that getting the complexity right in CPython is important, when it can be done. Armin
On Sunday 26 October 2003 05:23 pm, Armin Rigo wrote: ...
It IS equivalent to that -- plus an explicit typetest to raise if start is an instance of str or unicode. I had originally tried forwarding to ''.join for strings, but Guido preferred to forbid them, and it still doesn't look like a problem to me. Alas, "fast" is debatable:-).
reduce(operator.add, seq, start)
sum doesn't reproduce reduce's quirk of using the first item of seq if start is not given. So, the def version is closer.
Strings are explicitly disallowed, so that should take care of the surprise factor for that specific case. As for lists, the semantics are right, the speed is not (could be made way faster with modest effort). Same for other mutable sequences. As for tuples and other immutable sequences, they ARE treated exactly like your 'def' above (roughly like your reduce) would treat them -- not very fast, but if all you know about something is that it's an immutable sequence, there's nothing more you can do. The use case of making a huge tuple from many smaller ones seems weird enough that I don't see specialcasing tuples specifically as particularly worthwhile (other immutable sequences that aren't exactly tuples would still suffer, after all).
tuples by the way, and my opinion on this is that it strongly contradicts the principle of least surprize.
For mutable sequences, I agree. For immutable ones, I don't see the performance trap as being a practical problem for tuples (and weirder things) -- it WOULD be for strings, but as we specifically disallow them with a message reminding the user of ''.join, in practice the problem seems minor. Maybe I'm coming to this with a too-pragmatical stance...?
I think all mutable sequences (that aren't especially weird in their + vs += behavior) might be handled correctly, without specialcasing, roughly as follows (Phillip Eby's idea): def sum(seq, start=0): it = iter(seq) try: result = start + it.next() except StopIteration: return start for item in it: result += item return result my original idea was perhaps a bit goofier, something like: def sum(seq, start=0): try: start = copy.copy(start) except TypeError: for item in seq: start = start + item else: for item in seq: start += item return start Admittedly the latter version may accept a few more cases, e.g. both versions would accept: sum([ range(3), 'foo' ], []) because [] is copyable, []+range(3) is fine, and list.__iadd__ is more permissive than list.__add__; however, the first version would fail on: sum([ 'foo', range(3) ], []) because []+'foo' fails, while the second version would be fine because [] is _still_ copyable and __iadd__ is still permissive:-). So, perhaps, implementing by Phillip's idea would still not reduce the suprise factor enough. Hmmm...
Absolutely -- we can't rely on psyco for everything, particularly not for getting the big-O right as opposed to speeding things up by constant multipliers (in part, for example, because psyco doesn't work on Mac's, which are going to be a HUGE part of Python's installed base...). However, I would be happy to "leave it to psyco" for a sum of a large sequence of tuples or other immutable sequences...:-). I just don't think that people in practice _will_ fall into that performance-trap... Alex
Hello Alex, On Sun, Oct 26, 2003 at 07:20:52PM +0100, Alex Martelli wrote:
Yes, it is what I'm saying: it is what we expect it to be, but there is an exception for no real reason apart from "don't do it like this, buddy, there is a faster version out there". I tend to regard this kind of exceptions as very bad, because if you write a generic algorithm using sum(), even if you don't really see why someone would think about using your algorithm with strings one day, chances are that someone will. Raising a Warning instead of an exception would have had the same result without the generality problem.
I was thinking about: def sum(seq, start=0): return reduce(operator.add, seq, start) which is the same as the previous one.
These cases all show that we have a surprize problem (although probably not a big one). The user will expect sum() to have a clean definition, and because the += one doesn't work, it must be +. To my opinion, sum() should be strictly equivalent to the naive + version and try to optimize common cases under the hood. Admittedly, this is not obvious, because of precisely all these strange mixed type cases which could be user-defined classes with __add__ or __radd__ operators... I'm sure someone will design a class class x: def __add__(self, other): return other so that x() can be used as a trivial starting point for sum() -- and then sum(["abc", "def"], x()) works :-) Armin
Alex Martelli <aleaxit@yahoo.com>:
Seems to me the bug there is not giving X an __rmul__ method and yet expecting y*x to work at all. The fact that it happens to work in some cases is an accident that should not be relied upon. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+
On Monday 27 October 2003 04:22, Greg Ewing wrote:
No, the bug is that it works in some cases where it should fail (and, secondarily, that -- where it does fail -- it gives a weird error message). In other words, the bug (in Python) is that "accident". Nobody's asking for 3.0*x to work where x is a user-coded type without an __rmul__; rather, the point is that 3*x should fail too, and ideally they'd have the same clear error message as 3+x gives when the type has no __radd__. Doesn't seem trivial to fix (though I hope I'm missing something obvious) and doesn't affect perfect user-programs, but I do think it should be fixed because it's sure extremely mysterious and could send a developer on wild goose chases when met in the course of development. Alex
Alex Martelli <aleaxit@yahoo.com>:
Okay, that makes sense. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+
On Tuesday 28 October 2003 01:04 am, Greg Ewing wrote:
So how do you think we should go about it? I can't see a way right now (at least not for 2.3, i.e. without breaking some programs). A user COULD have coded a class that's meant to represent a sequence AND relied on the (undocumented, I think) feature that giving the class a __mul__ automatically makes instances of that class multipliable by integers on EITHER side, after all. We can't (sensibly), I think, distinguish that from the case where the user has coded a class that's meant to represent a number and gets astonished that __mul__, undocumentedly, makes isntances of that class multipliable by integers on either side. So perhaps for 2.3 we should just apologetically note the anomaly in the docs, and for 2.4 forbid the former case, i.e., require both __mul__ AND __rmul__ to exist if one wants to code sequence classes that can be multiplied by integers on either side...? Any opinions, anybody...? Alex
What's wrong with the status quo? So 3*x is undefined, and it happens to return x*3. Is that so bad? --Guido van Rossum (home page: http://www.python.org/~guido/)
On Tuesday 28 October 2003 04:16 pm, Guido van Rossum wrote:
Where is it specified that 3*x "is undefined" when x's type exposes __mul__ but not __rmul__ ? Sorry, I don't understand the viewpoint you seem to imply here. If x's type exposed no __add__ but "it just so happened" that x+23 always returned 12345 -- while every other addition, as expected, failed -- would you doubt the lack of a normal and reasonably expected exception is bad? I think that if Python returns "arbitrary" results, rather than raising an exception, for operations that "should" raise an exception, that is surely very bad -- it makes it that much harder for programmers to debug the programs they're developing. If there's some doubt about the words I've put in hyphens -- that treating x*y just like y*x only for certain values of type(y) isn't arbitrary or shouldn't raise -- then we can of course discuss this, but isn't the general idea correct? Now, the docs currently say, about sequences under http://www.python.org/doc/current/ref/sequence-types.html : """ sequence types should implement ... multiplication (meaning repetition) by defining the methods __mul__(), __rmul__() and __imul__() described below; they should not define __coerce__() or other numerical operators. """ So, a sequence-emulating type that implements __mul__ but not __rmul__ appears to violate that "should". The description of __mul__ and __rmul__ referred to seems to be that at http://www.python.org/doc/current/ref/numeric-types.html . It says that methods corresponding to operations not supported by a particular kind of number should be left undefined (as opposed to the behavior of _attempts at those operations_ being undefined), so if I had a hypothetical number type X such that, for x instance of X and an integer k, x*k should be supported but k*x shouldn't, isn't this a recommendation to not write __rmul__ in X ...? Besides, this weird anomaly is typical of newstyle classes only. Consider:
ALL wonderful, just as expected, hunky-dory. But now, having read that newstyle classes are better, I want to make X newstyle -- can't see any indication in the docs that I shouldn't -- and...:
*eep*! Yes, it DOES seem to be that this is QUITE bad indeed. Alex
You're making a mountain of a molehill here, Alex. I know that in group theory there are non-Abelian groups (for which AB != BA), but I've never encountered one myself in programming; more typical such non-commutative operations are modeled as __add__ rather than as __mul__. Anyway, the real issue AFAICT is not that people depend on __rmul__'s absence to raise a TypeError, but that people learn by example and find __rmul__ isn't necessary by experimenting with integers. The reason why it works at all for integers without __rmul__ is complicated; it has to do with very tricky issues in trying to implement multiplication of a sequence with an integer. That code has gone through a number of iterators, and every time someone eventually found a bug in it, so I'd rather leave the __rmul__ blemish than uproot it again. If you can come up with a fix that doesn't break sequence repetition I'd be open to accepting it (for 2.4 only, in 2.3 there may be too much code depending on the bug) but only after serious review -- and not by me, because I'm not all that familiar with all the subtleties of that code any more. :-( --Guido van Rossum (home page: http://www.python.org/~guido/)
I need to give myself a small slap on the forehead head, because of course non-square matrix multiplication is an excellent example where AB != BA. However even there, Ax == xA when x is a singleton, and the issue only arises for integers, so I still don't think there are use cases. --Guido van Rossum (home page: http://www.python.org/~guido/)
On Tuesday 28 October 2003 07:37 pm, Guido van Rossum wrote:
There may be no "perfectly correct code" that will ever notice 3*x weirdly works. But would that make it acceptable to return 42, rather than raise IndexError, when a list of length exactly 33 is indexed by index 666? That, too, might "have no practical use cases" for perfectly correct code. But programmers make mistakes, and one of Python's strength is that it does NOT (crash, hang, or) return weird wrong results when they do -- most often it raises appropriate exceptions, which make it easy to diagnose and fix one's mistakes. Thus, it troubles me that we can't do it here. I know it's hard to fix (I've stared at that code for QUITE a while...). But "deducing" from that difficulty that the error's not worth fixing seems like a classic case of "sour grapes":-). Alex
I dunno. As language warts go I find this one minuscule, and the effort you spend on rhetoric to convince me a waste of breath. My position is: I understand that it's a wart, I just don't think I know of a good solution, and I can live with the status quo just fine. --Guido van Rossum (home page: http://www.python.org/~guido/)
On Tuesday 28 October 2003 07:28 pm, Guido van Rossum wrote: ...
You're making a mountain of a molehill here, Alex. I know that in
You have a point: when one is in love (and I still _am_ madly in love with Python!-), it's hard to admit of imperfections in the loved one:-). Even a tiny defect...:-).
I don't remember ever coding a __mul__ that I WANTED to be non-commutative, right.
Or more seriously: they write what LOOK like perfectly adequate unit tests, but the numbers they try in "number * x" happen to be ints; so the unit tests pass -- but their code is broken because they forgot the __rmul__ and the unittests-with-ints didn't catch that.
Yes, I think I understand some of that -- I included the analysis of the bug in my bugreport on SF.
I do have one weird idea that might help here (for 2.4), but I'd better post that separately because I suspect it's going to fuel its own long discussion thread. As things are, without an ability to distinguish a sequence from a number securely, and IF sequences must work w/o __rmul__ (but they didn't in classic classes...? and the docs don't indicate that...?) then I'm stumped. Who'd be the right people to review such proposed changes, btw? Alex
Guido van Rossum <guido@python.org>:
I thought the plan was to get rid of all the special case code in the interpreter for multiplying sequences and push it all down into methods of the objects concerned, i.e. all sequences, including the built-in ones, would implement the C equivalent of both __mul__ and __rmul__ if they wanted to support multiplication on both sides. Is there some reason why that wouldn't work? Or is it just that nobody has had time to fix all the built-in sequences to work this way? Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+
It would be a lot of work, and I expect that for 3rd party extension types (and possibly for 3rd party Python classse) it wouldn't be quite compatible. I want it to work this way in Python 3.0, but I don't know if it's worth reworking all that tedious detail in the 2.x series. (Understanding that 3.0 is a few years away still.) --Guido van Rossum (home page: http://www.python.org/~guido/)
On Saturday 25 October 2003 11:18 pm, Guido van Rossum wrote:
I have reverted it; it's obviously true that, by causing side effects on the 2nd argument, the fix as I had commited it could change semantics. I apologize for not thinking of this (and adding the missing unit-tests to catch this, see next paragraph). If it was up to me I would still pursue the possibility of using PyNumber_InPlaceAdd, for example by only doing so if the second argument could first be successfully copy.copy'ed into the result and falling back to PyNumber_Add otherwise. The alternative of leaving sum as a performance trap for the unwary -- an "attractive nuisance" in legal terms -- would appear to me to be such a bad situation, as to warrant such effort (including adding unit-tests to ensure sum does not alter its second argument, works correctly with a non-copyable 2nd argument, etc). However, it's YOUR decision, and you have already made it clear in another mail that your objections to remedying this performance bug are such that no possible solution will satisfy them. If a type gives different results for "a = a + b" vs "a += b", there is no way sum can find this out; and while, were it my decision, I would not care to support such weird cases at such a huge performance price, it's not my decision. Similarly for types which let you do "a = copy.copy(b)" but do NOT return a valid copy of b, or return b itself even though it's mutable, and so on weirdly. I'm just very sad that I didn't think of this performance-trap back when the specs of sum were first being defined. Oh well:-(. Can I at least add a warning about this performance trap to the docs at http://www.python.org/doc/current/lib/built-in-funcs.html ? Alex
Oh, but we all *did* think of it. For strings. :-)
Definitely. You know, I don't even think that I would consider using sum() if I wanted to concatenate a bunch of lists. Let's use sum() for numbers. Big deal. --Guido van Rossum (home page: http://www.python.org/~guido/)
On Sunday 26 October 2003 04:26, Guido van Rossum wrote: ...
Yeah, and your decision to forbid them (while my first prototype tried forwarding to ''.join) simplified sum's implementation a lot. Unfortunately we cannot easily distinguish numbers from sequences in the general case, when user-coded classes are in play; so we can't easily forbid sequences and allow numbers. Exactly the same underlying reason as a bug I just opened on SF: if x is an instance of a class X having __mul__ but not __rmul__, 3*x works (just like x*3) but 3.0*x raises TypeError (with a message that shows the problem -- x is being taken as a sequence). When X is intended as a number class, this asymmetry between multiplication and (e.g.) addition violates the principle of least surprise.
Currently the docs say that sum is mostly meant for numbers. By making that observation into a stronger warning, we can at least be somewhat helpful to those few Python users who read the manuals;-). If sum just couldn't be used for a list of lists it would indeed not be a big problem. The problem is that it can, it's just (unexpectedly for the naive user) dog-slow, just like a loop of += on a list of strings. And people WILL and DO consider and try and practice _any_ use for a language or library feature. The problem of the += loop on strings is essentially solved by psyco, which has tricks to catch that and make it almost as fast as ''.join; but psyco can't get into a built-in function such as sum, and thus can't help us with the performance trap there. As you've indicated that for 2.4 the risk of semantics changes to sum in weird cases _can_ be at least considered (you're still opposed but open to perhaps being convinced) I hope to get something for that (with a copy.copy of the "accumulator" and in-place addition if that succeeds, falling back to plain addition otherwise) and all the unit tests needed to show it makes sense. An aside...: One common subtheme of this and other recent threads here and on c.l.py is that, as we think of "accumulator functions" to consume iterators, we should not ignore the mutating methods (typically returning None) that are NOT appropriate for list comprehensions just as they weren't for map and friends. A substantial minority of intermediate Python users, knowing or feeling that loops coded in Python aren't as fast as those that happen inside C-coded funcs such as sum, those in itertools, etc, is NOT enthusiastic about coding e.g. "for x in stuff: tot += x". Most often their performance focus is of course inappropriate, but it's hard to uproot it. So, in a typical example, we might have: L = [ [x] for x in xrange(1000) ] def aloop(L=L): tot = [] for x in L: tot += x return tot def asum(L=L): return sum(L, []) def amap(L=L): tot = [] map(tot.extend, L) return tot With the now-regressed fix, this gave: [alex@lancelot bo]$ timeit.py -c -s'import d' 'd.aloop()' 1000 loops, best of 3: 640 usec per loop [alex@lancelot bo]$ timeit.py -c -s'import d' 'd.asum()' 1000 loops, best of 3: 480 usec per loop [alex@lancelot bo]$ timeit.py -c -s'import d' 'd.amap()' 1000 loops, best of 3: 790 usec per loop so sum could be touted as "the only obvious solution" -- shortest, neatest, fastest... IF it were indeed fast!-) Unfortunately, with the sum change regressed, d.asum times to 8.4e+03 usec per loop, so it clearly cannot be considered any more:-). So, there might be space for an accumulator function patterned on map but [a] which stops on the shortest sequence like zip and [b] does NOT build a list of results, meant to be called a bit like map is in the 'amap' example above. itertools is a great little collection of producers and manipulators of iterators, but the "accumulator functions" might provide the "one obvious way" to _consume_ iterators for common cases; and accumulating by calling an accumulator-object's mutator method, such as tot.extend above, on all items of an iterator, clearly is pretty common. Alex
Alex Martelli <aleaxit@yahoo.com> writes:
I *think* I see what you're getting at here, but I'm struggling to follow in the absence of concrete use cases. As we're talking about library functions, I'd suggest that your suggested "accumulator functions" start their life as an external module - maybe even in Python, although I take our point about the speed advantages of C. With a bit of "real life" use, migration into the standard library might be more of an obvious step. Paul. -- This signature intentionally left blank
On Sunday 26 October 2003 05:21 pm, Paul Moore wrote: ...
I *think* I see what you're getting at here, but I'm struggling to follow in the absence of concrete use cases. As we're talking about
Assuming the simplest definition, equivalent to: def loop(bound_method, it): for item in it: bound_method(item) typical simple use cases might be, e.g.: Merge a stream of dictionaries into one dict: merged_dict = {} loop(merged_dict.update, stream_of_dictionaries) rather than: merged_dict = {} for d in stream_of_dictionaries: merged_dict.update(d) Add a bunch of sequences into one list: all_the_seqs = [] loop(all_the_seqs.extend, bunch_of_seqs) rather than: all_the_seqs = [] for s in bunch_of_seqs: all_the_seqs.extend(s) Add two copies of each of a bunch of sequences ditto: all_the_seqs = [] loop(all_the_seqs.extend, s+s for s in bunch_of_seqs) ditto but only for sequences which have 23 somewhere in them: seqs_with_23 = [] loop(seqs_with_23.extend, s for s in bunch_of_seqs in 23 in s) and so on. There are no doubt possibly more elegant ways, e.g. def init_and_loop(initvalue, unboundmethod, it, *its): for items in itertools.izip(it, *its): unboundmethod(initvalue, *items) return initvalue which would allow, e.g., merged_dict = init_and_loop({}, dict.update, stream_of_dictionaries) or other variants yet, but the use cases are roughly the same. The gain of such tiny "accumulator functions" (consuming one or more iterators by just passing their items to some mutating-method and ignoring the latter's results) are essentially conceptual -- it's not a matter of saving a couple of lines at the point of use, nor of saving some "bananoseconds" if the accumulator functions are implemented in C, when compared to the coded-out loops. Rather, such functions would allow "more declarative style" presentation (of underlying functionality that remains imperative): expressions feel more "declarative", stylistically, to some, while spelling a few steps out feels more "imperative". We've had this preference explained recently on this group, and others over in c.l.py are breaking over the champagne at the news of list.sorted for essentially the same motivation.
Absolutely. It's not _my_ suggestion to have more accumulator functions -- it came up repeatedly on the threads started by Peter Norvig original proposal about accumulation, and Guido mentioned them in the 'product' thread I believe (where we also discussed 'any', 'all' etc, if I recall correctly). I don't think anybody's ever thought of making these built-ins. But if that external module[s] (one or more) is/are not part of the Python 2.4 library, if 2.4 does not come with a selection of accumulation functions [not necessarily including that 'loop' &c above mentioned, though I think something like that might help], I don't think we can have the "accumulation functionality" -- we only have great ways to make and express iterators but not many great ways to _consume_ them (and most particularly if sum, one of the few "good iterator consumers" we have, is practically unusable for iterators whose items are lists..).
With a bit of "real life" use, migration into the standard library might be more of an obvious step.
You could have said the same of itertools before 2.3, but I think it was a great decision to accept them into the standard library instead; 2.3 would be substantially poorer without them. With an even richer complement of iterator tools in itertools, and the new "generator expressions" to give us even more great ways to make iterators, I think a module of "iterator consumers", also known as accumulation functions, would be a good idea. Look at Peter Norvig's original ideas for some suggestions, for example. Which reminds me of an issue with Top(10), but, this is a long enough post, so I think I should write a separate one about that. Alex
Alex Martelli <aleaxit@yahoo.com> writes:
[...]
and so on.
None of which are, to me, particularly convincing. Then again, while I like a "declarative style" in some cases, I've got nothing against the sort of "idiom-based" style in which short code patterns just "mean something" as a whole, and aren't viewed as being comprised of their individual parts (much like the standard C idiom for walking a linked list).
OK. I'd bow out here, as I don't feel the need to push the declarative style that extra step. Let others champion the style.
I'm sorry - I'd got the impression that you were arguing the case. In which case, I'd have to say that I'm not at all clear who it is who's proposing anything here, or what specifically the proposals are. I suspect the original intention is getting lost in generalities, and it's time for those original posters to speak up and clarify exactly what they want. Maybe a PEP is in order, to get back to the core of the proposal.
Agreed. I was very conscious of itertools when I made that statement. But my gut feel is that in this case, there has been so much discussion that the key concept has been obscured. A PEP, or some prior art, would recapture that.
In principle, I don't have a problem with that. Let's get concrete, though, and see either a PEP or some code. Otherwise, the discussion isn't really going anywhere. And on that note, I really ought to bow out :-) Paul. -- This signature intentionally left blank
Hello, On Sun, Oct 26, 2003 at 11:09:56AM +0100, Alex Martelli wrote:
Oh, but we all *did* think of it. For strings. :-)
I must admit I was a bit surprized when I first tested sum(), without first reading its doc because I thought I knew what it should do. I expected it to be a fast equivalent to: def sum(seq, start=0): for item in seq: start = start + seq return start or: reduce(operator.add, seq, start) I immediately tried it with strings and lists. I immediately thought about lists because of their use of "+" for concatenation. So it seems that neither strings nor lists are properly supported, neither tuples by the way, and my opinion on this is that it strongly contradicts the principle of least surprize. I would not object to an implementation of sum() that special-case lists, tuples and strings for efficiency. (by which I mean I can contribute a patch)
Supporing sum() in Psyco is no big issue, and it could help the same way as it does for str.__add__. (It is not explicitely supported yet, but it could be added.) Still I believe that getting the complexity right in CPython is important, when it can be done. Armin
On Sunday 26 October 2003 05:23 pm, Armin Rigo wrote: ...
It IS equivalent to that -- plus an explicit typetest to raise if start is an instance of str or unicode. I had originally tried forwarding to ''.join for strings, but Guido preferred to forbid them, and it still doesn't look like a problem to me. Alas, "fast" is debatable:-).
reduce(operator.add, seq, start)
sum doesn't reproduce reduce's quirk of using the first item of seq if start is not given. So, the def version is closer.
Strings are explicitly disallowed, so that should take care of the surprise factor for that specific case. As for lists, the semantics are right, the speed is not (could be made way faster with modest effort). Same for other mutable sequences. As for tuples and other immutable sequences, they ARE treated exactly like your 'def' above (roughly like your reduce) would treat them -- not very fast, but if all you know about something is that it's an immutable sequence, there's nothing more you can do. The use case of making a huge tuple from many smaller ones seems weird enough that I don't see specialcasing tuples specifically as particularly worthwhile (other immutable sequences that aren't exactly tuples would still suffer, after all).
tuples by the way, and my opinion on this is that it strongly contradicts the principle of least surprize.
For mutable sequences, I agree. For immutable ones, I don't see the performance trap as being a practical problem for tuples (and weirder things) -- it WOULD be for strings, but as we specifically disallow them with a message reminding the user of ''.join, in practice the problem seems minor. Maybe I'm coming to this with a too-pragmatical stance...?
I think all mutable sequences (that aren't especially weird in their + vs += behavior) might be handled correctly, without specialcasing, roughly as follows (Phillip Eby's idea): def sum(seq, start=0): it = iter(seq) try: result = start + it.next() except StopIteration: return start for item in it: result += item return result my original idea was perhaps a bit goofier, something like: def sum(seq, start=0): try: start = copy.copy(start) except TypeError: for item in seq: start = start + item else: for item in seq: start += item return start Admittedly the latter version may accept a few more cases, e.g. both versions would accept: sum([ range(3), 'foo' ], []) because [] is copyable, []+range(3) is fine, and list.__iadd__ is more permissive than list.__add__; however, the first version would fail on: sum([ 'foo', range(3) ], []) because []+'foo' fails, while the second version would be fine because [] is _still_ copyable and __iadd__ is still permissive:-). So, perhaps, implementing by Phillip's idea would still not reduce the suprise factor enough. Hmmm...
Absolutely -- we can't rely on psyco for everything, particularly not for getting the big-O right as opposed to speeding things up by constant multipliers (in part, for example, because psyco doesn't work on Mac's, which are going to be a HUGE part of Python's installed base...). However, I would be happy to "leave it to psyco" for a sum of a large sequence of tuples or other immutable sequences...:-). I just don't think that people in practice _will_ fall into that performance-trap... Alex
Hello Alex, On Sun, Oct 26, 2003 at 07:20:52PM +0100, Alex Martelli wrote:
Yes, it is what I'm saying: it is what we expect it to be, but there is an exception for no real reason apart from "don't do it like this, buddy, there is a faster version out there". I tend to regard this kind of exceptions as very bad, because if you write a generic algorithm using sum(), even if you don't really see why someone would think about using your algorithm with strings one day, chances are that someone will. Raising a Warning instead of an exception would have had the same result without the generality problem.
I was thinking about: def sum(seq, start=0): return reduce(operator.add, seq, start) which is the same as the previous one.
These cases all show that we have a surprize problem (although probably not a big one). The user will expect sum() to have a clean definition, and because the += one doesn't work, it must be +. To my opinion, sum() should be strictly equivalent to the naive + version and try to optimize common cases under the hood. Admittedly, this is not obvious, because of precisely all these strange mixed type cases which could be user-defined classes with __add__ or __radd__ operators... I'm sure someone will design a class class x: def __add__(self, other): return other so that x() can be used as a trivial starting point for sum() -- and then sum(["abc", "def"], x()) works :-) Armin
Alex Martelli <aleaxit@yahoo.com>:
Seems to me the bug there is not giving X an __rmul__ method and yet expecting y*x to work at all. The fact that it happens to work in some cases is an accident that should not be relied upon. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+
On Monday 27 October 2003 04:22, Greg Ewing wrote:
No, the bug is that it works in some cases where it should fail (and, secondarily, that -- where it does fail -- it gives a weird error message). In other words, the bug (in Python) is that "accident". Nobody's asking for 3.0*x to work where x is a user-coded type without an __rmul__; rather, the point is that 3*x should fail too, and ideally they'd have the same clear error message as 3+x gives when the type has no __radd__. Doesn't seem trivial to fix (though I hope I'm missing something obvious) and doesn't affect perfect user-programs, but I do think it should be fixed because it's sure extremely mysterious and could send a developer on wild goose chases when met in the course of development. Alex
Alex Martelli <aleaxit@yahoo.com>:
Okay, that makes sense. Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+
On Tuesday 28 October 2003 01:04 am, Greg Ewing wrote:
So how do you think we should go about it? I can't see a way right now (at least not for 2.3, i.e. without breaking some programs). A user COULD have coded a class that's meant to represent a sequence AND relied on the (undocumented, I think) feature that giving the class a __mul__ automatically makes instances of that class multipliable by integers on EITHER side, after all. We can't (sensibly), I think, distinguish that from the case where the user has coded a class that's meant to represent a number and gets astonished that __mul__, undocumentedly, makes isntances of that class multipliable by integers on either side. So perhaps for 2.3 we should just apologetically note the anomaly in the docs, and for 2.4 forbid the former case, i.e., require both __mul__ AND __rmul__ to exist if one wants to code sequence classes that can be multiplied by integers on either side...? Any opinions, anybody...? Alex
What's wrong with the status quo? So 3*x is undefined, and it happens to return x*3. Is that so bad? --Guido van Rossum (home page: http://www.python.org/~guido/)
On Tuesday 28 October 2003 04:16 pm, Guido van Rossum wrote:
Where is it specified that 3*x "is undefined" when x's type exposes __mul__ but not __rmul__ ? Sorry, I don't understand the viewpoint you seem to imply here. If x's type exposed no __add__ but "it just so happened" that x+23 always returned 12345 -- while every other addition, as expected, failed -- would you doubt the lack of a normal and reasonably expected exception is bad? I think that if Python returns "arbitrary" results, rather than raising an exception, for operations that "should" raise an exception, that is surely very bad -- it makes it that much harder for programmers to debug the programs they're developing. If there's some doubt about the words I've put in hyphens -- that treating x*y just like y*x only for certain values of type(y) isn't arbitrary or shouldn't raise -- then we can of course discuss this, but isn't the general idea correct? Now, the docs currently say, about sequences under http://www.python.org/doc/current/ref/sequence-types.html : """ sequence types should implement ... multiplication (meaning repetition) by defining the methods __mul__(), __rmul__() and __imul__() described below; they should not define __coerce__() or other numerical operators. """ So, a sequence-emulating type that implements __mul__ but not __rmul__ appears to violate that "should". The description of __mul__ and __rmul__ referred to seems to be that at http://www.python.org/doc/current/ref/numeric-types.html . It says that methods corresponding to operations not supported by a particular kind of number should be left undefined (as opposed to the behavior of _attempts at those operations_ being undefined), so if I had a hypothetical number type X such that, for x instance of X and an integer k, x*k should be supported but k*x shouldn't, isn't this a recommendation to not write __rmul__ in X ...? Besides, this weird anomaly is typical of newstyle classes only. Consider:
ALL wonderful, just as expected, hunky-dory. But now, having read that newstyle classes are better, I want to make X newstyle -- can't see any indication in the docs that I shouldn't -- and...:
*eep*! Yes, it DOES seem to be that this is QUITE bad indeed. Alex
You're making a mountain of a molehill here, Alex. I know that in group theory there are non-Abelian groups (for which AB != BA), but I've never encountered one myself in programming; more typical such non-commutative operations are modeled as __add__ rather than as __mul__. Anyway, the real issue AFAICT is not that people depend on __rmul__'s absence to raise a TypeError, but that people learn by example and find __rmul__ isn't necessary by experimenting with integers. The reason why it works at all for integers without __rmul__ is complicated; it has to do with very tricky issues in trying to implement multiplication of a sequence with an integer. That code has gone through a number of iterators, and every time someone eventually found a bug in it, so I'd rather leave the __rmul__ blemish than uproot it again. If you can come up with a fix that doesn't break sequence repetition I'd be open to accepting it (for 2.4 only, in 2.3 there may be too much code depending on the bug) but only after serious review -- and not by me, because I'm not all that familiar with all the subtleties of that code any more. :-( --Guido van Rossum (home page: http://www.python.org/~guido/)
I need to give myself a small slap on the forehead head, because of course non-square matrix multiplication is an excellent example where AB != BA. However even there, Ax == xA when x is a singleton, and the issue only arises for integers, so I still don't think there are use cases. --Guido van Rossum (home page: http://www.python.org/~guido/)
On Tuesday 28 October 2003 07:37 pm, Guido van Rossum wrote:
There may be no "perfectly correct code" that will ever notice 3*x weirdly works. But would that make it acceptable to return 42, rather than raise IndexError, when a list of length exactly 33 is indexed by index 666? That, too, might "have no practical use cases" for perfectly correct code. But programmers make mistakes, and one of Python's strength is that it does NOT (crash, hang, or) return weird wrong results when they do -- most often it raises appropriate exceptions, which make it easy to diagnose and fix one's mistakes. Thus, it troubles me that we can't do it here. I know it's hard to fix (I've stared at that code for QUITE a while...). But "deducing" from that difficulty that the error's not worth fixing seems like a classic case of "sour grapes":-). Alex
I dunno. As language warts go I find this one minuscule, and the effort you spend on rhetoric to convince me a waste of breath. My position is: I understand that it's a wart, I just don't think I know of a good solution, and I can live with the status quo just fine. --Guido van Rossum (home page: http://www.python.org/~guido/)
On Tuesday 28 October 2003 07:28 pm, Guido van Rossum wrote: ...
You're making a mountain of a molehill here, Alex. I know that in
You have a point: when one is in love (and I still _am_ madly in love with Python!-), it's hard to admit of imperfections in the loved one:-). Even a tiny defect...:-).
I don't remember ever coding a __mul__ that I WANTED to be non-commutative, right.
Or more seriously: they write what LOOK like perfectly adequate unit tests, but the numbers they try in "number * x" happen to be ints; so the unit tests pass -- but their code is broken because they forgot the __rmul__ and the unittests-with-ints didn't catch that.
Yes, I think I understand some of that -- I included the analysis of the bug in my bugreport on SF.
I do have one weird idea that might help here (for 2.4), but I'd better post that separately because I suspect it's going to fuel its own long discussion thread. As things are, without an ability to distinguish a sequence from a number securely, and IF sequences must work w/o __rmul__ (but they didn't in classic classes...? and the docs don't indicate that...?) then I'm stumped. Who'd be the right people to review such proposed changes, btw? Alex
Guido van Rossum <guido@python.org>:
I thought the plan was to get rid of all the special case code in the interpreter for multiplying sequences and push it all down into methods of the objects concerned, i.e. all sequences, including the built-in ones, would implement the C equivalent of both __mul__ and __rmul__ if they wanted to support multiplication on both sides. Is there some reason why that wouldn't work? Or is it just that nobody has had time to fix all the built-in sequences to work this way? Greg Ewing, Computer Science Dept, +--------------------------------------+ University of Canterbury, | A citizen of NewZealandCorp, a | Christchurch, New Zealand | wholly-owned subsidiary of USA Inc. | greg@cosc.canterbury.ac.nz +--------------------------------------+
It would be a lot of work, and I expect that for 3rd party extension types (and possibly for 3rd party Python classse) it wouldn't be quite compatible. I want it to work this way in Python 3.0, but I don't know if it's worth reworking all that tedious detail in the 2.x series. (Understanding that 3.0 is a few years away still.) --Guido van Rossum (home page: http://www.python.org/~guido/)
participants (5)
-
Alex Martelli -
Armin Rigo -
Greg Ewing -
Guido van Rossum -
Paul Moore