[Python-ideas] Adding collections.abc.Ordered

[Amir Rachum]

I am suggesting the addition of a collections abstract base class called "Ordered". Its meaning is that a collection's iteration order is part of its API. The bulk of this mail describes a use case for this. The reason I believe that such abstract base class is required is that there is no way to test this behavior in a given class. An ordered collection has the exact same interface as an unordered collection (e.g, dict and OrderedDict), other than a _promise_ of the API that the order in which this collection will be iterated has some sort of meaning (In OrderedDict, it is the order in which keys were added to it.)

As examples, set, frozenset, dict and defaultdict should *not* be considered as ordered. list, OrderedDict, deque and tuple should be considered ordered.

Before I dive into the use case I am presenting, I would like to point out that a similar discussion was already done on the subject (suggesting at first that OrderedDict would abstract-subclass from Sequence) at the following thread* - http://code.activestate.com/lists/python-ideas/29532/. That thread was abandoned largely from a lack of a clear use case, which I hope will be more clear in this suggestion.

I am working on package called basicstruct (https://pypi.python.org/pypi/basicstruct). The way it works is that you define an object that inherits from basicstruct.BasicStruct, define __slots__ , and automatically get behaviors such as a nice __init__, __str__, comparison functions, attribute access, dict-like access, pickleability, etc. It is similar to namedtuple, except that it is mutable.

In the Python documentation, the following is said regarding __slots__:

   Any non-string iterable may be assigned to __slots__. Mappings may also be used; however, in the future, special meaning may be assigned to the values corresponding to each key.

Here's how the current__init__ method of BasicStruct looks like:

   class BasicStruct(object):

       """Class for holding struct-like objects."""

       __slots__ = ()  # should be extended by deriving classes

       def __init__(self, *args, **kwargs):

           arg_pairs = zip(self.__slots__, args)

           for key, value in chain(arg_pairs, six.iteritems(kwargs)):

               setattr(self, key, value)

           for key in self.__slots__:

               if not hasattr(self, key):

                   setattr(self, key, None)

Notice the following line:

   

   arg_pairs = zip(self.__slots__, args)

It assumes that __slots__ defines attributes in a certain order. So as a use I would expect that the following code

   class MyStruct(BasicStruct):

      __slots__ = ('x', 'y')

   

   MyStruct(0, 1)

... will create a struct in which x is 0 and y is 1.

However, if I define __slots__ as a set, or dict, the result is undefined.

   class MyStruct(BasicStruct):

      __slots__ = {'x', 'y'}  # No order is defined here

   

   MyStruct(0, 1)  # Which is which?

So, In BasicStruct's __init__ method it is required to test whether __slots__ was defined with a collection that has a meaningful order. If it was _not_, using non-keyword arguments in __init__ should be forbidden, since the order of __slots__ is arbitrary. Here is how I wish the code would look like:

   class BasicStruct(object):

       """Class for holding struct-like objects."""

   

       __slots__ = ()  # should be extended by deriving classes

   

       def __init__(self, *args, **kwargs):

           ordered = isinstance(self.__slots__, Ordered)

   

           if args and not ordered:

               raise ValueError("Can't pass non-keyword arguments to {}, since "

                                "__slots__ was declared with an unordered "

                                "iterable.".format(self.__class__.__name__))

   

           arg_pairs = zip(self.__slots__, args)

           for key, value in chain(arg_pairs, six.iteritems(kwargs)):

               setattr(self, key, value)

   

           for key in self.__slots__:

               if not hasattr(self, key):

                   setattr(self, key, None)

Thanks,

Amir Rachum

* The author of the original thread is Ram Rachum. To avoid some confusion - yes, we are related - Ram is my big brother. It's just so happens that I was looking around for this issue and found that he did so in the past as well.

[Andrew Barnert via Python-ideas]

As I understand it, the only reason you want this ABC is so that if someone uses your struct-sequence class and defines his attributes with no inherent order, you want to be able to raise an error if he uses positional initialization. Has anyone ever done that? Has anyone complained "I created a struct type with attributes a and b in arbitrary order, and then when I do Spam(1, 2), sometimes a gets 1 and sometimes it gets 2"?

It seems to me that this is obviously the same as, say, a user explicitly zipping two sets together. Sure, it's a stupid thing to do—but it's an _obvious_ stupid thing to do, so zip doesn't have to prevent them from doing it or go out of its way to warn them. And it's the same here. The order of the attributes is the order of the slots, so if you specify them in arbitrary order, that will be an arbitrary order, obviously.

Maybe there's something about this use case that causes people to not notice they've screwed up like this? If so, I think that's what you have to make a case for. (That's why I asked whether anyone has actually complained about it.)

One more thing: what's stopping you from defining Ordered in your module and registering all the relevant builtin types there? In fact, you pretty much have to do this even if your proposal is accepted, unless you want your module to require 3.6+ (which seems unlikely, given that you're using six). So what would you gain by having it in the stdlib?

_______________________________________________
Python-ideas mailing list
Python...@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

[Stephen J. Turnbull]

Amir Rachum writes:

> An ordered collection has the exact same interface as an unordered
> collection (e.g, dict and OrderedDict), other than a _promise_ of
> the API that the order in which this collection will be iterated
> has some sort of meaning (In OrderedDict, it is the order in which
> keys were added to it.)

I think this is underspecified. One of the main reasons why ordered
versions of initially unordered types, especially dict, take so long
to standardize is that people (even the Dutch!) disagree about the One
Obvious Order to impose. After repeated refusals, only the factions
that continue clamoring- and preferably, only one -need be considered.

