Georg Wrede wrote:
> Walter Bright wrote:
>> Don Clugston wrote:
>>> Walter Bright wrote:
>>>
>>>> A function is pure or it isn't, there really isn't any room for "unstable" purity, or the point of purity is lost.
>>>
>>> I think there is. A function which accesses a global is inherently impure. But, a function which takes a non-invariant argument, can in theory safely be called from inside a pure function, provided any non-invariant arguments are local variables, or invariant.
>>>
>>> eg.
>>>
>>> class C
>>> {
>>>   int numcalls;
>>>   this() { numcalls=0; }
>>>   void foo() { ++numcalls; } // Not pure - but no global side effects.
>>> }
>>>
>>> pure int bar(int x)
>>> {
>>>     C c = new C;
>>>     for (int i=0; i<x; ++i) c.foo();
>>>     return c.numcalls;
>>> }
>>>
>>> Is bar() pure or not?
>>
>> I think it is pure, although it might be difficult for the compiler to detect it. Like for CTFE, I think the compiler should start out rather restrictive about what it regards as pure, and over time expand it as it gets more capable.
> 
> No.
> 
> The result of having run the function changes something outside the function, and that makes it impure.

foo() is definitely not pure. But bar() doesn't change anything outside bar().

* foo() doesn't read or write anything other than its parameters.
* The only parameters bar() provides to foo() are local.

> It does not matter that what's being changed is hidde behind the bushes in a small tin box.

I don't think that's what happening here. A 'partially pure' function like foo() can be wrapped in a pure function.
The question is whether the compiler can allow this, without foo() being marked in some way.
It works for CTFE, because in CTFE, the compiler has access to the source code; but that's not necessarily true for run time functions.

This partial impurity is not transitive! (whereas accessing a global is transitive).

Janice Caron wrote:
> What about this one. Is f pure?
> 
>     import std.date;
> 
>     void main()
>     {
>         invariant s = toString(getUTCtime());
> 
>         pure string f()
>         {
>             return s;
>         }
> 
>         writefln(s);
>     }
> 
> The function f relies only on the string s. which is fully invariant
> and in scope. Yet f will give a different return value for the same
> input (void), each time the program is run.
> 
> I assume the answer is no, but this one seems a bit grey to me. Is it
> impure because s is not global?

f() is pure because it relies on invariant data. Invariant data can be initialized at runtime, as long as it is before any pure functions attempt to read it.

On 2008-04-04 01:36:42 -0400, Walter Bright <newshound1@digitalmars.com> said:

> Don Clugston wrote:
> 
>> class C
>> {
>>   int numcalls;
>>   this() { numcalls=0; }
>>   void foo() { ++numcalls; } // Not pure - but no global side effects.
>> }
>> 
>> pure int bar(int x)
>> {
>>     C c = new C;
>>     for (int i=0; i<x; ++i) c.foo();
>>     return c.numcalls;
>> }
>> 
>> Is bar() pure or not?
> 
> I think it is pure, although it might be difficult for the compiler to detect it. Like for CTFE, I think the compiler should start out rather restrictive about what it regards as pure, and over time expand it as it gets more capable.

Personally, I'd rather say foo is pure. I'd define pure as "always giving the same outputs given the same inputs and having no external effect". That would make foo pure, because given any object C, it'll always change C in the same, predictable way.

This definition allows parallelizing loops that wouldn't be parallelizable if foo wasn't pure (assuming you label foo as pure), such as this one:

	foreach (C c; arrayOfUniqueC)
		c.foo();

It also mean that purity doesn't prevent you from altering an out parameter and that you don't have to make all your parameters invariant. As long as you only alter what was given to you in the parameters, since the compiler knows about these parameters from the call site it can take the decision to parallelize or not, at the call site. In the example above, if you did this:

	C c;
	for (int i = 0; i < 10; ++i)
		c.foo();

it wouldn't be parallelizable because calling foo alters the state for the next call. But it's okay, because the compiler can figure that out from the call site and it won't do the parallelization. In other words, if the result depends on the previous result, you can't parallelize. That same situation can happen with a pure function returning a value:

	C c;
	for (int i = 0; i < 10; ++i)
		c = pureFunction(c);

So in other words, altering a non-const parameter isn't a side effect, it's a predictable effect you can deduce from the function signature, and I think it should be allowed in a pure function.

P.S.: I'm not sure what would happen if arrayOfUniqueC in the example above was to contain two or more pointers to the same object. That would be a problem, and that's why I put the word "unique" in the name to mean there are no duplicate. I'm not sure how the compiler could find about that though. Anyway, the worse that can happen is that the compiler cannot parallelize this particular case without an additional clue; allowing foo to be pure would still permit the optimization in the case of the bar function in Don's example, and in any case the compiler knows there are no duplicate pointers.

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

"Georg Wrede" wrote
> Walter Bright wrote:
>> Bill Baxter wrote:
>>
>>> So does that mean
>>>
>>>   pure int f(const Class c)
>>>   { ...
>>>   }
>>>
>>> will *not* be allowed?  Because some part of c *could* change, even if it's not f() doing the changing.  I.e. another thread could be changing c concurrently.
>>
>> Right. That declaration of f is erroneous.
>
> I'd disagree.
>
> Whether a function is pure or not, has nothing to do with whether c could change or not.

