September 23, 2010
Tomek Sowiński napisał:

>> Note that this is possible only because immutable and const are transitive. It wouldn't be possible with head-const, or logical const.
> 
> But it would be possible with tail const. Quite a few functions could be made immutably pure if it meant tail immutability of their parameters. One example are manipulations of ranges on immutable structures.

I take that back. Guarantees on parameters still hold with tail const but it's not a big win in context of purity. It is a huge win elsewhere, though.

-- 
Tomek
September 24, 2010
On Thu, 23 Sep 2010 18:26:28 -0400, Robert Jacques <sandford@jhu.edu> wrote:

> On Thu, 23 Sep 2010 10:05:45 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>
>> On Wed, 22 Sep 2010 21:48:19 -0400, Robert Jacques <sandford@jhu.edu> wrote:
>>
>>> On Wed, 22 Sep 2010 13:10:36 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>>>
>>>> On Wed, 22 Sep 2010 12:00:16 -0400, Robert Jacques <sandford@jhu.edu> wrote:
>>>>> What about value types?
>>>>
>>>> Value types are implicitly convertable to immutable, so they can be strongly-pure.
>>>
>>> No their not. Remember, arrays and other structs are value types in the type system. Logically, they may be reference types, but as far as their type signature goes, they are value types.
>>
>> Arrays are not value types.  A value type is one that contains no references, no matter how deep.  It is irrelevant if you have to spell out the references or not.
>
> Arrays are implemented as a struct. And as per the language spec: (http://www.digitalmars.com/d/2.0/struct.html) all structs are value types *to the compiler*. This doesn't mean that logically, from the programmer's point of view, they aren't providing reference semantics.

structs can have value copy semantics.  But for a struct that contains a reference, the references have reference semantics, which makes the struct a reference type.

Look, terms can be debated, but here is the bottom line: A struct with a reference type inside it cannot be implicitly converted to immutable, whereas a struct with only non-reference types in it can.  The compiler knows this, and makes its decision on what must be immutable or not based on that knowledge.  Call it whatever you want, but that's how it works internally, and it's not hidden from the compiler.

When you say "what about value types" what do you mean?  I thought you meant types which have value copy semantics, which can only have non-references in them.

A type that has both value copy semantics and reference semantics, I guess you could call it a hybrid type (an array is such a type), but primarily it is treated like a reference.  If that's what you're asking about, then those also would make a function weakly pure.

>
>> another example of something that is not a value type:
>>
>> alias int * iptr;
>>
>> foo(iptr p);
>>
>> iptr is not a value type just because you don't see any * in the signature.
>
> *sigh* I explicitly referred to the type system/compiler. And to the type system iptr is a pointer, no matter what you call it.

This is also purely a reference type.  Semantically, it's exactly the same as a pointer, except you have to refer to the member.

struct iptr
{
   int *ptr;
}

You are splitting hairs here, and it's not really furthering the discussion.

>
>>>>
>>>> But the compiler will be able to tell.  I think adding a __traits(isStronglyPure, symbol) will be good for those rare occasions where you really want to ensure purity.
>>>>
>>>> static assert(__traits(isStronglyPure, foo));
>>>>
>>>> -Steve
>>>
>>> This would work, but it wouldn't be self-documenting, etc.
>>
>> Hm... OK, well I disagree, it looks like it's documented to me.  I don't see a difference between tagging something as strongly pure and putting in the static assert (except verbosity of course).  I will note that I think the above would be a rare situation.
>
> To clarify, self-documenting => be able to automatically shows up in ddoc, etc.

OK, that's a fair point, I hadn't thought of that aspect.  The only counter I have for that is, does it matter in the docs whether the compiler will optimize via parallelizing or not?  Or is it more important just to have the compiler refuse to compile if it can't parallelize?

-Steve
September 24, 2010
retard wrote:
> Thu, 23 Sep 2010 22:35:23 +0200, Tomek Sowiński wrote:
> 
>> dsimcha napisał:
>>
>>> 1.  The documentation that says that the parameters need to be
>>> convertible to immutable is outdated.  This was changed a while ago to
>>> only requiring const.
>> Good to know. Yet, I wonder why such changes are not discussed on this
>> NG and at the very least announced in the change log...
> 
> Just download the documentation of two subsequent versions and run gnu diff. It's that simple.

It's not in the docs. I don't remember ever hearing about this, and I can't find this documented anywhere. And I made the patches for all of the improvements to the compiler's support for pure which have happened in the last year.

There have always been bugs where the compiler accepts 'const' instead of immutable. These date back to 2.022, when pure was first implemented.

In fact, my motivation in bringing up this topic was after I observed these bugs, and realized that most existing 'pure' code will break when they are fixed. Also 'pure' will become even more useless than it is now.
September 24, 2010
On Fri, 24 Sep 2010 09:32:40 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> On Thu, 23 Sep 2010 18:26:28 -0400, Robert Jacques <sandford@jhu.edu> wrote:
>
>> On Thu, 23 Sep 2010 10:05:45 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>>
>>> On Wed, 22 Sep 2010 21:48:19 -0400, Robert Jacques <sandford@jhu.edu> wrote:
>>>
>>>> On Wed, 22 Sep 2010 13:10:36 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>>>>
>>>>> On Wed, 22 Sep 2010 12:00:16 -0400, Robert Jacques <sandford@jhu.edu> wrote:
>>>>>> What about value types?
>>>>>
>>>>> Value types are implicitly convertable to immutable, so they can be strongly-pure.
>>>>
>>>> No their not. Remember, arrays and other structs are value types in the type system. Logically, they may be reference types, but as far as their type signature goes, they are value types.
>>>
>>> Arrays are not value types.  A value type is one that contains no references, no matter how deep.  It is irrelevant if you have to spell out the references or not.
>>
>> Arrays are implemented as a struct. And as per the language spec: (http://www.digitalmars.com/d/2.0/struct.html) all structs are value types *to the compiler*. This doesn't mean that logically, from the programmer's point of view, they aren't providing reference semantics.
>
> structs can have value copy semantics.  But for a struct that contains a reference, the references have reference semantics, which makes the struct a reference type.

A struct is never a reference type. It may have reference semantics, but this is a high-order feature that is uncheckable by the compiler. At best the compiler can detect that a struct contains references, not how those references are exposed/managed by the API.

> Look, terms can be debated, but here is the bottom line: A struct with a reference type inside it cannot be implicitly converted to immutable, whereas a struct with only non-reference types in it can.  The compiler knows this, and makes its decision on what must be immutable or not based on that knowledge.  Call it whatever you want, but that's how it works internally, and it's not hidden from the compiler.

Right. Immutable transitivity for the win.

> When you say "what about value types" what do you mean?  I thought you meant types which have value copy semantics, which can only have non-references in them.

Given that I explicitly referred to the spec and compiler and contrasted that to logical/semantic value types, I thought I was pretty clear about what I mean.
September 24, 2010
On Fri, 24 Sep 2010 10:33:10 -0400, Robert Jacques <sandford@jhu.edu> wrote:

> On Fri, 24 Sep 2010 09:32:40 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>> structs can have value copy semantics.  But for a struct that contains a reference, the references have reference semantics, which makes the struct a reference type.
>
> A struct is never a reference type. It may have reference semantics, but this is a high-order feature that is uncheckable by the compiler. At best the compiler can detect that a struct contains references, not how those references are exposed/managed by the API.

Containing references means it cannot be cast to immutable, the only important thing when determining the strength of purity here.

This whole discussion is going nowhere, you haven't made any real points.  Can you think of a case where the compiler would be wrong in determining purity strength for "value types" as you define them?  An example would be most helpful.

-Steve
September 24, 2010
On Fri, 24 Sep 2010 10:47:16 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> On Fri, 24 Sep 2010 10:33:10 -0400, Robert Jacques <sandford@jhu.edu> wrote:
>
>> On Fri, 24 Sep 2010 09:32:40 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>>> structs can have value copy semantics.  But for a struct that contains a reference, the references have reference semantics, which makes the struct a reference type.
>>
>> A struct is never a reference type. It may have reference semantics, but this is a high-order feature that is uncheckable by the compiler. At best the compiler can detect that a struct contains references, not how those references are exposed/managed by the API.
>
> Containing references means it cannot be cast to immutable, the only important thing when determining the strength of purity here.
>
> This whole discussion is going nowhere, you haven't made any real points.  Can you think of a case where the compiler would be wrong in determining purity strength for "value types" as you define them?  An example would be most helpful.
>
> -Steve

I feel like I've upset you and would like to make amends. First, this discussion was never about the compiler being able to determine purity. That's easy. The point raised was about whether the programmer could enforce strong-purity for any strongly-pure fucntion. The answer is that you can by making all arguments immutable, which is a fairly minor restriction on the callee. Second, this thread (fiber?), has veered a little off-topic due to a misunderstanding/debate about value-types vs value-semantics and reference-types vs reference-semantics. Perhaps it's because I work with large, 'hybrid' structs a lot, but the difference between value-type and value-semantics is very large in my mind. Third, this fiber started, in part, due to a question by regarding value-types being answered with value-semantics. Forth, I raised the question regarding value-types in part due to half-remembered old posts in which value-semantics were discussed but under the label of value-types, thus causing confusion in my brain. And because it was late at night, I decided to ask a simple question instead of testing DMD's current behavior myself. I did end up testing DMD the next day (and then banging my head on a wall), but by then all this had started.
September 24, 2010
On Fri, 24 Sep 2010 12:16:23 -0400, Robert Jacques <sandford@jhu.edu> wrote:

> On Fri, 24 Sep 2010 10:47:16 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>
>> On Fri, 24 Sep 2010 10:33:10 -0400, Robert Jacques <sandford@jhu.edu> wrote:
>>
>>> On Fri, 24 Sep 2010 09:32:40 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>>>> structs can have value copy semantics.  But for a struct that contains a reference, the references have reference semantics, which makes the struct a reference type.
>>>
>>> A struct is never a reference type. It may have reference semantics, but this is a high-order feature that is uncheckable by the compiler. At best the compiler can detect that a struct contains references, not how those references are exposed/managed by the API.
>>
>> Containing references means it cannot be cast to immutable, the only important thing when determining the strength of purity here.
>>
>> This whole discussion is going nowhere, you haven't made any real points.  Can you think of a case where the compiler would be wrong in determining purity strength for "value types" as you define them?  An example would be most helpful.
>>
>> -Steve
>
> I feel like I've upset you and would like to make amends. First, this discussion was never about the compiler being able to determine purity. That's easy. The point raised was about whether the programmer could enforce strong-purity for any strongly-pure fucntion. The answer is that you can by making all arguments immutable, which is a fairly minor restriction on the callee. Second, this thread (fiber?), has veered a little off-topic due to a misunderstanding/debate about value-types vs value-semantics and reference-types vs reference-semantics. Perhaps it's because I work with large, 'hybrid' structs a lot, but the difference between value-type and value-semantics is very large in my mind. Third, this fiber started, in part, due to a question by regarding value-types being answered with value-semantics. Forth, I raised the question regarding value-types in part due to half-remembered old posts in which value-semantics were discussed but under the label of value-types, thus causing confusion in my brain. And because it was late at night, I decided to ask a simple question instead of testing DMD's current behavior myself. I did end up testing DMD the next day (and then banging my head on a wall), but by then all this had started.

You haven't upset me, I just couldn't follow what you were saying :)

When you said "what about value types," I thought it was a suggestion that value types would make it hard to determine whether a function was strongly pure or weakly pure, and my interpretation of what "value type" means sent us off on this tangent.

I think we both agree that the proposed changes by Don will work with the compiler, and I understand your desire to ensure a function is strongly-pure, and why the proposal does not give an easy solution to that.

So no hard feelings, we can move on and forget this whole thread ever happened :)

-Steve
September 24, 2010
On Fri, 24 Sep 2010 13:09:05 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> On Fri, 24 Sep 2010 12:16:23 -0400, Robert Jacques <sandford@jhu.edu> wrote:
>
>> On Fri, 24 Sep 2010 10:47:16 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>>
>>> On Fri, 24 Sep 2010 10:33:10 -0400, Robert Jacques <sandford@jhu.edu> wrote:
>>>
>>>> On Fri, 24 Sep 2010 09:32:40 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>>>>> structs can have value copy semantics.  But for a struct that contains a reference, the references have reference semantics, which makes the struct a reference type.
>>>>
>>>> A struct is never a reference type. It may have reference semantics, but this is a high-order feature that is uncheckable by the compiler. At best the compiler can detect that a struct contains references, not how those references are exposed/managed by the API.
>>>
>>> Containing references means it cannot be cast to immutable, the only important thing when determining the strength of purity here.
>>>
>>> This whole discussion is going nowhere, you haven't made any real points.  Can you think of a case where the compiler would be wrong in determining purity strength for "value types" as you define them?  An example would be most helpful.
>>>
>>> -Steve
>>
>> I feel like I've upset you and would like to make amends. First, this discussion was never about the compiler being able to determine purity. That's easy. The point raised was about whether the programmer could enforce strong-purity for any strongly-pure fucntion. The answer is that you can by making all arguments immutable, which is a fairly minor restriction on the callee. Second, this thread (fiber?), has veered a little off-topic due to a misunderstanding/debate about value-types vs value-semantics and reference-types vs reference-semantics. Perhaps it's because I work with large, 'hybrid' structs a lot, but the difference between value-type and value-semantics is very large in my mind. Third, this fiber started, in part, due to a question by regarding value-types being answered with value-semantics. Forth, I raised the question regarding value-types in part due to half-remembered old posts in which value-semantics were discussed but under the label of value-types, thus causing confusion in my brain. And because it was late at night, I decided to ask a simple question instead of testing DMD's current behavior myself. I did end up testing DMD the next day (and then banging my head on a wall), but by then all this had started.
>
> You haven't upset me, I just couldn't follow what you were saying :)
>
> When you said "what about value types," I thought it was a suggestion that value types would make it hard to determine whether a function was strongly pure or weakly pure, and my interpretation of what "value type" means sent us off on this tangent.
>
> I think we both agree that the proposed changes by Don will work with the compiler, and I understand your desire to ensure a function is strongly-pure, and why the proposal does not give an easy solution to that.
>
> So no hard feelings, we can move on and forget this whole thread ever happened :)
>
> -Steve

