First-class function: Difference between revisions

Revision as of 21:05, 2 September 2020

Latest revision as of 00:14, 24 August 2025

(46 intermediate revisions by 42 users not shown)

Line 1:

{{Short description|Programming language feature}}

In [[], a [[]] if it treats [[]]s as [[]]s. This means the language supports passing functions as arguments to other functions, returning them as the values from other functions, functions are a necessity for the [[]] style, in which the use [[]]s is a standard practice. A simple examplea higher-ordered function is the ''[[]]'' function, which takes, as its arguments, a function and a list, and returns the list formed by applying the function to each memberthe list. For a language to supportmap it must support passing a function as an argument.

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=https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3|access-date=2021-09-27|archive-date=2021-09-21|archive-url=https://web.archive.org/web/20210921155625/https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3|url-status=dead}}</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 |s2cid=1989590 |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>

There are certain implementation difficulties in passing functions as ]]s introduced in []] and anonymous The Function or wh problem Should be Called the Environment proble MIT AI Memo 199, 1970.<ref> In early imperative languages these problems were avoided by either not supporting functions functionswhich in turn makes [[]] a necessity.

In [[], a [[]] if it treats [[]]s as [[]]s. This means the language supports passing functions as arguments to other functions, returning them as the values from other functions,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 exampleaexample of a higher-ordered function is the ''[[map (higher-order function)|map]]'' function, which takes, as its arguments, a function and a list, and returns the list formed by applying the function to each memberthemember of the list. For a language to supportmapsupport ''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.{{Citation needed|reason=Rust does it without GC|date=April 2025}}

== Concepts ==

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

=== Higher-order functions: passing functions as arguments ===

Line 23 ⟶ 27:

</syntaxhighlight>

Between the two samples, thereThere 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 [[List (computing)|list]]s, while the C sample operates on [[Array data structure|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 function 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 data structure|persistent]] (a new list is returned while the old is left intact.) The Haskell sample uses [[recursion]] to traverse the list, while the C sample uses [[iteration]]. 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 (higher-order function)|fold]] and the C sample in terms of recursion. Finally, the Haskell function has a [[Polymorphism (computer science)|polymorphic]] type, as this is not supported by C we have fixed all type variables to the type constant <code>int</code>.

=== Anonymous and nested functions ===

Line 59 ⟶ 63:

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]);

}

Line 76 ⟶ 80:

int a = 3;

int b = 1;

closure_t closure = {f, &a, &b};

map(&closure, l, 5);

}

Line 87 ⟶ 91:

=== Assigning functions to variables ===

[[Assignment (computer science)|Assigning]] functions to [[variable (computer science)|variables]] and storing them inside (global) datastructuresdata structures potentially suffers from the same difficulties as returning functions.

<syntaxhighlight lang="haskell">

f :: [[Integer] -> [Integer]]

Line 96 ⟶ 100:

=== Equality of functions ===

