Add new "true" VectorObj / MatrixObj implementation which do not lie in `IsList`

[fingolfin]

The existing "vectors-as-lists" and "matrices-as-lists-of-lists" paradigm in GAP causes many subtle and not so subtle problems. Recently, one of them struck again, namely that of vectors of length 0, which are represented by empty lists; but the empty (plain) list does not have the "right" family for a vector space, so one gets confusing behaviour like this:

gap> V:=GF(3)^0;;
gap> Zero(V) in V;
false
gap> Zero(V) in Elements(V);
true
gap> Zero(V);
[  ]

And also this:

gap> W:=GF(5)^0;;
gap> Zero(W) = Zero(V);
true

Using VectorObj types seems like the natural solution. At first glance, the existing compressed vectors seem to solve the problem (at least for the small fields were they are available):

gap> v:=[];; CONV_VEC8BIT(v,3); v;
< mutable compressed vector length 0 over GF(3) >
gap> v in V;
true

So one might think about just using a compressed empty vector -- but (a) there are technical problems with that (zero length compressed vectors are poorly supported, see #2121), and (b) that doesn't actually solve that much, because compressed vector for historical reasons still lie in the filter IsList, and that means they have to adopt all kinds of undesirable behavior. Like this:

gap> v:=[];; CONV_VEC8BIT(v,3); v;
< mutable compressed vector length 0 over GF(3) >
gap> w:=[];; CONV_VEC8BIT(w,5); w;
< mutable compressed vector length 0 over GF(5) >
gap> v = w; v = []; w = [];
false
true
true

So transitivity of = is violated, and the reason is that v=w is buggy: since both are supposed to be lists, and lists are equal if they have equal elements, and both lists are empty, well: v=w should return true.

To overcome this, we need new VectorObj (and MatrixObj) implementations which are deliberately not in the filter IsList. We'd also need these for larger finite fields, and for characteristic zero. Then, we'd have to slowly switch the library to use these everywhere (or at least in as many places as possible), while simultaneously getting package authors to adapt their packages, too...

As to how to get there, I'll quote @stevelinton from PR #2125:

I think the right way to do this is just to retire the existing compressed vectors entirely in favour of somethign based on cvec and/or meataxe64 which have never been designed to lie in IsList. Cleaning up all the crud in the existing compressed vectors which is only there because of compatibility with lists is probably more work than writing something better.

However, I think that means switching all the linear algebra and matrix groups to work via MatrixObj, which is a huge task.

Personally, I also consider it an option to start with our existing compressed vector code, but to duplicate that and then edit the duplicate by removing list compatibility (i.e. I don't consider overhauling that code quite as problematic as Steve does). A fourth option would of course also be to start from scratch.

[stevelinton]

As part of the meataxe64 package, I have been playing with an implementation of meataxe64 matrices wrapped as VectorObj or MatrixObj objects. I haven't run into any insuperable problems so far but I did find the documentation a bit lacking in one respect.

The interface defines the semantics of lots of operations (new and existing) for these objects, but it doesn't make clear which ones you have to implement for a new representation and which ones are covered by generic methods so that you only need to implement them if you have a faster way of doing it in your particular representation, so I ended up writing a lot of code that was actually generic, and possibly unnecessary.

[fingolfin]

Yes, that's a known issue, and one that needs to be tackled ASAP. And the whole MatrixObj2 branch should be integrated back into master ASAP, too (though I have 1-2 concerns about it -- mostly, I object to the FoldList operation it introduces, whose name I find misleading (fold has other more well-known meaning in CS), and the general utility of which I do not see. But that's a minor quibble, easy to resolve... Still, some dedicated time to work on MatrixObj by a few people would be badly needed if there is to be any hope of progressing that. Perhaps another GAP Days for this should be organized.

[fingolfin]

Some more points to keep in mind:

• proper compressed MatrixObj would not store a list of VectorObjs; this means they can be even more compressed, and avoid a lot of overhead, and improve memory locality
• there is no need to support Unbind for entries, it rather should give an error
• for non-compressed MatrixObj, they could still often beat plists-of-plists, due to avoiding the massive type check performance penalty in method lookup for nested mutable plists.

[fingolfin]

See also #2776 (comment)

[fingolfin]

I am working on one such "proper" MatrixObj implementation in PR #2973. It would still be very nice to have them for compressed GF2 and 8bit vectors and matrices, too.