Design question about rings, re #6441
Sebastian Pancratz
At SAGE Days 16 I implemented some code for division-free matrix
operations, which is being tracked as ticket #6441. The main
contribution is code to compute the characteristic polynomial without
divisions, and this leads to code to compute the characteristic
polynomial, the adjoint matrix and the determinant of matrices over
any ring (commutative and with unity). On the one hand this will
extend the capabilities of SAGE, but in some cases it will also
provide a speed-up (by avoiding working in the field of fractions, or
because an O(n^4) algorithm beats the previous backup option for
computing determinants).
With this little background provided, here is the actual problem on
which I would very much like to hear your opinion.
A design-related technical problem is that, when given a ring R and
asked to construct or compute with certain objects related to R (see
below for some examples), SAGE tries to find out whether R is merely a
ring, or maybe an integral domain,or perhaps even a field. The
generic methods for this are located in sage/rings/ring.pyx.
In this file, the current behaviour is the following,
o Try to establish the answer (yes or no).
o If this doesn't work, throw an exception.
although the actual behaviour is down to the inheriting classes.
From the point of view of the ring, this might seem sensible. But I
think the case where this is used is something like this: One has
various algorithms at hand for computing with a given ring, and the
computation would be done much better if one knew the ring was a
field, say. I think the code would be a lot cleaner if the following
behaviour was offered:
o Try to find out whether the ring is a field, say.
o If the positive answer can be established, return yes. Otherwise,
return false.
To this extent, the current patch code includes methods
"is_certainly_field" and"is_certainly_integral_domain".
As part of the discussion on the trac ticket #6441, it was suggested
to instead do with the usual "is_field" etc. methods and handle
exceptions in the calling method. If it was only my new method that
would suffer from this problem, I'd be tempted to agree that this
would be the correct way to handle the problem. However, there are
two reasons why I think rings should have simple yes/no (rather than
yes/no/some exception) methods to be queried for being a field,
integral domain,etc. Firstly, the same problem occurs in other
places, too, for example when constructing polynomial rings or
vectors. Secondly, the exceptions can also be raised at a deeper
level, e.g. when a quotient ring is asked whether it is a field, it
checks whether the ideal is maximal. It is not clear to me from this
that the current implementation provides an answer of the kind (yes/no/
NotImplementedError); it's a least plausible that the determination
of whether a ring is a field could fail for a number of other reasons
and hence raise other exceptions, too.
I think this is one of the last few things in the way of completing
this trac ticket, so please let me know what you think.
Many thanks,
Sebastian
[Examples]
Let's take the following quotient ring S.
sage: R.<a,b> = QQ[]
sage: S.<x,y> = R.quo((b^3))
sage: A = matrix(S, [[x*y^2,2*x],[2,x^10*y]])
sage: A
[ x*y^2 2*x]
[ 2 x^10*y]
Then computing the charpoly of A will fail with a NotImplementedError
in "is_maximal" when checking whether the defining ideal is maximal.
sage: A.charpoly('T')
T^2 + (-x^10*y - x*y^2)*T - 4*x
(Interestingly, A.det() fails with an IndexError, but this would also
disappear with the patch in ticket #6441 applied.) The same happens
if we try to create a vector over the ring S,
sage: v = vector(S, 3)
or if we try to create a univariate polynomial ring over S,
sage: P.<x> = PolynomialRing(S, 'x')
William Stein
If R is a ring that is in fact a field, I'm sure that many people will be very unhappy if we have:
sage: R.is_field()
False
This would be more acceptable:
sage: R.is_field(unknown_returns_false=True)
True or False
So why not just add a flag that is off by default to the "is_field", etc. functions, so they do what you want? It makes the code very easy to read, will be easy to document, since it will be easy to learn about if you get frustrated and type "R.is_field?". Then much of the library code code use it.
William
Nick Alexander
> True or False
Why not R.is_field(unknown_returns=XXX) so you can specify the desired
value for "I don't know", either False or True? Otherwise, +1 -- this
has been a problem in other places for me.
Nick
Jason Grout
Would this be a good place for the proof=True/False parameter? If
proof=True, then an exception is thrown if we don't know the result. If
proof=False, then False means that we don't know for sure it is True.
A similar issue to this came up when testing equality of symbolic
expressions. There, the decision was that True was returned if we knew
two expressions were equal, and otherwise False was returned. The logic
between the equality testing and this question seems like it should be
consistent.
Thanks,
Jason
William Stein
I thought about that too. I'm not sure. Usually I think of proof=True/False as not changing the behavior of the function so much. It might work here.
A similar issue to this came up when testing equality of symbolic
expressions. There, the decision was that True was returned if we knew
two expressions were equal, and otherwise False was returned. The logic
between the equality testing and this question seems like it should be
consistent.
That's a good point -- the question is perhaps impossible to answer in general in both cases. That said, I know for a fact a lot of people will complain if R.is_field() returns False by default when one can't decide, even when R is a field, since I think that used to be the case and people *very* frequently completely. This was when is_Field(...) was in the top-level namespace (it has since been deprecated).
-- William
Simon King
On Aug 22, 8:30 pm, William Stein <wst...@gmail.com> wrote:
[...]
> > between the equality testing and this question seems like it should be
> > consistent.
>
> That's a good point -- the question is perhaps impossible to answer in
> general in both cases. That said, I know for a fact a lot of people will
> complain if R.is_field() returns False by default when one can't decide,
> even when R is a field, since I think that used to be the case and people
> *very* frequently completely. This was when is_Field(...) was in the
> top-level namespace (it has since been deprecated).
sage: is_field(RR)
True
without a deprecation warning and without importing anything in Sage
4.1
I agree that consistent behaviour is good, but I don't see the point
of the "proof=True" option: Catching an error is not more difficult
than putting an extra argument "proof=False".
What do you think about returning "None" if the answer can't be
determined?
Namely, the typical use case in existing programs should be
if R.is_field():
run some special algorithm
else:
do the generic blurp
If R.is_field() returns None, then the generic case would apply (which
is natural if one doesn't know for sure whether R is a field).
If one really wants to know whether R is provably not a field, then
one asks R.is_field()==False.
Since it is generally undecidable whether a ring is a field, I think
there should be a generic method for rings that allows the user to
assert that R is a field. Say:
sage: R = some weird definition, the user knows it is a field
sage: R.is_field()
=> NotImplementedError
sage: R.assert_field(True)
sage: R.is_field()
True
Simon
William Stein
Hi William,
On Aug 22, 8:30 pm, William Stein <wst...@gmail.com> wrote:
[...]
> > The logicIs it deprecated? I get
> > between the equality testing and this question seems like it should be
> > consistent.
>
> That's a good point -- the question is perhaps impossible to answer in
> general in both cases. That said, I know for a fact a lot of people will
> complain if R.is_field() returns False by default when one can't decide,
> even when R is a field, since I think that used to be the case and people
> *very* frequently completely. This was when is_Field(...) was in the
> top-level namespace (it has since been deprecated).
sage: is_field(RR)
True
without a deprecation warning and without importing anything in Sage
4.1
I was talking about is_Field, which behaves as I claimed:
flat:illustrations wstein$ sage
----------------------------------------------------------------------
| Sage Version 4.1.1, Release Date: 2009-08-14 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: is_Field(RR)
/Users/wstein/.sage/temp/flat.local/1363/_Users_wstein__sage_init_sage_0.py:1: DeprecationWarning:
Using is_Field from the top level is deprecated since it was designed to be used by developers rather than end users.
It most likely does not do what you would expect it to do. If you really need to use it, import it from the module that it is defined in.
# -*- coding: utf-8 -*-
True
The "is_field" is just a shorthand for R.is_field().
I agree that consistent behaviour is good, but I don't see the point
of the "proof=True" option: Catching an error is not more difficult
than putting an extra argument "proof=False".
Personally, I am for leaving things the way they are now with exceptions, and adding a way to assert that a ring is a field. See my comment on your excellent suggestion along those lines below.
What do you think about returning "None" if the answer can't be
determined?
I don't like that because None and False are basically the same thing, and I'm sure this won't make users that happy either:
sage: R = some construction of my favorite field
sage: R.is_field()
sage: # No output? It's broken!
Anyway, I think all "predicates", i.e., functions in Sage of the form "is_", should return either True or False.
Namely, the typical use case in existing programs should be
if R.is_field():
run some special algorithm
else:
do the generic blurp
If R.is_field() returns None, then the generic case would apply (which
is natural if one doesn't know for sure whether R is a field).
If one really wants to know whether R is provably not a field, then
one asks R.is_field()==False.
Since it is generally undecidable whether a ring is a field, I think
there should be a generic method for rings that allows the user to
assert that R is a field. Say:
sage: R = some weird definition, the user knows it is a field
sage: R.is_field()
=> NotImplementedError
sage: R.assert_field(True)
sage: R.is_field()
True
That's definitely a good idea. It would be good to advertise that function in the except that is raised when "R.is_field()" fails.
William
Sebastian Pancratz
a lot cleaner if the following behaviour was offered" I did not mean
that the default behaviour of the current implementations of
"is_field" etc should be changed. Instead, that is why I included the
methods "is_certainly_field" etc. However, I think your suggestion of
adjusting the current implementation of "is_field" etc by including an
optional parameter looks much cleaner.
If other people agree with this approach, I guess I can just leave a
short note explaining this behaviour in the generic method in sage/
rings/ring.pyx and then go through all inheriting classes overwriting
the method to make the adjustments, right?
Sebastian
William Stein
Yes.
I'm not sure I agree or not, but since you're "in the code" and actually working on code that is made much cleaner by making this change, I assume you know what you're talking about. So I'm fine with you making the change suggested above.
-- William
Sebastian Pancratz
> of the "proof=True" option: Catching an error is not more difficult
> than putting an extra argument "proof=False".
intermediate methods (e.g. for quotient rings, there's "is_field"
calling "is_maximal", but in principal many more methods might be
involved!) catch any errors. I don't think that it is the right
approach for the user methods to catch any errors in this case. If
there was only one type of error that could occur, I would share your
opinion, but in that case propagating the error would be essentially
the same as returning "None" as you suggest. In particular with the
typical use case in mind, I think the user should be presented with a
method to suit this, without throwing any errors.
> What do you think about returning "None" if the answer can't be
> determined?
>
> Namely, the typical use case in existing programs should be
> if R.is_field():
> run some special algorithm
> else:
> do the generic blurp
behaviour of methods like "is_field" as it is at the moment (thereby
not breaking any other code!) and introducing an optional argument to
specifically suit the typical use case.
Sebastian
Simon King
On 22 Aug., 23:46, Sebastian Pancratz <s...@pancratz.org> wrote:
[...]
> behaviour of methods like "is_field" as it is at the moment (thereby
> not breaking any other code!) and introducing an optional argument to
> specifically suit the typical use case.
field, being commutative, being integrally closed?
Thank you for working on it!
Best regards,
Simon
William Stein
Yes that would be very very nice indeed. And I think it shouldn't stop one from even changing something. E.g., it is fun to make elliptic curves over Z/nZ with n composite, and currently I do this by changing the is_field method
R.is_field = lambda : True
but it would be better to make it possible to correctly just say -- henceforth pretend R is a field.
Thank you for working on it!
Yes, many thanks!
William
Best regards,
Simon
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
Jason Grout
> If one really wants to know whether R is provably not a field, then
> one asks R.is_field()==False.
A short aside unrelated to the general discussion, but good to know:
it's usually much faster to do "some_value is False", since that is a
pointer comparison. Also, 0==False is true, where I don't think that's
what you want in the above test.
sage: %timeit None==False
1000000 loops, best of 3: 264 ns per loop
sage: %timeit None is False
10000000 loops, best of 3: 171 ns per loop
sage: a=3
sage: %timeit a==False
100000 loops, best of 3: 2.82 盜 per loop
sage: %timeit a is False
10000000 loops, best of 3: 211 ns per loop
sage: 0==False
True
sage: 0 is False
False
Jason
Sebastian Pancratz
for the two methods "is_field" and "is_integral_domain".
For the other suggestion, namely to allow the user to assert that a
ring is in fact a field, would the following be the "right" way to
implement this? 1. Add a new attribute to the ring class, say
IS_FIELD, initialised to None, 2. Implement "assert_field(check)" to
set IS_FIELD = check, 3. Change "is_field" such that (ignoring the
issue about raising an exception or returning False) if IS_FIELD is
None it should behave as now and otherwise it should return the value
of IS_FIELD.
Many thanks,
Sebastian
William Stein
Don't make it upper case. Make the attribute _is_field. Otherwise the above sounds great to me.
William
Simon King
> above sounds great to me.
dictionary, and then one can define
self._properties['integrally_closed'] = True
self._properties['field'] = False
...
I guess this would provide some flexibility, but I don't know if it
would be a "clean" thing to do.
Since I am not an experienced programmer: Are there reasons to not use
a dictionary for those kind of things?
Cheers,
Simon
William Stein
Hi!
On Aug 23, 8:42 pm, William Stein <wst...@gmail.com> wrote:
[...]
> Don't make it upper case. Make the attribute _is_field. Otherwise theOr one could have a single attribute "_properties", which is a
> above sounds great to me.
dictionary, and then one can define
self._properties['integrally_closed'] = True
self._properties['field'] = False
...
That's a great idea.
I guess this would provide some flexibility, but I don't know if it
would be a "clean" thing to do.
Since I am not an experienced programmer:
At this point you are too an experienced programmer. How many "lines of code" have you written?
Are there reasons to not use
a dictionary for those kind of things?
I can't think of any.
William
Simon King
On 24 Aug., 02:10, Minh Nguyen <nguyenmi...@gmail.com> wrote:
[...]
> > a dictionary for those kind of things?
>
>
> A bad point: can't assume that each key/value pair in a dictionary
> would always be ordered in exactly the same way. This assumption was
> uncovered during the development of Sage 4.1.1 when a doctest failed.
> The cause of the failure: the doctest assumed that printing the
> key/value pairs of a dictionary would always result in exactly the
> same arrangement of key/value pairs. Bad assumption there.
But you couldn't use the attribute "._properties" in doc tests anyway,
because AFAIK rings are cdef classes, so, you can't access the
attributes on a python level.
However, you can call the methods "is_field()", "is_integrally_closed
()" etc, which would reflect the ccontent of "._properties".
Cheers
Simon
William Stein
Hi Minh,
On 24 Aug., 02:10, Minh Nguyen <nguyenmi...@gmail.com> wrote:
[...]
> > Since I am not an experienced programmer: Are there reasons to not useBut you couldn't use the attribute "._properties" in doc tests anyway,
> > a dictionary for those kind of things?
>
> A good point: searching through a dictionary is essentially constant time.
>
> A bad point: can't assume that each key/value pair in a dictionary
> would always be ordered in exactly the same way. This assumption was
> uncovered during the development of Sage 4.1.1 when a doctest failed.
> The cause of the failure: the doctest assumed that printing the
> key/value pairs of a dictionary would always result in exactly the
> same arrangement of key/value pairs. Bad assumption there.
because AFAIK rings are cdef classes, so, you can't access the
attributes on a python level.
Yes you can, if you declare them "cdef public _properties". But the dictionaries-in-doctests issue is something we have contended with for years and their a standard solution. When you write a doctest that involves printing out d, instead print out say:
list(sorted(list(d)))
or something like that.
Simon King
> > because AFAIK rings are cdef classes, so, you can't access the
> > attributes on a python level.
>
> Yes you can, if you declare them "cdef public _properties".
> But the
> dictionaries-in-doctests issue is something we have contended with for years
> and their a standard solution. When you write a doctest that involves
> printing out d, instead print out say:
> list(sorted(list(d)))
> or something like that.
tests!
Thank you
Simon
Robert Bradshaw
> On Sun, Aug 23, 2009 at 12:27 PM, Sebastian Pancratz
> <sa...@pancratz.org> wrote:
>
> I think as a first step I'll only implement the additional argument
> for the two methods "is_field" and "is_integral_domain".
+1 to this idea.
> For the other suggestion, namely to allow the user to assert that a
> ring is in fact a field, would the following be the "right" way to
> implement this? 1. Add a new attribute to the ring class, say
> IS_FIELD, initialised to None, 2. Implement "assert_field(check)" to
> set IS_FIELD = check, 3. Change "is_field" such that (ignoring the
> issue about raising an exception or returning False) if IS_FIELD is
> None it should behave as now and otherwise it should return the value
> of IS_FIELD.
>
> Don't make it upper case. Make the attribute _is_field. Otherwise
> the above sounds great to me.
I'm not sure about this--it means everyone implementing an is_field
method will have to know about this "trick" and the number of
properties to know about grows as the number of is_* methods. What
I'd rather see is something like
sage: R = Zmod(6)
sage: K = categories.Fields(R, check=False) # any ring R
sage: K
Ring of integers modulo 6 as a field.
sage: K.is_field()
True
where all other methods are inherited via dynamically.
- Robert
William Stein
Bradshaw<robe...@math.washington.edu> wrote:
>
> On Aug 23, 2009, at 12:42 PM, William Stein wrote:
>
>> On Sun, Aug 23, 2009 at 12:27 PM, Sebastian Pancratz
>> <sa...@pancratz.org> wrote:
>>
>> I think as a first step I'll only implement the additional argument
>> for the two methods "is_field" and "is_integral_domain".
>
> +1 to this idea.
>
>> For the other suggestion, namely to allow the user to assert that a
>> ring is in fact a field, would the following be the "right" way to
>> implement this? 1. Add a new attribute to the ring class, say
>> IS_FIELD, initialised to None, 2. Implement "assert_field(check)" to
>> set IS_FIELD = check, 3. Change "is_field" such that (ignoring the
>> issue about raising an exception or returning False) if IS_FIELD is
>> None it should behave as now and otherwise it should return the value
>> of IS_FIELD.
>>
>> Don't make it upper case. Make the attribute _is_field. Otherwise
>> the above sounds great to me.
>
> I'm not sure about this--it means everyone implementing an is_field
> method will have to know about this "trick" and the number of
> properties to know about grows as the number of is_* methods.
You have a really good point.
> What I'd rather see is something like
>
> sage: R = Zmod(6)
> sage: K = categories.Fields(R, check=False) # any ring R
> sage: K
> Ring of integers modulo 6 as a field.
> sage: K.is_field()
> True
>
> where all other methods are inherited via dynamically.
That would be pretty cool. I'm not sure if I like
sage: K = categories.Fields(R, check=False)
since it could be hard for me to remember. That said, it does fit
the "Sage/Magma" design philosophy pretty nicely, and is a natural way
to use coercions and categories.
Cool idea.
William
Nicolas M. Thiery
Getting back on my late sage e-mails ...
Variant:
sage: R = Zmod(6)
sage: R.set_category(Fields()) # or maybe better R.add_category(Fields())
sage: R in Fields()
True
sage: assert R in Fields()
This avoids cluttering each sage object with an is_bla method which
might refer to a completely unrelated category bla. Also, this handles
automatically the inheritance of category (so that stating that R is
in Fields imposes that it also is a division ring, ...).
Now, to what `x in Y` should return. That's a general problem, that we
also often encounter in our enumerated sets. For example, in generic
code, it's often natural to write:
sage: assert x in Y
But what if containment test is expensive/indecidable/not implemented?
In the use case above, we would like the assertion to just be ignored.
In MuPAD, we had taken advantage of the available three-valued logic
(TRUE / FALSE / UNKNOWN), to write:
sage: assert x in Y = TRUE
which is pretty similar to the suggestion of using None for UNKNOWN
(without the peculiarities of `None` and its disadvantages that
William pointed out).
In fact, most of this kind of type checking was done by specifying the
types of the arguments of a procedure:
MuPAD: proc(R: Rings()) ...
which resulted down the road to an assertion check as above.
The downside is that there is no way to specify how hard one wants to
do a containment test.
Altogether, I would vote for something along the lines:
sage: x in Y
returns True or False if provable; raises an exception in all other cases
sage: Y.__contains__(x, proof = False)
returns a best guess, or raises an exception
sage: x.hopefully_in(Y) # find a better name!
Try in turn Y.__contains__(x, proof = False) and Y.__contains__(x)
Return False if the first returned False, or if the first raised and the second returned False
Return True in all other situations (exception, ...).
Allowing altogether for:
sage: assert x.hopefully_in(Y)
Programmatically speaking, it might be easier to use something like
Y._contains_probabilist(x) rather then Y.__contains__(x, proof =
False); this plays better with inheritance.
More thoughts on demand!
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/
Robert Bradshaw
One issue with that is that, forever after in your sage session, Zmod
(6) will be a field (unless you change it manually back, if you know
that the library function you called changed it...) That's why I
liked the new object method. Alternatively, this might be a good use
for contexts.
- Robert
Nicolas M. Thiery
Good point. I am not very keen on adding new categories on the fly
either. Then, I would vote for R = Zmod(6, category = Fields()), since
many parents readily support this features.