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; }

  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.

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