On 11/15/15 8:29 PM, Timon Gehr wrote:
> On 11/15/2015 10:06 PM, Andrei Alexandrescu wrote:
>> ...
>> I do agree that "pure const" may have other, stronger
>> properties.  But let's discuss "const" and what it can promise, or move
>> over to a whole new topic of "pure const".
>> ...
>
> "pure" is independent of "const" at the moment. So what you want to
> discuss is "const" in impure method signatures. Fine.
>
> In any case, consider that you might at some point be asked to explain
> why a const List is a good thing to want but a const pure List isn't.
>
>>>> Note that I
>>>> could even afford to have getFoo() return const, so no need for the
>>>> caller to make it so!
>>>>
>>>> With immutable, it's all cool. Immutable data is truly immutable, and
>>>> that can be counted on. But const, even today, cannot be assumed to be
>>>> as strong.
>>>> ...
>>>
>>> This is obviously true (it is what justifies the distinction between
>>> const and immutable in the first place), but this is not a way to
>>> justify making it weaker.
>>
>> Weaker than what? I've just shown black on white it's not a guarantee of
>> constant data.
>
> In one particular case.
>
> import package.module : foo, bar, baz, fun;
>
> final class C{
>      int x;
>      private this(int x){ this.x=x; }
> }
>
> void main(){
>      auto c = new C(2);
>      foo(c); // void foo(const C c);
>      bar();  // impure
>      baz();  // impure
>      fun(c.x); // this read of c.x can be optimized away under current
> semantics, not under the new ones
> }

Actually, you're wrong here. Typechecking main() does not take C's constructor's body into consideration, just the signature. So all the compiler knows about C whilst typechecking main() is:

final class C {
  int x;
  private this(int x);
}

What could happen (implausibly, but typechecking must be conservative) is that C's constructor may communicate with foo's package through a global, e.g. setting a global int* with the address of x. Then clearly the read of c.x cannot be optimized away today.

It's possible a class of examples can be found, but this is not one.

>> Today. With no compiler bugs in sight.
>> ...
>
> Do you mean, even ignoring compiler bugs?
>
>>> This is all just moving in the direction of a
>>> setting where all structs/classes just prevent immutable construction
>>> and make all member functions const, and const becomes the new mutable.
>>> I don't see the point.
>>
>> I don't understand this.
>> ...
>
> const is transitive and contagious. Make casting away const legal and
> spuriously require const in some places in the library, and you will
> have created a quite large incentive to use the now legal casts in a way
> that some will consider unprincipled.

Yah, I agree with that argument. Probably @mutable is a more principled way to go about things.


Andrei

On 11/16/2015 03:25 AM, Andrei Alexandrescu wrote:
>> In one particular case.
>>
>> import package.module : foo, bar, baz, fun;
>>
>> final class C{
>>      int x;
>>      private this(int x){ this.x=x; }
>> }
>>
>> void main(){
>>      auto c = new C(2);
>>      foo(c); // void foo(const C c);
>>      bar();  // impure
>>      baz();  // impure
>>      fun(c.x); // this read of c.x can be optimized away under current
>> semantics, not under the new ones
>> }
>
> Actually, you're wrong here. Typechecking main() does not take C's
> constructor's body into consideration, just the signature. So all the
> compiler knows about C whilst typechecking main() is:
>
> final class C {
>    int x;
>    private this(int x);
> }
>
> What could happen (implausibly, but typechecking must be conservative)

(Optimizations are not the same as type checking.)

> is that C's constructor may communicate with foo's package through a
> global, e.g. setting a global int* with the address of x. Then clearly
> the read of c.x cannot be optimized away today.
>

D's unit of encapsulation is the module, so the compiler actually knows the body of the constructor of C while optimizing main.

> It's possible a class of examples can be found, but this is not one.

One could just use a struct and inline the constructor, if you think that helps. Another way to avoid your objection is to make the constructor pure.

