Pure functions in D

[Sergey Gromov]

Sun, 28 Sep 2008 07:28:19 +0900,
Bill Baxter wrote:
> But I think a stack overflow is something that doesn't usually occur
> in a properly written program, and they are also are not something you
> can recover from.  Insufficient memory errors can be and often are
> recovered from.   E.g. you try to create a giant image in an image
> editing program, if there's not enough memory your image editor
> *should* realize the image alloc failed and bail out gracefully
> telling you there's not enough memory for that operation.

My thoughts so far.

Since a real purity is unachievable, there are different grades of 
purity which make a practical difference:

A. Independence of an external state in the sense that a pure function 
can be executed in parallel without the need for synchronization.  This 
is the simplest, most obvious and a must have kind of purity.  It also 
allows for an arbitrary execution order of functions with independent 
arguments and results.  Even malloc() conforms to this kind of purity 
because memory management is thread-safe at the low level anyway so it 
can be executed in parallel without compiler taking additional 
precautions.

B. Repeatability of the result that allows to cache parameters and reuse 
the same result if the same parameters are given.  This type of purity 
is way stricter than the first and is harder to check and utilize.

What happens if an exception is thrown?

Purity of type A is perfectly preserved.  Naturally, an exception can 
happily be thrown in parallel and in any order.  Purity of type B can 
also be preserved if an exception is thrown consistently with function 
parameters and compiler is able to prove that.  If another kind of 
exception is thrown, the purity B is broken.

What does it mean, broken purity?  It means that any results of a B-pure 
computation are invalid and must be discarded.  I think that a smart 
compiler should catch exceptions from B-pure functions and, if an 
exception is unexpected, wrap them in a PurityError exception which B-
pure functions must never catch.  Yet this exception does no harm to the 
purity of A-pure functions and can be handled there.

Now to exception handling.  Any exceptions from A-pure functions and 
selected exceptions from B-pure functions are considered the function 
result.  Therefore

try {
  localState = pureFun();
} catch(...) {
  localState = ...
}

is a valid pure statement, it can be executed in parallel and in any 
order with the surrounding statements and localState can be completely 
replaced with a cached or pre-computed value if pureFunc is B-pure.  
This is actually valid for any try-catch statement with an important 
note: the statements inside the try block can never be executed in 
parallel to each other, though B-pure functions still can be replaced 
with their cached values/exceptions.  Also a try-catch block in a B-pure 
function can never catch a PurityError.

The image creation routine in your example is A-pure because it creates 
new image every time it is called with the same arguments.  It can 
safely throw OutOfMemory which you catch and report to the user via 
something completely unpure.