Opened 6 years ago

Closed 5 years ago

#19163 closed enhancement (fixed)

LatticePoset creation, better error reporting

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.4
Component: combinatorics Keywords:
Cc: dkrenn Merged in:
Authors: Jori Mäntysalo, Travis Scrimshaw Reviewers: Travis Scrimshaw, Jori Mäntysalo
Report Upstream: N/A Work issues:
Branch: 7d6e21b (Commits, GitHub, GitLab) Commit: 7d6e21b7e78e17d84efc4d2dd5e6444fc226ea85
Dependencies: Stopgaps:

Status badges

Description (last modified by jmantysalo)

There is an error in current exception for join-semilattices:

P = Poset({'a': ['b', 'c'], 'b': ['d', 'e'], 'c': ['d', 'e'], 'd': ['f'], 'e': ['f']})
P._hasse_diagram._meet
P._hasse_diagram._join

gives

ValueError: No meet for x=4 y=3
ValueError: No join for x=4 y=3

i.e. the message is wrong for _join.

What's more, currently sage outputs only ValueError: Not a lattice. when creating a lattice. After this it will output ValueError: Not a lattice: no meet for e and d.

Change History (40)

comment:1 Changed 6 years ago by jmantysalo

  • Branch set to u/jmantysalo/latticeposet_creation__empty_argument__better_error_reporting

comment:2 Changed 6 years ago by git

  • Commit set to cbece0d1a2161cc786b1022a1ca01bea65ca6d38

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

cbece0dSome tests of exceptions.

comment:3 Changed 6 years ago by jmantysalo

This is ready for comments, even if it is not ready for review.

comment:4 Changed 6 years ago by git

  • Commit changed from cbece0d1a2161cc786b1022a1ca01bea65ca6d38 to e2d3e57198405f66192d75905e14ecf03582da2e

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

e2d3e57Make LatticePoset() to return the empty lattice.

comment:5 follow-up: Changed 5 years ago by jmantysalo

  • Cc jdemeyer added

Jeroen, can you check this until I do more? I.e. is LatticeMeetException done as it should?

This is kind of first time when I add something more than new functions to existing classes.

comment:6 in reply to: ↑ 5 Changed 5 years ago by jmantysalo

Replying to jmantysalo:

Jeroen, can you check this until I do more? I.e. is LatticeMeetException done as it should?

Ping...

comment:7 Changed 5 years ago by git

  • Commit changed from e2d3e57198405f66192d75905e14ecf03582da2e to b42c0e7cabca4264e55291ff5e6114d1d00a0a7b

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

b42c0e7Error reporting for non-existing meet and join.

comment:8 Changed 5 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Cc jdemeyer removed
  • Description modified (diff)
  • Milestone changed from sage-wishlist to sage-7.1
  • Status changed from new to needs_review

As I got no comments for custom error class, I did this with string manipulation.

comment:9 Changed 5 years ago by jmantysalo

  • Cc dkrenn added

Daniel? This is more trivial than you could think from number of lines.

comment:10 follow-up: Changed 5 years ago by tscrim

I think this approach of parsing the error message just makes things needlessly more complicated (and takes extra time if you, say, want to check if a set of posets are meet-semilattices). Instead, I would just allow the error from calling self._hasse_diagram.meet_matrix() to propagate up.

comment:11 in reply to: ↑ 10 ; follow-up: Changed 5 years ago by jmantysalo

Replying to tscrim:

I think this approach of parsing the error message just makes things needlessly more complicated (and takes extra time if you, say, want to check if a set of posets are meet-semilattices).

?? Error message is only parsed when there is a message. And to just check use is_meet_semilattice(). I can't see how this would slow down anything.

Instead, I would just allow the error from calling self._hasse_diagram.meet_matrix() to propagate up.

It is very irritating if the elements of the lattice are integers. Then we may got error saying that 5 and 8 have no meet, when actually it is 6 and 10 that have no meet.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 5 years ago by tscrim

Replying to jmantysalo:

Replying to tscrim:

I think this approach of parsing the error message just makes things needlessly more complicated (and takes extra time if you, say, want to check if a set of posets are meet-semilattices).

?? Error message is only parsed when there is a message. And to just check use is_meet_semilattice(). I can't see how this would slow down anything.

Suppose you iterate over a collection of posets and you want to determine which of them are (semi)lattices. Then for those that are lattices, you do some extra processing on them. Being Pythonic (and to avoid double checking things), you just cast the poset to a lattice and do nothing if an error is thrown. That is where the slowdown comes in.

Instead, I would just allow the error from calling self._hasse_diagram.meet_matrix() to propagate up.

It is very irritating if the elements of the lattice are integers. Then we may got error saying that 5 and 8 have no meet, when actually it is 6 and 10 that have no meet.

