LOOPS breaks FR

[nagygp]

Hi! I want to present an issue, my explanation and my suggested solution. I may be wrong at many places, so I apologize in advance for my mistakes. :-)

Issue:

Loading LOOPS before FR breaks the command FullSCGroup, provided the assertion level is at least 2.
Notice that seemingly at GAP tests, the assertion level is set to 2.

The correct behaviour without loading LOOPS:

gap> LoadPackage("fr",false);
true
gap> SetAssertionLevel(2);
gap> TraceMethods( \in, EpimorphismPermGroup );
gap> g:=FullSCGroup(Group((1,2,3)),1);
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  EpimorphismPermGroup: (FR) for a f.g. FR group and a level at /home/gap/inst/gap-master/pkg/fr-2.4.5/gap/group.gi:1435
#I  in: for a permutation, and a permutation group at /home/gap/inst/gap-master/lib/grpperm.gi:633
#I  in: default method, checking for <g> being among the generators at /home/gap/inst/gap-master/lib/grp.gi:4558
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
FullSCGroup([ 1 .. 3 ], Group( [ (1,2,3) ] ), 1)

The wrong behaviour with loading LOOPS:

gap> LoadPackage("loops",false);
     ______________________________________________________
       LOOPS: Computing with quasigroups and loops in GAP  
                         version 3.4.0                     
       Gabor P. Nagy             &      Petr Vojtechovsky  
       nagyg@math.u-szeged.hu           petr@math.du.edu   
     ------------------------------------------------------
                homepage: www.math.du.edu/loops            
     ______________________________________________________

true
gap> LoadPackage("fr",false);
#I  method installed for IsNormalOp matches more than one declaration
#I  method installed for NormalClosure matches more than one declaration
true
gap> SetAssertionLevel(2);
gap> TraceMethods( \in, EpimorphismPermGroup );
gap> g:=FullSCGroup(Group((1,2,3)),1);
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  EpimorphismPermGroup: (FR) for a f.g. FR group and a level at /home/gap/inst/gap-master/pkg/fr-2.4.5/gap/group.gi:1435
#I  in: for a permutation, and a permutation group at /home/gap/inst/gap-master/lib/grpperm.gi:633
#I  in: (FR) for an FR element and an FR semigroup at /home/gap/inst/gap-master/pkg/fr-2.4.5/gap/group.gi:946
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  EpimorphismPermGroup: (FR) for a f.g. FR group and a level at /home/gap/inst/gap-master/pkg/fr-2.4.5/gap/group.gi:1435
#I  in: for a permutation, and a permutation group at /home/gap/inst/gap-master/lib/grpperm.gi:633
#I  in: (FR) for an FR element and an FR semigroup at /home/gap/inst/gap-master/pkg/fr-2.4.5/gap/group.gi:946
Error, Record Element: '<rec>.pi' must have an assigned value in
  if not x ^ G!.FRData.pi in Image( G!.FRData.pi ) then
    return false;
elif ForAny( G!.FRData.sphere, function ( s )
          return x in s;
      end ) then
    return true;
fi; at /home/gap/inst/gap-master/pkg/fr-2.4.5/gap/group.gi:166 called from 
SEARCH@FR.IN( g, G ) at /home/gap/inst/gap-master/pkg/fr-2.4.5/gap/group.gi:959 called from
x in H at /home/gap/inst/gap-master/lib/ghom.gi:309 called from
func( elm ) at /home/gap/inst/gap-master/lib/coll.gi:1530 called from
ForAll( imgs, function ( x )
      return x in H;
  end ) at /home/gap/inst/gap-master/lib/ghom.gi:309 called from
GroupGeneralMappingByImagesNC( q, g, List( GeneratorsOfGroup( g ), function ( w )
        return ActivityPerm( w, n );
    end ), GeneratorsOfGroup( g ) ) at /home/gap/inst/gap-master/pkg/fr-2.4.5/gap/group.gi:1441 called from
...  at *stdin*:5
you can 'return;' after assigning a value
brk> 

Explanation:

