Mailman 3 August 2002 - Python-Dev

RE: [Python-Dev] PEP 218 (sets); moving set.py to Lib
by Delaney, Timothy Aug. 21, 2002

Aug. 21, 2002

> From: Guido van Rossum [mailto:guido@python.org] > > > Hmm ... is there a case that NotImplementedError should be a > > subclass of TypeError? Conceptually it would make sense (this *type* > > does not implement this method). > > I think you're overthinking this. NotImplementedError is fine for > code that wants to send that particular message to the user. We're > playing with TypeError here because we're trying to be close to the > metal. I'd be willing to concede that I was overthinking, except that it took surprisingly little thought for the connection to be made ;) Tim Delaney

1 0

RE: Python-Dev digest, Vol 1 #2574 - 14 msgs
by Noah Aug. 21, 2002

Aug. 21, 2002

On Wed, 21 Aug 2002 Aahz wrote: > On Wed, Aug 21, 2002, Skip Montanaro wrote: > > parsing != tokenizing. ;-) > > Regular expressions are great for tokenizing (most of the time). > Ah. Here we see one of the little drawbacks of not finishing my CS > degree. ;-) Can someone suggest a good simple reference on the > distinctions between parsing / lexing / tokenizing, particularly in the > context of general string processing (e.g. XML) rather than the arcane > art of compiler technology? > Aahz (aahz(a)pythoncraft.com) <*> http://www.pythoncraft.com/ It's been 8 or 9 years since I took a compiler design class, so this info is probably be WRONG, but as luck would have it I've been reviewing some of this stuff lately so I can feel some of the old neuron paths warming up. Basically the distinction between a lexer and a parser refers to the complexity of symbol inputs that they can recognize. A lexer (AKA tokenizer) is modeled by a finite state machine (FSM). These don't have a stack or memory, just a state. They are not good for things that require nested structure. A parser recognizes more complex structures. They are good for things like XML and source code where you have NESTED tree structures (familiarly known as SYNTAX). If you have to remember how many levels deep you are in something then it means you need a parser. Technically a parser is something that can be defined by a context free grammar and can be recognized by a Push Down Automata (PDA). A PDA is a FSM with memory. A PDA has at least one stack. The "context free" on the grammar means that you can unambiguously recognize any section of the input stream no matter what came earlier in the stream. ... Sometimes real grammars are a little dirty and context does matter, but only within a small window. That means you might have to "look ahead" or behind a few symbols to eliminate some ambiguity. The amount that you have to look ahead sets the complexity of the grammar. This is called LALR (look ahead left reduce). So a simple grammar with no look ahead is called LALR(0). A slightly more complex grammar that requires 1 symbol look-ahead is called LALR(1). We like most parsing to be simple. I think languages like C and Python require are LALR(0). I think FORTRAN does require a look-ahead, so it's LALR(1). I have no idea what it must require to parse Perl. [Again Note: I sure I probably got some details wrong here.] If you go further in complexity and you want to handle evaluating expressions then you need a Turing Machine (TM). These are problems where a context-free grammar cannot be tweaked with a look-ahead. Another way to think about it is if your input is so complex that it must be described algorithmically then you need a TM. For example neither a FSM nor a PDA can recognize a non-rational number like SQRT(2) or pi. Nor can they recognize the truthfulness of expressions like "2*5=10" (although a PDA can recognize that it's a valid expression). RegExs are hybrids of FSM and PDA and are fine for ad hoc lexing. They are not very good for parsing. I think older style RegExs started life off as pure FSM, but newer flavors made popular by Perl added memory and became PDAs... or something like that. But somehow they are limited and not quite as powerful as a real PDA, so they can't parse. Traditionally C programmers used a combination of LEX and YACC (or GNU's versions of FLEX and Bison) to build parsers. You really only need YACC, but the problem is so much simpler if the input stream is tokenized before you try to parse it, which is why you also use LEX. Hopefully that captures the essence if not the actual facts. But then I'm trying to compress one year of computer science study into this email :-) If you are interested I just wrote a little PDA class for Python. Yours, Noah

1 0

RE: [Python-Dev] PEP 218 (sets); moving set.py to Lib
by Delaney, Timothy Aug. 21, 2002

Aug. 21, 2002

> From: Guido van Rossum [mailto:guido@python.org] > > OK, from the checkins: > > - Changed the NotImplementedError in BaseSet.__init__ to TypeError, > both for consistency with basestring() and because we have to use > TypeError when denying Set.__hash__. Together those provide > sufficient evidence that an unimplemented method needs to raise > TypeError. Hmm ... is there a case that NotImplementedError should be a subclass of TypeError? Conceptually it would make sense (this *type* does not implement this method). Of course, it would probably also break code ... Tim Delaney

