How mutable is immutable?

[Artur Skawina]

On 10/18/12 10:08, Don Clugston wrote:
> On 17/10/12 18:02, Timon Gehr wrote:
>> On 10/17/2012 01:49 PM, Don Clugston wrote:
>>> On 01/01/12 13:50, Timon Gehr wrote:
>>>> On 01/01/2012 10:40 AM, Denis Shelomovskij wrote:
>>>>> So, I'm a function `f`, I have an `immutable(type)[]` argument and I
>>>>> want to store it for my friend `g` in an TLS variable `v`:
>>>>> ---
>>>>> string v;
>>>>> debug string sure;
>>>>>
>>>>> void f(string s) { v = s; debug sure = s.idup; }
>>>>> void g() { assert(v == sure); }
>>>>> ---
>>>>> I also store a copy of `s` into `sure` for my friend to ensure
>>>>> immutable
>>>>> date hasn't been mutated.
>>>>> Can my friend's assertion ever fail without breaking a type-system?
>>>>> Sure. Just consider this:
>>>>> ---
>>>>> void main() {
>>>>> auto s = "abba".idup;
>>>>>     f(s);
>>>>>     delete s;
>>>>>     g();
>>>>> }
>>>>> ---
>>>>> Is it by-design? Looks like deleting immutable (and const because of
>>>>> implicit conversion) data should be prohibited.
>>>>> OK. Let `delete` be fixed. Can we still fail?
>>>>> ---
>>>>> void h() {
>>>>>     immutable(char)[4] s = "abba";
>>>>>     f(s);
>>>>> }
>>>>> void main() {
>>>>>     h();
>>>>>     g();
>>>>> }
>>>>> ---
>>>>> Damn! So, what can we do with it? Not sure, but I have a proposal.
>>>>>
>>>>> Fix it in language:
>>>>> * disallow `delete` of const/immutable data
>>>>> * disallow immutable data on the stack
>>>>>
>>>>> This makes data really immutable if I don't miss something. Anyway, I
>>>>> want `immutable` qualified data to be immutable without breaking a
>>>>> type-system (if one do it, its his own responsibility), so some changes
>>>>> should be made (IMHO).
>>>>
>>>> You are using unsafe language features to break the type system. That is
>>>> not the fault of the type system.
>>>>
>>>> '@safe:' at the top of the program should stop both examples from
>>>> working, it is a bug that it does not.
>>>
>>> That's the point -- *which* checks are missing from @safe?
>>
>> Escaping stack data and arbitrarily freeing memory are not operations
>> found in memory safe languages.
> 
> HOW do you propose to check for escaping stack data?

/How/ is not a problem (ignoring implementation costs), the /language definition/
part is trickier - you need a very precise definition of what is allowed and what
isn't; otherwise different compilers will make different decisions and every
compiler will support only a vendor-specific non-std dialect...
(eg storing a scoped-ref into some kind of container, passing that down to other
functions could work, but what if you then need to let the container escape and
want to do that by removing the scoped-ref? It might be possible for the compiler
to prove that it's safe, but it's unlikely that every compiler will act the same)

>>> But I'm not sure that you're right, this looks broken to me, even
>>> without @safe.
>>>
>>> What does it mean to create immutable data on the stack? The stack is
>>> intrinsically mutable!
>>
>> So is the heap.
> 
> No it is not. Data on the stack *cannot* survive past the end of the function call. Data on the heap can last forever.

Lifetime and mutability are different things.

>> What does it mean to garbage collect immutable data?
> 
> From the point of view of the application, it doesn't happen. There are no observable semantics. It's merely an implementation detail.
> 
>> What does it mean to allocate an 'int' on the stack?
>>
>>> What does it mean to delete immutable data?
>>
>> Deallocate the storage for it and make it available for reuse.
>> Accessing it afterwards leads to arbitrary behaviour. This is the same
>> with mutable data. As the program may behave arbitrarily in this case,
>> it is valid behaviour to act as if immutable data changed.
> 
> No, you've broken the type system if you've deleted immutable data.
> If I have a reference to an immutable variable, I have a guarantee that it will never change. delete will break that guarantee.

Yes. The alternative (to allow explicit delete on immutable data) would likely
be too complicated to be worth implementing in the near future - you need to
ensure the data is unique, there are no other refs to it, and forbid accessing
it after the 'delete' op. I guess an easy way out would be to ask the GC to run
a collect cycle and return back whether an object was successfully collected.
But i can't really see a useful application for it, and you'd need a special
convention, as the GC would have to given the last ref to the object.


> With a mutable variable, I have no such guarantee. (It's not safe to allocate something different in the deleted location, but it's OK to run the finalizer and then wipe all the memory).
> 
>>> I think it's reasonable for both of them to require a cast, even in
>>> @system code.
>>>
>>
>> The implementation of the 'scope' storage class should be fixed. We
>> could then require an unsafe cast(scope) to disable prevention of stack
>> address escaping.
> 
> No we can't. f cannot know that the string it has been given is on the stack. So main() must prevent it from being given to f() in the first place. How can it do that?
> 
> void foo(bool b, string y)
> {
>   immutable (char)[4] x = "abba";
>   string s = b ? x : y;
>   f(s);
> }
> 
> Make it safe.

Trivial. 

   void f(scope string s) { /*v = s; # now illegal */ debug sure = s.idup; }

Obviously, it would need a properly working 'scope'. /Then/ making
it illegal to pass refs to local (or otherwise) scoped object in a
way that would allow them to escape would work.
Right now, when 'scope' is just decoration, trying to enforce such
restrictions would only create more bugs and confusion, I'm afraid.

The other reason why a working 'scope' is important is so that

   void g(string s) { f(s~"xyz"); }

does not cause heap allocation unless necessary. Even when the 
allocation is necessary the new object can be reused and the given 
back to the allocator when it's really dead. Reducing the amount of
garbage left behind is the best way to optimize the GC...

[of course 'scope' should have been the default etc etc, but that's
not really D2 material] 

artur