DO-loop in recursive Function

Hello, task of the recursive function below is to analyse a network of of elements. The elements are characterized by a section no. 'iA' and an element no 'iM'. Each element can have up to 8 inlets and outlets. IANMSA is the number of oulets of an element. The circuitry of the elements is stored in the arrays IAANRA, IAMNRA. At runtime the error 'Active Do-loop index altered' occurs.

     Recursive Function CFBCheckLoop(iA, iM) RESULT(KFehl)
     Integer, Intent(in) :: iA, iM 
     Integer :: KFehl
     Integer :: iT, iA1, iM1
       if (iA == WSMem%IAVB) then
         KFehl = 0
       else if (kkdms(iA,iM) == 506) then
         KFehl = 1
       else
         do iT = 1, IANMSA(iA, iM)
           iA1 = IAANRA(iA, iM, iT)
           iM1 = IAMNRA(iA, iM, iT)
           if (iA1 == 0) then 
             KFehl = 2
           else 
             KFehl = CFBCheckLoop(iA1, iM1)
           end if
           if (KFehl > 0) Exit 
         end do 
       end if  
     End Function CFBCheckLoop

Obviously the inner instance of the recursive function changes the index 'iT' of the calling instance of the function. The variable iT is declared inside the function. Normally each instance of an recursive function should have its own protected internal variables, which cannot be changed from outside. They should also be protected against changes from another instance of the function. I have used recursive functions like this in Delphi/Pascal many times without any problems.

I don't see that the recursion has anything to do with the error. Inside the DO loop, you are passing the loop index as an argument to the function IANMSA. If that function changes its third argument, the code is illegal and runtime behavior is unpredictable. Section 8.1.6.6.2, Clause 2 of the Fortran 2008 standard states, 'Except for the incrementation of the DO variable that occurs in step (3), the DO variable shall neither be redefined nor become undefined while the DO construct is active.' Similar statements can be seen in Section 8.1.6.4.2 of the F2003 standard and earlier standards. Postscript: If IANMSA is an array, is there a declaration in scope for it?

Quoted from Garling

Normally each instance of an recursive function should have its own protected internal variables, which cannot be changed from outside. They should also be protected against changes from another instance of the function.

Yes, this is exactly how it works (local variables are created on the stack for each function invocation). This is guaranteed if you use the RECURSIVE declaration but you need to create an explicit interface for the function where you call it from outside.

I have not found any problems with Recursion with this compiler. However, there is too much missing from your example to debug your problem. Too many arrays that are not there.

Could you produce a simpler version which is self-contained that could be compiled and run to demonstrate the error.

Looking at your code I can't see anywhere that IT would be re-defined. What does the stack trace look like when you call this from the debugger; how many times is your function called? Is the error in some other function? (Look at the stack).

mecej4

My reading of this is that IANMSA is supposed to be an array (not a function) that is somehow in scope. So that would mean this function is part of a module or an internal function.

Quoted from mecej4 I don't see that the recursion has anything to do with the error. Inside the DO loop, you are passing the loop index as an argument to the function IANMSA. If that function changes its third argument, the code is illegal and runtime behavior is unpredictable. Section 8.1.6.6.2, Clause 2 of the Fortran 2008 standard states, 'Except for the incrementation of the DO variable that occurs in step (3), the DO variable shall neither be redefined nor become undefined while the DO construct is active.' Similar statements can be seen in Section 8.1.6.4.2 of the F2003 standard and earlier standards.

Another possible source of error. In a call to CFBCheckLoop from elsewhere (i.e., other than calls to self), the function result type would be wrong with IMPLICIT variable typing.

No, the function would need to have an explicit interface so could deduce that the function returns an integer.

There could be numerous problems. We just don't know without seeing the code.

My guess is the error has nothing to do with this function at all, which is why I suggested the OP looks at the stack trace (to find the real culprit)

Sorry for the incomplete source code, as davidb supposed the function is an internal function after a 'CONTAINS' in a subroutine. IANMSA, IAANRA, IAMNRA and KKDMS are arrays, which contain information about the circuitry and the type of element. The variable iT is exclusively changed by the Do-loop itself. The function is called once from its owner-subroutine within a complex program containing about 250000 lines of source-code. I have reduced the problem to some 50 lines:

Program Rekursion Integer, Dimension (10, 8) :: IANMSA Integer, Dimension (10, 8, 8) :: IAANRA, IAMNRA Integer :: iAVB , KF

