www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Purity

reply bearophile <bearophileHUGS lycos.com> writes:
http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/

Bye,
bearophile
Dec 16 2010
next sibling parent Iain Buclaw <ibuclaw ubuntu.com> writes:
== Quote from bearophile (bearophileHUGS lycos.com)'s article
 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/
 Bye,
 bearophile

The way I see it, there are 4 ways of describing the purity of a function. Though the comments on them are slightly vague and different to the way I'll describe it, the way I assume them to be treated in D <-> GCC is: Pure if the function has no effects except the return value, which depends only on parameters, and may read (but not write to) global memory. Constly Pure if the function does not read global memory (immutable data being the only notable exception because of the way it's treated) and has no effects except the return value. Weakly Pure if the function does not read global memory, but may have arbitrary side effects, such as a method altering it's local state. Impure if the function may write into global memory/have other side effects that won't appropriately categorize it into the above. Regards Iain
Dec 17 2010
prev sibling next sibling parent reply Don <nospam nospam.com> writes:
bearophile wrote:
 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/
 
 Bye,
 bearophile

Nice. BTW you're incorrectly attributing some things to me. Although I recently championed the 'weakly pure' idea, I think Bruno made the original proposal.
Dec 17 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Don:

 BTW you're incorrectly attributing some things to me. Although I 
 recently championed the 'weakly pure' idea, I think Bruno made the 
 original proposal.

I am sorry, but It's easy to fix that error. I guess you mean Bruno Medeiros. Bye, bearophile
Dec 17 2010
prev sibling parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
On 17/12/2010 09:41, Don wrote:
 bearophile wrote:
 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/

 Bye,
 bearophile

Nice. BTW you're incorrectly attributing some things to me. Although I recently championed the 'weakly pure' idea, I think Bruno made the original proposal.

Well, kinda... I started the thread which described the original proposal in detail, and described how it was actually sound and potentially useful: http://www.digitalmars.com/d/archives/digitalmars/D/Idea_partially_pure_functions_70762.html But the idea itself didn't originate from me, it was derived from something you said, (or at least inspired by something you said): "I want to conceptualize an idea that has been briefly mentioned in the previous pure discussions (by Don I think?), but has not been explicitly brought into attention." -- Bruno Medeiros - Software Engineer
Jan 27 2011
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 17 Dec 2010 02:42:14 -0500, bearophile <bearophileHUGS lycos.com>  
wrote:

 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/

 Bye,
 bearophile

This is a good post, you sort of lost me at the SPARK example, but I want to particularly note some inaccuracies that you have. At one point you have an example that creates memory, and say that two different calls to create memory with the same size could return the same array. This is not valid, you introduce an aliasing issue by optimizing. Only if the return is immutable can you do this. Another inaccuracy (really an omission) is that a weakly pure function is just like a pure function but cannot be memoized. In fact, it cannot be optimized in any way like strongly pure functions can. In fact, a weakly pure function is exactly like a normal function except it can only call pure functions, it can be called by a pure function (strong or weak), and it cannot access mutable globals. In particular, a function like this: pure int foo(ref int x) {return ++x;} cannot be factored or reordered, i.e. this doesn't work: foo(x) + foo(x) => 2 * foo(x) If you think about it, you can see why. This actually ties together nicely with my first point -- a pure function that returns a mutable pointer must be weakly pure. Your example which returns an int[] is returning such a pointer, so it is weakly pure. Therefore, this is why your example that creates memory cannot return the same array twice (that memoization optimization cannot legally be done). -Steve
Dec 17 2010
next sibling parent reply Don <nospam nospam.com> writes:
Steven Schveighoffer wrote:
 On Fri, 17 Dec 2010 02:42:14 -0500, bearophile 
 <bearophileHUGS lycos.com> wrote:
 
 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/

 Bye,
 bearophile


You've got two statements here which are both sort-of true, but taken together are not correct: <1>
 Another inaccuracy (really an omission) is that a weakly pure function 
 is just like a pure function but cannot be memoized.  In fact, it cannot 
 be optimized in any way like strongly pure functions can. 

<2>
 This actually ties together nicely with my first point -- a pure 
 function that returns a mutable pointer must be weakly pure.  

A function which has immutably pure parameters can undergo *some* optimisation, even if the return value is a mutable pointer. For example, if the parameters are identical for both calls, you can do a deepdup of the first return value instead of calling the function again.
Dec 17 2010
next sibling parent Don <nospam nospam.com> writes:
Steven Schveighoffer wrote:
 On Fri, 17 Dec 2010 09:39:19 -0500, Don <nospam nospam.com> wrote:
 
 A function which has immutably pure parameters can undergo *some* 
 optimisation, even if the return value is a mutable pointer.
 For example, if the parameters are identical for both calls, you can 
 do a deepdup of the first return value instead of calling the function 
 again.

