Funarg Problem - Upwards Funarg Problem

Upwards Funarg Problem

When one function calls another during a typical program's execution, the local state of the caller (including parameters and local variables) must be preserved in order for execution to proceed after the callee returns. In most compiled programs, this local state is stored on the call stack in a data structure called an activation record or stack frame. This stack frame is pushed, or allocated, when a function is called, and popped, or deallocated, when the function returns. The upwards funarg problem arises when the calling function refers to the called/exited function's state after that function has returned. Therefore, the activation record containing the called function's state variables must not be deallocated when the function returns, violating the stack-based function call paradigm.

One solution to the upwards funarg problem is to simply allocate all activation records from the heap instead of the stack, and rely on some form of garbage collection or reference counting to deallocate the activation records when they are no longer needed. Managing activation records on the heap is much less efficient than on the stack, so this strategy may significantly degrade performance. Moreover, because most functions in typical programs do not create upwards funargs, much of this overhead is unnecessary.

Some efficiency-minded compilers employ a hybrid approach in which the activation records for a function are allocated from the stack if the compiler is able to deduce, through static program analysis, that the function creates no upwards funargs. Otherwise, the activation records are allocated from the heap.

Another solution is to simply copy the value of the variables into the closure at the time the closure is created. This will cause a different behavior in the case of mutable variables, because the state will no longer be shared between closures. But if it is known that the variables are constant, then this approach will be equivalent. The ML languages take this approach since variables in those languages are bound to values -- i.e. variables cannot be changed. Java also takes this approach with respect to anonymous classes, in that it only allows one to refer to variables in the enclosing scope that are final (i.e. constant).

Some languages allow the programmer to explicitly choose between the two behaviors. PHP 5.3's anonymous functions allow one to specify variables to include in the closure using the use clause; if the variable is listed by reference, it includes a reference to the original variable; otherwise, it makes a copy. In Apple's Blocks anonymous functions, captured local variables are by default captured by value; if one wants to share the state between closures or between the closure and the outside scope, the variable must be declared with the __block modifier, in which case that variable is allocated on the heap.