Purely functional programming

<h2 id="difference-between-pure-and-impure-functional-programming">Difference between pure and impure functional programming</h2>
<p>The exact difference between pure and impure functional programming is a matter of controversy. Sabry's proposed definition of purity is that all common <a href="/facts/Evaluation_strategy/Pc9kLWgs">evaluation strategies</a> (call-by-name, call-by-value, and call-by-need) produce the same result, ignoring strategies that error or diverge.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p><p>A program is usually said to be functional when it uses some concepts of <a href="/facts/Functional_programming/cdxqPEIM">functional programming</a>, such as <a href="/facts/First-class_function/dtMzp81k">first-class functions</a> and <a href="/facts/Higher-order_function/VjnjGbpt">higher-order functions</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> However, a first-class function need not be purely functional, as it may use techniques from the <a href="/facts/Imperative_programming/6b5dUnE1">imperative</a> paradigm, such as <a href="/facts/Array_data_structure/BKGvF8AM">arrays</a> or input/output <a href="/facts/Method_(computer_programming)/8kAXxVYs">methods</a> that use mutable cells, which update their state as side effects. In fact, the earliest programming languages cited as being functional, <a href="/facts/Information_Processing_Language/06CVyAF4">IPL</a> and <a href="/facts/Lisp_(programming_language)/xJHA3CrX">Lisp</a>,<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> are both "impure" functional languages by Sabry's definition.
</p>
<h2 id="properties-of-purely-functional-programming">Properties of purely functional programming</h2>
<h3>Strict versus non-strict evaluation</h3>
<p class="note">Main article: <a href="/facts/Evaluation_strategy/Pc9kLWgs">Evaluation strategy</a></p>
<p>Each <a href="/facts/Evaluation_strategy/Pc9kLWgs">evaluation strategy</a> which ends on a purely functional program returns the same result. In particular, it ensures that the programmer does not have to consider in which order programs are evaluated, since <a href="/facts/Eager_evaluation/vLXH27zR">eager evaluation</a> will return the same result as <a href="/facts/Lazy_evaluation/mD3DxDkc">lazy evaluation</a>. However, it is still possible that an eager evaluation may not terminate while the lazy evaluation of the same program halts.
An advantage of this is that lazy evaluation can be implemented much more easily; as all expressions will return the same result at any moment (regardless of program state), their evaluation can be delayed as much as necessary.
</p>
<h3>Parallel computing</h3>
<p>In a purely functional language, the only dependencies between computations are data dependencies, and computations are deterministic. Therefore, to program in parallel, the programmer need only specify the pieces that should be computed in parallel, and the runtime can handle all other details such as distributing tasks to processors, managing synchronization and communication, and collecting garbage in parallel. This style of programming avoids common issues such as race conditions and deadlocks, but has less control than an imperative language.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p><p>To ensure a speedup, the granularity of tasks must be carefully chosen to be neither too big nor too small. In theory, it is possible to use runtime profiling and compile-time analysis to judge whether introducing parallelism will speed up the program, and thus automatically parallelize purely functional programs. In practice, this has not been terribly successful, and fully automatic parallelization is not practical.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p>
<h3>Data structures</h3>
<p class="note">Main article: <a href="/facts/Purely_functional_data_structure/sV5TBGqB">Purely functional data structure</a></p>
<p><a href="/facts/Purely_functional_data_structure/sV5TBGqB">Purely functional data structures</a> are <a href="/facts/Persistent_data_structure/K7IpHlkR">persistent</a>. Persistency is required for functional programming; without it, the same computation could return different results. Functional programming  may use persistent non-purely functional <a href="/facts/Data_structure/yNsNvL1I">data structures</a>, while those data structures may not be used in purely functional programs.
</p><p>Purely functional <a href="/facts/Data_structure/yNsNvL1I">data structures</a> are often represented in a different way than their <a href="/facts/Imperative_programming/6b5dUnE1">imperative</a> counterparts.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> For example,  <a href="/facts/Array_data_structure/BKGvF8AM">array</a>  with constant-time access and update is a basic component of most imperative languages and many imperative data-structures, such as <a href="/facts/Hash_table/Ht4ptDPF">hash table</a> and <a href="/facts/Binary_heap/YPJAEN94">binary heap</a>,  are based on arrays. Arrays can be replaced by <a href="/facts/Map_(computer_science)/IFGd2xcP">map</a> or random access list, which admits purely functional implementation, but the  access and update time is <a href="/facts/Logarithm/QeXaV97q">logarithmic</a>. Therefore, purely functional data structures can be used in languages which are non-functional, but they may not be the most efficient tool available, especially if persistency is not required.
</p><p>In general, conversion of an imperative program to a purely functional one also requires ensuring that the formerly-mutable structures are now explicitly returned from functions that update them, a program structure called <a href="/facts/Store-passing_style/ADbqhbPC">store-passing style</a>.
</p>
<h2 id="purely-functional-language">Purely functional language</h2>
<p class="note">For a more comprehensive list, see <a href="/facts/List_of_programming_languages_by_type/XuWNoawk">List of programming languages by type § Pure</a>.</p>
<p>A purely functional language is a language which only admits purely functional programming. Purely functional programs can however be written in languages which are not purely functional.
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Sabry, Amr (January 1993). "What is a purely functional language?". Journal of Functional Programming. 8 (1): 1–22. CiteSeerX 10.1.1.27.7800. doi:10.1017/S0956796897002943. S2CID 30595712. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Atencio, Luis (18 June 2016). Functional Programming in Javascript. Manning Publications. ISBN 978-1617292828. <a href="978-1617292828" target="_blank">978-1617292828</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>The memoir of Herbert A. Simon (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 claims that he, Al Newell, and Cliff Shaw are "commonly adjudged to be the parents of [the] artificial intelligence [field]", for writing Logic Theorist, a program which proved theorems from Principia Mathematica automatically. In order to accomplish this, they had to invent a language and a paradigm which, which viewed retrospectively, embeds functional programming. <a href="/wiki/Herbert_A._Simon" target="_blank">/wiki/Herbert_A._Simon</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>McCarthy, John (June 1978). "History of LISP". The first ACM SIGPLAN conference on History of programming languages - HOPL-1. pp. 217–223. doi:10.1145/800025.808387. <a href="/wiki/John_McCarthy_(computer_scientist)" target="_blank">/wiki/John_McCarthy_(computer_scientist)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Marlow, Simon (18 June 2013). Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming. O'Reilly Media. pp. 5–6. ISBN 978-1449335946. <a href="978-1449335946" target="_blank">978-1449335946</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Marlow, Simon (18 June 2013). Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming. O'Reilly Media. pp. 5–6. ISBN 978-1449335946. <a href="978-1449335946" target="_blank">978-1449335946</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Purely functional data structures by Chris Okasaki, Cambridge University Press, 1998, ISBN 0-521-66350-4 <a href="http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/purely-functional-data-structures" target="_blank">http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/purely-functional-data-structures</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
</ol>

Purely functional programming open-in-new

Purely functional programming