Yes, I agree with this. However, I still believe statement 1 is still correct, because you really have just introduced a third class of pure functions that I was not aware of :) So we have: weak-pure functions : functions which can accept and return any type of values, but can only call pure functions and cannot access global state. middle-pure ? functions : weak-pure functions which accept only immutable or implicitly convertable to immutable values, but returns a mutable reference.

 strong-pure funtions : pure functions which accept and return only 
 immutable or implicitly convertible to immutable values.
 
 There actually could be another class, const-pure functions: pure 
 functions which accept and return only const or implicitly convertible 
 to const values.

The problem with these ones, is there could be aliasing between the input and the output. Do they have any interesting properties? Another interesting one is a function with all-const parameters, that returns a mutable reference that has only mutable or immutable members. (ie, nothing const). Like the one you've called middle-pure, this returns a unique result, because you're guaranteed there is no aliasing.
 I suspect the compiler will need to classify things as strong or weak 
 pure, and store various attributes on weak-pure functions to see what 
 optimizations can be had.

The compiler does that already.
Dec 17 2010
prev sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
On 17/12/2010 14:39, Don wrote:
 <1>
 Another inaccuracy (really an omission) is that a weakly pure function
 is just like a pure function but cannot be memoized.  In fact, it
 cannot be optimized in any way like strongly pure functions can.

<2>
 This actually ties together nicely with my first point -- a pure
 function that returns a mutable pointer must be weakly pure.

A function which has immutably pure parameters can undergo *some* optimisation, even if the return value is a mutable pointer. For example, if the parameters are identical for both calls, you can do a deepdup of the first return value instead of calling the function again.

Are you sure? If I understood you correctly, that doesn't seem to be the case. Consider for example: string[] func(string arg) pure { string elem2 = "blah".idup; return [ arg, elem2 ]; } The compiler *cannot* know (well, looking at the signature only of course) how to properly deepdup the result from the first return value, so as to give the exact same result as if func was called again. Apologies if this has been discussed in some thread further ahead. -- Bruno Medeiros - Software Engineer
Jan 27 2011
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
On 27/01/2011 21:05, Simen kjaeraas wrote:
 Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 string[] func(string arg) pure {
 string elem2 = "blah".idup;
 return [ arg, elem2 ];
 }

 The compiler *cannot* know (well, looking at the signature only of
 course) how to properly deepdup the result from the first return
 value, so as to give the exact same result as if func was called again.

Could you please elucidate, as I am unsure of your reasoning for saying the compiler cannot know how to deepdup the result.

string str = "blah"; string[] var1 = func(str); string[] var2 = func(str); How can the compiler optimize the second call to func, the one that is assigned to var2, such that he deepdups var1 instead of calling func again? Which code would be generated? The compiler can't do that because of all the transitive data of var1, the compiler doesn't know which of it was newly allocated by func, and which of it was reused from func's parameters or some other global inputs. -- Bruno Medeiros - Software Engineer
Jan 28 2011
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
On 28/01/2011 20:25, Simen kjaeraas wrote:
 Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 On 27/01/2011 21:05, Simen kjaeraas wrote:
 Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 string[] func(string arg) pure {
 string elem2 = "blah".idup;
 return [ arg, elem2 ];
 }

 The compiler *cannot* know (well, looking at the signature only of
 course) how to properly deepdup the result from the first return
 value, so as to give the exact same result as if func was called again.

Could you please elucidate, as I am unsure of your reasoning for saying the compiler cannot know how to deepdup the result.

string str = "blah"; string[] var1 = func(str); string[] var2 = func(str); How can the compiler optimize the second call to func, the one that is assigned to var2, such that he deepdups var1 instead of calling func again? Which code would be generated? The compiler can't do that because of all the transitive data of var1, the compiler doesn't know which of it was newly allocated by func, and which of it was reused from func's parameters or some other global inputs.

But for immutable data (like the contents of the elements of a string[]), that doesn't matter, does it?

Maybe it won't matter for the *contents of the elements* of the string array, but the whole result value has to be /the same/ as if the optimization was not applied. Otherwise the optimization is invalid, even if for most uses of the result value it would not make a difference for the program. -- Bruno Medeiros - Software Engineer
Feb 01 2011
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
On 01/02/2011 14:15, Simen kjaeraas wrote:
 Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 But for immutable data (like the contents of the elements of a
 string[]),
 that doesn't matter, does it?

Maybe it won't matter for the *contents of the elements* of the string array, but the whole result value has to be /the same/ as if the optimization was not applied. Otherwise the optimization is invalid, even if for most uses of the result value it would not make a difference for the program.

