Content deleted Content added
MichaelMaggs (talk | contribs) Adding local short description: "Programming language implementation problem", overriding Wikidata description "compiler construction difficulty in supporting first-class functions that capture variables without dynamic memory allocation" |
m Replace FTP link to PostScrpt file with link to page for that report, and add link to PDF containing report contents |
||
Line 9:
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. [https://www.cambridge.org/core/services/aop-cambridge-core/content/view/30303C7D7A9ACCC12AAA130855B7E6CF/S095679680000157Xa.pdf/empirical_and_analytic_study_of_stack_versus_heap_cost_for_languages_with_closures.pdf An Empirical and Analytic Study of Stack vs. Heap Cost for Languages with Closures]. [
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.
| |||