First-class function: Difference between revisions

Revision as of 18:50, 7 May 2021

Revision as of 16:27, 16 June 2021

Line 2:

In [[computer science]], a [[programming language]] is said to have '''first-class functions''' if it treats [[function (programming)|function]]s as [[first-class citizen]]s. 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.<ref>{{cite book|first1=Harold|last1=Abelson|authorlink1=Harold Abelson|first2=Gerald Jay|last2=Sussman|authorlink2=Gerald Jay Sussman|title=Structure and Interpretation of Computer Programs|at=[https://archive.org/details/structureinterpr00abel/page/ Formulating Abstractions with Higher-Order Procedures]|publisher=MIT Press|year=1984|isbn=0-262-01077-1|url=http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#call_footnote_Temp_121}}</ref> Some programming language theorists require support for [[anonymous function]]s (function literals) as well.<ref name="test">[http://www.worldcat.org/oclc/222529448 Programming language pragmatics], by Michael Lee Scott, section 11.2 "Functional Programming".</ref> In languages with first-class functions, the [[name (computer science)|names]] of functions do not have any special status; they are treated like ordinary [[variable (computer science)|variable]]s with a [[function type]].<ref>{{cite journal |title=The Implementation of Lua 5.0 |author1=Roberto Ierusalimschy |author1-link=Roberto Ierusalimschy |author2=Luiz Henrique de Figueiredo |author3=Waldemar Celes |journal=Journal of Universal Computer Science |doi=10.3217/jucs-011-07-1159 |doi-access=free |volume=11 |issue=7 |date=2005 |pages=1159–1176}}</ref> The term was coined by [[Christopher Strachey]] in the context of "functions as first-class citizens" in the mid-1960s.<ref name=strachey>{{cite journal|last1=Burstall |first1=Rod |last2=Strachey |first2=Christopher |title=Understanding Programming Languages |journal=[[Higher-Order and Symbolic Computation]] |date=2000 |volume=13 |issue=52 |pages=11–49 |doi=10.1023/A:1010052305354 |url=http://www.cs.cmu.edu/~crary/819-f09/Strachey67.pdf |url-status=bot: unknown |archiveurl=https://web.archive.org/web/20100216060948/http://www.cs.cmu.edu/~crary/819-f09/Strachey67.pdf |archivedate=February 16, 2010 }} (also on 2010-02-16</ref>

First-class functions are a necessity for the [[functional programming]] style, in which the use of [[higher-order function]]s is a standard practice. A simple example of a higher-ordered function is the ''[[map (higher-order function)|map]]'' function, which takes, as its arguments, a function and aan listiterable, and returns the listiterator formed by applying the function to each member of the listiterable. 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 variable]]s introduced in [[nested function|nested]] and [[anonymous function]]s. Historically, these were termed the [[funarg problem]]s, the name coming from "function argument".<ref>[[Joel Moses]]. [https://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.</ref> In early imperative languages these problems were avoided by either not supporting functions as result types (e.g. [[ALGOL 60]], [[Pascal (programming language)|Pascal]]) or omitting nested functions and thus non-local variables (e.g. [[C (programming language)|C]]). The early functional language [[Lisp (programming 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 (programming language)|Scheme]] and requires handling references to functions as [[closure (computer science)|closure]]s instead of bare [[function pointer]]s,<ref name="strachey"/> which in turn makes [[Garbage collection (computer science)|garbage collection]] a necessity.