|
Funarg is an abbreviation for "functional argument"; in computer science, the funarg problem relates to the difficulty of implementing functions as first-class objects in stack-based programming language implementations. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
In computer science, a subroutine (function, procedure, or subprogram) is a sequence of code which performs a specific task, as part of a larger program, and is grouped as one, or more, statement blocks; such code is sometimes collected into software libraries. ...
In computing, a first-class object (also value, entity, and citizen), in the context of a particular programming language, is an entity which can be used in programs without restriction (when compared to other kinds of objects in the same language). ...
A stack-oriented programming language is one that relies on a stack machine model for passing parameters. ...
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 outer function (including parameters and local variables) must be preserved in order for execution to proceed after the inner function returns. In most compiled programs, this local state is stored on the call stack in a data structure called an activation record or stack frame. This stack frame is pushed, or allocated, when a function is called, and popped, or deallocated, when the function returns. The upwards funarg problem arises when the calling function refers to the called/exited function's state after that function has returned. Therefore, the activation record containing the called function's state variables must not be deallocated when the function returns, violating the stack-based function call paradigm. A parameter is a variable which can be accepted by a subroutine. ...
In computer science, a local variable is a variable that is given local scope. ...
In computer science, a call stack is a special stack which stores information about the active subroutines of a computer program. ...
In computer science, a call stack is a special stack which stores information about the active subroutines of a computer program. ...
To meet Wikipedias quality standards, this article or section may require cleanup. ...
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 the activation records when they are no longer needed. Managing activation records on the heap is much less efficient than on the stack, so this strategy may significantly degrade performance. Moreover, because most functions in typical programs do not create upwards funargs, much of this overhead is unnecessary. In computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program. ...
In computer science, garbage collection (GC) is a form of automatic memory management. ...
In computer science, reference counting is a technique of storing the number of references, pointers, or handles to a resource such as an object or block of memory. ...
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. Static code analysis is a set of methods for analysing software source code or object code in an effort to gain understanding of what the software does and establish certain correctness criteria. ...
Example The following Haskell-inspired pseudocode defines function composition: Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ...
Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...
In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ...
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. Look up Λ, λ in Wiktionary, the free dictionary. ...
The problem in this case exists if the compose function had allocated the parameter variables f and g on the stack. When compose returns, the stack frame containing f and g is discarded. When the internal function λx attempts to access g, 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 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. In computer science, a closure is a function that is evaluated in an environment containing one or more bound variables. ...
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. In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function is a recursive call. ...
Continuation passing style (CPS) is a term used within functional programming to describe a style of programming wherein functions never return. ...
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 Oberon programming language (a descendant of Pascal) allows functions both as parameters and return values but the assigned function may not be a nested function. 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. The Java programming language deals with it by requiring that context used by nested functions in anonymous inner classes be declared final. Pascal is an imperative computer programming language, developed in 1970 by Niklaus Wirth as a language particularly suitable for structured programming. ...
Oberon is a reflective programming language created in the late 1980s by Professor Niklaus Wirth (creator of the Pascal, Modula, and Modula-2 programming languages) and his associates at ETHZ in Switzerland. ...
C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...
Java is an object-oriented programming language developed by James Gosling and colleagues at Sun Microsystems in the early 1990s. ...
In the Java programming language, the final keyword is used in several different contexts to define an entity which cannot later be changed. ...
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. Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ...
Scheme is a multi-paradigm programming language. ...
SML (Standard ML) is a general-purpose, modular, functional programming language with compile-time type checking and type inference. ...
In computer science, dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program. ...
Objective Caml (OCaml) is a general-purpose programming language descended from the ML family, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996. ...
Computer program analysis is the process of automatically analysing the behavior of computer programs. ...
See also In computing, a stack frame is a data structure used to create temporary storage for data and saved state in functions. ...
In computer science, a closure is a function that is evaluated in an environment containing one or more bound variables. ...
Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
In programming languages, name binding refers to the association of values with identifiers. ...
Referential transparency is a property of parts of computer programs. ...
In computer programming, scope is an enclosing context where values and expressions are associated. ...
A spaghetti stack is in fact an N-ary tree data structure in which child nodes have pointers to the parent nodes. ...
External links - Joel Moses. The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem. MIT AI Memo 199, 1970.
|
Feeds |
Contact