Funarg problem: Difference between revisions

Revision as of 16:36, 20 May 2021

Revision as of 11:13, 29 May 2021

Line 8:

When one function calls another during a typical program's execution, the local state of the caller (including [[parameter (computer science)|parameters]] and [[local variable]]s) 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 a ''[[Call stack#Structure|stack frame]]'' or ''activation record''. This stack frame is pushed, or allocated, as prelude to calling another function, and is popped, or deallocated, when the other function returns to the function that did the call. The upwards funarg problem arises when the calling function refers to the called/exited function's state after that function has returned. Therefore, the stack frame containing the called function's state variables must not be deallocated when the function returns, violating the [[stack-based memory allocation|stack-based function call paradigm]].

One solution to the upwards funarg problem is to simply allocate all activation records from the [[Heap (data structure)|heap]] instead of the stack and rely on some form of [[Garbage collection (computer science)|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<ref>[[Andrew Appel|Andrew W. Appel]], Zhong Shao. An Empirical and Analytic Study of Stack vs. Heap Cost for Languages with Closures. [ftp://ftp.cs.princeton.edu/techreports/1994/450.ps.gz Princeton CS Tech Report TR-450-94], 1994.</ref>) 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.

Line 24:

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

The downwards funarg problem complicates the efficient compilation of [[tail recursioncall]]s 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 [[Modula-2]] and [[Oberon (programming language)|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)|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, Inc.|Apple]] has proposed and implemented a [[Blocks (C language extension)|closure syntax for C]] that solves the upwards funarg problem by dynamically moving closures from the stack to the heap as necessary.{{citation needed|date=November 2012}} The [[Java programming language]] deals with it by requiring that context used by nested functions in anonymous inner and local classes be declared [[Final (Java)|final]], and context used by [[Anonymous function#Java|lambda expressions]] be effectively final. [[C Sharp (programming language)|C#]] and [[D (programming language)|D]] have lambdas (closures) that encapsulate a function pointer and related variables.

In [[functional language]]s, functions are first-class values andthat can be passed anywhere. Thus, implementations of [[Scheme (programming language)|Scheme]] or [[SMLStandard programming language|SMLML]] must address both the upwards and downwards funarg problems. This is usually accomplished by representing function values as [[Dynamic memory allocation|heap-allocated]] closures, as previously described. The [[OCaml]] compiler employs a hybrid technique (based on [[program analysis (computer science)|program analysis]]) to maximize efficiency.{{Citation needed|date=April 2011}}

==See also==