Is (Probabilistic) Non-Determinism Pure ?

What exactly is a purely functional programming language? Here is the Wikipedia definition of a pure function:

In computer programming, a function may be described as pure if both these statements about the function hold:

  1. The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change as program execution proceeds or between different executions of the program, nor can it depend on any external input from I/O devices.
  2. Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.

The result value need not depend on all (or any) of the argument values. However, it must depend on nothing other than the argument values.

Note the sentence that I deleted from the original Wikipedia definition. Let us call a function that obeys all of the above definition (including the deleted sentence) strongly pure, and a function that obeys all of the above definition except maybe the deleted sentence weakly pure.

The two functions random and choice cannot be considered strongly pure. Let us look at these two functions. The meaning of “choice a b” is to return a or b. In particular, sometimes it might return a, sometimes it might return b when called. Similarly, the meaning of “random a b” is to randomly return a or b, giving both a and b equal chances of getting returned.

But can these functions be considered weakly pure ? IMHO, the answer is yes. Both functions do not exhibit any side effects, do not depend on hidden state, and do not depend on anything else than their arguments. Note that nevertheless some people might refuse to call choice or random even only weakly pure, because they will not separate the abstract semantics of a function from its practical implementation. For example, how would you implement random for a real language running on a real computer? Two real-world implementations are in use:

  1. A pseudo random number generator. The current seed of the pseudo number generator can be viewed as hidden state / additional argument, making random not even weakly pure.
  2. An extra device is used which generates random numbers based on certain physical stochastic processes. Using such a device clearly violates the “no I/O” part of weakly pure.

Weakly pure functions are not necessarily referentially transparent. What implications does this have? Two things come to mind:

  1. Caching (memoizing) a weakly pure function can change the meaning of that function. Note that while caching weakly pure functions which rely only on choice is perfectly fine (but may reduce the number of possible outcomes of this function), caching a weakly pure function which also relies on random generally changes the meaning of that function.
  2. Reasoning about weakly pure functions is harder because the application of a function cannot simply be replaced by its result.

The first issue cannot be helped; but is there any reason why it should be helped?

It seems that the second issue can be dealt with. Because if weakly pure functions do not have side effects, and do only depend on their arguments, it should be possible to replace reasoning about a weakly pure function by reasoning about an induced strongly pure function with a lifted result range. Instead of reasoning about “choice a b” one could reason about “Choice a b”, where “Choice a b” evaluates to the set “{a, b}”. And instead of reasoning about “random a b” one could reason about “Random a b” where “Random a b” evaluates to the measure “(50% : a, 50% : b)”. Of course all weakly pure functions in a functional program then need to be lifted that way, even those which were strongly pure to begin with. And because the output of one function is the input of another, not only the result range of all functions would need lifting, but also the input domain. It is not clear if this is always possible, and deserves more thought.

Note that an important aspect of strong purity is preserved even by weak purity: weakly pure functions are particularly well suited for parallelization on multi-core and distributed computers.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: