Opened 7 years ago

Closed 6 years ago

Last modified 6 years ago

#16644 closed enhancement (fixed)

LinearCode.cardinality category breakage

Reported by: ppurka Owned by:
Priority: major Milestone: sage-6.3
Component: coding theory Keywords:
Cc: ncohen, SimonKing, nthiery, tscrim Merged in:
Authors: Travis Scrimshaw, Punarbasu Purkayastha Reviewers: Nathann Cohen, Punarbasu Purkayastha, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 709878e (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by vbraun)

sage: C = codes.HammingCode(3, GF(2))
sage: C.cardinality()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-2-2e23aafacb95> in <module>()
----> 1 C.cardinality()

/home/release/Sage/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__getattr__ (build/cythonized/sage/structure/parent.c:7211)()

AttributeError: 'LinearCode' object has no attribute 'cardinality'
sage: 'cardinality' in dir(C)
True
sage: hasattr(C, 'cardinality')
False

Change History (34)

comment:1 follow-up: Changed 7 years ago by ncohen

(the same happens with c.cartesian_product and c.sum, and probably others too... :-/)

comment:2 Changed 7 years ago by ppurka

  • Branch set to u/ppurka/ticket/16644

comment:3 in reply to: ↑ 1 ; follow-up: Changed 7 years ago by ppurka

  • Commit set to fe1233458e4ae0308a02fc3e71c819533b060ecf

Replying to ncohen:

(the same happens with c.cartesian_product and c.sum, and probably others too... :-/)

Yikes! Where are all these methods coming from? They are not in any of the classes that LinearCode inherits from.


New commits:

af3e48einitial commit to enable thickness of edges in graph plots
be6042dintroduce thickness parameter in scatter_plot
fe12334add cardinality() method to LinearCode

comment:4 in reply to: ↑ 3 Changed 7 years ago by ncohen

Yikes! Where are all these methods coming from? They are not in any of the classes that LinearCode inherits from.

Don't ask me, I always blame it on categories whatever happens.

Nathann

comment:5 Changed 7 years ago by git

  • Commit changed from fe1233458e4ae0308a02fc3e71c819533b060ecf to 4ccae66296a47a62daf12fc8a6662439e6183f35

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

4ccae66add cardinality() method to LinearCode

comment:6 Changed 7 years ago by ppurka

Sorry, I need to sleep. I based previous commit on the wrong branch. Did a forced update now.

comment:7 Changed 7 years ago by ncohen

Oh, I see. WHen you will be awake: we had to write a LOT of code in the combinatorial design folders recently, and had queues of 5/6 ticket in needs_review depending on each other: we would have died if we had not added to every commit the ticket number at the beginning of the commit message. Otherwise you have no way to guess which commits belong to a given ticket.

Good night ! ;-)

Nathann

comment:8 Changed 7 years ago by ncohen

Should this be in needs_review ?

Nathann

comment:9 follow-up: Changed 7 years ago by ppurka

  • Authors set to Punarbasu Purkayastha
  • Status changed from new to needs_review

Yes, of course. Thanks. I think cardinality should definitely be implemented, but am not so clear about cartesian product and sum, and possibly a bunch of others.

comment:10 in reply to: ↑ 9 Changed 7 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Yes, of course. Thanks. I think cardinality should definitely be implemented, but am not so clear about cartesian product and sum, and possibly a bunch of others.

Well, that's a different problem: why the hell are all those function half-inherited ? T_T

Nathann

comment:11 Changed 7 years ago by vbraun

  • Authors Punarbasu Purkayastha deleted
  • Cc SimonKing nthiery tscrim added
  • Description modified (diff)
  • Reviewers Nathann Cohen deleted
  • Status changed from positive_review to needs_work

Nicolas, can you explain to me why this is not working. And, more importantly. why do we get totally useless diagnostics for why it is not working?

comment:12 Changed 7 years ago by vbraun

  • Summary changed from Implement LinearCode.cardinality() to LinearCode.cardinality category breakage

comment:13 Changed 7 years ago by tscrim

I believe it's because it's not a new style parent and it doesn't properly initialize its category:

class LinearCode(module.Module_old):
    def __init__(self, gen_mat, d=None):
        ParentWithGens.__init__(self, base_ring)

and in Module_old:

def category(self):
    """
    Return the category to which this module belongs.
    """
    # Defining a category method is deprecated for parents.
    # Instead, the category should be specified in the constructor.
    # See: http://sagetrac.org/sage_trac/wiki/CategoriesRoadMap
    if self._is_category_initialized():
        return Parent.category(self)
    from sage.categories.modules import Modules
    return Modules(self.base_ring())

comment:14 Changed 7 years ago by vbraun

That doesn't explain why it half-works, nor is it an excuse for the total failure to provide a useful error message.

