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

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. :-)

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

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.

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

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?

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.

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.

"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

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