First-class function

First-class functions are a necessity for the functional programming style, in which the use of higher-order functions is a standard practice. A simple example of a higher-ordered function is the 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 variables introduced in nested and anonymous functions. Historically, these were termed the funarg problems, the name coming from function argument. In early imperative languages these problems were avoided by either not supporting functions as result types (e.g. ALGOL 60, Pascal) or omitting nested functions and thus non-local variables (e.g. C). The early functional 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 and requires handling references to functions as closures instead of bare function pointers, which in turn makes garbage collection a necessity.

Concepts

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

Higher-order functions: passing functions as arguments

In languages where functions are first-class citizens, functions can be passed as arguments to other functions in the same way as other values (a function taking another function as argument is called a higher-order function). In the language Haskell:

<span id="mwSw"></span><span class="nf" id="mwTA">map</span><span class="w" id="mwTQ"> </span><span class="ow" id="mwTg">::</span><span class="w" id="mwTw"> </span><span class="p" id="mwUA">(</span><span class="n" id="mwUQ">a</span><span class="w" id="mwUg"> </span><span class="ow" id="mwUw">-></span><span class="w" id="mwVA"> </span><span class="n" id="mwVQ">b</span><span class="p" id="mwVg">)</span><span class="w" id="mwVw"> </span><span class="ow" id="mwWA">-></span><span class="w" id="mwWQ"> </span><span class="p" id="mwWg">[</span><span class="n" id="mwWw">a</span><span class="p" id="mwXA">]</span><span class="w" id="mwXQ"> </span><span class="ow" id="mwXg">-></span><span class="w" id="mwXw"> </span><span class="p" id="mwYA">[</span><span class="n" id="mwYQ">b</span><span class="p" id="mwYg">]</span> <span class="nf" id="mwYw">map</span><span class="w" id="mwZA"> </span><span class="n" id="mwZQ">f</span><span class="w" id="mwZg"> </span><span class="kt" id="mwZw">[]</span><span class="w" id="mwaA"> </span><span class="ow" id="mwaQ">=</span><span class="w" id="mwag"> </span><span class="kt" id="mwaw">[]</span> <span class="nf" id="mwbA">map</span><span class="w" id="mwbQ"> </span><span class="n" id="mwbg">f</span><span class="w" id="mwbw"> </span><span class="p" id="mwcA">(</span><span class="n" id="mwcQ">x</span><span class="kt" id="mwcg">:</span><span class="n" id="mwcw">xs</span><span class="p" id="mwdA">)</span><span class="w" id="mwdQ"> </span><span class="ow" id="mwdg">=</span><span class="w" id="mwdw"> </span><span class="n" id="mweA">f</span><span class="w" id="mweQ"> </span><span class="n" id="mweg">x</span><span class="w" id="mwew"> </span><span class="kt" id="mwfA">:</span><span class="w" id="mwfQ"> </span><span class="n" id="mwfg">map</span><span class="w" id="mwfw"> </span><span class="n" id="mwgA">f</span><span class="w" id="mwgQ"> </span><span class="n" id="mwgg">xs</span>

Languages where functions are not first-class often still allow one to write higher-order functions through the use of features such as function pointers or delegates. In the language C:

