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