• \in is based on EpimorphismPermGroup in a rather complicated way.
• EpimorphismPermGroup calls GroupGeneralMappingByImagesNC.
• Despite its name, at assertion level >=2, GroupGeneralMappingByImagesNC checks if the generators are in respective the groups.
• This causes new \in method calls.
• With no LOOPS loaded, at this point \in uses the "default method" for groups by checking if elm is in the list of generators.
• With LOOPS loaded, at this point \in calls the "(FR) for an FR element and an FR semigroup" method which calls EpimorphismPermGroup again and chaos breaks out.

Proposed solution:

Add a "default \in method" for FR element and an FR semigroup with high priority.
As in the group case (see $GAPROOT/lib/grp.gi:4434), this simply checks if elm is among the generators; if not, then TryNextMethod().
In this way, the tests for FR pass with no errors.
The solution is not "ad hoc", since the problem is caused by GroupGeneralMappingByImagesNC, where only generators are being checked.

gap> LoadPackage("loops",false);
     ______________________________________________________
       LOOPS: Computing with quasigroups and loops in GAP  
                         version 3.4.0                     
       Gabor P. Nagy             &      Petr Vojtechovsky  
       nagyg@math.u-szeged.hu           petr@math.du.edu   
     ------------------------------------------------------
                homepage: www.math.du.edu/loops            
     ______________________________________________________

true
gap> LoadPackage("fr",false);
#I  method installed for IsNormalOp matches more than one declaration
#I  method installed for NormalClosure matches more than one declaration
true
gap> InstallMethod(\in,
>         "(FR) default method, checking for <g> being among the generators",
>          ReturnTrue,
>         [IsFRElement, IsFRSemigroup], 1000,
>   function ( g, G )
>     if   g = One(G)
>       or (IsFinite(GeneratorsOfGroup(G)) and g in GeneratorsOfGroup(G))
>     then return true;
>     else TryNextMethod(); fi;
> end );
gap> SetAssertionLevel(2);
gap> TraceMethods( \in, EpimorphismPermGroup );
gap> g:=FullSCGroup(Group((1,2,3)),1);
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
#I  EpimorphismPermGroup: (FR) for a f.g. FR group and a level at /home/gap/inst/gap-master/pkg/fr-2.4.5/gap/group.gi:1435
#I  in: for a permutation, and a permutation group at /home/gap/inst/gap-master/lib/grpperm.gi:633
#I  in: (FR) default method, checking for <g> being among the generators at *stdin*:3
#I  in: for an object, and a small list at /home/gap/inst/gap-master/lib/list.gi:234
FullSCGroup([ 1 .. 3 ], Group( [ (1,2,3) ] ), 1)

[fingolfin]

@laurentbartholdi are you aware of this report?

Anywhere, I believe this is an instance of this deeper problem in GAP: gap-system/gap#2513. In particular, note that the problem depends on the order in which the packages are loaded. If I load fr before loops, the issue goes away. It also goes away with the changes in PR gap-system/gap#2773 which will be in GAP 4.11 (but not in GAP 4.10)

In the meantime, the workaround suggested by @nagygp should do it, although of course one may argue that it's a bit unfair that FR has to make changes to accommodate a longstanding "bug" (misfeature? design problem? ...) in GAP. But GAP 4.10 has already been tagged, and the changes in the mentioned PR are rather big, so we don't want to rush them into GAP 4.10 now. But GAP 4.11 is at least 6 months away, so having a pragmatic solution now (which could be removed once GAP 4.11 is out) would be better.

Note that we could add such a high-ranked \in method to GAP, too, but then it'd have to be for a more general set of input filters, and it would risk creating more regressions (e.g. if such an \in method gets applied to objects for which testing equality is expensive, it might cause other code that somehow works right now to misbehave). So it's also not a change I'd want to cram into GAP 4.10 right now, so it's mostly off the table.

Some more options:

• fudge the rank modifiers of the "offending' InstallMethod calls some more to paper over the issue for now
• adjust the .tst file in question by inserting a SetAssertionLevel(0) (or 1) call into it.

Long-term, GAP could also not switch the assertion level in START_TEST (or at least only set it to 1); see gap-system/gap#527 ; and of course one may wonder if the specific assertion in GroupGeneralMappingByImagesNC should be there, resp. whether it should perhaps be set for a level other than 2 (see also issue gap-system/gap#564)