Agreed :)
October 25, 2010
On 22/09/2010 09:13, 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.

I'm confused: Isn't this essentially the same as the "partially pure" functions idea that was discussed as far back as 2008? And wasn't it agreed already that this would be the way things would work?


-- 
Bruno Medeiros - Software Engineer
October 25, 2010
On 23/09/2010 23:39, Robert Jacques wrote:
> On Thu, 23 Sep 2010 16:35:23 -0400, Tomek Sowiński <just@ask.me> wrote:
>>
>> On topic: this means a pure function can take a reference to data that
>> can be mutated by
>> someone else. So we're giving up on the "can parallelize with no
>> dataraces" guarantee on
>> pure functions?
>>
>
> In short, No. In long; the proposal is for pure functions become broken
> up into two groups (weak and strong) based on their function signatures.
> This division is internal to the compiler, and isn't expressed in the
> language in any way. Strongly-pure functions provide all the guarantees
> that pure does today and can be automatically parallelized or cached
> without consequence. Weakly-pure functions, don't provide either of
> these guarantees, but allow a much larger number of functions to be
> strongly-pure. In order to guarantee a function is strongly pure, one
> would have to declare all its inputs immutable or use an appropriate
> template constraint.

I think we need to be more realistic with what kinds of optimizations
we could expect from a D compiler and pure functions.
Caching might be done, but only a temporary sense (caching under a limited execution scope). I doubt we would ever have something like memoization, which would incur memory costs (potentially quite big ones), and so the compiler almost certainly would not be able to know (without additional metadata/anotations or compile options) if that trade-off is acceptable.

Similarly for parallelism, how would the compiler know that it's ok to spawn 10 or 100 new threads to parallelize the execution of some loop?
The consequences for program and whole-machine scheduling would not be trivial and easy to understand. For this to happen, amongst other things the compiler and OS would need to ensure that the spawned threads would not starve the rest of the threads of that program.
I suspect all these considerations might be very difficult to guarantee on a non-VM environment.

-- 
Bruno Medeiros - Software Engineer