#20246: Use `with strict_equality(True)` to work around hashing of p-adics
-------------------------------------+-------------------------------------
Reporter: saraedum | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-7.2
Component: padics | Resolution:
Keywords: days71 | Merged in:
Authors: Julian Rüth | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/saraedum/use__with_strict_equality_true___to_work_around_hashing_of_p_adics|
f4c5a9db729ccf911517039fdced282588210133
Dependencies: #16342, #16339 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by saraedum):
Replying to [comment:25 nbruin]:
> Replying to [comment:24 saraedum]:
> > However, most parents get used as cache keys in our factories and
`UniqueRepresentation`. And parents may depend on p-adic numbers in some
way.
Sorry. I meant: Most parents *use* caching in our factories and …
> In any case, I would be very surprised if there are any structures out
there that depend on anything else than sequences, polynomials, and
matrices. If those have cache_key strategies, we'd be OK.
Well, apparently elements depend on an overconvergent modular form and a
hyperbolic point which in turn depend on p-adics. So you need to implement
`_cache_key` there.
> > No but a lot of our code assumes that everything is usable as a key in
a dictionary for the sake of caching. I believe that this is a reasonable
assumption: Running a method on indistinguishable inputs should produce
the same output. And in some cases it should even produce the exact same
object, for example when creating parents; in those cases you can not do
without caching.
> But I am pretty sure this is limited to polynomials and matrices.
I guess most things that have coefficients. Polynomials and matrices sure
are the most popular ones. But then there are things that wrap these, like
linear maps, finite sets, …
> > I am not sure what you mean with "high up". For correctness you have
to implement it in any class that gets instantiated with a parameter that
may depend (in some way) on something unhashable, because essentially you
just need to write this as a method that produces the constructor
parameters that serve to produce an indistinguishable element.
> I meant: you could start sticking implementations into the more generic
classes for polynomials and matrices. I don't think we need to define
"correctness" as "p-adic numbers are hashable".
I meant to define correctness of caching as "indistinguishable input =>
indistinguishable output".
> > Though I originally implemented `_cache_key` what I dislike about it
is that you just have to add silly boilerplate to many classes. The new
approach is much better in that sense. The changes are where the actual
problem arises, namely in the classes that can not define a usual
`__hash__`. For everybody else it just works and it is actually correct.
The current `_cache_key` is calling for trouble in the long run: People
add a constructor parameter but don't add it to `_cache_key`; the doctests
pass but caching eventually produces incorrect results.
> Most parents do not need a `_cache_key`, because they are actually
hashable thanks to `EqualityByID`. I'd expect that only some element
classes need a `_cache_key`. So the scenario you sketch would only play
out if the identity-determining components of an element change.
I did not mean to focus that much on parents.
> > Of course, if the end user decides to run all its code `with
strict_equality(True)` then many things break. But the docstring tries to
be clear about this.
> The fundamental point is that you make equality context dependent. It
means you now need to know global state in order to reason about code that
otherwise looks completely local. I think that's an incredibly big
complexification and a major step back in the understandability and
maintainability of sage code. Whatever you write in the docstring doesn't
change that fact. You can't fix bad design by good documentation.
I don't think it is bad design. It is as much bad design as say a mutex.
If used incorrectly it creates deadlocks, however it is very hard to
certain things without it (double locking, memory barriers, …) So, people
are aware of these things and they try to write code that does not need
it. But sometimes it just makes sense to do so. And that is my
understanding why you should use `with strict_equality(True)` as locally
as possible. I think it is just fine like that.
> > I think the "strategic places" is a problem here. What this says it
that using p-adics (or fraction field elements) just works in places where
there happened to be a doctest that implied p-adics (and usually extension
fields to actually trigger `__hash__`.) Why not make it work everywhere?
> I think you are too pessimistic about the multitude of ways in which
padic numbers can end up being hashed in legitimate ways. I think you can
get this covered pretty quickly (polys and matrices). Plus: a lot of
places where p-adics aren't initially foreseen will actually break with
p-adics, because they are imprecise objects. That usually breaks
algorithms that weren't built with that in mind.
Many algorithms that do not take imprecise objects into account break. But
now they still break explicitly by raising a TypeError: not hashable.
Nothing changes there. However, many very trivial algorithms don't break
if what they do does not depend on the p-adic object (because they only
look at the dimensions of a matrix, or the spaces from to which a linear
map maps, ...)
> re. why not everywhere: because the proposed solution (making equality
testing depend on global state) incurs too high a price on the
maintainability of sage.
I disagree. I still think that forcing people into keeping constructors
and `_cache_key` in sync is not going to work. Those not concerned about
imprecise objects won't think about it when they modify a constructor and
then you get incorrect (cached) results.
> > Yes, global state is bad. The implementation is very clear on that and
I can elaborate on this further in the docstrings.
> Being clear about it doesn't fix a bad design decision (an, I think,
justified technical qualification of the proposal which in no way reflects
on the proposers)
Not sure what you are trying to say here…
> [Different notions of equality]
It is unfortunate that sage did not start with many notions of equality.
In an "ideal" (but probably unusable) computer algebra system `==` would
just throw an exception unless all reasonable notions of equality are the
same for both sides of the equation (taking into account precision,
properties that are outside of mathematics like printing, coercion, …) and
would require you to be precise about what equality should mean here.
--
Ticket URL: <http://trac.sagemath.org/ticket/20246#comment:26>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
