doctesting __hash__ ?

4 views
Skip to first unread message

William Stein

unread,
Jan 23, 2009, 3:41:31 PM1/23/09
to Martin Albrecht, sage-...@googlegroups.com
On Fri, Jan 23, 2009 at 9:24 AM, Martin Albrecht
<ma...@informatik.uni-bremen.de> wrote:
> On Friday 23 January 2009, you wrote:
>> Hi Martin,
>>
>> I don't like the hash doctest changes you introduced in #4965.
>> They should be
>>
>> sage: hash(GF(3^4),'a')
>>
>> or
>>
>> sage: h = hash(GF(3^4),'a')
>>
>> instead of
>>
>> sage: {GF(3^4, 'a'):1} #indirect doctest
>> {Finite Field in a of size 3^4: 1}
>
> I disagree. h = hash(GF(3^4,'a')) encodes no information whatsoever except
> that the function actually returns something. Printing the explicit values is
> weird also because it just doesn't matter what that value is if it is
> sufficiently pseudo-random.
>
> sage: {GF(3^4, 'a'):1} #indirect doctest
> {Finite Field in a of size 3^4: 1}
>
> tests one very important use-case.
>
> Martin

I disagree. {GF(3^4, 'a'):1} also tests nothing whatsover except that the
hash function actually returns something. Using a dictionary with key 1
is weird also because it just doens't matter what hash was computed.

I think we are both wrong. Doctesting of __hash__ should be done by
a function:

sage: test.hash(GF(3^4, 'a'))
'ok' # or not raise exception

The advantages of doing this:

(1) It is readable -- it's clear what is being done -- a function
made for testing hashing is read.

(2) it centralizes the design decision about what the actual test
should be. One huge objection to you changing all the doctests in
your files, is that they are now inconsistent with the rest of sage,
which is very jarring for readers (it certainly was for me).

(3) it enables all kinds of interestings tests to be put in
test.hash. For example, suppose I wonder if there are any objects in
Sage with the property that calling hash multiple times doesn't get
"very fast" after the first call (e.g, the bug in your
finite_field_givaro.pyx hash that I fixed). I can easily just change
test.hash to test for that, run the test suite, and it will tell me
everywhere this happens. Or suppose I want to hunt for instances
where hashing is inconsistent (doesn't always return the same thing on
10 calls say) -- again that's easy. Suppose we decide that
set([GF(3^4,'a'))]) is a good test -- we could trivially add that.

William

Robert Bradshaw

unread,
Jan 23, 2009, 4:03:45 PM1/23/09
to sage-...@googlegroups.com

This sounds like an interesting proposal, but where does test come
from? I guess it's some global variable of some sort.

I don't like how it obscures what is actually being tested, i.e. the
desirable properties and design decisions of the hash. nor are there
ways to overwrite it (e.g. one might want hash(5) == hash(R(5)) for
most rings R, but if R=GF(3) this will fail.)

- Robert


Carl Witty

unread,
Jan 23, 2009, 6:35:00 PM1/23/09
to sage-devel
On Jan 23, 1:03 pm, Robert Bradshaw <rober...@math.washington.edu>
wrote:
I like this part of the proposal (although I suggest the name
"doctest" instead of "test").

> I don't like how it obscures what is actually being tested, i.e. the  
> desirable properties and design decisions of the hash. nor are there  
> ways to overwrite it (e.g. one might want hash(5) == hash(R(5)) for  
> most rings R, but if R=GF(3) this will fail.)

Also, I actually like the testing of just printing out the hash code.
Yes, it's pretty meaningless; but you'll notice if things hash to 0,
and you'll notice if some change accidentally changes the hash code.

Carl

William Stein

unread,
Jan 23, 2009, 7:16:59 PM1/23/09
to sage-...@googlegroups.com

One can just include all that too if you want.

William

Nicolas M. Thiery

unread,
Feb 6, 2009, 2:53:21 PM2/6/09
to sage-...@googlegroups.com
Dear all,


On Fri, Jan 23, 2009 at 12:41:31PM -0800, William Stein wrote:
> ... discussion about the right way of testing __hash__


>
> Doctesting of __hash__ should be done by a function:
>
> sage: test.hash(GF(3^4, 'a'))
> 'ok' # or not raise exception
>
> The advantages of doing this:
>
> (1) It is readable -- it's clear what is being done -- a function
> made for testing hashing is read.
>
> (2) it centralizes the design decision about what the actual test
> should be. One huge objection to you changing all the doctests in
> your files, is that they are now inconsistent with the rest of sage,
> which is very jarring for readers (it certainly was for me).
>
> (3) it enables all kinds of interestings tests to be put in
> test.hash. For example, suppose I wonder if there are any objects in
> Sage with the property that calling hash multiple times doesn't get
> "very fast" after the first call (e.g, the bug in your
> finite_field_givaro.pyx hash that I fixed). I can easily just change
> test.hash to test for that, run the test suite, and it will tell me
> everywhere this happens. Or suppose I want to hunt for instances
> where hashing is inconsistent (doesn't always return the same thing on
> 10 calls say) -- again that's easy. Suppose we decide that
> set([GF(3^4,'a'))]) is a good test -- we could trivially add that.

I just want to mention that I am precisely setting up a standardized
way in the category framework for setting up this kind of generic
tests. See in particular Sets? after installing the sage-combinat
patches. Comments, suggestions and reviews most welcome!

General idea: Imagine you have just implemented a parent P in the
category SemiGroups(). Here, I'll just take the example of semi-group
provided by the category:

sage: P = SemiGroups().example()
The trivial semigroup with a*b == a

(for the record, this line above is fake, but it will actually work
very soon; by the way: should this be called a_parent() or something else?)

Now, you want to run generic checks on P. You can just do:

sage: P.check(verbose = True)
running test_an_element ...
running test_some_elements ...
running test_pickling ...
running test_element_pickling ...
running test_associativity ...

If you want to run individual tests, you can do directly:

sage: P.test_associativity()

In case something goes wrong (which is the case currently, bummer),
you get a traceback:

sage: P.check()
PicklingError Traceback (most recent call last)
...
PicklingError: Can't pickle ...


Let's open the hood. Here is the default implementation for
test_associativity, which is provided by the SemiGroups category:

def test_associativity(self, tester = trivial_tester):
tester.assert_(all((x * y) * z == x * (y * z)
for x in self.some_elements()
for y in self.some_elements()
for z in self.some_elements()))


The tester gadget is a plugin mechanism so that in the long run one
will be able to ask for other treatment of errors, like issuing
warnings, counting the errors, or using the test case within a
standard testunit framework.

some_elements is a method, similar to an_element, which returns a
"good" collection of elements, typically to run tests upon. What
"good" means is left upon the parent implementer, but there are some
reasonable defaults (like returning all the elements for a finite
group, or all the basis elements for a finite dimensional vector
space). Of course, there should be an easy way for the user to specify
on which sets he wants to run the tests, so as to use this method for
proofs.


P.check() (should it be P.test()?) just calls every methods of the
parent called test* (parallel to what is done in testunit). So the
parent may very well add extra test cases, or override some of them
with more efficient ones.

To come back to __hash__, a sane default might be to check that
__hash__ at least returns something different for each element in
P.some_elements() (I am not sure about the specs of __hash__; should
we also check that __hash__ returns an int?).

Best regards,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

mabshoff

unread,
Feb 6, 2009, 4:01:56 PM2/6/09
to sage-devel


On Feb 6, 11:53 am, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
>         Dear all,

<SNIP>

HI Nicolas,
This looks *very* cool and useful. Any idea when it will be ready and
how much of it has a dependency on code in Sage-combinat not yet
merged into Sage?

Cheers,

Michael

> --
> Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>http://Nicolas.Thiery.name/

William Stein