<span id="mwiQ"></span><span class="kt" id="mwig">void</span><span class="w" id="mwiw"> </span><span class="nf" id="mwjA">map</span><span class="p" id="mwjQ">(</span><span class="kt" id="mwjg">int</span><span class="w" id="mwjw"> </span><span class="p" id="mwkA">(</span><span class="o" id="mwkQ">*</span><span class="n" id="mwkg">f</span><span class="p" id="mwkw">)(</span><span class="kt" id="mwlA">int</span><span class="p" id="mwlQ">),</span><span class="w" id="mwlg"> </span><span class="kt" id="mwlw">int</span><span class="w" id="mwmA"> </span><span class="n" id="mwmQ">x</span><span class="p" id="mwmg">[],</span><span class="w" id="mwmw"> </span><span class="kt" id="mwnA">size_t</span><span class="w" id="mwnQ"> </span><span class="n" id="mwng">n</span><span class="p" id="mwnw">)</span><span class="w" id="mwoA"> </span><span class="p" id="mwoQ">{</span> <span class="w" id="mwog"> </span><span class="k" id="mwow">for</span><span class="w" id="mwpA"> </span><span class="p" id="mwpQ">(</span><span class="kt" id="mwpg">int</span><span class="w" id="mwpw"> </span><span class="n" id="mwqA">i</span><span class="w" id="mwqQ"> </span><span class="o" id="mwqg">=</span><span class="w" id="mwqw"> </span><span class="mi" id="mwrA">0</span><span class="p" id="mwrQ">;</span><span class="w" id="mwrg"> </span><span class="n" id="mwrw">i</span><span class="w" id="mwsA"> </span><span class="o" id="mwsQ"><</span><span class="w" id="mwsg"> </span><span class="n" id="mwsw">n</span><span class="p" id="mwtA">;</span><span class="w" id="mwtQ"> </span><span class="o" id="mwtg">++</span><span class="n" id="mwtw">i</span><span class="p" id="mwuA">)</span><span class="w" id="mwuQ"> </span><span class="p" id="mwug">{</span> <span class="w" id="mwuw"> </span><span class="n" id="mwvA">x</span><span class="p" id="mwvQ">[</span><span class="n" id="mwvg">i</span><span class="p" id="mwvw">]</span><span class="w" id="mwwA"> </span><span class="o" id="mwwQ">=</span><span class="w" id="mwwg"> </span><span class="n" id="mwww">f</span><span class="p" id="mwxA">(</span><span class="n" id="mwxQ">x</span><span class="p" id="mwxg">[</span><span class="n" id="mwxw">i</span><span class="p" id="mwyA">]);</span> <span class="w" id="mwyQ"> </span><span class="p" id="mwyg">}</span> <span class="p" id="mwyw">}</span>

