Helping with __mutable (which will be renamed to __metadata)

[Timon Gehr]

On 16.04.19 11:51, RazvanN wrote:
> On Saturday, 13 April 2019 at 00:45:07 UTC, Andrei Alexandrescu wrote:
>> Razvan Nitu is working on the DIP initiated by Timon Gehr, known 
>> colloquially as the one that introduces __mutable - i.e. a mechanism 
>> for allowing controlled changes to immutable data. Here's a draft:
>>
>> https://github.com/RazvanN7/DIPs/blob/Mutable_Dip/DIPs/DIP1xxx-rn.md
>>
>> We figured that we're dealing a misnomer - we don't want __mutable, 
>> but instead __metadata - information that is nominally part of the 
>> object but needs certain leeway from the type system. Typical use 
>> cases are:
>>
>> * reference counting of immutable data structures
>> * caching
>> * lazy evaluation
>>
>> We got stuck at the interaction of __mutable with const parent objects 
>> (unclear whether the parent object originated as immutable or 
>> unqualified), and how pure functions should deal with __mutable. The 
>> few solutions we are toying with are either incomplete or too 
>> complicated (or both).
>>
>> The help of a few PL and compiler specialists would be very valuable 
>> here. I'm cc'ing a few, if anyone wants to help please let us know.
> 
> This is a draft proposal and it is not finished. The initial draft that 
> was done by Timon [1] considers __mutable functions that act as 
> optimization blockers for
> the compiler with regards to `pure` functions. I feel that optimization 
> blockers
> for `pure` are a totally different concept than __mutable/__metadata 
> fields.
> ...

On the contrary, it's the type system information you _need_ in order to 
abstract over code that mutates __metadata. An assignment to a 
__metadata field is something you cannot ignore even though it is `pure` 
and does not return any interesting value. For any statement, you need 
to be able to assign a valid type to a function that contains this 
statement, and that captures what the type system knows about the statement.

> Considering that the currently the compiler does not do any 
> optimizations based on purity, I think it would be a lot easier to just 
> get __mutable/__metadata fields
> in, because they are a needed feature; after that, we can think on what 
> optimizations we want to implement and how they interact with 
> __mutable/__mutable.
> ...

You need to specify that there are optimizations that are allowed even 
though they change the set of mutations that the program performs. As I 
suggested earlier, if you want the semantics that's least restrictive 
for language evolution, you need to say something that implies that all 
optimizations based on the function signature are allowed, not "the 
compiler currently does not do any optimizations". That's precisely the 
wrong direction if you want to be conservative.

> Consider this code:
> 
> int foo() pure
> {
>       immutable(T)* x = allocate();
>       int y = bar(x);
>       deallocate(x);
>       return y;
> }
> 
> Currently, the compiler does not do any optimizations regarding purity 
> with it. If it did, it could have swapped the invocation of `deallocate` 
> with the one of `bar` leading to use-after-free.

What the compiler does and does not do has no bearing on the validity of 
the code per language semantics.

> Annotating `deallocate` 
> with __mutable would solve the issue in the event of compiler 
> optimizations. However, this example has nothing to do with 
> __mutable/__metadata fields; this kind of optimizations should be 
> discussed in a DIP of their own and not in a __mutable/__metadata DIP. 

That's simply nonsense. You define the language semantics, the compiler 
developer figures out optimizations that are consistent with that 
semantics. You don't need any DIPs for optimizations, you need DIPs to 
specify how programs may or may not behave. You can't really first come 
and say programs may not behave a certain way and then later relax that 
and say that actually those programs can also behave in this other way 
and at the same time claim that this is a conservative approach. It is 
not; it breaks code.


> Moreover,
> is this the direction we want to head in?
Absolutely. If you want to use __metadata you need to be aware that pure 
functions can be elided, and if the mutation of __metadata within a 
function is not self-contained such that it can be elided, you need to 
annotate that function.

> Require the user to mentally 
> trace the optimizations that the compiler might do?

The user of __metadata. _Some_ kinds of optimizations.

> This is just too complicated.
> ...

Then give up on __metadata and just implement your persistent data 
structures without the `immutable` qualifier slapped on top! `immutable` 
has no value if it cannot be used to justify equational reasoning on 
pure functions.

> That is why, I think that we should focus on implementing __metadata 
> with regards to fields and later on think about the optimizations that 
> we can perform.
> 
> As for __metadata fields:
> 
> 1. If we decide that __metadata fields are not conceptually part of the
> object, why would accesses to them be unsafe? We could  still make them 
> `private`,
> but we can view them as normal accesses from a @safety perspective.
> ...

Then those accesses can't be pure because they are like accesses to 
global variables.

> 2. I agree that `purity` should not be affected by __mutable/__metadata 
> fields; the object passed as argument will not be conceptually modified.
> ...

1 and 2 are fundamentally at odds with each other if you want __mutable 
fields to be accessible in pure functions, because you can't check 2 safely.


> If we take out optimizations out of the picture, things become a lot 
> more clearer.

You need to define the semantics!

> For me, the DIP is more of "how can we mutate fields in a non-mutable 
> object", not

You clearly can't mutate fields in a non-mutable object except 
non-mutable is some higher-level abstraction. That abstraction has to be 
defined. One way to define semantics for __metadata is to explicitly 
give the set of allowed rewrites, but you can also define it implicitly.

> "how do we implement optimizations regarding purity".
> 
> I don't see why the addition of __metadata should be delayed by how 
> optimizations based on purity are applied in the compiler,
> 
> ...

It shouldn't.