6 9

PEP 277 (unicode filenames): please review
by Martin v. Löwis Aug. 21, 2002

Aug. 21, 2002

http://www.python.org/peps/pep-0277.html The PEP describes a Windows-only change to Unicode in file names: On Windows NT/2k/XP, Python would allow arbitrary Unicode strings as file names and pass them to the OS, instead of converting them to CP_ACP first. This applies to open() and all os functions that accept filenames. In addition, os.list() would return Unicode filenames if the argument is Unicode. Please comment on the PEP. There is an updated patch on http://python.org/sf/594001; please comment on the patch as well. Regards, Martin

14 46

Embarassed in Malvern
by Eric S. Raymond Aug. 21, 2002

Aug. 21, 2002

Apparently I was hallucinating when I thought these has been released in open source. Aaarrgghh. Well, they had a butt-ugly API anyway. I'll replace the with Damian Ivereigh's libredblack in 0.3. -- <a href="http://www.tuxedo.org/~esr/">Eric S. Raymond</a> Government should be weak, amateurish and ridiculous. At present, it fulfills only a third of the role. -- Edward Abbey

3 2

Sort() returning sorted list
by Sean Reifschneider Aug. 21, 2002

Aug. 21, 2002

It would be nice to have, at times, sort() return the sorted list, but doing so could lead people to believe that returns a sorted copy of the list. What about if we could do "list.sort(returnAfterSorting = 1)" or something? It'd be nice if it were short and sweet, but it should be clear what it's doing too... Sean -- Passionate hatred can give meaning and purpose to an empty life. -- Eric Hoffer Sean Reifschneider, Inimitably Superfluous <jafo(a)tummy.com> tummy.com - Linux Consulting since 1995. Qmail, KRUD, Firewalls, Python

2 3

Re: [Python-Dev] Re: PEP 218 (sets); moving set.py to Lib
by Guido van Rossum Aug. 21, 2002

Aug. 21, 2002

A few transformations down the road, here's a 4-line powerset() generator: def powerset(base): pairs = [(2**i, x) for i, x in enumerate(base)] for n in xrange(2**len(pairs)): yield [x for m, x in pairs if m&n] --Guido van Rossum (home page: http://www.python.org/~guido/)

2 1

Re: [Python-Dev] PEP 277 (unicode filenames): please review
by Matthias Urlichs Aug. 20, 2002

Aug. 20, 2002

Guido: > > My guess it's not his listdir() or filesystem, but the keyboard > driver. > No, it's MacOSX. It always uses the decomposed form. That is very noticeable via NFS volumes where files with combined character names are unopenable from the GUI. I've filed a bug report about that - i don't know whether OSX 10.2 will allow NFC filenames, at least read-only. -- Matthias Urlichs

2 2

What is a backport candidate?
by Guido van Rossum Aug. 20, 2002

Aug. 20, 2002

