Merging #2640 broke Semigroups

[markuspf]

Merging of #2640 broke Semigroups

gap> LoadPackage("semigroups");;
gap> Monoid(Matrix(GF(4), [[Z(4)]]));
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 2nd choice method found for `OneMutable' on 1 arguments at /home/makx/git/gap/master/lib/methsel2.g:250 called from
OneOp( elm ) at /home/makx/git/gap/master/lib/arith.gi:267 called from
One( gens ) at /home/makx/git/gap/master/pkg/semigroups/gap/semigroups/semigrp.gi:165 called from
<compiled statement>  called from
<compiled statement>  called from
SetGeneratorsOfMagmaWithOne( M, gens ); at /home/makx/git/gap/master/lib/monoid.gi:99 called from
...  at *stdin*:2
type 'quit;' to quit to outer loop
brk> 

(Semigroups has its own implementation of matrices, and now the Matrix methods from the GAP library take precedence over the semigroups ones, reworking semigroups is a bit of an undertaking).

[olexandr-konovalov]

That's unfortunate. The latest release of Semigroups did not compile with master branch since mid-June (see semigroups/Semigroups#497) and while testing this PR there was no way to spot this. The fix for the compilation problem was merged in Semigroups repository on June 18th (semigroups/Semigroups#499) but no release followed, so who knew?

First, I am now setting up another Travis test which will use nightly build Docker container for master branch with packages-master.tar.gz archive to test development versions of packages. This will be limited to packages from gap-packages organisation as an additional benefit of hosting a package repository there.

Second, dependently on how complicated reworking the Semigroups is as @james-d-mitchell thinks, we can:

• revert Merge some MatrixObj work into master #2640, branch off stable-4.10, and then merge Merge some MatrixObj work into master #2640 into master again to appear in GAP 4.11, assuming that Semigroups will become compatible with it by GAP 4.11 (in ~6 month?), or
• continue as it is, assuming that Semigroups will be fixed in September. @james-d-mitchell what do you think?

[olexandr-konovalov]

Side remark: I have a version which gets a Docker container gapsystem/gap-docker-master, clones package repository, builds it (that part relies on standardised build setup), and then calls TestPackage with GAP (in a setting when GAP started with default set of packages). Playing with it now in https://travis-ci.org/gap-packages/gap-docker-pkg-tests-master-devel/.

[james-d-mitchell]

That's unfortunate. The latest release of Semigroups did not compile with master branch since mid-June (see semigroups/Semigroups#497) and while testing this PR there was no way to spot this. The fix for the compilation problem was merged in Semigroups repository on June 18th (semigroups/Semigroups#499) but no release followed, so who knew?

Just for the record, the reason that Semigroups didn't compile against GAP master was because of another (not related to MatrixObj) breaking change introduced in GAP master earlier (related, I think, to the signature of GVarFilt). Yes, the fix for this earlier issue was easy and was merged in mid-June, and then I was busy doing other things, and didn't find the time to make a release.

The matrix code in Semigroups has been there since June 2017, it is likely to be complicated to resolve this, and it is unlikely that I can resolve the issues before September.

[james-d-mitchell]

Maybe I should also add that I'm in favour of the MatrixObj stuff and that the matrix stuff in Semigroups was only ever meant to be a temporary solution.

[olexandr-konovalov]

@james-d-mitchell so I think we will have to revert #2640 for GAP 4.10. Maybe even not being too fast in merging it back into master and breaking Semigroups, but wait till you will hopefully be ready to start to update Semigroups?

[fingolfin]

I would strongly prefer not to revert #2640. This has been cooking for far too long, without progress, and we need it exposed to catch conflicts like this.

What exactly are the conflicts? I don't have time to test right now, but from the issue description, it sounded as if "only" the Matrix operation is clashing, right?

If so, we could temporarily disable/rename the new Matrix in GAP, until semigroups is adjusted to cooperate with it. (Or perhaps not just temporarily, but permanently -- I did not have a chance to see what either does in GAP and/or semigroups right now.)

Yet another alternative: perhaps I or somebody else can make a "fix" for semigroups that @james-d-mitchell then only has to merge. But that only helps if James has time to cut a release of semigroups; but it didn't quite sound like that?

[markuspf]

As far as I can see right now there are two problems:

• both Semigroups and the matobj code install methods for Matrix with first argument a field, and second argument a list, that conflict (there even is a warning baout this at package load time, its just very lost in all the banners being printed),
  The library methods rank higher than the semigroups ones, and this leads to all code in Semigroups that deals with matrices to fall over.

  Fixing this properly is not entirely trivial: We introduced "proper" matrix objects to get around certain limitations with list typing in GAP, so the "backwards compatible" matrices that come out of GAP's Matrix are not really good for Semigroups.
  Ranking Semigroups' Matrix method higher makes the corresponding tests pass; I think one could fix this by fixing enough of the surface code in semigroups (if semigroups wanted, as a temporary measure, retain its own matrix objects). I can look into that.

• Methods for BaseDomain for collections of (Semigroups-Package) matrices don't apply anymore leading to failures in verification code checking BaseDomain. For some reason GAP's "generic method for a row vector" is applicable before Semigroups' method for IsMatrixOverFiniteFieldCollection in this code:

gap> coll := [Matrix(GF(3), [[Z(3), Z(3), 0 * Z(3)],
>                            [Z(3), Z(3) ^ 0, Z(3)],
>                            [0 * Z(3), 0 * Z(3), Z(3)]]),
>             Matrix(GF(2 ^ 2), [[Z(2 ^ 2) ^ 2, Z(2 ^ 2) ^ 2, Z(2) ^ 0],
>                              [Z(2) ^ 0, 0 * Z(2), Z(2) ^ 0],
>                              [0 * Z(2), 0 * Z(2), Z(2 ^ 2) ^ 2]])];;
gap> BaseDomain(coll);

[ChrisJefferson]

One possible suggestion, rather than un-merge from master we could add a temporary constant boolean, set to false by default until after 4.10 is released, to enable/disable MatrixObj? (I haven't looked at the code carefully, so I don't know if that is a reasonable suggestion, sorry).

[olexandr-konovalov]

This is now a crucial issue to decide before branching off stable-4.10...

[markuspf]

@alex-konovalov @ChrisJefferson and @markuspf just discussed a way forward on this for 4.10; The suggestion is to introduce a command-line option (say --enable-matrixobj) to enable this code as an experimental feature, so we can branch & ship 4.10 and not ask @james-d-mitchell to rewrite or quick-fix semigroups (as that might cause subtle breakage).

I was looking into this but am now: I would probably disable the whole lot of methods installed for Matrix, Vector, ZeroMatrix, and IdentityMatrix that were added in #2640 in the default GAP session, giving @james-d-mitchell (and me) a way to quickly test things by giving the --enable-matrixobj commandline switch.

Do any other packages already rely on matrixobj?

[james-d-mitchell]

I can try renaming the operation Matrix in Semigroups to MatrixOverSemiring with the longer term aim of removing the matrix code from Semigroups completely. If this turns out to be too complicated, or other things don't work because of changes in GAP master, then I don't really have an opinion about what the best course of action would be.

[markuspf]

Just renaming Matrix will take care of one problem (the one with the Matrix clash), not the one with BaseDomain.

I have a fairly small pull request coming up of which I'd like to see the test outcomes. It fixes SemigroupsTestStandard() on my machine, but who knows what else it breaks.

[james-d-mitchell]

Thanks @markuspf, I'll be happy to make a release of Semigroups if we can make a suitable fix.

[fingolfin]

Just to mention: from my POV, if necessary it would also be a possibility to modify the ranks of the GAP Matrix and/or BaseDomain methods, or even temporarily disabling some of them in upcoming the stable-4.10 branch. Of course a "proper" fix is better, but if that's too much effort to get done quickly, we can start out with a hackish but working solution.

I hope I can free my brain to help deal with this issue sometime soon; in the meantime, thanks to all who are looking into it as well.

[james-d-mitchell]

Markus and I have discussing this, and it seems to us that there is no "proper" fix for this issue in the Semigroups package, but that change in GAP is required. One problem is the following:

gap> m := Matrix(GF(2), [[Z(2)]]);;
gap> IsMultiplicativeElement(m);
true
gap> IsMultiplicativeElementCollection([m]);
false

If I recall correctly, some time in the past we changed the filter for MonoidByGenerators from IsMultiplicativeElementWithOneCollection to IsCollection for precisely this reason, i.e. that collections of matrices over finite fields do not belong to IsMultiplicativeElementWithOneCollection, but it is still natural to want to create monoids out of them.

As far as I can see, to use MatrixObj, as it currently is, in Semigroups rather than the hack that is there just now, we would have to limit the permissible types of matrices to those belonging in a sensible category (such as IsMatrixOverSemiring in Semigroups). In particular, if you wanted to do:

gap> m := Matrix(IsMatrixOverSemiring, GF(2), [[Z(2)]]); # there's no such method installed at present
gap> Monoid(m);

this would work, but

gap> m := Matrix(GF(2), [[Z(2)]]);
gap> Monoid(m);

wouldn't work. This would break backwards compatibility for Semigroups, since the latter works with GAP 4.9, but not with the master branch, and it looks weird and artificial to not be able to create semigroups/monoids generated by matrices.

Would it possible to fix GAP so that:

gap> m := Matrix(GF(2), [[Z(2)]]);;
gap> IsMultiplicativeElement(m);
true
gap> IsMultiplicativeElementCollection([m]);
true

??

[james-d-mitchell]

BTW: the documentation of MatrixObj in matobj2.gd states:

The whole idea of this interface is that vectors and matrices must
be proper objects with a stored type (i.e. created by Objectify allowing
inheritance) to benefit from method selection. We therefore refer
to the new style vectors and matrices as vector objects and
matrix objects respectively.

which the return value of Matrix(GF(2), [[Z(2)]]) seems to violate.

[james-d-mitchell]

I can see there's a huge appetite to resolve this issue⸮ Another possibility would be to leave GAP broken in this regard (the status quo for many years), and for the Semigroups package to simply ignore the MatrixObjs stuff and do our own implementation (also the status quo).

[fingolfin]

I do think there is "appetite" to resolve this; but just like you, James, others are busy with other stuff / ill / on vacation etc, so it's unfortunately slow going; but I am confident we can and will resolve this (first with a workaround for 4.10; then properly later).

As it is, I am a bit confused: I thought PR #2754 was supposed to be the workaround. But it wasn't merged, so perhaps there is a problem with it? But I see no hint for that on that PR?!?

[markuspf]

I think the confusion stems from the fact that we're trying to decide which is the best option going forward, for 4.10 and beyond that and are looking for some input (which isn't forthcoming, maybe we have to ask more widely? @frankluebeck @ThomasBreuer @ssiccha might have opinions?)

#2754 fixes the Semigroups package (but might break GAP or packages with Semigroups loaded, we did not try this).

We identified the underlying cause for our issues to be that with the matrices returned by Matrix (the method from the GAP library), there is no way to make a IsMultiplicativeElementWithOneCollection, an issue that should be overcome by objects in IsMatrixObj actually being objects. This is not the case.

How will we address this issue? For a collection of matrices to be eligible to be generators of a semigroup (or monoid) they need an associative multication defined between them, such as n x n matrices over a fixed semiring (which are thus elements of the full matrix semiring over said semiring and should hence be in IsMultiplicativeElementWithOneCollection and ideally in an appropriate elements family);

We could write some "surface code" (for the lack of a better word) that a user can give even a list of lists of lists of semiring elements to and convert those to an appropriate (semigroups internal?) MatrixObj. This is what semigroups does right now, though arguably using the name Matrix wasn't a good choice.
So we could just rename these functions to SemigroupGeneratorMatrix (slightly exaggerating here) and keep all the custom code in semigroups around.
This might also not be a great user API for semigroups. Will "the user" expect that their semigroups don't actually have the matrices they gave to the constructor as elements? In particular, if "the user" wants to use semigroup matrices in computations in other packages, they'll have to convert them. This seems silly.

So for the purposes of semigroups, we need collections of MatrixObjs that form are IsMultiplicativeElementWithOneCollections and IsAssociativeElementCollections.

(Incidentally see also #2776)

[james-d-mitchell]

I agree with @markuspf, there are any number of hacks that can fix this issue temporarily, but I'd like to understand what a "proper" fix, might look like. In particular, if Semigroups is to use MatrixObjs, then Matrix from GAP (not Semigroups) will have to return a proper object (not a list of lists). If this isn't going to happen, then we will just not use MatrixObjs and find another way.

It is probably not a very important issue for GAP what happens in Semigroups, so if no decision or discussion about the future of MatrixObj is going to happen, then it would be useful to know this too.
What I'd like to avoid is no discussion or decision leading to us abandoning MatrixObj because of the incompatibility of the return value of the Matrix operation (probably by renaming Matrix to something else, and breaking backwards compatibility for Semigroups), only to have the MatrixObj stuff return proper objects at some later point.

[ThomasBreuer]

@markuspf
I do not see why the filter IsMultiplicativeElementWithOneCollection is relevant for an argument
of a method that creates a domain (in this case a semigroup).
As a rule of thumb, I would say that a filter like that (IsAssociativeElementCollection is another example which had occurred recently) is useful only in the context of implications between filters
but not in GAP's method selection.
Note that if such a filter is set for an object then it is set for all objects in its family.
For example, IsMultiplicativeElementWithInverseCollection returns true for GF(2) or [ 0 ].
Independent of any IsSomethingCollection information, a method that gets such a collection has to check whether its elements are admissible.

[fingolfin]

So, part of a solution to this situations is to simply not require (or rely) on IsMultiplicativeElementWithInverseCollection. I agree with that notion. Despite its name, it simply was not made for the purpose semigroups seems to want to use it: namely, argument validation.

@james-d-mitchell wrote:

In particular, if Semigroups is to use MatrixObjs, then Matrix from GAP (not Semigroups) will have to return a proper object (not a list of lists). If this isn't going to happen, then we will just not use MatrixObjs and find another way.

I do not understand this. First off, why does the return value of Matrix determine whether you use MatrixObj or not? MatrixObj is an abstract interface. One can thus use MatrixObj objects without ever calling Matrix -- the latter is simply a convenience function, but esp. for custom matrix types, you could easily have other constructors.

Warning: RANT ON ;-)

Also, you go on to talk about how you wait for a decision, and how what semigroups needs may not be important etc. etc. -- but as I repeatedly said before: the point of MatrixObj is not to satisfy some abstract need for, err, abstraction; but rather to facilitate writing code that solves actual problems people have. But to do so, we desperately need input from all people interested in this. That's why I wanted to badly to get this code finally into a shipping GAP version -- so that people can try it and give feedback.
So, if you just sit and wait for us to magically implement what you need, it won't happen. We need concrete feedback on what you need, and what works well, and what now, and what APIs are missing or useless, or ... So, "We need Matrix() to return a real object, not just a old-style list-of-list" is a highly useful data point, and will of course inform future decisions. I just wish there was more interaction, and that semigroups developers (and all other developers of GAP code) would join in the discussions on MatrixObj. Then there'd be some hope to eventually converge to something that works for all of us.

RANT OFF

Anyway, on the short term, I can't make any promises on what Matrix will or won't do -- simply because I don't know. For now, it returns lists-of-lists, simply because that's pragmatic and makes it possible to adapt some existing code quickly. It's conceivable that at some point, it'll always return a "proper" object (be it a IsPlistMatrixRep, or an instance of a hypothetical T_MATRIX tnum, or ... see also the discussion on issue #2776). That depends on somebody implementing the needed changes in a PR. And also perhaps some performance tuning (again, see discussion on #2776), to make the resulting objects attractive (nobody will use them if they make your code an order of magnitude slower).

[james-d-mitchell]

Alright @fingolfin that’s all the answer I need.

[fingolfin]

Update: so actually m := Matrix(GF(2), [[Z(2)]]); does not (contrary to what I believed before) return a list-of-lists, it rather returns a proper object. The problem with IsMultiplicativeElementCollection([m]); returning false is still caused by the family being used not having the IsMultiplicativeElement filter set. This could be fixed by using a different family, I guess -- but right now, this family is set to match the family of the corresponding list-of-lists, for compatibility reasons, i.e., to make lists containing both compressed and not compressed matrices be homogeneous...

I am afraid that changing this now would cause all kinds of legacy code to break. The "best" solution (as far as I can judge it right now) seems to be to add a new "compressed matrix" implementation which implements the new-style MatrixObj API only - so it doesn't try to act and look like a list-of-lists, gets its own family, doesn't support unbinding entries in the middle of the matrix, and is truly compact -- see issue #2148 for details.

Back to the old claim that Matrix may return a list-of-lists -- this is still true, e.g. when the base domains are the integers -- see issue #2972.