The question is, should pure functions be protected from other threads changing c?   I think Walter wants this to be true, and for that, c must be invariant.  I think Walter is trying to promote a different definition for pure than what you are thinking of.

>
> Take, for example sin(x). We all know that it's pure, period. Now, whether x changes between two consecutive invocations or not, is irrelevant. Of course you get a different result. And you should.

sin(x) is a completely different animal, because x is not a reference type, it is pushed on the stack, and the pure function has the only reference to it.  Nothing can change x while sin is running.

>
> But pure, IMHO, means (1) the function is guaranteed to give the same result every time /if/ the input is the same (like sin(x) does), (2) it does not change anything at all anywhere, it's only way of affecting life is by its return value, (3) it doesn't access info from non-constants anywhere.
>
> Now, to the issue between
>
>     (1)pure int f(const Class c)
>     (2)pure int f(Class c)
>
> I'd say that, since a Pure function promises not to change /anything/ (other than its return value, of course) anywhere, this means a pure function /simply has to implicitly treat its arguments as unchangeable/!
>
> Therefore, depending on what A/W want, either:
>
>  - a pure function has to have const decorated parameters only (1)
>  - and (2) would be a syntax error
>
> or
>
>  - a pure function's parameters are implicitly const, and (1) is then a
> syntax error

If the arguments must be invariant, then they cannot be implicitly cast.  I understand what you are saying, but I think A/W want something different.

