On 2008-05-31 18:41:24 +0200, "Janice Caron" <caron800@googlemail.com> said:

> On 31/05/2008, Fawzi Mohamed <fmohamed@mac.com> wrote:
>> It seems that with a safe no_state and a cast this is possible, so yes I
>> very much want no_state.
> 
> But it's likely also to be possible /without/ nostate.
> 
> As I noted in my first post on this thread, only a small handful of
> use-cases for nostate (aka mutable, aka unpaintable, etc) have been
> identified. One of these uses is caching (aka memoization). The
> current plan is to make caching available as a library solution, and
> so *therefore*, you will not need "nostate" in order to do this.
> 
> I have no idea whether or not the library solution will be considered
> pure. I imagine that if it can be proven safe, then it will count as
> pure. If not, well, there's always explicit casting.
> 
> So, given that, do you /still/ want nostate? Remember that (like
> explicit casts and unions) it opens the door to /serious/ abuse of the
> const system, just like in C++. Inexperienced programmers may well
> think to themselves: "I can't get this program to compile, unless I
> make member x mutable, so I'll do that". It seems to me that instead
> of opening that door, a better solution is (1) identify all reasonable
> use-cases (and we've only managed to come up with three or four so
> far, so even if we've missed a few, it's clearly not a big number),
> and then (2) provide alternative solutions for each of those
> use-cases.
> 
> What do you think?

Yes, I agree that the no_state can be dangerous (and in fact it is the primary reason I was dubious about it).
If the library solution is efficient then and the use cases I identified are covered then I see no need for the keyword (and keeping the language simple and ensuring the the users understand the style of the language is worth some effort).
What made me change a little my idea is that writing down the use cases I saw that most of them can be implemented efficiently (both in space and time) with mutable state.
If the compiler really gets more aggressive in ensuring that invariant is constant then the only possible solution will be fully external (id_number in the object+cleanup handle in destructor, and external hashtable mutable_state[id_number]), and it would be a pity to have to pay this extra cost when most cases in which this is used are related to the need of being more efficient.
Still maybe it is a price that does not have to be payed (if the library solution can avoid it) or is worth being payed.

Fawzi

On 01/06/2008, Fawzi Mohamed <fmohamed@mac.com> wrote:
>  If the library solution is efficient then and the use cases I identified
> are covered then I see no need for the keyword (and keeping the language
> simple and ensuring the the users understand the style of the language is
> worth some effort).

So let's make a list of all of the use-cases that we can collectively think of. These are the ones I can come up with:

(1) caching
(2) reference counting
(3) intrusive linked lists (also intrusive binary tree nodes, etc).
(4) "is associated with"

Any more?



>  If the compiler really gets more aggressive in ensuring that invariant is
> constant then the only possible solution will be fully external (id_number
> in the object

No need for that. The hashtable can be keyed on "this".

> +cleanup handle in destructor,

which would be transparent

> and external hashtable
> mutable_state[id_number]),

It wouldn't need to be external, it could be a static member variable. (I think it would have to be, if we want cleanup to be transparent). So you'd end up with something like

    class A
    {
        mixin Cache!(int) x;
    }

    const a = new A;
    a.x = 3; // OK


>it would be a pity to have to pay this extra
> cost when most cases in which this is used are related to the need of being more efficient.

If the calculation is faster than a hashtable lookup, then you shouldn't be caching anyway. If the calculation is slower than a hashtable lookup, then with a hashtable lookup, you still win.

I'm not so sure about the other use cases. That's why it's a good idea to make a list, and weigh up the pros and cons of each possible solution.

On 2008-06-01 08:44:59 +0200, "Janice Caron" <caron800@googlemail.com> said:

> On 01/06/2008, Fawzi Mohamed <fmohamed@mac.com> wrote:
>> If the library solution is efficient then and the use cases I identified
>> are covered then I see no need for the keyword (and keeping the language
>> simple and ensuring the the users understand the style of the language is
>> worth some effort).
> 
> So let's make a list of all of the use-cases that we can collectively
> think of. These are the ones I can come up with:
> 
> (1) caching
> (2) reference counting
> (3) intrusive linked lists (also intrusive binary tree nodes, etc).
> (4) "is associated with"
> 
> Any more?

I had written the cases I could come up with here
		http://www.wikiservice.at/d/wiki.cgi?TransitiveConst

