First-class function: Difference between revisions

Revision as of 11:20, 13 April 2024

Latest revision as of 00:14, 24 August 2025

(9 intermediate revisions by 9 users not shown)

Line 4:

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 "''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 ==

Line 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 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 108 ⟶ 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 228 ⟶ 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 246 ⟶ 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}}