Functional programming: Encyclopedia II - Functional programming - Pure functions

Functional programming - Pure functions

Purely functional programs have no side-effects. Since functions do not modify state, no data may be changed by parallel function calls. For this reason, pure functions are always thread-safe, a fact which is exploited by languages that use call-by-future evaluation. Because ordering of side-effects does not have to be preserved in their absence, some languages (such as Haskell) use call-by-need evaluation for pure functions.

"Pure" functional programming languages typically enforce referential transparency, which is the notion that 'equals can be substituted for equals': if two expressions have "equal" values (for some notion of equality), then one can be substituted for the other in any larger expression without affecting the result of the computation. For example, in

    y = f(x) * f(x);

a compiler can factor out f(x) if it is pure, transforming the program to

    z = f(x);
    y = z * z;

and eliminating the second evaluation of the (possibly costly) call to f(x).

This optimization is called common subexpression elimination.

However, if a function has effects, the function call cannot be eliminated. Consider the following program fragment:

    y = random() * random();

The second call to random cannot be eliminated, because its return value may be different from that of the first call (the random function is not idempotent).

Similarly,

    y = printf("x") * printf("x");

cannot be optimized away; even if printf returns the same value both times, failing to make the second call would result in different program output.

Many modern compilers for imperative programming languages do not perform common subexpression elimination for function calls, because they do not track whether a function is pure. It is possible for an advanced compiler to infer whether a local function has effects and optimize accordingly; however, most pre-compiled libraries do not expose this information, preventing calls to external functions from being optimized away. Some compilers, such as gcc, add extra keywords for a programmer to explicitly mark pure functions so that this optimization can be performed.

Functional programming - Monads

Some functional languages remove or sandbox side-effects during evaluation using monads. In such languages, all functions become "pure"; the program's evaluation can then be reasoned about using traditional mathematical techniques, and common-subexpression elimination can be performed on all function calls. Because monadic functions depend on the monad values produced by previous function calls, multiple calls still cannot be eliminated; however, their sequencing is made explicit in the program.

Alternative methods (such as Hoare logic) have been developed to track effects in programs. Some modern research languages use effect systems to make explicit the presence of effects.

Adapted from the Wikipedia article "Pure functions", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki