Pure function
Encyclopedia
In computer programming
, a function may be described as pure if both these statements about the function hold:
The result value need not depend on all (or any) of the argument values. However, it must depend on nothing other than the argument values. The function may return multiple result values and these conditions must apply to all returned values for the function to be considered pure. If an argument is call by reference it is considered to be a combination of one argument and one return value and so the argument will get overwritten; because of this call by reference will make an expression impure even if the function called is pure.
s. Constant expressions are pure by definition. An expression consisting of a function subexpression applied to one or more argument subexpressions is pure if both these statements about the subexpressions hold:
Typically the function subexpression is simply a function identifier. Pure expressions are often referred to as being referentially transparent.
Evaluation of a given pure expression will yield the same result regardless of when or how many times evaluation occurs during program execution. This property is what makes it meaningful to talk about an expression's "value". It also makes it possible to replace an expression with the corresponding value (or it with an equivalent alternative expression) without changing the meaning of a program.
It is also possible for an expression to be pure even if one or more of the argument subexpressions yields 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 system
s, 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 expose it to the outer world or maintain its state between invocations).
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
, a function may be described as pure if both these statements about the function hold:
- The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or stateProgram stateOne of the key concepts in computer programming is the idea of state, essentially a snapshot of the measure of various conditions in the system. Most programming languages require a considerable amount of state information in order to operate properly - information which is generally hidden from...
that may change as program execution proceeds or between different executions of the program, nor can it depend on any external input from I/OInput/outputIn computing, input/output, or I/O, refers to the communication between an information processing system , and the outside world, possibly a human, or another information processing system. Inputs are the signals or data received by the system, and outputs are the signals or data sent from it...
devices. - Evaluation of the result does not cause any semantically observable side effectSide effect (computer science)In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
or output, such as mutation of mutable objects or output to I/O devices.
The result value need not depend on all (or any) of the argument values. However, it must depend on nothing other than the argument values. The function may return multiple result values and these conditions must apply to all returned values for the function to be considered pure. If an argument is call by reference it is considered to be a combination of one argument and one return value and so the argument will get overwritten; because of this call by reference will make an expression impure even if the function called is pure.
Pure functions
-
sin(x), returning the sineSineIn mathematics, the sine function is a function of an angle. In a right triangle, sine gives the ratio of the length of the side opposite to an angle to the length of the hypotenuse.Sine is usually listed first amongst the trigonometric functions....
of a number x -
length(s), returning the size of a string s -
encrypt(k,d), running an encryption algorithm on a piece of data d using a keyKey (cryptography)In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
k
Impure functions
- A hypothetical function
todaythat returns the current day of the week is impure because at different times it will yield different results—it refers to some global state. Similarly, any function that uses global state or a static variable is potentially impure. -
randomis impure because each call potentially yields a different value. (This is because pseudorandom generatorPseudorandom generatorIn theoretical computer science, a pseudorandom generator is a deterministic procedure that produces a pseudorandom distribution from a short uniform input, known as a random seed.-Definition:...
s use and update a global "seed" state. If we modify it to take the seed as an argument, i.e.random(seed); thenrandombecomes pure, because multiple calls with the same seed value return the same random number.) -
printfis impure because it causes output to an I/O device as a side effect.PrintfPrintf format string refers to a control parameter used by a class of functions typically associated with some types of programming languages. The format string specifies a method for rendering an arbitrary number of varied data type parameter into a string...
Pure expressions
Pure functions are required to construct pure expressionExpression (programming)
An expression in a programming language is a combination of explicit values, constants, variables, operators, and functions that are interpreted according to the particular rules of precedence and of association for a particular programming language, which computes and then produces another value...
s. Constant expressions are pure by definition. An expression consisting of a function subexpression applied to one or more argument subexpressions is pure if both these statements about the subexpressions hold:
- The function and argument subexpressions are pure expressions.
- The function subexpression yields a pure function.
Typically the function subexpression is simply a function identifier. Pure expressions are often referred to as being referentially transparent.
Evaluation of a given pure expression will yield the same result regardless of when or how many times evaluation occurs during program execution. This property is what makes it meaningful to talk about an expression's "value". It also makes it possible to replace an expression with the corresponding value (or it with an equivalent alternative expression) without changing the meaning of a program.
Impure functions in pure expressions
The definitions above still allow some laxity with regard to purity. It is possible for a pure expression to yield an impure function (or more generally a value which contains one or more impure functions).It is also possible for an expression to be pure even if one or more of the argument subexpressions yields 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
Purely functional
Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications...
programming languages do not allow impure functions to be defined. Effect system
Effect system
An effect system is a formal system which describes the computational effects of computer programs, such as side effects. An effect system can be used to provide a compile-time checking of the possible effects of the program....
s, 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 expose it to the outer world or maintain its state between invocations).
See also
- Purely functionalPurely functionalPurely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications...
- Referential transparency (computer science)
- Lambda calculusLambda calculusIn mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
- Side effect (computer science)Side effect (computer science)In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
- IdempotenceIdempotenceIdempotence is the property of certain operations in mathematics and computer science, that they can be applied multiple times without changing the result beyond the initial application...