That is a good point. However, I would much rather have a less informative error message than the (IMO fugly) string parsing code you currently have. It seems like Volker's suggestion of doing a custom error class will be what you want (if you think it is important to see (only) one instance where the lattice property fails).

comment:13 in reply to: ↑ 12 Changed 5 years ago by jmantysalo

Replying to tscrim:

Suppose you iterate over a collection of posets and you want to determine which of them are (semi)lattices. Then for those that are lattices, you do some extra processing on them. Being Pythonic (and to avoid double checking things), you just cast the poset to a lattice and do nothing if an error is thrown. That is where the slowdown comes in.

You mean something like

n = 0
for P in PP:
    try:
        if LatticePoset(P).cardinality() != 0:
            n += 1
    except:
        pass

where PP is precomputed list of posets. This error reporting is O(1) and checking if a poset is lattice is O(n^2.5). So this would be a question only if most posets are non-lattices that are easily recognized (like a poset that is not bounded). I will run some timing on this.

Instead, I would just allow the error from calling self._hasse_diagram.meet_matrix() to propagate up.

It is very irritating if the elements of the lattice are integers. Then we may got error saying that 5 and 8 have no meet, when actually it is 6 and 10 that have no meet.

That is a good point. However, I would much rather have a less informative error message than the (IMO fugly) string parsing code you currently have. It seems like Volker's suggestion of doing a custom error class will be what you want (if you think it is important to see (only) one instance where the lattice property fails).

I guess this conflicts with performance you cared in a paragraph just before this one :=). I suppose creating an object is slower than manipulating a string.

Actually I did a code using specific error class and tried to get comments on it, to be sure that I did nothing stupid. But as I got no comments, I decided to do this in a way that I know to work. (And added tests, so that if somebody changes the error string at hasse_diagram.py it will be noticed.)

comment:14 Changed 5 years ago by jmantysalo

I tested with a list of all non-isomorphic posets of 8 elements. There are 16999 of those.

Before the patch it took 0,69 seconds to run my test code for the first time. Second run took 0,39 seconds. After the patch timings were 0,70 and 0,41 second. So this will take something like 15 ms for 15000 posets, i.e. a microsecond per poset. (At i5-3470 CPU @ 3.20GHz).

I think that this in not too much penalty for better usability.

comment:15 follow-up: Changed 5 years ago by tscrim

Thanks for doing those timings. I didn't expect too much of a penalty, but if we can have cleaner and less fragile code with extra speed, then why shouldn't we?

I would say the lack of response for your question (if it was "Am I doing something stupid?") is a strong indication that you are not. Personally, I don't think we need to include this in the error message as pdb can be used, but I'm neutral if we add it responsibly.

In more detail, the fragility comes from the fact that we have to rewrite this error message if the underlying error message changes wording. By having a custom class, it means we can easily change the message without having to rewrite this (essentially unrelated) code.

Also, the int(error.message.split()[3][2:]) creates many, many new transient objects: the split, in and of itself, creates a new list, plus the int, plus each of the strings in the split. However I was thinking of doing a catch-and-release with the error message by simply updating the two elements of said message. So the error class would look something like this:

class LatticeException(ValueError):
    def __init__(self, fail, x, y):
        ValueError.__init__(self, None)
        self.fail = fail
        self.x = x
        self.y = y
    def __str__(self):
        return "no {} for {} and {}".format(self.fail, self.x, self.y)

The result would look like this:

sage: raise LatticeException('meet', 5, 2)
---------------------------------------------------------------------------
LatticeException                          Traceback (most recent call last)
<ipython-input-20-626aad3b7a17> in <module>()
----> 1 raise LatticeException('meet', Integer(5), Integer(2))

LatticeException: no meet for 5 and 2

comment:16 in reply to: ↑ 15 ; follow-ups: Changed 5 years ago by jmantysalo

Replying to tscrim:

I would say the lack of response for your question (if it was "Am I doing something stupid?") is a strong indication that you are not.

No. I do not trust silence being acception.

But see my commit on comment number 3. I guess it was something like what you suggested.

In more detail, the fragility comes from the fact that we have to rewrite this error message if the underlying error message changes wording.

That's why I added tests. We could also add a comment to the code raising exception in _meet() and _join().

Also, the int(error.message.split()[3][2:]) creates many, many new transient objects: the split, in and of itself, creates a new list, plus the int, plus each of the strings in the split.

Maybe I can optimize if, it one microsecond is too much...

comment:17 in reply to: ↑ 16 Changed 5 years ago by tscrim

Replying to jmantysalo:

Replying to tscrim:

I would say the lack of response for your question (if it was "Am I doing something stupid?") is a strong indication that you are not.

No. I do not trust silence being acception.

But see my commit on comment number 3. I guess it was something like what you suggested.

