Method rank adjustment needed in GreensXClassOfElement

[wilfwilson]

Example: GreensDClassOfElement has filters [IsSemigroup, IsMultiplicativeElement], which (now that GAP master branch has fixed ranks of methods) is beaten by the library method with filters [IsSemigroup and HasIsFinite and IsFinite, IsObject]. The method is the Semigroups package also applies only to finite semigroups, but since it first checks whether its argument is finite, the result is that it has a lower rank than the worse library method.

Therefore the following things happen:

gap> D := GreensDClassOfElement(
>  Semigroup(
>    BooleanMat([[0, 1, 1, 0, 1, 0], [0, 1, 0, 1, 0, 0], [1, 1, 1, 0, 0, 0],
>                [0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1], [1, 0, 1, 0, 1, 1]]),
>    BooleanMat([[1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 1, 0], [0, 1, 0, 1, 1, 0],
>                [1, 0, 1, 1, 1, 0], [1, 1, 1, 0, 0, 1], [1, 1, 0, 0, 0, 0]])),
>  BooleanMat([[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1],
>              [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]));;
gap> IsEnumerableSemigroupGreensClassRep(D);
true
gap> LoadPackage("rcwa", false);
#I  method installed for SmallGeneratingSet matches more than one declaration
#I  method installed for DirectProductOp matches more than one declaration
#I  method installed for SmallGeneratingSet matches more than one declaration
#I  method installed for PreImagesSet matches more than one declaration
#I  method installed for Factorization matches more than one declaration
#I  method installed for Factorization matches more than one declaration
#I  method installed for DirectProductOp matches more than one declaration
#I  method installed for SmallGeneratingSet matches more than one declaration
#I  method installed for Factorization matches more than one declaration
#I  method installed for StructureDescription matches more than one declaration
#I  method installed for StructureDescription matches more than one declaration
true
gap> D := GreensDClassOfElement(
>  Semigroup(
>    BooleanMat([[0, 1, 1, 0, 1, 0], [0, 1, 0, 1, 0, 0], [1, 1, 1, 0, 0, 0],
>                [0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1], [1, 0, 1, 0, 1, 1]]),
>    BooleanMat([[1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 1, 0], [0, 1, 0, 1, 1, 0],
>                [1, 0, 1, 1, 1, 0], [1, 1, 1, 0, 0, 1], [1, 1, 0, 0, 0, 0]])),
>  BooleanMat([[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1],
>              [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]));;
gap> IsEnumerableSemigroupGreensClassRep(D);
false

This leads to horrendous diffs in the test files.

[wilfwilson]

See gap-system/gap#2513 and gap-system/gap#2773

[james-d-mitchell]

Just to comment that the checking for finiteness inside the method (not in the filter) is intentional, since we have some methods for checking if some types of semigroups are finite, without enumerating them.

[wilfwilson]

Of course!

[james-d-mitchell]

Is this resolved @wilfwilson ? Or are we waiting for something? If it's resolve, please close the issue. Thanks!

[james-d-mitchell]

Sorry, don't close the issue but mark it resolved-pending-release, thanks!

[wilfwilson]

This specific problem is resolved, but we should expect similar such problems in the future.

[james-d-mitchell]

Why should we expect similar such problems in the future @wilfwilson ??

[wilfwilson]

In GAP's master branch, gap-system/gap#2773 was merged, fixing gap-system/gap#2513.

The result is that the applicability of methods is now being calculated correctly. In particular, for semigroup-related objects, this means that in some cases different methods are being applied from before, and not necessarily the ones that we want. This is causing problems, and I believe it is our problem to fix these things when they arise.

For instance, in this issue, the Semigroups package methods for GreensXClassOfElement were being beaten by those in the library, because those in the library had the additional filter IsFinite, making them higher ranked. In GAP's previous (buggy) behaviour, the lower-ranked Semigroups methods were applied first.

My belief is that there will be other places where this causes problems in the Semigroups package, so we should be on the lookout for GAP library methods (or methods in other packages) being applied to semigroups-related things when we think the Semigroups package methods should apply instead. The fixes will require rank adjustments, or adjustments to the actual filters.

[wilfwilson]

Unfortunately @james-d-mitchell this situation is messier than I had hoped. In my PR #533 I stopped the specific thing above from being a problem. But it's not enough in general.

My 'fix' was to add RankFilter(IsFinite) to the ranks of the Semigroups package methods. So, when the Semigroups package is loaded, the value of RankFilter(IsFinite) is calculated, and added to the rank of the method. When Semigroups is loaded early in a GAP session, the rank of IsFinite is some small single digit number, say 6. For all time, therefore, this method has rank 6 higher than its filter suggests. Often this is enough to beat the library method, including above.

The problem is that, if enough packages are loaded and implications added, RankFilter(IsFinite) can be much much larger (I've seen it at three digits), and the GAP library methods win again.

The nice solution to this is to use {} -> RankFilter(IsFinite) as the rank adjustment to the method; this way, every time method ordering is recalculated, the actual current version of RankFilter(IsFinite) is used, rather than the original rank of IsFinite when Semigroups was loaded. The problem with this is that this feature is not present in GAP's stable-4.10 or stable-4.9 branches, so we can't use it yet.

Alternatively, we add some huge constants, like SUM_FLAGS or something, to our methods if we are sure that no other packages will legitimately want to install methods to beat Semigroups. This brings the problem of making sure that the various Semigroups package methods for (say) GreensLClassOfElement are still in their correct relative order (i.e. acting, non-acting, etc).

Or we could add methods whose filters match the GAP methods' filters, and which do what we want. (Our methods would beat GAP thanks to being loaded later; they would always have equal rank). But such code duplication seems silly.

[james-d-mitchell]

Resolved in v3.0.20.