[laurentbartholdi]

Sure, I'll add it.

[laurentbartholdi]

I just put the method in the new head. If everything works fine, I'll release a new version.

[fingolfin]

@laurentbartholdi Thank you very much!

@nagygp @alex-konovalov can you confirm that Laurent's change resolves the issue?

[olexandr-konovalov]

@laurentbartholdi @nagygp @fingolfin I've checked that I can reproduce the problem with the latest FR release, and that with the fresh clone of the FR repository everything works as below:

gap> LoadPackage("loops",false);
     ______________________________________________________
       LOOPS: Computing with quasigroups and loops in GAP  
                         version 3.4.0                     
       Gabor P. Nagy             &      Petr Vojtechovsky  
       nagyg@math.u-szeged.hu           petr@math.du.edu   
     ------------------------------------------------------
                homepage: www.math.du.edu/loops            
     ______________________________________________________

true
gap> LoadPackage("fr",false);
#I  method installed for IsNormalOp matches more than one declaration
#I  method installed for NormalClosure matches more than one declaration
true
gap> TraceMethods( \in, EpimorphismPermGroup );
gap> SetAssertionLevel(2);
gap> g:=FullSCGroup(Group((1,2,3)),1);
#I  in: for an object, and a small list at /Users/alexk/gap-4.10.0/lib/list.gi:234
#I  in: for an object, and a small list at /Users/alexk/gap-4.10.0/lib/list.gi:234
#I  in: for an object, and a small list at /Users/alexk/gap-4.10.0/lib/list.gi:234
#I  in: for an object, and a small list at /Users/alexk/gap-4.10.0/lib/list.gi:234
#I  EpimorphismPermGroup: (FR) for a f.g. FR group and a level at /Users/alexk/Library/Preferences/GAP/pkg/fr/gap/group.gi:1435
#I  in: for a permutation, and a permutation group at /Users/alexk/gap-4.10.0/lib/grpperm.gi:633
#I  in: (FR) default method, checking for <g> being among the generators at /Users/alexk/Library/Preferences/GAP/pkg/fr/read.g:33
#I  in: for an object, and a small list at /Users/alexk/gap-4.10.0/lib/list.gi:234
FullSCGroup([ 1 .. 3 ], Group( [ (1,2,3) ] ), 1)
gap> 

So @laurentbartholdi please make a release indeed!

[laurentbartholdi]

Done, fr is 2.4.6 now.

[olexandr-konovalov]

Thanks - testing now:

* FR - new version 2.4.6 discovered!!!
  ============================================
  Getting new archives from 
  https://github.com/gap-packages/fr/releases/download/v2.4.6/fr-2.4.6
[ ".tar.gz" ]
  unpacking fr-2.4.6.tar.gz
  Validation of the info file successful!
  Package FR 2.4.6 from 03/11/2018 has dependencies:
  * NeededOtherPackages [ [ "FGA", ">=1.1" ], [ "IO", ">=4.0" ], 
  [ "Polycyclic", ">=2.2" ], [ "GAPDoc", ">=1.0" ] ]
  * GAP >=4.8
  * SuggestedOtherPackages [ [ "GBNP", ">=0.9" ], [ "NQ", ">=2.4" ], 
  [ "LPRES", ">=0.1" ] ]
  finding text files  . . .

