View mode: basic / threaded / horizontal-split · Log in · Help
May 01, 2008
Re: Idea: partially pure functions
Bruno Medeiros Wrote:

> 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.
> 
> As we know, the current definition of pure functions (according to 
> http://www.digitalmars.com/d/2.0/accu-functional.pdf) is that they can 
> only access invariant, or local mutable data. This means that all of the 
> function's parameters have to be invariant.
> 
> The idea is: let's also allow pure functions to have (and access) 
> non-invariant parameters. These won't be normal pure functions, but 
> instead "partially" pure functions. Their semantics are: the function 
> promises not to change any external/global data, except for the 
> parameters that are not invariant. Example:
> 
>    pure char[] mutable_tolower(char[] str) {
>      // in-place tolower here as str is mutable...
>    }
> 
> But what's the use of partially pure functions then?
> Well, what happens is that, since the set of possible mutable data of a 
> partial function is "finite", and restricted to only the function's 
> parameters, one can safely allow the calling of partially pure functions 
> inside fully pure functions (and also other partially pure functions).
> 
> How come? Well, a fully pure function is allowed to mutate local state. 
> Thus, it can use that mutable local sate as arguments to a partially 
> pure function, since that partially pure function will only mutable 
> those arguments, and nothing else. The contract for a full pure function 
> is maintained.
> 
> 
> Example: consider a pure function that takes two strings as arguments, 
> concatenates them, tolower's the first half, and toupper's the second 
> half. How does one write that function with the usual rules for pure 
> functions? Something like:
> 
>    alias char[] mstring;
> 
>    char[] xpto(string a, string b) {
>      mstring result = a ~ b;
> 
>      auto halflen = result.length/2;
>      return (tolower(result[0..halflen]) ~ toupper(result[halflen..$]));
>    }
> 
> But notice that this version is inefficient. About 3 unnecessary 
> temporary allocations are performed. How could this be prevented? One 
> solution would be to call mutable versions of tolower and toupper... but 
> since they are not pure functions, they cannot be called under the 
> normal rules. But if one allows the partially pure function rules, it 
> becomes possible. One then could write the previous function as this:
> 
> 
>    char[] xpto2(string a, string b) {
>      mstring result = a ~ b;
> 
>      auto halflen = result.length/2;
>      mutable_tolower(result[0..halflen]);
>      mutable_toupper(result[halflen..$]);
>      return result;
>    }
> 
> 
> Now, I know that xpto could be rewritten so as to be as efficient as 
> xpto2 with the current rules, but the code wouldn't look nearly as nice. 
> And that is precisely the point: You would have to code tolower inside 
> of xpto, and this is just a trivial example, imagine with more 
> complicated functions... The partially pure functions allow more 
> expressiveness and efficiency without any kind of compromise.
> 
> -- 
> Bruno Medeiros - Software Developer, MSc. in CS/E graduate
> http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D

Rather than thinking of functions than can mix with pure functions as partially pure, I'd prefer to think of them as having no side effect.  For arguments sake, I'll just use the keyword noside (analogous to nothrow).

class A{}
class C{}

void f(); // impure
void f() noside; // pure
void f(A c) noside; // partially pure
void f(invariant(A) c) noside; // pure
C f() noside; // illegal
invariant(C) f() noside; // pure (using global invariant data)

class B{
 C cc;
 void f(); // impure
 void f() noside; // pure
 void f(A c) noside; // partially pure
 void f(invariant(A) a) noside; // pure
 C f() noside; // partially pure
 invariant(C) f() noside; // pure
}
May 02, 2008
Re: Idea: partially pure functions
Jason House wrote:
> Bruno Medeiros Wrote:
> 
>> 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.
>>
>> As we know, the current definition of pure functions (according to 
>> http://www.digitalmars.com/d/2.0/accu-functional.pdf) is that they can 
>> only access invariant, or local mutable data. This means that all of the 
>> function's parameters have to be invariant.
>>
>> The idea is: let's also allow pure functions to have (and access) 
>> non-invariant parameters. These won't be normal pure functions, but 
>> instead "partially" pure functions. Their semantics are: the function 
>> promises not to change any external/global data, except for the 
>> parameters that are not invariant. Example:
>>
>>    pure char[] mutable_tolower(char[] str) {
>>      // in-place tolower here as str is mutable...
>>    }
>>
>> But what's the use of partially pure functions then?
>> Well, what happens is that, since the set of possible mutable data of a 
>> partial function is "finite", and restricted to only the function's 
>> parameters, one can safely allow the calling of partially pure functions 
>> inside fully pure functions (and also other partially pure functions).
>>
>> How come? Well, a fully pure function is allowed to mutate local state. 
>> Thus, it can use that mutable local sate as arguments to a partially 
>> pure function, since that partially pure function will only mutable 
>> those arguments, and nothing else. The contract for a full pure function 
>> is maintained.
>>
>>
>> Example: consider a pure function that takes two strings as arguments, 
>> concatenates them, tolower's the first half, and toupper's the second 
>> half. How does one write that function with the usual rules for pure 
>> functions? Something like:
>>
>>    alias char[] mstring;
>>
>>    char[] xpto(string a, string b) {
>>      mstring result = a ~ b;
>>
>>      auto halflen = result.length/2;
>>      return (tolower(result[0..halflen]) ~ toupper(result[halflen..$]));
>>    }
>>
>> But notice that this version is inefficient. About 3 unnecessary 
>> temporary allocations are performed. How could this be prevented? One 
>> solution would be to call mutable versions of tolower and toupper... but 
>> since they are not pure functions, they cannot be called under the 
>> normal rules. But if one allows the partially pure function rules, it 
>> becomes possible. One then could write the previous function as this:
>>
>>
>>    char[] xpto2(string a, string b) {
>>      mstring result = a ~ b;
>>
>>      auto halflen = result.length/2;
>>      mutable_tolower(result[0..halflen]);
>>      mutable_toupper(result[halflen..$]);
>>      return result;
>>    }
>>
>>
>> Now, I know that xpto could be rewritten so as to be as efficient as 
>> xpto2 with the current rules, but the code wouldn't look nearly as nice. 
>> And that is precisely the point: You would have to code tolower inside 
>> of xpto, and this is just a trivial example, imagine with more 
>> complicated functions... The partially pure functions allow more 
>> expressiveness and efficiency without any kind of compromise.
>>
>> -- 
>> Bruno Medeiros - Software Developer, MSc. in CS/E graduate
>> http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
> 
> Rather than thinking of functions than can mix with pure functions as partially pure, I'd prefer to think of them as having no side effect.  For arguments sake, I'll just use the keyword noside (analogous to nothrow).
> 
> class A{}
> class C{}
> 
> void f(); // impure
> void f() noside; // pure
> void f(A c) noside; // partially pure
> void f(invariant(A) c) noside; // pure
> C f() noside; // illegal

Why is this last case illegal? It's fine for a pure function to return a 
mutable value. (see my other discussion with Steven)

> 
> class B{
>   C cc;
>   void f(); // impure
>   void f() noside; // pure
>   void f(A c) noside; // partially pure
>   void f(invariant(A) a) noside; // pure
>   C f() noside; // partially pure
>   invariant(C) f() noside; // pure
> }

All the examples here that you mention as pure, are not pure but in fact 
partial pure, because the methods have a mutable this parameter.


-- 
Bruno Medeiros - Software Developer, MSc. in CS/E graduate
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
May 02, 2008
Re: Idea: partially pure functions
Bruno Medeiros Wrote:

> Jason House wrote:
> > Rather than thinking of functions than can mix with pure functions as partially pure, I'd prefer to think of them as having no side effect.  For arguments sake, I'll just use the keyword noside (analogous to nothrow).
> > 
> > class A{}
> > class C{}
> > 
> > void f(); // impure
> > void f() noside; // pure
> > void f(A c) noside; // partially pure
> > void f(invariant(A) c) noside; // pure
> > C f() noside; // illegal
> 
> Why is this last case illegal? It's fine for a pure function to return a 
> mutable value. (see my other discussion with Steven)

That's a trickier case.  I should have explained it.  How does the function get a mutable C to return?  It can't use mutable global data and it can't allocate a new C.  Because of that, it becomes impossible to give a body to f that satisfies the contract.


> > class B{
> >   C cc;
> >   void f(); // impure
> >   void f() noside; // pure
> >   void f(A c) noside; // partially pure
> >   void f(invariant(A) a) noside; // pure
> >   C f() noside; // partially pure
> >   invariant(C) f() noside; // pure
> > }
> 
> All the examples here that you mention as pure, are not pure but in fact 
> partial pure, because the methods have a mutable this parameter.

You're right.  True purity requires the class member functions to be marked as invariant.
May 03, 2008
Re: Idea: partially pure functions
Jason House wrote:
> 
> and it can't allocate a new C.  
> 

Says who? If the constructor of C is pure/partial-pure, the calling of 
it should be allowed as well. I don't know however if this will work in 
the planned initial version of the pure system.

-- 
Bruno Medeiros - Software Developer, MSc. in CS/E graduate
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
May 03, 2008
Re: Idea: partially pure functions
Bruno Medeiros wrote:

> Jason House wrote:
>> 
>> and it can't allocate a new C.
>> 
> 
> Says who? If the constructor of C is pure/partial-pure, the calling of
> it should be allowed as well. I don't know however if this will work in
> the planned initial version of the pure system.
> 

Use of "new" causes side effects.  Maybe to a part of code that most
programmers don't care about, but it's a side effect.  This can also be an
important side effect when trying to do multithreading.
Top | Discussion index | About this forum | D home