I admit to still not understanding this. The data can't be changed, so the contents do not matter. The array structs (prt/length) would not be the same as those fed to the function in any case, so I really cannot see how those would matter. If others do understand, please elucidate.

Here is a synthetic example: string[] func(string arg) pure { string elem2 = "blah".idup; return [ arg, elem2 ]; } string str = "blah"; string[] result1 = func(str); string[] result2 = func(str); if(result2[0] is str) { // then } else { // else } In this code sample if the optimization is applied on the second call to func, it would cause different code with be executed: the else clause instead of the then clause. Obviously this is not acceptable for an optimization, even if such code would be rare in practice. -- Bruno Medeiros - Software Engineer
Feb 11 2011
parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
result1 ==On 11/02/2011 22:51, Simen kjaeraas wrote:
 Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 In this code sample if the optimization is applied on the second call
 to func, it would cause different code with be executed: the else
 clause instead of the then clause. Obviously this is not acceptable
 for an optimization, even if such code would be rare in practice.

Ah yes, I see now. I could argue that 'is' is cheating. :p I believe actually, that pure is only said to promise that the returned values should be such that func(args) == func(args), not accounting for overloaded operators.

That still would not be guaranteed. In the example I mentioned before, it already happens that (result1 == result2) == false I think that the concession that pure will be allowed to allocate memory does inescapably remove some of the guarantees that pure functions offer (like that one that the return value depends only on the arguments). One possible fix to this would be to say that the allocated memory must be temporary (used only during the execution of the pure function). Thus you would not be able to return any newly-allocated value. But I don't know if this further restriction is desirable or not. I don't remember if this aspect of memory allocation in pure functions was discussed/thought-out extensively or not. (it probably needs to) -- Bruno Medeiros - Software Engineer
Mar 23 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 17 Dec 2010 09:39:19 -0500, Don <nospam nospam.com> wrote:

 Steven Schveighoffer wrote:
 On Fri, 17 Dec 2010 02:42:14 -0500, bearophile  
 <bearophileHUGS lycos.com> wrote:

 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/

 Bye,
 bearophile


You've got two statements here which are both sort-of true, but taken together are not correct: <1>
 Another inaccuracy (really an omission) is that a weakly pure function  
 is just like a pure function but cannot be memoized.  In fact, it  
 cannot be optimized in any way like strongly pure functions can.

<2>
 This actually ties together nicely with my first point -- a pure  
 function that returns a mutable pointer must be weakly pure.

A function which has immutably pure parameters can undergo *some* optimisation, even if the return value is a mutable pointer. For example, if the parameters are identical for both calls, you can do a deepdup of the first return value instead of calling the function again.

Yes, I agree with this. However, I still believe statement 1 is still correct, because you really have just introduced a third class of pure functions that I was not aware of :) So we have: weak-pure functions : functions which can accept and return any type of values, but can only call pure functions and cannot access global state. middle-pure ? functions : weak-pure functions which accept only immutable or implicitly convertable to immutable values, but returns a mutable reference. strong-pure funtions : pure functions which accept and return only immutable or implicitly convertible to immutable values. There actually could be another class, const-pure functions: pure functions which accept and return only const or implicitly convertible to const values. These 4th class of functions could be classified as strong-pure when called with all immutable or implicitly convertible to immutable parameters. I suspect the compiler will need to classify things as strong or weak pure, and store various attributes on weak-pure functions to see what optimizations can be had. This shouldn't matter too much to the user, he should be oblivious to such optimizations. I think it's going to be very difficult to 'accidentally' create pure functions that could be optimized better. -Steve P.
Dec 17 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 17 Dec 2010 09:53:15 -0500, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 -Steve

 P.

Damn, accidentally hit shift-enter which sent the message. Meant to write: P.S. is there a better adjective for 'immutable or implicitly convertable to immutable'? That's a lot of verbiage for something that's really needed in a lot of places in the spec.
Dec 17 2010
prev sibling next sibling parent "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
On Fri, 17 Dec 2010 09:55:18 -0500, Steven Schveighoffer wrote:

 On Fri, 17 Dec 2010 09:53:15 -0500, Steven Schveighoffer
 <schveiguy yahoo.com> wrote:
 
 
 -Steve

 P.

Damn, accidentally hit shift-enter which sent the message. Meant to write: P.S. is there a better adjective for 'immutable or implicitly convertable to immutable'? That's a lot of verbiage for something that's really needed in a lot of places in the spec.

