[R] Problem with nested functions - functions nested too deeply in source code

[Duncan Murdoch]

Duncan Murdoch wrote:
> Maximilian Kofler wrote:
>   
>> Duncan Murdoch <murdoch.duncan <at> gmail.com> writes:
>>
>>
>>   
>>     
>>> I doubt if that was the error message.  More likely you saw
>>>
>>> Error: evaluation nested too deeply: infinite recursion / 
>>> options(expressions=)?
>>>     
>>>       
>> Exactly this was the error message I recieved
>>  
>>   
>>     
>>> This isn't a case of the source being nested to deeply, but rather of the 
>>> evaluation being nested too deeply.  
>>> This happens in recursive algorithms when R runs out of 
>>> stack space, around 5000 calls deep.  Is it likely in your dataset that 
>>> a recursion depth of 5000 is reasonable?  In most cases this indicates a 
>>> programming error that leads to an infinite recursion, but there are 
>>> probably cases where a depth like that is reasonable.
>>>     
>>>       
>> I don't think that it is a programming error, because I succeyyfully 
>> calculated subgraph isomirphism with the algorithm, but with 
>> smaller input graphs.
>>     
>
> The programming error might be in the design, not the implementation.  
> For example, you can sum a vector like this:
>   

I've taken a look at your original functions, and I can't spot cases as 
obvious as the one below, so there isn't going to be a quick fix for 
this.  Here are my suggestions:

 - Name your functions meaningfully.  You named them refine1 to refine9, 
so it's not at all obvious what they are trying to do.

 - Use nested functions.  You are passing lots of arguments in every 
function call, e.g.

> refine1 <- function(M, A, B, p_A, p_B, FAIL, elim, i, j, k, sc, h, lst, x){
>     
>     #print("refine 1")
>     
>     # elim marks if there was eliminated a 1 (and changed to 0)
>     
>     lst <- vector(mode = "numeric")
>     elim <- 0
>     i <- 1
>     
>     refine2(M, A, B, p_A, p_B, FAIL, elim, i, j, k, sc, h, lst, x)
> }

The call to refine2 uses exactly the same values of M, A, B, p_A, p_B, FAIL, j, k, sc, h and x as were passed to refine1.  Those
might be good candidates to be variables in a big outside function, with refine1 being nested within it, e.g.

refine <- function(M, A, B, p_A, p_B, FAIL, j, k, sc, h, x) {
  refine1 <- function() {
    lst <- ...
    elim <- 0
    i <- 1
    refine2(elim, i, lst)
  }

etc.

which might make it easier to read and fix.  Doing this won't reduce the depth of nesting of your functions, but it will save
some memory (and maybe some protection stack) and will make your functions easier to read, so perhaps you can recognize what's wrong.  (It does make things slightly harder to debug:  you can't say debug(refine1) outside of the refine(), but you can use setBreakpoint() to set a breakpoint in it.)

Duncan Murdoch


> badSum <- function(x) {
>   if (length(x) > 1) x[1] + badSum(x[-1])
>   else x
> }
>
> and you'll get the right result for vectors of lengths from 1 up to 
> around length 5000, but not for bigger ones.  The solution in some 
> languages is to recognize when recursion is being used unnecessarily and 
> to optimize it away, but R doesn't do that.  So the programmer has to 
> recognize when recursion isn't really needed and rewrite the function to 
> work without it.  For example, in the case above, we don't need x after 
> extracting x[1], so there's no need to make a new call to badSum (which 
> preserves it).  Just turn it into a loop:
>
> notsobadSum <- function(x) {
>   result <- x[1]
>   while (length(x) > 1) {
>     x <- x[-1]
>     result <- result + x[1]
>   }
>   result
> }
>
> (This is still a bad way to compute a sum in R, it is just a simple 
> illustration).
>
>   
>>  So the algorithm seems to work. 
>> I already tried to set options(expressions=500000), but 
>> then I cause a protection stack overflow: 
>>
>> error:  protect(): protection stack overflow
>>
>> Is the problem that too many objects are stored in the stack? 
>>   
>>     
>
> Too many stack frames.  You're not running out of memory, you're running 
> out of a particular type of memory.  When you set expressions to 500000 
> you just started to run out of a different resource.  The help page 
> ?options tells you how to work around that one, but I suspect you really 
> need to rewrite your functions so they only recurse
> when they need to.
>
> Duncan Murdoch
>   
>> If yes, somebody knows how to solve this 
>> problem?
>>
>> thanks for your replies
>>
>> ______________________________________________
>> R-help at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
>> and provide commented, minimal, self-contained, reproducible code.
>>   
>>     
>
>