www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Idea: partially pure functions

reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
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
Apr 29 2008
next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
2008/4/30 Bruno Medeiros <brunodomedeiros+spam com.gmail>:

  Example: consider a pure function that takes two strings as arguments,
 concatenates them, tolower's the first half, and toupper's the second half.


Not that this in any way changes your argument, but I take it you do
realise that toupper and tolower cannot be done in place, because the
UTF-8 sequences representing dchar c might be a different length from
the UTF-8 sequences representing toupper(c) or tolower(c).

This is a common misconception popular among people who only use ASCII. :-)
Apr 29 2008
parent reply Robert Fraser <fraserofthenight gmail.com> writes:
Janice Caron wrote:

 2008/4/30 Bruno Medeiros <brunodomedeiros+spam com.gmail>:

  Example: consider a pure function that takes two strings as arguments,
 concatenates them, tolower's the first half, and toupper's the second half.


 
 Not that this in any way changes your argument, but I take it you do
 realise that toupper and tolower cannot be done in place, because the
 UTF-8 sequences representing dchar c might be a different length from
 the UTF-8 sequences representing toupper(c) or tolower(c).
 
 This is a common misconception popular among people who only use ASCII. :-)


I don't think that was the point of the post... but I never knew that. 
Can you give me an example of a character where the number of bytes in 
that character's representation changes when its case is changed?
Apr 30 2008
parent "Janice Caron" <caron800 googlemail.com> writes:
2008/4/30 Robert Fraser <fraserofthenight gmail.com>:

 Can
 you give me an example of a character where the number of bytes in that
 character's representation changes when its case is changed?


Your wish is my command:

Character '\u023A' is LATIN CAPITAL LETTER A WITH STROKE
In UTF-8: [ 0xC8, 0xBA ]

Character '\u2C65' is LATIN SMALL LETTER A WITH STROKE
In UTF-8: [ 0xE2, 0xB1, 0xA5 ]

So it gets longer when you lowercase it, shorter when you uppercase it.
Apr 30 2008
prev sibling next sibling parent sambeau <sambeau-nospam mac.com> writes:
Phil Wadler's ideas of "Blame" might be of interest to you

(essentially it's about mixing dynamic typing with static typing, but I think
it is relevent to pure/impure thoughts, too)

http://video.google.com/videoplay?docid=-4167170843018186532
Apr 30 2008
prev sibling next sibling parent reply Don <nospam nospam.com.au> 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:


The first case to consider is nested functions.

pure int func(int x)
{
    int var=0;
    int localfunc(int y) { ++var; return x*var;  }
    int localfunc2(int y) { return y; }
    return localfunc(x)*localfunc(x+1)+localfunc2(x);
}

localfunc() is definitely not pure. localfunc2() is not marked as pure.
But I think you can make a pretty decent argument that func() is pure.

But Walter's already said that pure functions will start out very 
restricted, and the rules will be relaxed over time. So it's not really 
worth worrying about the rules right now.
Apr 30 2008
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Don 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:


 
 The first case to consider is nested functions.
 


Nested functions are a more complicated case than regular functions, as 
they have other "inputs" other than the parameters: the outer variables.
So I think that if you implement partial pure semantics for nested 
functions, then you have it working for normal functions as well.


 
 But Walter's already said that pure functions will start out very 
 restricted, and the rules will be relaxed over time. So it's not really 
 worth worrying about the rules right now.


True, if we're thinking about compiler implementation only. But in terms 
of design, this might not be just an improvement, it could a crucial 
functionality. For example, consider this other example: Suppose you 
have a pure function with a local object and you want to mutate that 
object using a mutable method. If you are not able to call the mutable 
method in the pure function, you might not even be able to describe the 
method changes inside the pure function, because of Object encapsulation 
(example: changing a private member).

So partial pure semantics might be necessary if one wants pure functions 
to be able to work with objects in the general sense.