There 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 lists, while the C sample operates on 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 (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 and the C sample in terms of recursion. Finally, the Haskell function has a polymorphic type, as this is not supported by C we have fixed all type variables to the type constant int.

Anonymous and nested functions

In languages supporting anonymous functions, we can pass such a function as an argument to a higher-order function:

<span id="mw3Q"></span><span class="nf" id="mw3g">main</span><span class="w" id="mw3w"> </span><span class="ow" id="mw4A">=</span><span class="w" id="mw4Q"> </span><span class="n" id="mw4g">map</span><span class="w" id="mw4w"> </span><span class="p" id="mw5A">(</span><span class="nf" id="mw5Q">\</span><span class="n" id="mw5g">x</span><span class="w" id="mw5w"> </span><span class="ow" id="mw6A">-></span><span class="w" id="mw6Q"> </span><span class="mi" id="mw6g">3</span><span class="w" id="mw6w"> </span><span class="o" id="mw7A">*</span><span class="w" id="mw7Q"> </span><span class="n" id="mw7g">x</span><span class="w" id="mw7w"> </span><span class="o" id="mw8A">+</span><span class="w" id="mw8Q"> </span><span class="mi" id="mw8g">1</span><span class="p" id="mw8w">)</span><span class="w" id="mw9A"> </span><span class="p" id="mw9Q">[</span><span class="mi" id="mw9g">1</span><span class="p" id="mw9w">,</span><span class="w" id="mw-A"> </span><span class="mi" id="mw-Q">2</span><span class="p" id="mw-g">,</span><span class="w" id="mw-w"> </span><span class="mi" id="mw_A">3</span><span class="p" id="mw_Q">,</span><span class="w" id="mw_g"> </span><span class="mi" id="mw_w">4</span><span class="p" id="mwAQA">,</span><span class="w" id="mwAQE"> </span><span class="mi" id="mwAQI">5</span><span class="p" id="mwAQM">]</span>

In a language which does not support anonymous functions, we have to bind it to a name instead:

<span id="mwAQc"></span><span class="kt" id="mwAQg">int</span><span class="w" id="mwAQk"> </span><span class="nf" id="mwAQo">f</span><span class="p" id="mwAQs">(</span><span class="kt" id="mwAQw">int</span><span class="w" id="mwAQ0"> </span><span class="n" id="mwAQ4">x</span><span class="p" id="mwAQ8">)</span><span class="w" id="mwARA"> </span><span class="p" id="mwARE">{</span> <span class="w" id="mwARI"> </span><span class="k" id="mwARM">return</span><span class="w" id="mwARQ"> </span><span class="mi" id="mwARU">3</span><span class="w" id="mwARY"> </span><span class="o" id="mwARc">*</span><span class="w" id="mwARg"> </span><span class="n" id="mwARk">x</span><span class="w" id="mwARo"> </span><span class="o" id="mwARs">+</span><span class="w" id="mwARw"> </span><span class="mi" id="mwAR0">1</span><span class="p" id="mwAR4">;</span> <span class="p" id="mwAR8">}</span> <span class="kt" id="mwASA">int</span><span class="w" id="mwASE"> </span><span class="nf" id="mwASI">main</span><span class="p" id="mwASM">()</span><span class="w" id="mwASQ"> </span><span class="p" id="mwASU">{</span> <span class="w" id="mwASY"> </span><span class="kt" id="mwASc">int</span><span class="w" id="mwASg"> </span><span class="n" id="mwASk">list</span><span class="p" id="mwASo">[]</span><span class="w" id="mwASs"> </span><span class="o" id="mwASw">=</span><span class="w" id="mwAS0"> </span><span class="p" id="mwAS4">{</span><span class="mi" id="mwAS8">1</span><span class="p" id="mwATA">,</span><span class="w" id="mwATE"> </span><span class="mi" id="mwATI">2</span><span class="p" id="mwATM">,</span><span class="w" id="mwATQ"> </span><span class="mi" id="mwATU">3</span><span class="p" id="mwATY">,</span><span class="w" id="mwATc"> </span><span class="mi" id="mwATg">4</span><span class="p" id="mwATk">,</span><span class="w" id="mwATo"> </span><span class="mi" id="mwATs">5</span><span class="p" id="mwATw">};</span> <span class="w" id="mwAT0"> </span><span class="n" id="mwAT4">map</span><span class="p" id="mwAT8">(</span><span class="n" id="mwAUA">f</span><span class="p" id="mwAUE">,</span><span class="w" id="mwAUI"> </span><span class="n" id="mwAUM">list</span><span class="p" id="mwAUQ">,</span><span class="w" id="mwAUU"> </span><span class="mi" id="mwAUY">5</span><span class="p" id="mwAUc">);</span> <span class="p" id="mwAUg">}</span>

Non-local variables and closures

Once we have anonymous or nested functions, it becomes natural for them to refer to variables outside of their body (called non-local variables):

<span id="mwAVA"></span><span class="nf" id="mwAVE">main</span><span class="w" id="mwAVI"> </span><span class="ow" id="mwAVM">=</span><span class="w" id="mwAVQ"> </span><span class="kr" id="mwAVU">let</span><span class="w" id="mwAVY"> </span><span class="n" id="mwAVc">a</span><span class="w" id="mwAVg"> </span><span class="ow" id="mwAVk">=</span><span class="w" id="mwAVo"> </span><span class="mi" id="mwAVs">3</span> <span class="w" id="mwAVw"> </span><span class="n" id="mwAV0">b</span><span class="w" id="mwAV4"> </span><span class="ow" id="mwAV8">=</span><span class="w" id="mwAWA"> </span><span class="mi" id="mwAWE">1</span> <span class="w" id="mwAWI"> </span><span class="kr" id="mwAWM">in</span><span class="w" id="mwAWQ"> </span><span class="n" id="mwAWU">map</span><span class="w" id="mwAWY"> </span><span class="p" id="mwAWc">(</span><span class="nf" id="mwAWg">\</span><span class="n" id="mwAWk">x</span><span class="w" id="mwAWo"> </span><span class="ow" id="mwAWs">-></span><span class="w" id="mwAWw"> </span><span class="n" id="mwAW0">a</span><span class="w" id="mwAW4"> </span><span class="o" id="mwAW8">*</span><span class="w" id="mwAXA"> </span><span class="n" id="mwAXE">x</span><span class="w" id="mwAXI"> </span><span class="o" id="mwAXM">+</span><span class="w" id="mwAXQ"> </span><span class="n" id="mwAXU">b</span><span class="p" id="mwAXY">)</span><span class="w" id="mwAXc"> </span><span class="p" id="mwAXg">[</span><span class="mi" id="mwAXk">1</span><span class="p" id="mwAXo">,</span><span class="w" id="mwAXs"> </span><span class="mi" id="mwAXw">2</span><span class="p" id="mwAX0">,</span><span class="w" id="mwAX4"> </span><span class="mi" id="mwAX8">3</span><span class="p" id="mwAYA">,</span><span class="w" id="mwAYE"> </span><span class="mi" id="mwAYI">4</span><span class="p" id="mwAYM">,</span><span class="w" id="mwAYQ"> </span><span class="mi" id="mwAYU">5</span><span class="p" id="mwAYY">]</span>

If functions are represented with bare function pointers, we can not know anymore how the value that is outside of the function's body should be passed to it, and because of that a closure needs to be built manually. Therefore, we can not speak of "first-class" functions here.

<span id="mwAYo"></span><span class="k" id="mwAYs">typedef</span><span class="w" id="mwAYw"> </span><span class="k" id="mwAY0">struct</span><span class="w" id="mwAY4"> </span><span class="p" id="mwAY8">{</span> <span class="w" id="mwAZA"> </span><span class="kt" id="mwAZE">int</span><span class="w" id="mwAZI"> </span><span class="p" id="mwAZM">(</span><span class="o" id="mwAZQ">*</span><span class="n" id="mwAZU">f</span><span class="p" id="mwAZY">)(</span><span class="kt" id="mwAZc">int</span><span class="p" id="mwAZg">,</span><span class="w" id="mwAZk"> </span><span class="kt" id="mwAZo">int</span><span class="p" id="mwAZs">,</span><span class="w" id="mwAZw"> </span><span class="kt" id="mwAZ0">int</span><span class="p" id="mwAZ4">);</span> <span class="w" id="mwAZ8"> </span><span class="kt" id="mwAaA">int</span><span class="w" id="mwAaE"> </span><span class="n" id="mwAaI">a</span><span class="p" id="mwAaM">;</span> <span class="w" id="mwAaQ"> </span><span class="kt" id="mwAaU">int</span><span class="w" id="mwAaY"> </span><span class="n" id="mwAac">b</span><span class="p" id="mwAag">;</span> <span class="p" id="mwAak">}</span><span class="w" id="mwAao"> </span><span class="n" id="mwAas">Closure</span><span class="p" id="mwAaw">;</span> <span class="kt" id="mwAa0">void</span><span class="w" id="mwAa4"> </span><span class="nf" id="mwAa8">map</span><span class="p" id="mwAbA">(</span><span class="n" id="mwAbE">Closure</span><span class="o" id="mwAbI">*</span><span class="w" id="mwAbM"> </span><span class="n" id="mwAbQ">closure</span><span class="p" id="mwAbU">,</span><span class="w" id="mwAbY"> </span><span class="kt" id="mwAbc">int</span><span class="w" id="mwAbg"> </span><span class="n" id="mwAbk">x</span><span class="p" id="mwAbo">[],</span><span class="w" id="mwAbs"> </span><span class="kt" id="mwAbw">size_t</span><span class="w" id="mwAb0"> </span><span class="n" id="mwAb4">n</span><span class="p" id="mwAb8">)</span><span class="w" id="mwAcA"> </span><span class="p" id="mwAcE">{</span> <span class="w" id="mwAcI"> </span><span class="k" id="mwAcM">for</span><span class="w" id="mwAcQ"> </span><span class="p" id="mwAcU">(</span><span class="kt" id="mwAcY">int</span><span class="w" id="mwAcc"> </span><span class="n" id="mwAcg">i</span><span class="w" id="mwAck"> </span><span class="o" id="mwAco">=</span><span class="w" id="mwAcs"> </span><span class="mi" id="mwAcw">0</span><span class="p" id="mwAc0">;</span><span class="w" id="mwAc4"> </span><span class="n" id="mwAc8">i</span><span class="w" id="mwAdA"> </span><span class="o" id="mwAdE"><</span><span class="w" id="mwAdI"> </span><span class="n" id="mwAdM">n</span><span class="p" id="mwAdQ">;</span><span class="w" id="mwAdU"> </span><span class="o" id="mwAdY">++</span><span class="n" id="mwAdc">i</span><span class="p" id="mwAdg">)</span><span class="w" id="mwAdk"> </span><span class="p" id="mwAdo">{</span> <span class="w" id="mwAds"> </span><span class="n" id="mwAdw">x</span><span class="p" id="mwAd0">[</span><span class="n" id="mwAd4">i</span><span class="p" id="mwAd8">]</span><span class="w" id="mwAeA"> </span><span class="o" id="mwAeE">=</span><span class="w" id="mwAeI"> </span><span class="p" id="mwAeM">(</span><span class="n" id="mwAeQ">closure</span><span class="o" id="mwAeU">-></span><span class="n" id="mwAeY">f</span><span class="p" id="mwAec">)(</span><span class="n" id="mwAeg">closure</span><span class="o" id="mwAek">-></span><span class="n" id="mwAeo">a</span><span class="p" id="mwAes">,</span><span class="w" id="mwAew"> </span><span class="n" id="mwAe0">closure</span><span class="o" id="mwAe4">-></span><span class="n" id="mwAe8">b</span><span class="p" id="mwAfA">,</span><span class="w" id="mwAfE"> </span><span class="n" id="mwAfI">x</span><span class="p" id="mwAfM">[</span><span class="n" id="mwAfQ">i</span><span class="p" id="mwAfU">]);</span> <span class="w" id="mwAfY"> </span><span class="p" id="mwAfc">}</span> <span class="p" id="mwAfg">}</span> <span class="kt" id="mwAfk">int</span><span class="w" id="mwAfo"> </span><span class="nf" id="mwAfs">f</span><span class="p" id="mwAfw">(</span><span class="kt" id="mwAf0">int</span><span class="w" id="mwAf4"> </span><span class="n" id="mwAf8">a</span><span class="p" id="mwAgA">,</span><span class="w" id="mwAgE"> </span><span class="kt" id="mwAgI">int</span><span class="w" id="mwAgM"> </span><span class="n" id="mwAgQ">b</span><span class="p" id="mwAgU">,</span><span class="w" id="mwAgY"> </span><span class="kt" id="mwAgc">int</span><span class="w" id="mwAgg"> </span><span class="n" id="mwAgk">x</span><span class="p" id="mwAgo">)</span><span class="w" id="mwAgs"> </span><span class="p" id="mwAgw">{</span> <span class="w" id="mwAg0"> </span><span class="k" id="mwAg4">return</span><span class="w" id="mwAg8"> </span><span class="n" id="mwAhA">a</span><span class="w" id="mwAhE"> </span><span class="o" id="mwAhI">*</span><span class="w" id="mwAhM"> </span><span class="n" id="mwAhQ">x</span><span class="w" id="mwAhU"> </span><span class="o" id="mwAhY">+</span><span class="w" id="mwAhc"> </span><span class="n" id="mwAhg">b</span><span class="p" id="mwAhk">;</span> <span class="p" id="mwAho">}</span> <span class="kt" id="mwAhs">void</span><span class="w" id="mwAhw"> </span><span class="nf" id="mwAh0">main</span><span class="p" id="mwAh4">()</span><span class="w" id="mwAh8"> </span><span class="p" id="mwAiA">{</span> <span class="w" id="mwAiE"> </span><span class="kt" id="mwAiI">int</span><span class="w" id="mwAiM"> </span><span class="n" id="mwAiQ">l</span><span class="p" id="mwAiU">[]</span><span class="w" id="mwAiY"> </span><span class="o" id="mwAic">=</span><span class="w" id="mwAig"> </span><span class="p" id="mwAik">{</span><span class="mi" id="mwAio">1</span><span class="p" id="mwAis">,</span><span class="w" id="mwAiw"> </span><span class="mi" id="mwAi0">2</span><span class="p" id="mwAi4">,</span><span class="w" id="mwAi8"> </span><span class="mi" id="mwAjA">3</span><span class="p" id="mwAjE">,</span><span class="w" id="mwAjI"> </span><span class="mi" id="mwAjM">4</span><span class="p" id="mwAjQ">,</span><span class="w" id="mwAjU"> </span><span class="mi" id="mwAjY">5</span><span class="p" id="mwAjc">};</span> <span class="w" id="mwAjg"> </span><span class="kt" id="mwAjk">int</span><span class="w" id="mwAjo"> </span><span class="n" id="mwAjs">a</span><span class="w" id="mwAjw"> </span><span class="o" id="mwAj0">=</span><span class="w" id="mwAj4"> </span><span class="mi" id="mwAj8">3</span><span class="p" id="mwAkA">;</span> <span class="w" id="mwAkE"> </span><span class="kt" id="mwAkI">int</span><span class="w" id="mwAkM"> </span><span class="n" id="mwAkQ">b</span><span class="w" id="mwAkU"> </span><span class="o" id="mwAkY">=</span><span class="w" id="mwAkc"> </span><span class="mi" id="mwAkg">1</span><span class="p" id="mwAkk">;</span> <span class="w" id="mwAko"> </span><span class="n" id="mwAks">Closure</span><span class="w" id="mwAkw"> </span><span class="n" id="mwAk0">closure</span><span class="w" id="mwAk4"> </span><span class="o" id="mwAk8">=</span><span class="w" id="mwAlA"> </span><span class="p" id="mwAlE">{</span><span class="n" id="mwAlI">f</span><span class="p" id="mwAlM">,</span><span class="w" id="mwAlQ"> </span><span class="n" id="mwAlU">a</span><span class="p" id="mwAlY">,</span><span class="w" id="mwAlc"> </span><span class="n" id="mwAlg">b</span><span class="p" id="mwAlk">};</span> <span class="w" id="mwAlo"> </span><span class="n" id="mwAls">map</span><span class="p" id="mwAlw">(</span><span class="o" id="mwAl0">&</span><span class="n" id="mwAl4">closure</span><span class="p" id="mwAl8">,</span><span class="w" id="mwAmA"> </span><span class="n" id="mwAmE">l</span><span class="p" id="mwAmI">,</span><span class="w" id="mwAmM"> </span><span class="mi" id="mwAmQ">5</span><span class="p" id="mwAmU">);</span> <span class="p" id="mwAmY">}</span>

Also note that the map is now specialized to functions referring to two ints outside of their environment. This can be set up more generally, but requires more boilerplate code. If f would have been a nested function we would still have run into the same problem and this is the reason they are not supported in C.

Higher-order functions: returning functions as results

When returning a function, we are in fact returning its closure. In the C example any local variables captured by the closure will go out of scope once we return from the function that builds the closure. Forcing the closure at a later point will result in undefined behaviour, possibly corrupting the stack. This is known as the upwards funarg problem.

Assigning functions to variables

Assigning functions to variables and storing them inside (global) data structures potentially suffers from the same difficulties as returning functions.

<span id="mwAno"></span><span class="nf" id="mwAns">f</span><span class="w" id="mwAnw"> </span><span class="ow" id="mwAn0">::</span><span class="w" id="mwAn4"> </span><span class="p" id="mwAn8">[[</span><span class="kt" id="mwAoA">Integer</span><span class="p" id="mwAoE">]</span><span class="w" id="mwAoI"> </span><span class="ow" id="mwAoM">-></span><span class="w" id="mwAoQ"> </span><span class="p" id="mwAoU">[</span><span class="kt" id="mwAoY">Integer</span><span class="p" id="mwAoc">]]</span> <span class="nf" id="mwAog">f</span><span class="w" id="mwAok"> </span><span class="ow" id="mwAoo">=</span><span class="w" id="mwAos"> </span><span class="kr" id="mwAow">let</span><span class="w" id="mwAo0"> </span><span class="n" id="mwAo4">a</span><span class="w" id="mwAo8"> </span><span class="ow" id="mwApA">=</span><span class="w" id="mwApE"> </span><span class="mi" id="mwApI">3</span> <span class="w" id="mwApM"> </span><span class="n" id="mwApQ">b</span><span class="w" id="mwApU"> </span><span class="ow" id="mwApY">=</span><span class="w" id="mwApc"> </span><span class="mi" id="mwApg">1</span> <span class="w" id="mwApk"> </span><span class="kr" id="mwApo">in</span><span class="w" id="mwAps"> </span><span class="p" id="mwApw">[</span><span class="n" id="mwAp0">map</span><span class="w" id="mwAp4"> </span><span class="p" id="mwAp8">(</span><span class="nf" id="mwAqA">\</span><span class="n" id="mwAqE">x</span><span class="w" id="mwAqI"> </span><span class="ow" id="mwAqM">-></span><span class="w" id="mwAqQ"> </span><span class="n" id="mwAqU">a</span><span class="w" id="mwAqY"> </span><span class="o" id="mwAqc">*</span><span class="w" id="mwAqg"> </span><span class="n" id="mwAqk">x</span><span class="w" id="mwAqo"> </span><span class="o" id="mwAqs">+</span><span class="w" id="mwAqw"> </span><span class="n" id="mwAq0">b</span><span class="p" id="mwAq4">),</span><span class="w" id="mwAq8"> </span><span class="n" id="mwArA">map</span><span class="w" id="mwArE"> </span><span class="p" id="mwArI">(</span><span class="nf" id="mwArM">\</span><span class="n" id="mwArQ">x</span><span class="w" id="mwArU"> </span><span class="ow" id="mwArY">-></span><span class="w" id="mwArc"> </span><span class="n" id="mwArg">b</span><span class="w" id="mwArk"> </span><span class="o" id="mwAro">*</span><span class="w" id="mwArs"> </span><span class="n" id="mwArw">x</span><span class="w" id="mwAr0"> </span><span class="o" id="mwAr4">+</span><span class="w" id="mwAr8"> </span><span class="n" id="mwAsA">a</span><span class="p" id="mwAsE">)]</span>

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:

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 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 languages by comparing the source code of the function bodies (such as in Interpreted Lisp 1.5) or the object code in compiled languages. 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 pure languages, such as Haskell.