On Sunday, 15 November 2015 at 19:57:12 UTC, Andrei Alexandrescu wrote:
> On 11/15/2015 01:50 PM, Jonathan M Davis wrote:
>> On Sunday, 15 November 2015 at 18:09:15 UTC, Andrei Alexandrescu wrote:
>>> On 11/15/2015 01:00 PM, Jonathan M Davis wrote:
>>>> Basically, we have to decide between having physical const with the
>>>> guarantees that it provides
>>>
>>> We have that - it's immutable. -- Andrei
>>
>> Yes and no. As it stands, I can know that
>>
>> const foo = getFoo();
>> foo.bar();
>>
>> won't mutate foo unless I have another, mutable reference to foo
>> somewhere that bar somehow accessed.
>
> That is an illusion, and we need to internalize that. Consider:
>
> // inside some module
> struct T
> {
>   int[] data;
>   void bar()
>   {
>     // look, ma, no hands
>     g_data[1]++;
>   }
> }
> static int[] g_data;
> const(T) getFoo()
> {
>   T result;
>   result.data = g_data = [1, 2, 3];
>   return result;
> }
>
> In other words, you truly need access to the implementation of getFoo() in order to claim anything about the changeability of stuff. Note that I could even afford to have getFoo() return const, so no need for the caller to make it so!

Which is why I brought up pure. If either getFoo or bar is pure, then your backdoor doesn't work. Yes, without pure, globals work as a backdoor, but technically, they do that with immutable too, since you can put the entire state of the object outside of the object using globals.

> With immutable, it's all cool. Immutable data is truly immutable, and that can be counted on. But const, even today, cannot be assumed to be as strong.

No, const is not as strong as immutable. But my point is that as-is const still provides some guarantees about physical constness. And particularly when it's combined with pure, there are a lot of cases where you can rely on a const object not being mutated unless the programmer violates the type system. Contrast that with C++ where pretty much any function could choose to cast away const and mutate an object, making the const attribute essentially meaningless in principle. In practice, programmers are obviously better behaved than that, but it means that in D right now, const does provide actual compiler guarantees (even if they're not as strong as those for immutable), whereas in C++ it really only prevents accidental mutation.

If we go the route of making casting away const and mutating defined behavior (and possible adding something like @mutable), then what we'll end up with is a transitive version of C++'s const, and that definitely provides worse guarantees than we have now. So, we would be losing something if we made that change.

