Content deleted Content added
Irontitan76 (talk | contribs) m Grammar updates |
|||
| (43 intermediate revisions by 40 users not shown) | |||
Line 1:
{{Short description|Programming language feature}}
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=
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 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 variable]]s introduced in [[nested function|nested]] and [[anonymous function]]s. Historically, these were termed the ''[[funarg problem]]s'', the name coming from
== Concepts ==
Line 26 ⟶ 27:
</syntaxhighlight>
=== Anonymous and nested functions ===
Line 62 ⟶ 63:
typedef struct {
int (*f)(int, int, int);
int
int
} closure_t;
void map(closure_t *closure, int x[], size_t n) {
for (int i = 0; i < n; ++i)
x[i] = (
}
Line 79 ⟶ 80:
int a = 3;
int b = 1;
closure_t closure = {f,
map(&closure, l, 5);
}
Line 90 ⟶ 91:
=== Assigning functions to variables ===
[[Assignment (computer science)|Assigning]] functions to [[variable (computer science)|variables]] and storing them inside (global)
<syntaxhighlight lang="haskell">
f :: [[Integer] -> [Integer]]
Line 99 ⟶ 100:
=== Equality of functions ===
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 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 [[
== Type theory ==
Line 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 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|
|-
| [[Pascal (programming language)|Pascal]] || {{yes}} || {{no}} || {{yes}} || {{no}} || {{partial|Downwards}} || {{no}}
Line 145:
|-
| rowspan=9 | C family
| [[C (programming language)|C]] || {{yes}} || {{yes}} || {{
|-
| [[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 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]] || {{
|-
| [[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 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
|-
| rowspan=
|-
| [[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> ||
|-
| [[
|-
| [[Clojure]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||
Line 175:
|-
| [[Haskell (programming language)|Haskell]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||
|-▼
| [[
|-
| [[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 182 ⟶ 188:
| [[OCaml]] || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} || {{yes}} ||
|-
| rowspan=
| [[
|-
| [[
|-
| [[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 | 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=
| [[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 205 ⟶ 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 211 ⟶ 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),
; 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 221 ⟶ 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>[
==See also==
Line 239 ⟶ 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
{{data types}}
| |||