=====================text files==========================
fr-2.4.6/CHANGES
fr-2.4.6/COPYING
fr-2.4.6/init.g
fr-2.4.6/makedoc.g
fr-2.4.6/PackageInfo.g
fr-2.4.6/read.g
fr-2.4.6/README
fr-2.4.6/TODO
fr-2.4.6/doc/chap0.html
fr-2.4.6/doc/chap0.txt
fr-2.4.6/doc/chap1.html
fr-2.4.6/doc/chap1.txt
fr-2.4.6/doc/chap10.html
fr-2.4.6/doc/chap10.txt
fr-2.4.6/doc/chap11.html
fr-2.4.6/doc/chap11.txt
fr-2.4.6/doc/chap2.html
fr-2.4.6/doc/chap2.txt
fr-2.4.6/doc/chap3.html
fr-2.4.6/doc/chap3.txt
fr-2.4.6/doc/chap4.html
fr-2.4.6/doc/chap4.txt
fr-2.4.6/doc/chap5.html
fr-2.4.6/doc/chap5.txt
fr-2.4.6/doc/chap6.html
fr-2.4.6/doc/chap6.txt
fr-2.4.6/doc/chap7.html
fr-2.4.6/doc/chap7.txt
fr-2.4.6/doc/chap8.html
fr-2.4.6/doc/chap8.txt
fr-2.4.6/doc/chap9.html
fr-2.4.6/doc/chap9.txt
fr-2.4.6/doc/chapBib.html
fr-2.4.6/doc/chapBib.txt
fr-2.4.6/doc/chapInd.html
fr-2.4.6/doc/chapInd.txt
fr-2.4.6/doc/chooser.html
fr-2.4.6/doc/fr.xml
fr-2.4.6/doc/frbib.xml
fr-2.4.6/doc/frbib.xml.bib
fr-2.4.6/doc/index.html
fr-2.4.6/doc/lefttoc.css
fr-2.4.6/doc/manual.css
fr-2.4.6/doc/nocolorprompt.css
fr-2.4.6/doc/ragged.css
fr-2.4.6/doc/times.css
fr-2.4.6/doc/toggless.css
fr-2.4.6/gap/algebra.gd
fr-2.4.6/gap/algebra.gi
fr-2.4.6/gap/bisets.gd
fr-2.4.6/gap/bisets.gi
fr-2.4.6/gap/cp.gd
fr-2.4.6/gap/cp.gi
fr-2.4.6/gap/examples.gd
fr-2.4.6/gap/examples.gi
fr-2.4.6/gap/frelement.gd
fr-2.4.6/gap/frelement.gi
fr-2.4.6/gap/frmachine.gd
fr-2.4.6/gap/frmachine.gi
fr-2.4.6/gap/group.gd
fr-2.4.6/gap/group.gi
fr-2.4.6/gap/helpers.gd
fr-2.4.6/gap/helpers.gi
fr-2.4.6/gap/linear-gbnp.gi
fr-2.4.6/gap/linear.gi
fr-2.4.6/gap/mealy.gd
fr-2.4.6/gap/mealy.gi
fr-2.4.6/gap/perlist.gd
fr-2.4.6/gap/perlist.gi
fr-2.4.6/gap/pickle.g
fr-2.4.6/gap/vector.gd
fr-2.4.6/gap/vector.gi
fr-2.4.6/gap/vhgroup.gi
fr-2.4.6/guest/Brieussels_algorithm.g
fr-2.4.6/tst/chapter-12.tst
fr-2.4.6/tst/chapter-3.tst
fr-2.4.6/tst/chapter-4.tst
fr-2.4.6/tst/chapter-5-a.tst
fr-2.4.6/tst/chapter-5-b.tst
fr-2.4.6/tst/cp.tst
fr-2.4.6/tst/frelements.g
fr-2.4.6/tst/frmachines.g
fr-2.4.6/tst/kneading.g
fr-2.4.6/tst/mealyelements.g
fr-2.4.6/tst/mealymachines.g
fr-2.4.6/tst/testall.g

=====================end of the list of text files=======
=====================binary files========================
fr-2.4.6/BUGS
fr-2.4.6/doc/basilica-ball.jpg
fr-2.4.6/doc/basilica-nucleus.jpg
fr-2.4.6/doc/fornaess-sibony.jpg
fr-2.4.6/doc/hasse.jpg
fr-2.4.6/doc/manual.js
fr-2.4.6/doc/manual.pdf
fr-2.4.6/doc/manual.six
fr-2.4.6/doc/rainbow.js
fr-2.4.6/doc/toggless.js
fr-2.4.6/scripts/build_gap.sh
fr-2.4.6/scripts/build_pkg.sh
fr-2.4.6/scripts/gather-coverage.sh
fr-2.4.6/scripts/run_tests.sh

=====================end of the list of binary files=====

[nagygp]

If I understand correctly, this issue is solved. I close it.