IANMSA(1, 1) = 2 IANMSA(2, 1) = 2 IANMSA(3, 1) = 1 IANMSA(4, 1) = 1 IANMSA(5, 1) = 1 IANMSA(6, 1) = 0 IAANRA(1, 1, 1) = 2
IAANRA(1, 1, 2) = 5
IAANRA(2, 1, 1) = 3
IAANRA(2, 1, 2) = 4
IAANRA(3, 1, 1) = 6
IAANRA(4, 1, 1) = 6
IAANRA(5, 1, 1) = 6
IAMNRA(1, 1, 1) = 1
IAMNRA(1, 1, 2) = 1
IAMNRA(2, 1, 1) = 1
IAMNRA(2, 1, 2) = 1
IAMNRA(3, 1, 1) = 1 IAMNRA(4, 1, 1) = 1 IAMNRA(5, 1, 1) = 1 IAVB = 6

KF = CFBCheckLoop(1, 1)

CONTAINS

Recursive Function CFBCheckLoop(iA, iM) RESULT(KFehl) Integer, Intent(in) :: iA, iM Integer :: KFehl Integer :: iT, iA1, iM1 if (iA == IAVB) then KFehl = 0 else do iT = 1, IANMSA(iA, iM) iA1 = IAANRA(iA, iM, iT) iM1 = IAMNRA(iA, iM, iT) if (iA1 == 0) then KFehl = 1 else KFehl = CFBCheckLoop(iA1, iM1) end if if (KFehl > 0) Exit end do end if End Function CFBCheckLoop

End Program Rekursion

This new version compiles and runs just fine for me (even with CheckMate enabled to check for re-definition of do loop variables). I can confirm the call stack grows and shrinks properly with a different activation record created at each function invocation.

What compiler version are you using?

What compile options have you got set?

I think that in extracting the code and reducing it to a small size you removed the part that was causing the problem. I do not find any problems in the putative 'reproducer', and DavidB has said the same.

I do notice a potential problem. In the contained function, if the loop upper limit is less than 1, the function returns without the function value having been defined. This would happen if, for example, you raised the value of IAVB to 7.

I have changed the sample program to track the calls. The returned value is always 0. Is this what it should do ?

Program Rekursion 
 Integer, Dimension (10, 8) :: IANMSA 
 Integer, Dimension (10, 8, 8) :: IAANRA, IAMNRA 
 Integer :: iAVB , KF, lev

   IANMSA(1, 1) = 2 
   IANMSA(2, 1) = 2 
   IANMSA(3, 1) = 1 
   IANMSA(4, 1) = 1 
   IANMSA(5, 1) = 1 
   IANMSA(6, 1) = 0 
!
   IAANRA(1, 1, 1) = 2 
   IAANRA(1, 1, 2) = 5 
   IAANRA(2, 1, 1) = 3 
   IAANRA(2, 1, 2) = 4 
   IAANRA(3, 1, 1) = 6 
   IAANRA(4, 1, 1) = 6 
   IAANRA(5, 1, 1) = 6 
!
   IAMNRA(1, 1, 1) = 1 
   IAMNRA(1, 1, 2) = 1 
   IAMNRA(2, 1, 1) = 1 
   IAMNRA(2, 1, 2) = 1 
   IAMNRA(3, 1, 1) = 1 
   IAMNRA(4, 1, 1) = 1 
   IAMNRA(5, 1, 1) = 1 
!
   IAVB = 6 
   lev  = 1

   KF = CFBCheckLoop(1, 1, lev, 0) 
   write (*,*) Kf

 CONTAINS 

 Recursive Function CFBCheckLoop(iA, iM, lev, iTe) RESULT(KFehl) 
 Integer, Intent(in) :: iA, iM, lev, iTe
 Integer :: KFehl 
 
 Integer :: iT, iA1, iM1, levn

 write (*,fmt='(a,4i4)') 'entry', lev, iA, iM, iTe

 if (iA == IAVB) then 
   iT    = -1
   KFehl = 0 
 else 
   do iT = 1, IANMSA(iA, iM) 
     iA1 = IAANRA(iA, iM, iT) 
     iM1 = IAMNRA(iA, iM, iT) 
     if (iA1 == 0) then 
       KFehl = 1 
     else 
       levn  = lev + 1
       KFehl = CFBCheckLoop (iA1, iM1, levn, iT) 
     end if 
     if (KFehl > 0) Exit 
   end do 
 end if 
 write (*,fmt='(a,5i4)') 'exit ', lev, iA, iM, iT, KFehl
 End Function CFBCheckLoop 

 End Program Rekursion

