Editing First-class function (section)

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

; [[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]] and [[merge sort]], would be considered equal. Deciding on extensional equality is [[undecidable problem|undecidable]] in general and even for functions with finite domains often intractable. For this reason no programming language implements function equality as extensional equality.

; [[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 [[purity (computer science)|pure]] languages, such as Haskell.