Then consider this as acceptance of doing a custom error message (along with Volker's comment on the sage-devel thread).

Last edited 5 years ago by tscrim (previous) (diff)

comment:18 in reply to: ↑ 16 Changed 5 years ago by tscrim

Replying to jmantysalo:

Replying to tscrim:

In more detail, the fragility comes from the fact that we have to rewrite this error message if the underlying error message changes wording.

That's why I added tests. We could also add a comment to the code raising exception in _meet() and _join().

It's not about the tests; it is about the fact you have to change code in the frontend class anytime you change this error message in the backend. An analogy would be like you changed the background color attribute in a css file, but now you have to change html code of the webpage because of that.

Also, the int(error.message.split()[3][2:]) creates many, many new transient objects: the split, in and of itself, creates a new list, plus the int, plus each of the strings in the split.

Maybe I can optimize if, it one microsecond is too much...

That was mainly as a counterpoint to your statement creating objects is more costly than string parsing. I strongly believe string parsing is an evil practice. The fact that it is (micro) slower is just a small part of that belief. The much bigger issue is the readability, extendability, and fragility of the code.

Last edited 5 years ago by tscrim (previous) (diff)

comment:19 Changed 5 years ago by git

  • Commit changed from b42c0e7cabca4264e55291ff5e6114d1d00a0a7b to bc131c26bb40434df3ae5cf4f9c77d9d37b01c52

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

bc131c2Use exception class.

comment:20 Changed 5 years ago by jmantysalo

  • Status changed from needs_review to needs_work

Doctests on hasse_diagram.py must be corrected, but otherwise this is ready for comments.

comment:21 Changed 5 years ago by git

  • Commit changed from bc131c26bb40434df3ae5cf4f9c77d9d37b01c52 to 0d0a09a405986b478644873761d2dd59cad03dc6

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

0d0a09aModified tests.

comment:22 Changed 5 years ago by jmantysalo

  • Status changed from needs_work to needs_review

Doctests corrected.

comment:23 follow-up: Changed 5 years ago by tscrim

Thank you for making the changes; it definitely improves the code. A few comments:

  • Move the comment before LatticeException as the docstring for that class so it is visible in the doc.
  • Could be bikeshedding, but I'm thinking we should call it LatticeError since it is inheriting from ValueError.
  • Make the default value for x and y in LatticeException to be None.
  • All methods need doctests, this includes those for the exceptions
  • I would consider making the no top/bottom errors just raise ValueError. Granted, this won't look as slick when the error gets reported, but it will be cleaner code. (This would mean we don't need default values for LatticeException.) IMO this is also okay since LatticeException inherits from ValueError.
  • The errors are not sentences, so they should start with a lowercase letter.
  • I would do:
    try:
        P._hasse_diagram.meet_matrix()
    except LatticeException as error:
        error.x = P._vertex_to_element(error.x)
        error.y = P._vertex_to_element(error.y)
        raise
    
  • Unrelated but I noticed it because there were changes made. I would do this:
    -if isinstance(data,FiniteLatticePoset) and len(args) == 0 and len(options) == 0:
    +if (isinstance(data, FiniteLatticePoset) and not args and not options):
    
    as it is the fastest way to check for emptiness.

comment:24 in reply to: ↑ 23 ; follow-up: Changed 5 years ago by jmantysalo

Replying to tscrim:

  • I would consider making the no top/bottom errors just raise ValueError. Granted, this won't look as slick when the error gets reported, but it will be cleaner code. (This would mean we don't need default values for LatticeException.) IMO this is also okay since LatticeException inherits from ValueError.

But then I guess that LatticePoset(P) could say "not a semilattice", assuming that I don't check the error string. Is that bad? Not that much, but...?

comment:25 Changed 5 years ago by git

  • Commit changed from 0d0a09a405986b478644873761d2dd59cad03dc6 to a60a36bd61d937ca05ebd2f791f8132368ccb83a

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

7d3620eSome tuning.
a60a36bSome tuning to hasse_diagram.py.

comment:26 Changed 5 years ago by jmantysalo

I did some changes. But I got strange error from make:

[polynomia] build succeeded.
Error building the documentation.
Traceback (most recent call last):
  File "/home/jm58660/sage/local/lib/python/runpy.py", line 162, in _run_module_as_main
    "__main__", fname, loader, pkg_name)
  File "/home/jm58660/sage/local/lib/python/runpy.py", line 72, in _run_code
    exec code in run_globals
  File "/home/jm58660/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
    main()
  File "/home/jm58660/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1620, in main
    builder()
  File "/home/jm58660/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 280, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/home/jm58660/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 491, in _wrapper
    x.get(99999)
  File "/home/jm58660/sage/local/lib/python/multiprocessing/pool.py", line 567, in get
    raise self._value
