September 22, 2010
On Wed, 22 Sep 2010 15:08:26 -0400, Don <nospam@nospam.com> wrote:

> Robert Jacques wrote:
>> On Wed, 22 Sep 2010 11:44:00 -0400, Don <nospam@nospam.com> wrote:
>>
>>> Robert Jacques wrote:
>>>> On Wed, 22 Sep 2010 07:54:26 -0400, Michel Fortin <michel.fortin@michelf.com> wrote:
>>>>
>>>>> On 2010-09-22 01:26:01 -0400, "Robert Jacques" <sandford@jhu.edu> said:
>>>>>
>>>>>> So removing the concurrency safety from pure would greatly  expand the number of pure functions, however, automatic parallelism would  be lost.
>>>>>
>>>>> Don clearly mentioned that this is not lost. Basically, for safe parallelism what you need is a function that has a) pure and b) no mutable reference parameter. Both are easily checkable at compile time, you'd just need to change your test for pure for a test that also checks the arguments.
>>>>  What is lost is my ability to declare a function does x in the signature and for the compiler to check that. I really want to know if code monkey A changed some type's implementation to be thread unsafe, because detecting and tracking down a loss of performance due to loss of automatic parallelism is devilish.
>>>
>>> No, you haven't lost that at all. Any function marked as pure still has no access to any state, other than what is provided by its parameters. It is still thread-safe.
>>  No, it isn't. A strongly-pure function is thread safe, but a weakly-pure function isn't. Since strong/weak is automatically determined by the compiler, a function's strength can switch due to long distance code changes.
>
> This is completely incorrect. It can only change strength if its signature changes.

Hypothetical counter-case

struct S
{
   version(stronglypure)
     string s;
   else
     char[] s;
}

pure foo(S s); // changes strength depending on S' contents

-Steve
September 22, 2010
On 9/22/10 9:14 PM, Steven Schveighoffer wrote:
> Hypothetical counter-case
>
> struct S
> {
> version(stronglypure)
> string s;
> else
> char[] s;
> }
>
> pure foo(S s); // changes strength depending on S' contents
>
> -Steve

This is a change to the signature of foo – S with the stronglypure version defined and S without it are two completely distinct types.
September 22, 2010
On Wed, 22 Sep 2010 15:21:57 -0400, klickverbot <see@klickverbot.at> wrote:

> On 9/22/10 9:14 PM, Steven Schveighoffer wrote:
>> Hypothetical counter-case
>>
>> struct S
>> {
>> version(stronglypure)
>> string s;
>> else
>> char[] s;
>> }
>>
>> pure foo(S s); // changes strength depending on S' contents
>>
>> -Steve
>
> This is a change to the signature of foo – S with the stronglypure version defined and S without it are two completely distinct types.

Wait, I didn't change foo's signature at all.  This is what the OP meant by long-range changes.  S can be defined far away from foo, and out of the author of foo's control.

-Steve
September 22, 2010
Don wrote:
> Don wrote:
>> The docs currently state that:
> 
>> PROPOSAL:
>> Drop the first requirement. Only one requirement is necessary:
>>
>> A pure function does not read or write any global mutable state.
>>
> 
> Wow. It seems that not one person who has responded so far has understood this proposal! I'll try again. Under this proposal:
> 
> If you see a function which has mutable parameters, but is marked as 'pure', you can only conclude that it doesn't use global variables. That's not much use on it's own. Let's call this a 'weakly-pure' function.
> 
> However, if you see a function maked as 'pure', which also has only immutable parameters, you have the same guarantee which 'pure' gives us as the moment. Let's call this a 'strongly-pure' function.
> 
> The benefit of the relaxed rule is that a strongly-pure function can call a weakly-pure functions, while remaining strongly-pure.
> This allows very many more functions to become strongly pure.
> 
> The point of the proposal is *not* to provide the weak guarantee. It is to provide the strong guarantee in more situations.