That being said, const as-is _is_ very restrictive, and a number of idioms are completely incompatible with it, and that sucks. But we've known that for some time, and the answer has generally been to either not use those idioms or to not use const - which unfortunately does mean that const often can't be used (and a container that needs to do fancy stuff with its internals is probably a prime place where it can't be used).

So, I'm not necessarily against changing how const works. It _is_ restrictive to the point of being impractical in a lot of code. But if we make such a change, we _will_ be losing out on the kind of compiler guarantees that Walter has been harping on for ages - how C++'s const is pretty much useless since it doesn't really guarantee anything, whereas D's const does provide compiler guarantees because it can't be legally cast away and mutated. And you don't seem to see that (at least based on what you've been saying).

There is a tradeoff to be made here. We've been choosing one side of that tradeoff for years now - the side that C++ didn't choose. Maybe we made the wrong choice and should switch sides. But it is a tradeoff, not a clear-cut decision.

- Jonathan M Davis

On Sunday, 15 November 2015 at 19:09:16 UTC, Andrei Alexandrescu wrote:
> So one important question is what style we use for Phobos and endorse as idiomatic. My sense after working on this for a while is - forget inout. Qualifiers are rather complex, and of them inout is the most. So I'd rather marginalize it. Please chime in with any thoughts.

Honestly, I'd say that if inout is needed, it should be used, since otherwise we're forced to have const results when we should be able to get mutable or immutable results.

Now, in many cases, templatizing fixes the problem, but that obviously won't work with member functions. For those, if you really want to avoid inout, you can always duplicate them, and in the case of PersistentList, it's not supposed to work with immutable anyway, so duplicating would only mean two copies, but if inout lets you do that with one body, it still seems better to use inout. Certainly, if you were trying to support mutable, const, and immutable, duplicating the function rather than using inout would be a bit much.

inout is unwieldy, but it does seem to solve a very real problem, and in some cases, the only alternative is writing the same function three times with different modifiers, so I would think that it would be a good idea to use it when the only alternative is needless code duplication.

If we want to revisit inout and try and come up with a better solution, then fine, but if it works, then I'd use it until we do have a better solution.

- Jonathan M Davis

On Sunday, 15 November 2015 at 21:45:08 UTC, Dicebot wrote:
> On Sunday, 15 November 2015 at 21:00:40 UTC, Andrei Alexandrescu wrote:
>> Passing arguments to functions that aren't supposed to change the containers. -- Andrei
>
> For that you don't need to mutate neither allocator nor RC (unless that const argument is actually leaked from inside the function to somewhere else - terrible, terrible thing to do). So strict physical const should suffice.

Except that what if the container is passed to something that keeps it around? The ref-count would need to at least be incremented when passing it, and if the container were passed around enough, it could potentially need to be incremented a lot.

Ranges are potentially another big issue. As I understand it, there have already been issues with const and ranges with std.container.Array, because some of the fancy stuff that it does internally really doesn't work with const (though maybe I misunderstood). But anything that would require that a range be able to mutate its associated container even for bookkeeping purposes wouldn't work with const. Certainly, any case where you want to do something like keep removed elements around specifically for a range and then destroy/free them when no range refers to them won't work with const.

Physical const works fantastically when you just want to pass something in and get a result. As soon as something needs to be stored as const or if you start trying to do fancy stuff like managing memory inside of an object, you quickly run into cases that don't work with it. I think that we can choose to live with that, but it _does_ mean that there are useful idioms that will be impossible with const, and ultimately, that probably means that const won't be used much - particularly when dealing with user-defined types.

And since you seem to think that it should be fine to cast away const and mutate when the object is actually mutable, I don't really see what objection you can have here as long as it's sure that PersistentList isn't immutable. Andrei's @mutable proposal would fix that, but even without that, I expect that we could force it by declaring an immutable constructor with no body and declaring opCast such that it doesn't work with immutable (though that's arguably abusing https://issues.dlang.org/show_bug.cgi?id=5747 ).

Regardless, I think that it's quite clear that certain idioms simply do not work with physical const, and there's been complaining about that for years. The only real question here is whether those idioms are worth enough to lose out on physical const. The answer up until now has always been no (at least from Walter), but since Andrei is now hitting this himself rather than seeing others complain about it, he clearly views it as a problem in a way that he didn't before, so that may result in him changing Walter's mind.

- Jonathan M Davis

On Monday, 16 November 2015 at 06:24:05 UTC, Jonathan M Davis wrote:
> On Sunday, 15 November 2015 at 21:45:08 UTC, Dicebot wrote:
>> [...]
>
> Except that what if the container is passed to something that keeps it around? The ref-count would need to at least be incremented when passing it, and if the container were passed around enough, it could potentially need to be incremented a lot.
>
> Ranges are potentially another big issue. As I understand it, there have already been issues with const and ranges with std.container.Array, because some of the fancy stuff that it does internally really doesn't work with const (though maybe I misunderstood).

this has a lot to do with const being virtually useless with structs

On Monday, 16 November 2015 at 06:36:31 UTC, rsw0x wrote:
> On Monday, 16 November 2015 at 06:24:05 UTC, Jonathan M Davis wrote:
>> On Sunday, 15 November 2015 at 21:45:08 UTC, Dicebot wrote:
>>> [...]
>>
>> Except that what if the container is passed to something that keeps it around? The ref-count would need to at least be incremented when passing it, and if the container were passed around enough, it could potentially need to be incremented a lot.
>>
>> Ranges are potentially another big issue. As I understand it, there have already been issues with const and ranges with std.container.Array, because some of the fancy stuff that it does internally really doesn't work with const (though maybe I misunderstood).
>
> this has a lot to do with const being virtually useless with structs

I'd say that there are two things about const which apply to structs which don't apply to classes which make const with structs bad. Stuff like having const member functions or having const values isn't necessarily any more of a problem with structs than it is with classes. What _is_ problematic is

1. const member variables (because they essentially force the whole struct to be treated as const even though it isn't - e.g. assignment doesn't work)

2. postblits don't work with const or immutable (so if you need a postblit, your struct really doesn't work with const or immutable)

Beyond that, const with structs is pretty much the same as it with classes. It's definitely restrictive, but not useless.

And actually, this gives me an interesting thought. Does making casting away const and mutating defined behavior give us a way to fix our postblit problem? I could see an argument that postblits should be completely unnecessary for immutable values (because you shouldn't need to avoid stuff like sharing references when it's immutable), which could mean that we could change it so that immutable structs values didn't trigger a postblit and thus worked fine as-is, and that would fix the problem with postblits and immutable. And if casting away const and mutating is legit, then it should be possible to treat the struct itself as mutable (or at least tail-const) within the postblit constructor, in which case it's then actually possible to have postblit constructor that works with const, whereas right now, we can't have it, because it would violate const to mutate the newly blitted, const struct.

So, if this really fixes our postblit problem, it might be worth it just for that. As it stands, postblit constuctors tend to have to be avoided in many cases because of how badly they interact with const and immutable.

- Jonathan M Davis

On Monday, 16 November 2015 at 06:24:05 UTC, Jonathan M Davis wrote:
[...]
>
> Regardless, I think that it's quite clear that certain idioms simply do not work with physical const, and there's been complaining about that for years. The only real question here is whether those idioms are worth enough to lose out on physical const. The answer up until now has always been no (at least from Walter), but since Andrei is now hitting this himself rather than seeing others complain about it, he clearly views it as a problem in a way that he didn't before, so that may result in him changing Walter's mind.
>
> - Jonathan M Davis

I appreciate this discussion. I feel better that I am not the only one having difficulty with the _const_ keyword. Honestly about the only time I use _const_ is to tell the D compiler that a struct member function does not modify its containing type. When I start to use _const_ I quickly get a headache trying to figure out how to fix my code when the compiler starts to complain about function overloading issues and starts to require explicit casts all over the place, _inout_ doesn't work, did I use _Unqual_ or maybe I shouldn't, should this be a template, etc. I end up with a headache and all I want is the thing to compile. I wonder many times why go through the trouble. Why not just use a unit test?

After reading through this discussion I wonder if it has been considered to keep _immutable_ and _const_ as they are, but add a less restrictive do-not-change-me type qualifier to the language? A keyword like _readonly_, for example, could represent the idea of intransitive const (or perhaps even a different type of do-not-change-me-ness). I appreciate the need to be conservative in language additions, especially at this point in the life cycle of D2. Still, if people want and can show they need a type of do-not-change-me type qualifier in addition to _const_ and _immutable_ (not overlapping with unique et. al.) why not provide it for them?

Just as a side thought, although it is probably a bit of a dasoku. But I have always wondered that if the purpose of _const_ is to allow some data to be changed by one reference but not changed by another, then why is it transitive. Doesn't that defeat its purpose? And then doesn't transitive const effectively have the same semantics and use-case as _immutable_? I mean, once you start to use transitive const in an interface, how are you supposed to get the mutable reference that is so promised? Perhaps this is the question that is essentially being asked here?

Joseph

On Monday, 16 November 2015 at 09:04:33 UTC, Joseph Cassman wrote:
> Just as a side thought, although it is probably a bit of a dasoku. But I have always wondered that if the purpose of _const_ is to allow some data to be changed by one reference but not changed by another, then why is it transitive. Doesn't that defeat its purpose?

The D designers might want to look at Pony lang's capability system, which has been proven sound. It has 6 different aliasing capabilites that regulates among other things transition from mutable to immutable.

D is a little bit better of (if it does not allow casting away const) than C++, because in C++ const is essentially "shared const", whereas in D in is "local const with potential aliasing". AFAIK the D sementics is that no other thread can hold a mutable reference to something you have as const. But it is still a relatively weak guarantee. In C you have "restricted" for notifying the compiler that the resource is aliasing free within the context.

> And then doesn't transitive const effectively have the same semantics and use-case as _immutable_? I mean, once you start to use transitive const in an interface, how are you supposed to get the mutable reference that is so promised? Perhaps this is the question that is essentially being asked here?

The right thing to do is to:

1. map out all possible aliasing combinations and pick a set of capabilities that is sound

2. poke a clean well defined hole through the constness by allowing a "mutable" modifier that does not depend on type state. (or you should add type state and an effect system).

3. implement something that is compatible with conservative C++ (shared head const with mutable fields and no const_cast).

D really should try to avoid repeating C++'s mistakes or add a different set of mistakes, in order to compensate for former mistakes.

On Sunday, 15 November 2015 at 20:23:58 UTC, Dicebot wrote:
> On Friday, 13 November 2015 at 23:10:04 UTC, Andrei Alexandrescu wrote:
>> I created a simple persistent list with reference counting and custom allocation at http://dpaste.dzfl.pl/0981640c2835.
>
>
> There is also another thing I wanted to mention on topic of persistent containers. Right now for me the most intriguing topic is trying to define immutable (and actually thread shared) cache data structure than can be efficiently and safely used without GC. There is whole class of tasks where you can get best performance by building new copy of cache in memory instead of modifying separate elements, trading increased memory concsumption for fast no lock parallel access. However in absence of GC task of deleting memory for older generations of cache becomes rather challenging. I have been thinking about approach with external two-level reference counting + dedicated allocator - quick thread-local RC comes first and once it goes to 0, shared RC in allocator gets decremented (being effetively user thread counter). Do you think it can work?

If the elements are immutable, you can actually write a parallel non-stop-the-world GC for your cache. You just need to record the "age" of each element, and define a grace period that must have passed before they can be freed.

As for your RC idea: You could either start by creating the objects as shared and add a `.unshare()` method to them, or start with thread-local objects and create the shared RC lazily (`.share()`).