cached_function and cached_method for unhashable elements

[saraedum]

Caching does currently not work for unhashable elements

sage: @cached_function
....: def f(x):
....:     return x
....:
sage: K.<a> = Qq(9)
sage: f(a)
TypeError: unhashable type: 'sage.rings.padics.padic_ZZ_pX_CR_element.pAdicZZpXCRElement'

In this case a should not be hashable since its current operator == could never be made consistent with a non-trivial hash value (cf. #11895). However, such elements should be cacheable.

This ticket adds a _cache_key() for such elements which can be used to hash and compare unhashable elements. That method should then return a tuple (or anything else that is hashable) which uniquely identifies the element, e.g. for p-adics the precision and a lift of the element to the integers.

Depends on #16251

CC: @simon-king-jena

Component: misc

Author: Julian Rueth

Branch/Commit: aa037de

Reviewer: Peter Bruin, Travis Scrimshaw

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

[pjbruin]

comment:40

Replying to @tscrim:

Replying to @pjbruin:

Hmm, I see. But if we store the parent itself, then I think we have to make sure that all unhashable elements belong to parents satisfying unique representation. Otherwise, calling a cached function on an element whose parent is equal but not identical to the parent of an element that was used before could return a cached result that lives in this equal-but-not-identical parent.

No, this isn't a problem because equal parents have equal hashes.

That is exactly what causes the problem. Consider the following example with a hypothetical parent class MyParent that has unhashable elements but does not have unique representation:

sage: @cached_function
sage: def f(x):
....:     """
....:     Return `x^2 + 1` in the parent of `x`.
....:     """
....:     return x^2 + 1
....: 
sage: P = MyParent()
sage: Q = MyParent()  # Q is equal but not identical to P
sage: f(P(0)).parent() is P
True
sage: f(Q(0)).parent() is Q
False  # since the parents are equal, f(q) returns the cached f(p)
sage: f(P(0)) is f(Q(0))
True

This already happens before this patch with parent P and Q where there exists a coercion map compatible with hashing (e.g. Z and Q):

sage: @cached_function
....: def f(x):
....:     return x^2 + 1
....: 
sage: f(ZZ(0)).parent()
Integer Ring
sage: f(QQ(0)).parent()
Integer Ring
sage: f(ZZ(0)) is f(QQ(0))
True

However, I think we should avoid this situation whenever possible.

[tscrim]

comment:41

Oh that's subtle. However this usually (almost always?) won't be a problem because the coercion, which allowed the elements to compare as equal, will step in to make the arithmetic work. I would think equal-but-not-identical parents should have coercions between themselves too.

[vbraun]

comment:42

Documentation doesn't build

build/pipestatus "./sage --docbuild --no-pdf-links all html -j  2>&1" "tee -a logs/dochtml.log"
Traceback (most recent call last):
  File "/mnt/SSD1/mod_buildslave/sage_git/build/src/doc/common/builder.py", line 27, in <module>
    from sage.misc.cachefunc import cached_method
ImportError: dynamic module does not define init function (initcachefunc)
make: *** [doc-html-mathjax] Error 1

[vbraun]

comment:43

Note: seems to only fail on UW mod

[vbraun]

comment:44

Doctests fail everywhere

File "src/sage/misc/cachefunc.pyx", line 416, in sage.misc.cachefunc
Failed example:
    b = a + O(3)
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.misc.cachefunc[98]>", line 1, in <module>
        b = a + O(Integer(3))
      File "parent.pyx", line 1064, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:8683)
    NotImplementedError

possibly due to the dependent ticket #16317

[vbraun]

comment:45

So actual objects and cache keys go into the same dictionary? Isn't that dangerous, one person's key could easily be another one's object? Shouldn't it be different dicts or some special object to hold the key?

[saraedum]

comment:46

Replying to @pjbruin:

Replying to @tscrim:

Replying to @pjbruin: No, this isn't a problem because equal parents have equal hashes.

That is exactly what causes the problem. Consider the following example with a hypothetical parent class MyParent that has unhashable elements but does not have unique representation:

As you wrote, this is not a new problem. It does not seem to be related to unhashable elements. Mixing non-unique parents and caching will simply lead to trouble.

[saraedum]

comment:47

Replying to @vbraun:

So actual objects and cache keys go into the same dictionary? Isn't that dangerous, one person's key could easily be another one's object? Shouldn't it be different dicts or some special object to hold the key?

Though this is very unlikely it is a valid point. I will take care of it.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c987fc7	_cache_key is not an attribute anymore
a4f17d1	fixed doctests
aa037de	Fix collisions between unhashable and hashable elements in @cached_method

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 83944fa to aa037de

[vbraun]

Changed branch from u/saraedum/ticket/16316 to aa037de