>> If the compiler really gets more aggressive in ensuring that invariant is
>> constant then the only possible solution will be fully external (id_number
>> in the object
> 
> No need for that. The hashtable can be keyed on "this".

ok, using a size_t, so that the object is not kept around for it

>> +cleanup handle in destructor,
> 
> which would be transparent

but needs at least a mixin in the destructor, or there is some magic that I don't know yet?

>> and external hashtable
>> mutable_state[id_number]),
> 
> It wouldn't need to be external, it could be a static member variable.
> (I think it would have to be, if we want cleanup to be transparent).
> So you'd end up with something like

yes with external I meant not packed with the object.

> 
>     class A
>     {
>         mixin Cache!(int) x;
>     }
> 
>     const a = new A;
>     a.x = 3; // OK
> 
> 
>> it would be a pity to have to pay this extra
>> cost when most cases in which this is used are related to the need of being
>> more efficient.
> 
> If the calculation is faster than a hashtable lookup, then you
> shouldn't be caching anyway. If the calculation is slower than a
> hashtable lookup, then with a hashtable lookup, you still win.
> 
> I'm not so sure about the other use cases. That's why it's a good idea
> to make a list, and weigh up the pros and cons of each possible
> solution.

I agree that listing the use cases is a good idea, and what I have tried to do.
I think for example that in the case of lazy linked list the external hastable solution is probably too expensive, at leas twice as slow to traverse, and with at least twice the overhead in memory.
Indeed a linked list is often a poor choice, as it is oversequentializing and has a rather large overhead, but it is a choice that come up naturally when using the functional programming style.
Also for statistical information about calling pattern to a pure function one probably doesn't want to spend much time/space.
Memoization, well maybe you are right, that is unless you are in a tight loop, you probably don't care about the hastable lookup, but this happens in *every* call independently if the element is present or not, so things like caching just the last request with a simple pointer, if it is often repeated are probably not an option.

Fawzi

On 2008-06-01 08:44:59 +0200, "Janice Caron" <caron800@googlemail.com> said:

> (3) intrusive linked lists (also intrusive binary tree nodes, etc).

just a note actually I think that it is lazyness (lazy construction) not intrusivness that gives problems with const and mutable...

On 01/06/2008, Fawzi Mohamed <fmohamed@mac.com> wrote:
> but needs at least a mixin in the destructor, or there is some magic that I don't know yet?

There's some magic that you don't know about yet - specifically, that classes are allowed to have multiple destructors. When the object goes out of scope, all of its destructors are called. That means that the Cache! mixin I mentioned earlier only needs to define an additional destructor of its own.


> I think for example that in the case of lazy linked list the external hastable solution is probably too expensive, at leas twice as slow to traverse, and with at least twice the overhead in memory.

Absolutely. However, if the standard library were to provide List!(T), then I think this need would go away.


>  Also for statistical information about calling pattern to a pure function
> one probably doesn't want to spend much time/space.

It might not be possible to collect "statistical information about calling pattern to a pure function" anyway, since if the compiler does any decent optimization, then the number of times that a pure function is executed may have no bearing whatosever on the number of times that it's called. I think, the question, "How often would it have been executed if it wasn't pure?" can only be answered by not making it pure!

On 2008-06-01 15:31:12 +0200, "Janice Caron" <caron800@googlemail.com> said:

> On 01/06/2008, Fawzi Mohamed <fmohamed@mac.com> wrote:
>> but needs at least a mixin in the destructor, or there is some magic that I
>> don't know yet?
> 
> There's some magic that you don't know about yet - specifically, that
> classes are allowed to have multiple destructors. When the object goes
> out of scope, all of its destructors are called. That means that the
> Cache! mixin I mentioned earlier only needs to define an additional
> destructor of its own.

nice!

>> I think for example that in the case of lazy linked list the external
>> hastable solution is probably too expensive, at leas twice as slow to
>> traverse, and with at least twice the overhead in memory.
> 
> Absolutely. However, if the standard library were to provide List!(T),
> then I think this need would go away.

The need of a mutable part in const comes form the lazyness of the construction of the list, not from the use of the list, any lazily constructed structure might need it.

let's look at a simple (and thus artificial) example (fully explicit, most of it can then be part of a mixin template) of what I want to be able to do: a lazy list of odd numbers from 1 to 1_000_000 (or even infinity)
This example as written is illegal and correctly so, but I want to be able to do something like this with a similar efficiency.

class ByTwo{
 int nAtt;
 private ByTwo *_next;
 this(int nAtt, ByTwo next){
   this.nAtt=nAtt;
   this._next=next;
 }
 ByTwo next() pure{
   if (_next==undefined){
    if (nAtt<1_000_000){
      _next=new ByTwo(nAtt+2,undefined);
    else
      _next=null;
   }
   return _next;
 }
}

Here undefined is just an invalid memory location 0x01, or if no such memory exist then just the address of an object that will stay around forever.

Now I might have a pure function like

int listLengthAcc(T)(T t,int length)pure{
 if (t is null) return length;
 return listLengthAcc(t.next,length+1);
}

and I want to call

listLengthAcc(cast(const) new ByTwo(1,undefined))

if everything would work this will use few memory, the stack will not grow and will return 499_999.

Note that the list is effectively constant from outside, and it is as if it would be there from the beginning, but it is potentially much more efficient from the memory point of view (and from the computational point of view in not all elements are needed).
This use is the (static) Lazy Caching (in the wiki).
To use it one could also use unsafe casts instead of some keyword, if it is guaranteed that no readonly memory (or something like it) are used.

>> Also for statistical information about calling pattern to a pure function
>> one probably doesn't want to spend much time/space.
> 
> It might not be possible to collect "statistical information about
> calling pattern to a pure function" anyway, since if the compiler does
> any decent optimization, then the number of times that a pure function
> is executed may have no bearing whatosever on the number of times that
> it's called. I think, the question, "How often would it have been
> executed if it wasn't pure?" can only be answered by not making it
> pure!

If I want to optimize the function I want the answer to the calling pattern of a pure function with all optimization.
Not a common use case, and it can be hacked around ad hoc, but still not unresonable.

Fawzi Mohamed Wrote:

> On 2008-05-29 18:41:21 +0200, "Steven Schveighoffer" <schveiguy@yahoo.com> said:
> 
> > What if D2 were to introduce a keyword that allows you to decouple a class member from the class state for the purposes of const?  This keyword basically means that the member is stored with the class data but is unaffected by the constancy of an instance.  In other words, a non-state member variable is not cast to const when the class instance is cast to const.  This is an implementation of the 'is associated with' OO relationship.  This is similar to the 'mutable' keyword in C++, or the way mutexes work in D.
> > 
> > If this were to happen, would you consider this to be a positive, negative, or inconsequential change?
> 
> I already expressed my view about it in
> 	http://www.wikiservice.at/d/wiki.cgi?TransitiveConst
> 
> I think that it is a good idea, but I think that its name should be much uglier unsafe_mutable, and should be seen by everybody in the community as a bad, and not to be used.

actually from the discussion I reconsidered (again) a little my position because I realized that the safe variant (together with an unsafe cast) gives what I want.
So yes either there is a tacit agreement that it is ok in extreme case to modify an object that was created as mutable then made const and maybe even passed as argument to a pure function (thus invariant into it) through a cast (no read only memory or things like it), or I would like to have the no_state keyword.

> > Would you stop using D because of it?
> no
> > Would you switch to D2 because of it?
> no
> > Would you consider this concept hard to explain or understand?
> no, but hard to use correctly if it really breaks the invariance, and not much useful if it does not break invariance.

well maybe I should say that what is keeping me away from D2.0 is the fact that I want to do some real work into it, and already in D 1.0 I got side tracked into many side tasks, and I am afraid that the transition to D 2.0 will be even more time consuming.
Furthermore I use GDC (mac and AMD64), and GDC has just began supporting D 2.0, so I think that I will encounter even more issues.
Probably with the next GDC version (and my project further along) I will give it a real try.

Fawzi

Fawzi Mohamed Wrote:

> Basically it is an unsafe hole that allows to implement nice an useful stuff (suspended values(lazy eval & cache), dataflow variables, memoization, performace/statistical information), but can break invariant and introduce subtle bugs.
>
Jeffrey Richter in "CLR via C#" proposes to implement immutability as a class design rather than compiler-checked const. Transitive const is good for POD, but for classes... it seems to have high complexity and unpredictable behavior in complex cases, and it's nearly unneeded in simple cases.