unread,
Feb 6, 2009, 6:32:25 PM2/6/09
to sage-...@googlegroups.com
On Fri, Feb 6, 2009 at 1:01 PM, mabshoff <mabs...@googlemail.com> wrote:
>
>
>
> On Feb 6, 11:53 am, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
> wrote:
>> Dear all,
>
> <SNIP>
>
> HI Nicolas,
>
>> I just want to mention that I am precisely setting up a standardized
>> way in the category framework for setting up this kind of generic
>> tests. See in particular Sets? after installing the sage-combinat
>> patches. Comments, suggestions and reviews most welcome!
>>
>> General idea: Imagine you have just implemented a parent P in the
>> category SemiGroups(). Here, I'll just take the example of semi-group
>> provided by the category:
>>
>> sage: P = SemiGroups().example()
>> The trivial semigroup with a*b == a
>>
>> (for the record, this line above is fake, but it will actually work
>> very soon; by the way: should this be called a_parent() or something else?)
>>
>> Now, you want to run generic checks on P. You can just do:
>>
>> sage: P.check(verbose = True)
>> running test_an_element ...
>> running test_some_elements ...
>> running test_pickling ...
>> running test_element_pickling ...
>> running test_associativity ...

>> Best regards,


>> Nicolas
>
> This looks *very* cool and useful. Any idea when it will be ready and
> how much of it has a dependency on code in Sage-combinat not yet
> merged into Sage?

Yes, a very big +1. I definitely would want to have doctests that use the
above in Sage somewhere.

William

Nicolas M. Thiery

unread,
Feb 9, 2009, 5:21:51 PM2/9/09
to sage-...@googlegroups.com
On Fri, Feb 06, 2009 at 03:32:25PM -0800, William Stein wrote:
> On Fri, Feb 6, 2009 at 1:01 PM, mabshoff <mabs...@googlemail.com> wrote:
> > On Feb 6, 11:53 am, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>

:-)

It's quite tied up into the category framework, so I don't see a way
to merge it into Sage without the category framework. As for the
category framework itself: it has been experimented with quite much
during the sage-combinat workshop, and sounds reasonably stable and
definitely useful. So it would make sense to start thinking about the
merge. At this stage, I'd love to get comments and pre-reviews on the
design from the Sage community.

There is one show-stopper though: the class pickling issue. I still
did not get any answer from my post in comp.lang.python and feel
pretty much stuck.

http://groups.google.com/group/comp.lang.python/msg/92fdf6759c0e087f

Any ideas on who to contact?

All the best,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

Robert Bradshaw

unread,
Feb 9, 2009, 11:40:47 PM2/9/09
to sage-...@googlegroups.com

Yes, let's get some non-combinat people looking at this! Could the
relevant patches be posted to a ticket?

> There is one show-stopper though: the class pickling issue. I still
> did not get any answer from my post in comp.lang.python and feel
> pretty much stuck.
>
> http://groups.google.com/group/comp.lang.python/msg/92fdf6759c0e087f
>
> Any ideas on who to contact?

I personally have no idea on this, but pickling is something that
certainly needs to work well. Is this because you're still making
classes on the fly to parallel all the existing classes?

- Robert

Nicolas M. Thiery

unread,
Feb 10, 2009, 5:45:02 AM2/10/09
to sage-...@googlegroups.com
Hi Robert,

> > It's quite tied up into the category framework, so I don't see a way
> > to merge it into Sage without the category framework. As for the
> > category framework itself: it has been experimented with quite much
> > during the sage-combinat workshop, and sounds reasonably stable and
> > definitely useful. So it would make sense to start thinking about the
> > merge. At this stage, I'd love to get comments and pre-reviews on the
> > design from the Sage community.
>
> Yes, let's get some non-combinat people looking at this! Could the
> relevant patches be posted to a ticket?

Will do. Though I'd recommend anyone wanting to look seriously at this
to just run:

sage -combinat install

The relevant patches (in .hg/patches) are:

categories-nt.patch
hopf_algebras-nt.patch
semi-group-monoids-category-fh.patch

(sorry, this is big, if not just because there are about 80 categories)

> > There is one show-stopper though: the class pickling issue. I still
> > did not get any answer from my post in comp.lang.python and feel
> > pretty much stuck.
>

> I personally have no idea on this, but pickling is something that
> certainly needs to work well.

YES. And currently my patch breaks pickling for many, if not most,
sage parents and elements (those that are not cythoned).