AttributeError: 'module' object has no attribute 'has'
make[2]: *** [doc-html] Error 1

Any ideas?

comment:27 in reply to: ↑ 24 ; follow-up: Changed 5 years ago by jmantysalo

Replying to jmantysalo:

Just pinging for this question:

But then I guess that LatticePoset(P) could say "not a semilattice", assuming that I don't check the error string. Is that bad? Not that much, but...?

comment:28 Changed 5 years ago by jmantysalo

Ping.

comment:29 in reply to: ↑ 27 ; follow-up: Changed 5 years ago by tscrim

Replying to jmantysalo:

Replying to jmantysalo:

Just pinging for this question:

But then I guess that LatticePoset(P) could say "not a semilattice", assuming that I don't check the error string. Is that bad? Not that much, but...?

Well, perhaps just have x and y be default to None in the exception __init__, but it contradicts your docstring for LatticeError. Moreover, I still think you should let that propagate up rather than creating a completely new error message.

comment:30 Changed 5 years ago by jmantysalo

  • Status changed from needs_review to needs_work

Needs thinking. I put this to needs_work to see what tickets are really just waiting for a review.

comment:31 Changed 5 years ago by git

  • Commit changed from a60a36bd61d937ca05ebd2f791f8132368ccb83a to fbe30ae2b1bbe2e1e3aeb0dca6ca4867c01a65fa

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

fbe30aeError reporting for lattice creation.

comment:32 Changed 5 years ago by jmantysalo

  • Description modified (diff)
  • Milestone changed from sage-7.1 to sage-7.3
  • Priority changed from minor to major
  • Status changed from needs_work to needs_review
  • Summary changed from LatticePoset creation: Empty argument, better error reporting to LatticePoset creation, better error reporting

OK, this was actually quite simple after thinking. Also I found an error in the process.

comment:33 in reply to: ↑ 29 ; follow-up: Changed 5 years ago by tscrim

  • Status changed from needs_review to needs_work

Replying to tscrim:

Moreover, I still think you should let that propagate up rather than creating a completely new error message.

This is still an issue, both for readability and performance. I can write a modified version if you want.

comment:34 in reply to: ↑ 33 ; follow-up: Changed 5 years ago by jmantysalo

Replying to tscrim:

Replying to tscrim:

Moreover, I still think you should let that propagate up rather than creating a completely new error message.

This is still an issue, both for readability and performance. I can write a modified version if you want.

Please do so, as I think that I don't understand what you mean.

comment:35 in reply to: ↑ 34 Changed 5 years ago by jmantysalo

Replying to jmantysalo:

Replying to tscrim:

Replying to tscrim:

Moreover, I still think you should let that propagate up rather than creating a completely new error message.

This is still an issue, both for readability and performance. I can write a modified version if you want.

Please do so, as I think that I don't understand what you mean.

Just pingin this.

comment:36 Changed 5 years ago by jmantysalo

Another ping. I don't get what you suggest until I see a code or at least a pseudocode.

comment:37 follow-up: Changed 5 years ago by tscrim

  • Branch changed from u/jmantysalo/latticeposet_creation__empty_argument__better_error_reporting to u/tscrim/lattice_errors-19163
  • Commit changed from fbe30ae2b1bbe2e1e3aeb0dca6ca4867c01a65fa to 7d6e21b7e78e17d84efc4d2dd5e6444fc226ea85
  • Milestone changed from sage-7.3 to sage-7.4
  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_work to needs_review

Sorry it took so long, kept having other things come up. Here is what I am suggesting, where we don't recreate the error, just trap it long enough to change the element labels.


New commits:

2584c1dMerge branch 'u/jmantysalo/latticeposet_creation__empty_argument__better_error_reporting' of git://trac.sagemath.org/sage into u/jmantysalo/latticeposet_creation__empty_argument__better_error_reporting
7d6e21bDo not recreate error messages, just propogate the result up.

comment:38 in reply to: ↑ 37 Changed 5 years ago by jmantysalo

  • Status changed from needs_review to positive_review

Now I understand: Green solution, recycling of error message!

Also test passed, and I manually checked meet- and join-semilattices. Hence positive review.

Replying to tscrim:

Sorry it took so long

No horry. I have said to some developer (you?) earlier: it took about 2000 years to proof that squaring a circle is impossible. So there is no horry, this is mathematics.

comment:39 Changed 5 years ago by jmantysalo

  • Authors changed from Jori Mäntysalo to Jori Mäntysalo, Travis Scrimshaw
  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Jori Mäntysalo

comment:40 Changed 5 years ago by vbraun

  • Branch changed from u/tscrim/lattice_errors-19163 to 7d6e21b7e78e17d84efc4d2dd5e6444fc226ea85
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.