Incomputer science, aprogramming language is said to havefirst-class functions if it treatsfunctions asfirst-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 foranonymous functions (function literals) as well.^[2] In languages with first-class functions, thenames of functions do not have any special status; they are treated like ordinaryvariables with afunction type.^[3] The term was coined byChristopher Strachey in the context of "functions as first-class citizens" in the mid-1960s.^[4]

First-class functions are a necessity for thefunctional programming style, in which the use ofhigher-order functions is a standard practice. A simple example of a higher-ordered function is themap 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 supportmap, 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 ofnon-local variables introduced innested andanonymous functions. Historically, these were termed thefunarg problems, the name coming fromfunction 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 languageLisp took the approach ofdynamic 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 forlexically scoped first-class functions was introduced inScheme and requires handling references to functions asclosures instead of barefunction pointers,^[4] which in turn makesgarbage collection a necessity.^{[citation needed]}

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).

In languages where functions are first-class citizens, functions can be passed as arguments to other functions in the same way as other values (a function taking another function as argument is called a higher-order function). In the languageHaskell:

map::(a->b)->[a]->[b]mapf[]=[]mapf(x:xs)=fx:mapfxs

Languages where functions are not first-class often still allow one to write higher-order functions through the use of features such asfunction pointers ordelegates. In the languageC:

voidmap(int(*f)(int),intx[],size_tn){for(inti=0;i<n;++i){x[i]=f(x[i]);}}

There are a number of differences between the two approaches that arenot directly related to the support of first-class functions. The Haskell sample operates onlists, while the C sample operates onarrays. Both are the most natural compound data structures in the respective languages and making the C sample operate on linked lists would have made it unnecessarily complex. This also accounts for the fact that the C function needs an additional parameter (giving the size of the array.) The C function updates the arrayin-place, returning no value, whereas in Haskell data structures arepersistent (a new list is returned while the old is left intact.) The Haskell sample usesrecursion to traverse the list, while the C sample usesiteration. Again, this is the most natural way to express this function in both languages, but the Haskell sample could easily have been expressed in terms of afold and the C sample in terms of recursion. Finally, the Haskell function has apolymorphic type, as this is not supported by C we have fixed all type variables to the type constantint.

In languages supporting anonymous functions, we can pass such a function as an argument to a higher-order function:

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

In a language which does not support anonymous functions, we have to bind it to a name instead:

intf(intx){return3*x+1;}intmain(){intlist[]={1,2,3,4,5};map(f,list,5);}

Once we have anonymous or nested functions, it becomes natural for them to refer to variables outside of their body (callednon-local variables):

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

If functions are represented with bare function pointers, we can not know anymore how the value that is outside of the function's body should be passed to it, and because of that a closure needs to be built manually. Therefore we can not speak of "first-class" functions here.

typedefstruct{int(*f)(int,int,int);inta;intb;}Closure;voidmap(Closure*closure,intx[],size_tn){for(inti=0;i<n;++i){x[i]=(closure->f)(closure->a,closure->b,x[i]);}}intf(inta,intb,intx){returna*x+b;}voidmain(){intl[]={1,2,3,4,5};inta=3;intb=1;Closureclosure={f,a,b};map(&closure,l,5);}

Also note that themap is now specialized to functions referring to twoints outside of their environment. This can be set up more generally, but requires moreboilerplate code. Iff would have been anested function we would still have run into the same problem and this is the reason they are not supported in C.^[6]

When returning a function, we are in fact returning its closure. In the C example any local variables captured by the closure will go out of scope once we return from the function that builds the closure. Forcing the closure at a later point will result in undefined behaviour, possibly corrupting the stack. This is known as theupwards funarg problem.

Assigning functions tovariables and storing them inside (global) data structures potentially suffers from the same difficulties as returning functions.

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

As one can test most literals and values for equality, it is natural to ask whether a programming language can support testing functions for equality. On further inspection, this question appears more difficult and one has to distinguish between several types of function equality:^[7]

Extensional equality

Two functionsf andg are considered extensionally equal if they agree on their outputs for all inputs (∀x.f(x) =g(x)). Under this definition of equality, for example, any two implementations of astable sorting algorithm, such asinsertion sort andmerge sort, would be considered equal. Deciding on extensional equality isundecidable in general and even for functions with finite domains often intractable. For this reason no programming language implements function equality as extensional equality.

Intensional equality

Under intensional equality, two functionsf andg are considered equal if they have the same "internal structure". This kind of equality could be implemented ininterpreted languages by comparing thesource code of the function bodies (such as in Interpreted Lisp 1.5) or theobject code incompiled languages. Intensional equality implies extensional equality (assuming the functions are deterministic and have no hidden inputs, such as theprogram counter or a mutableglobal variable.)

Reference equality

Given the impracticality of implementing extensional and intensional equality, most languages supporting testing functions for equality use reference equality. All functions or closures are assigned a unique identifier (usually the address of the function body or the closure) and equality is decided based on equality of the identifier. Two separately defined, but otherwise identical function definitions will be considered unequal. Referential equality implies intensional and extensional equality. Referential equality breaksreferential transparency and is therefore not supported inpure languages, such as Haskell.

Intype theory, the type of functions accepting values of typeA and returning values of typeB may be written asA →B orB^A. In theCurry–Howard correspondence,function types are related tological implication; lambda abstraction corresponds to discharging hypothetical assumptions and function application corresponds to themodus ponens inference rule. Besides the usual case of programming functions, type theory also uses first-class functions to modelassociative arrays and similardata structures.

Incategory-theoretical accounts of programming, the availability of first-class functions corresponds to theclosed category assumption. For instance, thesimply typed lambda calculus corresponds to the internal language ofCartesian closed categories.

Functional programming languages, such asErlang,Scheme,ML,Haskell,F#, andScala, all have first-class functions. WhenLisp, 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 laterScheme andCommon Lisp dialects do have lexically scoped first-class functions.

Many scripting languages, includingPerl,Python,PHP,Lua,Tcl/Tk,JavaScript andIo, 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 bymove 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 (seedangling 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'sfunction types are represented as Classes. Anonymous functions take the type inferred from the context. Method references are limited. For more details, seeAnonymous 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]

InCommon Lisp, the identifier of a function in the function namespace cannot be used as a reference to a first-class value. The special operatorfunction 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 thefuncall function:(funcall #'foo bar baz).

Python

Explicit partial application withfunctools.partial since version 2.5, andoperator.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 aMethod orProc 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[1].

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

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

• First-class functions onRosetta Code.
• Higher order functionsArchived November 12, 2019, at theWayback Machine at IBM developerWorks

• Compiler construction
• Data types
• Functional programming
• Primitive types
• Programming language theory
• Subroutines

• CS1 maint: bot: original URL status unknown
• Webarchive template wayback links
• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from April 2025
• Articles with example C code
• Articles with example Haskell code