> When we say "backport candidate", does that mean we need to think > about it more or that it is waiting for someone like me to pounce on > it and get it done? It means somebody (like you :-) should do triage on the feasibility of it. The triage can have several outcomes: - Trivial yes: the patch applies directly to the 2.2 branch and doesn't cause problems there. In this case, you can apply it right away and be done with it. - Trivial no: the patch doesn't make sense at all -- this should only happen when the patch patches code that was added in 2.3; in this case the backport/bugfix marking was a mistake, but mistakes happen. - Needs work: the idea behind the patch applies to 2.2, but the code there is sufficiently different that patch (or cvs update -j) doesn't quite work. There are gradations of this, depending on what's in the way. In this case, you may put it off. We need a database of these triage decisions; the new RoundUp-based tracker (prototype at python.org:8080) is supposed to have a feature to add this info to the tracker, but I don't know how it works or whether it is adequate yet. I'm cc'ing this to python-dev since others may be interested in this topic. Also note that I believe we've been inconsistent in marking up candidates: some say "bugfix candidate", some say "backport candidate", some may not be marked at all. :-( --Guido van Rossum (home page: http://www.python.org/~guido/)

1 0

PEP 218 (sets); moving set.py to Lib
by Guido van Rossum Aug. 20, 2002

Aug. 20, 2002

(I know there's a sets list at SF, but SF refuses mail from this machine, and that list is essentially dead.) In CVS at python/nondist/sandbox/sets/ you'll find a module set.py (and its unit tests) that implement a versatile Set class roughly according to PEP 218. This code has three authors: Greg V. Wilson wrote the first version; Alex Martelli changed the strategy around (im)mutability and removed inheritance from dict in favor of having a dict attribute; and I cleaned it up and changed some implementation approaches to what I think are faster algorithms (at the cost of somewhat more verbose code), also changing the API a little bit. I'd like to do a little more cleanup and then move it into the standard library. The API is roughly that of PEP 218, although it supports several methods and operations that aren't listed in the PEP, such as comparisons and subset/superset tests. I'm not sure whether I want to go fix the PEP to match this implementation, or whether to skip that step and simply document the module in the standard library docs (that has to be done anyway). The biggest difference with the PEP is a different approach to the (im)mutability issue. This problem is that on the one hand, sets are containers that hold a potentially large number of elements, and as such they ought to be mutable: you should be able to start with an empty set and then add elements to it one at a time. On the other hand, the only efficient implementation strategy is to represent a set internally as the keys of a dictionary whose values are ignored. This way insertion and removal can be done very efficiently, at the cost of a restriction: set elements must be immutable. The implication is that you can't have sets of sets -- but occasionally those are handy! The PEP proposed a strategy based on "freezing" a set as soon as it is incorporated into another set; but in practice this didn't work out very well, in part because the test 's1 in s2' would cause s1 to be frozen: its hash value has to be computed to implement the membership test, and computing the hash value signals freezing the set. This caused too many surprises. Alex Martelli implemented a different strategy (see python.org/sf/580995): there are two set classes, (mutable) Set and ImmutableSet. They derive from a common base class (BaseSet, an abstract class) that implements most set operations. ImmutableSet adds __hash__, and Set adds mutating operations like update(), clear(), in-place union, and so on. The ImmutableSet constructor accepts a sequence or another set as its argument. While this is an easy enough way to construct an immutable set from a mutable set, for added convenience, if a mutable set is added to another set (except in the constructor), an immutable shallow copy is automatically made under the covers and added instead. Also, when 's1 in s2' is requested and s1 is a mutable set, it is wrapped in a temporarily-immutable wrapper class (an internal class that is not exposed) which compares equal to s1 and has a hash value equal to the hash value that would be computed for an immutable copy of s1. The temporary wrapper does not make a copy; none of the code here is thread-safe anyway, so if multiple threads are going to share a mutable set, they will have to use their own locks. I deviated from the original API in a few places: - I renamed the method is_subset_of() to issubset(), since I don't like underscores in method names, and think leaving the 'of' off will cause ambiguity; I also added issuperset(). - I renamed intersect() to intersection() and sym_difference() to symmetric_difference(); ditto for the corresponding _update() methods. - Alex's code explicitly disallowed in-place operators (e.g. __ior__ meaning in-place union) for immutable sets. I decided against this; instead, when s1 is a variable referencing an immutable set, the statement 's1 |= s2' will compute s1|s2 as an immutable set and store that in the variable s1. On the other hand, if s1 references a mutable set, 's1 |= s2' will update the object refereced by s1 in-place. This is similar to the behavior of lists and tuples under the += operator. - The left operand of a union, intersection or difference operation will decide the type of the result. This means that generally when you've got immutable sets, you'll produce more immutable sets; and when you've got mutable sets, you'll produce mutable sets. When you mix the two kinds, the left argument of binary operations wins. Some minor open questions: - The set constructors have an optional second argument, sort_repr, defaulting to False, which decides whether the elements are sorted when str() or repr() is taken. I'm not sure if there would be negative consequences of removing this argument and always sorting the string representation. It would simplify the interface and make the output nicer (since usually you don't think about setting this argument until it's too late). I don't think that the extra cost of sorting the list of elements will be a burden in practice, since normally one would only print small sets (if a set has thousands of elements, printing it isn't very user friendly). - I'd like to change the module name from set.py to sets.py. Somehow it makes more sense to write from sets import Set, ImmutableSet than from set import Set, ImmutableSet - I'm aware that this set implementation is not the be-all and end-all of sets. I've seen a set implementation written in C, but I was not very impressed -- it was a massive copy-paste-edit job done on the dict implementation, and we don't need such code duplication. But eventually there may be a C implementation which will change some implementation details. - Like other concrete types in Python, these Set classes aren't really designed to mix well with other set implementations. For example, sets of small cardinal numbers may be represented efficiently by long ints, but the union method currently requires that the other argument uses the same implementation. I'm not sure whether this will eventually require changing. Any comments? Or shall I just check this in? --Guido van Rossum (home page: http://www.python.org/~guido/)

8 16