Summary
I am examing the meaning of purity with regards to functions in an attempt to close the gap between imperative and functional languages.

---

Advertisement

Previously I was uing the terms "clean" and "dirty" but the terms "pure" and "impure" are perhaps more standard and understandable. Here I attempt to clarify the meaning of purity and impurity, and how I am dealing with it.

A pure function is one which has no side-effects and does not depend on any state beyond its local scope. This means that it can be replaced with any other pure function which returns the same result given the same input. This property is often referred to as referential transparency.

Consider the following psuedo-code:

  def pure_f(x) = { return x + 1; }
  def impure_f(x) = { Console.WriteLine(x); return x + 1; }

Now consider the following function:

  def pure_g(list) = { return map(list, pure_f); }
  def impure_g(list) = { return map(list, impure_f); }

Note: A map function generates a list from another list by applying a function to each member of the original list.

The conundrum is that if we don't distinguish between the uses of map in these contexts then we are stuck having to implement map in an order-dependant way.

I am trying to bridge the gap in the Cat language. My solution is to use purity labeling which is similar to const labeling in C++. It has some parallels to Haskell monads, Clean uniqueness and escape analysis.

In Cat there are only functions. Functions all share a global stack. They take their parameters from the top of the shared stack, and return their results on the top of the shared stack. Local variables are emulated by simply pushing and popping values from the top of the stack. The local scope of a function is the part of the stack above, and including, the lowest value it observes or manipulates on the shared stack.

A Cat function is pure iff takes a constant number of parameters from the top of the stack, it returns a constant number of results to the top of the stack, and it has no side-effects. Some of the primitives of Cat are pure, while others aren't. It is easy enough, for the compiler to identify an impure function. If a function contains an impure function, then it is impure.

Some cat primitive functions (such as map, ifthen, or whiledo) operate on other functions, in these cases there needs to be overloaded versions of the functions: a pure version and an impure version. Returning to the map problem, the proposed Cat solution, is that depending on the type of the second parameter (i.e. is it a pure function or an impure function) then either a pure_map or impure_map is chosen by the compiler. The pure version of map is order independant, and as such is easily optimized, and easily parallelized (which supports my earlier post ).

Postscript

As Jules Jacobs pointed out, some impure functions, can become pure when they are passed constant values.

Talk Back!

Have an opinion? Readers have already posted 14 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever Christopher Diggins adds a new entry to his weblog, subscribe to his RSS feed.

Digg | del.icio.us | Reddit

About the Blogger

Christopher Diggins is a software developer and freelance writer. Christopher loves programming, but is eternally frustrated by the shortcomings of modern programming languages. As would any reasonable person in his shoes, he decided to quit his day job to write his own ( www.heron-language.com ). Christopher is the co-author of the C++ Cookbook from O'Reilly. Christopher can be reached through his home page at www.cdiggins.com.