This ABC would be a tar pit of recriminations between class authors
and class clients. At the very least, the author's intended
comparison function should be introspectable so that client subclasses
can include validation functions. (I guess you could just use
"lambda slot: list(self.__slots__).index(slot)" as the key function,
but that doesn't say much about the conceptual semantics.) Then the
presence of the ordering function would provide a way to duck-type
abc.Ordered.

I haven't thought carefully about it, but a method with semantics of
"insert next slot at end according to natural order" (named
"natural_append"? "ordered_append"? or maybe the existing "append"
used by sequences could be given this semantic as well?

Nevertheless, I don't think this shold be added to Python yet. I
don't think your use case is a valid one for supporting it. I have
two reasons:

(1) In principle, record types should not be initialized with
positional arguments. I experienced cogniztive dissonance as soon
as I saw your __init__():

> Here's how the current__init__ method of BasicStruct looks like:

> class BasicStruct(object):
> """Class for holding struct-like objects."""

"with naturally-ordered slots" should be appended.

> __slots__ = () # should be extended by deriving classes

> def __init__(self, *args, **kwargs):

Yes, we do it in C all the time, and it works fine[1] there. But
the semantics are mismatched at the conceptual level, and it is
error-prone in practice if the type has more than about 3 slots of
differing types. If a concrete BasicStruct "wants" to provide a
positional constructor, it can use a factory function.

Unfortunately this would be impossible to do automatically in the
exactly the cases of interest -- you need the *source code* order
of slots, but that's not available for introspection at runtime.
So it would violate DRY. I don't consider that an argument for
the proposal at the moment, but feel free to try to convince the
list (and maybe me too<wink/>) otherwise.) (In fact I consider it
the reverse: for Sequences, The Order You See Is The Order You
Get, and the DRY violation occurs *because* you are using an
inappropriate container for your purpose (ordered slots).

(2) BasicStruct isn't the relevant use case: you can always just
document that __slots__ is restricted to ordered finite iterables
except string-like ones which use sequences of length 1 to
represent individual members, and perhaps trap some of the more
obvious mistakes (set and dict and maybe their subclasses).

The use case you need to present is one where a non-Sequence (eg,
a set or dict) is the obvious representation for __slots__ in a
BasicStruct. Note that __slots__ allows nearly arbitrary finite
iterables of strings only because there's no reason not to, and it
simplifies the implementation. In Python practice, that is indeed
an invitation to experiment with concrete classes that use
unordered __slots__ for some reason. But there's no sense that
abstract classes that use __slots__ in an abstract way (as yours
does) must preserve that generality, and therefore no reason (yet)
for Python to help you preserve that generality.


Footnotes:
[1] According to the usual definition of "works fine in C": is no
more than twice as error-prone as other features of C. Given the
existence of pointers....

[Andrew Barnert via Python-ideas]

On Nov 6, 2015, at 21:00, Stephen J. Turnbull <ste...@xemacs.org> wrote:
>
> Amir Rachum writes:
>
>> An ordered collection has the exact same interface as an unordered
>> collection (e.g, dict and OrderedDict), other than a _promise_ of
>> the API that the order in which this collection will be iterated
>> has some sort of meaning (In OrderedDict, it is the order in which
>> keys were added to it.)
>
> I think this is underspecified. One of the main reasons why ordered
> versions of initially unordered types, especially dict, take so long
> to standardize is that people (even the Dutch!) disagree about the One
> Obvious Order to impose. After repeated refusals, only the factions
> that continue clamoring- and preferably, only one -need be considered.
>
> This ABC would be a tar pit of recriminations between class authors
> and class clients.

I think you've missed the point of his proposal. It doesn't matter _what_ the order is—insertion order, sorted by __lt__ (possibly with a key function), looked up by a function that maps keys to indices, whatever—only that there is some meaningful order (and that iteration follows that order). If so, your type can declare that it implements Ordered.

Of course the user has to know what that order is and what it means in order to do anything with it. In his example, if you use, say, a blist.sortedlist instead of a list for your slots, then you have to pass positional parameters to the initializer in sorted order instead of in source code order. But if that's what makes sense for your code, then great.

The reason I'm not sure it's helpful is that "ordered in some way that makes sense to me that you don't know about" isn't really that useful of a thing for you to check for me. After all, I can use a blist.sortedlist('bac') and then pass the initializer values in b-a-c order, or use list('bac') and pass them in a-b-c order. Each of those is at least as easy to screw up, and just as wrong, as using a set('bac'), and his code can't possibly check for the first two, so what's the point of checking for the third?

But, whether the proposal is useful or not, it is sufficiently specified.

> At the very least, the author's intended
> comparison function should be introspectable so that client subclasses
> can include validation functions. (I guess you could just use
> "lambda slot: list(self.__slots__).index(slot)" as the key function,
> but that doesn't say much about the conceptual semantics.) Then the
> presence of the ordering function would provide a way to duck-type
> abc.Ordered.

How would you define the comparison function for OrderedDict in a way that makes any semantic sense? Or, for that matter, list? The order is the result of a dynamic sequence of operations that nobody's kept track of and that in general can't be recovered. But it doesn't matter why the values are in some particular order, only that they are. Surely OrderedDict and list are perfectly reasonable types for __slots__, despite the fact that their comparison function doesn't exist.

> I haven't thought carefully about it, but a method with semantics of
> "insert next slot at end according to natural order" (named
> "natural_append"? "ordered_append"? or maybe the existing "append"
> used by sequences could be given this semantic as well?

You're talking about the API for a mutable sorted collection here. That's an interesting question (and I've written a blog post about it, and had long conversations with the authors of various different sorted collection libs on PyPI), but it's not relevant here. If we wanted to add sorted collection ABCs to the stdlib, that still wouldn't help the OP at all, because things like list and OrderedDict are Ordered in his sense but not sorted in any useful sense.

(If you're curious: I think the best answer is to use add. A sorted collection is more like a multiset, at least from the mutation side, than like a list. Append, insert, and __setitem__ are all nonsense; add makes perfect sense. But not everyone agrees with me. If you want to discuss this, you should probably take it off-list, or start a new thread on adding sorted collections ABCs, because they have very little to do with adding an Ordered ABC.)

> Nevertheless, I don't think this shold be added to Python yet. I
> don't think your use case is a valid one for supporting it. I have
> two reasons:
>
> (1) In principle, record types should not be initialized with
> positional arguments. I experienced cogniztive dissonance as soon
> as I saw your __init__():
>
>> Here's how the current__init__ method of BasicStruct looks like:
>
>> class BasicStruct(object):
>> """Class for holding struct-like objects."""
>
> "with naturally-ordered slots" should be appended.
>
>> __slots__ = () # should be extended by deriving classes
>
>> def __init__(self, *args, **kwargs):
>
> Yes, we do it in C all the time, and it works fine[1] there. But
> the semantics are mismatched at the conceptual level, and it is
> error-prone in practice if the type has more than about 3 slots of
> differing types

It's worth noting that the C committee agrees with you, which is why they added designated initializers to the language, which are often considered among the best upgrades from C89. Unless you need C89 support or (portable) C++ compatibility (sadly, you usually do need one or the other…), unless you're initializing something with only a few attributes with an obvious-to-the-reader order (like a point, where it's pretty clear that { 1, 2, 3 } is initializing x, y, and z), you use a designated initializer like { .spam=1, .eggs=2, .cheese=3 }. Which looks sort of like Python, but with extra line noise.

> If a concrete BasicStruct "wants" to provide a
> positional constructor, it can use a factory function.
>
> Unfortunately this would be impossible to do automatically in the
> exactly the cases of interest -- you need the *source code* order
> of slots, but that's not available for introspection at runtime.
> So it would violate DRY. I don't consider that an argument for
> the proposal at the moment, but feel free to try to convince the
> list (and maybe me too<wink/>) otherwise.) (In fact I consider it
> the reverse: for Sequences, The Order You See Is The Order You
> Get, and the DRY violation occurs *because* you are using an
> inappropriate container for your purpose (ordered slots).
>
> (2) BasicStruct isn't the relevant use case: you can always just
> document that __slots__ is restricted to ordered finite iterables

It had better be a repeatable one too; after all, iter(['a', 'b']) is an ordered finite iterable, but not a very good candidate for slots. But that's a whole other thread. :)

[Stephen J. Turnbull]

Andrew Barnert writes:
> On Nov 6, 2015, at 21:00, Stephen J. Turnbull <ste...@xemacs.org> wrote:

> > This ABC would be a tar pit of recriminations between class authors
> > and class clients.

> I think you've missed the point of his proposal. It doesn't matter
> _what_ the order is

That's precisely what I see as problematic, unless the author of the
subclass is the same as the author of the code using the subclass.

> But, whether the proposal is useful or not, it is sufficiently
> specified.

I wrote inaccurately, I guess. My contention is that it's more
dangerous than useful as currently specified but that could be
reversed with additional restrictions.

> How would you define the comparison function for OrderedDict in a
> way that makes any semantic sense? Or, for that matter, list?

Again, bad nomenclature, sorry.[1] I should have used "index". For
this application, I have in mind

class Ordered:

def index(self, key):
return list(z for z in self).index(key)

def compare(self, key1, key2):
return self.index(key1) < self.index(key2)

as the default implementation (except that for Amir's application it's
.index() that's interesting, not .compare() -- .compare() could be
omitted I guess, fn. [1] applies). The problem with list would be
that it can have multiple entries of the same value that are not
adjacent, of course, but then it wouldn't work for Amir's application
anyway. This is part of what I have in mind when I say
"underspecified".

I don't think thought about how this collections.abc.Ordered should
interact with objects that could be considered to represent multisets.
Do you?

> Surely OrderedDict and list are perfectly reasonable types for
> __slots__, despite the fact that their comparison function doesn't
> exist.

If given the above renaming you still say it doesn't exist, I don't
understand what you're trying to say.



Footnotes:
[1] As an excuse for the poor nomenclature, in my field I have to
worry about (pre-) ordered structures for which an index function does
not exist, thus "comparison function".

[Neil Girdhar]

On Saturday, November 7, 2015 at 9:42:19 AM UTC-5, Stephen J. Turnbull wrote:

Andrew Barnert writes:
 > On Nov 6, 2015, at 21:00, Stephen J. Turnbull <ste...@xemacs.org> wrote:

 > > This ABC would be a tar pit of recriminations between class authors
 > > and class clients.  

 > I think you've missed the point of his proposal. It doesn't matter
 > _what_ the order is

That's precisely what I see as problematic, unless the author of the
subclass is the same as the author of the code using the subclass.

 > But, whether the proposal is useful or not, it is sufficiently
 > specified.

I wrote inaccurately, I guess.  My contention is that it's more
dangerous than useful as currently specified but that could be
reversed with additional restrictions.

It's not "dangerous"!!  Talk about hyperbole.  It's just a question of utility.  Personally I would like to see a much richer collections.abc for tests like this.

 

 > How would you define the comparison function for OrderedDict in a
 > way that makes any semantic sense?  Or, for that matter, list?

Again, bad nomenclature, sorry.[1]  I should have used "index".  For
this application, I have in mind

class Ordered:

    def index(self, key):
        return list(z for z in self).index(key)

    def compare(self, key1, key2):
        return self.index(key1) < self.index(key2)

as the default implementation (except that for Amir's application it's
.index() that's interesting, not .compare() -- .compare() could be
omitted I guess, fn. [1] applies).  The problem with list would be
that it can have multiple entries of the same value that are not
adjacent, of course, but then it wouldn't work for Amir's application
anyway.  This is part of what I have in mind when I say
"underspecified".

I don't think thought about how this collections.abc.Ordered should
interact with objects that could be considered to represent multisets.
Do you?

Did you read the original post?  All you need is a consistent order.  It doesn't matter if the same element turns up twice in order to be Ordered.  He can check uniqueness after the fact.

[Serhiy Storchaka]

On 07.11.15 00:11, Amir Rachum wrote:
> I am suggesting the addition of a collections abstract base class called
> "Ordered". Its meaning is that a collection's iteration order is part of
> its API. The bulk of this mail describes a use case for this. The reason
> I believe that such abstract base class is required is that there is no
> way to test this behavior in a given class. An ordered collection has
> the exact same interface as an unordered collection (e.g, dict and
> OrderedDict), other than a _promise_ of the API that the order in which
> this collection will be iterated has some sort of meaning (In
> OrderedDict, it is the order in which keys were added to it.)
>
>
> As examples, set, frozenset, dict and defaultdict should *not* be
> considered as ordered. list, OrderedDict, deque and tuple should be
> considered ordered.

I just wanted to offer this idea. I have two use cases:

1. Human-readable output. If the collection is not ordered, it is
preferable to sort it before output. pprint and testing frameworks will
benefit from this.

2. Serialization. If the mapping is not ordered, we can serialize its
content as dict (that can be more efficient), otherwise we have to
serialize it as a sequence of key-value pairs.

Actually we need only two functions: test if the collection is ordered,
and a way to register the class as ordered (or unordered).

[Neil Girdhar]

FYI: 1. might not work since the elements in a dict may not be sortable.

--

---
You received this message because you are subscribed to a topic in the Google Groups "python-ideas" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/python-ideas/B1Pt76OtJi8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to python-ideas...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Andrew Barnert via Python-ideas]

On Nov 7, 2015, at 06:41, Stephen J. Turnbull <ste...@xemacs.org> wrote:
>
> Andrew Barnert writes:
>> On Nov 6, 2015, at 21:00, Stephen J. Turnbull <ste...@xemacs.org> wrote:
>
>>> This ABC would be a tar pit of recriminations between class authors
>>> and class clients.
>
>> I think you've missed the point of his proposal. It doesn't matter
>> _what_ the order is
>
> That's precisely what I see as problematic, unless the author of the
> subclass is the same as the author of the code using the subclass.
>
>> But, whether the proposal is useful or not, it is sufficiently
>> specified.
>
> I wrote inaccurately, I guess. My contention is that it's more
> dangerous than useful as currently specified but that could be
> reversed with additional restrictions.

Not very useful, sure—I argued that myself—but how is it dangerous? The only risk here is the risk that comes from adding more code, docs, and complexity to the stdlib.

>> How would you define the comparison function for OrderedDict in a
>> way that makes any semantic sense? Or, for that matter, list?
>
> Again, bad nomenclature, sorry.[1] I should have used "index". For
> this application, I have in mind
>
> class Ordered:
>
> def index(self, key):
> return list(z for z in self).index(key)
>
> def compare(self, key1, key2):
> return self.index(key1) < self.index(key2)

For, How is that at all useful? What code can you imagine that needs to compare elements from an arbitrary iterable, and would rather have a comparison that's linear in the length of the iterable than none at all?

Second, why list(z for z in self) instead of just list(self) or [z for z in self]? It seems like you're deliberately trying to find the slowest and least straightforward way of implementing it…

But, most importantly, if you want an index method, why aren't you just requiring Sequence, which has one? The notion of index implies the notion of random accessibility—which is exactly what Sequence adds on top of Sized Iterable Container.

Of course there are types for which compare might exist but index might not (e.g., a range of reals, or a set that's only partially ordered), but they're not iterables. (Well, a partially ordered set could Iterate in partially-arbitrary order, but then it's not Ordered in the OP's sense.)

His proposal really does specify exactly what he wants, it's dead simple, and it does all he asks of it. The only question is whether anyone needs it (and, even if they do, whether it needs to be in the stdlib).

> as the default implementation (except that for Amir's application it's
> .index() that's interesting, not .compare() -- .compare() could be
> omitted I guess, fn. [1] applies). The problem with list would be
> that it can have multiple entries of the same value that are not
> adjacent, of course, but then it wouldn't work for Amir's application
> anyway. This is part of what I have in mind when I say
> "underspecified".

Well, yes, what he _really_ requires here is an ordered, _unique_, finite, repeatable iterable. Adding a test for Ordered is clearly insufficient for that, and doesn't seem particularly useful. But again, that doesn't mean that Ordered is underspecified in any way; it just means he doesn't have a good use case for it.

> I don't think thought about how this collections.abc.Ordered should
> interact with objects that could be considered to represent multisets.
> Do you?

I'm not sure what you're asking here. But clearly list, OrderedCounter, and a SortedMultiSet type are all ordered, and can all be used to represent multisets in rather obvious ways. And the only way his proposed Ordered has to interact with them is that they all inherit from or get registered with the Ordered ABC (and aren't lying about it).

Of course your proposal for some kind of sorting-related ABC that generates the sort order from indexes would have a problem with multisets, and especially with list as you mentioned above, but that has nothing to do with his proposal.

>> Surely OrderedDict and list are perfectly reasonable types for
>> __slots__, despite the fact that their comparison function doesn't
>> exist.
>
> If given the above renaming you still say it doesn't exist, I don't
> understand what you're trying to say.

OK, they're perfectly reasonable types for __slots__, despite the fact that no useful, acceptably efficient, or in any way desirable comparison function exists. Better?

[Michael Selik]

Hi Amir,

Could you (or someone else) help me understand the use case for this base class? Rather than describing the use case, could you point me to somewhere in the standard library or a public project where it would clarify the code?

I currently share Andrew's concern -- knowing a thing is ordered does not help us understand *how* it's ordered. Therefore, despite an `Ordered` base class, we would still need to rely on error messages, tests, and documentation. As he said, calling this "dangerous" is not hyperbole but a proper description of how any change to the standard library will increase the maintenance burden, may reduce usability/learnability, and may have unpredictable consequences.

-- Michael

[Stephen J. Turnbull]

Andrew Barnert writes:

> Not very useful, sure—I argued that myself—but how is it
> dangerous? The only risk here is the risk that comes from adding
> more code, docs, and complexity to the stdlib.

This proposal requires that users not only read the docs in the
stdlib, but also the docs of each class, perhaps each object, using
the functionality. Asking users to read docs thoroughly is a recipe
for bugs, especially since the order used is likely to be documented
as "the natural order", and people will have different ideas about
that. This is the "complication" the Zen warns about, as well as
being "implicit". You may not consider that dangerous, but I do.

And on top of that, not only doesn't it provide any guarantees, you've
pretty much convinced me it's impossible to do so. If that's not an
attractive nuisance, what is?

> But, most importantly, if you want an index method, why aren't you
> just requiring Sequence, which has one?

Because "ordered sets" and "ordered dicts" aren't Sequences.

But don't ask me, ask the OP. As I wrote earlier, no use case for
set- or dict-valued __slots__ has been given. I have nothing invested
in anything I wrote except that. I'm happy to concede that everything
else I wrote was boneheaded, retract it, and apologize for wasting
your time.

[Guido van Rossum]

I'm warming up slightly to the idea of this ABC.

I've re-read Amir's post, and if I found myself in his situation I would have used a combination of documenting that __slots__ needs to be ordered and at runtime only checking for a few common definitely-bad cases. E.g. for exactly set or dict (not subclasses, since OrderedDict inherits from dict) would cover most of the common mistakes: most people will use a literal in their __slots__ definition so we just need to watch out for the common literals. Those users who are sophisticated enough to use some advanced mapping type in their __slots__ should just be expected to deal with the consequences.

But the Ordered ABC, while not essential (unless you're a perfectionist, in which case you're in the wrong language community anyways :-) still fills a niche.

The Ordered ABC should have no additional methods, and no default implementations. I think it should apply to collections but not to iterators. It should apply at the level of the read-only interface. Sequence is always Ordered. Mapping and Set are not by default, but can have it added. OrderedDict is the prime (maybe only) example -- it's a MutableMapping and Ordered. We might eventually get an OrderedSet.

A sorted set or mapping (e.g. one implemented using some kind of tree) should also be considered Ordered, even though otherwise this is a totally different topic -- while some other languages or branches of math use "order" to refer to sorting (e.g. "partial ordering"), in Python we make a distinction: on the one hand there's sorted() and list.sort(), and on the other hand there's OrderedDict.

So, I think that the Ordered ABC proposed here is totally well-defined and mildly useful. It may be somewhat confusing (because many people when they first encounter the term "ordered" they think it's about sorting -- witness some posts in this thread). The use cases are not very important. I guess I'm -0 on adding it -- if better use cases than Amir's are developed I might change to +0. (I don't care much about Serhiy's use cases.)

Sorry for the rambling.

--

--Guido van Rossum (python.org/~guido)

[Amir Rachum]

I would like to expand on my original use case, which I hope will provide a more persuading argument.

As part of BasicStruct I intend to allow the use of mapping types as __slots__, with the semantics of default values.

So it'll look something like this:

    class Point(BasicStruct):

        __slots__ = {'x': 5, 'y': 7}

My fear is that someone will just use a dict literal as stated above and try to create an object with positional arguments:

    Point(0)

The problem is that iteration order over a dict is not guaranteed, so this might initialize Point(x=0, y=7) like the use intends, or Point(x=5, y=0). So in this case I want to disable positional arguments. However, positional arguments for initializing struct are pretty convenient, so I would like to make that available as far as possible. An implementation using Ordered might look like this:

    class BasicStruct(object):

        """Class for holding struct-like objects."""

        __slots__ = ()  # should be extended by deriving classes

        def __init__(self, *args, **kwargs):

            default_values = isinstance(self.__slots__, Mapping)

            ordered = isinstance(self.__slots__, Ordered)

            if args and not ordered:

                raise ValueError("Can't pass non-keyword arguments to {}, since "

                                 "__slots__ was declared with an unordered "

                                 "iterable.".format(self.__class__.__name__))

            arg_pairs = zip(self.__slots__, args)

            for key, value in chain(arg_pairs, six.iteritems(kwargs)):

                setattr(self, key, value)

            for key in self.__slots__:

                if not hasattr(self, key):

                    default_value = None

                    if default_values:

                        default_value = self.__slots__[key]

                    setattr(self, key, default_value)

This will allow users who are interested in positional argument initialization to use an Ordered mapping (such as OrderedDict, or a custom collection).

I would like to emphasize again that the most compelling reason for me that this should be part of the stdlib is that there is no workaround for this that also allows users to use ordered custom collections. There is no way to check for "promised ordering" in any functional manner.

[Neil Girdhar]

Did you know that you can register your custom collection with an abc? 

--

---
You received this message because you are subscribed to a topic in the Google Groups "python-ideas" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/python-ideas/B1Pt76OtJi8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to python-ideas...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

_______________________________________________
Python-ideas mailing list
Python...@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

[Sjoerd Job Postmus]

On 8 Nov 2015, at 20:06, Amir Rachum <am...@rachum.com> wrote:

I would like to expand on my original use case, which I hope will provide a more persuading argument.

As part of BasicStruct I intend to allow the use of mapping types as __slots__, with the semantics of default values.

So it'll look something like this:

    class Point(BasicStruct):

        __slots__ = {'x': 5, 'y': 7}

So instead they'll write

    __slots__ = OrderedDict({'x': 5, 'y': 7})

Causing the same issues?

My fear is that someone will just use a dict literal as stated above and try to create an object with positional arguments:

    Point(0)

The problem is that iteration order over a dict is not guaranteed, so this might initialize Point(x=0, y=7) like the use intends, or Point(x=5, y=0). So in this case I want to disable positional arguments. However, positional arguments for initializing struct are pretty convenient, so I would like to make that available as far as possible. An implementation using Ordered might look like this:

    class BasicStruct(object):

        """Class for holding struct-like objects."""

        __slots__ = ()  # should be extended by deriving classes

        def __init__(self, *args, **kwargs):

            default_values = isinstance(self.__slots__, Mapping)

            ordered = isinstance(self.__slots__, Ordered)

            if args and not ordered:

                raise ValueError("Can't pass non-keyword arguments to {}, since "

                                 "__slots__ was declared with an unordered "

                                 "iterable.".format(self.__class__.__name__))

            arg_pairs = zip(self.__slots__, args)

            for key, value in chain(arg_pairs, six.iteritems(kwargs)):

                setattr(self, key, value)

            for key in self.__slots__:

                if not hasattr(self, key):

                    default_value = None

                    if default_values:

                        default_value = self.__slots__[key]

                    setattr(self, key, default_value)

This will allow users who are interested in positional argument initialization to use an Ordered mapping (such as OrderedDict, or a custom collection).

I would like to emphasize again that the most compelling reason for me that this should be part of the stdlib is that there is no workaround for this that also allows users to use ordered custom collections. There is no way to check for "promised ordering" in any functional manner.

Besides the fact that you can create that base-class yourself, and register OrderedDict as an instance of it already, I think there's a better solution to your problem (not quite tested, but should work):

1. Create a Field class which maintains a creation-counter to be able to query ordering.

2. In the __init__ check against the creation ordering.

Added bonus: you can choose to have some attributes have a default value, and others not having a default value. 

If you're willing to do some metaclass trickery, you could even end up with a syntax like:

    class Point(Struct):

        x = Field(5)

        y = Field(7)

        z = Field()  # we force the user to supply the z value, as it has no default. 

And generate the __slots__ from that. Maybe look at Django's ModelBase implementation, and how it uses metaclasses for that?

Even more added bonus would be defining special Field sub-classes which also check the type/value of the supplied values (NumericField raising ValueError when you pass it the string "foo").

Not really sure what the added benefit of an Ordered base-class would be here.

[Serhiy Storchaka]

On 08.11.15 23:12, Sjoerd Job Postmus wrote:
> On 8 Nov 2015, at 20:06, Amir Rachum <am...@rachum.com

> <mailto:am...@rachum.com>> wrote:
>> As part of BasicStruct I intend to allow the use of mapping types as

>> __slots__, with the semantics of default values..

>> So it'll look something like this:
>>
>> class Point(BasicStruct):
>> __slots__ = {'x': 5, 'y': 7}
>
> So instead they'll write
> __slots__ = OrderedDict({'x': 5, 'y': 7})
> Causing the same issues?

Perhaps OrderedDict should reject unordered sources. Hey, here is yet
one use case!

[Andrew Barnert via Python-ideas]

On Nov 8, 2015, at 14:10, Serhiy Storchaka <stor...@gmail.com> wrote:
>
>> On 08.11.15 23:12, Sjoerd Job Postmus wrote:
>> On 8 Nov 2015, at 20:06, Amir Rachum <am...@rachum.com
>> <mailto:am...@rachum.com>> wrote:
>>> As part of BasicStruct I intend to allow the use of mapping types as
>>> __slots__, with the semantics of default values..
>>> So it'll look something like this:
>>>
>>> class Point(BasicStruct):
>>> __slots__ = {'x': 5, 'y': 7}
>>
>> So instead they'll write
>> __slots__ = OrderedDict({'x': 5, 'y': 7})
>> Causing the same issues?
>
> Perhaps OrderedDict should reject unordered sources. Hey, here is yet one use case!

I've maintained code that does this:

self.headers = OrderedDict(headers)
self.origheaders = len(headers)

… so it can later do this:

altheaders = list(self.headers.items())[self.origheaders:]

Not a great design, but one that exists in the wild, and would be broken by OrderedDict not allowing a dict as an argument.

Also, this wouldn't allow creating an OrderedDict from an empty dict (which seems far less stupid, but I didn't lead with it because I can't remember seeing it in real code).

[Guido van Rossum]

So if OrderedDict had always rejected construction from a dict, how would you have written this?

--
--Guido (mobile)

[Ram Rachum]

I'm not Andrew, but I'm guessing simply writing `OrderedDict(headers.items())`.

[Guido van Rossum]

Well, that would still defeat the purpose, wouldn't it? The items are no more ordered than the headers dict itself. Also, items() doesn't return a sequence -- it's an ItemsView (which inherits from Set) and presumably it's not Ordered.

I guess my question is not so much how to prevent getting an exception -- I'm trying to tease out what the right order for the headers would be. Or perhaps I'm just trying to understand what the code is doing (the snippet shown mostly looks like bad code to me).

[Michael Selik]

I found a use case, out in the wild!

I've been searching through GitHub for "ordered" and similar phrases.
Much of the usage is OrderedDict and OrderedSet, which really don't
benefit from an essentially redundant inheritance from a hypothetical
collections.Ordered. There are some tools that enable UI reordering,
and a bunch of tree- and graph-traversal ordering functions. Again,
not much benefit from a collections.Ordered.

However, Django has a class factory that creates an attribute `can_order`:

def formset_factory(form, formset=BaseFormSet, extra=1, can_order=False,
can_delete=False, max_num=None, validate_max=False,
min_num=None, validate_min=False):
"""Return a FormSet for the given form class."""
if min_num is None:
min_num = DEFAULT_MIN_NUM
if max_num is None:
max_num = DEFAULT_MAX_NUM
# hard limit on forms instantiated, to prevent memory-exhaustion attacks
# limit is simply max_num + DEFAULT_MAX_NUM (which is 2*DEFAULT_MAX_NUM
# if max_num is None in the first place)
absolute_max = max_num + DEFAULT_MAX_NUM
attrs = {'form': form, 'extra': extra,
'can_order': can_order, 'can_delete': can_delete,
'min_num': min_num, 'max_num': max_num,
'absolute_max': absolute_max, 'validate_min': validate_min,
'validate_max': validate_max}
return type(form.__name__ + str('FormSet'), (formset,), attrs)

This attribute gets set in several places, but checked only twice in
the Django codebase. Unfortunately, I think switching to the proposed
inheritance mechanism would make the code worse, not better:
`self.can_order` would become `isinstance(self, collections.Ordered)`.
The readability of the Django internal code would not be much
different, but users would lose consistency of introspectability as
the other features like `can_delete` are simple class attributes.

[Guido van Rossum]

Hm, this just indicates whether some UI appears by which the user can reorder the forms in a list? Is it even appropriate to move this from the instance to the class?

[Michael Selik]

If my thoughts got lost in the mess of text: No, I don't think it is appropriate.

[Stephen J. Turnbull]

Guido van Rossum writes:

> I guess my question is not so much how to prevent getting an
> exception -- I'm trying to tease out what the right order for the
> headers would be.

If they are email headers, then each MTA is supposed to *prepend* its
trace fields (Received and friends) to the existing header block.
Those new fields would correspond to Andrew's "alternate" headers.

Perhaps you are thinking of the fact that MTAs are also supposed to
preserve the existing order of headers. However, the mail system as a
whole is in practice not reliable because of intermediating agents
like mailing lists and user forwarding. These sometimes insert
application fields (such as List-* and Resent-*) before the trace
fields block rather than prepend their fields to the existing header.
As an indication of this lack of reliability, DKIM does not prescribe
a set or block of fields to sign, but rather the fields to sign are
specified as a sequence in the DKIM-Signature header, and verifiers
must extract and append the fields to the content to be signed in that
order regardless of physical order.

Python's email package provides a header abstraction which is an
ordered mapping. The point is to be able to reproduce the entire
message with full accuracy by Message.flatten() (ie, without affecting
signatures). So the relevant order is order found in the input
message (ie, FIFO). However, this order is not stable in the sense
required by the OP of this thread: existing fields may be deleted and
new ones inserted at arbitrary positions. Nor does it refer to any
externally-defined collation order for fields.

BTW, I do understand the difference between sorting and ordering.
What I missed is that that Amir (the OP) didn't ask for his
BasicStruct to be Ordered (although I guess it would be, considered as
a container for its slots); he wants to check that the initializer for
__slots__ is Ordered.

But that is insufficient in this use case (an alphabetically-ordered
instance would be a problematic initializer: consider a derived
BasicStruct that adds members to its parent BasicStruct). I still
question the general usefulness of this ABC on the one hand, and ask
how far to proliferate its more useful subclasses on the other.

[Andrew Barnert via Python-ideas]

On Nov 8, 2015, at 20:28, Guido van Rossum <gu...@python.org> wrote:

So if OrderedDict had always rejected construction from a dict, how would you have written this?

Well, I wouldn't have written it this way in the first place. The obvious way to do it is to store the original headers and new headers separately. ChainMapping two dicts together is much more obvious than cramming them into one OrderedDict and keeping track of where the dividing index is. So, I'd do this:

    self.original_headers = copy.copy(headers)

    self.alt_headers = OrderedDict()

    self.headers = ChainMap(self.alt_headers, self.original_headers)

Now origheaders is just len(self.original_headers), altheaders is self.alt_headers.items().

I didn't make this change to the code in question because it worked, and had no edits for over 2 years, and it only took me a couple minutes to figure out what it was doing, so it made more sense just to leave it alone.

If Python 3.7 forced me to change it by not allowing OrderedDict to be constructed from a dict, I'd have to decide whether to make this change, or the obvious mechanical fix of just calling OrderedDict on iter(headers.items()) instead of headers to trick the Ordered check.

By the way, the fact that this simple mechanical workaround works, and provides no additional semantics to tell the reader what's going on, seems like a minor strike against the proposal. (And if you ban iterators too, I'd just change the iter(…) to list(…).) All Ordered can really check is that the type provides some way to preserve a meaningful order, not that the data really are meaningfully ordered, after all.

[Serhiy Storchaka]

On 07.11.15 00:11, Amir Rachum wrote:

> I am suggesting the addition of a collections abstract base class called
> "Ordered". Its meaning is that a collection's iteration order is part of
> its API. The bulk of this mail describes a use case for this. The reason
> I believe that such abstract base class is required is that there is no
> way to test this behavior in a given class. An ordered collection has
> the exact same interface as an unordered collection (e.g, dict and
> OrderedDict), other than a _promise_ of the API that the order in which
> this collection will be iterated has some sort of meaning (In
> OrderedDict, it is the order in which keys were added to it.)
>
> As examples, set, frozenset, dict and defaultdict should *not* be
> considered as ordered. list, OrderedDict, deque and tuple should be
> considered ordered.

Actually we already have such abstract class. It's typing.Reversible.
Iterating non-ordered collection doesn't make sense.

>>> issubclass(list, typing.Reversible)
True
>>> issubclass(collections.deque, typing.Reversible)
True
>>> issubclass(collections.OrderedDict, typing.Reversible)
True
>>> issubclass(type(collections.OrderedDict().items()),
typing.Reversible)
True
>>> issubclass(dict, typing.Reversible)
False
>>> issubclass(set, typing.Reversible)
False
>>> issubclass(frozenset, typing.Reversible)
False
>>> issubclass(collections.defaultdict, typing.Reversible)
False
>>> issubclass(type({}.items()), typing.Reversible)
False

Unfortunately the test returns False for tuple, str, bytes, bytearray,
and array:

>>> issubclass(tuple, typing.Reversible)
False
>>> issubclass(str, typing.Reversible)
False
>>> issubclass(bytes, typing.Reversible)
False
>>> issubclass(bytearray, typing.Reversible)
False
>>> issubclass(array.array, typing.Reversible)
False

This looks as a bug in typing.Reversible.

[Wes Turner]

"[Python-ideas] OrderedCounter and OrderedDefaultDict"
https://mail.python.org/pipermail/python-ideas/2015-November/037163.html

- +2 for collections.ABC.Ordered
- exception on initialization w/ an unordered collection /// __init__force_from_unordered

[Wes Turner]

On Nov 8, 2015 1:46 PM, "Guido van Rossum" <gu...@python.org> wrote:
>
> I'm warming up slightly to the idea of this ABC.
>
> I've re-read Amir's post, and if I found myself in his situation I would have used a combination of documenting that __slots__ needs to be ordered and at runtime only checking for a few common definitely-bad cases. E.g. for exactly set or dict (not subclasses, since OrderedDict inherits from dict) would cover most of the common mistakes: most people will use a literal in their __slots__ definition so we just need to watch out for the common literals. Those users who are sophisticated enough to use some advanced mapping type in their __slots__ should just be expected to deal with the consequences.
>
> But the Ordered ABC, while not essential (unless you're a perfectionist, in which case you're in the wrong language community anyways :-) still fills a niche.

I take issue with this comment because it's in the middle of the text.

It's more than a perfection thing:

- Ordered collections may already be Sorted [1]

- [ ] would collectiond.namedtuple [~struct w/ slots] also be Ordered

- [1] here's a rejected PR for jupyter/nbformat https://github.com/jupyter/nbformat/pull/30 "ENH: v4/nbjson.py: json.loads(object_pairs_hook=collections.OrderedDict)"

>
> The Ordered ABC should have no additional methods, and no default implementations. I think it should apply to collections but not to iterators. It should apply at the level of the read-only interface. Sequence is always Ordered. Mapping and Set are not by default, but can have it added. OrderedDict is the prime (maybe only) example -- it's a MutableMapping and Ordered. We might eventually get an OrderedSet.
>
> A sorted set or mapping (e.g. one implemented using some kind of tree) should also be considered Ordered, even though otherwise this is a totally different topic -- while some other languages or branches of math use "order" to refer to sorting (e.g. "partial ordering"), in Python we make a distinction: on the one hand there's sorted() and list.sort(), and on the other hand there's OrderedDict.
>
> So, I think that the Ordered ABC proposed here is totally well-defined and mildly useful. It may be somewhat confusing (because many people when they first encounter the term "ordered" they think it's about sorting -- witness some posts in this thread). The use cases are not very important. I guess I'm -0 on adding it -- if better use cases than Amir's are developed I might change to +0. (I don't care much about Serhiy's use cases.)
>
> Sorry for the rambling.
>
> --
> --Guido van Rossum (python.org/~guido)
>

[Guido van Rossum]

Is there also a collections.Reversible? Either way, can you report that bug in the typehinting tracker on GitHub.

--Guido (mobile)

[Serhiy Storchaka]

On 26.12.15 18:43, Guido van Rossum wrote:
> Is there also a collections.Reversible? Either way, can you report that
> bug in the typehinting tracker on GitHub.

Ah, I didn't know there is the typehinting tracker. I had reported this
on CPython tracker in the comment to issue #25864 [1] (the issue itself
is related to Reversible too).

What is the address of the typehinting tracker?

[1] http://bugs.python.org/issue25864#msg256910

[Guido van Rossum]

https://github.com/ambv/typehinting

--Guido (mobile)

[Andrew Barnert via Python-ideas]

On Dec 26, 2015, at 04:00, Serhiy Storchaka <stor...@gmail.com> wrote:
>
>> On 07.11.15 00:11, Amir Rachum wrote:
>> I am suggesting the addition of a collections abstract base class called
>> "Ordered". Its meaning is that a collection's iteration order is part of
>> its API. The bulk of this mail describes a use case for this. The reason
>> I believe that such abstract base class is required is that there is no
>> way to test this behavior in a given class. An ordered collection has
>> the exact same interface as an unordered collection (e.g, dict and
>> OrderedDict), other than a _promise_ of the API that the order in which
>> this collection will be iterated has some sort of meaning (In
>> OrderedDict, it is the order in which keys were added to it.)
>>
>> As examples, set, frozenset, dict and defaultdict should *not* be
>> considered as ordered. list, OrderedDict, deque and tuple should be
>> considered ordered.
>
> Actually we already have such abstract class. It's typing.Reversible.

But surely an infinite list, for example, is ordered but not reversible.

Also, typing types aren't abstract base classes--one is for static type checking, the other for runtime tests. Of course they're closely related, but if they were the same thing, we wouldn't need a separate module for typing in the first place.

Of course there's nothing stopping us from adding collections.abc.Reversible, but that still doesn't solve the problem that not all ordered things are reversible. (I still don't think Ordered is necessary--but if it is, I don't think Reversible being kind of close helps, any more than Sequence and Iterable both being kind of close helps.)

> Unfortunately the test returns False for tuple, str, bytes, bytearray, and array:

It's defined (and implemented) as testing for the presence of __reversed__. But the reverse function works on types that don't implement __reversed__ if they implement the old-style sequence protocol, which can't be tested structurally.

Iterable is defined similarly, but it's a supertype of Sequence, and all of those builtin types get registered explicitly with Sequence (as some third-party types do), so they're all Iterable too.

The obvious fix is to make Reversible a subtype of Iterable, and Sequence a subtype of Reversible instead of Iterable. That would fix tuple, str, and all the other types that are registered explicitly with Sequence or MutableSequence.

This still doesn't cover OrderedDict and friends, but they could be explicitly registered with Reversible.

I think for any solution to work with static typing, you'd also need to change the hierarchy in typing to parallel the new hierarchy in collections.abc, and change typing.Reversible to use collections.abc.Reversible as its "extra".

One last thing: issue 25864, about all mappings except dict and its subclasses accidentally (and incorrectly) implementing the old-style sequence protocol well enough that when you call reverse on them, you successfully get an unusable iterator, instead of getting a TypeError. The only obvious fix is to add a __reversed__ that raises. But, as you pointed out there, that makes the problem with typing.Reversible (and any collections.abc.Reversible) worse. Currently, by being overly strict, Reversible happens to fail on Mapping subclasses, for the same reason it fails on things that actually _are_ properly reversible. I'm not sure what the solution is there. Fixing both Reversible and Mapping will accidentally make all
Mappings statically pass as Reversible, which we definitely don't want. Maybe we need a way to explicitly mark (for type checking) that a method isn't implemented, or to explicitly "unregister" from an ABC and/or typing type that takes precedence over structural checks?

[Guido van Rossum]

There is a precedent for declaring that a method isn't implemented: __hash__. The convention is to set it to None in the subclass that explicitly doesn't want to implement it. The __subclasshook__ in collections.Hashable checks for this. The pattern is also used for __await__.

[Ben Finney]

Guido van Rossum <gu...@python.org> writes:

> There is a precedent for declaring that a method isn't implemented:
> __hash__. The convention is to set it to None in the subclass that
> explicitly doesn't want to implement it.

Isn't ‘raise NotImplementedError’ the more explicit convention provided
by Python (as a built-in, explicitly-named exception!) for communicating
this meaning?

--
\ “[It's] best to confuse only one issue at a time.” —Brian W. |
`\ Kernighan, Dennis M. Ritchie, _The C programming language_, 1988 |
_o__) |
Ben Finney

[Guido van Rossum]

No, raising NotImplementedError means that a subclass was supposed to implement the method. In this case it's different -- it should appear as if the method isn't implemented to code that checks for the method's presence. Introspecting whether the code raises NotImplementedError is unfeasible. We explicitly decided that setting the method to None indicates that it should be considered as absent by code that checks for the method's presence.

[Ben Finney]

Guido van Rossum <gu...@python.org> writes:

> No, raising NotImplementedError means that a subclass was supposed to
> implement the method. In this case it's different -- it should appear
> as if the method isn't implemented to code that checks for the
> method's presence.

Understood, thanks for explaining the difference.

> Introspecting whether the code raises NotImplementedError is
> unfeasible. We explicitly decided that setting the method to None
> indicates that it should be considered as absent by code that checks
> for the method's presence.

Oh, you mean setting the attribute so it's not a method at all but a
simple non-callable object? That makes sense.

Why recommend ‘None’, though? We now have the ‘NotImplemented’ object;
why not set the attribute of the class as ‘foo = NotImplemented’?

--
\ “We are stuck with technology when what we really want is just |
`\ stuff that works.” —Douglas Adams |

[Andrew Barnert via Python-ideas]

On Dec 26, 2015, at 15:05, Guido van Rossum <gu...@python.org> wrote:
>
> There is a precedent for declaring that a method isn't implemented: __hash__. The convention is to set it to None in the subclass that explicitly doesn't want to implement it. The __subclasshook__ in collections.Hashable checks for this. The pattern is also used for __await__.

Well, that makes things a lot simpler.

But getting back to Serhiy's point: would a `collections.abc.Reversible` (with this fix) solve the need for Ordered, and, if so, should it be added?

[Serhiy Storchaka]

On 27.12.15 01:05, Guido van Rossum wrote:
> There is a precedent for declaring that a method isn't implemented:
> __hash__. The convention is to set it to None in the subclass that
> explicitly doesn't want to implement it. The __subclasshook__ in
> collections.Hashable checks for this. The pattern is also used for
> __await__.

Yes, this was the first thing that I tried, but it doesn't work, as
shown in my example in issue25864. This is yet one thing that should be
fixed in Reversible.

May be we have to use this idiom more widely, and specially handle
assigning special methods to None. The error message "'sometype' can't
be reverted" looks better than "'NoneType' is not callable".

[Guido van Rossum]

On Sat, Dec 26, 2015 at 4:33 PM, Ben Finney <ben+p...@benfinney.id.au> wrote:

Guido van Rossum <gu...@python.org> writes:

> No, raising NotImplementedError means that a subclass was supposed to
> implement the method. In this case it's different -- it should appear
> as if the method isn't implemented to code that checks for the
> method's presence.

Understood, thanks for explaining the difference.

> Introspecting whether the code raises NotImplementedError is
> unfeasible. We explicitly decided that setting the method to None
> indicates that it should be considered as absent by code that checks
> for the method's presence.

Oh, you mean setting the attribute so it's not a method at all but a
simple non-callable object? That makes sense.

Why recommend ‘None’, though? We now have the ‘NotImplemented’ object;
why not set the attribute of the class as ‘foo = NotImplemented’?

Too late by many language releases, and not worth fixing. Either way it's an arbitrary token that you would have to check for specially and whose meaning you'd have to look up. Also, NotImplemented has very special semantics (its main use is for *binary* operators to indicate "not overloaded on this argument, try the other") -- this has nothing to do with that.

(If I had to do it over again, I'd choose more different names for the exception you raise to indicate that a method should be implemented by a subclass, and the value you return to indicate that the other argument of a binary operator should be given a chance. But that's also too late by many releases.)

[Ben Finney]

Guido van Rossum <gu...@python.org> writes:

> On Sat, Dec 26, 2015 at 4:33 PM, Ben Finney <ben+p...@benfinney.id.au>
> wrote:
>
> > Why recommend ‘None’, though? We now have the ‘NotImplemented’
> > object; why not set the attribute of the class as ‘foo =
> > NotImplemented’?
>
> Too late by many language releases, and not worth fixing.

Yes, to be clear I'm not suggesting a change of ‘__hash__ = None’.

I am talking of new code, like the changes being discussed in this
thread: since we have ‘NotImplemented’ now, we can more explicitly
indicate not-implemented attributes with ‘foo = NotImplemented’.

> Either way it's an arbitrary token that you would have to check for
> specially and whose meaning you'd have to look up. Also,
> NotImplemented has very special semantics (its main use is for
> *binary* operators to indicate "not overloaded on this argument, try
> the other") -- this has nothing to do with that.

Okay, that's clear. Semantics can change over time, though, and I think
‘NotImplemented’ much more clearly indicates the desired semantics than
‘None’, and is not ambiguous with existing uses of ‘foo = None’ on a
class.

So I advocate a class-level ‘foo = NotImplemented’ as an obvious way to
indicate an expected method is not implemented on this class.

Thanks for discussing and explaining. My vote counts for whatever it
counts for, and I'll let these arguments stand or fall as I've presented
them.

--
\ “Every sentence I utter must be understood not as an |
`\ affirmation, but as a question.” —Niels Bohr |

[Andrew Barnert via Python-ideas]

On Dec 26, 2015, at 16:09, Serhiy Storchaka <stor...@gmail.com> wrote:
>
>> On 27.12.15 01:05, Guido van Rossum wrote:
>> There is a precedent for declaring that a method isn't implemented:
>> __hash__. The convention is to set it to None in the subclass that
>> explicitly doesn't want to implement it. The __subclasshook__ in
>> collections.Hashable checks for this. The pattern is also used for
>> __await__.
>
> Yes, this was the first thing that I tried, but it doesn't work, as shown in my example in issue25864. This is yet one thing that should be fixed in Reversible.

As Guido pointed out in your typehinting #170, that isn't a bug with typing.Reversible. You can't use typing types in runtime type tests with issubclass. That isn't supposed to work, and the fact that it often kind of does work is actually a bug that he's fixing. So the fact that it doesn't work in this case is correct.

That also means your attempted solution to this thread is wrong; typing.Reversible cannot be used as a substitute for collections.abc.Ordered.

> May be we have to use this idiom more widely, and specially handle assigning special methods to None. The error message "'sometype' can't be reverted" looks better than "'NoneType' is not callable".

I agree with this. A new collections.abc.Reversible (interposed between Iterable and Sequence) would be a potential substitute for Ordered, and would have this problem, which would be solvable by treating __reversed__ = None specially, just like __hash__ = None. And I'm pretty sure it would come up in practice (see issue 25864). And once we've got two or three special methods doing this instead of one, making it more general does sound like a good idea. So, if we need Reversible as a substitute for Ordered, then I think we want the general "is None" test.

But I'm still not sure Reversible is a good substitute for Ordered (again, consider an infinitely long collection, or just a lazy proxy that doesn't compute values until needed and doesn't know its length in advance--they're clearly ordered, and just as clearly not reversible), and I'm not sure we actually need either Reversible or Ordered in the first place.

[Wes Turner]

* collections.abc.Ordered
* collections.abc.Reversible
* collections.abc.Infinite [...]

* collections.abc.Sorted ?

[Chris Angelico]

On Sun, Dec 27, 2015 at 11:34 AM, Wes Turner <wes.t...@gmail.com> wrote:
> * collections.abc.Ordered
> * collections.abc.Reversible
> * collections.abc.Infinite [...]
>
> * collections.abc.Sorted ?

-1. Can you imagine trying to explain to everyone what the difference
is between Ordered and Sorted? (My understanding is that Ordered has
an inherent order, and Sorted will maintain an externally-defined
order, but I might be wrong.)

ChrisA

[Wes Turner]

* collections.abc.Ordered
* collections.abc.Reversible
* collections.abc.Infinite [...]

* collections.abc.Sorted ?
* collections.abc.Recursive ?

Rationale:

These are all attributes of collections that would allow us to reason about [complexity, types, runtime]?

[While someone is at it, annotating functions and methods with complexity class URI fragments accessible at runtime could also be useful for [dynamic programming].]

* Ordered is justified by this thread
* Reversible is distinct from Ordered (because Infinite sequences)
* Infinite is the distinction between Ordered and Reversible

* collections.abc.Sorted would be a useful property to keep track of (because then you don't have to do element-wise comparisons for each collection member)

...

* collections.abc.Recursive could also be a useful property to mixin [again for dynamic programming]

https://en.wikipedia.org/wiki/Dynamic_programming

[Wes Turner]

On Dec 26, 2015 8:11 PM, "Wes Turner" <wes.t...@gmail.com> wrote:
>
> * collections.abc.Ordered
> * collections.abc.Reversible
> * collections.abc.Infinite [...]
>
> * collections.abc.Sorted ?

> * collections.abc.Recursive ?
>
> Rationale:
>
> These are all attributes of collections that would allow us to reason about [complexity, types, runtime]?
>
> [While someone is at it, annotating functions and methods with complexity class URI fragments accessible at runtime could also be useful for [dynamic programming].]
>
> * Ordered is justified by this thread
> * Reversible is distinct from Ordered (because Infinite sequences)
> * Infinite is the distinction between Ordered and Reversible
>
> * collections.abc.Sorted would be a useful property to keep track of (because then you don't have to do element-wise comparisons for each collection member)
>
> ...
>
> * collections.abc.Recursive could also be a useful property to mixin [again for dynamic programming]
>
> https://en.wikipedia.org/wiki/Dynamic_programming

https://en.wikipedia.org/wiki/Goal_programming

There are more properties of sequences listed here; IDK if this is out of scope for OT: https://en.wikipedia.org/wiki/Sequence#Formal_definition_and_basic_properties

Vague use case: algorithmic selection / unhalting-avoidance with combinatorial data/logic sequences. [e.g. find the fastest halting solution]

Practically, Ordered is a property of various types [e.g. is this a poset or not]. There is currently no way to check for .ordered with hasattr.

These properties are things we currently keep in mind (some of our 7±2 things) and haven't yet figured out how to annotate with and access at runtime.

[Guido van Rossum]

On Sat, Dec 26, 2015 at 5:09 PM, Serhiy Storchaka <stor...@gmail.com> wrote:

On 27.12.15 01:05, Guido van Rossum wrote:

There is a precedent for declaring that a method isn't implemented:
__hash__. The convention is to set it to None in the subclass that
explicitly doesn't want to implement it. The __subclasshook__ in
collections.Hashable checks for this. The pattern is also used for
__await__.

Yes, this was the first thing that I tried, but it doesn't work, as shown in my example in issue25864. This is yet one thing that should be fixed in Reversible.

Yeah, sorry, I didn't mean it already works. I just meant that we should adopt the same convention here.

 

May be we have to use this idiom more widely, and specially handle assigning special methods to None. The error message "'sometype' can't be reverted" looks better than "'NoneType' is not callable".

Yes, that's what I'm proposing. Just like hash() says "TypeError: unhashable type: 'list'" instead of "TypeError: 'NoneType' object is not callable" or "AttributeError: 'list' object has no attribute '__hash__'".

[Guido van Rossum]

Thanks. I'm not convinced -- I think you're trying too hard to invent a special protocol for a pretty obscure corner case.

[Steven D'Aprano]

On Sat, Dec 26, 2015 at 07:11:59PM -0600, Wes Turner wrote:

> * collections.abc.Ordered
> * collections.abc.Reversible
> * collections.abc.Infinite [...]
>
> * collections.abc.Sorted ?

> * collections.abc.Recursive ?
>
> Rationale:
>
> These are all attributes of collections that would allow us to reason about
> [complexity, types, runtime]?

Rather than vague abstractions like "reason about complexity", can we
have some concrete use-cases for these?

"Sorted" is not strictly property of the collection alone, it is a
property of the collection, the item in the collection, and a sorting
function. The collection cannot be Sorted unless the items themselves
are Sortable, which is clearly a property of the items, not the
collection; and whether or not the collection actually is sorted or not
depends on what you are sorting by.

So ["apple", "bear", "cat", "do"] may or may not be sorted. If you mean
"sorted in dictionary order", it is, but if you mean "sorted by the
length of the word", it most certainly is not. If abc.Sorted only
considers the default sort order, it will be useless for many purposes.

Just this morning I was writing some code where I needed a sequence of
2-tuples sorted in reverse order (highest to lowest) by the second item
and by the length of the first item, in that order. For my purposes,
this list would count as Sorted:

[("dog", 9.2), ("apple", 7.5), ("aardvark", 7.5), ("dog", 4.1)]

How does your abc.Sorted help me?

> [While someone is at it, annotating functions and methods with complexity
> class URI fragments accessible at runtime could also be useful for [dynamic
> programming].]

I'm afraid I don't understand what you mean by "complexity class URI
fragments", or why they would be useful for dynamic programming.

> * Ordered is justified by this thread
> * Reversible is distinct from Ordered (because Infinite sequences)
> * Infinite is the distinction between Ordered and Reversible

Where do you put something which has indefinite length? It's not
infinite, but you don't know how long it is. For example:

def gen():
while random.random() < 0.5:
yield "spam"

Obviously this isn't a collection, as such, its an iterator, but I could
write a lazy collection which similarly has a finite but indefinite
length that isn't known ahead of time and so can't be reversed.
Something like a stream of data coming from an external device perhaps?
You can't reverse it, not because it is infinite, but because you don't
know how far forward to go to get the last item.



--
Steve

[Steven D'Aprano]

On Sun, Dec 27, 2015 at 11:36:30AM +1100, Chris Angelico wrote:
> On Sun, Dec 27, 2015 at 11:34 AM, Wes Turner <wes.t...@gmail.com> wrote:
> > * collections.abc.Ordered
> > * collections.abc.Reversible
> > * collections.abc.Infinite [...]
> >
> > * collections.abc.Sorted ?
>
> -1. Can you imagine trying to explain to everyone what the difference
> is between Ordered and Sorted? (My understanding is that Ordered has
> an inherent order, and Sorted will maintain an externally-defined
> order, but I might be wrong.)

The same problem comes up with OrderedDict. People often want a *sorted*
dict, in the sense that it always iterates in the naive sorted order
that sorted(dict.keys()) would give, but without having to sort the
keys. So you will sometimes find people using "ordered" and "sorted"
interchangably -- I must admit I've been guilty of that once or twice.

In general, though, "ordered" means *items are always in insertion
order*, while "sorted" means "the order you would get if you sorted".

And neither may apply to data structures that order their items in
something other than insertion order, e.g. order of frequency of use.


--
Steve

[Nick Coghlan]

I was trying to recall if we'd ever seriously considered
NotImplemented for this use case, but as near as I can tell, the
"__hash__ = None" approach was born as the obvious Python level
counterpart of setting the C level tp_hash slot to NULL in Python 3.0:
https://hg.python.org/cpython/rev/c6d9fa81f20f/

We then retained the "__hash__ = None" behaviour at the Python level
even after switching to a custom slot entry at the C level as part of
resolving some corner cases that were found when backporting the abc
module from Python 3.0 to 2.6:
https://bugs.python.org/issue2235#msg69324

So this is a case of C's NULL pointer concept being visible in
Python's semantic model as "attribute = None". Operand coercion is
actually the special case on that front, as "None" needs to be
permitted as a possible result, and exceptions can't be used as an
alternative signalling channel due to the runtime cost involved.

Cheers,
Nick.

--
Nick Coghlan | ncog...@gmail.com | Brisbane, Australia