www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Poll: a nonstate keyword

reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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?

Would you stop using D because of it?

Would you switch to D2 because of it?

Would you consider this concept hard to explain or understand?
May 29 2008
next sibling parent reply Fawzi Mohamed <fmohamed mac.com> writes:
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.

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.


 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.

Fawzi
May 29 2008
next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 29/05/2008, Fawzi Mohamed <fmohamed mac.com> wrote:

 but can break invariant


That part is not correct. A couple of months back, I submitted a paper
to Walter and the gang, based on these ideas, in which I showed that
the transitive closure of const/invariant remained fully intact under
this model. Andrei confirmed that I was correct, and subsequently
tried to help explain it to Walter.


 and introduce subtle bugs.


That part is probably true, but it depends on whether or not people
"get it", which I think is what Steven was asking. Consider the
following (legal) code

    struct A
    {
        static int n;
    }

    invariant A a;
    a.n = 42;

I don't think anyone would argue that "static breaks invariant", but
could you say that code like the above "introduces subtle bugs"?
Maybe. Maybe not. It depends on understanding.

"nonstate" has been known by other names in previous discussions,
including "unpaintable". (There was quite a long thread with that
one). The general feeling over at Phobos is that the number of
use-cases is small enough that a handful of library solutions could
eliminate the need for the keyword. The problem, as I see it, is that
those library solutions have been talked about, but not yet
implemented. Consequently, there is still a perceived need for
"nonstate" - a perceived need which would go away as soon as those
alternative solutions were made available.
May 29 2008
parent reply Fawzi Mohamed <fmohamed mac.com> writes:
On 2008-05-30 08:08:35 +0200, "Janice Caron" <caron800 googlemail.com> said:


 On 29/05/2008, Fawzi Mohamed <fmohamed mac.com> wrote:

 but can break invariant


 
 That part is not correct. A couple of months back, I submitted a paper
 to Walter and the gang, based on these ideas, in which I showed that
 the transitive closure of const/invariant remained fully intact under
 this model. Andrei confirmed that I was correct, and subsequently
 tried to help explain it to Walter.


Indeed there are two ways to introduce mutable space.
The first one that gives access to the mutable space also to pure 
functions (but potentially breaks everything).
The catch is that by default updates to this mutable state might get 
lost due to compiler optimizations (as the compiler is free to float 
pure functions on them out of a loop, or to copy invariant objects), 
and this should be considered ok (which means that the result of the 
program cannot depend on this mutable state).
This can be used to implement efficiently memoization and lazy caching 
also for pure functions (which I want).

The other possibility (that Steven and you propose, if I understood 
correctly) is to disallow pure functions to access mutable state. This 
diminished the usefulness of pure functions or mutable state depending 
from how you look at the problem.
Indeed this solution does not break  invariance.

If implicit automatic copies (without calling a copy method) of object 
or part of it are allowed then the picture becomes more complex, but 
such a thing has a questionable value.


 and introduce subtle bugs.


 
 That part is probably true, but it depends on whether or not people
 "get it", which I think is what Steven was asking. Consider the
 following (legal) code
 
     struct A
     {
         static int n;
     }
 
     invariant A a;
     a.n = 42;
 
 I don't think anyone would argue that "static breaks invariant", but
 could you say that code like the above "introduces subtle bugs"?
 Maybe. Maybe not. It depends on understanding.
 
 "nonstate" has been known by other names in previous discussions,
 including "unpaintable". (There was quite a long thread with that
 one). The general feeling over at Phobos is that the number of
 use-cases is small enough that a handful of library solutions could
 eliminate the need for the keyword. The problem, as I see it, is that
 those library solutions have been talked about, but not yet
 implemented. Consequently, there is still a perceived need for
 "nonstate" - a perceived need which would go away as soon as those
 alternative solutions were made available.


I agree that a good library implementation is what one should strive to-
The question is how to implement them.
Without keyword one could achieve this using fully unsafe casts, I 
think, but is something like that allowed in a pure function?
If the answer is no, then to be able to implement them in plain D in a 
library the keyword would still be needed, or a way to declare an 
unsafe function pure (basically haskell unsafePerformIO).
May 30 2008
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 30/05/2008, Fawzi Mohamed <fmohamed mac.com> wrote:

  The other possibility (that Steven and you propose, if I understood
 correctly) is to disallow pure functions to access mutable state.


As currently planned, inputs and outputs to pure functions must be
invariant (or implicitly castable to invariant, e.g. int). You can use
mutable data inside the function, but the lifetime of that data is the
scope of the function - it will not persist beyond it.


 Without keyword one could achieve [a good library implementation] using fully
 unsafe casts, I think, but is something like that allowed in a pure function?


I think not. Also, caching could be achieved by a library
implementation without any unsafe casts at all - but it still wouldn't
be allowed in a pure function because it modifies global state.

