Explore Black History

In computer science, the funarg problem (function argument problem) refers to the difficulty in implementing first-class functions (functions as first-class objects) in programming language implementations so as to use stack-based memory allocation of the functions.

The difficulty only arises if the body of a nested function refers directly (i.e., not by argument passing) to identifiers defined in the environment in which the function is defined, but not in the environment of the function call.^[1] A standard resolution is either to 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.

When one function A calls another function B during a typical program's execution, the local state of B (including parameters and local variables) must be stored somewhere. In a leaf function, this can be stored in registers, but if B calls another function C which itself uses those registers, they must be preserved somewhere in memory so B can proceed after C returns.

In most compiled programs, this local state is stored on the call stack in a data structure called a stack frame or activation record. This stack frame is pushed, or allocated, before B calls C, and is popped, or deallocated, just before B returns. The upwards funarg problem arises when the return value of B is itself a function F which refers to B's state (say, some local variable V) after B has returned. A may call F, which needs V to still be allocated. Therefore, the stack frame containing B's state variables must not be deallocated when B 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 them when they are no longer needed. Managing activation records on the heap has historically been perceived to be less efficient than on the stack (although this is partially contradicted^[3]) and has been perceived to impose significant implementation complexity. Most functions in typical programs (less so for programs in functional programming languages) do not create upwards funargs, adding to concerns about potential overhead associated with their implementation. Furthermore, this approach is genuinely difficult in languages that do not support garbage collection.

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 (and lambdas since Java 8), in that it only allows one to refer to variables in the enclosing scope that are effectively final (i.e. constant).

Some languages allow the programmer to explicitly choose between the two behaviors. PHP 5.3's anonymous functions require one to specify which 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 passes the value. 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.

The following Haskell-like 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.

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 stack frame for the function can usually still be stored on the stack. Nonetheless, the existence of downwards funargs implies a tree structure of closures and stack frames that can complicate human and machine reasoning about the program state.

Downwards funargs must also be compatible with the upwards funarg implementation. For example, consider A calling B, which computes a function value F referring to some local variable V of B. B then passes F as a parameter to function C, which calls F (downwards funarg) before returning. B then uses the local variable V, and finally returns F to A, which also calls F (upwards funarg). B and both calls to F must all share the same local variable V.

The downwards funarg problem complicates the efficient compilation of tail calls. Normally, if the last action by B before returning to A is to call a function C (and return C's return value to A, unmodified), then B may deallocate its stack frame before calling C, leaving the stack is if A had called C directly. Some languages promise that recursive tail calls may be performed an unlimited number of times in a fixed, limited, amount of stack space. If, however, B passes a function F to C, and F refers to a local variable V of B, then B's stack frame (or at least the variable V) must be preserved until C returns.

The same problem occurs with code written in continuation-passing style, where functions do not return, but instead terminate by passing their return values to (non-returning) continuation functions. Such calls must be implemented as tail calls to prevent an unlimited memory leak. This turns an upwards funarg situation (B returns F) into a downwards funarg (B passes F to the continuation function), and again B's stack frame muct be preserved as long as F might be called.

Historically, the upwards funarg problem has proven to be 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 Modula-2 and Oberon programming languages (descendants of Pascal) allow 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.^{[citation needed]} The Java programming language deals with it by requiring that context used by nested functions in anonymous inner and local classes be declared final, and context used by lambda expressions be effectively final. C# and D have lambdas (closures) that encapsulate a function pointer and related variables.

In functional languages, functions are first-class values that can be passed anywhere. Thus, implementations of Scheme or Standard ML 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 OCaml compiler employs a hybrid technique (based on static program analysis) to maximize efficiency.^{[citation needed]}

• Closure (computer science)
• Functional programming
• Lambda calculus
• Man or boy test
• Name binding
• Referential transparency
• Scope (programming)
• Spaghetti stack

• Joseph Weizenbaum. "The FUNARG Problem Explained", 1968.
• Joel Moses. "The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem". MIT AI Memo 199, 1970.
• Bindings, Procedures, Functions, Functional Programming, and the Lambda Calculus