Pure not acting pure.

[Jonathan M Davis]

On 2011-06-15 17:38, Charles McAnany wrote:
> Hi, all. I'm implementing a little linked list that selection-sorts itself.
> Basically, the sort code is: swap this element with the minimum element in
> the list.
> sort the rest of the list.
> 
> Obviously, one part of this is swapping elements. It seemed easiest to swap
> the contents of two nodes, rather than messing with rearranging the
> elements.
> Now, that description of swap sounds impure, right? But this compiles:
> private pure void swap(SortableListNode other){ //SortableListNode is a
> class. T temp = this.datum;
> 	this.datum = other.datum;
> 	other.datum = temp;
> }
> Am I missing the point of pure somehow? Am I going crazy? (The sort does
> work, so the elements are being mutated.)

There are two types of pure functions: weakly pure and strongly pure. Pure 
functions (of either variety) cannot access mutable global variables. Any pure 
function can be called from any other pure function, but you can't call impure 
functions from pure functions. Strongly pure functions are pure functions 
whose parameters are either immutable or implicitly convertible to immutable. 
Calls to strongly pure functions can be optimized out within an expression. 
For instance, something like

5 * abs(a) * abs(a)

would only call abs once and would just use the result of the first call again 
rather than making a second function call. Calls to weakly pure functions, on 
the other hand, cannot be optimized out. This is because they can affect the 
state of their arguments and each call to them could have differing results. 
However, because they can only affect the state of their arguments and not any 
global state, they're safe to call from within strongly pure functions.

The function that you have there is weakly pure. Its argument is a mutable 
reference, which cannot be implicitly convertible to immutable, so calls to it 
cannot be optimized out. However, it _can_ be called from a strongly pure 
function.

Originally, all we had were strongly pure functions, but they were far too 
limiting, because so few functions can be strongly pure. So, weakly pure 
functions were introduced, which makes it possible to make many more functions 
strongly pure.

- Jonathan M Davis