Editing Functional programming (section)

== Concepts ==
A number of concepts<ref>Sean Tull - Monoidal Categories for Formal Concept Analysis.</ref> and paradigms are specific to functional programming, and generally foreign to [[imperative programming]] (including [[object-oriented programming]]). However, programming languages often cater to several programming paradigms, so programmers using "mostly imperative" languages may have utilized some of these concepts.<ref>{{cite web |url=http://byte.com/art/9408/sec11/art1.htm |archive-url=https://web.archive.org/web/20060827094123/http://byte.com/art/9408/sec11/art1.htm |archive-date=2006-08-27 |title=Functional Programming Comes of Age |first=Dick |last=Pountain |work=[[Byte (magazine)|Byte]] (August 1994) |access-date=August 31, 2006 |url-status=dead }}</ref>

=== First-class and higher-order functions ===
{{main|First-class function|Higher-order function}}

[[Higher-order function]]s are functions that can either take other functions as arguments or return them as results. In calculus, an example of a higher-order function is the [[differential operator]] <math>d/dx</math>, which returns the [[derivative]] of a function <math>f</math>.

Higher-order functions are closely related to [[first-class function]]s in that higher-order functions and first-class functions both allow functions as arguments and results of other functions. The distinction between the two is subtle: "higher-order" describes a mathematical concept of functions that operate on other functions, while "first-class" is a computer science term for programming language entities that have no restriction on their use (thus first-class functions can appear anywhere in the program that other first-class entities like numbers can, including as arguments to other functions and as their return values).

Higher-order functions enable [[partial application]] or [[currying]], a technique that applies a function to its arguments one at a time, with each application returning a new function that accepts the next argument. This lets a programmer succinctly express, for example, the [[successor function]] as the addition operator partially applied to the [[natural number]] one.

=== Pure functions ===
{{main|Pure function}}
[[Pure function]]s (or expressions) have no [[side effect (computer science)|side effects]] (memory or I/O). This means that pure functions have several useful properties, many of which can be used to optimize the code:
* If the result of a pure expression is not used, it can be removed without affecting other expressions.
* If a pure function is called with arguments that cause no side-effects, the result is constant with respect to that argument list (sometimes called [[referential transparency]] or [[idempotence]]), i.e., calling the pure function again with the same arguments returns the same result. (This can enable caching optimizations such as [[memoization]].)
* If there is no data dependency between two pure expressions, their order can be reversed, or they can be performed in [[parallelization|parallel]] and they cannot interfere with one another (in other terms, the evaluation of any pure expression is [[thread-safe]]).
* If the entire language does not allow side-effects, then any evaluation strategy can be used; this gives the compiler freedom to reorder or combine the evaluation of expressions in a program (for example, using [[deforestation (computer science)|deforestation]]).

While most compilers for imperative programming languages detect pure functions and perform common-subexpression elimination for pure function calls, they cannot always do this for pre-compiled libraries, which generally do not expose this information, thus preventing optimizations that involve those external functions. Some compilers, such as [[GNU Compiler Collection|gcc]], add extra keywords for a programmer to explicitly mark external functions as pure, to enable such optimizations. [[Fortran 95]] also lets functions be designated ''pure''.<ref name=fortran95>{{cite web |title=ISO/IEC JTC 1/SC 22/WG5/N2137 – Fortran 2015 Committee Draft (J3/17-007r2) |publisher=International Organization for Standardization |date=July 6, 2017 |url=https://wg5-fortran.org/N2101-N2150/N2137.pdf |pages=336–338}}</ref> C++11 added <code>constexpr</code> keyword with similar semantics.

=== Recursion ===
{{Main|Recursion (computer science)}}

[[Iteration]] (looping) in functional languages is usually accomplished via [[recursion]]. [[recursion (computer science)|Recursive functions]] invoke themselves, letting an operation be repeated until it reaches the [[Recursion (computer science)|base case]]. In general, recursion requires maintaining a [[Call stack|stack]], which consumes space in a linear amount to the depth of recursion. This could make recursion prohibitively expensive to use instead of imperative loops. However, a special form of recursion known as [[tail recursion]] can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages. Tail recursion optimization can be implemented by transforming the program into [[continuation passing style]] during compiling, among other approaches.

The [[Scheme (programming language)|Scheme]] language standard requires implementations to support proper tail recursion, meaning they must allow an unbounded number of active tail calls.<ref name='SchemeProperTailRec'>{{cite web|url=http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_sec_5.11 |title=Revised^6 Report on the Algorithmic Language Scheme |publisher=R6rs.org |access-date=2013-03-21}}</ref><ref>{{cite web|url=http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale-Z-H-7.html#node_sec_5.3 |title=Revised^6 Report on the Algorithmic Language Scheme - Rationale |publisher=R6rs.org |access-date=2013-03-21}}</ref> Proper tail recursion is not simply an optimization; it is a language feature that assures users that they can use recursion to express a loop and doing so would be safe-for-space.<ref>{{cite book|chapter=Proper tail recursion and space efficiency|last=Clinger|first=William|title=Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation - PLDI '98|date=1998|pages=174–185|doi=10.1145/277650.277719|isbn=0897919874|s2cid=16812984}}</ref> Moreover, contrary to its name, it accounts for all tail calls, not just tail recursion. While proper tail recursion is usually implemented by turning code into imperative loops, implementations might implement it in other ways. For example, [[Chicken (Scheme implementation)|Chicken]] intentionally maintains a stack and lets the [[stack overflow]]. However, when this happens, its [[Garbage collection (computer science)|garbage collector]] will claim space back,<ref>{{cite web |url=http://home.pipeline.com/~hbaker1/CheneyMTA.html |title=CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A. |last=Baker |first=Henry |date=1994 |access-date=2020-04-29 |archivedate=2006-03-03 |archiveurl=https://web.archive.org/web/20060303155622/http://home.pipeline.com/~hbaker1/CheneyMTA.html |url-status=deviated }}</ref> allowing an unbounded number of active tail calls even though it does not turn tail recursion into a loop.

Common patterns of recursion can be abstracted away using higher-order functions, with [[catamorphism]]s and [[anamorphism]]s (or "folds" and "unfolds") being the most obvious examples. Such recursion schemes play a role analogous to built-in control structures such as [[Program loops|loops]] in [[imperative languages]].

Most general purpose functional programming languages allow unrestricted recursion and are [[Turing complete]], which makes the [[halting problem]] [[undecidable problem|undecidable]], can cause unsoundness of [[equational reasoning]], and generally requires the introduction of [[inconsistency]] into the logic expressed by the language's [[type system]]. Some special purpose languages such as [[Coq (software)|Coq]] allow only [[well-founded]] recursion and are [[strongly normalizing]] (nonterminating computations can be expressed only with infinite streams of values called [[codata (computer science)|codata]]). As a consequence, these languages fail to be Turing complete and expressing certain functions in them is impossible, but they can still express a wide class of interesting computations while avoiding the problems introduced by unrestricted recursion. Functional programming limited to well-founded recursion with a few other constraints is called [[total functional programming]].<ref name=totalfp>{{cite journal |last=Turner |first=D.A.|author-link=David Turner (computer scientist) |title=Total Functional Programming |journal=Journal of Universal Computer Science|volume=10| date=2004-07-28 |pages=751–768 |url=http://www.jucs.org/jucs_10_7/total_functional_programming|doi=10.3217/jucs-010-07-0751|issue=7}}</ref>

=== Strict versus non-strict evaluation ===
{{Main|Evaluation strategy}}

Functional languages can be categorized by whether they use ''strict (eager)'' or ''non-strict (lazy)'' evaluation, concepts that refer to how function arguments are processed when an expression is being evaluated. The technical difference is in the [[denotational semantics]] of expressions containing failing or divergent computations. Under strict evaluation, the evaluation of any term containing a failing subterm fails. For example, the expression:

<!-- language? -->
 print length([2+1, 3*2, 1/0, 5-4])

fails under strict evaluation because of the division by zero in the third element of the list. Under lazy evaluation, the length function returns the value 4 (i.e., the number of items in the list), since evaluating it does not attempt to evaluate the terms making up the list. In brief, strict evaluation always fully evaluates function arguments before invoking the function. Lazy evaluation does not evaluate function arguments unless their values are required to evaluate the function call itself.

The usual implementation strategy for lazy evaluation in functional languages is [[graph reduction]].<ref>[http://research.microsoft.com/~simonpj/papers/slpj-book-1987/index.htm The Implementation of Functional Programming Languages]. Simon Peyton Jones, published by Prentice Hall, 1987</ref> Lazy evaluation is used by default in several pure functional languages, including [[Miranda (programming language)|Miranda]], [[Clean (programming language)|Clean]], and [[Haskell]].

{{Harvnb|Hughes|1984}} argues for lazy evaluation as a mechanism for improving program modularity through [[separation of concerns]], by easing independent implementation of producers and consumers of data streams.<ref name="hughesWhyFPMatters">{{cite web |url=http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html |title=Why Functional Programming Matters |author-link=John Hughes (computer scientist) |first=John |last=Hughes |year=1984}}</ref> Launchbury 1993 <!-- a cite arguing more strongly against lazy evaluation would be preferable here, if someone knows of one. --> describes some difficulties that lazy evaluation introduces, particularly in analyzing a program's storage requirements, and proposes an [[operational semantics]] to aid in such analysis.<ref name=launchbury1993>{{cite conference |last=Launchbury |first=John |author-link=John Launchbury |title=A Natural Semantics for Lazy Evaluation |date=March 1993 |conference=Symposium on Principles of Programming Languages |location=Charleston, South Carolina |publisher=[[Association for Computing Machinery|ACM]] |pages=144–154 |doi=10.1145/158511.158618 |doi-access=free}}</ref> Harper 2009 proposes including both strict and lazy evaluation in the same language, using the language's type system to distinguish them.<ref>{{cite book |url=https://www.cs.cmu.edu/~rwh/plbook/book.pdf |archive-url=https://web.archive.org/web/20160407095249/https://www.cs.cmu.edu/~rwh/plbook/book.pdf |archive-date=2016-04-07 |title=Practical Foundations for Programming Languages |author=Robert W. Harper |author-link=Robert Harper (computer scientist) |year=2009}}</ref>

=== Type systems ===
{{main|Type system}}
<!-- expand this section!!! also split it into several sections -->

Especially since the development of [[Hindley–Milner type inference]] in the 1970s, functional programming languages have tended to use [[typed lambda calculus]], rejecting all invalid programs at compilation time and risking [[false positives and false negatives#False positive error|false positive errors]], as opposed to the [[untyped lambda calculus]], that accepts all valid programs at compilation time and risks [[false positives and false negatives#False negative error|false negative errors]], used in Lisp and its variants (such as [[Scheme (programming language)|Scheme]]), as they reject all invalid programs at runtime when the information is enough to not reject valid programs. The use of [[algebraic data type]]s makes manipulation of complex data structures convenient; the presence of strong compile-time type checking makes programs more reliable in absence of other reliability techniques like [[test-driven development]], while [[type inference]] frees the programmer from the need to manually declare types to the compiler in most cases.

Some research-oriented functional languages such as [[Coq (software)|Coq]], [[Agda (programming language)|Agda]], [[Lennart Augustsson|Cayenne]], and [[Epigram (programming language)|Epigram]] are based on [[intuitionistic type theory]], which lets types depend on terms. Such types are called [[dependent type]]s. These type systems do not have decidable type inference and are difficult to understand and program with.<ref>{{cite journal |last=Huet |first=Gérard P. |date=1973 |title=The Undecidability of Unification in Third Order Logic |journal=Information and Control |doi=10.1016/s0019-9958(73)90301-x |volume=22 |issue=3 |pages=257–267}}</ref><ref>{{cite thesis |type=Ph.D. |last=Huet |first=Gérard |date=Sep 1976 |title=Resolution d'Equations dans des Langages d'Ordre 1,2,...ω |language=fr |publisher=Universite de Paris VII}}</ref><ref>{{cite book |last=Huet |first=Gérard |date=2002 |editor1-last=Carreño |editor1-first=V. |editor2-last=Muñoz |editor2-first=C. |editor3-last=Tahar |editor3-first=S. |chapter=Higher Order Unification 30 years later |title=Proceedings, 15th International Conference TPHOL |volume=2410 |pages=3–12 |publisher=Springer |series=LNCS |chapter-url=http://pauillac.inria.fr/~huet/PUBLIC/Hampton.pdf}}</ref><ref>{{cite journal |first=J. B. |last=Wells |title=Typability and type checking in the second-order lambda-calculus are equivalent and undecidable |citeseerx=10.1.1.31.3590 |journal=Tech. Rep. 93-011 |year=1993 |pages=176–185}}</ref> But dependent types can express arbitrary propositions in [[higher-order logic]]. Through the [[Curry–Howard isomorphism]], then, well-typed programs in these languages become a means of writing formal [[mathematical proof]]s from which a compiler can generate [[formal verification|certified code]]. While these languages are mainly of interest in academic research (including in [[formalized mathematics]]), they have begun to be used in engineering as well. [[Compcert]] is a [[compiler]] for a subset of the language [[C (programming language)|C]] that is written in Coq and formally verified.<ref>{{cite web |url=http://compcert.inria.fr/doc/index.html |title=The Compcert verified compiler |last1=Leroy|first1=Xavier|date=17 September 2018}}</ref>

A limited form of dependent types called [[generalized algebraic data type]]s (GADT's) can be implemented in a way that provides some of the benefits of dependently typed programming while avoiding most of its inconvenience.<ref>{{cite journal |url=http://research.microsoft.com/en-us/um/people/simonpj/papers/gadt/ |title=Simple unification-based type inference for GADTs |first1=Simon |last1=Peyton Jones |first2=Dimitrios |last2=Vytiniotis |first3=Stephanie |last3=Weirich |author3-link= Stephanie Weirich |author4=Geoffrey Washburn |journal=Icfp 2006 |pages=50–61 |date=April 2006}}</ref> GADT's are available in the [[Glasgow Haskell Compiler]], in [[OCaml]]<ref>{{Cite web|title=OCaml Manual|url=https://caml.inria.fr/pub/docs/manual-ocaml/gadts.html|access-date=2021-03-08|website=caml.inria.fr}}</ref> and in [[Scala (programming language)|Scala]],<ref>{{Cite web|title=Algebraic Data Types|url=https://docs.scala-lang.org/scala3/book/types-adts-gadts.html|access-date=2021-03-08|website=Scala Documentation}}</ref> and have been proposed as additions to other languages including Java and C#.<ref>{{cite conference |title=Generalized Algebraic Data Types and Object-Oriented Programming |first1=Andrew |last1=Kennedy |first2=Claudio V. |last2=Russo |conference=OOPSLA |date=October 2005 |publisher=[[Association for Computing Machinery|ACM]] |location=San Diego, California |url=https://www.microsoft.com/en-us/research/publication/generalized-algebraic-data-types-and-object-oriented-programming/ |archive-url=https://web.archive.org/web/20061229164852/http://research.microsoft.com/~akenn/generics/gadtoop.pdf |archive-date=2006-12-29 |doi=10.1145/1094811.1094814 |isbn=9781595930316}}</ref>

=== Referential transparency ===
{{Main|Referential transparency}}
Functional programs do not have assignment statements, that is, the value of a variable in a functional program never changes once defined. This eliminates any chances of side effects because any variable can be replaced with its actual value at any point of execution. So, functional programs are referentially transparent.<ref>{{cite web|last1=Hughes |first1=John |title=Why Functional Programming Matters |url=http://www.cse.chalmers.se/~rjmh/Papers/whyfp.pdf |publisher=[[Chalmers University of Technology]]}}</ref>

Consider [[C (programming language)|C]] assignment statement <code>x=x*10</code>, this changes the value assigned to the variable <code>x</code>. Let us say that the initial value of <code>x</code> was <code>1</code>, then two consecutive evaluations of the variable <code>x</code> yields <code>10</code> and <code>100</code> respectively. Clearly, replacing <code>x=x*10</code> with either <code>10</code> or <code>100</code> gives a program a different meaning, and so the expression ''is not'' referentially transparent. In fact, assignment statements are never referentially transparent.

Now, consider another function such as <syntaxhighlight lang="c" inline>int plusone(int x) {return x+1;}</syntaxhighlight> ''is'' transparent, as it does not implicitly change the input x and thus has no such [[side effect (computer science)|side effects]].
Functional programs exclusively use this type of function and are therefore referentially transparent.

===Data structures===
{{main|Purely functional data structure}}
Purely functional [[data structure]]s are often represented in a different way to their [[imperative programming|imperative]] counterparts.<ref>[http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/purely-functional-data-structures ''Purely functional data structures''] by [[Chris Okasaki]], [[Cambridge University Press]], 1998, {{ISBN|0-521-66350-4}}</ref> For example, the [[array data structure|array]] with constant access and update times is a basic component of most imperative languages, and many imperative data-structures, such as the [[hash table]] and [[binary heap]],  are based on arrays. Arrays can be replaced by [[Map (computer science)|maps]] or random access lists, which admit purely functional implementation, but have [[logarithm]]ic access and update times. Purely functional data structures have [[Persistent data structure|persistence]], a property of keeping previous versions of the data structure unmodified. In Clojure, persistent data structures are used as functional alternatives to their imperative counterparts. Persistent vectors, for example, use trees for partial updating. Calling the insert method will result in some but not all nodes being created.<ref>{{Cite web|url=http://www.hypirion.com/musings/understanding-persistent-vector-pt-1|title=polymatheia - Understanding Clojure's Persistent Vector, pt. 1 |last=L’orange |first=Jean Niklas |website=Polymatheia |access-date=2018-11-13}}</ref>