#26221 closed defect (fixed)

Enable hash for FreeMonoid_class

Reported by: jhpalmieri Owned by:
Priority: major Milestone: sage-8.4
Component: python3 Keywords:
Cc: Merged in:
Authors: John Palmieri Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 8d3b505 (Commits) Commit: 8d3b5050403616744dc49b2b58f9b43e25dff3b6
Dependencies: Stopgaps:

Description (last modified by jhpalmieri)

As in #26162 and other tickets, removing __eq__ does the job. Also:

  • use UniqueRepresentation instead of UniqueFactory for constructing instances of FreeMonoid.
  • clean up caching of subclasses: no need to do this by hand, since they will now inherit from UniqueRepresentation.

Without this change, there are Python 3 doctest failures in sage/algebras/lie_algebras, among other places. For example,

File "src/sage/algebras/lie_algebras/lie_algebra.py", line 1402, in sage.algebras.lie_algebras.lie_algebra.LiftMorphismToAssociative.preimage
Failed example:
    L = LieAlgebra(associative=R)
Exception raised:
    Traceback (most recent call last):
      File "sage/misc/cachefunc.pyx", line 1000, in sage.misc.cachefunc.CachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6175)
        return self.cache[k]
      File "sage/misc/weak_dict.pyx", line 706, in sage.misc.weak_dict.WeakValueDictionary.__getitem__ (build/cythonized/sage/misc/weak_dict.c:3538)
        cdef PyObject* wr = PyDict_GetItemWithError(self, k)
    TypeError: unhashable type: 'FreeMonoid_class_with_category'

...

Part of #24551.

Change History (18)

comment:1 Changed 15 months ago by jhpalmieri

  • Branch set to u/jhpalmieri/free-monoid-hash

comment:2 Changed 15 months ago by jhpalmieri

  • Commit set to d6c3b5f71741dedfddb0c4aa8e54f00ee1f81a90
  • Status changed from new to needs_review

New commits:

d6c3b5ftrac 26221: enable hash for FreeMonoid_class_with_category

comment:3 Changed 15 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to needs_work

Doctest failures (see patchbots):

sage -t --long src/sage/crypto/classical.py  # 8 doctests failed
sage -t --long src/sage/crypto/classical_cipher.py  # 5 doctests failed

The issue comes from the fact that StringMonoid_class inherits from FreeMonoid_class, but because the FreeMonoid_class uses UniqueFactory, it does not have UniqueRepresentation behavior inherited. Moreover, all of the subclasses of StringMonoid_class have their own hand-rolled caches. The proper thing to do would be to rename FreeMonoid_class -> FreeMonoid and have it inherit from UniqueRepresentation and get rid of all of those custom caches. It is a bit of work, but it will be a good improvement to the code.

comment:4 follow-up: Changed 15 months ago by jhpalmieri

I think I would prefer to keep FreeMonoid as a function, since it forks depending on whether the monoid is abelian or not, but I can try to work on having FreeMonoid_class inherit from UniqueRepresentation.

comment:5 in reply to: ↑ 4 Changed 15 months ago by tscrim

Replying to jhpalmieri:

I think I would prefer to keep FreeMonoid as a function, since it forks depending on whether the monoid is abelian or not, but I can try to work on having FreeMonoid_class inherit from UniqueRepresentation.

You can absorb this behavior into the __classcall_private__, but perhaps considering the documentation, it might be better to actually keep it separate. I don't have a particularly strong opinion either way.

comment:6 Changed 15 months ago by git

  • Commit changed from d6c3b5f71741dedfddb0c4aa8e54f00ee1f81a90 to 8c1e9ea9b7c24392604bf60d934b7b1fabe2a354

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

8c1e9eatrac 26221: FreeMonoid: use UniqueRepresentation instead of UniqueFactory.

comment:7 follow-up: Changed 15 months ago by jhpalmieri

  • Status changed from needs_work to needs_review

Okay, here is a branch using UniqueRepresentation, but I'm confused by

Moreover, all of the subclasses of StringMonoid_class have their own hand-rolled caches.

Can you clarify?

comment:8 in reply to: ↑ 7 Changed 15 months ago by tscrim

Replying to jhpalmieri:

Okay, here is a branch using UniqueRepresentation, but I'm confused by

Great, thank you. Small detail: the doc from __classcall_private__ should almost entirely be moved into the class-level doc so it is visible under FreeMonoid? and in the html docs.

Moreover, all of the subclasses of StringMonoid_class have their own hand-rolled caches.

Can you clarify?

See the _cache module variable and def BinaryStrings() in string_monoid.py. So they are double-caching with your current changes.

comment:9 Changed 15 months ago by git

  • Commit changed from 8c1e9ea9b7c24392604bf60d934b7b1fabe2a354 to 24dedf599a03fddf79e54bf7f7aef784c749db44

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

24dedf5trac 26221: fix the docstrings.

comment:10 Changed 15 months ago by git

  • Commit changed from 24dedf599a03fddf79e54bf7f7aef784c749db44 to f7d20463f4a1b53907d9a2b614c93d286a8738db

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

f7d2046trac 26221: remove superfluous caching in string_monoid.py.

comment:11 Changed 15 months ago by jhpalmieri

Okay, how about this? (Independently, I realized the same thing about the docstrings, which is why I made that change almost immediately after your comment.) I also thought about just renaming BinaryStringMonoid -> BinaryStrings, but both are used in different parts of the Sage library, so I left it as is.

comment:12 Changed 15 months ago by jhpalmieri

  • Description modified (diff)

comment:13 Changed 15 months ago by jhpalmieri

  • Description modified (diff)

comment:14 Changed 15 months ago by tscrim

The docstrings still will not show in the ? and html doc if they are in the __init__ because there is already a class-level doc. I would rather have it in the class-level doc so we can use the __init__ to discuss implementation details. You also should be able to just call the index_set as n in the __init__.

I am okay with leaving the alias for now, but it should really be uniformized at some point. Yet, I've already asked quite a lot from you on this ticket.

comment:15 Changed 15 months ago by git

  • Commit changed from f7d20463f4a1b53907d9a2b614c93d286a8738db to 8d3b5050403616744dc49b2b58f9b43e25dff3b6

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

8d3b505trac 26221: fix a bug and add a doctest for it. Move the main

comment:16 Changed 15 months ago by jhpalmieri

Okay, how about this?

comment:17 Changed 15 months ago by tscrim

  • Status changed from needs_review to positive_review

Yep. LGTM. Thank you.

comment:18 Changed 15 months ago by vbraun

  • Branch changed from u/jhpalmieri/free-monoid-hash to 8d3b5050403616744dc49b2b58f9b43e25dff3b6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.