Pure function

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computer programming, a function is considered pure if it has two properties:[1][2]

  1. its return value depends only on its parameters and not on any internal or external state (such as local static variables, non-local variables or inputs from I/O devices);
  2. its evaluation has no side effect (such as mutation of local static variables or non-local variables, or performing I/O operations).

Thus a pure function is a computational analogue of a mathematical function. Some authors, particularly from the imperative language community, use the term "pure" for all functions that just have property 2[3][4] (discussed below). Other authors use "pure" in an even different sense.

Examples

Pure functions

  • sin(x), returning the sine of a number x.

Impure functions

  • time(nullptr), because it depends on a global calendar time.
  • rand(), because each call uses a pseudorandom generators that reads and updates a global seed. If we modify it to take the seed as an argument, i.e. rand(seed), then the function becomes pure as it has no side effect anymore.
  • printf(s), because it performs I/O as a side effect.

I/O in pure functions

I/O is inherently impure: input operations undermine referential transparency, and output operations create side effects. Nevertheless, there is a sense in which function can perform input or output and still be pure, if the sequence of operations on the relevant I/O devices is modeled explicitly as both an argument and a result, and I/O operations are taken to fail when the input sequence does not describe the operations actually taken since the program began execution.

The second point ensures that the only sequence usable as an argument must change with each I/O action; the first allows different calls to an I/O-performing function to return different results on account of the sequence arguments having changed.[5][6]

The I/O monad is a programming idiom typically used to perform I/O in pure functional languages.

Pure expressions

It is possible for a pure expression to yield an impure function (or more generally a value which contains one or more impure functions). For example, the C expression ( b ? rand : time) is pure, since neither of the two impure functions is actually called.

It is also possible for a pure expression to have one or more of the argument subexpressions yield an impure function (or a value which contains one or more impure functions). In this case the impure function(s) in the argument must not be applied during evaluation (but may be incorporated in the result somehow).

However, dealing with programs that allow impure and pure functions to be mixed like this can be quite difficult in practice, thus purely functional programming languages do not allow impure functions to be defined. Effect systems, among other things, allow one to reason precisely and formally about the purity of certain expressions even in the presence of higher-order functions etc.; they even allow to prove that a certain function does not have any side effects although it uses impure operations (for example, uses a mutable array for computation internally, but does not maintain its state between invocations).

Side-effect free functions

Functions that have just the above property 2 allow for compiler optimization techniques such as common subexpression elimination and loop optimization similar to arithmetic operators.[3] Examples include:

Both examples depend on the memory contents where s points to, therefore they don't have the above property 1. Nevertheless, in a single-threaded environment, e.g. the code

int lg = 0; 
for (int i=0; i<n; ++i) 
    lg += length(s) + length(t[i]);

can be optimized such that the value of length(s) is computed only once, before the loop.

In some C and Fortran dialects, the keyword "pure" can be used to declare a function to be just side-effect free (i.e. have just the above property 2). The keyword "const" can be used in C to declare a function to have properties 1 and 2 (i.e. to be pure in the sense used in this article); such functions are subject to common subexpression elimination and loop optimization even in multi-threaded environments.

See also

References

  1. ^ Bartosz Milewski (2013). "Basics of Haskell". School of Haskell. FP Complete. Retrieved 2018-07-13. Here are the fundamental properties of a pure function: 1. A function returns exactly the same result every time it's called with the same set of arguments. In other words a function has no state, nor can it access any external state. Every time you call it, it behaves like a newborn baby with blank memory and no knowledge of the external world. 2. A function has no side effects. Calling a function once is the same as calling it twice and discarding the result of the first call. 
  2. ^ Brian Lonsdorf (2015). "Professor Frisby's Mostly Adequate Guide to Functional Programming". GitBook. Retrieved 2018-07-14. A pure function is a function that, given the same input, will always return the same output and does not have any observable side effect. 
  3. ^ a b "GCC 8.1 Manual". GCC, the GNU Compiler Collection. Free Software Foundation, Inc. 2018. Retrieved 2018-06-28. 
  4. ^ Fortran 95 language features#Pure Procedures
  5. ^ Peyton Jones, Simon L. (2003). Haskell 98 Language and Libraries: The Revised Report (PDF). Cambridge, United Kingdom: Cambridge University Press. p. 95. ISBN 0-521 826144. Retrieved 17 July 2014. 
  6. ^ Hanus, Michael. "Curry: An Integrated Functional Logic Language" (PDF). http://www-ps.informatik.uni-kiel.de/currywiki/. Institut für Informatik, Christian-Albrechts-Universität zu Kiel. p. 33. Retrieved 17 July 2014.  External link in |website= (help)

External links

  • Pure attribute in Fortran
  • constexpr attribute in C++
  • Pure attribute in D language
Retrieved from "https://en.wikipedia.org/w/index.php?title=Pure_function&oldid=850500376"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Pure_function
This page is based on the copyrighted Wikipedia article "Pure function"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA