Funarg problem
|
|
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 is the problem of passing a function as a value returned "upwards" from a function call
- The downwards funarg problem is the problem of passing a function value as a parameter "down" into another function call
In both of these cases, the problem relates to correctly passing the function's environment together with the function's code. If this is done correctly, passing the resulting closure (that is to say, the code and environment together) as a value, instead of merely the code, completely solves the funarg problem. The fact that most older computer languages have used stack-based data structures to implement variable bindings has been the cause of most problems with implementing closures properly.
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 modern 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. Closure-based techniques have proven successful for imperative languages that allow function values as well. In fact, aside from some questions about performance, most language designers do not consider functional arguments a "problem" anymore.
See also
- activation record
- spaghetti stack
- closure
- shallow binding
- deep binding
- referential transparency
- dynamic scoping
- static scoping
- lexical scoping
- functional programming
- lambda calculus
- stack-oriented programming language
External link
- Bindings, Procedures, Functions, Functional Programming, and the Lambda Calculus (http://www.cse.ucsc.edu/~abadi/CS203_S04/l6.pdf)
- Joel Moses. The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem. MIT AI Memo 199 (https://dspace.mit.edu/handle/1721.1/5854), 1970.