Problems with and limitations of recursive lists

[Stefan-Kohl]

Observed behaviour

gap> EncodeGraphAsRecursiveList := function ( edges )
> 
>      local  vertices, edge, n;
> 
>      n := Maximum(Flat(edges));
>      vertices := List([1..n],i->[]);
>      for edge in edges do
>        Add(vertices[edge[1]],vertices[edge[2]]);
>        Add(vertices[edge[2]],vertices[edge[1]]);
>      od;
>      return vertices;
>    end;
function( edges ) ... end
gap> edges := [[1,2],[2,3],[3,4],[4,5],[1,5],
>              [1,6],[2,7],[3,8],[4,9],[5,10],
>              [6,8],[6,9],[7,9],[7,10],[8,10]];;
gap> PetersenGraph := EncodeGraphAsRecursiveList(edges);;
gap> PetersenGraph[1][1][1] = PetersenGraph[3];
Speicherzugriffsfehler (Speicherabzug geschrieben)

Expected behaviour

gap> PetersenGraph[1][1][1] = PetersenGraph[3];
true

Observed behaviour

gap> edges := [[1,2],[2,3],[3,4],[1,4]];;
gap> square := EncodeGraphAsRecursiveList(edges);
[ [ [ ~[1], [ ~[1][1], [ ~[1][1][2], ~[1] ] ] ], 
      [ [ [ ~[1], ~[1][2][1] ], ~[1][2] ], ~[1] ] ], 
  [ [ ~[2], [ [ ~[2], ~[2][1][2] ], ~[2][1] ] ], 
      [ ~[2], [ ~[2][2], [ ~[2], ~[2][2][2] ] ] ] ], 
  [ [ [ ~[3][1], [ ~[3], ~[3][1][1] ] ], ~[3] ], 
      [ ~[3], [ [ ~[3][2][2], ~[3] ], ~[3][2] ] ] ], 
  [ [ [ [ ~[4][1][1], ~[4] ], ~[4][1] ], ~[4] ], 
      [ [ ~[4][2], [ ~[4][2][1], ~[4] ] ], ~[4] ] ] ]
gap> square =
> [ [ [ ~[1], [ ~[1][1], [ ~[1][1][2], ~[1] ] ] ], 
>       [ [ [ ~[1], ~[1][2][1] ], ~[1][2] ], ~[1] ] ], 
>   [ [ ~[2], [ [ ~[2], ~[2][1][2] ], ~[2][1] ] ], 
>       [ ~[2], [ ~[2][2], [ ~[2], ~[2][2][2] ] ] ] ], 
>   [ [ [ ~[3][1], [ ~[3], ~[3][1][1] ] ], ~[3] ], 
>       [ ~[3], [ [ ~[3][2][2], ~[3] ], ~[3][2] ] ] ], 
>   [ [ [ [ ~[4][1][1], ~[4] ], ~[4][1] ], ~[4] ], 
>       [ [ ~[4][2], [ ~[4][2][1], ~[4] ] ], ~[4] ] ] ];
> [ [ [ ~[1], [ ~[1][1], [ ~[1][1][2], ~[1] ] ] ], 
Error, List Element: <list>[1] must have an assigned value
not in any function at line 16 of *stdin*
you can 'return;' after assigning a value
brk>       [ [ [ ~[1], ~[1][2][1] ], ~[1][2] ], ~[1] ] ], 
Error, List Element: <list>[1] must have an assigned value
not in any function at line 1 of *errin*
you can 'return;' after assigning a value
brk_2>   [ [ ~[2], [ [ ~[2], ~[2][1][2] ], ~[2][1] ] ], 
Error, List Element: <list>[2] must have an assigned value
not in any function at line 1 of *errin*
you can 'return;' after assigning a value
brk_3>       [ ~[2], [ ~[2][2], [ ~[2], ~[2][2][2] ] ] ] ], 
Error, List Element: <list>[2] must have an assigned value
not in any function at line 1 of *errin*
you can 'return;' after assigning a value
brk_4>   [ [ [ ~[3][1], [ ~[3], ~[3][1][1] ] ], ~[3] ], 
Error, List Element: <list>[3] must have an assigned value
not in any function at line 1 of *errin*
you can 'return;' after assigning a value
brk_5>       [ ~[3], [ [ ~[3][2][2], ~[3] ], ~[3][2] ] ] ], 
Error, List Element: <list>[3] must have an assigned value
not in any function at line 1 of *errin*
you can 'return;' after assigning a value
brk_6>   [ [ [ [ ~[4][1][1], ~[4] ], ~[4][1] ], ~[4] ], 
Error, List Element: <list>[4] must have an assigned value
not in any function at line 1 of *errin*
you can 'return;' after assigning a value
brk_7>       [ [ ~[4][2], [ ~[4][2][1], ~[4] ] ], ~[4] ] ] ];
Error, List Element: <list>[4] must have an assigned value
not in any function at line 1 of *errin*
you can 'return;' after assigning a value

Expected behaviour

gap> square =
> [ [ [ ~[1], [ ~[1][1], [ ~[1][1][2], ~[1] ] ] ], 
>       [ [ [ ~[1], ~[1][2][1] ], ~[1][2] ], ~[1] ] ], 
>   [ [ ~[2], [ [ ~[2], ~[2][1][2] ], ~[2][1] ] ], 
>       [ ~[2], [ ~[2][2], [ ~[2], ~[2][2][2] ] ] ] ], 
>   [ [ [ ~[3][1], [ ~[3], ~[3][1][1] ] ], ~[3] ], 
>       [ ~[3], [ [ ~[3][2][2], ~[3] ], ~[3][2] ] ] ], 
>   [ [ [ [ ~[4][1][1], ~[4] ], ~[4][1] ], ~[4] ], 
>       [ [ ~[4][2], [ ~[4][2][1], ~[4] ] ], ~[4] ] ] ];
true