-- 
Bruno Medeiros - Software Developer, MSc. in CS/E graduate
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Apr 30 2008
next sibling parent reply Don <nospam nospam.com.au> writes:
Bruno Medeiros wrote:

 Don 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:


 The first case to consider is nested functions.


 
 Nested functions are a more complicated case than regular functions, as 
 they have other "inputs" other than the parameters: the outer variables.
 So I think that if you implement partial pure semantics for nested 
 functions, then you have it working for normal functions as well.


I don't think so, in practice. Nested functions are a lot easier to 
implement, since while compiling the outer function, the compiler always 
has access to the complete code of the inner function and can confirm 
that the outer function remains pure. It's impossible to change the 
nested function in a way that accidentally violates purity of the outer 
function -- it just won't compile.

But a regular function could appear in a completely different library, 
so the contextually purity needs to be enforced, and this would need a 
language change.


 

 But Walter's already said that pure functions will start out very 
 restricted, and the rules will be relaxed over time. So it's not 
 really worth worrying about the rules right now.


 
 True, if we're thinking about compiler implementation only. But in terms 
 of design, this might not be just an improvement, it could a crucial 
 functionality. For example, consider this other example: Suppose you 
 have a pure function with a local object and you want to mutate that 
 object using a mutable method. If you are not able to call the mutable 
 method in the pure function, you might not even be able to describe the 
 method changes inside the pure function, because of Object encapsulation 
 (example: changing a private member).
 
 So partial pure semantics might be necessary if one wants pure functions 
 to be able to work with objects in the general sense.


Yes, I don't see how objects can be used in pure functions without some 
form of 'contextually pure' functions.
Apr 30 2008
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Don wrote:

 Bruno Medeiros wrote:

 Don 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:


 The first case to consider is nested functions.


 Nested functions are a more complicated case than regular functions, 
 as they have other "inputs" other than the parameters: the outer 
 variables.
 So I think that if you implement partial pure semantics for nested 
 functions, then you have it working for normal functions as well.


 
 I don't think so, in practice. Nested functions are a lot easier to 
 implement, since while compiling the outer function, the compiler always 
 has access to the complete code of the inner function and can confirm 
 that the outer function remains pure. It's impossible to change the 
 nested function in a way that accidentally violates purity of the outer 
 function -- it just won't compile.
 
 But a regular function could appear in a completely different library, 
 so the contextually purity needs to be enforced, and this would need a 
 language change.
 


I state that if you have 'pure' implemented (in a sensible manner), it 
takes zero effort to implement partial/contextual pure.

The definition of partial pure functions requires no extra effort from 
the compiler to check. (The *same* check for normal pure functions is 
made: that no external state is accessed unless invariant)