{{further information|Function equality}}

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:<ref>[[Andrew W. Appel]] (1995). [http://www.cs.princeton.edu/~appel/papers/conteq.pdf "Intensional Equality ;=) for Continuations"].</ref>

Line 104 ⟶ 107:

; [[Intensional equality]]: Under intensional equality, 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]]s by comparing the [[source code]] of the function bodies (such as in Interpreted Lisp 1.5) or the [[object code]] in [[compiled language]]s. Intensional equality implies extensional equality (assuming the functions are deterministic and have no hidden inputs, such as the [[program counter]] or a mutable [[global 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 breaks [[referential transparency]] and is therefore not supported in [[purityPure (computer science)function|pure]] languages, such as Haskell.

== Type theory ==

Line 113 ⟶ 116:

== Language support ==

Functional programming languages, such as [[Erlang (programming language)|Erlang]], [[Scheme (programming language)|Scheme]], [[ML (programming language)|ML]], [[Haskell (programming language)|Haskell]], [[F Sharp (programming language)|F#]], and [[Scala (programming language)|Scala]], all have first-class functions. When [[Lisp (programming language)|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 (programming language)|Scheme]] and [[Common Lisp]] dialects do have lexically scoped first-class functions.

Many scripting languages, including [[Perl]], [[Python (programming language)|Python]], [[PHP]], [[Lua (programming language)|Lua]], [[Tcl]]/Tk, [[JavaScript]] and [[Io (programming language)|Io]], have first-class functions.

Line 121 ⟶ 124:

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

{| class=wikitable width=100% style="font-size: 85%"

Line 131 ⟶ 134:

| [[ALGOL 60]] || {{yes}} || {{no}} || {{yes}} || {{no}} || {{partial|Downwards}} || {{no}} || rowspan=6 | Have [[function type]]s.

|-

| [[ALGOL 68]] || {{yes}} || {{Partial|Yes}}<ref name=compa68pascal>{{cite journal|page=319|title=A comparison of PASCAL and Algol 68|journal=The Computer Journal|volume=21|number=4|year=1977|first=A.S.|last=Tanenbaum|urldoi=http:/10.1093/comjnl.oxfordjournals.org/content/21/.4/316.full.pdf316|doi-access=10.1093free|url=https:/comjnl/21research.4vu.316nl/files/110789276/11054}}</ref> || {{yes}} || {{yes}} || {{partial|Downwards}}<ref>{{Cite web|url=http://python-history.blogspot.nl/2009/04/origins-of-pythons-functional-features.html?showComment=1243166621952#c702829329923892023|title = The History of Python: Origins of Python's "Functional" Features|date = 21 April 2009}}</ref> || {{no}}

|-

| [[Pascal (programming language)|Pascal]] || {{yes}} || {{no}} || {{yes}} || {{no}} || {{partial|Downwards}} || {{no}}

Line 142 ⟶ 145:

|-

| rowspan=9 | C family

| [[C (programming language)|C]] || {{yes}} || {{yes}} || {{noPartial|Yes in GNU C}} || {{noPartial|Yes in Clang([[Blocks (C language extension)|Blocks]])}} || {{noPartial|Yes in Clang([[Blocks (C language extension)|Blocks]])}} || {{no}} || Has [[function pointer]]s.

|-

| [[C++]] || {{yes}} || {{yes}} || {{yes|C++11<ref>[https://stackoverflow.com/a/4324829 Nested functions using lambdas/closures]</ref>}} || {{yes|C++11}}<ref name=doc1968>Doc No. [http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1968.pdf 1968]: V Samko; J Willcock, J Järvi, D Gregor, A Lumsdaine (February 26, 2006) ''Lambda expressions and closures for C++''</ref> || {{partial|C++11}}<ref name=doc1968/> || {{partial|C++11}} || Has function pointers, [[function object]]s. (Also, see below.)

Line 149 ⟶ 152:

| [[C Sharp (programming language)|C#]] || {{yes}} || {{yes}} || {{yes|7}} || {{yes|2.0 / 3.0}} || {{yes|2.0}} || {{yes|3.0}} || Has [[Delegate (CLI)|delegate]]s (2.0) and lambda expressions (3.0).

|-

| [[Objective-C]] || {{yes}} || {{yes}} || {{partial|Using anonymous}} || {{yes|2.0 + Blocks<ref>{{cite web |url=https://developer.apple.com/mac/library/documentation/Cocoa/Conceptual/Blocks/Articles/00_Introduction.html |url-status=dead |archive-url=https://web.archive.org/web/20090831133626/http://developer.apple.com/mac/library/documentation/Cocoa/Conceptual/Blocks/Articles/00_Introduction.html |archive-date=2009-08-31 |title=Mac Dev Center: Blocks Programming Topics: Introduction}}</ref>}} || {{yes|2.0 + Blocks}} || {{no}} || Has function pointers.

|-

| [[Java (programming language)|Java]] || {{partialyes}} || {{partialyes}} || {{partial|Using anonymous}} || {{yes|Java 8}} || {{yes|Java 8}} || {{noyes}} || Has [[anonymous inner class]]es.

|-

| [[Go (programming language)|Go]] || {{yes}} || {{yes}} || {{partial|Using anonymous}} || {{yes}} || {{yes}} || {{yes}}<ref>{{cite web |url=https://play.golang.org/p/lZHXrX-yR6 |title=2 examples in Go that you can have partial application }}</ref> ||

Line 159 ⟶ 162:

| [[Newsqueak]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{no}} ||

|-

| [[Rust (programming language)|Rust]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}}<ref>{{cite web |url=https://docs.rs/partial_application/0.2.1/ |title=partial_application/ |website=Docs.rs |access-date=2020-11-03}}</ref> ||

|-

| rowspan=912 | Functional languages || [[Lisp (programming language)|Lisp]] || {{partial|Syntax}} || {{partial|Syntax}} || {{yes}} || {{yes}} || {{partial|Common Lisp}} || {{no}} || (see below)

|-

| [[Scheme (programming language)|Scheme]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes|SRFI 26}}<ref>{{Cite web|url=http://srfi.schemers.org/srfi-26/srfi-26.html|title=SRFI 26: Notation for Specializing Parameters without Currying}}</ref> ||

|-

| [[Julia_Julia (programming_languageprogramming language)|Julia]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||

|-

| [[Clojure]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||

Line 172 ⟶ 175:

|-

| [[Haskell (programming language)|Haskell]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||

|-

| [[Iojq (programming language)|Iojq]] || {{yes}} || {{yesno}} || {{yes}} || {{yespartial|Expressions only}} || {{yespartial|Downwards}} || {{no}} ||

|-

| [[Scala (programming language)|Scala]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||

|-

| [[Erlang (programming language)|Erlang]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||

|-

| [[Elixir (programming language)|Elixir]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||

|-

| [[F Sharp (programming language)|F#]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||

Line 179 ⟶ 188:

| [[OCaml]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||

|-

| rowspan=67 | Scripting languages

| [[JavaScriptIo (programming language)|Io]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes|ECMAScript 5no}} || Partial application possible with user-land code on ES3 <ref>http://ejohn.org/blog/partial-functions-in-javascript/</ref>

|-

| [[Lua (programming language)|LuaJavaScript]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes|ECMAScript 5}} || Partial application possible with user-land code on ES3 <ref>{{citeCite web |url=http://tinylittlelifeejohn.org/?p=249 blog/partial-functions-in-javascript/|title=LuaJohn CodeResig for Curry (Currying Functions) |date=2010-07-23 |accessdate=2016-04-05Partial |archive-url=https://web.archive.org/web/20101105040747/http://tinylittlelife.org/?p=249Application |archive-date=2010-11-05 |url-status=deadin JavaScript}}</ref> ||

|-

| [[Lua (programming language)|Lua]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}}<ref>{{cite web |last1=Katz |first1=Ian |url=http://tinylittlelife.org/?p=249 |title=Lua Code for Curry (Currying Functions) |date=2010-07-23 |df=mdy |archive-url=https://web.archive.org/web/20181106235506/http://tinylittlelife.org/?p=249 |archive-date=2018-11-06}}</ref> ||

|-

| [[PHP]] || {{yes}} || {{yes}} || {{partial|Using anonymous}} || {{yes|5.3}} || {{yes|5.3}} || {{no}} || Partial application possible with user-land code.

|-

| [[Perl]] || {{yes}} || {{yes}} || {{yes|6}} || {{yes}} || {{yes}} || {{yes|6}}<ref>{{Cite web|url=http://perlgeek.de/blog-en/perl-5-to-6/28-currying.html|title = Blog &#124; Perlgeek.de :: Currying}}</ref> ||

|-

| [[Python (programming language)|Python]] || {{yes}} || {{yes}} || {{yes}} || {{partial|Expressions only}} || {{yes}} || {{yes|2.5}}<ref>{{Cite web|url=https://docs.python.org/whatsnew/2.5.html#pep-309-partial-function-application|title=What's New in Python 2.5 — Python 3.10.0 documentation}}</ref> || (see below)

|-

| [[Ruby (programming language)|Ruby]] || {{partial|Syntax}} || {{partial|Syntax}} || {{no|Unscoped}} || {{yes}} || {{yes}} || {{partial|1.9}} || (see below)

|-

| rowspan=76 | Other languages

| [[Fortran]] || {{yes}} || {{yes}} || {{yes}} || {{no}} || {{no}} || {{no}} ||

|-

| [[Io (programming language)|Io]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{no}} ||

|-

| [[Maple (software)|Maple]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{no}} ||

Line 202 ⟶ 211:

| [[Mathematica]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{no}} ||

|-

| [[MATLAB]] || {{yes}} || {{yes}} || {{yes}} || {{yes}}<ref>{{Cite web|url=http://www.mathworks.co.uk/help/matlab/matlab_prog/anonymous-functions.html|title=Anonymous Functions - MATLAB & Simulink - MathWorks United Kingdom}}</ref> || {{yes}} || {{yes}} || Partial application possible by automatic generation of new functions.<ref>[https://stackoverflow.com/q/9154271 Partial Function Evaluation in MATLAB]</ref>

|-

| [[Smalltalk]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{partial}} || Partial application possible through library.

Line 208 ⟶ 217:

| [[Swift (programming language)|Swift]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||

|}

; C++: [[C++11]] closures can capture non-local variables by copy construction, by reference (without extending their lifetime), by copy construction or by [[C++11#Rvalue references and move constructors|move construction]] (the variable lives as long as the closure does). The formerfirst potentiallyoption avoidsis ansafe expensiveif the closure is returned but requires a copy and allowscannot be used to modify the original variable but(which ismight unsafenot inexist caseany more at the time the closure is returned (see [[dangling reference]]scalled). The second isoption safepotentially ifavoids thean closure is returned but requires aexpensive copy and cannot be usedallows to modify the original variable (whichbut mightis notunsafe existin any more at the timecase the closure is calledreturned (see [[dangling reference]]s). The latterthird 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 type]]s are represented as Classes. Anonymous functions take the type inferred from the context. Method references are limited. For more details, see {{slink|Anonymous function|Java limitations}}.

; Lisp

Line 218 ⟶ 227:

: 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 <code>Method</code> or <code>Proc</code> 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 <code>[httphttps://wwwdocs.ruby-doclang.org/core-1.9.3en/master/Proc.html#method-i-curry]</code>.

==See also==

Line 236 ⟶ 245:

==External links==

* [http://rosettacode.org/wiki/First-class_functions First-class functions] on [[Rosetta Code]].

* [http://www.ibm.com/developerworks/linux/library/l-highfunc/index.html Higher order functions] {{Webarchive|url=https://web.archive.org/web/20191112160401/http://www.ibm.com/developerworks/linux/library/l-highfunc/index.html|date=November 12, 2019}} at [[IBM developerWorks]]

{{data types}}