Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
is said to have first-class functions if it treats functions as first-class object
First-class object
In programming language design, a first-class citizen , in the context of a particular programming language, is an entity that can be constructed at run-time, passed as a parameter, returned from a subroutine, or assigned into a variable...
s. Specifically, this means that 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. Some authors require support for anonymous function
Anonymous function
In programming language theory, an anonymous function is a function defined, and possibly called, without being bound to an identifier. Anonymous functions are convenient to pass as an argument to a higher-order function and are ubiquitous in languages with first-class functions such as Haskell...
Christopher Strachey was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design...
in the context of “functions as first-class citizens” in the mid-1960s.
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
In mathematics and computer science, higher-order functions, functional forms, or functionals are functions which do at least one of the following:*take one or more functions as an input*output a function...
s is a standard practice. A simple example of a higher-ordered function is the map
Map (higher-order function)
In many programming languages, map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results. They are examples of both catamorphisms and anamorphisms...
or mapcar 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 and returning them as results, especially in the presence of non-local variable
Non-local variable
In programming language theory, a non-local variable is a variable that is not defined in the local scope. While the term can refer to global variables, it is primarily used in the context of nested and anonymous functions where some variables can be neither in the local nor the global scope.-...
In computer programming, a nested function is a function which is lexically encapsulated within another function. It can only be called by the enclosing function or by functions directly or indirectly nested within the same enclosing function. In other words, the scope of the nested function is...
In programming language theory, an anonymous function is a function defined, and possibly called, without being bound to an identifier. Anonymous functions are convenient to pass as an argument to a higher-order function and are ubiquitous in languages with first-class functions such as Haskell...
In computer science, the funarg problem refers to the difficulty in implementing first-class functions in stack-based programming language implementations....
s, the name coming from "function argument". In early imperative languages these problems were avoided by either not supporting functions as result types (Algol, Pascal) or omitting nested functions and thus non-local variables (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 function was introduced in Scheme and requires handling references to functions as closure
Closure (computer science)
In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
A function pointer is a type of pointer in C, C++, D, and other C-like programming languages, and Fortran 2003. When dereferenced, a function pointer can be used to invoke a function and pass it arguments just like a normal function...
In computer science, garbage collection is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program...
a necessity.
Concepts
In this section we compare how some concepts are handled in a functional language with first-class functions (Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
) compared to an imperative language where functions are second-class citizens (C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
).
Higher-order functions: passing functions as arguments
In languages where functions are first-class citizens, functions can be passed as arguments to other functions in the same way other types can (a function taking another function as argument is called a higher-order function). In the Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
programming language:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
Languages where functions are not first-class often still allow one to write higher-order functions through the use of concepts such as function pointer
Function pointer
A function pointer is a type of pointer in C, C++, D, and other C-like programming languages, and Fortran 2003. When dereferenced, a function pointer can be used to invoke a function and pass it arguments just like a normal function...
A delegate is a person who speaks or acts on behalf of an organization at a meeting or conference between organizations of the same level A delegate is a person who speaks or acts on behalf of an organization (e.g., a government, a charity, an NGO, or a trade union) at a meeting or conference...
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
programming language:
void map(int (*f)(int), int x[], size_t n) {
for (int i = 0; i < n; i++)
x[i] = (*f)(x[i]);
}
When comparing the two samples one should note that there are a number of differences between the two approaches that are not directly related to the support of first-class functions. The Haskell sample operates on lists, while the C sample operates on arrays. 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 functions needs an additional parameter (giving the size of the array.) The C function updates the array in-place, returning no value, whereas in Haskell data structures are persistent
Persistent
Persistent may refer to:* Persistent Systems, a technology company* USS Persistent, three United States Navy ships...
(a new list is returned while the old is left intact.) The Haskell sample uses recursion
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
to traverse the list, while the C sample uses iteration
Iteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
. 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 a fold and the C sample in terms of recursion. Finally, the Haskell function has a polymorphic type, as this is not supported by C we have fixed all type variables to the type constant int.
Anonymous and nested functions
In language 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:
int f(int x) {
return 3 * x + 1;
}
int main {
int l[] = {1, 2, 3, 4, 5};
map(f, l, 5);
}
Non-local variables and closures
Once we have anonymous or nested functions it becomes natural for them to refer to variables outside of their body (called non-local variables):
main = let a = 3
b = 1
in map (\x -> a * x + b) [1, 2, 3, 4, 5]
If functions are represented as bare function pointers it is no longer obvious how we should pass the value outside of the function body to it. We instead have to manually build a closure and one can at this point no longer speak of "first-class" functions.
typedef struct {
int (*f)(int, int, int);
int *a;
int *b;
} closure_t;
void map(closure_t *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_t closure = {f, &a, &b};
map(&closure, l, 5);
}
Also note that the map is now specialized to functions referring to two ints outside of their environment. This can be set up more generally, but requires more boilerplate code. If f would have been a nested function
Nested function
In computer programming, a nested function is a function which is lexically encapsulated within another function. It can only be called by the enclosing function or by functions directly or indirectly nested within the same enclosing function. In other words, the scope of the nested function is...
we would still have run into the same problem and this is the reason they are not supported in C.
Higher-order functions: returning functions as results
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 the upwards funarg problem.
In computer programming, an assignment statement sets or re-sets the value stored in the storage location denoted by a variable name. In most imperative computer programming languages, assignment statements are one of the basic statements...
functions to variables and storing them inside (global) datastructures potentially suffers from the same difficulties as returning functions.
f :: Integer] -> [Integer
f = let a = 3
b = 1
in [map (\x -> a * x + b), map (\x -> b * x + a)]
Equality of functions
As one can test most literals and values for equality, it is natural to ask of a programming language to support testing functions for equality. On further inspection this question appears more difficult and one has to distinguish between several types of function equality:
Extensional equality: Two functions f and g 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 a stable sorting algorithm, such as insertion sort
Insertion sort
Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
Merge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...
, would be considered equal. Deciding on extensional equality is undecidable
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
in general and even for functions with finite domains often infeasible. For this reason no programming language implements function equality as extensional equality.
Intensional equality: Under intensional, two functions f and g are considered equal if they have the same "internal structure". This kind of equality could be implemented in interpreted language
Interpreted language
Interpreted language is a programming language in which programs are 'indirectly' executed by an interpreter program. This can be contrasted with a compiled language which is converted into machine code and then 'directly' executed by the host CPU...
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
of the function bodies (such as in Interpreted Lisp 1.5) or the object code
Object code
Object code, or sometimes object module, is what a computer compiler produces. In a general sense object code is a sequence of statements in a computer language, usually a machine code language....
A compiled language is a programming language whose implementations are typically compilers , and not interpreters ....
s. Intensional equality implies extensional equality (under the assumption that the function do not depend on the value of the program counter
Program counter
The program counter , commonly called the instruction pointer in Intel x86 microprocessors, and sometimes called the instruction address register, or just part of the instruction sequencer in some computers, is a processor register that indicates where the computer is in its instruction sequence...
.)
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 breaks referential transparency and is therefore not supported in pure languages, such as Haskell.
In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
, the type of functions accepting values of type A and returning values of type B may be written as A → B or BA. In the Curry-Howard correspondence, function type
Function type
In computer science, a function type is the type of a variable or parameter to which a function has or can be assigned or the result type of a higher-order function returning a function....
s are related to logical implication; lambda abstraction corresponds to discharging hypothetical assumptions and function application corresponds to the modus ponens
Modus ponens
In classical logic, modus ponendo ponens or implication elimination is a valid, simple argument form. It is related to another valid form of argument, modus tollens. Both Modus Ponens and Modus Tollens can be mistakenly used when proving arguments...
inference rule. Besides the usual case of programming functions, type theory also uses first-class functions to model associative array
Associative array
In computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
accounts of programming, the availability of first-class functions corresponds to the closed category
Closed category
In category theory, a branch of mathematics, a closed category is a special kind of category.In any category , the morphisms between any two given objects x and y comprise a set, the external hom...
assumption. For instance, the simply-typed lambda calculus corresponds to the internal language of cartesian closed categories
Cartesian closed category
In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...
.
Language support
Functional programming languages, such as Scheme, ML
ML programming language
ML is a general-purpose functional programming language developed by Robin Milner and others in the early 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM...
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
Scala is a multi-paradigm programming language designed to integrate features of object-oriented programming and functional programming. The name Scala is a portmanteau of "scalable" and "language", signifying that it is designed to grow with the demands of its users...
A lisp is a speech impediment, historically also known as sigmatism. Stereotypically, people with a lisp are unable to pronounce sibilants , and replace them with interdentals , though there are actually several kinds of lisp...
, one of the earliest functional languages, was designed not all aspects of first-class function were properly understood yet, resulting in functions being dynamically scoped. The later Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
dialect, does have lexically-scoped first-class functions.
Many recent interpreted and scripting languages, include Perl
Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...
Tcl is a scripting language created by John Ousterhout. Originally "born out of frustration", according to the author, with programmers devising their own languages intended to be embedded into applications, Tcl gained acceptance on its own...
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
, Ruby, and Io have first-class functions.
For the imperative languages a distinction has to be made between the traditional Algol familiy, 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. 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.
The C family allowed both passing functions as arguments and returning them as results, but avoided any problems not supporting nested functions. 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 language 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 function 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 the non-garbage collected nature of the language and capture semantics of non-local variables still make it problematic for functions to be returned as results.
In mathematics and computer science, higher-order functions, functional forms, or functionals are functions which do at least one of the following:*take one or more functions as an input*output a function...
In programming language theory, a non-local variable is a variable that is not defined in the local scope. While the term can refer to global variables, it is primarily used in the context of nested and anonymous functions where some variables can be neither in the local nor the global scope.-...
In computer science, partial application refers to the process of fixing a number of arguments to a function, producing another function of smaller arity...
In computer programming, a nested function is a function which is lexically encapsulated within another function. It can only be called by the enclosing function or by functions directly or indirectly nested within the same enclosing function. In other words, the scope of the nested function is...
In programming language theory, an anonymous function is a function defined, and possibly called, without being bound to an identifier. Anonymous functions are convenient to pass as an argument to a higher-order function and are ubiquitous in languages with first-class functions such as Haskell...
In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
ALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...
In computer science, a function type is the type of a variable or parameter to which a function has or can be assigned or the result type of a higher-order function returning a function....
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...
Oberon is a programming language created in 1986 by Professor Niklaus Wirth and his associates at ETH Zurich in Switzerland. It was developed as part of the implementation of the Oberon operating system...
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
A function pointer is a type of pointer in C, C++, D, and other C-like programming languages, and Fortran 2003. When dereferenced, a function pointer can be used to invoke a function and pass it arguments just like a normal function...
A function pointer is a type of pointer in C, C++, D, and other C-like programming languages, and Fortran 2003. When dereferenced, a function pointer can be used to invoke a function and pass it arguments just like a normal function...
A function object, also called a functor, functional, or functionoid, is a computer programming construct allowing an object to be invoked or called as though it were an ordinary function, usually with the same syntax.-Description:...
A delegate is a form of type-safe function pointer used by the .NET Framework. Delegates specify a method to call and optionally an object to call the method on. They are used, among other things, to implement callbacks and event listeners....
A function pointer is a type of pointer in C, C++, D, and other C-like programming languages, and Fortran 2003. When dereferenced, a function pointer can be used to invoke a function and pass it arguments just like a normal function...
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
Clojure |closure]]") is a recent dialect of the Lisp programming language created by Rich Hickey. It is a general-purpose language supporting interactive development that encourages a functional programming style, and simplifies multithreaded programming....
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
Mathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...
C++: C++0x closures can capture non-local variables by copy or by reference, without extending their lifetime.
Lisp
Lexically scoped Lisp variants support closures, dynamically scoped variants do not.
In Common Lisp, the identifier of a function in the function namespace cannot be used as a first-class value. It must be converted into a value using the (function ) or #' operators. Conversely, to apply a function encapsulated in such a way as a value, one must use the (funcall ) operator instead of calling it directly.
PHP: Nested functions are created at global scope once the outer function is executed. Anonymous functions could be created using create_function but could not refer to variable in the outer scope.
Python
Python's anonymous functions can only have an expression as the body
The identifier of a regular "function" in Ruby (which is really a method) cannot be used as a value or passed. It must be 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.
In some programming languages, eval is a function which evaluates a string as though it were an expression and returns a result; in others, it executes multiple lines of code as though they had been included instead of the line including the eval...
In mathematical logic, category theory, andcomputer science, kappa calculus is aformal system for defining first-orderfunctions.Unlike lambda calculus, kappa calculus has nohigher-order functions; its functions arenot first class objects...
-- a formalism which excludes first-class functions
In computer science, partial application refers to the process of fixing a number of arguments to a function, producing another function of smaller arity...
In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
Rosetta Code is a wiki-based programming chrestomathy website with solutions to various programming problems in many different programming languages. It was created in 2007 by Mike Mol. Rosetta Code includes 450 programming tasks, and covers 351 programming languages...
