LatticePoset creation, better error reporting

[jm58660]

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.

CC: @dkrenn

Component: combinatorics

Author: Jori Mäntysalo, Travis Scrimshaw

Branch/Commit: 7d6e21b

Reviewer: Travis Scrimshaw, Jori Mäntysalo

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

[jm58660]

Branch: u/jmantysalo/latticeposet_creation__empty_argument__better_error_reporting

[sagetrac-git]

Commit: cbece0d

[sagetrac-git]

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

cbece0d

Some tests of exceptions.

[jm58660]

comment:3

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

[sagetrac-git]

Changed commit from cbece0d to e2d3e57

[sagetrac-git]

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

e2d3e57

Make LatticePoset() to return the empty lattice.

[jm58660]

comment:5

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.

[jm58660]

comment:6

Replying to @jm58660:

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

Ping...

[sagetrac-git]

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

b42c0e7

Error reporting for non-existing meet and join.

[sagetrac-git]

Changed commit from e2d3e57 to b42c0e7

[jm58660]

Author: Jori Mäntysalo

[jm58660]

comment:8

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

[jm58660]

comment:9

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

[tscrim]

comment:10

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.

[jm58660]

comment:11

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.

[tscrim]

comment:12

Replying to @jm58660:

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).

[jm58660]

comment:13

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.)

[jm58660]

comment:14

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.

[tscrim]

comment:15

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

[jm58660]

comment:16

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...

[tscrim]

comment:17

Replying to @jm58660:

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).

[tscrim]

comment:18

Replying to @jm58660:

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.

[tscrim]

comment:33

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.

[jm58660]

comment:34

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.

[jm58660]

comment:35

Replying to @jm58660:

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.

[jm58660]

comment:36

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

[tscrim]

comment:37

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:

2584c1d	Merge 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
7d6e21b	Do not recreate error messages, just propogate the result up.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

Changed commit from fbe30ae to 7d6e21b

[tscrim]

Changed branch from u/jmantysalo/latticeposet_creation__empty_argument__better_error_reporting to u/tscrim/lattice_errors-19163

[jm58660]

comment:38

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.

[jm58660]

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Jori Mäntysalo

[jm58660]

Changed author from Jori Mäntysalo to Jori Mäntysalo, Travis Scrimshaw

[vbraun]

Changed branch from u/tscrim/lattice_errors-19163 to 7d6e21b