Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make Compositions into a collections.abc.Sequence #34527

Closed
trevorkarn opened this issue Sep 13, 2022 · 43 comments
Closed

Make Compositions into a collections.abc.Sequence #34527

trevorkarn opened this issue Sep 13, 2022 · 43 comments

Comments

@trevorkarn
Copy link
Contributor

Currently Sage does not understand Compositions as a collections.abc.Sequence:

sage: c = Composition([3,4,2,4])
sage: from collections.abc import Sequence
sage: isinstance(c, Sequence)
False

This ticket registers Composition as a Sequence.

CC: @tscrim @trevorkarn

Component: combinatorics

Keywords: gsoc2022 compositions sequence

Author: Trevor K. Karn

Branch/Commit: 78f3a92

Reviewer: Travis Scrimshaw, Matthias Köppe

Issue created by migration from https://trac.sagemath.org/ticket/34527

@trevorkarn
Copy link
Contributor Author

comment:1

The methods required according to the collections documentation (https://docs.python.org/3/library/collections.abc.html#collections-abstract-base-classes) are present except for __reversed__ and count.

sage: c.__getitem__
<bound method CombinatorialObject.__getitem__ of [3, 4, 2, 4]>
sage: c.__len__
<bound method CombinatorialObject.__len__ of [3, 4, 2, 4]>
sage: c.__contains__
<bound method CombinatorialObject.__contains__ of [3, 4, 2, 4]>
sage: c.__iter__
<bound method CombinatorialObject.__iter__ of [3, 4, 2, 4]>
sage: c.__reversed__
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Input In [30], in <cell line: 1>()
----> 1 c.__reversed__

File ~/Applications/sage/src/sage/structure/element.pyx:494, in sage.structure.element.Element.__getattr__()
    492         AttributeError: 'LeftZeroSemigroup_with_category.element_class' object has no attribute 'blah_blah'
    493     """
--> 494     return self.getattr_from_category(name)
    495 
    496 cdef getattr_from_category(self, name):

File ~/Applications/sage/src/sage/structure/element.pyx:507, in sage.structure.element.Element.getattr_from_category()
    505     else:
    506         cls = P._abstract_element_class
--> 507     return getattr_from_other_class(self, cls, name)
    508 
    509 def __dir__(self):

File ~/Applications/sage/src/sage/cpython/getattr.pyx:356, in sage.cpython.getattr.getattr_from_other_class()
    354     dummy_error_message.cls = type(self)
    355     dummy_error_message.name = name
--> 356     raise AttributeError(dummy_error_message)
    357 cdef PyObject* attr = instance_getattr(cls, name)
    358 if attr is NULL:

AttributeError: 'Compositions_all_with_category.element_class' object has no attribute '__reversed__'
sage: index(c)
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Input In [31], in <cell line: 1>()
----> 1 index(c)

NameError: name 'index' is not defined
sage: c.index
<bound method CombinatorialObject.index of [3, 4, 2, 4]>
sage: c.count
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Input In [33], in <cell line: 1>()
----> 1 c.count

File ~/Applications/sage/src/sage/structure/element.pyx:494, in sage.structure.element.Element.__getattr__()
    492         AttributeError: 'LeftZeroSemigroup_with_category.element_class' object has no attribute 'blah_blah'
    493     """
--> 494     return self.getattr_from_category(name)
    495 
    496 cdef getattr_from_category(self, name):

File ~/Applications/sage/src/sage/structure/element.pyx:507, in sage.structure.element.Element.getattr_from_category()
    505     else:
    506         cls = P._abstract_element_class
--> 507     return getattr_from_other_class(self, cls, name)
    508 
    509 def __dir__(self):

File ~/Applications/sage/src/sage/cpython/getattr.pyx:356, in sage.cpython.getattr.getattr_from_other_class()
    354     dummy_error_message.cls = type(self)
    355     dummy_error_message.name = name
--> 356     raise AttributeError(dummy_error_message)
    357 cdef PyObject* attr = instance_getattr(cls, name)
    358 if attr is NULL:

AttributeError: 'Compositions_all_with_category.element_class' object has no attribute 'count'

@trevorkarn
Copy link
Contributor Author

New commits:

1463b3eRegister Composition as a sequence

@trevorkarn
Copy link
Contributor Author

Commit: 1463b3e

@trevorkarn
Copy link
Contributor Author

Branch: u/tkarn/composition-34527

@trevorkarn

This comment has been minimized.

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 13, 2022

comment:4

Maybe some doctests to illustrate the supported operations would be good, to help other Sage users understand the Sequence protocol?

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 13, 2022

comment:5

Also in the doctest I would suggest to use the fully qualified name collections.abc.Sequence for clarity because there's also the unrelated global binding Sequence in Sage.

@tscrim
Copy link
Collaborator

tscrim commented Sep 13, 2022

comment:6

+1 to Matthias’s comments; in particular the count method is a bit unnatural for compositions.

It might make more sense to simply inherit from Sequence instead of registering it and providing a __reversed__ method (which should return a Composition). The default count should be okay.

@trevorkarn
Copy link
Contributor Author

comment:7

It looks like things are sufficiently fixed just by calling Sequence.register(Composition). As Matthias suggested, I updated the doctest. I'm not sure there is a need to actually implement the __reversed__ or count methods as I had suggested earlier.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 15, 2022

Branch pushed to git repo; I updated commit sha1. New commits:

e74e0b2Update doctest

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 15, 2022

Changed commit from 1463b3e to e74e0b2

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 15, 2022

comment:9

Replying to Trevor Karn:

It looks like things are sufficiently fixed just by calling Sequence.register(Composition).

Yes, this is equivalent to inheriting from Sequence.

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 15, 2022

comment:10

comment:4?

@trevorkarn
Copy link
Contributor Author

comment:11

Replying to Matthias Köppe:

comment:4?

Sorry, I think I misunderstood. Since we are registering it as a Sequence rather than implementing the "required" methods, the general Sequence protocol is not really followed. Maybe this is something that should go in the developer's guide rather than a doctest here?

@tscrim
Copy link
Collaborator

tscrim commented Sep 15, 2022

comment:12

Replying to Trevor Karn:

It looks like things are sufficiently fixed just by calling Sequence.register(Composition).

Does it also pass the issubclass test too?

As Matthias suggested, I updated the doctest. I'm not sure there is a need to actually implement the __reversed__ or count methods as I had suggested earlier.

What is the type of the result from applying reversed to the composition? Some tests would help here, a la comment:4.

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 15, 2022

comment:13

Replying to Matthias Köppe:

Replying to Trevor Karn:

It looks like things are sufficiently fixed just by calling Sequence.register(Composition).

Yes, this is equivalent to inheriting from Sequence.

I realize that I have to clarify this: It is equivalent as far as isinstance and issubclass are concerned, but you will get the mix-in methods listed in https://docs.python.org/3/library/collections.abc.html#collections-abstract-base-classes (__reversed__, count, etc.) only if you inherit from Sequence in the class definition.

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 15, 2022

comment:14

Replying to Travis Scrimshaw:

Replying to Trevor Karn:

It looks like things are sufficiently fixed just by calling Sequence.register(Composition).

Does it also pass the issubclass test too?

Yes, of course, that should be added as a test maybe:

sage: import collections.abc
sage: C = Composition([3,2,3])
sage: issubclass(C.__class__, collections.abc.Sequence)
True
sage: isinstance(C, collections.abc.Sequence)
True

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 15, 2022

comment:15

Replying to Travis Scrimshaw:

What is the type of the result from applying reversed to the composition?

sage: reversed(C)
<reversed object at 0x7fe2e86c4e50>

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 15, 2022

comment:16

Replying to Trevor Karn:

Replying to Matthias Köppe:

comment:4?

Sorry, I think I misunderstood. Since we are registering it as a Sequence rather than implementing the "required" methods, the general Sequence protocol is not really followed.

It is followed. The "mixin" methods are not part of the protocol.

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 15, 2022

comment:17

Replying to Matthias Köppe:

Replying to Trevor Karn:

Replying to Matthias Köppe:

comment:4?

Sorry, I think I misunderstood. Since we are registering it as a Sequence rather than implementing the "required" methods, the general Sequence protocol is not really followed.

It is followed. The "mixin" methods are not part of the protocol.

No, sorry, my mistake. It's getting late here.

You are right, it is not allowed to register it without implementing these mixin methods.
But you'll get them for free by changing it to subclassing instead of registering.

@tscrim
Copy link
Collaborator

tscrim commented Sep 15, 2022

comment:18

Replying to Matthias Köppe:

Replying to Travis Scrimshaw:

What is the type of the result from applying reversed to the composition?

sage: reversed(C)
<reversed object at 0x7fe2e86c4e50>

Ah, right, duh. It is an iterator and does not return the reversed object.

@trevorkarn
Copy link
Contributor Author

comment:19

After subclassing:

  File "/Users/trevorkarn/Applications/sage/src/sage/combinat/composition.py", line 50, in <module>
    class Composition(CombinatorialElement, Sequence):
TypeError: metaclass conflict: the metaclass of a derived class must be a (non-strict) subclass of the metaclasses of all its bases

Should this be fixed at the CombinatorialElement level? Or would it be better to just make Composition a subclass of ClonableArray to update it?

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 15, 2022

Changed commit from e74e0b2 to 27b986a

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 15, 2022

Branch pushed to git repo; I updated commit sha1. New commits:

27b986aMore updates to doctest

@tscrim
Copy link
Collaborator

tscrim commented Sep 15, 2022

comment:21

Replying to Trevor Karn:

After subclassing:

  File "/Users/trevorkarn/Applications/sage/src/sage/combinat/composition.py", line 50, in <module>
    class Composition(CombinatorialElement, Sequence):
TypeError: metaclass conflict: the metaclass of a derived class must be a (non-strict) subclass of the metaclasses of all its bases

Ouch. Python used a metaclass for their (collections) ABCs abc.ABCMeta. Well, I guess that settles it; we have to register it.

Should this be fixed at the CombinatorialElement level?

No, that is going to go away at some point.

Or would it be better to just make Composition a subclass of ClonableArray to update it?

This won't solve the problem:

sage: from sage.structure.list_clone import ClonableArray
sage: ClonableArray.__class__
<class 'sage.misc.inherit_comparison.InheritComparisonMetaclass'>

@trevorkarn
Copy link
Contributor Author

comment:22

Replying to Travis Scrimshaw:

Replying to Trevor Karn:

After subclassing:

  File "/Users/trevorkarn/Applications/sage/src/sage/combinat/composition.py", line 50, in <module>
    class Composition(CombinatorialElement, Sequence):
TypeError: metaclass conflict: the metaclass of a derived class must be a (non-strict) subclass of the metaclasses of all its bases

Ouch. Python used a metaclass for their (collections) ABCs abc.ABCMeta. Well, I guess that settles it; we have to register it.

Got it - then I think this is ready for review. I tried to inclued the doctests which were relevant to this conversation, but please let me know if I need more.

Or would it be better to just make Composition a subclass of ClonableArray to update it?

This won't solve the problem:

sage: from sage.structure.list_clone import ClonableArray
sage: ClonableArray.__class__
<class 'sage.misc.inherit_comparison.InheritComparisonMetaclass'>

Huh. Should ClonableArray be a Sequence?

@tscrim
Copy link
Collaborator

tscrim commented Sep 16, 2022

comment:23

Replying to Trevor Karn:

Replying to Travis Scrimshaw:

Replying to Trevor Karn:

Or would it be better to just make Composition a subclass of ClonableArray to update it?

This won't solve the problem:

sage: from sage.structure.list_clone import ClonableArray
sage: ClonableArray.__class__
<class 'sage.misc.inherit_comparison.InheritComparisonMetaclass'>

Huh. Should ClonableArray be a Sequence?

This is saying it also has a metaclass.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 17, 2022

Changed commit from 27b986a to c0eb2b4

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 17, 2022

Branch pushed to git repo; I updated commit sha1. New commits:

c0eb2b4Add to documentation and remove reversed type-check

@trevorkarn
Copy link
Contributor Author

comment:26

Documentation is updated.

@tscrim
Copy link
Collaborator

tscrim commented Sep 18, 2022

comment:27

Thanks. I am happy with this (modulo the one change below). Matthias?

Sphinx treats the backtick as normal text when between alpha(numeric?) characters:

     Typically, instances of ``collections.abc.Sequence`` have a ``.count`` method.
-    This is *not* the case for ``Composition``s::
+    This is *not* the case for a ``Composition``::

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 18, 2022

Changed commit from c0eb2b4 to b0a87c6

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 18, 2022

Branch pushed to git repo; I updated commit sha1. New commits:

b0a87c6Fix documentation

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 18, 2022

comment:29

I think in comment:17, I concluded that all mix-in methods must be provided. Too tired this evening to re-read the Python reference to confirm it

@trevorkarn
Copy link
Contributor Author

comment:30

Replying to Matthias Köppe:

I think in comment:17, I concluded that all mix-in methods must be provided. Too tired this evening to re-read the Python reference to confirm it

I understand this python discussion post to mean that mix-in methods are not required.

On the other hand it is easy enough to implement .count() where .count(n) returns the number of parts of size n. So I'll do that later today.

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 19, 2022

Branch pushed to git repo; I updated commit sha1. New commits:

78f3a92Add .count

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Sep 19, 2022

Changed commit from b0a87c6 to 78f3a92

@trevorkarn
Copy link
Contributor Author

comment:32

Replying to Matthias Köppe:

I think in comment:17, I concluded that all mix-in methods must be provided. Too tired this evening to re-read the Python reference to confirm it

Ok. I think Sequence things should be good to go.

@tscrim
Copy link
Collaborator

tscrim commented Sep 20, 2022

comment:33

Replying to Matthias Köppe:

I think in comment:17, I concluded that all mix-in methods must be provided. Too tired this evening to re-read the Python reference to confirm it

This is in point (2) of the main Python ABC doc in comment:1.

@tscrim
Copy link
Collaborator

tscrim commented Sep 20, 2022

Reviewer: Travis Scrimshaw, Matthias Köppe

@tscrim
Copy link
Collaborator

tscrim commented Sep 20, 2022

comment:34

That takes care of all of the mixin methods. So I am good with this. Anything objections to a positive review Matthias?

@mkoeppe
Copy link
Contributor

mkoeppe commented Sep 22, 2022

comment:35

LGTM, thanks.

@vbraun
Copy link
Member

vbraun commented Sep 25, 2022

Changed branch from u/tkarn/composition-34527 to 78f3a92

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants