Koroskin Denis Wrote:

> It works, you are very glad that your program is parallelized and uses
> full power of your multi-processor CPU.
> But now you want to make some optimizations to speed it up a little. You
> add some SSE instruction in assembly (it's ok in pure methods, I hope?).
> And then you take a step further and it looks like you calculate
> determinant for your Matrix every time, and it consumes quite some time.
> You move you determinant calculations to class' ctor and just store the
> value. But now it turns out that performance degraded dramatically because
> now you are forced to calculate determinant for every Matrix, even
> temporary ones, during addition, subtruction etc.
> 
> A C++ programmer would add mutable member here:
> 
> This is *transparent* optimization, and it's a programmer now who makes guaranties, that his code makes no side effect. Yes, binary represination of the class is changed, but its logical invariance is preserved. If programmers fails to do it correctly, then it's his fault. By signing his code as pure he claims that the method is thread-safe, doesn't rely on other threads' execution order, calls to it can be rearranged and given the same input it yields the same result.
> 
> You might say that this code smells, but it's correct. And it could look slightly better if mutable was not a user-defined template hack, but a language-level feature. You just should expose some restrictions on its usage (like, only private members can be mutable, access to it can be achieved via read-write lock only http://en.wikipedia.org/wiki/Readers-writers_problem).
> 
> IMO, mutable is a powerful optimization mechanish, that should be used with *great* care.

I think the future of D will no require the mutable keyword as you describe.

class matrix{
  pure int determinant(){ ... }
  ...
}

By simply making the determinant function pure, the compiler is free to do optimization/caching of the result.  I haven't been in the habit of giving compilers that much trust...

On Thu, 03 Apr 2008 15:33:20 +0200, Bill Baxter <dnewsgroup@billbaxter.com> wrote:

> Simen Kjaeraas wrote:
>> On Thu, 03 Apr 2008 03:55:47 +0200, Bill Baxter <dnewsgroup@billbaxter.com> wrote:
>>
>>> They can be run in parallel, as long as you don't stick non-pure mutating operations in between them.
>>>
>>> That's quite useful for automatically parallelizing tight loops like this:
>>>
>>> nosfx int foo(const C c) { return c.p[0]; }
>>> ...
>>>
>>> C[] array;
>>> ...// put bunch of C's in array
>>> int sum = 0;
>>> foreach(c; array) {
>>>     sum += foo(c);
>>> }
>>>
>>> Those foreach bodies could be run in parallel (with appropriate reduce logic added to handling of 'sum' by compiler) since we know each call to foo() in that loop has no external side effects.
>>>
>>> This is the kind of thing OpenMP lets you do with directives like "#pragma pfor reduce".  Except I don't believe OpenMP has any way to verify that foo() is really side-effect free.
>>>
>>> --bb
>>   And could this not be done with real pure functions?
>>  pure int foo(invariant C c) { return c.p[0];}
>>  C[] array;
>> ...// put bunch of C's in array
>> int sum = 0;
>> foreach(c; array) {
>>     sum += foo(cast(invariant)c);
>> }
>>  We know that c will not change, so we can cast it to invariant.
>>  --Simen
>
> That complicates things if you want to modify the C's in the array after the foreach.
>
> --bb

I can't quite see why, as long as we know the foreach has completed running.
foo does not care whether the array changes after it's exited, and the
array does not consist of invariant Cs, they're only cast to invariant when
fed to foo.

-- Simen

"Janice Caron" wrote
> On 02/04/2008, Steven Schveighoffer wrote:
>> Absolutely, but I'd at least like Walter to stop saying that transitive
>>  const (read, transitive *keyword* const) is neccessary for pure
>> functions :)
>>  If he says "Oh yeah, I guess transitive const isn't necessary, but it's
>> not
>>  a priority to fix it right now", then I'd be happy.
>
> But hang on. It's all very well saying "pure functions can access the non-mutable bits only", but in every case I can think of where I might use the mutable keyword in C++, the non-mutable subset of the class is completely useless without the mutable subset.
>
> Can you give me a counterexample of a logically const (muty) class in which the non-mutable subset is actually useful?

Certainly:

class SuperIntensiveCalculator
{
    private mutable int[int] cache;

    int f(int x) const
    {
         int *result = x in cache;
         if(result !is null)
             return result;
         /* do really intense calculation, cache the value */
    }

    pure int puref(int x) invariant
    {
        /* do really intense calculation, do not use cache */
    }
}

If your instance is invariant, you can call puref, which doesn't use the cache, but allows the compiler to do it's own optimizations (and possibly memoization).

Yes, I could make cache just a normal member, and remove the const on f(x), but then I couldn't call f on const instances, which gives me less functionality.  I could also implement this in globby form, but then the lookup for the cache is going through 2 AA's, and I have to manually initialize and destroy the cache for each instance.

-Steve

"Simen Kjaeraas" wrote
> On Wed, 02 Apr 2008 16:50:12 +0200, Steven Schveighoffer  wrote:
>
>> "Simen Kjaeraas" wrote
>>> On Wed, 02 Apr 2008 16:41:33 +0200, Steven Schveighoffer  wrote:
>>>
>>>> "Simen Kjaeraas" wrote
>>>>> On Wed, 02 Apr 2008 16:04:36 +0200, Steven Schveighoffer  wrote:
>>>>>
>>>>>> - a pure method cannot access the mutable portion of a logically invariant data value.
>>>>>
>>>>> Wouldn't this basically make it transitive invariant?
>>>>
>>>> Yes, which makes my point :)  pure must be transitive, but const /
>>>> invariant
>>>> by itself does not need to be.
>>>>
>>>> -Steve
>>>
>>> So yes, you can do without transitive const, as long as you define
>>> logical
>>> const as transitive. I can't quite see what point you're trying to make.
>>
>> No, I'm not defining logical const as transitive.  I'm defining that
>> pure is
>> transitive.  pure functions have nothing to do with requiring const to be
>> transitive, which is my point.
>>
>> Did you look at my example in the original post?  What we have now is semantically equivalent to logical const.
>>
>> -Steve
>
> Yes, there are ways to bypass the const system. We know that, and we accept it. Why not just do:
>
> class foo
> {
>   int bar;
>   const void baz()
>   {
>     (cast(foo)this).bar++;
>   }
> }
>
> That also works.

