[Python-3000] Need help completing ABC pep (original) (raw)

Jeffrey Yasskin jyasskin at gmail.com
Fri Apr 20 09:48:28 CEST 2007

On 4/19/07, Guido van Rossum <guido at python.org> wrote:

I've started a PEP on Abstract Base Classes (ABCs), PEP 3119:

http://www.python.org/dev/peps/pep-3119/ While I'm not ready yet to answer tough questions about this compared to alternative proposals, I am ready for feedback on the various open issues sprinkled throughout the current text, especially concerning decisions regarding exactly which operations to include in the various ABCs, and also regarding the level of detail required in the PEP.

I have a bunch of comments that aren't all related to the open issues. I'm more familiar with statically typed languages, so sorry if some of these comments don't make sense in a Python context.

Hashable might want to specify the exception that should be thrown for mutable objects.

I wouldn't have guessed what Finite was from the name, but I don't mind it now that I know. I do prefer 'Sized'.

A possible name for the contains ABC for sequences and strings is 'Searchable'. On the other hand, an annotation of some sort for the running time of the method might do as well, but I don't know of any prior art for that.

On Sets: Do you have an example of a data structure that is a Set but not a ComposableSet?

Set should inherit from a PartiallyOrdered ABC that defines the comparison operators.

The final specification of Set should spell out the invariants, but they're clear enough that the PEP probably doesn't need to. It's odd, though, that you mention optimizations to eq and le but not their semantics.

ComposableSet's open issues:

Should we define an API for creating new instances (e.g. a class method or a fixed constructor signature)?

There are some set types that can't be constructed from arbitrary sequences. For example, Patricia Tries (http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-IntSet.html) can be used to make very efficient sets of integers, but only integers.

Should we just pick a concrete return type (e.g. set)?

For set compositions, you should say whether the arguments need to be uniform. (Is (IntSet(1,2,3) | set('a','b','c')) allowed?) If they do, then you don't need a concrete return type; if they don't, then you do, and the default implementations should use it. Even this may be a problem if someone writes a TreeSet which requires TotallyOrdered-but-not-Hashable elements. In any case, the ABC should encourage implementors to return an instance of the same type as the arguments when the arguments are of the same type.

Should we add the copy method? Not on ComposableSet, but maybe in a Copyable ABC, which it might inherit from.

MutableSet:

Should we support more operations implemented by the Python 2 set type?

You have groups of equivalent operations (add, update, ior), (discard, difference_update, isub), (??, intersection_update, iand), and (??, symmetric_difference_update, ixor)

It would be nice to make these all uniform. Intersection is hard to support one element at a time, but symmetric difference would work with a toggle() method. The operations that work a group at a time are likely be more efficient on Sized arguments, and much more efficient on arguments of the same type. How much are you trying to support these kinds of optimizations to implementations?

Should we unify remove and discard, a la Java (which has a single method returning a boolean indicating whether it was removed or not)?

Yes. :)

Mappings: Set-like unions, intersections, and differences are useful on maps too, but you usually have to provide a function to say what to do with colliding values. This is probably a different PEP though.

Sequence: I guess you've already dealt with this, but allowing getitem with integer indices on str objects forces you to use UTF-32 or play interesting games with caching. Most string algorithms are quite happy with (bidirectional? multipass?) iterators, but programmers aren't used to using them.

Numbers: Haskell might be good to use for inspiration on the numeric classes: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#7. Note that Haskell's "Real" doesn't imply that the number is fractional, just that it's not complex. Some differences I see from Bill Janssen's proposal:

Fortress (http://research.sun.com/projects/plrg/fortress.pdf#page=270) has an extremely detailed hierarchy of algebraic traits, and it looks like they plan a similarly detailed hierarchy of numbers, but the numbers aren't yet specified beyond integers and rationals.

Cardinal is also useful as the argument to (Sequence * Cardinal).

Index (Ix) is used in Haskell primarily in the form of tuples of Ints for multi-dimensional arrays.

-- Namasté, Jeffrey Yasskin

More information about the Python-3000 mailing list