Opened 5 years ago

Last modified 5 years ago

#17898 closed defect

Removal of wrong stopgap — at Version 25

Reported by: aschilling Owned by:
Priority: major Milestone: sage-6.6
Component: combinatorics Keywords: stopgap, partitions
Cc: tscrim, nthiery, vdelecroix, jdemeyer Merged in:
Authors: Travis Scrimshaw, Anne Schilling Reviewers: Travis Scrimshaw, Anne Schilling
Report Upstream: N/A Work issues:
Branch: public/combinat/fix_bad_stopgap-17898 (Commits) Commit: 2f7a90d8419ca8d2202b3cb31290e58194f666e3
Dependencies: Stopgaps:

Description (last modified by aschilling)

As documented in http://trac.sagemath.org/ticket/17548 there are no reported bugs related to IntegerListsLex?. All cases listed on that ticket have non-valid input (as documented in the code).

Since the stopgap is not related to any bug and shows up in completely unrelated code, where IntegerListsLex? is correctly used, for example

sage: K = crystals.KirillovReshetikhin(['D',4,1],1,1)
/Applications/sage/local/lib/python2.7/site-packages/sage/combinat/partition.py:4827:
********************************************************************************
This code contains bugs and may be mathematically unreliable.
This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/17548.
********************************************************************************

and

sage: Partitions(3,max_part=2)
/Applications/sage/local/lib/python2.7/site-packages/sage/combinat/partition.py:6622:
********************************************************************************
This code contains bugs and may be mathematically unreliable.
This issue is being tracked at http://trac.sagemath.org/sage_trac/ticket/17548.
********************************************************************************
Partitions of 3 having parts less than or equal to 2

it should be moved to the user interface level, which is done in this ticket.

Change History (25)

comment:1 Changed 5 years ago by aschilling

  • Branch set to public/ticket/17898
  • Commit set to 39142901893bc0207e8271ccd4772469fe958e0f
  • Keywords stopgap partitions added
  • Status changed from new to needs_review

New commits:

3914290Removed erroneous stopgap

comment:2 Changed 5 years ago by tscrim

  • Status changed from needs_review to positive_review

LGTM.

comment:3 Changed 5 years ago by ncohen

  • Cc vdelecroix jdemeyer added
  • Status changed from positive_review to needs_work

Hello everybody,

Sorry to interrupt, but I believe that what is being done by this code is not advisable for Sage. You make several points in the ticket's description that I will now try to answer.

The function IntegersListsLex returns unexpected results

1) Indeed, as shown on #17637, one can get:

sage: Partitions(5, min_slope=1).list()
ValueError: [2, 4] is not a valid partition
sage: IntegerListsLex(5, length=3, max_slope=0).list()   # 0 is allowed in the partition
[[5, 0, 0], [4, 1, 0], [3, 2, 0], [3, 1, 1], [2, 2, 1]]
sage: IntegerListsLex(5, max_slope=0).list()             # now its not
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

2) Another example comes from the documentation of IntegersListsLex itself

In the following example, the slope condition is not satisfied
by the upper bound on the parts, and ``[3,3]`` is erroneously
included in the result::

    sage: list(IntegerListsLex(6, max_part=3, max_slope=-1))
    [[3, 3], [3, 2, 1]]

Returning wrong results should be considered as a bug

The fact that the docstring of this function reads that "several constraints must be satisfied by the input, lest the output be incorrect" is not a sufficient protection.

1) This function can be (and is) called by other functions. Thus, users cannot be expected to read the documentation of IntegerListsLex.

2) In general, a simple line in the documentation in a function is not a sufficient protection against wrong results. This is the reason why these 'stopgap' tickets exist.

3) It took me a couple of hours to realise that I was not able to write a code that checks that the input of IntegerListsLex is satisfiable. I take it as a proof that checking it is non-trivial (at least for me). I cannot expect users to check something that I am not able to check myself.

Some functions which call IntegerListsLex are actually correct