If you think about it logically, Steven's proposed keyword "nostate"
is a good way of looking at it. A "nostate" variable is not part of
the class's state. It is well known that pure functions cannot access
global state, but more generally, pure functions cannot access
anything which is not part of the state of its inputs. "nostate"
variables would be, by definition, not part of the objects' state, and
therefore inaccessible to pure functions, same as static member
variables.



 If the answer is no, then to be able to implement them in plain D in a library
 the keyword would still be needed, or a way to declare an unsafe function pure
 (basically haskell unsafePerformIO).


I don't think I've completely understood what you're trying to get at.
Saying "basically haskell unsafePerformIO" tells me nothing, because I
don't speak Haskell and have no idea what that means.

One of the advantages of pure functions, however, is that (like
inlining) memoization can be done /by the compiler/, so you don't have
to do it yourself. How good a job the compiler will do remains to be
seen. My guess would be, poor at first, getting increasingly better
over time.
May 30 2008
parent reply Fawzi Mohamed <fmohamed mac.com> writes:
On 2008-05-31 07:40:56 +0200, "Janice Caron" <caron800 googlemail.com> said:


 On 30/05/2008, Fawzi Mohamed <fmohamed mac.com> wrote:


[...]

 If the answer is no, then to be able to implement them in plain D in a library
 the keyword would still be needed, or a way to declare an unsafe function pure
 (basically haskell unsafePerformIO).


 
 I don't think I've completely understood what you're trying to get at.
 Saying "basically haskell unsafePerformIO" tells me nothing, because I
 don't speak Haskell and have no idea what that means.


Sorry , basically I want a hack to convince the compiler that even if a 
function looks not pure it actually is.
Maybe a cast, like this (or with an uglier name)
pure int function(T) x=cast(pure int function(T))&y;
basically it says, to the compiler "yes I was careful and you can treat 
this function as pure, just do it, an if there are bug they are my 
fault because I am doing something potentially unsafe".

If there is something like this then no_state becomes useful, otherwise 
t is much less useful.


 One of the advantages of pure functions, however, is that (like
 inlining) memoization can be done /by the compiler/, so you don't have
 to do it yourself. How good a job the compiler will do remains to be
 seen. My guess would be, poor at first, getting increasingly better
 over time.


Sorry that is not good enough for me I want functions lifted out of 
inner loops, and a compiler that says to me either you use the slow 
pure function, and I will lift it out of the loop, or the fast one, but 
it will stay in the loop, is not good enough for me.
I want a hole to be able to trick the compiler into floating out the 
fast function.
In haskell this hole is called unsafePerformIO, and I think that it is 
a good name because when you use it it makes it very clear that you are 
on your own on slippery soil... :)

Fawzi
May 31 2008
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 31/05/2008, Fawzi Mohamed <fmohamed mac.com> wrote:

  Sorry , basically I want a hack to convince the compiler that even if a
 function looks not pure it actually is.


The one example of this which I can recall, which has been
demonstrated in this forum, is calling a "helper function" from within
a pure function. Is that what you're talking about? If so, it's been
mentioned before. Here's an example:

    void helper(char[] s) // not pure
    {
        s[0] = 'J';
    }

    string foo(string s) pure
    {
        char[] tmp = s.dup;
        helper(tmp);
        return assumeUnique(tmp);
    }

Currently, it seems that the above might not be legal code, since pure
functions cannot call non-pure functions. However, what makes this
case (and others like it) special is that, although helper itself is
not pure, if it were inlined, it wouldn't stop foo from being pure.

This has been pointed out before, and I am /sure/ that Walter will
come up with a solution which makes it possible (though not
necessarily in the first attempt).

I have absolutely no idea, however, what this has to do with Steven's
question. Is it relevant, or are we heading off-topic?




  Maybe a cast, like this (or with an uglier name)
  pure int function(T) x=cast(pure int function(T))&y;


The way I read it, the following will work, as is already legal syntax

    auto x = cast(function int(T) pure)&y;



 One of the advantages of pure functions, however, is that (like
 inlining) memoization can be done /by the compiler/, so you don't have
 to do it yourself. How good a job the compiler will do remains to be
 seen. My guess would be, poor at first, getting increasingly better
 over time.


  Sorry that is not good enough for me I want functions lifted out of inner
 loops, and a compiler that says to me either you use the slow pure function,
 and I will lift it out of the loop, or the fast one, but it will stay in the
 loop, is not good enough for me.
  I want a hole to be able to trick the compiler into floating out the fast
 function.