The usage of partial pure functions also requires no extra effort. 
Inside a pure function body, the compiler already has to check if no 
external, non-invariant variables are accessed, like this:

   Foo globalVar;

   pure void func(...) {
     localVar = globalVar + 1; // not allowed

then just apply this same check on *any* expression, including function 
call expressions:

   partiallyPureFunction(localVar, globalVar); // not allowed
   partiallyPureFunction(localVar, localVar2); // but this is allowed


-- 
Bruno Medeiros - Software Developer, MSc. in CS/E graduate
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
May 01 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bruno Medeiros" wrote

 I state that if you have 'pure' implemented (in a sensible manner), it 
 takes zero effort to implement partial/contextual pure.

 The definition of partial pure functions requires no extra effort from the 
 compiler to check. (The *same* check for normal pure functions is made: 
 that no external state is accessed unless invariant)

 The usage of partial pure functions also requires no extra effort. Inside 
 a pure function body, the compiler already has to check if no external, 
 non-invariant variables are accessed, like this:

   Foo globalVar;

   pure void func(...) {
     localVar = globalVar + 1; // not allowed

 then just apply this same check on *any* expression, including function 
 call expressions:

   partiallyPureFunction(localVar, globalVar); // not allowed
   partiallyPureFunction(localVar, localVar2); // but this is allowed


What if localVar is a pointer to global data, or transitively contains a 
pointer to global data?  There is no way to know whether localVar is a 
pointer to global data or 'contained' heap data without lots of context 
checking.  If partially pure functions with mutable parameters were allowed, 
I'd say it's a requirement that you can only call them from partially or 
fully pure functions, as local pointers from those functions are guaranteed 
to be contained within the function.

-Steve
May 01 2008
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Steven Schveighoffer wrote:

 "Bruno Medeiros" wrote

 I state that if you have 'pure' implemented (in a sensible manner), it 
 takes zero effort to implement partial/contextual pure.

 The definition of partial pure functions requires no extra effort from the 
 compiler to check. (The *same* check for normal pure functions is made: 
 that no external state is accessed unless invariant)

 The usage of partial pure functions also requires no extra effort. Inside 
 a pure function body, the compiler already has to check if no external, 
 non-invariant variables are accessed, like this:

   Foo globalVar;

   pure void func(...) {
     localVar = globalVar + 1; // not allowed

 then just apply this same check on *any* expression, including function 
 call expressions:

   partiallyPureFunction(localVar, globalVar); // not allowed
   partiallyPureFunction(localVar, localVar2); // but this is allowed


 
 What if localVar is a pointer to global data, or transitively contains a 
 pointer to global data?  There is no way to know whether localVar is a 
 pointer to global data or 'contained' heap data without lots of context 
 checking.  


Whatever checks you have to make for localVar, you still have to do them 
with normal pure. (And not that it matters to the point, how do you 
initialize a local var with global data?)


 If partially pure functions with mutable parameters were allowed, 
 I'd say it's a requirement that you can only call them from partially or 
 fully pure functions, as local pointers from those functions are guaranteed 
 to be contained within the function.
 


I'm not sure I understand what you're saying. Are you saying that 
partially pure functions should not be called from *non-pure* functions? 
What's the sense in that?


-- 
Bruno Medeiros - Software Developer, MSc. in CS/E graduate
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
May 01 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bruno Medeiros" wrote

 Steven Schveighoffer wrote:

 "Bruno Medeiros" wrote

 I state that if you have 'pure' implemented (in a sensible manner), it 
 takes zero effort to implement partial/contextual pure.

 The definition of partial pure functions requires no extra effort from 
 the compiler to check. (The *same* check for normal pure functions is 
 made: that no external state is accessed unless invariant)

 The usage of partial pure functions also requires no extra effort. 
 Inside a pure function body, the compiler already has to check if no 
 external, non-invariant variables are accessed, like this:

   Foo globalVar;

   pure void func(...) {
     localVar = globalVar + 1; // not allowed

 then just apply this same check on *any* expression, including function 
 call expressions:

   partiallyPureFunction(localVar, globalVar); // not allowed
   partiallyPureFunction(localVar, localVar2); // but this is allowed


 What if localVar is a pointer to global data, or transitively contains a 
 pointer to global data?  There is no way to know whether localVar is a 
 pointer to global data or 'contained' heap data without lots of context 
 checking.


 Whatever checks you have to make for localVar, you still have to do them 
 with normal pure. (And not that it matters to the point, how do you 
 initialize a local var with global data?)


 If partially pure functions with mutable parameters were allowed, I'd say 
 it's a requirement that you can only call them from partially or fully 
 pure functions, as local pointers from those functions are guaranteed to 
 be contained within the function.


 I'm not sure I understand what you're saying. Are you saying that 
 partially pure functions should not be called from *non-pure* functions? 
 What's the sense in that?


From the digitalmars web site:

"A pure function can throw exceptions and allocate memory via a 
NewExpression."

So in the case of a partially pure function that takes a char array:

pure void f(char[] x) {...}

Let's say I have a non-pure function g:

void g()
{
    char[] v;
    ...
    f(v);
}

In the ..., v can be set to local mutable heap data (via new char[x] or 
whatever), or it could be set to point to a global mutable string.  How can 
the compiler be sure without severe context analysis?  The point is, in 
order to ensure context-free lexical analysis by the compiler, it must 
disallow calling f from a non-pure function.

Contrast that from a pure version of g:

pure void g()
{
   char[] v;
   ...
   f(v);
}

Because g is now pure, it is a requirement that v cannot be assigned to some 
global variable.  The fact that g is pure ensures that f can safely be 
called.  v can only be set by calling a new expression.

-Steve
May 01 2008
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Steven Schveighoffer wrote:

 
 
 So in the case of a partially pure function that takes a char array:
 
 pure void f(char[] x) {...}
 
 Let's say I have a non-pure function g:
 
 void g()
 {
     char[] v;
     ...
     f(v);
 }
 
 In the ..., v can be set to local mutable heap data (via new char[x] or 
 whatever), or it could be set to point to a global mutable string.  How can 
 the compiler be sure without severe context analysis?  The point is, in 
 order to ensure context-free lexical analysis by the compiler, it must 
 disallow calling f from a non-pure function.
 


Huh? You're mixing things up.
Yes, if g() is not pure, then the compiler will not check if v points to 
global data or not. Thus we cannot guarantee that calling "f(v)" will 
not change global state. But so what?
That doesn't mean we shouldn't allow it. It just means such call may 
have side-effects, and the compiler should threat that as a normal 
function call (make no particular pure optimizations). Thus "partially" 
pure: pure in some contexts, impure in other contexts.



-- 
Bruno Medeiros - Software Developer, MSc. in CS/E graduate
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
May 01 2008
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bruno Medeiros" wrote

 Steven Schveighoffer wrote:

 So in the case of a partially pure function that takes a char array:

 pure void f(char[] x) {...}

 Let's say I have a non-pure function g:

 void g()
 {
     char[] v;
     ...
     f(v);
 }

 In the ..., v can be set to local mutable heap data (via new char[x] or 
 whatever), or it could be set to point to a global mutable string.  How 
 can the compiler be sure without severe context analysis?  The point is, 
 in order to ensure context-free lexical analysis by the compiler, it must 
 disallow calling f from a non-pure function.


 Huh? You're mixing things up.
 Yes, if g() is not pure, then the compiler will not check if v points to 
 global data or not. Thus we cannot guarantee that calling "f(v)" will not 
 change global state. But so what?
 That doesn't mean we shouldn't allow it. It just means such call may have 
 side-effects, and the compiler should threat that as a normal function 
 call (make no particular pure optimizations). Thus "partially" pure: pure 
 in some contexts, impure in other contexts.


OK, I think I see what the barrier here is.  Walter and Andrei's version of 
pure is supposed to be for solving multithreading issues.  There is an 
attribute of D pure functions that is inherently true in functional 
programming languages.  Not only does a pure function have no side effects, 
but nothing outside the pure function can affect its execution.  If v points 
to global data, and some other thread changes that data mid-way through the 
function execution, the function might crash or throw an exception because 
it is expecting to be the only one that can change it's own data.  With that 
in mind, partially pure functions that have mutable parameters cannot have 
that attribute unless it is guaranteed that those mutable parameters won't 
be changed by anything outside the partially pure function.  The only way to 
guarantee that is to only allow calling that function from another pure or 
partially pure function.

-Steve
May 01 2008
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bruno Medeiros" wrote

 Yes, if g() is not pure, then the compiler will not check if v points to 
 global data or not. Thus we cannot guarantee that calling "f(v)" will not 
 change global state. But so what?
 That doesn't mean we shouldn't allow it. It just means such call may have 
 side-effects, and the compiler should threat that as a normal function 
 call (make no particular pure optimizations). Thus "partially" pure: pure 
 in some contexts, impure in other contexts.


I re-read this and I see what you are proposing.

I can see how that would work, but you would definitely need another 
keyword.  Any time a developer sees the pure keyword, he will assume he 
doesn't need to worry about thread issues.  However, a partially pure 
function would be subject to thread issues when not called from a pure 
function.

I still think it would be a worthwhile feature to have, as it would save on 
implementing lots of functionality more than once.

BTW, forget my other post, we were arguing about totally different things.

-Steve
May 01 2008
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bruno Medeiros" wrote

 Don wrote:

 But Walter's already said that pure functions will start out very 
 restricted, and the rules will be relaxed over time. So it's not really 
 worth worrying about the rules right now.


 True, if we're thinking about compiler implementation only. But in terms 
 of design, this might not be just an improvement, it could a crucial 
 functionality. For example, consider this other example: Suppose you have 
 a pure function with a local object and you want to mutate that object 
 using a mutable method. If you are not able to call the mutable method in 
 the pure function, you might not even be able to describe the method 
 changes inside the pure function, because of Object encapsulation 
 (example: changing a private member).

 So partial pure semantics might be necessary if one wants pure functions 
 to be able to work with objects in the general sense.


I really like the idea of 'partially pure'.  It basically allows you to 
build functions from modular pieces, which is key to any successful project. 
To have to implement every piece of common functions every time you write 
one seems very error-prone to me.

However, I tend to agree with Don.  What you want is a relaxation of the 
rules, which can easily happen after pure functions are supported.  In fact, 
you don't even need any new keywords or syntax, the compiler just implies 
the partial purity from the parameter/return types.

As for your idea, to be complete, I'd say there are different levels of 
partially pure functions.

level 1: mutable return value, but const/invariant parameters.  These 
functions can be re-ordered, and can be called from pure or unpure 
functions.  The result cannot be memoized.
level 2: mutable parameters.  These functions cannot be re-ordered, but can 
be used inside pure functions.  They cannot be called from non-pure 
functions.  These also cannot be memoized.

There may be more levels, but I think that's at least a start.

An example of a level 1 partially pure function is new.

A level 2 function may need a new keyword, as the contract is different than 
a level 1 or pure function in that it cannot be called from a non-pure 
function.  Level 1 functions are no different contract-wise than fully pure 
functions, just the optimization is different (cannot memoize).

-Steve
Apr 30 2008
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Steven Schveighoffer wrote:

 
 However, I tend to agree with Don.  What you want is a relaxation of the 
 rules, which can easily happen after pure functions are supported.  In fact, 
 you don't even need any new keywords or syntax, the compiler just implies 
 the partial purity from the parameter/return types.
 


The compiler can only infer partial purity if it has access to the 
function body (just the same as it can infer normal purity). But if you 
only have a function signature, you need a keyword.


 As for your idea, to be complete, I'd say there are different levels of 
 partially pure functions.
 
 level 1: mutable return value, but const/invariant parameters.  These 
 functions can be re-ordered, and can be called from pure or unpure 
 functions.  The result cannot be memoized.


This is already a regular pure function. The idea that a pure function 
has to return an invariant is a misconception, it can safely return 
mutable data. It can me memoized just the same (although a copy would 
have to be made if the result is not invariant)


-- 
Bruno Medeiros - Software Developer, MSc. in CS/E graduate
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
May 01 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bruno Medeiros" wrote

 Steven Schveighoffer wrote:

 However, I tend to agree with Don.  What you want is a relaxation of the 
 rules, which can easily happen after pure functions are supported.  In 
 fact, you don't even need any new keywords or syntax, the compiler just 
 implies the partial purity from the parameter/return types.


 The compiler can only infer partial purity if it has access to the 
 function body (just the same as it can infer normal purity). But if you 
 only have a function signature, you need a keyword.


I meant an *extra* keyword.  If you mark a function as pure, it can be 
partially pure or fully pure depending on the arguments.  However, having an 
extra keyword lets the developer decide whether he is expecting a function 
to be partially pure or not, so there are no surprises :)  I'd vote for a 
new keyword, but this does not need to happen right away.


 As for your idea, to be complete, I'd say there are different levels of 
 partially pure functions.

 level 1: mutable return value, but const/invariant parameters.  These 
 functions can be re-ordered, and can be called from pure or unpure 
 functions.  The result cannot be memoized.


 This is already a regular pure function. The idea that a pure function has 
 to return an invariant is a misconception, it can safely return mutable 
 data. It can me memoized just the same (although a copy would have to be 
 made if the result is not invariant)


I would hope that the compiler would not memoize if I returned a mutable 
piece of data, as I would generally expect to use this function as a way to 
initialize some data that I want to build with (in a pure function or 
otherwise).  If I wanted it to memoize, I can return invariant.  For 
example, to memoize on 'new' would be a waste, but 'new' can be considered a 
pure (arguably partially pure) function.  Sometimes memoization is not 
desirable, especially if you are rarely calling the pure function with the 
same arguments.

I guess it all depends on what you consider partially pure :)  I believe the 
current rules as stated on D's website require invariant return data, or 
data that can be implicitly cast to invariant.

-Steve
May 01 2008
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Steven Schveighoffer wrote:

 "Bruno Medeiros" wrote

 Steven Schveighoffer wrote:

 However, I tend to agree with Don.  What you want is a relaxation of the 
 rules, which can easily happen after pure functions are supported.  In 
 fact, you don't even need any new keywords or syntax, the compiler just 
 implies the partial purity from the parameter/return types.


 The compiler can only infer partial purity if it has access to the 
 function body (just the same as it can infer normal purity). But if you 
 only have a function signature, you need a keyword.


 
 I meant an *extra* keyword.  If you mark a function as pure, it can be 
 partially pure or fully pure depending on the arguments.  However, having an 
 extra keyword lets the developer decide whether he is expecting a function 
 to be partially pure or not, so there are no surprises :)  I'd vote for a 
 new keyword, but this does not need to happen right away.
 


That decision of "whether he is expecting a function to be partially 
pure or " pure is not a useful decision to have to make, it's redundant 
(and thus cumbersome) to ask the programmer to specify that.

Also, having two different keywords would impossibilitate or difficult 
templating of constness (like with the "scoped const" proposal).

Just think of 'pure' as meaning: this function does not depend on, or 
modify, external state. (external state being any data other than the 
parameters)



 As for your idea, to be complete, I'd say there are different levels of 
 partially pure functions.

 level 1: mutable return value, but const/invariant parameters.  These 
 functions can be re-ordered, and can be called from pure or unpure 
 functions.  The result cannot be memoized.


 This is already a regular pure function. The idea that a pure function has 
 to return an invariant is a misconception, it can safely return mutable 
 data. It can me memoized just the same (although a copy would have to be 
 made if the result is not invariant)


 
 I would hope that the compiler would not memoize if I returned a mutable 
 piece of data, as I would generally expect to use this function as a way to 
 initialize some data that I want to build with (in a pure function or 
 otherwise).  If I wanted it to memoize, I can return invariant.  For 
 example, to memoize on 'new' would be a waste, but 'new' can be considered a 
 pure (arguably partially pure) function.  Sometimes memoization is not 
 desirable, especially if you are rarely calling the pure function with the 
 same arguments.
 


I said the compiler *could* memoize the result just the same. Doesn't 
mean it *should* memoize if the result is mutable.
As a matter of fact, even if the result is invariant, doesn't mean the 
compiler should memoize it. Memoization is a complicated optimization 
that likely only the user knows when it should be applied, not the compiler.


 I guess it all depends on what you consider partially pure :)  I believe the 
 current rules as stated on D's website require invariant return data, or 
 data that can be implicitly cast to invariant.
 
 -Steve 
 
 


