NC versions of PreImages, PreImagesSet, PreImagesElm and PreImagesRepresentative

[cdwensley]

This aims to start work on the process outlined in issue #4809. The operation PreImagesRepresentative has been renamed PreImagesRepresentativeNC throughout the library, many doc files, and some tests. A new PreImagesRepresentative has been introduced which just, for now, calls PreImagesRepresentativeNC. If this change is included in 4.12.1 then package authors can be given the option of converting their calls of this operation. After that a test can be introduced to check that the element is in the range of the map. Further changes may be recommended, e.g. a new PreImageElmNC.

Text for release notes

Too early to write this down.

[fingolfin]

Thanks for working on this!

So the new PreImagesRepresentative method is in lib/mapping.gi.

Once major concern I have is how we plan to transition packages which install methods for PreImagesRepresentative. Those will be broken if we start calling PreImagesRepresentativeNC everywhere now without giving them a chance to provide such methods themselves!

So I think we need to go the other way around: we first must work with package authors to give them the chance to adapt and release their packages, then we can move forward. Here is one way this could be done:

• perform the renaming here, but for now leave PreImagesRepresentative as a synonym for PreImagesRepresentativeNC (so that methods installed for the one are also installed for the other)
• identify all packages which install methods for PreImagesRepresentative; on a quick scan these seem to be
  • [ ] cryst
  • [ ] fga
  • [ ] fr
  • [ ] orb
  • [ ] polycyclic
  • [ ] qpa
  • [ ] rcwa
  • [ ] semigroups
  • [ ] utils
  • [ ] wedderga
• either tell the author which changes to make, or directly submit a PR with the required changes
  • I suggest the following: they should install their methods for PreImagesRepresentativeNC instead of PreImagesRepresentative; but to stay compatible with prior GAP versions, they can add code to their init.g of the kind if not IsBound(PreImagesRepresentativeNC) then BindGlobal("PreImagesRepresentativeNC", PreImagesRepresentative); fi;
  • wait until they all made releases

That's how I've done similar migrations in the past. It's a slow and tiresome process, Ia m afraid... Here is a pull request from 2019 by me for FGA which still has not been merged, much less released: https://github.com/chsievers/fga/pull/7. On the upside, all the other packages have a fairly good track record for releases (well perhaps except for polycyclic, of which I am maintainer; there the background is that we have a major bug that must be fixed and I can't seem to get around to it... ARGH).

Anyway: because this is so tedious, it's best to not do this too often. So here one may wonder if there aren't other methods that need similar treatment and that should be dealt with in one go. E.g. I wonder whether we also need ImagesRepresentativeNC for similar reasons?

[cdwensley]

There were 3 files where it appeared that after a call to PreImagesRepresentativeNC a test for the return of fail followed immediately: alghom.gi, ghomperm.gi, mapphomo.gi.

[cdwensley]

I am very perplexed by some methods in mapprep.gi which are full of tests for "im = fail". Should these be methods for the non-NC PreImagesRepresentative?

[cdwensley]

@fingolfin Sorry if I'm slow on the uptake, but I do not understand what will be broken. As it stands at present PreImagesRepresentative just calls PreImagesRepresentativeNC (without any test). So, it seems to me, everything should work as before, and changes to packages can come later. The Utils package installs a method for PreImagesRepresentative and tests this, and the test works fine in my preimrep branch.

[cdwensley]

PreImages produces the same error as PreImagesRepresentative, so the same procedure applies.

[cdwensley]

Further details of the use by packages of one or more of PreImages, PreImagesElm, PreImagesSet and PreImagesRepresentative. In the following list 'I' indicates that an InstallMethod for one of these functions has been declared; while 'L', 'T' and 'M' indicate an occurrence in the library; tests or examples, and the manual. ace T alnuth T M atlasrep L automgrp L T M autpgrp L congruence L crisp L T cryst I L ctbllib T M cubefree L difsets L fga I T M fining I L fr I L T M grpconst L guarana L T hap L M irredsol L
JupyterKernel L kan L laguna L liealgdb L liering L T M matgrp I L modison L orb I permut L polenta M polycyclic I L T M qpa I L T M radiroot L T M rcwa I L T M recog L repsn L rewriting L semigroups I L T M smallsemi L sonata L sophus L transgrp L utils I L T M walrus I L T M xmod L xmodalg L YangBaxter L

[cdwensley]

When nothing happens for weeks one can forget exactly what has been done. But who would want the hassle of reviewing a PR with 77 files changed?

[ChrisJefferson]

I started writing this in a comment, but it got too long, so I'll pop it here.