comment:15 follow-up: Changed 7 years ago by tscrim

  • Branch changed from u/ppurka/ticket/16644 to public/categories/new_parent_linear_codes-16644
  • Commit changed from 4ccae66296a47a62daf12fc8a6662439e6183f35 to b48b62702d0d4ff382111ad093ac80808aef6231
  • Status changed from needs_work to needs_info

Because it doesn't initialize its category, we have:

sage: C = codes.HammingCode(3, GF(2))
sage: C.__class__.__mro__
(sage.coding.linear_code.LinearCode,
 sage.modules.module.Module_old,
 sage.structure.parent_gens.ParentWithAdditiveAbelianGens,
 sage.structure.parent_gens.ParentWithGens,
 sage.structure.parent_base.ParentWithBase,
 sage.structure.parent_old.Parent,
 sage.structure.parent.Parent,
 sage.structure.category_object.CategoryObject,
 sage.structure.sage_object.SageObject,
 object)

I believe the __getattr__ in parent.pyx is why it gets listed by tab completion, but because the method doesn't actually exist in the MRO, it can't call it. Simon or Nicolas could probably give a better explanation. IMO it's not worth it to try and contrive a "proper" error message, but instead put a note somewhere that this is a sign that the category framework is being abused.

So here's the branch which changes LinearCode to a new-style parent and all (non-long) tests pass in the coding folding. However because I don't know about codes, I can't implement an _an_element_ for the test suite, nor do I know what the proper/best category is (i.e. are they finite dimensional modules? I'm guessing they are but IDK for sure). However this does fix the issue on this ticket.


New commits:

b48b627Changed LinearCode into a new-style parent.

comment:16 in reply to: ↑ 15 Changed 7 years ago by vbraun

Replying to tscrim:

IMO it's not worth it to try and contrive a "proper" error message

I suggest you read the history of this ticket again. Getting proper error messages is crucial for any programming framework.

comment:17 Changed 7 years ago by ppurka

@tscrim: there is still this problem with element_class. I have been able to get some other stuff working with your patch.

sage: C = codes.HammingCode(3, GF(2))                                           
sage: C.cardinality()                                                           
16
sage: C.an_element()
(1, 0, 0, 0, 0, 1, 1)
sage: C2 = C.cartesian_product(C)
sage: C2.an_element()
((1, 0, 0, 0, 0, 1, 1), (1, 0, 0, 0, 0, 1, 1))
sage: C.categories()
[Category of vector spaces over Finite Field of size 2,
 Category of modules over Finite Field of size 2,
 Category of bimodules over Finite Field of size 2 on the left and Finite Field of size 2 on the right,
 Category of right modules over Finite Field of size 2,
 Category of left modules over Finite Field of size 2,
 Category of commutative additive groups,
 Category of additive groups,
 Category of additive inverse additive unital additive magmas,
 Category of commutative additive monoids,
 Category of additive monoids,
 Category of additive unital additive magmas,
 Category of commutative additive semigroups,
 Category of additive commutative additive magmas,
 Category of additive semigroups,
 Category of additive magmas,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]
sage: C.element_class()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-5-66b2e3babdf7> in <module>()
----> 1 C.element_class()

/home/punarbasu/Installations/sage-git/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__getattr__ (build/cythonized/sage/structure/parent.c:7290)()

/home/punarbasu/Installations/sage-git/local/lib/python2.7/site-packages/sage/structure/misc.so in sage.structure.misc.getattr_from_other_class (build/cythonized/sage/structure/misc.c:1687)()

AttributeError: 'LinearCode_with_category' object has no attribute 'element_class'

Edit: Also implemented C.zero() so that C.sum() works.

sage: C.zero_element()
(0, 0, 0, 0, 0, 0, 0)
sage: C.sum(()) # indirect doctest
(0, 0, 0, 0, 0, 0, 0)

So, we just need to figure out where this element_class is coming from and fix that.

Last edited 7 years ago by ppurka (previous) (diff)

comment:18 Changed 7 years ago by git

  • Commit changed from b48b62702d0d4ff382111ad093ac80808aef6231 to eef3aaabca400ce0be8460f85f70eef38cfb8a28

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

740bbd3implement _an_element_ for LinearCode
d1fca72Implement LinearCode.cardinality()
eef3aaaimplement LinearCode.zero()

comment:19 Changed 7 years ago by git

  • Commit changed from eef3aaabca400ce0be8460f85f70eef38cfb8a28 to 60130279bc91553f0bb8418cebd0597506eb0978

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

6013027Fixed LinearCode a facade parent and so that it passes the test suite.

comment:20 Changed 7 years ago by tscrim

  • Authors set to Travis Scrimshaw, Punarbasu Purkayastha
  • Reviewers set to Punarbasu Purkayastha, Travis Scrimshaw
  • Status changed from needs_info to needs_review