In Andrei's latest presentation 
(http://www.digitalmars.com/d/2.0/accu-functional.pdf)
when he lists the requirements for pure, it does not say that is should 
return invariant data. (and I'm assuming those requirements are complete)


-- 
Bruno Medeiros - Software Developer, MSc. in CS/E graduate
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
May 01 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Bruno Medeiros" wrote

 Steven Schveighoffer wrote:

 "Bruno Medeiros" wrote

 Steven Schveighoffer wrote:

 However, I tend to agree with Don.  What you want is a relaxation of 
 the rules, which can easily happen after pure functions are supported. 
 In fact, you don't even need any new keywords or syntax, the compiler 
 just implies the partial purity from the parameter/return types.


 The compiler can only infer partial purity if it has access to the 
 function body (just the same as it can infer normal purity). But if you 
 only have a function signature, you need a keyword.


 I meant an *extra* keyword.  If you mark a function as pure, it can be 
 partially pure or fully pure depending on the arguments.  However, having 
 an extra keyword lets the developer decide whether he is expecting a 
 function to be partially pure or not, so there are no surprises :)  I'd 
 vote for a new keyword, but this does not need to happen right away.


 That decision of "whether he is expecting a function to be partially pure 
 or " pure is not a useful decision to have to make, it's redundant (and 
 thus cumbersome) to ask the programmer to specify that.


