Error Messages/40938

Example Error Message

 Stack overflow. This condition occurs when pending evaluations of variables or functions get nested too deeply. The most common cause is a recursive user-defined function with an infinite, or excessively deep, recursion.

Call stack:

   Do_srch
   Do_srch
   Do_srch
   ... { 8656 function calls not shown }
   Do_srch
   Do_srch
   Srch_on_v
   Va1

Cause: UDF Recursion

As the message suggests, the most common cause is a recursive User-Defined Function (a UDF that calls itself), with no termination condition ever satisfied. For example, the error occurred in this recursive function:

 Function Do_srch(v: atom handle; L: list handle) 
 Definition:  
   Var n := Size(L, listLen: true);
   If n > 0 Then (
     MetaVar f1 := Slice(L, 1);
     MetaVar rest := Slice(L, Sequence(2, n, strict: true));
     WhatIf(Do_srch(v, L), f1, fixVal[theVar = f1])
    ) Else ...

In this case, there was a bug in Do_srch(v, L), which should have been Do_srch(v, rest). The bug caused the recursive function to call itself with the same parameters each time.

Cause: Dynamic Recursion

In some cases, a deep recursion can result from within a Dynamic loop, which can lead to a stack overflow, especially with large Time indexes. A few examples will be shown to illustrate the issue.

Reverse Recurrence

The first example is a Dynamic loop that depends on the next element, rather than the previous element, with the boundary condition being at the last time point rather than at the first time point:

Index Time := 1..100K

Variable U := Dynamic(If Time = 100K Then 1 Else Self[Time = Time + 1]/1.10)

When this is evaluated, the computation starts with U[Time = 1]. But to complete this, U[Time = 2] is required, so a call to compute U[Time = 2] is launched. This requires U[Time = 3], which requires U[Time = 4], etc., each spawning a new call, resulting in a long recursion which increases stack depth. In this example, 100,000 nested calls are required, which far overflows available stack space.

The problem is easily remedied in this case by specifying reverse: true:

Variable U := Dynamic(If Time = 100K Then 1 Else Self[Time = Time + 1]/1.10, reverse: true )

Delayed request of future value

A second example illustrates a trickier case. Consider:

Index Time := 1..100K

Variable X := Dynamic(1, If Time > 99K Then Y[Time - 1] + 1 Else Self[Time - 1] + 1)

Variable Y := Dynamic(1, Self[Time - 1] + X[Time - 1])

In this example, X and Y are in the same dynamic loop, each depending on the other's value at the previous time step. However, X doesn't make use of Y's value until Time > 99K. When X is evaluated, the values X[Time = 1..99K] are immediately computed via iteration, so that no stack growth occurs during this stage. But then when the evaluation of X[Time = 99001] is attempted, it is found that Y[Time = 99000] is required. The evaluation of Y[Time = 99000] requires Y[Time = 89999] which requires Y[Time = 89998] which requires Y[Time = 89997], and so on. This sequence of evaluations becomes a recursion, and in this example the recursion is 99000 levels deep, which easily overflows the stack.

In a case like this, evaluating Y before X solves the problem, since Y is then evaluated in order via an iteration. To handle the case where X is evaluated first, you can ensure that Y's computation keeps pace with X's computation, so that when it reaches Y[Time = 99001], the entire sequence back doesn't have to be computed fresh. In this example, changing If to IfAll would have the desired effect:

Variable X := Dynamic(1, IfAll Time > 99K Then Y[Time - 1] + 1 Else Self[Time - 1] + 1)

Alternatively, you could reduce the maximum recursion within Y itself:

Variable Y := Dynamic(1,

If Time > 100 Then Self[Time - 100];

Self[Time - 1] + X[Time - 1])

The clause inserted here has no impact on the computed result; however, its effect reduces the recursion depth by a factor of 100. To see this, consider the calculation of Y[Time = 99000]. The clause requests Y[Time = 89900] before requesting Y[Time = 89999]. The first clause ensures that Y is computed through Time = 89900, so the recursion afterwards needs to proceed only from Y[Time = 89999], Y[Time = 89998], ..., Y[Time = 89900]. Hence, the original clause (to the right of the semi-colon) is now limited to a recursive depth of 100. The computation of Y[Time = 89900] must recurse to obtain [Time = 89800] and so on, but the number of steps is now 1/100th what is previously was (a depth of 1000, rather than the original 100K). Pushing this idea a bit further, an iteration can be used to ensure that the recursion depth is kept to 100:

Variable Y := Dynamic(1,

For k := Sequence(100, Time - 1, 100, 100, strict: true) Do Self[Time - k]; { Limit recursion depth to 100 }

Self[Time - 1] + X[Time - 1])

Luckily, this type of trickery is seldom necessary. The examples illustrated here have arisen in practice, but only rarely. However, if you have encountered a stack overflow involving a dynamic loop, then you may need to understand this principle, and then worry about injecting a recursion limiter only where it is necessary.

Finding the Dynamic recursion

How do you find where in your model a dynamic recursion is occurring? The stack overflow error message often points you to the key variable (e.g., Y in the above example), but not always, and it doesn't reveal where it is being called from and which time value the recursion is starting from. It also just tells you that a stack overflow has occurred, but doesn't diagnose it as a delayed request as in this example.

The best way to locate the precise source of a dynamic recursion problem is to do the following.

Open the Typescript window by pressing F12
Type: Verbosity:134
Type: Photo "C:\Temp\photo.log" { pick your own filename, as appropriate }
Evaluate your model until the stack overflow occurs.
Note: With Verbosity on, this will take much longer than usual
After the stack overflow has occurred, press F12 again to return to the Typescript window.
Type: EndPhoto
Type: Verbosity:2 { restore its original value}
Open the log file, "C:\Temp\photo.log", in a text editor such as Notepad.
Scan the file for a series of lines, probably near the end, with a huge number of dots preceding them. Each dot of indentation indicates one level of recursion.

Here is an excerpt from a log file where this problem occurred:

....Evaluating Spinning_Reserves_Di[Time = 1801] dloop=263 .
.....Evaluating Minimum_Operating_L3.
.....Evaluating Net_Spinning_Reserve[Time = 1801] (dynamic) dloop = 263.
......Evaluating Net_Spinning_Reserve[Time = 1800] (dynamic) dloop = 263.
.......Evaluating Net_Spinning_Reserve[Time = 1799] (dynamic) dloop = 263.
........Evaluating Net_Spinning_Reserve[Time = 1798] (dynamic) dloop = 263.
.........Evaluating Net_Spinning_Reserve[Time = 1797] (dynamic) dloop = 263.
..........Evaluating Net_Spinning_Reserve[Time = 1796] (dynamic) dloop = 263.
...........Evaluating Net_Spinning_Reserve[Time = 1795] (dynamic) dloop = 263.

the indentation continued in this fashion until there were 1800 dots of indentation on each line. In this case, the caller, Spinning_reserves_Di had an expression similar to X in the second example above, requesting Net_Spinning_Reserve for the first time at Time = 1801.