Bug implementing infinite Recursion?

[StephenG1CMZ]

I unintentionally implemented an infinite recursion of a function taking a list which should return a real integer (the number of items counter in the list).

The infinite recursion behaved unexpectedly.
The Prime only limits recursion depth in the CAS.

But instead of crashing, the code that should never return an integer, instead returns tthe input list and continues to execute (after several seconds).

Code:


 
 //Forward
 ListCOUNTANYDUPLICATES_SORTED(SORTEDLST);
 LOCAL ListANS;//OUTPUT LIST(WHEN NOT RETURNED)
  //Also, useful temporary results 
 EXPORT ListCOUNTANYDUPLICATES (LST)
 //Preferred-SORTED
 BEGIN
  ListANS:=ListSORT(LST);
  RETURN ListCOUNTANYDUPLICATES(ListANS);//UNINTENDED RECURSION
 END;

 EXPORT ListCOUNTANYDUPLICATES_SLOW(LST)
 //Caution ऊਉऊ be much slower but may be faster
 //REAL LST NO DUPS:5s 
 //INT LST 8000 DUPS:0.2s
 BEGIN
  RETURN SIZE(LST)-SIZE(ListREMOVEDUPLICATES(LST));
 END;

 EXPORT ListCOUNTANYDUPLICATES_SORTED(SortedLST)
 //Count how many duplicates in a sortedlist,Return a REAL INT
 //({1,9,9}=1 dup, {1,2,2,3,3,3}=3 dup)
 //Timings consistent 0.3s
 BEGIN
  LOCAL II;
  LOCAL DUPCOUNT:=0;
  IF SIZE(SortedLST)>1 THEN
   FOR II FROM 1 TO SIZE(SortedLST)-1 DO
    IF SortedLST(II) ==SortedLST(II+1) THEN
     DUPCOUNT:=DUPCOUNT+1;
    END;//IF
   END;//FOR
   //ELSE:SMALL LISTS HAVE NO DUPLICATES
  END;//IF
  RETURN DUPCOUNT;
 END;

 EXPORT ListExamples()
 //In real use, use XXX:=List...()
 BEGIN
  LOCAL LL:={1,2,3,4,5,6,7,8,9};
  PRINT();
  PRINT("C");
  PRINT("SLOW?");
  PRINT(ListCOUNTANYDUPLICATES({0,2,2,2}));//INFINITE RECURSION COMPLETES
  //SHOULD RETURN INTEGER (IF RECURSION CORRECTED) BUT RETURNS INPUT LIST
  PRINT("D");
  PRINT("Exampled");
  //RETURN 0; 
 END;

 EXPORT LBUG()
 BEGIN
  ListExamples();
 END;

(A fragment from my List V1.2 code, before bug fix. The intended return procedurename should be ..._SORTED)

Instead of printing C and erroring, the code fragment prints
C
{Input list}
D

At the point where D is printed, the count contains a list instead of an integer, which could lead to subsequent bugs in the user code...It would be better if the recursion were trapped and subsequent code not executed.

[Tim Wessman]

How would one be able to know if the recursion was intended a) and infinite b)...?

[Dave Britten]

(01-04-2018 04:43 PM)Tim Wessman Wrote:  How would one be able to know if the recursion was intended a) and infinite b)...?

Oh come on, everybody's solved the halting problem these days!

But yeah, if it's returning something rather than dying with a call stack overflow, that's kind of odd.

[Tim Wessman]

Not a question of "how to implement" but rather pointing out that just "block the recursion" is not something that is either desirable in many cases or possible within reason as there are many cases when you can have what appears to be an infinite recursion when in actuality it is not.

[StephenG1CMZ]

(01-04-2018 04:43 PM)Tim Wessman Wrote:  How would one be able to know if the recursion was intended a) and infinite b)...?

(A) one should note the reference to the code being a code fragment and compare the routine with the corrected code in my List V1.2 program... I didn't mention it just to plug my new program
The corrected code in V1.2 returns a count, and has no recursion.

The code fragment seems to call itself instead and has no obvious terminating condition...
Or am I missing something. Which in my working code would be unintended, though intended here in the interests of intending to show that the recursion is finite and the code continues to execute.
When in the full program, all the calls in ListExamples V1.2 execute after the infinitely finite recursion executes.

(B) The fact that my code prints SLOW and then the input list and then D suggests that on the Android, at least, the recursion is not infinite but is quite deep.

[TheKaneB]

One thing is not clear to me: is the call stack increasing as in a true infinite recursion, or does it stays the same depth as in a infinite iteration caused by recursive calling a function which always hit the base termination condition?

[StephenG1CMZ]

(01-04-2018 05:06 PM)Tim Wessman Wrote:  Not a question of "how to implement" but rather pointing out that just "block the recursion" is not something that is either desirable in many cases or possible within reason as there are many cases when you can have what appears to be an infinite recursion when in actuality it is not.

Of course whether or not it is infinite, or even whether or not it is recursion, is difficult to detect and largely unimportant. The simpler question is: Is there room to add another call to the stack? And if not, should I make it look like the program worked (almost)?

So, if you are struggling to discover some obscure bug such as how your code assigned a list to an integer... Consider the possibility that an infinitely deeply nested procedure call earlier in the execution might have completed and done that for you. In my case, I wasn't tracking down a non-integer count, just wondering why the program was a little slow (but only seconds, not minutes...With some calculations, you might not notice).