digitalmars.D - Re: Idea: partially pure functions
- Jason House <jason.james.house gmail.com> May 01 2008
- Bruno Medeiros <brunodomedeiros+spam com.gmail> May 02 2008
- Jason House <jason.james.house gmail.com> May 02 2008
- Bruno Medeiros <brunodomedeiros+spam com.gmail> May 03 2008
- Jason House <jason.james.house gmail.com> May 03 2008
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
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
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
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
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.
May 03 2008