I still don't get it. Can you show me what you mean with an example?
May 31 2008
parent reply Fawzi Mohamed <fmohamed mac.com> writes:
On 2008-05-31 11:37:44 +0200, "Janice Caron" <caron800 googlemail.com> said:


 On 31/05/2008, Fawzi Mohamed <fmohamed mac.com> wrote:

 Sorry , basically I want a hack to convince the compiler that even if a
 function looks not pure it actually is.


 
 The one example of this which I can recall, which has been
 demonstrated in this forum, is calling a "helper function" from within
 a pure function. Is that what you're talking about? If so, it's been
 mentioned before. Here's an example:
 
     void helper(char[] s) // not pure
     {
         s[0] = 'J';
     }
 
     string foo(string s) pure
     {
         char[] tmp = s.dup;
         helper(tmp);
         return assumeUnique(tmp);
     }
 
 Currently, it seems that the above might not be legal code, since pure
 functions cannot call non-pure functions. However, what makes this
 case (and others like it) special is that, although helper itself is
 not pure, if it were inlined, it wouldn't stop foo from being pure.
 
 This has been pointed out before, and I am /sure/ that Walter will
 come up with a solution which makes it possible (though not
 necessarily in the first attempt).
 
 I have absolutely no idea, however, what this has to do with Steven's
 question. Is it relevant, or are we heading off-topic?


but yes with this we are heading off-topic, what I meant is
1) I want a loophole to be able to access this no state mutable state 
also in pure functions (even if I know that in general this should not 
be allowed as it potentially breaks everything)

2) if there is a way to convince the compiler that a non pure function 
should be treated as a pure function (and this is what I was after 
before) then the "safe" no_state can be used to achieve 1).

If the following works:

 Maybe a cast, like this (or with an uglier name)
 pure int function(T) x=cast(pure int function(T))&y;


 
 The way I read it, the following will work, as is already legal syntax
 
     auto x = cast(function int(T) pure)&y;


then basically we have 2)
int potentiallyUnsafe(T x){ ...}

pure int ITellYouItIsSafe(T x){
  return (cast(function int(T) pure)&potentiallyUnsafe)(x);
}

(I am surprised at how harmlessly it looks)
and adding no_state is equivalent with the more powerful (and 
dangerous) version that I want.


 One of the advantages of pure functions, however, is that (like
 inlining) memoization can be done /by the compiler/, so you don't have
 to do it yourself. How good a job the compiler will do remains to be
 seen. My guess would be, poor at first, getting increasingly better
 over time.


 
 Sorry that is not good enough for me I want functions lifted out of inner
 loops, and a compiler that says to me either you use the slow pure function,
 and I will lift it out of the loop, or the fast one, but it will stay in the
 loop, is not good enough for me.
 I want a hole to be able to trick the compiler into floating out the fast
 function.


 
 I still don't get it. Can you show me what you mean with an example?


This is like a generalization of the array indexing example

starting with a code like this:
  void g(int i, const Pippo x, Pippo y){
	auto t=pureF(x);
	y.doSomething(t,i);
  }

then this loop
  for (int i=0;i<100;i++)
    g(i,x,y);
should be transformed as follow:
inline g:
  for (int i=0;i<100;i++){
	auto t=pureF(x);
	y.doSomething(t,i);
}

move pureF(x) outside the loop:
  auto t=pureF(x);
  for (int i=0;i<100;i++){
	y.doSomething(t,i);
}

This last operation is valid *only* if pureF is pure.
Now imagine that the previous fragment is called several times, and 
that memoization in pureF can improve much its performance.
Then I either have to choose to use memoization (but then the function 
is not pure anymore for D, and it stays in the loop) or avoid 
memoization, and the function is pure but then pay the penalty later 
when the previous code snipped is calculated several times.
I want it all, I want it to be possible to have memoization a purity 
related optimizations.

It seems that with a safe no_state and a cast this is possible, so yes 
I very much want no_state.

Fawzi
May 31 2008
parent reply "Janice Caron" <caron800 googlemail.com> writes:
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?
May 31 2008
parent reply Fawzi Mohamed <fmohamed mac.com> writes:
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
May 31 2008
parent reply "Janice Caron" <caron800 googlemail.com> writes:
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.
May 31 2008
next sibling parent reply Fawzi Mohamed <fmohamed mac.com> writes:
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
Jun 01 2008
parent reply "Janice Caron" <caron800 googlemail.com> writes:
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!
Jun 01 2008
parent Fawzi Mohamed <fmohamed mac.com> writes:
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.
Jun 01 2008
prev sibling parent Fawzi Mohamed <fmohamed mac.com> writes:
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...
Jun 01 2008
prev sibling next sibling parent Fawzi <fawzi gmx.ch> writes:
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
Jun 02 2008
prev sibling parent terranium <spam here.lot> writes:
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.



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.
Jun 02 2008
prev sibling parent "Neil Vice" <sardonicpresence gmail.com> writes:
"Steven Schveighoffer" <schveiguy yahoo.com> wrote in message 
news:g1mmbh$ftq$1 digitalmars.com...

 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?


This is certainly a feature I've felt the need for in the past, and caching 
to me is the obvious use-case.

Having said that, I recall arguments to the effect that there are better 
ways to implement such things that don't require the use of such a keyword 
and prevent the need to "break" the transitive-const model.

Given this, my current stance is that it should be left out unless it can be 
demonstrated that there is a useful design that cannot be implemented 
without it, and I will be interested to see if I continue to feel the need 
for it when optimising code in future.
May 29 2008