Funarg is an abbreviation for "functional argument"; in computer science, the funarg problem relates to the difficulty of implementing functions as first-class citizen objects in stack-based programming language implementations.
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
In most compiled programs, the local state of a function call, including its parameters and local variables, are stored in a data structure allocated from the stack. This activation record (in this case called a stack frame) is "pushed" when the function is called, and "popped", or deallocated, when the function returns. The upwards funarg problem arises because the funarg may refer to the local state of the function after that function has returned. Therefore, the activation record 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 them when they are no longer needed. Managing activation records on the heap is much less efficient versus a stack, and so this approach may have undesirable performance implications. Moreover, because most functions in typical programs do not create upwards funargs, much of this overhead is unnecessary.
Some compilers for efficiency-minded functional languages employ a hybrid approach in which the activation records for a function are allocated from the stack if the compiler is able to prove, through static program analysis, that the function creates no upwards funargs. Otherwise, the activation records are allocated from the heap.
Example
The following Haskell-inspired pseudocode defines function composition:
compose( f , g ) = λx → f( g( x ) )
The λ is the operator for constructing a new function, in this case of one argument x, which returns the result of first applying g to x, then applying f to the result. This function carries the functions f and g (or pointers to them) as internal state.
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 C programming language 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.
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.
See also
- activation record
- spaghetti stack
- closure
- shallow v. deep name binding
- referential transparency
- static (or lexical) v. dynamic scope
- functional programming
- lambda calculus
- stack-oriented programming language
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.