Channels ▼

Walter Bright

Dr. Dobb's Bloggers

Pure Functions

September 21, 2008

Pure functions have some interesting and useful properties. A pure function is one that only depends on its parameters, and its only output is its return value. In the D programming language, the requirements specifically are:

  • Global variables (or any variables that persist outside of the scope of the function) cannot be written to.
  • Such variables cannot be read from, either, unless they are invariant.
    (Invariant means immutable.)
  • Pure functions can only call other pure functions.
  • Parameters to a pure function can be mutable, but calls cannot be cached or executed asynchronously if the arguments contain any references to mutable data.
  • A pure function can throw an exception (purity does not imply nothrow).

An example of a pure function in D is:

  pure int foo(int x, const int[] a)
  {
     int sum = 0;
     foreach (s; a)
         sum += s;     // mutable non-static local variables are allowed
     return x * sum;
  }

An impure function:

  int bar(int x, int[] a)
  {  static int sum = 0;
      foreach (s; a)   // reference to mutable array contents
        sum += s;     // read/write to mutable persistent variable
     return x * sum;  // read of mutable persistent variable
  }


These properties can be checked at compile time if the function is typed as being pure. A common question is that if the compiler can check to see if a function is pure, why annotate the function? Why not just let the compiler check for purity, and if so, then accrue the advantages of purity? The answer is that purity is a property the programmer needs to know about. If purity was inferred rather than specified, a seemingly innocuous change in one function can make it impure, and every function that calls it impure, etc. There will be no reasonable way for the programmer who expects a function to be pure, to see if it actually is pure. If he does check (which might be arbitrarilly difficult to do) and it is not pure, he has no reasonable way to determine why the compiler thought it was impure.

So now that we have pure functions, what are they good for?

The first is self-documentation. A person trying to understand a code base, once they see that a function is pure, they know it only depends on its arguments, has no side effects, and there's no monkey business going on inside it. This greatly reduces the cognitive load of dealing with it. A big chunk of functions can be marked as pure, and just this benefit alone is enough to justify supporting it.

Pure functions do not require synchronization for use by multiple threads, because their data is all either thread local or immutable.

Common subexpression elimination is an important compiler optimization, and with pure functions this can be extended to cover them, so:

    int x = foo(3) + bar[foo(3)];

need only execute foo(3) once.

User level code can take this further by noting that the result of a pure function depends only on the bits passed to it on the stack (as the transitivity of invariants guarantees the constancy of anything they may refer to). Those bits can therefore be used as a key to access memoized results of the function call, rather than calling the function again.

Pure functions can be executed asynchronously. This means that not only can the function be executed lazily, it can also be farmed out to another core (this will become increasingly important as more cores become commonplace).

They can be hot swapped (meaning replaced at runtime), because they do not rely on any global initialization or termination state.

Functional programming capability is an exciting addition to imperative programming languages.

Further reading:

"Grafting Functional Support on Top of an Imperative Language" http://www.digitalmars.com/d/2.0/accu-functional.pdf is Andrei Alexandrescu's explanation of how functional purity works in the D programming language.


"Verifiable Functional Purity in Java" http://www.cs.berkeley.edu/~daw/papers/pure-ccs08.pdf shows how pure functions could be added to Java.

Thanks to Andrei Alexandrescu and Bartosz Milewski for reviewing this.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video