First-class function

In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures.^[1] Some programming language theorists require support for anonymous functions (function literals) as well.^[2] In languages with first-class functions, the names of functions do not have any special status; they are treated like ordinary variables with a function type.^[3] The term was coined by Christopher Strachey in the context of "functions as first-class citizens" in the mid-1960s.^[4]

First-class functions are a necessity for the functional programming style, in which the use of higher-order functions is a standard practice. A simple example of a higher-ordered function is the map function, which takes, as its arguments, a function and a list, and returns the list formed by applying the function to each member of the list. For a language to support map, it must support passing a function as an argument.

There are certain implementation difficulties in passing functions as arguments or returning them as results, especially in the presence of non-local variables introduced in nested and anonymous functions. Historically, these were termed the funarg problems, the name coming from function argument.^[5] In early imperative languages these problems were avoided by either not supporting functions as result types (e.g. ALGOL 60, Pascal) or omitting nested functions and thus non-local variables (e.g. C). The early functional language Lisp took the approach of dynamic scoping, where non-local variables refer to the closest definition of that variable at the point where the function is executed, instead of where it was defined. Proper support for lexically scoped first-class functions was introduced in Scheme and requires handling references to functions as closures instead of bare function pointers,^[4] which in turn makes garbage collection a necessity.^{[citation needed]}

Concepts

In this section, we compare how particular programming idioms are handled in a functional language with first-class functions (Haskell) compared to an imperative language where functions are second-class citizens (C).

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

void map(int (*f)(int), int x[], size_t n) {
    for (int i = 0; i < n; ++i) {
        x[i] = f(x[i]);
    }
}

main = map (\x -> 3 * x + 1) [1, 2, 3, 4, 5]

int f(int x) {
    return 3 * x + 1;
}

int main() {
    int list[] = {1, 2, 3, 4, 5};
    map(f, list, 5);
}

main = let a = 3
           b = 1
        in map (\x -> a * x + b) [1, 2, 3, 4, 5]

typedef struct {
    int (*f)(int, int, int);
    int a;
    int b;
} Closure;

void map(Closure* closure, int x[], size_t n) {
    for (int i = 0; i < n; ++i) {
        x[i] = (closure->f)(closure->a, closure->b, x[i]);
    }
}

int f(int a, int b, int x) {
    return a * x + b;
}

void main() {
    int l[] = {1, 2, 3, 4, 5};
    int a = 3;
    int b = 1;
    Closure closure = {f, a, b};
    map(&closure, l, 5);
}

f :: [[Integer] -> [Integer]]
f = let a = 3
        b = 1
     in [map (\x -> a * x + b), map (\x -> b * x + a)]

Type theory

In type theory, the type of functions accepting values of type A and returning values of type B may be written as A → B or B^A. In the Curry–Howard correspondence, function types are related to logical implication; lambda abstraction corresponds to discharging hypothetical assumptions and function application corresponds to the modus ponens inference rule. Besides the usual case of programming functions, type theory also uses first-class functions to model associative arrays and similar data structures.

In category-theoretical accounts of programming, the availability of first-class functions corresponds to the closed category assumption. For instance, the simply typed lambda calculus corresponds to the internal language of Cartesian closed categories.

Language support

Functional programming languages, such as Erlang, Scheme, ML, Haskell, F#, and Scala, all have first-class functions. When Lisp, one of the earliest functional languages, was designed, not all aspects of first-class functions were then properly understood, resulting in functions being dynamically scoped. The later Scheme and Common Lisp dialects do have lexically scoped first-class functions.

Many scripting languages, including Perl, Python, PHP, Lua, Tcl/Tk, JavaScript and Io, have first-class functions.

For imperative languages, a distinction has to be made between Algol and its descendants such as Pascal, the traditional C family, and the modern garbage-collected variants. The Algol family has allowed nested functions and higher-order taking function as arguments, but not higher-order functions that return functions as results (except Algol 68, which allows this). The reason for this was that it was not known how to deal with non-local variables if a nested-function was returned as a result (and Algol 68 produces runtime errors in such cases).

The C family allowed both passing functions as arguments and returning them as results, but avoided any problems by not supporting nested functions. (The gcc compiler allows them as an extension.) As the usefulness of returning functions primarily lies in the ability to return nested functions that have captured non-local variables, instead of top-level functions, these languages are generally not considered to have first-class functions.

Modern imperative languages often support garbage-collection making the implementation of first-class functions feasible. First-class functions have often only been supported in later revisions of the language, including C# 2.0 and Apple's Blocks extension to C, C++, and Objective-C. C++11 has added support for anonymous functions and closures to the language, but because of the non-garbage collected nature of the language, special care has to be taken for non-local variables in functions to be returned as results (see below).

C++

C++11 closures can capture non-local variables by copy construction, by reference (without extending their lifetime), or by move construction (the variable lives as long as the closure does). The first option is safe if the closure is returned but requires a copy and cannot be used to modify the original variable (which might not exist any more at the time the closure is called). The second option potentially avoids an expensive copy and allows to modify the original variable but is unsafe in case the closure is returned (see dangling references). The third option is safe if the closure is returned and does not require a copy but cannot be used to modify the original variable either.

Java

Java 8 closures can only capture final or "effectively final" non-local variables. Java's function types are represented as Classes. Anonymous functions take the type inferred from the context. Method references are limited. For more details, see Anonymous function § Java limitations.

Lisp

Lexically scoped Lisp variants support closures. Dynamically scoped variants do not support closures or need a special construct to create closures.^[22]

In Common Lisp, the identifier of a function in the function namespace cannot be used as a reference to a first-class value. The special operator function must be used to retrieve the function as a value: (function foo) evaluates to a function object. #'foo exists as a shorthand notation. To apply such a function object, one must use the funcall function: (funcall #'foo bar baz).

Python

Explicit partial application with functools.partial since version 2.5, and operator.methodcaller since version 2.6.

Ruby

The identifier of a regular "function" in Ruby (which is really a method) cannot be used as a value or passed. It must first be retrieved into a Method or Proc object to be used as first-class data. The syntax for calling such a function object differs from calling regular methods.

Nested method definitions do not actually nest the scope.

Explicit currying with .

See also

• Defunctionalization
• eval
• First-class message
• Kappa calculus – a formalism which excludes first-class functions
• Man or boy test
• Partial application

Notes

References

• Leonidas Fegaras. "Functional Languages and Higher-Order Functions". CSE5317/CSE4305: Design and Construction of Compilers. University of Texas at Arlington.

External links

• First-class functions on Rosetta Code.
• Higher order functions Archived November 12, 2019, at the Wayback Machine at IBM developerWorks