Copy and paste GAP banner (to tell us about your setup)

GAP 4.8.5, 25-Sep-2016, build of 2016-09-27 22:24:36 (CEST)
 │  GAP  │   http://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-gcc-default64
 Libs used:  gmp
 Loading the library and packages ...
 Components: trans 1.0, prim 2.1, small* 1.0, id* 1.0
 Packages:   GAPDoc 1.5.1

[fingolfin]

Here is a much simplyer way to trigger the crash:

gap> x:=[~];y:=[~];
[ ~ ]
[ ~ ]
gap> x=y;

[Stefan-Kohl]

@fingolfin : Yes, indeed. -- What I wanted to show is what one might want to work.

[fingolfin]

@Stefan-Kohl Well for debugging the issue, the most simple way to reproduce it is best :-). And a crash is a bug that must be fixed, regardless of whether the example to reproduce it is contrived or not...

Anyway: I think we all agree that a crash is not an acceptable outcome for such an comparision.

However, it is less clear to me what the correct result should be. Maybe true, but maybe also Error: comparison of recursive data structures is not supported... After all, what should the definition be for comparing recursive list or records? So far, we define equality of lists more or less like this: "two lists are equal if they have the same lenght, have the same positions bound, and the elements in these bounds positions are equal". But that definition only works for non-recursive structures.

For recursive structures, fully solving this would require solving graph isomorphism problems, as you example shows. I do not think we should attempt to do that!

So all in all, producing an error seems to be the only sensible solution to me.

[ChrisJefferson]

Another option would be to at least produce a stack overflow.

The reason this currently crashes, rather than producing GAP's normal Error, recursion depth trap (5000) is that it stays in C code. We could extend the stack check to include C code (this would involve explicit function calls in the C code, but wouldn't be hard), so the same error message occurred.

[Stefan-Kohl]

@fingolfin Indeed solving graph isomorphism problems might be unreasonable -- though why not make this work for small cases, and if the graphs to be compared get too big, isomorphism testing just takes too long? -- Where things seem to work is the case that the compared objects are even identical (at least in the cases I have tried).

[fingolfin]

Comparing identical objects indeed always works in GAP, because we assume the axiom that identity implies equality (footnote: this is actually not always satisfied on computers; for some reasons I'll never agree with, the IEEE 754 committee thought it to be a good idea to define NaN == NaN as false).

As to solving graph isomorphism for "small cases": What should that even mean? How do we define the "size" of the graph, given that it's not really a graph, but possibly a complicated structure consisting of nested lists, records, and other objects? The relevant code necessarily would be horribly complicated and error prone -- yet I fail to see any substantial advante for that. If somebody really, really wanted to use recursive data structures to e.g. represent graphs like that, I think it would be reasonable to expect them to provide their own equality test function.

So I'd prefer if our current recursive equality test also marks objects it already saw, and raises an error if it sees an object again. But of course that is also non-trivial (and one has to be careful to make this work in HPC-GAP; e.g. by using the objset code). Alternatively, the equality code could have a recursion depth counter, and refuse to compare objects which are nested beyind a certain depth, say 1000.

[ChrisJefferson]

One problem I have with explicitly fixing = is where to stop... obviously then have to do <, then what about say Flat, or ....

Now, GAP shouldn't crash to the command line certainly, and we should have a good plan (for example, I noticed while you can output recursive lists to the terminal, String doesn't work. But it at least prints a GAP level recursion depth trap).

[fingolfin]

@ChrisJefferson I am not sure what you mean with "explicitly fixing" -- for me, "fixing" means "not crash". And as I described earlier, I'd be fine if comparing recursive data structures (RDS) leads to an error.

Bow, things that are implemented on the library level should be fine because the GAP interpreter already has a recursion depth trap. E.g.

gap> Flat([~]);
Error, recursion depth trap (5000)

and I think that's perfectly fine: it's an error, but not a crash.

So, the point where we stop should be when we fixed all kernel functions to correctly deal with RDS. We also should add test for these cases, of course.

[ChrisJefferson]

Ah, I interpreted fix to mean "produce the logically correct answer".

[fingolfin]

As I said, it's not clear to me whether there really is a "logically correct answer" in all conceivable cases... And even if there is, as explained, I don't think it's reasonable to solve a problem that is at least as complicated as graph isomorphism to achieve this :-).

Just not crashing is IMHO enough here. But even if people disagree, I hope we can agree that making it not crash should be the top priorit.

[fingolfin]

Perhaps we can simply reuse the existing RecursionDepth counter for this.

E.g. we could modify the EQ and LT macros to check it. Or at least the EqPlist, LtPlist, ... methods?

[fingolfin]

and also FuncEQ_PREC and FuncLT_PREC. BTW, I wonder why those aren't installed for EqFuncs resp. LtFuncs, that seems to cause unecessary overhead?!?

[stevelinton]

In the past I've steered clear of doing this because it seemed likely to slow down lots of useful things like matric comparison, just in order to produce an error from code that was essentially never going to do anything useful. However now we have an implementation in @fingolfin's branch, we can actually check whether it does slow things down noticeably.

[Stefan-Kohl]

@stevelinton Would such checks really cause a significant slowdown for comparisons that work? -- If so, then likely introducing these checks is too much overhead (in the end, what may otherwise happen is only a crash, and not wrong results).