There is a huge difference between my code and your code.  My code is well-defined by the language spec, yours is not.  I hope to never write undefined code, as I'm not sure it will always work.

-Steve

Janice Caron, el  2 de abril a las 08:00 me escribiste:
> On 02/04/2008, Jason House <jason.james.house@gmail.com> wrote:
> > And how do global variables fit into that?  Technically, they're always
> >  reachable and never inherit const.
> 
> Global variables will /not/ be reachable from a pure function. Example:

And how is that related to transitive const? pure functions could be implemented in D1.0 without const at all...

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------
You can try the best you can
If you try the best you can
The best you can is good enough

"Walter Bright" wrote
> If you do away with transitive const, you cannot have invariant either. Const allows you to reuse code that works on invariants to work with mutables, too.

I'm not "doing away with" transitive const.  I'm saying allow the exception that already exists as global variables to be easier to implement.  I still believe that the default meaning of const is transitive.  This is unlike C++'s const.  The exception is when you declare a piece of a class to be mutable, it is now declared to be not part of the state of the class, but a piece of data associated with the class, just like a global AA would associate a class (the key) with some data (the value).

> Logical const just utterly breaks the whole system. Every scheme we've looked at for logical const winds up in some way breaking invariants. If invariants are broken, the advantages of them all just go away. I suspect that logical const is like perpetual motion - if you think you've solved it, you've just made a mistake somewhere <g>. I also suspect that the failure of logical const validates the D scheme of invariants as being correct - there shouldn't be any holes in it.

Think of the mutable portion of logically invariant classes as global variables, but with better protection capabilities.  And saying "logical const winds up in some way breaking invariants" doesn't make it true :)  In fact, it is false.  I have proven that logical const is already possible. You have not pointed out any mistakes I have made.  History is full of examples where people were absolutely sure that something was true, but they turned out to be wrong.  I have offered proof for my views.  You have offered anecdotes and analogies.  Please try harder :)

> You're right that invariant by itself is not enough to specify a pure function, a pure function also cannot read or write global state. But invariant is still a necessary condition, it's just not sufficient.

Exactly, since the mutable portion is not part of the object state, it should be inaccessible to pure functions.

>
> Peoples' troubles with const seem to stem from attempting to defeat it in one way or another. While defeating const is legal and trivial in C++, D tries to close those doors.

I'm not trying to defeat the const system.  I'm showing you that the const system already supports "operationally equivalent" logical const.  Since it already supports an equivalent version of logical const, why not support it directly, and make coders lives easier who want to use it.

I can come up with a set of rules for logical const that allow pure functions which the compiler can statically verify that the function has no side effects and is not affected by any other function's side effects.  I think this is the goal, is it not?

-Steve

On 03/04/2008, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
>  > Can you give me a counterexample of a logically const (muty) class in
>  > which the non-mutable subset is actually useful?
>
> Certainly:
> <snip>

In the example you just gave me, the non-mutable subset consisted of the empty set - i.e. no members whatsoever. I don't call that useful.

Given that, the function pure f could just have easily have been taken outside the class altogether and been a standalone function.

Do you want to try again?

Walter Bright, el  2 de abril a las 15:22 me escribiste:
> Janice Caron wrote:
> >However, I suspect that the following will be OK.
> >    enum g = 42;
> >    pure int f()
> >    {
> >        return g;
> >    }
> 
> Yes, because the value of g can never change.
> 
> The way to think about pure functions is that if the arguments are the same, the result will be the same. This precludes reading any global state that could change, and precludes writing to any global state.

And using most of the IO functions, like read/write.

pure byte f()
{
	byte b;
	read(0, &b, 1);
	return b;
}

Can't be a pure function.

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------
Dentro de 30 años Argentina va a ser un gran supermercado con 15
changuitos, porque esa va a ser la cantidad de gente que va a poder
comprar algo.
	-- Sidharta Wiki

On 03/04/2008, Leandro Lucarella <llucax@gmail.com> wrote:
>  > Global variables will /not/ be reachable from a pure function.
>
>  And how is that related to transitive const?

It isn't.


> pure functions could be
> implemented in D1.0 without const at all...

Stating the obvious isn't very interesting.

"Janice Caron" wrote
> On 03/04/2008, Steven Schveighoffer wrote:
>>  > Can you give me a counterexample of a logically const (muty) class in
>>  > which the non-mutable subset is actually useful?
>>
>> Certainly:
>> <snip>
>
> In the example you just gave me, the non-mutable subset consisted of the empty set - i.e. no members whatsoever. I don't call that useful.
>
> Given that, the function pure f could just have easily have been taken outside the class altogether and been a standalone function.
>
> Do you want to try again?

Have you no imagination? :)

class SuperIntensiveCalculator
{
    private mutable int[int] cache;

    private int configParameterThatIsNecessaryForIntenseCalculation;

    int f(int x) const
    {
         int *result = x in cache;
         if(result !is null)
             return result;
         /* do really intense calculation, cache the value */
    }

    pure int puref(int x) invariant
    {
        /* do really intense calculation, do not use cache */
    }
}