Dear GAP-Forum,

Alexander Hulpke writes:
> Roberto Radina wrote:
>
> > I'm using recursively defined lists, i.e. objects of this kind:
> > gap> a:=[];; b:=[a];; a[1]:=b;;
> >
> > I found that the basic operations don't work with these lists. For example:
> > gap> a=b;
> > causes to run out of memory.
> [...]
> > Is my usage of lists supported or it must be considered bad usage
>
> The GAP language permits the creation of recursive structures.
>
> Normally such recursive structures will arise only if two objects refer to
> each other (for example a group pointing to its derived subgroup and the
> derived subgroup pointing back to its parent) . In this situation comparison
> will not have to refer to the recursive part and thus the error you observed
> will not arise.
>
> However the comparison for lists which is used by GAP (two lists are equal
> if and only if its elements are equal) cannot be guarantee to
> test recursive objects of the kind you created for equality.
> I have to regret that your example -- while syntactically perfectly
> correct -- goes beyond the capabilities of GAP.
> (I must admit that I'm not even sure whether in your example `a' is equal to
> `b' -- either answer seems to be consistent. Therefore I can not even
> imagine an algorithm that would answer your question.)
>
> You might consider this to be an unfixed error and our only excuse for this
> is that we are only human.

IMHO, this is not an unfixed error - indeed, no program can check if
any two *infinite* (nested) lists are equal. In the example above,
both a and b are equal to [[[...]]] (infinitely many brackets there.)

The only advice I can give you for your concrete problem is either not to
use equality comparison (Probably an `IsIdenticalObj' which only compares
the pointers to the top level lists is sufficient for your purpose?) or to
make the recursion indirect via indices (coding the equality test
yourself).

The problem is rather how one can handle infinite lists on a computer.
It seems that the standard technique is "lazy evaluation".
Say, for the example above, one could do the following.

gap> a:=[];; # initial assignment.
gap> b:=function() return a; end; # b:=[a]
function (  ) ... end
gap> a:=function() return b; end; # a:=[b];
function (  ) ... end
gap> a=b;
false
gap> a()=b; # a[1]=b ?
true
gap> b()=a; # b[1]=a?
true
gap> b()()=a; (b[1])[1]=a?
false
gap> b()()=b; # etc...
true
---------------
The results of that "="'s can be perhaps considered to be a proof that 
a and b are infinite.

>I think that if recursion is to be allowed then the function '=' must at
>least report the problem and not cause exiting, wasting all the work made.

I agree that it would be desirable to have GAP report an error message
than simply exiting. Not knowing how much work this would involve to
implement (and whether it would come with a performance cost for
``ordinary'' list comparisons) however I'm reluctant to promise that such a
test will be implemented in future versions.

If this is simply a stack overflow that causes GAP to exit abnormally,
then it can probably be caught somehow. Perhaps the user might have
an installation option whether he wants a "safe" or an "unsafe"
executable.

If it's a problem that GAP tries to request more space from the OS,
and this fails, then I don't know...

Best regards,
Dmitrii
http://ssor.twi.tudelft.nl/~dima/