A pure function also cannot modify any data via its parameters. In other words, its parameters must be transitively const.
September 22, 2010
Steven Schveighoffer wrote:
> On Wed, 22 Sep 2010 15:21:57 -0400, klickverbot <see@klickverbot.at> wrote:
> 
>> On 9/22/10 9:14 PM, Steven Schveighoffer wrote:
>>> Hypothetical counter-case
>>>
>>> struct S
>>> {
>>> version(stronglypure)
>>> string s;
>>> else
>>> char[] s;
>>> }
>>>
>>> pure foo(S s); // changes strength depending on S' contents
>>>
>>> -Steve
>>
>> This is a change to the signature of foo – S with the stronglypure version defined and S without it are two completely distinct types.
> 
> Wait, I didn't change foo's signature at all.  This is what the OP meant by long-range changes.  S can be defined far away from foo, and out of the author of foo's control.
> 
> -Steve

Is that really what he meant?
Note that foo() would need to be recompiled, and the silent change in strength would occur only if it still compiles despite a significant change in the definition of one of types.

If you change the definition of a type, you're always going to have influences everywhere it's used in a function definition. I'd hardly call that a 'long-range' change.

By contrast, in a language where you don't have pure at all, if someone sticks in a global variable somewhere, (even in a separate library), then code could suddenly have severe contention with another thread.
That's long range, and nearly impossible to track down.

September 22, 2010
On Wed, 22 Sep 2010 15:52:03 -0400, Don <nospam@nospam.com> wrote:

> Steven Schveighoffer wrote:
>> On Wed, 22 Sep 2010 15:21:57 -0400, klickverbot <see@klickverbot.at> wrote:
>>
>>> On 9/22/10 9:14 PM, Steven Schveighoffer wrote:
>>>> Hypothetical counter-case
>>>>
>>>> struct S
>>>> {
>>>> version(stronglypure)
>>>> string s;
>>>> else
>>>> char[] s;
>>>> }
>>>>
>>>> pure foo(S s); // changes strength depending on S' contents
>>>>
>>>> -Steve
>>>
>>> This is a change to the signature of foo – S with the stronglypure version defined and S without it are two completely distinct types.
>>  Wait, I didn't change foo's signature at all.  This is what the OP meant by long-range changes.  S can be defined far away from foo, and out of the author of foo's control.
>>  -Steve
>
> Is that really what he meant?
> Note that foo() would need to be recompiled, and the silent change in strength would occur only if it still compiles despite a significant change in the definition of one of types.

This isn't hard to come up with:

struct S
{
   string s;
   version(stronglypure)
   {
   }
   else
     char[] notused;
}

>
> If you change the definition of a type, you're always going to have influences everywhere it's used in a function definition. I'd hardly call that a 'long-range' change.

I think the OP's request is to be able to tell the compiler "I want you to make *sure* this function is strongly pure."  Not that I think it's terribly important, I'm just trying to convey what has been said.

Adding another member to a struct is a much better example than my first, and I don't think it's an uncommon thing.  Whether its extremely important to have this ability, I'm not sure about.  It's sort of akin to having an inline directive.

-Steve
September 22, 2010
On Wed, 22 Sep 2010 15:36:34 -0400, Walter Bright <newshound2@digitalmars.com> wrote:

> Don wrote:
>> Don wrote:
>>> The docs currently state that:
>>
>>> PROPOSAL:
>>> Drop the first requirement. Only one requirement is necessary:
>>>
>>> A pure function does not read or write any global mutable state.
>>>
>>  Wow. It seems that not one person who has responded so far has understood this proposal! I'll try again. Under this proposal:
>>  If you see a function which has mutable parameters, but is marked as 'pure', you can only conclude that it doesn't use global variables. That's not much use on it's own. Let's call this a 'weakly-pure' function.
>>  However, if you see a function maked as 'pure', which also has only immutable parameters, you have the same guarantee which 'pure' gives us as the moment. Let's call this a 'strongly-pure' function.
>>  The benefit of the relaxed rule is that a strongly-pure function can call a weakly-pure functions, while remaining strongly-pure.
>> This allows very many more functions to become strongly pure.
>>  The point of the proposal is *not* to provide the weak guarantee. It is to provide the strong guarantee in more situations.
>
> A pure function also cannot modify any data via its parameters. In other words, its parameters must be transitively const.