Value type? That is, a real value type, not one that is really a reference in disguise. "Pure value type", perhaps? -Lars
Dec 17 2010
prev sibling next sibling parent "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
On Fri, 17 Dec 2010 15:22:25 +0000, Lars T. Kyllingstad wrote:

 On Fri, 17 Dec 2010 09:55:18 -0500, Steven Schveighoffer wrote:
 
 On Fri, 17 Dec 2010 09:53:15 -0500, Steven Schveighoffer
 <schveiguy yahoo.com> wrote:
 
 
 -Steve

 P.

Damn, accidentally hit shift-enter which sent the message. Meant to write: P.S. is there a better adjective for 'immutable or implicitly convertable to immutable'? That's a lot of verbiage for something that's really needed in a lot of places in the spec.

Value type? That is, a real value type, not one that is really a reference in disguise. "Pure value type", perhaps?

Ah, forget it. That doesn't include immutable references. -Lars
Dec 17 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 18 Dec 2010 01:27:40 -0500, Don <nospam nospam.com> wrote:

 Steven Schveighoffer wrote:
 On Fri, 17 Dec 2010 09:39:19 -0500, Don <nospam nospam.com> wrote:

 A function which has immutably pure parameters can undergo *some*  
 optimisation, even if the return value is a mutable pointer.
 For example, if the parameters are identical for both calls, you can  
 do a deepdup of the first return value instead of calling the function  
 again.

correct, because you really have just introduced a third class of pure functions that I was not aware of :) So we have: weak-pure functions : functions which can accept and return any type of values, but can only call pure functions and cannot access global state. middle-pure ? functions : weak-pure functions which accept only immutable or implicitly convertable to immutable values, but returns a mutable reference.

 strong-pure funtions : pure functions which accept and return only  
 immutable or implicitly convertible to immutable values.
  There actually could be another class, const-pure functions: pure  
 functions which accept and return only const or implicitly convertible  
 to const values.

The problem with these ones, is there could be aliasing between the input and the output. Do they have any interesting properties?

They can act like strong-pure functions when all the arguments being passed in are IOICTI (immutable or implicitly convertable to immutable).
 Another interesting one is a function with all-const parameters, that  
 returns a mutable reference that has only mutable or immutable members.
 (ie, nothing const). Like the one you've called middle-pure, this  
 returns a unique result, because you're guaranteed there is no aliasing.

Yes.
 I suspect the compiler will need to classify things as strong or weak  
 pure, and store various attributes on weak-pure functions to see what  
 optimizations can be had.

The compiler does that already.

OK, good. -Steve
Dec 19 2010
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 string[] func(string arg) pure {
      string elem2 = "blah".idup;
      return [ arg, elem2 ];
 }

 The compiler *cannot* know (well, looking at the signature only of  
 course) how to properly deepdup the result from the first return value,  
 so as to give the exact same result as if func was called again.

Could you please elucidate, as I am unsure of your reasoning for saying the compiler cannot know how to deepdup the result. -- Simen
Jan 27 2011
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 On 27/01/2011 21:05, Simen kjaeraas wrote:
 Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 string[] func(string arg) pure {
 string elem2 = "blah".idup;
 return [ arg, elem2 ];
 }

 The compiler *cannot* know (well, looking at the signature only of
 course) how to properly deepdup the result from the first return
 value, so as to give the exact same result as if func was called again.

Could you please elucidate, as I am unsure of your reasoning for saying the compiler cannot know how to deepdup the result.

string str = "blah"; string[] var1 = func(str); string[] var2 = func(str); How can the compiler optimize the second call to func, the one that is assigned to var2, such that he deepdups var1 instead of calling func again? Which code would be generated? The compiler can't do that because of all the transitive data of var1, the compiler doesn't know which of it was newly allocated by func, and which of it was reused from func's parameters or some other global inputs.

But for immutable data (like the contents of the elements of a string[]), that doesn't matter, does it? -- Simen
Jan 28 2011
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 But for immutable data (like the contents of the elements of a  
 string[]),
 that doesn't matter, does it?

Maybe it won't matter for the *contents of the elements* of the string array, but the whole result value has to be /the same/ as if the optimization was not applied. Otherwise the optimization is invalid, even if for most uses of the result value it would not make a difference for the program.

I admit to still not understanding this. The data can't be changed, so the contents do not matter. The array structs (prt/length) would not be the same as those fed to the function in any case, so I really cannot see how those would matter. If others do understand, please elucidate. -- Simen
Feb 01 2011
prev sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Bruno Medeiros <brunodomedeiros+spam com.gmail> wrote:

 In this code sample if the optimization is applied on the second call to  
 func, it would cause different code with be executed: the else clause  
 instead of the then clause. Obviously this is not acceptable for an  
 optimization, even if such code would be rare in practice.

