www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Pure not acting pure.

reply Charles McAnany <mcanance rose-hulman.edu> writes:
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.
Jun 15 2011
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Jun 15 2011
parent reply Charles McAnany <mcanance rose-hulman.edu> writes:
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
Jun 15 2011
parent reply Michel Fortin <michel.fortin michelf.com> writes:
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/
Jun 16 2011
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
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
Jun 16 2011
prev sibling parent Charles McAnany <mcanance rose-hulman.edu> writes:
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!
Jun 16 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Jun 15 2011
prev sibling next sibling parent reply "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
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
Jun 16 2011
next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Jun 16 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 16 Jun 2011 14:33:17 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 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.

Actually, it can matter. For instance, a pure function like this: pure int foo(const(int)* m); can be strong pure if you pass it a pointer to immutable data. -Steve
Jun 16 2011
prev sibling next sibling parent "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
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
Jun 16 2011
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-06-16 11:59, Steven Schveighoffer wrote:
 On Thu, 16 Jun 2011 14:33:17 -0400, Jonathan M Davis <jmdavisProg gmx.com>
 
 wrote:
 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.

Actually, it can matter. For instance, a pure function like this: pure int foo(const(int)* m); can be strong pure if you pass it a pointer to immutable data.

I believe that every time that Don has discussed it, he has made it clear that it's entirely a matter of the function's signature and that all parameters must be immutable or implicitly convertible to immutable for a function to be strongly pure. So, that's what I'm going by. However, I can see how passing immutable values to a pure function with const parameters could be optimized out just like if the parameters were actually immutable. So, it may be that things were changed so that that counts as well. Everything that I've seen discussed on it though has been about the parameters all having to be immutable or implicitly convertible to immutable. - Jonathan M Davis
Jun 16 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:

 I'm _very_ glad that Don came up with the weakly pure idea, or 
 pure would have been almost unusable.

I think Don has said this wasn't fully his idea. The D community is good at creating ideas in group :-) Bye, bearophile
Jun 16 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 16 Jun 2011 16:36:01 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On 2011-06-16 11:59, Steven Schveighoffer wrote:
 On Thu, 16 Jun 2011 14:33:17 -0400, Jonathan M Davis  
 <jmdavisProg gmx.com>

 wrote:
 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  


 mutable arguments, but the compiler's job to make sure it doesn't  


 anything not in the arguments. And that's why a strongly pure  


 can
 call a weakly pure one - only the first function's internal state  


 mutated by a weakly pure function. Thanks!

Well, essentially. But it's a question of parameters, not arguments.

 doesn't matter whether you pass the function mutable arguments or not.

Actually, it can matter. For instance, a pure function like this: pure int foo(const(int)* m); can be strong pure if you pass it a pointer to immutable data.

I believe that every time that Don has discussed it, he has made it clear that it's entirely a matter of the function's signature and that all parameters must be immutable or implicitly convertible to immutable for a function to be strongly pure. So, that's what I'm going by. However, I can see how passing immutable values to a pure function with const parameters could be optimized out just like if the parameters were actually immutable. So, it may be that things were changed so that that counts as well. Everything that I've seen discussed on it though has been about the parameters all having to be immutable or implicitly convertible to immutable.

Don's the one who brought it to my attention (have no idea what thread it was in...) that the optimizations could be done based on this. AFAIK, this optimization is not implemented. -Steve
Jun 16 2011
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On 2011-06-16 13:47, Steven Schveighoffer wrote:
 On Thu, 16 Jun 2011 16:36:01 -0400, Jonathan M Davis <jmdavisProg gmx.com>
 
 wrote:
 On 2011-06-16 11:59, Steven Schveighoffer wrote:
 On Thu, 16 Jun 2011 14:33:17 -0400, Jonathan M Davis
 <jmdavisProg gmx.com>
 
 wrote:
 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.

Actually, it can matter. For instance, a pure function like this: pure int foo(const(int)* m); can be strong pure if you pass it a pointer to immutable data.

I believe that every time that Don has discussed it, he has made it clear that it's entirely a matter of the function's signature and that all parameters must be immutable or implicitly convertible to immutable for a function to be strongly pure. So, that's what I'm going by. However, I can see how passing immutable values to a pure function with const parameters could be optimized out just like if the parameters were actually immutable. So, it may be that things were changed so that that counts as well. Everything that I've seen discussed on it though has been about the parameters all having to be immutable or implicitly convertible to immutable.

Don's the one who brought it to my attention (have no idea what thread it was in...) that the optimizations could be done based on this. AFAIK, this optimization is not implemented.

Well, conceptually, it seems solid. And ultimately, it's up to the compiler what it decides is actually strongly pure, so it'll probably be implemented at some point. I think that it's safe to say that in the long run at least, we'll optimize pure functions as much as we can reasonably get away with. But regardless, I'm _very_ glad that Don came up with the weakly pure idea, or pure would have been almost unusable. - Jonathan M Davis
Jun 16 2011