> Is this because you're still making
> classes on the fly to parallel all the existing classes?

Indeed. There is an easy and robust fix, which is to exchange two
lines in pickle.py and cpickle.py. But this means changing plain
python libraries with all the debates that this should raise.

Cheers,

mabshoff

unread,
Feb 10, 2009, 4:57:57 PM2/10/09
to sage-devel


On Feb 10, 2:45 am, "Nicolas M. Thiery" <Nicolas.Thi...@u-psud.fr>
wrote:
>         Hi Robert,
>
> > > It's quite tied up into the category framework, so I don't see a way
> > > to merge it into Sage without the category framework. As for the
> > > category framework itself: it has been experimented with quite much
> > > during the sage-combinat workshop, and sounds reasonably stable and
> > > definitely useful. So it would make sense to start thinking about the
> > > merge. At this stage, I'd love to get comments and pre-reviews on the
> > > design from the Sage community.
>
> > Yes, let's get some non-combinat people looking at this! Could the  
> > relevant patches be posted to a ticket?
>
> Will do. Though I'd recommend anyone wanting to look seriously at this
> to just run:
>
>         sage -combinat install

Nicolas, now I am seeing your intention, you are just trying to get
people to use combiant :)

> The relevant patches (in .hg/patches) are:
>
>         categories-nt.patch
>         hopf_algebras-nt.patch
>         semi-group-monoids-category-fh.patch
>
> (sorry, this is big, if not just because there are about 80 categories)

Yes, and my suspicion that hopf_algebras-nt.patch was "just" in there
to get code into Sage is wrong - it seems to be somewhat mislabeled.
Overall this is an amazing amount of hard work.

> > > There is one show-stopper though: the class pickling issue. I still
> > > did not get any answer from my post in comp.lang.python and feel
> > > pretty much stuck.
>
> > I personally have no idea on this, but pickling is something that  
> > certainly needs to work well.
>
> YES. And currently my patch breaks pickling for many, if not most,
> sage parents and elements (those that are not cythoned).

Yeah, that is a major issue.

> > Is this because you're still making  
> > classes on the fly to parallel all the existing classes?
>
> Indeed. There is an easy and robust fix, which is to exchange two
> lines in pickle.py and cpickle.py. But this means changing plain
> python libraries with all the debates that this should raise.

Well, we ship our own Python for a reason, but this causes trouble for
distributions. Could you open another thread and describe the problem
in detail - maybe something good will come out of it.

> Cheers,
>                                 Nicolas

Cheers,

Michael

> --
> Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>http://Nicolas.Thiery.name/

Nicolas M. Thiery

unread,
Feb 12, 2009, 5:36:20 PM2/12/09
to sage-...@googlegroups.com
On Tue, Feb 10, 2009 at 01:57:57PM -0800, mabshoff wrote:
> Nicolas, now I am seeing your intention, you are just trying to get
> people to use combiant :)

Of course, what else?

> > (sorry, this is big, if not just because there are about 80 categories)
>
> Yes, and my suspicion that hopf_algebras-nt.patch was "just" in there
> to get code into Sage is wrong - it seems to be somewhat mislabeled.
> Overall this is an amazing amount of hard work.

:-)

The name is indeed misleading. It just evolved as such from having to
work out a complete example of category usage to check that all of
this was not complete nonsense. And of course I am biased when it come
to my favorite example :-)

> Well, we ship our own Python for a reason, but this causes trouble for
> distributions. Could you open another thread and describe the problem
> in detail - maybe something good will come out of it.

Will do!

Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

Nicolas M. Thiery

unread,
Feb 14, 2009, 3:08:04 AM2/14/09
to sage-...@googlegroups.com
Dear Robert and all,


On Tue, Feb 10, 2009 at 11:45:02AM +0100, Nicolas Thiéry wrote:
> About the category framework patch ...

I'll be in Davis from March 2nd to July 15th. In particular it will be
easy for me to go to the upcoming Sage Days at MSRI. That could be a
good occasion to work on the integration of the category patch. Who
will be there besides William and Mike?

I could also come to Seattle at some point.

Reply all
Reply to author
Forward
0 new messages