Purely functional programming

In computer science, purely functional programming usually designates a programming paradigm—a style of building the structure and elements of computer programs—that treats all computation as the evaluation of mathematical functions. Purely functional programming may also be defined by forbidding changing-state and mutable data.

Programming paradigms

Purely functional programming consists of ensuring that functions, inside the functional paradigm, will only depend on their arguments, regardless of any global or local state.

Difference between pure and not-pure functional programming

The exact difference between pure and impure functional programming is a matter of controversy.[1]

A program is usually said to be functional when it uses some concepts of functional programming, such as first-class functions and higher-order functions.[2] However, a first-class function need not be purely functional, as it may use techniques from the imperative paradigm, such as arrays or input/output methods that are not purely functional programs. In fact, the earliest programming languages cited as being functional, IPL and Lisp,[3][4] were both "impure" functional languages by the current definition.

Purely functional data structures are persistent. Persistency is required for functional programming; without it, the same computation could return different results. Functional programming may use persistent non-purely functional data structures, while those data structures may not be used in purely functional programs.

Properties of purely functional programming

Strict versus non-strict evaluation
Main article: Evaluation strategy

Each evaluation strategy 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 eager evaluation will return the same result as lazy evaluation. 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.

Parallel computing

Purely functional programming simplifies parallel computing[5] since two purely functional parts of the evaluation never interact.

Data structures
Main article: Purely functional data structure

Purely functional data structures are often represented in a different way than their imperative counterparts.[6] For example, array with constant-time access and update is a basic component of most imperative languages and many imperative data-structures, such as hash table and binary heap, are based on arrays. Arrays can be replaced by map or random access list, which admits purely functional implementation, but the access and update time is logarithmic. 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.

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 store-passing style.

Purely functional language
For a more comprehensive list, see List of programming languages by type § Pure.

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.

gollark: I might have already, I forgot.
gollark: Very advanced.
gollark: Analog quantum computers simulating truth cuboid hardware, in real time.
gollark: They are already quantum.
gollark: ddg! Trie (data structure)

References
  1. Sabry, Amr (January 1993). "What is Purely Functional Language ?". Journal of Functional Programming. 8 (1): 1–22. CiteSeerX 10.1.1.27.7800. doi:10.1017/S0956796897002943.
  2. Atencio, Luis (18 June 2016). Functional Programming in Javascript. Manning Publications. ISBN 978-1617292828.
  3. 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.
  4. McCarthy, John (June 1978). "History of Lisp". In ACM SIGPLAN History of Programming Languages Conference: 217–223. doi:10.1145/800025.808387.
  5. Marlow, Simon (18 June 2013). Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming. O'Reilly Media. ISBN 978-1449335946.
  6. Purely functional data structures by Chris Okasaki, Cambridge University Press, 1998, ISBN 0-521-66350-4
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.