I agree with you that in some cases the IntegersListsLex function seems to return correct results. This is not, however, a sufficient reason to remove a stopgap whose purpose is to warn users against *possible* wrong results.

An alternative way out

As I understand that you may be bothered by those warnings, which appear in any function that calls IntegersListsLex and thus in your code too, perhaps you could go over some of the use cases of IntegerListsLex that are of interest to you, and only remove the stopgap message after you have convinced yourself that the function is indeed correct in these situations?

if (some_situation_that_was_checked):
    pass
else:
    <stopgap code>

The message would still be shown in other (unchecked) cases, and thus only in dangerous situations.

A long-term fix

As you say in this ticket's description, a real check should be implemented at the head of IntegerListsLex, or the function itself should should be reimplemented.

I gave the first option a try already, and I remember rather well the knots it made in my head, as I was going over all ways in which the parameters can be combined. Checking that they are consistent is nontrivial.

It convinced me that this function already accepts an unhealthy amount of parameters, and that we will not be able to write a function that handles all that efficiently and correctly. I believe that we should split this function into many, that will handle well each combination of parameters that interests us.

If possible in Cython, for the most useful computations. That would not be a terribly hard work, in particular for your own code which (I believe) enumerates only partitions.

Nathann

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

comment:4 follow-ups: Changed 5 years ago by tscrim

  • Status changed from needs_work to positive_review

Bad input is not a bug. Ever.

