Funarg problem

In computer science, the funarg problem refers to the difficulty in implementing first-class functions (functions as first-class objects) in stack-based programming language implementations.

The difficulty only arises if the body of a nested function refers directly (i.e., not via argument passing) to identifiers defined in the environment in which the function is defined, but not in the environment of the function call.^[1] To summarize the discussion below, two standard resolutions are to either forbid such references or to create closures.^[2]

There are two subtly different versions of the funarg problem. The upwards funarg problem arises from returning (or otherwise transmitting "upwards") a function from a function call. The downwards funarg problem arises from passing a function as a parameter to another function call.

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 you to explicitly choose between the two behaviors. PHP 5.3's anonymous functions allow you 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, the upwards funarg problem is solved by requiring one to use Block_copy() when returning the block to a higher context, and Block_copy() copies normal variables from the stack into a separate copy in the closure; if one wants to share the state between closures, the variable must be declared with the __block modifier, in which case that variable is allocated on the heap.

Example

The following Haskell-inspired pseudocode defines function composition:

compose f g = λx → f (g x)

λ is the operator for constructing a new function, which -- in this case -- has one argument, x, and returns the result of first applying g to x then applying f to that. This λ function carries the functions f and g (or pointers to them) as internal state.

The problem in this case exists if the compose function allocates the parameter variables f and g on the stack. When compose returns, the stack frame containing f and g is discarded. When the internal function λx attempts to access g, it will access a discarded memory area.

Downwards funarg problem

A downwards funarg may also refer to a function's state when that function is not actually executing. However, because, by definition, the existence of a downwards funarg is contained in the execution of the function that creates it, the activation record for the function can usually still be stored on the stack. Nonetheless, the existence of downwards funargs implies a tree structure of closures and activation records that can complicate human and machine reasoning about the program state.

The downwards funarg problem complicates the efficient compilation of tail recursion and code written in continuation-passing style. In these special cases, the intent of the programmer is (usually) that the function run in limited stack space, so the "faster" behavior may actually be undesirable.

Practical implications

Historically, the upwards funarg problem has proven to be the more difficult. For example, the Pascal programming language allows functions to be passed as arguments but not returned as results; thus implementations of Pascal are required to address the downwards funarg problem but not the upwards one. The Oberon programming language (a descendant of Pascal) allows functions both as parameters and return values but the assigned function may not be a nested function. The C programming language historically avoids the main difficulty of the funarg problem by not allowing function definitions to be nested; because the environment of every function is the same, containing just the statically-allocated global variables and functions, a pointer to a function's code describes the function completely. Apple has proposed and implemented a closure syntax for C that solves the upwards funarg problem by dynamically moving closures from the stack to the heap as necessary. The Java programming language deals with it by requiring that context used by nested functions in anonymous inner classes be declared final.

In functional languages, functions are first-class values and can be passed anywhere. Thus, implementations of Scheme or SML must address both the upwards and downwards funarg problems. This is usually accomplished by representing function values as heap-allocated closures, as previously described. The Objective Caml compiler employs a hybrid technique (based on program analysis) to maximize efficiency^{[citation needed]}.

See also

• Activation record
• Closure (computer science)
• Functional programming
• Lambda calculus
• Name binding
• Referential transparency
• Scope (programming)
• Spaghetti stack

References

1. ^ The function of FUNCTION in LISP or why the FUNARG problem should be called the environment problem, by Joel Moses, in: ACM SIGSAM Bulletin 17 (July 1970), pp. 13-27
2. ^ A proposed solution to the FUNARG problem, by Erik Sandewall, in: ACM SIGSAM Bulletin 17 (Jan. 1971), pp. 29-42

External links

• Bindings, Procedures, Functions, Functional Programming, and the Lambda Calculus
• Joel Moses. "The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem". MIT AI Memo 199, 1970.
• Andrew W. Appel, Zhong Shao. An Empirical and Analytic Study of Stack vs. Heap Cost for Languages with Closures. Princeton CS Tech Report TR-450-94, 1994.