We could consider adding something like: InstallMethods([PreImagesRepresentativeNC, PreImagesRepresentative], ..., which is like InstallMethod but lets you install methods for multiple things at once -- except InstallMethods could only install once when the objects are identical. This would give a compact way of handling the case of having one method for both PreImagesRepresentativeNC and PreImagesRepresentative.

This could, in principle, then be used in other places, for just having a quick search for NC I notice in ctbl.gi:3345, we install the same method for Index, IndexOp and IndexNC.

[cdwensley]

@fingolfin Sorry to be bothering you again. With my system more or less back to where it was, I would like to restart work on this PR. However, the branch of gapdev I was using has been lost. I have used "git fetch upstream refs/pull/5073/head:preimrep" to restore it; rebased on yesterday's master; and dealt with all the resulting diffs. How to push this to 5073? If I "git push origin preimrep" I am asked to create a new PR. If I "git push upstream preimrep" the request is rejected (probably not a fast-forward). Is there a simple solution, or is a new PR a good idea, with a comment here that the PR has been updated? There are a large number of suggestions here that should not be lost. And while I'm asking: it's reasonable to extend from PreImagesRepresentative to PreImages, PreimagesElm and PreImagesSet, but is adding Images, etc. really a good idea?

[cdwensley]

No progress on this since last February. Restarting activity today with PR#98 for Wedderga.

[cdwensley]

Progress report: (25/10/23) RCWA: agreed to leave files unchanged as any tests would not be costly. (15/11/23) SEMIGROUPS: PR#965 merged.

[cdwensley]

In order to fix conflicts in 22 lib/.gi and lib/grpnice.gd I have made copies from master; changed all the PreImages to nPreImages*.NC; and then committed these edited copies. The result is that that checks fail because of changes in some of the corresponding lib/*.gd files. These can be fixed in the same way by making copies from master and, so far, grplatt.gd and gpr.gd have been processed in this way.

[cdwensley]

And now fitfreee.gd. It's a pity tests fail after finding the first undefined variable, rather than looking for more.

[cdwensley]

I'm thinking that it might be best to close this PR and start again with a branch of the current gapdev?

[cdwensley]

There were so many conflicts between files edited in this PR and changes made in master that it seemed sensible to rebase the PR on the current master and make sure all the previous changes to ...NC were made. This has now been done, which will hopefully allow most of the checks to pass.

[cdwensley]

PR #58 for FR merged 11/01/2024and included in release 2.4.13.

[fingolfin]

@cdwensley there was a merge conflict which I took the liberty of resolving. It would be great to get this finally done. Thank you for not dropping the torch on this!

[fingolfin]

Perhaps to keep track of progress, we could take the list from https://github.com/gap-system/gap/pull/5073/#issuecomment-1271306150 and copy it in slightly edited form to the issue description; I would turn it into a task list, i.e.

- [ ] task 1
- [x] task 2
- [ ] task 3

which renders as

• [ ] task 1
• [x] task 2
• [ ] task 3

and one can "tick the boxes". Then for each package, if there is a relevant issue or PR, I'd add a link to that.

This way one can quickly see what's done already, what is in progress, and what is incomplete.

[cdwensley]

The plan was to get those packages with methods installed for one of PreImages, PreImagesElm, PreImagesSet and PreImagesRepresentative to prepare for this merge. Here is my list of such packages:

• [x] cryst merged gap-packages/cryst#31 13/2/23 in release 4.1.25
• [ ] fga gap-packages/fga#10 not yet merged (reminder for @fingolfin)
• [x] fining merged gap-packages/fining#28 26/7/23
• [x] fr merged gap-packages/fr#58 11/1/24 in release 2.4.13
• [ ] matgrp not on GitHub, small package, just one method for PreImagesRepresentative
• [x] orb merged gap-packages/orb#67 16/1/24
• [ ] polycyclic recently created gap-packages/polycyclic#84
• [x] qpa nothing to do
• [ ] rcwa issue gap-packages/rcwa#26 - agreed to make no changes
• [x] semigroups merged semigroups/semigroups#965 14/11/23 in release 5.3.3
• [x] utils merged gap-packages/utils#52 4/10/22 in release 0.81
• [x] walrus nothing to do
• [ ] wedderga gap-packages/wedderga#98 opened 12/9/23 but no response

A number of the other distributed packages call one of more of these functions a handful of times in their library, but it seems unnecessary for them to make any adjustments at this stage. The exception is HAP, which has 157 calls, and has recently defined the four NC versions in its init.g in PR#121 17/1/24. Package sonata has 17 calls - there's nothing in between.

If @fingolfin is able to turn this into a task list, that can only be helpful.

[fingolfin]

@cdwensley turned it into a list, and the PR refs into links... please verify I set the checkboxes right (and otherwise just adjust them). Some additional remarks:

• matgrp is on GitHub, just not in the gap-packages org: https://github.com/hulpke/matgrp
• I'll try to look into the FGA and polycyclic PRs during or before GAP Days
• I don't understand the "conclusion" for rcwa: wouldn't new code that uses, say, PreImagesNC on a group homomorphism potentially run into an error when used with an RCWA homomorphism due there not being a PreImagesNC method, just one for PreImages? I think we'll have PreImages delegate to PreImagesNC but we can't also delegate in the other direction otherwise there'll be infinite recursion?

[cdwensley]

@fingolfin: how you changed the PR references in the list above into links I cannot imagine, but they all appear to be correct. matgrp: there is now PR#17. rcwa: do not understand your comment, but have created a new PR #28 which just defines the 4 PreImages...NC in init.g. delegation: How does "I think we'll have PreImages delegate to PreImagesNC" not conflict with all the "if not IsBound( PreImagesNC ) then BindGlobal( "PreImagesNC", PreImages );" added to numerous init.g's?