Digital Mars - digitalmars.D - Re: Idea: partially pure functions

↑ ↓ ← → Jason House <jason.james.house gmail.com> writes:

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 01 2008

↑ ↓ ← → Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:

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

↑ ↓ ← → Jason House <jason.james.house gmail.com> writes:

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 02 2008