>
> (Not making the latter a syntax error isn't technically impossible, but for those learning the language and the casual readers of ex. magazine articles, this would wreak havoc with their understanding D.)
>
>
> *Back to concurrency*, if someone changes c in mid-run, then it's the programmer's fault. It's his headache. The function f only guarantees not to change c /by itself/.

I think this is what A/W want to prevent.  Otherwise, all this touting about pure functions being the way to multiprogram in D is not completely true, you still have to deal with multithreadded issues.  Walter has said before he wants multithreaded programming to "just work" without having to do any locking, just like FP languages have.

-Steve

"Sean Reque" wrote
> Steven Schveighoffer Wrote:
>
>> "Sean Kelly" wrote
>> > == Quote from Janice Caron article
>> >> ...which raises an interesting point. Can "synchronized" be used on a const object? What about an invariant object?
>> >
>> > They'll work just fine with const objects in D.  Object monitors in D
>> > currently
>> > live outside the const checking scheme.
>>
>> Oh so you mean Walter couldn't implement mutexes without logical const
>> huh?
>> I think this part of the system should be ripped out and you should have
>> to
>> pass mutexes along with objects everywhere you want to ensure thread
>> safety
>> and const is transitive.  That's easier and less obfuscated, right?
>>
>> -Steve
>>
>>
>
> The whole point of invariant objects and pure functions in terms of thread safety is that you don't need any form of synchronized data access. If, for instance a piece of data is guaranteed not to change, then two cores can hold two separate copies of the same data in each of their local caches instead of having to fetch the same data from an external source. Requiring synchronization on all const objects would entirely defeat optimizations like these.

Correct, for pure functions.  But for non-pure functions, which is 100% of D2 code right now, you do need synchronization.  When pure is introduced, then I believe at least 75% of D will not use it (just a guess, but I believe more D code will be non-pure than will be pure), and you STILL will need synchronization for those functions.  In that case, you still need to synchronize at least const objects, and where do we store the mutex?  WITH THE OBJECT!   Which means, it is not part of the object state, because otherwise you couldn't lock it while the object was const!

I'm not arguing about how mutexes are implemented.  I'm pointing out the hipocrasy of how logical const is not allowed for developers, yet Walter uses it in the standard library to implement mutexes.

>
> The end result is, don't use const, invariant, or pure if you plan on modifying internal data on an object. A caching calculator, for instance, is inherently not thread safe, because one thread might cause the calculator to write to the cache at the same time another thread reads from it, so the calculator should never be allowed to be const or invariant. If I understand correctly, Walter wants the compiler to be able to make assumptions on an invariant object that would not be possible if it had mutable members.

I'd like to do that, but the way D const works, it's very difficult.  For example, what if a calculator is expected to be const? (see the other branch of this thread with the arguments between myself and Janice)  Now, I cannot pass my caching calculator unless I make the cache a global, which is totally unnecessary, it should be piggy-backed around with the calculator object, but not part of the object state, just like mutexes are...

>
> I think that the ideas of pure and invariant will be very valuable in the end and one of D's strong selling points. It will require more careful library design though, and some designs and features, such as caching calculations or synchronizing memory access, will simply not be usable with it.

I do not have an opinion on whether pure and invariant will be huge for D, as I am not experienced enough with FP, but I know for a fact that having logical const will not inhibit this, just as logical const mutexes will not.

-Steve

"Walter Bright" wrote
> Steven Schveighoffer wrote:
>> "Walter Bright" wrote
>>> Sure, but static class members are *not* part of the transitive closure state of the object. They're just global variables.
>>
>> Neither are mutable member variables.
>
> How can a member not be a member of the state of an object?

The very act of declaring it mutable tells the compiler "this is not object state."  I don't like the keyword mutable, what about 'nonstate' or something like that.  It's not really saying "this will always be mutable", it's just saying "this is not part of the object state, so don't apply const casts to it," which happens to mean it's mutable when the rest of the object is const or invariant.

Declaring a nonstate member is basically a way to associate data with an object that is not owned by the object.  For example, a cache in a calculator object may be used by the methods of the object, but it's not 'owned' by anything, just like the methods of the object can use global data, or data from the arguments passed to the function.  I like to think of nonstate data as extra arguments passed to every method call, in addition to the 'this' pointer.  In fact, this could be how it was implemented in the compiler (but I think implementing it inline with the class would have better performance):

class C
{
   // this is like a struct passed as an argument to all methods, and is
always mutable
   nonstate
   {
       int c;
   }

   // is passed an implicit nonstate pointer to the nonstate values
   int f(int x) const
   {
       return nonstate.c++;
   }
}

This way, the nonstate part could be laid out in the same memory chunk as the class, and is passed around with the class, but is not technically part of the class.  This is similar to how a mutex is associated with a class, lives in the same memory space as the class, but is not considered part of the transitive const closure of the object.  There could be a vtable entry that points to the nonstate data, so the layout would move with derived classes.

-Steve

Don Clugston, el  4 de abril a las 09:52 me escribiste:
> >The result of having run the function changes something outside the function, and that makes it impure.
> 
> foo() is definitely not pure. But bar() doesn't change anything outside bar().

Maybe foo should be marked as ... "local"? I.e. make some distinction between methods that afect globals and methods that only modify locals.

> * foo() doesn't read or write anything other than its parameters.
> * The only parameters bar() provides to foo() are local.
> 
> >It does not matter that what's being changed is hidde behind the bushes in a small tin box.
> 
> I don't think that's what happening here. A 'partially pure' function like foo() can be
> wrapped in a pure function.
> The question is whether the compiler can allow this, without foo() being marked in some
> way.
> It works for CTFE, because in CTFE, the compiler has access to the source code; but that's
> not necessarily true for run time functions.
> 
> This partial impurity is not transitive! (whereas accessing a global is transitive).

Well, this apply to functions too, what about:

class Foo { int i; }

void foo(Foo f)
{
	f.i = 5;
}

pure void bar()
{
	Foo f;
	foo(f);
}

bar() has no side effects either. Maybe foo should be marked... like "local". But I think it should be much nicer if can be infered by the compiler, but as you say it could be a problema if the source code is not available.

Maybe this kind of "annotations" can be automatically generated by the compiler and put in the .di "headers"?

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------
Wake from your sleep,
the drying of your tears,
Today we escape, we escape.

Steven Schveighoffer, el  4 de abril a las 09:24 me escribiste:
> class C
> {
>    // this is like a struct passed as an argument to all methods, and is
> always mutable
>    nonstate
>    {
>        int c;
>    }
> 
>    // is passed an implicit nonstate pointer to the nonstate values
>    int f(int x) const
>    {
>        return nonstate.c++;
>    }
> }

Why don't you just do something like this:

static int[C] nonstate;
class C
{
   // is passed an implicit nonstate pointer to the nonstate values
   int f(int x) const
   {
       return nonstate[this] += 1;
   }
}

If nonstate is not part of the object, why to put it in it? I this the cache-problem is a very specific problem, which is OK to have a specific solution. Even more, I find a lot more clear if the cache it's outside the class, because is not part of it (if it's not part of the state of the object, it's not part of the object at all!).

So C.f() is clearly not pure, but it's const, it doesn't change the state
of the object.

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------
Pack and get dressed
before your father hears us,
before all hell breaks loose.

On 04/04/2008, Leandro Lucarella <llucax@gmail.com> wrote:
> Why don't you just do something like this:
> <snip>
>  If nonstate is not part of the object, why to put it in it?

You're having the same problem with Steven's jargon as I had. I found that terminology confusing. Rest assured, we /are/ talking about part of the object. If we come up with a better way of describing it, we'll tell the world.

What we're talking about here is a member whose constancy cannot be changed (but whose value maybe can).

On 04/04/2008, Janice Caron <caron800@googlemail.com> wrote:
> On 04/04/2008, Leandro Lucarella <llucax@gmail.com> wrote:
>  > Why don't you just do something like this:
>
> > <snip>
>
> >  If nonstate is not part of the object, why to put it in it?
>
>
> You're having the same problem with Steven's jargon as I had. I found
>  that terminology confusing. Rest assured, we /are/ talking about part
>  of the object. If we come up with a better way of describing it, we'll
>  tell the world.
>
>  What we're talking about here is a member whose constancy cannot be
>  changed (but whose value maybe can).

See the thread "unpaintable..." for an alternative description of the solution.