Funarg problem: Difference between revisions

Revision as of 20:31, 11 March 2013

Latest revision as of 08:02, 9 August 2025

(39 intermediate revisions by 32 users not shown)

Line 1:

{{Short description|Programming language implementation problem}}

In [[computer science]], the '''funarg problem''' ''(function argument problem)'' refers to the difficulty in implementing [[first-class function]]s ([[function (programming)|function]]s as [[first-class object]]s) in programming language implementations withso 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 viaby argument passing) to identifiers defined in the environment in which the function is defined, but not in the environment of the function call.<ref>[httphttps://portalweb.acmarchive.org/citationweb/20170706125408/ftp://publications.cfm?id=1093411ai.mit.edu/ai-publications/pdf/AIM-199.pdf ''The function of FUNCTION in LISP or why the FUNARG problem should be called the environment problem''], by Joel Moses, in:MIT ACMProject SIGSAMMAC Bulletinmemo 17AI-199, (JulyMAC-M-428, June 1970), (15 pp. 13-27]).</ref> A Tostandard summarizeresolution theis discussion below, two standard resolutions areeither to either forbid such references or to create [[closure (computer science)|closureclosures]]s.<ref>[http://portal.acm.org/citation.cfm?id=1093420.1093422 ''A proposed solution to the FUNARG problem''], by Erik Sandewall, in: ACM SIGSAM Bulletin 17 (Jan. 1971), pp. 29-42]29–42.</ref>

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==

When one function calls another during a typical program's execution, the local state of the caller (including [[parameter (computer science)|parameterparameters]]s 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 ana ''[[Call stack#Structure|activationstack recordframe]]'' or ''stackactivation framerecord''. 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 activationstack recordframe 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 [[dynamic memory allocation#Heap-based memory(data allocationstructure)|heap]] instead of the stack, and rely on some form of [[Garbage collection (computer science)|garbage collection]] or [[reference counting]] to deallocate the activation recordsthem when they are no longer needed. Managing activation records on the heap ishas muchhistorically been perceived to be less efficient than on the stack, so(although this strategyis maypartially significantlycontradicted<ref>[[Andrew degradeAppel|Andrew performanceW. MoreoverAppel]], becauseZhong mostShao. [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]. [https://www.cs.princeton.edu/research/techreps/150 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, muchadding ofto thisconcerns about potential overhead associated with their implementation. Furthermore, this approach is unnecessarygenuinely 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 (programming language)|ML]] languages take this approach, since variables in those languages are bound to values -- ivalues—i.e. variables cannot be changed. [[Java_(programming_language)|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 <code>final</code> (i.e. constant).

Some languages allow the programmer to explicitly choose between the two behaviors. [[PHP]] 5.3's anonymous functions allowrequire one to specify which variables to include in the closure using the <code>use ()</code> clause; if the variable is listed by reference, it includes a reference to the original variable; otherwise, it makespasses athe copyvalue. In Apple's [[Blocks (C language extension)|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 <code>__block</code> modifier, in which case that variable is allocated on the heap.

===Example===

The following [[Haskell (programming language)|Haskell]]-inspiredlike [[pseudocode]] defines [[Function_composition_(computer_science)|function composition]]:

{{sxhl|2=haskell|1=compose f g = λx → f (g x)}}

<code>[[Lambda calculus|λ]]</code> is the operator for constructing a new function, which -- in this case -- has one argument, <code>''x''</code>, and returns the result of first applying <code>''g''</code> to <code>''x''</code>, then applying <code>''f''</code> to that. This λ function carries the functions <code>''f''</code> and <code>''g''</code> (or pointers to them) as internal state.

The problem in this case exists if the compose function allocates the parameter variables <code>''f''</code> and <code>''g''</code> on the stack. When <code>''compose''</code> returns, the stack frame containing <code>''f''</code> and <code>''g''</code> is discarded. When the internal function <code>''λx''</code> attempts to access <code>''g''</code>, it will access a discarded memory area.

compose f g = λx → f (g x)

<code>[[Lambda calculus|λ]]</code> is the operator for constructing a new function, which -- in this case -- has one argument, <code>''x''</code>, and returns the result of first applying <code>''g''</code> to <code>''x''</code> then applying <code>''f''</code> to that. This λ function carries the functions <code>''f''</code> and <code>''g''</code> (or pointers to them) as internal state.

The problem in this case exists if the compose function allocates the parameter variables <code>''f''</code> and <code>''g''</code> on the stack. When <code>''compose''</code> returns, the stack frame containing <code>''f''</code> and <code>''g''</code> is discarded. When the internal function <code>''λx''</code> attempts to access <code>''g''</code>, it will access a discarded memory area.

==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 activationstack recordframe 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 activationstack recordsframes 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.{{clarify|date=October 2023|reason=What does running in limited stack space entail in this case? What is the faster and the slower behaviour and why would either 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]] (aprogramming descendantlanguages (descendants of Pascal) allowsallow 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 <code>[[Final (Java)|final]]</code>, and context used by [[Anonymous function#Java|lambda expressions]] be effectively final. [[C_Sharp_C Sharp (programming_languageprogramming 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|Objective Caml]] compiler employs a hybrid technique (based on [[programstatic analysis (computer science)|program analysis]]) to maximize efficiency.{{Citation needed|date=April 2011}}.

==See also==

* [[Closure (computer science)]]

*[[Activation record]]

* [[Functional programming]]

*[[Closure (computer science)]]

* [[FunctionalLambda programmingcalculus]]

* [[LambdaMan or boy calculustest]]

* [[Man or boyName testbinding]]

* [[Referential transparency]]

*[[Name binding]]

* [[Scope (programming)]]

*[[Referential transparency (computer science)|Referential transparency]]

* [[ScopeSpaghetti (programming)stack]]

*[[Spaghetti stack]]

==References==

Line 50 ⟶ 48:

==External links==

* [[Joseph Weizenbaum]]. [http://www.softwarepreservation.org/projects/LISP/MIT/Weizenbaum-FUNARG_Problem_Explained-1968.pdf "The FUNARG Problem Explained"], 1968.

*[http://www.soe.ucsc.edu/classes/cmps203/Winter11/09-lambda.ppt.pdf Bindings, Procedures, Functions, Functional Programming, and the Lambda Calculus]

* [[Joel Moses]]. [http://dspace.mit.edu/handle/1721.1/5854 "The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem"]. MIT AI Memo 199, 1970.

* [https://web.archive.org/web/20120722020445/http://wwwclasses.soe.ucsc.edu/classes/cmps203/Winter11/09-lambda.ppt.pdf Bindings, Procedures, Functions, Functional Programming, and the Lambda Calculus]

*[[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.

[[Category:Compiler construction]]