Purely functional - Definition and Overview

Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications (updates). As a consequence of this restriction, variables refer to immutable, persistent values. This means that old values available prior to a change continue to be accessible and may be updated following a modification.

Such persistence can be advantageous in the development of many applications. Moreover, the inherent referential transparency tends to make purely functional computation more amenable to analysis, both formal and informal.

Since every value in an purely functional computation is built up out of existing values, it would seem that it were impossible to create a cycle of references, resulting in an reference graph (a graph which has edges from objects to the objects they reference) that is a directed acyclic graph. However, this is not true. Even under eager evaluation, functions can be defined recursively, referring to themselves. And under lazy evaluation, even regular data structures can be defined self-referentially.