It's not possible to call a partially pure function with mutable arguments 
from a non-pure function.  Doing so would be a nightmare for the compiler. 
So from a maintainability perspective, changing a function from fully pure 
to partially pure changes the contract that the function provides.

However, changing from fully pure to partially pure involves changing an 
argument type, so in essence, code that used the fully pure function would 
break anyways...  Having an extra keyword for 'partially pure' is probably 
not necessary, so I agree with you now.


 Also, having two different keywords would impossibilitate or difficult 
 templating of constness (like with the "scoped const" proposal).

 Just think of 'pure' as meaning: this function does not depend on, or 
 modify, external state. (external state being any data other than the 
 parameters)


For D, there is also the notion that a pure function will not be affected by 
it's parameters changing mid-way through the function.


 As for your idea, to be complete, I'd say there are different levels of 
 partially pure functions.

 level 1: mutable return value, but const/invariant parameters.  These 
 functions can be re-ordered, and can be called from pure or unpure 
 functions.  The result cannot be memoized.


 This is already a regular pure function. The idea that a pure function 
 has to return an invariant is a misconception, it can safely return 
 mutable data. It can me memoized just the same (although a copy would 
 have to be made if the result is not invariant)


 I would hope that the compiler would not memoize if I returned a mutable 
 piece of data, as I would generally expect to use this function as a way 
 to initialize some data that I want to build with (in a pure function or 
 otherwise).  If I wanted it to memoize, I can return invariant.  For 
 example, to memoize on 'new' would be a waste, but 'new' can be 
 considered a pure (arguably partially pure) function.  Sometimes 
 memoization is not desirable, especially if you are rarely calling the 
 pure function with the same arguments.


 I said the compiler *could* memoize the result just the same. Doesn't mean 
 it *should* memoize if the result is mutable.
 As a matter of fact, even if the result is invariant, doesn't mean the 
 compiler should memoize it. Memoization is a complicated optimization that 
 likely only the user knows when it should be applied, not the compiler.


I suspect the goal of Walter is to not have the developer make the decision 
to memoize...  Similar to how we do not have the ability to force inlining, 
but we have the ability to force NOT inlining (by making a function opaque). 
I believe making a pure function return mutable heap data should be a signal 
that the compiler does not memoize the result.


 I guess it all depends on what you consider partially pure :)  I believe 
 the current rules as stated on D's website require invariant return data, 
 or data that can be implicitly cast to invariant.


 In Andrei's latest presentation 
 (http://www.digitalmars.com/d/2.0/accu-functional.pdf)
 when he lists the requirements for pure, it does not say that is should 
 return invariant data. (and I'm assuming those requirements are complete)


Those requirements are not complete.  For instance, the web site says that 
pure functions can call new expressions, but that is not stated in the pdf 
(or at least, I don't remember seeing it).  I think it will eventually be 
stated that pure functions initially will have to return invariant data, or 
data that can be implicitly cast to invariant.  Unless I can convince Andrei 
otherwise :)

-Steve
May 01 2008
next sibling parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Steven Schveighoffer wrote:

 "Bruno Medeiros" wrote

 I guess it all depends on what you consider partially pure :)  I believe 
 the current rules as stated on D's website require invariant return data, 
 or data that can be implicitly cast to invariant.


 In Andrei's latest presentation 
 (http://www.digitalmars.com/d/2.0/accu-functional.pdf)
 when he lists the requirements for pure, it does not say that is should 
 return invariant data. (and I'm assuming those requirements are complete)


 
 Those requirements are not complete.  For instance, the web site says that 
 pure functions can call new expressions, but that is not stated in the pdf 
 (or at least, I don't remember seeing it).  I think it will eventually be 
 stated that pure functions initially will have to return invariant data, or 
 data that can be implicitly cast to invariant.  Unless I can convince Andrei 
 otherwise :)
 
 -Steve 
 
 


It's not stated in the pdf "that pure functions can call new 
expressions" because it only states what pure functions *cannot* do. 
What they can do is everything else. So new expressions are allowed 
(likely following the same rules as function calling, ie, only pure 
constructors are allowed).

-- 
Bruno Medeiros - Software Developer, MSc. in CS/E graduate
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
May 02 2008
prev sibling parent reply mort <mortm gmail.com> writes:
I'm not an expert on D, but it looks like a pretty nice language.  While
reading about 'pure' recently, however, I found what appeared to be pretty
major usability problems with the idea as it was presented:

- Pure functions can have local mutable state, but aren't allowed to factor the
logic for manipulating that state out into functions (since such a function
would be non-pure).

- Pure functions can't be applied to mutable data.  So you potentially need a
mutable non-pure version of each pure function.

An elegant solution to both of these problems would seem to be the one proposed
in this thread - get rid of the requirement that parameters be invariant.  The
first problem above is solved by pure functions with mutable parameters, and
the second by pure functions with const parameters.

Special optimizations that require purity and parameter invariance can always
be done by creating a specialized version of each pure function that's invoked
when the arguments are known to be invariant.  Let the compiler handle the
duplication - don't make the programmer copy/paste.

Thanks
Jul 31 2008
parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
On Fri, 01 Aug 2008 03:46:30 +0200, mort <mortm gmail.com> wrote:


 - Pure functions can't be applied to mutable data.  So you potentially  
 need a mutable non-pure version of each pure function.


I would believe the following to work:

pure SomeStruct foo(invariant SomeStruct f);

foreach (ref s; SomeStructArray)
	s = foo(cast(invariant)s);

-- 
Simen
Aug 01 2008
prev sibling next sibling parent reply 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
parent reply 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
parent reply 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
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
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
parent Jason House <jason.james.house gmail.com> writes:
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
prev sibling parent Sean Reque <seanthenewt yahoo.com> writes:
mort Wrote:


 I'm not an expert on D, but it looks like a pretty nice language.  While
reading about 'pure' recently, however, I found what appeared to be pretty
major usability problems with the idea as it was presented:
 
 - Pure functions can have local mutable state, but aren't allowed to factor
the logic for manipulating that state out into functions (since such a function
would be non-pure).
 
 - Pure functions can't be applied to mutable data.  So you potentially need a
mutable non-pure version of each pure function.
 
 An elegant solution to both of these problems would seem to be the one
proposed in this thread - get rid of the requirement that parameters be
invariant.  The first problem above is solved by pure functions with mutable
parameters, and the second by pure functions with const parameters.
 
 Special optimizations that require purity and parameter invariance can always
be done by creating a specialized version of each pure function that's invoked
when the arguments are known to be invariant.  Let the compiler handle the
duplication - don't make the programmer copy/paste.
 
 Thanks
 
 


I agree with you completely, and was planning on making an similar post about
the subject.

Take one of the string functions, for instance, countchars. It has the
following signature:

 size_t countchars(string s, string pattern);
  
This function etiher is or could be pure. However, the function would work just
as well when operating on const (char)[] data, which is potentially mutable, or
char[] data, which is explicitly mutable. Being able to have a conditionally
pure function, one that was pure if its arguments were invariant and not pure
if they were not, would allow this function to work for both mutable and
immutable data, and gain all the optimization benefits of a pure function if
its parameters were indeed invariant.

There are of course occasions where functions might need to act differently
based on the invariance of its parameters. string.split, for instance, would
probably want to copy the data it returns if its parameters were not invariant.
However, I think differences like these could easily be handled with D's
compile-time reflection abilities.

Lastly, I never thought about the case where a pure function would need to call
another function to operate on explicitly mutable but temporary local data. It
would be nice to have that handled as well! It seems like the more you dig in
to pure functions, the more you realize that the compiler needs to be able to
be very smart to make the concept usable for programmers. As it stands now, it
seems difficult for pure functions to interact with the rest of D.
Aug 01 2008