If you feel that something needs better documentation (like the description of max_slope in Partitions, then put better documentation, not some stopgap which says to everyone that *ANY* time you use this class, don't expect correct answers. By having this stopgap, you've said just that. It is obviously a horrible thing for Sage.

Also that first example is correct; it's subtle because of the trailing 0's, but it is correct.

You speak of unhealthy amount of stuff into 1 class, but IIRC you've also said that (Di)Graph needs to be one class. If you have a problem with this class, then fix it instead of saying nothing works (which is completely false).

comment:5 in reply to: ↑ 4 Changed 5 years ago by ncohen

  • Status changed from positive_review to needs_work

Hello Travis,

Bad input is not a bug. Ever.

When we are not able to write a piece of code that checks whether the input is bad, I believe that it is a bug.

If you feel that something needs better documentation [...]

I do not. I believe that the wrong results that this function returns are dangerous, and that the users should be warned.

I also proposed that you would only change this code to *not* display the warning in situations that have been checked for correction, and I would like to know why this does not satisfy you.

Also that first example is correct; it's subtle because of the trailing 0's, but it is correct.

It is an unexpected output. This example is not, however, the only one I provided. Perhaps you will accept the other lines as legit bugs?

You speak of unhealthy amount of stuff into 1 class, but IIRC you've also said that (Di)Graph needs to be one class. If you have a problem with this class, then fix it instead of saying nothing works (which is completely false).

This is totally unrelated, but since you ask I highly doubt that I ever suggested that. Indeed, this is the purpose of GenericGraph.

I will write to sage-devel in a second to ask for everybody's advice on this matter. Please, wait for this discussion to take place before setting this ticket back to positive_review.

Nathann

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

comment:7 in reply to: ↑ 4 ; follow-ups: Changed 5 years ago by dimpase

Replying to tscrim:

Bad input is not a bug. Ever.

in your own private code it will only shoot you in the foot.

As it is a non-private function is should check that the input is correct. Otherwise it has potential to do a lot of damage to other people.

I am sure you would scream "Bug!" upon finding an incorrect Python expression that Python runs without any warnings.

comment:8 in reply to: ↑ 7 ; follow-ups: Changed 5 years ago by aschilling

Replying to dimpase:

Replying to tscrim:

Bad input is not a bug. Ever.

in your own private code it will only shoot you in the foot.

As it is a non-private function is should check that the input is correct. Otherwise it has potential to do a lot of damage to other people.

I am sure you would scream "Bug!" upon finding an incorrect Python expression that Python runs without any warnings.

The stopgap that is currently in Sage now pops up all over Sage in situations where IntegerListsLex? is used within the range of parameters and hence totally fine. It just scares users unnecessarily. Also, it does not point the user to the documentation where the limitations are listed. Hence the current stopgap in Sage, in my opinion, does more harm than good!

comment:9 in reply to: ↑ 8 Changed 5 years ago by jdemeyer

Replying to aschilling:

The stopgap that is currently in Sage now pops up all over Sage in situations where IntegerListsLex? is used within the range of parameters and hence totally fine. It just scares users unnecessarily. Also, it does not point the user to the documentation where the limitations are listed.

I agree with all of this, but just removing the stopgap isn't the right solution.

comment:10 in reply to: ↑ 4 Changed 5 years ago by nbruin

Replying to tscrim:

Bad input is not a bug. Ever.

But having an interface that declares some input "bad" and other input "good" in a way that makes it hard to decide in which category your input falls is bad design, which is perhaps not a "bug" in the sense that a specification is not followed, but is certainly a "bug" in that it makes the interface very hard to use correctly.

As far as I can see, pretty much arbitrary combinations of the input parameters make sense mathematically. It might just be that they specify an empty or hard (impossible?) to enumerate set. Thus, the routine really only provides a partial implementation of the *suggested* interface.

There are probably plenty of cases (all the ones where other code calls this routine?) where you *know* your parameters lie inside the "valid" part of the parameter space. Probably because you know that a certain easily described subset lies in the "valid" part.

As Nathann suggests, just first test if the parameters are "known good". If not, either don't accept the parameters (i.e., raise an error) or print a toned-down warning:

Warning: IntegerListsLex is called with input parameters for which it is not guaranteed to produce correct output

comment:11 in reply to: ↑ 8 ; follow-ups: Changed 5 years ago by ncohen

Hello Anne,

It just scares users unnecessarily.

I totally agree with that.

I asked in my earlier comment whether you could, instead of removing the stopgap, only raise it in case that have not been checked for correctness. I do not understand why this proposal has been ignored. To me, it sounds like the best way out: you would not see it in case for which you know the code is correct, and we would see it when there is a risk. Isn't it all good for everyone?

Nathann

comment:12 in reply to: ↑ 7 Changed 5 years ago by tscrim

Replying to dimpase:

Replying to tscrim:

Bad input is not a bug. Ever.

in your own private code it will only shoot you in the foot.

As it is a non-private function is should check that the input is correct. Otherwise it has potential to do a lot of damage to other people.

I am sure you would scream "Bug!" upon finding an incorrect Python expression that Python runs without any warnings.

I would not be screaming bug, but I do agree that it makes it difficult to debug. However the equivalent of this stopgap is to say when Python starts up that "Python may evaluate incorrect expressions and may be unreliable". Would you use Python if that occurred? I wouldn't because I know there are stable languages (or at least claim to be).

@ncohen Your proposal is not being ignored, but you have brought about this current state of affairs which needs to be rectified immediately. I am not going to put my time and work into a "hard" problem which I don't see any benefit towards. Instead I think what should be done is have the paths into IntegerListsLex (e.g., in Partitions) check for bad in put (if min_slope >= 0). However the stopgap needs to be removed immediately, and then I will review your implementation.

comment:13 in reply to: ↑ 4 Changed 5 years ago by nbruin

Replying to tscrim:

Bad input is not a bug. Ever.

The documentation is inconsistent on this part for release 6.5. It has one example about "wrong" output

    In the following example, the slope condition is not satisfied
    by the upper bound on the parts, and ``[3,3]`` is erroneously
    included in the result::

        sage: list(IntegerListsLex(6, max_part=3, max_slope=-1))
        [[3, 3], [3, 2, 1]]

However, the conditions mentioned just above:

       - The upper and lower bounds themselves should satisfy the
         slope constraints.

       - The maximal and minimal slopes values should not be equal.

       - The maximal and minimal part values should not be equal.

don't mention any restrictions on max_part. In fact, it's not documented as possible input at all, so I can't even verify why the output above is wrong:

    INPUT:

    - ``n`` -- a non negative integer
    - ``min_length`` -- a non negative integer
    - ``max_length`` -- an integer or `\infty`
    - ``length`` -- an integer; overrides min_length and max_length if
      specified
    - ``floor`` -- a function `f` (or list);    defaults to ``lambda i: 0``
    - ``ceiling`` -- a function `f` (or list);  defaults to
      ``lambda i: infinity``
    - ``min_slope`` -- an integer or `-\infty`; defaults to `-\infty`
    - ``max_slope`` -- an integer or `+\infty`; defaults to `+\infty`

    An *integer list* is a list `l` of nonnegative integers, its
    *parts*. The *length* of `l` is the number of its parts;
    the *sum* of `l` is the sum of its parts.

and the meaning of max_part and min_part is not documented (not on the effect they have on the generated sequence either)

so ... the stopgap might be screaming a bit loudly, but it doesn't look wrong to me.

comment:14 Changed 5 years ago by tscrim

It does violate the assumptions because ceiling defaults to returns max_part, which is constant, whereas the max_slope condition says that all parts must be strictly decreasing. So it is wrong input. While it is not explicitly documented (which should be fixed), this hardly deserves a stopgap.

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

  • Status changed from needs_work to positive_review

I also strongly believe this stopgap message, with all of the different places this shows up across combinatorics, is very harmful to Sage. Moreover #17637 was positively reviewed and merged very quickly (within 2 days IIRC) and as such did not receive the scrutiny that it deserved. As such, this ticket is about returning to the status-quo where we can have a discussion and proposals about a good solution instead of blindly saying things may be wrong.

comment:16 in reply to: ↑ 15 Changed 5 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Replying to tscrim:

I also strongly believe this stopgap message, with all of the different places this shows up across combinatorics, is very harmful to Sage. Moreover #17637 was positively reviewed and merged very quickly (within 2 days IIRC) and as such did not receive the scrutiny that it deserved. As such, this ticket is about returning to the status-quo where we can have a discussion and proposals about a good solution instead of blindly saying things may be wrong.

In #17637, we followed the correct stopgap procedure: somebody finds a dangerous bug, a stopgap is created to warn people and in the mean time (while the stopgap exists), people can fix the bug.

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

Replying to ncohen:

I asked in my earlier comment whether you could, instead of removing the stopgap, only raise it in case that have not been checked for correctness. I do not understand why this proposal has been ignored. To me, it sounds like the best way out: you would not see it in case for which you know the code is correct, and we would see it when there is a risk. Isn't it all good for everyone?

I absolutely agree with this. Travis, if you really want to remove the stopgap, just implement the above!

comment:18 in reply to: ↑ description Changed 5 years ago by jdemeyer

Note this last sentence from the ticket description. The current branch doesn't fit this description:

Replying to aschilling:

Instead, either a check should be added to the code to check the user input or the IntegerListsLex? code should be extended to allow for all input.

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

Replying to ncohen:

Hello Anne,

It just scares users unnecessarily.

I totally agree with that.

I asked in my earlier comment whether you could, instead of removing the stopgap, only raise it in case that have not been checked for correctness. I do not understand why this proposal has been ignored. To me, it sounds like the best way out: you would not see it in case for which you know the code is correct, and we would see it when there is a risk. Isn't it all good for everyone?

Yes, since you wrote the original stopgap, I suggest that you put in the tests so that the message does not get displayed when the Partition code is used. Also, I would strongly suggest that you add a pointer to the documentation where the limitations of IntegerListsLex? is spelled out. Otherwise the stopgap message seems rather useless. At least then the user will know how to use the code!

Thanks,

Anne

comment:20 in reply to: ↑ 19 Changed 5 years ago by ncohen

Hello Anne,

Yes, since you wrote the original stopgap, I suggest that you put in the tests so that the message does not get displayed when the Partition code is used.

I know that the Partition code is used in many places, and I expect that your crystal code tests it extensively. I have to say, however, that I do not trust it very much myself: e.g. I wrote #15467 when I noticed that providing values for 'parts_in', 'starting' and 'ending' lead Sage to ignore two among the three.

I believe that this code should be rewritten from scratch, carefully, and more simply (with less combinations of parameters). That would also most definitely lead to speedups.

Also, I would strongly suggest that you add a pointer to the documentation where the limitations of IntegerListsLex? is spelled out. Otherwise the stopgap message seems rather useless. At least then the user will know how to use the code!

The description of ticket #17548 can be edited to be more informative to users of Partitions/Crystal. This is where the stopgap currently redirect users.

Nathann

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

  • Branch changed from public/ticket/17898 to public/combinat/fix_bad_stopgap-17898
  • Commit changed from 39142901893bc0207e8271ccd4772469fe958e0f to b6f375ce349643dbff01ba8cb4c86ffc5a446e0e

Replying to jdemeyer:

Replying to ncohen:

I asked in my earlier comment whether you could, instead of removing the stopgap, only raise it in case that have not been checked for correctness. I do not understand why this proposal has been ignored. To me, it sounds like the best way out: you would not see it in case for which you know the code is correct, and we would see it when there is a risk. Isn't it all good for everyone?

I absolutely agree with this. Travis, if you really want to remove the stopgap, just implement the above!

Why didn't either of you do so to begin with? Instead you both got us into this sad situation. So yet again, I had to spend my time and energy fixing this ridiculous stopgap in order for Sage not to look like it doesn't even work for simple and common combinatorial objects. I am tired of being forced into these things because someone wants to swing a hatchet around on a soapbox.

Thus the issue is now fixed. This may not be the best way, but because this situation, this ticket must go in.

sage: P = Partitions(6, min_slope=0)
sage: list(P)
[[6], [3, 3], [2, 2, 2]]

New commits:

b6f375cFix known errors and remove the appalling stopgap.

comment:22 Changed 5 years ago by git

  • Commit changed from b6f375ce349643dbff01ba8cb4c86ffc5a446e0e to 2f7a90d8419ca8d2202b3cb31290e58194f666e3

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

2f7a90dAdded a stopgap only when accessed in the global namespace.

comment:23 Changed 5 years ago by tscrim

  • Status changed from needs_work to needs_review

I've added a stopgap warning for accessing IntegerListsLex from the global namespace, otherwise the code which uses IntegerListsLex as a backend is working as expected AFAIK.

comment:24 Changed 5 years ago by ncohen

  • Status changed from needs_review to needs_info

Hello Travis,

Your current branch removes the stopgap in all cases, despite not properly checking all input (which I do not think can be done). Jeroen and I (if I did not misunderstand his position) stand for something like that:

1) If the set of parameters satisfy constraints for which we know that IntegerListsLex works, then do the job without warning 2) Otherwise, raise a warning

This is the safest path, as we have examples of what you would call bad/misleading input that should not be accepted by this function.

If I understand the intent behind your patch, you believe that IntegerListsLex is used correctly by all of Sage's functions, and that we are only at risk when users call it directly, with possibly wrong input. Thus only the 'public' version of IntegerListsLex will raise the stopgap, and all internal calls will be silent. I believe that it is dangerous too, for many user-exposed functions call IntegerListsLex (and so bypass IntegerListsLexPublic), and may also return wrong output. I am not sure that all internal calls to IntegerListsLex are safe and checked either.

To answer one of your earlier question, I personally did not implement this conditional stopgap because I do not know any restriction of the parameters for which I could swear that only trustworthy results will ever be returned. If you know such a combination and find a reviewer who double-checks it, however, that is a good way out for this ticket.

Nathann

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

comment:25 Changed 5 years ago by aschilling

  • Authors changed from Anne Schilling to Travis Scrimshaw, Anne Schilling
  • Description modified (diff)
  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Anne Schilling
  • Status changed from needs_info to needs_review
Note: See TracTickets for help on using tickets.