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.)
Thanks,
Charles.

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

Ah, so does the compiler figure out which ones are strongly and weakly pure and then optimize as
appropriate? Is there a way to indicate that a function is strongly pure? Because it would seem odd
to call a function you thought was pure and wind up with a mutated argument.
-Charles

On 2011-06-15 20:29, Charles McAnany wrote:
> Ah, so does the compiler figure out which ones are strongly and weakly pure and then optimize as appropriate? Is there a way to indicate that a function is strongly pure? Because it would seem odd to call a function you thought was pure and wind up with a mutated argument. -Charles

It is not odd to have a function which is pure wind up with a mutated argument. All pure by itself does is indicate that the function cannot access mutable, global variables. That's it.

Now, extra calls to a strongly pure function can be optimized out within an expression, because it is not possible for a strongly pure function to alter its arguments, and so it is guaranteed to have the same result every time that it is called, and it is guaranteed to have no side effects. So, yes, calls to strongly pure can be optimized out.

What makes the difference between a weakly pure function and a strongly pure function is their parameters. All of the parameters of a strongly pure function are either immutable or implicitly convertible to mutable. The parameters of a weakly pure function can be anything (just so long as they aren't all immutable or implicitly convertible to immutable, since that would make the function strongly pure). The advantage to weakly pure functions over impure functions (aside from the guarantee that they don't alter the state of any global variables) is that they can be called by other pure functions. This makes it possible to have strongly pure functions which call all kinds of useful functions which may alter their arguments, because the arguments of the strongly pure function are never altered, and its return value is always the same.

- Jonathan M Davis

On 2011-06-15 23:29:46 -0400, Charles McAnany <mcanance@rose-hulman.edu> said:

> Ah, so does the compiler figure out which ones are strongly and weakly pure and then optimize as
> appropriate? Is there a way to indicate that a function is strongly pure? Because it would seem odd
> to call a function you thought was pure and wind up with a mutated argument.

Just make sure all the parameters are either const or immutable or passed by copy and do not contain any pointer or reference. That'll make the function strongly pure, and the compiler will be able optimize.

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

Michel Fortin:

> Just make sure all the parameters are either const or immutable or passed by copy and do not contain any pointer or reference. That'll make the function strongly pure, and the compiler will be able optimize.

I have just done a little test on this, currently DMD calls sqr one time in main() only if you add "nothrow" too:

pure nothrow int sqr(int x) { return x * x; }
int main() {
    enum int n = 10;
    immutable int r = sqr(n) + sqr(n);
    return r;
}

Bye,
bearophile

On Thu, 16 Jun 2011 06:52:45 -0400, Michel Fortin wrote:

> On 2011-06-15 23:29:46 -0400, Charles McAnany <mcanance@rose-hulman.edu> said:
> 
>> Ah, so does the compiler figure out which ones are strongly and weakly
>> pure and then optimize as
>> appropriate? Is there a way to indicate that a function is strongly
>> pure? Because it would seem odd
>> to call a function you thought was pure and wind up with a mutated
>> argument.
> 
> Just make sure all the parameters are either const or immutable or passed by copy and do not contain any pointer or reference. That'll make the function strongly pure, and the compiler will be able optimize.

If you want a strongly pure function, the parameters need to be immutable or implicitly convertible to immutable.  const references may be mutated elsewhere.

-Lars

Ok, I think I get it. That cleared it up. =).
So, if you have a functioned labelled pure, it's your job to not pass it mutable arguments, but the compiler's job to
make sure it doesn't mutate anything not in the arguments. And that's why a strongly pure function can call a weakly
pure one - only the first function's internal state can be mutated by a weakly pure function.
Thanks!

On Thu, 16 Jun 2011 17:38:27 +0000, Charles McAnany wrote:

> Ok, I think I get it. That cleared it up. =). So, if you have a functioned labelled pure, it's your job to not pass it mutable arguments, but the compiler's job to make sure it doesn't mutate anything not in the arguments. And that's why a strongly pure function can call a weakly pure one - only the first function's internal state can be mutated by a weakly pure function. Thanks!

Exactly. :)

-Lars

On 2011-06-16 10:38, Charles McAnany wrote:
> Ok, I think I get it. That cleared it up. =).
> So, if you have a functioned labelled pure, it's your job to not pass it
> mutable arguments, but the compiler's job to make sure it doesn't mutate
> anything not in the arguments. And that's why a strongly pure function can
> call a weakly pure one - only the first function's internal state can be
> mutated by a weakly pure function. Thanks!

Well, essentially. But it's a question of parameters, not arguments. It doesn't matter whether you pass the function mutable arguments or not. What matters is whether its parameters are immutable or implicitly immutable. If they are, then you'll be forced to pass it arguments which are immutable or implicitly immutable. If they aren't, then the function is weakly pure and no optimizations can take place (but the function still can't access mutable global variables and can still be called from other pure functions), regardless of how mutable the arguments are.

- Jonathan M Davis