Plan: get rid of hidden implications

[fingolfin]

Short summary

I would like to get rid of hidden implications in GAP completely. They can lead to counterintuitive problems, like the order in which packages were loaded can affect ranking; and other problems, see e.g. issue #1649 (and esp. this comment by @frankluebeck which already sketches the plan here, and gives additional useful information)

• [x] adding a way to turn off hidden implications temporarily, for testing: see PR #2246
• [x] turning hidden implications in the GAP library into actual implications where possible: see PRs #2222 and #2247
• [ ] turning hidden implications in GAP packages into actual implications where possible
• [ ] identifying the effect of the remaining hidden implications, and trying to get minimize or eliminate it (i.e.: identify changes in method ordering; determine if they matter; adjust method ranking if needed; etc.)
• [ ] finally, eliminate the remaining hidden implications and the mechanism powering them.

Background: What are hidden implications?

Currently, GAP's method ranking relies on both implications, and so-called "hidden implications". An implication is when a filter IsFOO implies another filter IsBAR (e.g. via InstallTrueMethod). In that case, the rank of IsFOO should be larger than that of IsBAR, reflecting the idea that the more "properties" (used in a non-technical sense here) a filter implies, the higher it should be ranked.

This is all good and fine, but apparently was/is not quite good enough to get a good ranking system (?). Thus GAP also uses so-called "hidden" implications: A "hidden" implication from a filter IsFOO to a filter IsBAR has the same effect on the relative ranking of the two filters, but without a mathematical implication between the two.

These typical are created indirectly when you declare a property or attribute. Example:

DeclareProperty( "IsNilpotentGroup", IsGroup );

This creates a hidden implication from IsNilpotentGroup to IsGroup, but not a mathematical one. Meaning that the rank of IsNilpotentGroup is larger than that of IsGroup; but in principle at least, something could be in the filter IsNilpotentGroup without being also in the filter IsGroup. Now, in this particular case, one "obviously" also intended an actual proper implication -- but none exists! One has to manually establish it, e.g. via this:

InstallTrueMethod( IsGroup, IsNilpotentGroup )

The reason for this is clearer if you consider this example: in polycyclic, we have this:

DeclareProperty( "IsTorsionFree", IsGroup );

Now, this installs a hidden implication IsTorsionFree to IsGroup. But now perhaps you are writing a package in which you deal with torsion free monoids. So you add this:

DeclareProperty( "IsTorsionFree", IsMonoid );

Both can happily coexist, but now we are glad that GAP did not erroneously install an actual implication from IsTorsionFree to IsGroup, as our most beloved torsion free monoid, the set N of natural numbers, isn't a group.

But GAP only installs a hidden implication the first time a property is declared... Thus now the ranking of the filter IsTorsionFree depends on the order in which packages are loaded: if the polycyclic package is loaded first, then the rank will be higher than as if your new package is loaded, as IsGroup has a higher rank than IsMonoid.

This kind of example is not made up, it occurs in practice that people want to define properties for different kind of objects.

Proposed solution

Get rid of hidden implications, gradually, as sketched above.

TODO: add more details later on?

[fingolfin]

One suggestion by @ThomasBreuer was that there could be an optional argument to DeclareProperty to indicate that a true reverse implications is intended; my variation of that would be to have a separately named declare function, such as DeclarePropertyWithReverseImplication or DeclareExclusiveProperty, as that stands out more and is easy to grep for

In either case, we could then keep track of this explicitly, and issue a warning or even error if a property of this kind gets redefined.

Also, one may consider a similar for the tester of an attribute: e.g. HasDerivedSubgroup and HasDerivedSeriesOfGroup both likely should imply IsGroup, so it would make sense to have such "automatic" reverse implications for attributes, too.

[ThomasBreuer]

It is fine to have two functions for the two purposes of property declarations. The main point is that GAP can detect (on startup or when a package gets loaded) where an existing property shall be redeclared with another intended behavior concerning implications, and can signal a warning or an error. I would not use the term reverse implication, DeclarePropertyWithImplication would fit.

[fingolfin]

Sadly things got worse since I last touched this, as lots packages added new code relying (accidentally) on hidden implications. At the same time, we keep encountering problems caused by hidden implications (see e.g. https://github.com/gap-system/gap/pull/4935/files#r940054140).

Ideally we'd come up with a plan to migrate incrementally to a world without hidden implications.... Perhaps we could add an optional argument for DeclareAttribute etc. which turns off (or on!) hidden implications for just that one call. Then the -N option would basically decide what the default for that option is. This would allow us to already avoid hidden implications in some places now, before the full switch.

Or perhaps we just need to make the switch, hard:

1. Switch PackageDistribution to use -N by default (possibly on a branch) to find any offending packages (to have that work, patch GAP to error instead of warn when there is a problem; perhaps we could have variants of -N like --hidden-implications=[on|warn|off] with warn corresponding to what giving -N does right now)
2. get as many (all?) packages to accept patches to fix any warnings they show when loaded with -N active
3. Also do the same to fix their test suites
4. Switch package CI job to (also? only) test with the --hidden-implications=off option to ensure they stay fixed
5. finally turn it off in GAP for good