It comes from the category framework, although I believe it is there more for compatibility with old-style parents.

I've made LinearCode into a facade parent (because I didn't want to deal with changing it over to have a proper element here...yes I'm being somewhat lazy), put it also in the category of FiniteEnumeratedSets (as such, we get cardinality for free), and made it so that it passes the TestSuite.

comment:21 Changed 7 years ago by vbraun

  • Status changed from needs_review to needs_work

The real WTF here is not that LinearCode is misusing the category framework, but the utterly wrong and misleading error message that was produced. In Python, AttributeError means you need to implement that attribute but haven't. Nathan and Punarbasu are experienced developers, and if you manage to confuse them then I can guarantee your that there are 10 potential Sage developers that gave up before they posted anything on trac. If only a handful of people that have talked personally to Nicolas can work with the framework then this is going to kill Sage sooner or later. We need to be able to attract new developers, and hurdles like the one in this ticket will prevent that for sure.

comment:22 Changed 7 years ago by ppurka

@tscrim: I think what vbraun brought up needs to be fixed in the category framework somewhere.

Other than that, we can not depend on cardinality of the FiniteEnumeratedSets, even if it comes "for free". It comes at a huge cost because it generates all the elements of the linear code - it makes working with large linear codes difficult. We have a vector space structure here, so we can be much more efficient (which was my original patch in this ticket).

sage: C = codes.ReedSolomonCode(10, 7, GF(11))
sage: %time C.cardinality()                                                                                             
CPU times: user 8.14 s, sys: 60 ms, total: 8.2 s
Wall time: 8.1 s
19487171
sage: %time len(C)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 62.9 µs
19487171

comment:23 Changed 7 years ago by git

  • Commit changed from 60130279bc91553f0bb8418cebd0597506eb0978 to 709878e72911d2630a021ed0485c4d7a099abaff

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

8df0577Merge branch 'public/categories/new_parent_linear_codes-16644' of trac.sagemath.org:sage into public/categories/new_parent_lienar_codes-16644
235dd8eAdded back in cardinality and made __len__ an alias.
709878eImport cleanup of linear_code.py.

comment:24 follow-up: Changed 7 years ago by tscrim

  • Status changed from needs_work to needs_review

@vbraun I would argue that AttributeError is the correct error: the attribute should be there according to the category, but it is not because it is an old-style parent. I'd rather spend my time fixing the problem and educating people about categories rather than trying to come up with a different error message. This solves the issue in the ticket description and we shouldn't hold up this ticket -- the error message should be on a separate ticket.

@ncohen You actually were right in comment:4. I wonder if you're starting to understand categories. :P

@ppurka I didn't look at/see the __len__ method. I've changed that into cardinality and made __len__ into an alias (so it will appear in the documentation).

comment:25 Changed 7 years ago by vbraun

  • Status changed from needs_review to needs_work

Giving correct diagnostics is a way of educating people about categories, and arguably the best way since you can't be looking over everybody's shoulder all the time. I just caught this ticket by chance, and you would have never noticed.

comment:26 Changed 7 years ago by ppurka

@vbraun I think we should open a different ticket for fixing the categories. In this ticket the LinearCode class is changed to use the new category framework. I will have to check the latest changes, but they seem quite ok at first glance.

I will open a different ticket for addressing the error messages given by the categories. Does this sound reasonable to you?

comment:27 Changed 7 years ago by vbraun

Fine with me...

comment:28 Changed 7 years ago by tscrim

  • Status changed from needs_work to needs_review

comment:29 in reply to: ↑ 24 Changed 7 years ago by ncohen

@ncohen You actually were right in comment:4. I wonder if you're starting to understand categories. :P

We are old ennemies now.

Nathann

comment:30 Changed 7 years ago by ppurka

  • Reviewers changed from Punarbasu Purkayastha, Travis Scrimshaw to Nathann Cohen, Punarbasu Purkayastha, Travis Scrimshaw
  • Status changed from needs_review to positive_review

This looks good to me. It passes all sage doctests and fails in 3 places which are due to gap (see #16660).

comment:31 Changed 7 years ago by vbraun

  • Dependencies set to #16660

comment:32 Changed 6 years ago by tscrim

  • Dependencies #16660 deleted

I get the errors of #16660 with develop, so it's not a dependency IMO.

comment:33 Changed 6 years ago by vbraun

  • Branch changed from public/categories/new_parent_linear_codes-16644 to 709878e72911d2630a021ed0485c4d7a099abaff
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:34 Changed 6 years ago by vbraun

  • Commit 709878e72911d2630a021ed0485c4d7a099abaff deleted

Followup at #16707

Note: See TracTickets for help on using tickets.