We need a typesystem-sanctioned way to cast qualifiers away

[Edmund Smith via Digitalmars-d]

First post, so let's see how this goes:

On Saturday, 20 June 2015 at 00:07:12 UTC, Andrei Alexandrescu 
wrote:
> 1. Reference counting: it's mutation underneath an immutable 
> appearance. For a good while I'd been uncomfortable about that, 
> until I figured that this is the "systems" part of D. Other 
> languages do use reference counting, but at the compiler level 
> which allows cheating the type system. It is somewhat fresh to 
> attempt a principled implementation of both reference counting 
> and safe functional collections, simultaneously and at library 
> level.
>
> My conclusion is that changing the reference count in an 
> otherwise immutable structure is an entirely reasonable thing 
> to want do. We need a way to explain the type system "even 
> though the payload is const or immutable, I'll change this 
> particular uint so please don't do any optimizations that would 
> invalidate the cast". The user is responsible for e.g. atomic 
> reference counting in immutable data etc.

This idea makes sense with the type checker, although I'm not 
sure how it fits D's current memory model. On the page detailing 
const and immutable (dlang.org/const3.html) it mentions that 
immutable data 'can be placed in ROM (Read Only Memory) or in 
memory pages marked by the hardware as read only', which may be 
problematic if an immutable's mutable reference counter is placed 
in a read-only page. Would this potentially be changed? It 
suggests that the compiler needs a way of telling if the struct 
is a typical immutable struct or is privately-mutable, 
publicly-immutable.

As for the language level, it helps to look at how an immutable 
value propagates. It can be passed by value or by reference, 
passed between threads without issue and its value never changes. 
The thread safety strongly implies that what isn't immutable is 
shared, so that every field in an immutable struct is still 
thread-safe. Its exposed value never changing is also crucial 
IMO, to the point where I think it should be a compiler error if 
the 'facade' of immutability collapses (e.g. mutable data is 
public or modifies a public function's result).

Passing copies also raises a point about the current state of 
'immutable struct S', which has a few things different to normal 
structs (and block anything but POD types. Is this intentional?).
Currently, D lacks destructors and postblit constructors on 
immutable structs, giving the error 'Error: immutable method 
SomeStruct.__postblit is not callable using a mutable object'. 
Throwing an immutable qualifier makes it no longer recognisable 
as a postblit constructor, so that doesn't work either. This 
makes perfect sense under the current assumption that 'immutable 
struct' implies it is a POD struct, but if/when under-the-bonnet 
mutability goes ahead, this assumption will no longer hold (and 
postblit constructors are pretty useful with refcounting). The 
same goes for destructors, too. Without these, passing immutable 
refcounts by copy isn't safe - the copy keeps the pointer, but 
doesn't increase the counter. This leads to a potential 
use-after-free if the copy outlives every 'proper' reference.
I'm not sure whether this is all necessary, however - it is 
possible to just ignore 'immutable struct' and use 'alias 
MyStruct = immutable(MyActualStruct);', in which case the 
previous paragraph can be ignored.

After playing around with examples of how to do proper immutable 
reference counting (e.g. static opCall factory) I think the 
smallest change large enough to work with would be to allow 
transitive immutability to not transfer immutability to 'private 
shared' variables (or behave this way in the memory model, so 
that casting to mutable is safe but the type system remains 
entirely transitive), while simultaneously making it a 
compile-time error to read or write to these variables from 
exposed (public) functions. This may want to be loosened or have 
exceptions (debug builds etc.), depending on other use-cases.

'shared' seems to be used at the moment for a few different hacks 
(e.g. GDC having 'shared' and 'volatile' behave identically for a 
while) and nothing particularly concrete, save some library 
functions and inter-thread message passing. It also seems 
suitable for avoiding overeager compiler optimisations, since the 
'shared' qualifier already shows that typical assumptions can't 
be made about it. Also, most existing scenarios I can think of 
for a private shared variable in an immutable object are rather 
contrived. Finally, it should push the use of atomic code, or at 
least basic multithreading good practices.

The forcing public code to avoid touching the mutable variables 
enforces the idea that this is meant for 'systems' code, not 
typical implementation logic (it would be pointless to use it for 
this). It also prevents the mutable-ness from leaking, either 
through return values or other logic ('return (mutaBool)?1:0') 
and enforces a clean design that the systems code wraps around, 
not the implementation logic wrapping around (and depending on) 
systems code.

A brief example using this change:

     struct Container(T) {
         struct Node {
             private shared uint count;
             ContainerImpl!T payload;
         }
         Node* node;
         IAllocator alloc;
         this() {
             node = alloc.make!Node(1, ContainerImpl!T());
         }
         this(this) {
             node.count.atomicOp!"++"; //
         }
         auto get() {
             return node.payload;
         }
         alias get this;
         ~this() {
             node.count.atomicOp!"++";
             if(node.count == 0) alloc.dispose(node);
         }
     }
     //Works like normal with enforced atomicity (maybe overkill 
in single-threaded code)
     //When immutable, everything but count is immutable, and the 
exposed interface
     //is statically guaranteed to be immutable too; everything is 
thread safe.

Looking for cases where this might not be backwards compatible 
leads to only a very narrow area that may cause behaviour changes:

     struct S {
         int i;
         private shared T t;
         ~this() { t.cleanup(); }
     }
     struct T {
         void cleanup();
         immutable void cleanup();
     }
     ...
     {
         immutable S s1 = S(1, T());
     }  //The transitively immutable s1.t is no longer immutable,
        // so calls the mutable cleanup on destruct instead


> 2. Allocation: functional containers carry with them a 
> reference to an IAllocator interface, which tells them how to 
> do memory allocation. Somewhat paradoxically, it is sometimes 
> necessary to allocate memory even for immutable objects. For 
> example, in the concatenation "value ~ list", the list's 
> allocator must be used.
>
> Again, the reference to IAllocator must be unqualified even 
> inside an otherwise qualified object.

The same idea should work here too.

Edmund

PS - any comments on this comment's style are welcome, I'm new to 
posting here