Results are Lev iA iM iT KFehl entry 1 1 1 0 entry 2 2 1 1 entry 3 3 1 1 entry 4 6 1 1 exit 4 6 1 -1 0 exit 3 3 1 2 0 entry 3 4 1 2 entry 4 6 1 1 exit 4 6 1 -1 0 exit 3 4 1 2 0 exit 2 2 1 3 0 entry 2 5 1 2 entry 3 6 1 1 exit 3 6 1 -1 0 exit 2 5 1 2 0 exit 1 1 1 3 0 0

The returned value is always 0. Is this what it should do ?

I think that there is no problem there. In fact, KFEHL could have been LOGICAL rather than INTEGER and, for English speakers, KFEHL could have been spelled KFAIL or LERROR.

Thus, it makes sense that KFEHL comes out with a value corresponding to 'NO ERROR', indicating that the logic implemented in the program is correct to the extent that the run did not encounter any instance of the logic being wrong. In other words, KFEHL.EQ.0 is a 'sanity check'.

Hello, I am a little bit surprised, that you have no problems with this code. When I run this reduced program, I get a runtime error:

Error: Active Do-loop index altered

REKURSION~CFBCHECKLOOP - in file rekursion.f95 at line 45 [+02e6] [recur= 1] main - in file rekursion.f95 at line 28 [+0138]

I am using the version 7.1.0.0 of the ftn95.exe from 2014/04/27. My ftn95.cfg contains the following option:

/132 /CHECK /COLOUR /DELETE_OBJ_ON_ERROR /INTL /LOGL /NO_BANNER /PAUSE_ON_ERROR /SAVE /ZEROISE

/save and Recursive are definitely incompatible. Make sure you understand this is a requirement for recursive. I am not sure about /zero also.

Remove /save and check that /zero is not needed, by initialising all appropriate variables before use and it should work.

John

Garling: I second what John said about recursion and /save being incompatible. To see this for yourself, take the program that you gave above (Fri Nov 28, 2014 9:05 am)

1. Add 'iasav' to the declarations of integer variables in the main program

2. Add 'iasav=ia' before the recursive call in the subroutine.

3. Add the following after the recursive call:

   if(iasav.ne.ia)then write(,)'IA changed from ',iasav,' to ',ia stop endif

Now compile and run (i) first without /save, then with /save. You may be surprised that invoking a function results in IA being changed even though the function arguments (and the variable to which the function value is assigned) are all variables other than IA. But that is precisely what happens when you use /save together with recursion.

Let me point out that it is possible to write a non-recursive version of the function, and you should consider taking this approach if you must use /save for the other portions of the program. However, note that using /save is often a temporary fix for a serious problem.

I agree. You cannot use /SAVE with recursive subprograms.

However, note that.

(1) The compiler should be detecting the recursive function (in this case) and should switch off the effect of /SAVE in this function. If it doesn't, this may be a bug or an oversight with the compiler (Paul could perhaps look at this?)

(2) If you need to save variables then it is better to insert SAVE statements in the appropriate subroutines and functions. This issue does not then arise. Note the compiler will correctly show an error if SAVE is inserted into a RECURSIVE subprogram.

(3) You may be able to fix your program and still use /SAVE by adding the PURE declaration (as well as RECURSIVE) to your function. The compiler may then switch /SAVE off properly (I have not tried this though).

Beyond the incompatibilities between /save and recursive functions, I think that the example code posted by Garling (on Fri Nov 28, 2014 9:05 am, see above) brings out a bug in the FTN95 7.1 compiler when the /save option is used.

Here are details on how to see the bug. Compile the code with /debug /save. Start SDBG and set a breakpoint on Line-40, which contains

iA1 = IAANRA(iA, iM, iT)

Press Run twice. With the program now stopped on Line-40, note the values of IA and IM (2 and 1). Step to the next line. Note that IA changed to 3! This happened, despite IA being an INTENT(IN) argument.

At the assembler level, the problem occurs because the static (because of /save) local variable, IA1, and the first function argument, IA, have been aliased to the same address (the SS and DS register contents are equal). Thus, assigning to IA1 on Line-40 changes the value of IA used on Line-41.

This is the bug at its inception. From now on, since this incorrect value of IA is used as an array index, lots of things start going wrong, including accesses to uninitialized parts of the arrays.

I have compared this behavior with IFort and Gfortran (using /Qsave and -fno-automatic, respectively). They do no behave in this fashion.