Logical const

[Fawzi Mohamed]

On 1-dic-10, at 04:52, Jesse Phillips wrote:

> Fawzi Mohamed Wrote:
>
>> The thing is that a lazy structure is very useful in functional
>> programming.
>> A lazy evaluation is something that should be possible using pure and
>> immutable.
>> I find it jarring that to do that one has to avoid D pure and  
>> immutable.
>
> Don't know what you mean by this.

a lazy list (for example one that list all natural numbers) cannot be  
immutable, without the possibility of a backdoor because all the  
"next" elements will have to be set at creation time.
(Lazy structures can be seen as memoizing a value produced by a pure  
function forever (i.e. never forgetting it).

>> To be able to safely use pure and immutable as I said one would need
>> some idioms that are guaranteed to be non optimized by the compiler.
>> for example casting a heap allocated type should be guaranteed to
>> remain modifiable behind the back:
>> auto t=new T;
>> auto t2=cast(immutable(typeof(t)))t;
>>
>> auto tModif=cast(typeof(t))t2; // the compiler has not moved or
>> flagged the memory of t, so one can modify tModif.
>
> This code is valid, the requirements placed on cast will not allow  
> it to move the data. Even types declared to be immutable my be  
> modifiable when cast to Unqual!(T), but the compiler can not  
> guarantee these.
>
> If I am wrong, please let me know why.

The code works now, I would like some assurance that  
cast(immutable(T)) doesn't do fancy stuff (or some equivalent way to  
ensure that *some* idiom will remain allowed.
If you think about it already now with opCast you cannot really know  
what opCast does, so a compiler would be allowed to return an  
immutable copy, or (if it uses whole pages) make the whole memory as  
read only.

>> clearly this is unsafe and it is up to the implementer to make sure
>> that the object is really logically const
>> and no function will see the internal changes.
>
> Yes, and I don't think compiler support adds any more guarantee than  
> casting those you want to modify in a const function. This Mutable  
> struct is supposed to help verify only modifiable data is cast:
>
> https://gist.github.com/721066

you example has an error in parallel, this is a good example of why  
the casting away should not be made convenient, and a user should just  
use well tested library code (for example dong thunk evaluation), that  
might be in a special type or mixed in.

You cannot have separate flag, and value without any synchronization,  
as other threads could see their value in a different order, so they  
could see dirty=false, but still no determinant.

This is somehow related to dataflow variables that can be set several  
times, but only to the same value (and indeed with a lazy list one can  
allow two threads to calculate the next element, but then only one  
should set it (using atomic ops to avoid collistions).
I have implemented DataFlow variables (but using the blip  
paralelization, that delays a task that waits, and resumes it when the  
value is ready, not with a thread lock) in
	https://github.com/fawzi/blip/blob/master/blip/parallel/smp/DataFlowVar.d
using D1


> I've taken many example use-cases for logical const and added them  
> as unittests. I think it is fairly reasonable if I could just get an  
> answer to my question about concurrency and declaring immutable types.
>
>> This is something that should be done sparingly, probably just in
>> library code implementing lazy evaluation or memoization (but code
>> that might be mixed in).
>
> Could you give an example of how lazy evaluation is achieved by  
> modifying state?

lazy structures need to modify the state (as I showed with the linked  
list example), lazy evaluation alone does not need to modify the state  
(and is indeed possible in D), but the storing/memoizing of the result  
needs it. To say the truth in D memoizing can be done with a static  
variable, but think about making the singly linked list like that, and  
you should immediately see that if gets *very* inefficient.