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
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
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 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 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
parent reply 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
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 parent reply "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
parent reply "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
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 reply "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  




 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.

-Steve
Jun 16 2011
parent reply "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
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