Ah yes, I see now. I could argue that 'is' is cheating. :p I believe actually, that pure is only said to promise that the returned values should be such that func(args) == func(args), not accounting for overloaded operators. -- Simen
Feb 11 2011
prev sibling next sibling parent reply spir <denis.spir gmail.com> writes:
On Fri, 17 Dec 2010 02:42:14 -0500
bearophile <bearophileHUGS lycos.com> wrote:

 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/
=20
 Bye,
 bearophile

I take the opportunity to question the def of weakly pure. -1- How can this even compile? pure append (ref int[] a, int i) {a ~=3D i;} The _only_ task of this func is to change state. -2- Why is output writing considered an impure task? It has no influence on= the rest/future of the program, lets reasoning easy, does not touch state. I would like weakly pure to include output funcs, and exclude all possibili= ties to modify (non-local) state. Denis -- -- -- -- -- -- -- vit esse estrany =E2=98=A3 spir.wikidot.com
Dec 18 2010
parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
On 18/12/2010 08:52, spir wrote:
 On Fri, 17 Dec 2010 02:42:14 -0500
 bearophile<bearophileHUGS lycos.com>  wrote:

 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/

 Bye,
 bearophile

I take the opportunity to question the def of weakly pure. -1- How can this even compile? pure append (ref int[] a, int i) {a ~= i;} The _only_ task of this func is to change state.

It is best not to think of D's pure as saying the function is pure in the traditional sense (side-effect free), but rather to say the side-effects are confined to the function's parameters only (and the state/data that is transitively reachable from them). The key benefit of this is that it allows the *caller* of such pure function to determine which subset of state/data *may* change by a call to such function. -- Bruno Medeiros - Software Engineer
Jan 27 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday 18 December 2010 00:52:23 spir wrote:
 On Fri, 17 Dec 2010 02:42:14 -0500
 
 bearophile <bearophileHUGS lycos.com> wrote:
 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/
 
 Bye,
 bearophile

I take the opportunity to question the def of weakly pure. -1- How can this even compile? pure append (ref int[] a, int i) {a ~= i;} The _only_ task of this func is to change state.

It's _weakly_ pure, not strongly pure. This pretty much just means that the function does not access global variables. No optimizations can be done to it. It's purely so that strongly pure (or other weakly pure) functions can legally call it. If it's a strongly pure function calling it, then not only do you know that global state can't be affected, but because all of the function's parameters are immutable (or full-on copies of mutable data in the case where it's a type implicitly convertible to/from immutable). Weakly pure functions are _not_ pure in the functional sense at all. Only strongly pure functions are.
 -2- Why is output writing considered an impure task? It has no influence on
 the rest/future of the program, lets reasoning easy, does not touch state.
 
 I would like weakly pure to include output funcs, and exclude all
 possibilities to modify (non-local) state.