Yes, a strongly pure function must have those traits.

But, purity exists to allow for optimization.  A weakly pure function cannot be optimized anymore than a normal function, but a strongly pure can still be optimized even if it calls weakly-pure functions.

I'll give you an example (with a new keyword to help you understand the difference):

weaklypure void reverse(int[] x)
{
   for(int i = 0; i * 2 < x.length; i++)
       swap(x[i], x[$-1-i]);
}

pure int foo(const(int)[] x)
{
    auto x2 = x.dup;
    reverse(x2);
    // do some calculation on x2
    ...
    return calculation;
}

Hopefully you can see how foo still is pure, while being able to call reverse.  Essentially, weakly-pure functions can be used to build strongly-pure functions.

-Steve
September 22, 2010
> weaklypure void reverse(int[] x)
> {
>     for(int i = 0; i * 2 < x.length; i++)
>         swap(x[i], x[$-1-i]);
> }
> pure int foo(const(int)[] x)
> {
>      auto x2 = x.dup;
>      reverse(x2);
>      // do some calculation on x2
>      ...
>      return calculation;
> }

noglobal void reverse(MyClass x)
{
  x.text = "";
}

So weakly-pure should not access global stuff. But that is harder to track by the compiler with mutable parameters.

Or weakly-pure is only noglobal when called in pure routines, because of the immutable barrier.

Unwritten contract, not checked by the compiler?  (Like property getters shouldn't modify the "state" of the object.)

September 22, 2010
On Wed, 22 Sep 2010 16:42:09 -0400, sclytrack <sclytrack@fake.com> wrote:

>
>> weaklypure void reverse(int[] x)
>> {
>>     for(int i = 0; i * 2 < x.length; i++)
>>         swap(x[i], x[$-1-i]);
>> }
>> pure int foo(const(int)[] x)
>> {
>>      auto x2 = x.dup;
>>      reverse(x2);
>>      // do some calculation on x2
>>      ...
>>      return calculation;
>> }
>
> noglobal void reverse(MyClass x)
> {
>   x.text = "";
> }
>
> So weakly-pure should not access global stuff. But that is harder
> to track by the compiler with mutable parameters.

No, it just means they cannot access data except through their arguments.  Global stuff is perfectly valid to pass in.  However, any references must not be shared, because those could be actively changed by other threads.

> Or weakly-pure is only noglobal when called in pure routines, because of the
> immutable barrier.

pure, weak or strong, means you cannot access global variables.  e.g.:

int x;
shared int y;

pure foo(int *n)
{
   x = 5; // illegal
   *n = 5; // fine
}

foo(&x); // fine, x is TLS, it is guaranteed not to change from another thread.
foo(&y); // nope

The difference between weak and strong is that weak pure functions cannot be more optimized than normal functions.  Strong pure functions can enjoy the optimizations that functional languages have.

-Steve
September 22, 2010
On Wed, 22 Sep 2010 16:03:08 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> I'll give you an example (with a new keyword to help you understand the difference):
>
> weaklypure void reverse(int[] x)
> {
>     for(int i = 0; i * 2 < x.length; i++)
>         swap(x[i], x[$-1-i]);
> }

A better example -- std.algorithm.sort can be made weakly pure (at least for arrays).  It doesn't affect anything but the array passed in.

Without this, you can't sort arrays within pure functions unless you make a strong-pure functional sort, which will likely not perform as well.

I'm kind of excited to think that D might be able to parallelize things in the right places, and allow imperative algorithms to stay imperative within those parallelized functions.

-Steve