The problem is that output is accessing global variables - which weakly pure functions _cannot_ do. If you call a weakly pure function from a strongly pure function, it's still guranteed that the result of the strongly pure function will be the same and have _no_ side effects - that is, it effectively has the functional definition of purity. However, if you allowed I/O, you then have a side effect, and two calls to a particular strongly pure function could differ, and yet the optimizer would then only do one call, thereby changing the results of the program. Optimizing out calls pure functions should _never_ change the results of a program. Allowing output in weakly pure functions would allow that. Now, there is arguably some need for the ability to have _debug_ functions for printing in pure functions (be they weakly pure or strongly pure), but they'd likely be used in cases where pure optimizations were not used (since you wouldn't be using -O for debugging), and if they were used, the programmer would effectively be saying that they were okay with the I/O not necessarily occuring every time that a function call occured in the code (since the call could be optimized out). That is _not_ acceptible for general I/O. I/O breaks purity. The way to get around it is to use monads, but that would affect the signatures of every single function in the chain of function calls which included the I/O. So, you wouldn't normally want to do that. - Jonathan M Davis
Dec 18 2010
prev sibling next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
spir <denis.spir gmail.com> wrote:

 -1- How can this even compile?
 	pure append (ref int[] a, int i) {a ~= i;}
 The _only_ task of this func is to change state.

It is designed to be usable in strongly pure functions. A strongly pure function may call this weakly pure function without compromising its purity. This because the strongly pure function could only pass the weakly pure function its own local state, and changes would thus be limited to the strongly pure function's scope.
 -2- Why is output writing considered an impure task? It has no influence  
 on the rest/future of the program, lets reasoning easy, does not touch  
 state.

Output would be affected by pure optimizations: pure int writeStuff() { output( "Hi!" ); return 1; } void foo( ) { int a = writeStuff( ) + writeStuff( ); } Normally, the compiler could rewrite to int a = 2 * writeStuff( ); but that would fuck up output. -- Simen
Dec 18 2010
prev sibling next sibling parent reply spir <denis.spir gmail.com> writes:
On Sat, 18 Dec 2010 01:08:20 -0800
Jonathan M Davis <jmdavisProg gmx.com> wrote:

Thank you for the explanation about strongly pure funcs calling weakly pure=
 ones --this fully makes sense.

 I would like weakly pure to include output funcs, and exclude all
 possibilities to modify (non-local) state. =20

The problem is that output is accessing global variables - which weakly p=

 functions _cannot_ do.

Why? What is the rationale for excluding output (I don't mean I/O, only O)?
 If you call a weakly pure function from a strongly pure=20
 function, it's still guranteed that the result of the strongly pure funct=

 will be the same and have _no_ side effects - that is, it effectively has=

 functional definition of purity. However, if you allowed I/O, you then ha=

 side effect, and two calls to a particular strongly pure function could d=

 and yet the optimizer would then only do one call, thereby changing the r=

 of the program.=20

I disagree. Again, I'm not talking of I/O. The FP definition of "pure" excl= uding output is irrational imo. Writing to output cannot change later funct= ion return values, so who cares? And it's not only true for debug --even if I very much agree debug is a sup= er important reason for allowing output. Denis -- -- -- -- -- -- -- vit esse estrany =E2=98=A3 spir.wikidot.com
Dec 18 2010
next sibling parent David Nadlinger <see klickverbot.at> writes:
On 12/18/10 12:52 PM, spir wrote:
 Why? What is the rationale for excluding output (I don't mean I/O, only O)?

Where would be the difference between writing to a global variable and writing to stdout? David
Dec 18 2010
prev sibling parent reply Don <nospam nospam.com> writes:
spir wrote:
 On Sat, 18 Dec 2010 01:08:20 -0800
 Jonathan M Davis <jmdavisProg gmx.com> wrote:
 
 Thank you for the explanation about strongly pure funcs calling weakly pure
ones --this fully makes sense.
 
 I would like weakly pure to include output funcs, and exclude all
 possibilities to modify (non-local) state.  

functions _cannot_ do.

Why? What is the rationale for excluding output (I don't mean I/O, only O)?

You're correct in saying that it doesn't affect the operation of the program. But in practice, program output is almost always important. For example, suppose we allowed output to be pure. Then consider: writeln("Hello, world!"); Since it returns nothing, and has no influence on the future execution of the program, the writeln can be dropped from the program. Hmmm....
Dec 18 2010
next sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2010-12-18 07:46:11 -0500, Don <nospam nospam.com> said:

 spir wrote:
 On Sat, 18 Dec 2010 01:08:20 -0800
 Jonathan M Davis <jmdavisProg gmx.com> wrote:
 
 Thank you for the explanation about strongly pure funcs calling weakly 
 pure ones --this fully makes sense.
 
 I would like weakly pure to include output funcs, and exclude all
 possibilities to modify (non-local) state.

pure functions _cannot_ do.

Why? What is the rationale for excluding output (I don't mean I/O, only O)?

You're correct in saying that it doesn't affect the operation of the program. But in practice, program output is almost always important. For example, suppose we allowed output to be pure. Then consider: writeln("Hello, world!"); Since it returns nothing, and has no influence on the future execution of the program, the writeln can be dropped from the program.

I agree with that for writeln, the function at global scope, can't be pure. The reason is simple: it refers to the stdout global variable. However, if someone was to pass stdout as a non-const function parameter I think it should work: pure void fun(File output, string msg) { output.writeln(msg); } void main() { fun(stdout, msg); } File.writeln cannot be strongly pure since it gets the File as a reference (and so it can't be optimized away), but it can be weakly pure. One could argue that this is not terribly useful since no strongly pure functions will be able to do IO, but there might be other reasons one would want a weakly pure function other than enabling strongly pure ones. (For one instance of this, see my two posts in the other discussion "Threads and static initialization".) -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Dec 18 2010
prev sibling next sibling parent Don <nospam nospam.com> writes:
spir wrote:
 On Sat, 18 Dec 2010 13:46:11 +0100
 Don <nospam nospam.com> wrote:
 
 spir wrote:
 On Sat, 18 Dec 2010 01:08:20 -0800
 Jonathan M Davis <jmdavisProg gmx.com> wrote:

 Thank you for the explanation about strongly pure funcs calling weakly pure
ones --this fully makes sense.

 I would like weakly pure to include output funcs, and exclude all
 possibilities to modify (non-local) state.  

functions _cannot_ do.


program. But in practice, program output is almost always important. For example, suppose we allowed output to be pure. Then consider: writeln("Hello, world!"); Since it returns nothing, and has no influence on the future execution of the program, the writeln can be dropped from the program. Hmmm....

For sure, if you specify (in the compiler behaviour) that the only purpose of a pure function is to return something.

Yes, that's what's done.
 Which excudes all "action-fonctions" (= funcs which purpose is to perform an
effect). 
 But why should the compiler rewrite of such a func be to erase it? Just let it
alone, it won't bother anybody. 

But if you do that, you lose most of the benefits of pure.
And can safely be qualified as pure. So that, transitively, pure funcs 

You could do this -- but in order to preserve the usefulness of pure, you'd need to introduce some way of flagging such functions. The signature would need to indicate that it is a "action function".
 	pure Report getReport (Data data) {
 	    // compute report from data (only)
 	    log.write(report);
 	    writefln("report computed:\n\t%s", report);   // debug
 	    return report;
 	}
 
 Anyway, aside practicle & efficiency purposes, 

 I'm even more annoyed by the "conceptual wrongness" of excluding functions
that perform output from the "world of purity" ;-)
 I would want them included even if this did not buy anything.

I think you're assuming that including them costs nothing. But it does. Including such functions destroys most of the benefits of pure. You do need to treat them differently.
 All of this would be easier and clearer if D made a proper distinction between
'true' functions (that compute a result) and 'action-functions' (that perform
an effect). The actual purity criteria need not be the same:
 * actions must not write to state
 * functions must not read from state
 Just state: output ports and memory do not belong to program state, and we're
done.

Definitely you could do this. I suspect that it wouldn't be worth it, though, because action functions are viral. Once a function is an action function, everything which calls it is also an action function. And from an optimisation perspective, there isn't much you can do with action functions.
 There is an asymmetry: runtime/variable data input (from user, file,...) must
be considered as state, else a compiler cannot memoize function results.

It also can't memoize the results of functions which call action functions. But aside from all of this, I'm actually rather sceptical that output can be done without using static variables. I cannot imagine how it could be done. It is an interesting point, that is particularly obvious at a low level. For example, in DOS text mode, writing 'a' to 0xB000 wrote an 'a' in the top left corner of the screen, even if the function never reads that address. But writing 'a' to 0x5000 is not output! Currently, a pure function cannot write to _any_ static variable. This disallows a few obscure functions which could be considered to be logically pure. Ultimately, I think your definition of 'pure function' would be: never reads from a static variable, and never writes to a static variable which is ever read by another function; and 'pure action function' would be: writes to an output port, or to a never-read static variable which is designated as an output. Again, although this could be done, I doubt that it's worth it. The costs seem high and the benefits low.
Dec 18 2010
prev sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
On 18/12/2010 12:46, Don wrote:
 spir wrote:
 On Sat, 18 Dec 2010 01:08:20 -0800
 Jonathan M Davis <jmdavisProg gmx.com> wrote:

 Thank you for the explanation about strongly pure funcs calling weakly
 pure ones --this fully makes sense.

 I would like weakly pure to include output funcs, and exclude all
 possibilities to modify (non-local) state.

weakly pure functions _cannot_ do.

Why? What is the rationale for excluding output (I don't mean I/O, only O)?

You're correct in saying that it doesn't affect the operation of the program. But in practice, program output is almost always important. For example, suppose we allowed output to be pure. Then consider: writeln("Hello, world!"); Since it returns nothing, and has no influence on the future execution of the program, the writeln can be dropped from the program. Hmmm....

Hum, it might still be useful to have something like a compiler switch that disables pure altogether, then people could use I/O and other non-pure operations for debugging purposes. One could wrap such code with a version statement: void myPurefunc(Foo foo) pure { version(pure_disabled) { writeln("some debug info: ", foo); } //... -- Bruno Medeiros - Software Engineer
Feb 11 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Bruno Medeiros:

 Hum, it might still be useful to have something like a compiler switch 
 that disables pure altogether, then people could use I/O and other 
 non-pure operations for debugging purposes. One could wrap such code 
 with a version statement:
 
 void myPurefunc(Foo foo) pure {
    version(pure_disabled) {
      writeln("some debug info: ", foo);
    }
    //...

This seems an interesting idea to help debug pure functions. Bye, bearophile
Feb 11 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On Sat, 18 Dec 2010 13:09:19 +0100
David Nadlinger <see klickverbot.at> wrote:

 On 12/18/10 12:52 PM, spir wrote:
 Why? What is the rationale for excluding output (I don't mean I/O, only=


=20
 Where would be the difference between writing to a global variable and=20
 writing to stdout?

How can writing to stdout change the result value of a later call to (the s= ame or any other) function? Denis -- -- -- -- -- -- -- vit esse estrany =E2=98=A3 spir.wikidot.com
Dec 18 2010
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On Sat, 18 Dec 2010 13:46:11 +0100
Don <nospam nospam.com> wrote:

 spir wrote:
 On Sat, 18 Dec 2010 01:08:20 -0800
 Jonathan M Davis <jmdavisProg gmx.com> wrote:
=20
 Thank you for the explanation about strongly pure funcs calling weakly =


=20
 I would like weakly pure to include output funcs, and exclude all
 possibilities to modify (non-local) state. =20




 functions _cannot_ do.

Why? What is the rationale for excluding output (I don't mean I/O, only=


=20
 You're correct in saying that it doesn't affect the operation of the=20
 program. But in practice, program output is almost always important.
=20
 For example, suppose we allowed output to be pure. Then consider:
=20
 writeln("Hello, world!");
=20
 Since it returns nothing, and has no influence on the future execution=20
 of the program, the writeln can be dropped from the program.
=20
 Hmmm....

For sure, if you specify (in the compiler behaviour) that the only purpose = of a pure function is to return something. Which excudes all "action-foncti= ons" (=3D funcs which purpose is to perform an effect). But why should the = compiler rewrite of such a func be to erase it? Just let it alone, it won't= bother anybody. And can safely be qualified as pure. So that, transitively= , pure funcs can call funcs that perform output. Just what we want. pure Report getReport (Data data) { // compute report from data (only) log.write(report); writefln("report computed:\n\t%s", report); // debug return report; } Anyway, aside practicle & efficiency purposes, I'm even more annoyed by the= "conceptual wrongness" of excluding functions that perform output from the= "world of purity" ;-) I would want them included even if this did not buy = anything. All of this would be easier and clearer if D made a proper distinction betw= een 'true' functions (that compute a result) and 'action-functions' (that p= erform an effect). The actual purity criteria need not be the same: * actions must not write to state * functions must not read from state Just state: output ports and memory do not belong to program state, and we'= re done. There is an asymmetry: runtime/variable data input (from user, file,...) mu= st be considered as state, else a compiler cannot memoize function results. Denis -- -- -- -- -- -- -- vit esse estrany =E2=98=A3 spir.wikidot.com
Dec 18 2010
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On Sat, 18 Dec 2010 12:30:31 +0100
"Simen kjaeraas" <simen.kjaras gmail.com> wrote:

 spir <denis.spir gmail.com> wrote:
=20
 -1- How can this even compile?
 	pure append (ref int[] a, int i) {a ~=3D i;}
 The _only_ task of this func is to change state.

It is designed to be usable in strongly pure functions. A strongly pure function may call this weakly pure function without compromising its purity. This because the strongly pure function could only pass the weakly pure function its own local state, and changes would thus be limited to the strongly pure function's scope.

Right, thank you.
 -2- Why is output writing considered an impure task? It has no influenc=


 on the rest/future of the program, lets reasoning easy, does not touch =


 state.

Output would be affected by pure optimizations: =20 pure int writeStuff() { output( "Hi!" ); return 1; } =20 void foo( ) { int a =3D writeStuff( ) + writeStuff( ); } =20 Normally, the compiler could rewrite to int a =3D 2 * writeStuff( ); but that would fuck up output.

... which means the optimisation scheme is wrong for "action-funcs". Note: As said in // post, languages maybe should properly make a distinctio= n between action-functions & true functions (returning a result) --but I'm = aware this goes against the whole culture of the C-line languages. I consider funcs like this one, that both perform an effect and return a re= sult, as confusing, and even erroneous, design/style. Denis -- -- -- -- -- -- -- vit esse estrany =E2=98=A3 spir.wikidot.com
Dec 18 2010
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/17/10 1:42 AM, bearophile wrote:
 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/

 Bye,
 bearophile

This is an excellent article, which is reflected in high reddit vote and a spirited but troll-free discussion. A homerun! We need more of this stuff. Congratulations, Leonardo! Andrei
Dec 18 2010
parent Walter Bright <newshound2 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 On 12/17/10 1:42 AM, bearophile wrote:
 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/

 Bye,
 bearophile

This is an excellent article, which is reflected in high reddit vote and a spirited but troll-free discussion. A homerun! We need more of this stuff. Congratulations, Leonardo!

I agree. Nice job!
Dec 18 2010
prev sibling parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
On 17/12/2010 07:42, bearophile wrote:
 http://www.reddit.com/r/programming/comments/enajl/purity_in_d_language/

 Bye,
 bearophile

"pure functions are contravariant (a "subset") with impure functions" Nope, there is a mistake here, it is the other way around: pure functions are covariant with impure functions. This is even mentioned in the beginning of the article: "a pure function: [...] - Is covariant with an impure function;" -- Bruno Medeiros - Software Engineer
Jan 27 2011