www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Persistent list

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I created a simple persistent list with reference counting and custom 
allocation at http://dpaste.dzfl.pl/0981640c2835. It's a good 
illustration of a number of issues. In particular, each cast must be 
properly explained.

Here's my exegesis:

* Lines 6: By construction the list doesn't work with mutable objects. 
This is because it uses sharing internally (in the classic manner of 
functional containers) to give the illusion of many copies.

* Lines 11-12: I came to terms with the notion that some types cannot be 
made immutable. We've been trying to do reference counting on immutable 
objects for a long time. It's time to acknowledge that true immutability 
(which the immutable keyword models) and reference counting don't mix. 
Const does work (more below). But overall I'm at peace with the notion 
that if you can't live without immutable, I'll refer you to the garbage 
collector.

* Lines 26-29: The allocator is fundamentally a mutable part of the 
container. This is an insufficiency of our type system - we can't say 
"this object may be constant, but this reference is to a mutable part of 
it". We can't explain that necessity out of existence, and List is part 
of the proof. So we need to make that cast legal.

One simple solution is to simply allow the cast. One more involved is to 
define an attribute  mutable with the following rules: (a)  mutable data 
is not affected by const; (b) if a type T contains transitively any 
 mutable member, immutable(T) is illegal. That would allow us to not 
need a cast in line 28.

* Line 35: the constness of the Node is taken away before deallocation. 
This is acceptable.

* Lines 40, 46: same matter as with the allocator - the reference count 
is a mutable part of a possibly const object.

* Line 65: deallocation again is allowed to cast things, even in safe 
code; the point here is we know we can do something the type system 
doesn't know.

* Lines 104-112: using recursion in the construction of objects with 
const parts is, I think, a major emerging idiom in D.

* Lines 141-152: I couldn't make tail() work with inout. Generally I'm 
very unhappy about inout. I don't know how to use it. Everything I read 
about it is extremely complicated compared to its power. I wish we 
removed it from the language and replaced it with an understandable idiom.

* Lines 161-185: Same problem: inout.

* Lines 191-199: Same problem: inout.

* Lines 208-259: I made inout work for getting the range of the list.

Please reply with improvements, ideas, comments, and such. Thanks!


Andrei
Nov 13 2015
next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 11/13/2015 03:10 PM, Andrei Alexandrescu wrote:


 at http://dpaste.dzfl.pl/0981640c2835



 * Lines 11-12: I came to terms with the notion that some types cannot be
 made immutable.


Could constructor qualifiers help in such cases? I would like to hear 
war stories and experiences from others who used that feature before:

The spec:

   http://dlang.org/struct.html#struct-constructor

My rewording:

 
http://ddili.org/ders/d.en/special_functions.html#ix_special_functions.constructor%20qualifier

DIP53:

   http://wiki.dlang.org/DIP53

Ali
Nov 13 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/13/2015 06:26 PM, Ali Çehreli wrote:

 On 11/13/2015 03:10 PM, Andrei Alexandrescu wrote:

  > at http://dpaste.dzfl.pl/0981640c2835

  > * Lines 11-12: I came to terms with the notion that some types cannot be
  > made immutable.

 Could constructor qualifiers help in such cases? I would like to hear
 war stories and experiences from others who used that feature before:

 The spec:

    http://dlang.org/struct.html#struct-constructor

 My rewording:


 http://ddili.org/ders/d.en/special_functions.html#ix_special_functions.constructor%20qualifier


 DIP53:

    http://wiki.dlang.org/DIP53

 Ali


Great writeup. Constructor qualifiers are part of the larger discussion 
about collections, but in this case it's a deeper matter.

The code uses non-atomic ++ and -- for the refcount exactly because an 
immutable List cannot be constructed, so it's not shared among threads.


Andrei
Nov 14 2015
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/13/15 6:10 PM, Andrei Alexandrescu wrote:

 I created a simple persistent list with reference counting and custom
 allocation at http://dpaste.dzfl.pl/0981640c2835. It's a good
 illustration of a number of issues. In particular, each cast must be
 properly explained.

 Here's my exegesis:



 * Lines 141-152: I couldn't make tail() work with inout. Generally I'm
 very unhappy about inout. I don't know how to use it. Everything I read
 about it is extremely complicated compared to its power. I wish we
 removed it from the language and replaced it with an understandable idiom.


This seems to work for me:

         inout(List) tail() inout
	{
		assert(root);
		auto n = root.next;
		incRef(n);
		return inout(List)(n, allocator);
	}



 * Lines 161-185: Same problem: inout.


	inout(List) opBinaryRight(string op)(T head) inout
		if (op == "~")
	{
		auto allocator = either(allocator, theAllocator);
         import std.conv : emplace;
         void[] buf = allocator.allocate(Node.sizeof);
         auto n = emplace!(const Node)(buf, head, root, 1);
         incRef(root);
		return inout(List)(n, allocator);
     }


 * Lines 191-199: Same problem: inout.


Should work now that inout is valid on both the others



 * Lines 208-259: I made inout work for getting the range of the list.


inout not necessary here, you can use const. If inout doesn't apply to 
the return value, I believe it devolves to straight const (not sure though).


 Please reply with improvements, ideas, comments, and such. Thanks!


Just note: anything inout is treated like it's const. You can't modify 
ANYTHING inside it. And since nothing casts to or from inout, when you 
return something that's composed via inout, it has to be done in a 
functional way (i.e. constructed and returned).

Here is an updated paste with inout functions:

http://dpaste.dzfl.pl/3fbc786a50c1

Two unrelated notes:

1. I've been writing swift code for the last couple weeks, and goddamn 
if it hasn't ruined my ability to type semicolons at the end of lines
2. I thought there was a way to clone dpastes? I had to make a new paste 
and then copy all the code.

-Steve
Nov 13 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/13/2015 06:36 PM, Steven Schveighoffer wrote:

 On 11/13/15 6:10 PM, Andrei Alexandrescu wrote:

 I created a simple persistent list with reference counting and custom
 allocation at http://dpaste.dzfl.pl/0981640c2835. It's a good
 illustration of a number of issues. In particular, each cast must be
 properly explained.

 Here's my exegesis:



 * Lines 141-152: I couldn't make tail() work with inout. Generally I'm
 very unhappy about inout. I don't know how to use it. Everything I read
 about it is extremely complicated compared to its power. I wish we
 removed it from the language and replaced it with an understandable
 idiom.


 This seems to work for me:

          inout(List) tail() inout
      {
          assert(root);
          auto n = root.next;
          incRef(n);
          return inout(List)(n, allocator);
      }


That doesn't work for me with my unittests, I get:

persistent_list.d(154): Error: None of the overloads of '__ctor' are 
callable using a inout object, candidates are:
persistent_list.d(93): 
persistent_list.List!(immutable(int)).List.this(const(Node*) n, 
IAllocator a)
persistent_list.d(264): Error: template instance 
persistent_list.List!(immutable(int)) error instantiating

154 is the last line in the function above.


Andrei
Nov 14 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/14/15 10:44 AM, Andrei Alexandrescu wrote:


 That doesn't work for me with my unittests, I get:



I'm such an idiot, I depended on dpaste to run the unit test, but forgot 
to check the unit test button.

So technically, my updated version *parses* correctly :)

Looking in more depth...

-Steve
Nov 16 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 11:03 AM, Steven Schveighoffer wrote:

 On 11/14/15 10:44 AM, Andrei Alexandrescu wrote:


 That doesn't work for me with my unittests, I get:



 I'm such an idiot, I depended on dpaste to run the unit test, but forgot
 to check the unit test button.

 So technically, my updated version *parses* correctly :)

 Looking in more depth...


Thanks for letting us know. -- Andrei
Nov 16 2015
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 11:03 AM, Steven Schveighoffer wrote:

 On 11/14/15 10:44 AM, Andrei Alexandrescu wrote:


 That doesn't work for me with my unittests, I get:



 I'm such an idiot, I depended on dpaste to run the unit test, but forgot
 to check the unit test button.

 So technically, my updated version *parses* correctly :)

 Looking in more depth...


I can't get your original code to work, so it's hard for me to figure 
out what is wrong. Using 2.069.1, I have the following error (after 
factoring out `either`, which I'm assuming is a new function):

Stevens-MacBook-Pro:testd steves$ dmd -unittest persistent_list.d
/Users/steves/.dvm/compilers/dmd-2.069.1/osx/bin/../../src/phob
s/std/conv.d(4161): 
Error: template std.conv.emplaceImpl!(const(Node)).emplaceImpl cannot 
deduce function from argument types !()(const(Node), immutable(int), 
const(Node)*, int), candidates are:
/Users/steves/.dvm/compilers/dmd-2.069.1/osx/bin/../../src/phob
s/std/conv.d(3932): 
        std.conv.emplaceImpl!(const(Node)).emplaceImpl()(ref UT chunk)
/Users/steves/.dvm/compilers/dmd-2.069.1/osx/bin/../../src/phob
s/std/conv.d(4037): 
        std.conv.emplaceImpl!(const(Node)).emplaceImpl(Args...)(ref UT 
chunk, auto ref Args args)
/Users/steves/.dvm/compilers/dmd-2.069.1/osx/bin/../../src/phob
s/std/conv.d(5087): 
Error: template instance std.conv.emplace!(const(Node), immutable(int), 
const(Node)*, int) error instantiating
persistent_list.d(169):        instantiated from here: 
emplace!(const(Node), immutable(int), const(Node)*, int)
persistent_list.d(195):        instantiated from here: opBinaryRight!"~"
persistent_list.d(266):        instantiated from here: List!(immutable(int))

However, examining the code, I think you don't even need inout here, 
just a const function will do fine, since nothing on the original is 
changing, and all your nodes are flavored as pointing to const nodes.

I see you have updated the code, and that doesn't work for me either.

I'm afraid without a working example, I can't figure out what's 
*supposed* to work with inout/const.

-Steve
Nov 16 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 12:35 PM, Steven Schveighoffer wrote:


 I'm afraid without a working example, I can't figure out what's
 *supposed* to work with inout/const.


Update, saw your other note. Working now, trying to figure out how to do 
this correctly without any duplication (or wrapping).

-Steve
Nov 16 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 12:42 PM, Steven Schveighoffer wrote:

 On 11/16/15 12:35 PM, Steven Schveighoffer wrote:


 I'm afraid without a working example, I can't figure out what's
 *supposed* to work with inout/const.


 Update, saw your other note. Working now, trying to figure out how to do
 this correctly without any duplication (or wrapping).

 -Steve


OK, I have figured it out.

inout isn't necessary here at all because everything is const internally.

For example, you had this:

         List tail()
	{
		assert(root);
		auto n = root.next;
		incRef(n);
		return List(n, allocator);
	}
	/// ditto
	const(List) tail() const
	{
		assert(root);
		auto n = root.next;
		incRef(n);
		return const(List)(n, allocator);
	}

Which I was able to replace with this:

     List tail() const
     {
         assert(root);
         auto n = root.next;
         incRef(n);
         return List(n, allocator);
     }

In any case, I think the choice between const and inout is confusing, 
and warrants a more in-depth explanation (when should I choose const or 
inout?)

-Steve
Nov 16 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 12:51 PM, Steven Schveighoffer wrote:

      List tail() const


I'd like tail to be qualifier-idempotent, i.e. return const for const 
and non-const for non-const. -- Andrei
Nov 16 2015
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 1:37 PM, Andrei Alexandrescu wrote:

 On 11/16/2015 12:51 PM, Steven Schveighoffer wrote:

      List tail() const


 I'd like tail to be qualifier-idempotent, i.e. return const for const
 and non-const for non-const. -- Andrei


Why? const(int)[] isn't const, why should List!(const(int)) be?

-Steve
Nov 16 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 01:55 PM, Steven Schveighoffer wrote:

 On 11/16/15 1:37 PM, Andrei Alexandrescu wrote:

 On 11/16/2015 12:51 PM, Steven Schveighoffer wrote:

      List tail() const


 I'd like tail to be qualifier-idempotent, i.e. return const for const
 and non-const for non-const. -- Andrei


 Why? const(int)[] isn't const, why should List!(const(int)) be?


I'm keeping an eye toward other containers and also more general use. 
It's a common need. -- Andrei
Nov 16 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 2:37 PM, Andrei Alexandrescu wrote:

 On 11/16/2015 01:55 PM, Steven Schveighoffer wrote:

 On 11/16/15 1:37 PM, Andrei Alexandrescu wrote:

 On 11/16/2015 12:51 PM, Steven Schveighoffer wrote:

      List tail() const


 I'd like tail to be qualifier-idempotent, i.e. return const for const
 and non-const for non-const. -- Andrei


 Why? const(int)[] isn't const, why should List!(const(int)) be?


 I'm keeping an eye toward other containers and also more general use.
 It's a common need. -- Andrei


Anywhere const can work, inout should work as well. The one exception as 
I've described is when you create and build a (im)mutable result, then 
converting it to const. In this case, you have to build it at once. 
Otherwise, the compiler can't tell whether this mutable thing you are 
constructing is safe to cast to inout (and whatever flavor it needs to 
cast to upon exit).

In this case, it appears to work only because of your cast of _allocator 
to mutable whenever you access it via allocator. Other than that, the 
only other member is the node pointer, which is const. Effectively, A 
list's data is always const, so there is no reason to make the struct 
itself const.

-Steve
Nov 16 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 03:38 PM, Steven Schveighoffer wrote:

 On 11/16/15 2:37 PM, Andrei Alexandrescu wrote:

 On 11/16/2015 01:55 PM, Steven Schveighoffer wrote:

 On 11/16/15 1:37 PM, Andrei Alexandrescu wrote:

 On 11/16/2015 12:51 PM, Steven Schveighoffer wrote:

      List tail() const


 I'd like tail to be qualifier-idempotent, i.e. return const for const
 and non-const for non-const. -- Andrei


 Why? const(int)[] isn't const, why should List!(const(int)) be?


 I'm keeping an eye toward other containers and also more general use.
 It's a common need. -- Andrei


 Anywhere const can work, inout should work as well. The one exception as
 I've described is when you create and build a (im)mutable result, then
 converting it to const. In this case, you have to build it at once.
 Otherwise, the compiler can't tell whether this mutable thing you are
 constructing is safe to cast to inout (and whatever flavor it needs to
 cast to upon exit).


I think the main problem is the difficulty of getting from "I want to 
make this method work with mutable and nonconst data" to "I have a 
working solution using inout".

The semantics is complex and difficult. Error messages are horrifying. 
Even explaining code that works is hard. Once a solution works, trying 
to change it in meaningful ways again makes the code not work, and again 
with uninformative error messages. So there's resistance to changing 
working code.

At the same time, we have a wonderful language ready to help with 
features that didn't exist when we introduced inout. Search 
http://dpaste.dzfl.pl/52a3013efe34 for QList - it's restricted properly, 
works very well, and is easy to explain.

Walter and I think inout didn't turn out well. It became a little 
monster mastering a swamp. Template solutions can drain that swamp, make 
the monster disappear, and build nice things on that field.

I think we should slowly marginalize inout - discourage it from new 
code, document and publicize better alternatives, the works.


 In this case, it appears to work only because of your cast of _allocator
 to mutable whenever you access it via allocator. Other than that, the
 only other member is the node pointer, which is const. Effectively, A
 list's data is always const, so there is no reason to make the struct
 itself const.


Plenty of reason. The list may be member in an object. Also, if you 
don't have const List you can't compose List with itself.


Andrei
Nov 16 2015
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, 16 November 2015 at 20:48:49 UTC, Andrei Alexandrescu 
wrote:

 I think we should slowly marginalize inout - discourage it from 
 new code, document and publicize better alternatives, the works.


When you can templatize the function on the type that would 
otherwise be inout, then there really isn't any reason to use 
inout. But what do you do when you're dealing with a member 
function - especially on a class? I don't know of any way to 
templatize a member function on the type of the this 
pointer/reference, but maybe there's a template feature with 
which I'm not familiar enough. But even if there _is_ such a 
feature, it won't work for virtual functions.

So, while I completely agree that it's cleaner to avoid inout 
when it's not needed, from what I can see, there are cases where 
you really don't have an alternative aside from duplicating the 
entire function. So, it does seem like on some level, we're stuck 
using inout, even if we can avoid it in many cases.

- Jonathan M Davis
Nov 16 2015
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/16/2015 10:18 PM, Jonathan M Davis wrote:

 I don't know of any way to templatize a member function on the type of
 the this pointer/reference, but maybe there's a template feature with
 which I'm not familiar enough.


Indeed there is.

class C{
     void foo(this T)(){ pragma(msg, T); }
}

class D: C{}

void main(){
     auto c=new const(C)();
     c.foo();
     auto d=new immutable(D)();
     d.foo();
}


 But even if there _is_ such a feature, it won't work for virtual functions.


Yup.
Nov 16 2015
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, 16 November 2015 at 21:25:52 UTC, Timon Gehr wrote:

 On 11/16/2015 10:18 PM, Jonathan M Davis wrote:

 I don't know of any way to templatize a member function on the 
 type of
 the this pointer/reference, but maybe there's a template 
 feature with
 which I'm not familiar enough.


 Indeed there is.

 class C{
     void foo(this T)(){ pragma(msg, T); }
 }

 class D: C{}

 void main(){
     auto c=new const(C)();
     c.foo();
     auto d=new immutable(D)();
     d.foo();
 }


Cool. That's good to know about. Thanks.

- Jonathan M Davis
Nov 16 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 04:18 PM, Jonathan M Davis wrote:

 When you can templatize the function on the type that would otherwise be
 inout, then there really isn't any reason to use inout. But what do you
 do when you're dealing with a member function - especially on a class? I
 don't know of any way to templatize a member function on the type of the
 this pointer/reference, but maybe there's a template feature with which
 I'm not familiar enough. But even if there _is_ such a feature, it won't
 work for virtual functions.


It does. Write one-liners that forward to the template function, as 
shown in http://dpaste.dzfl.pl/52a3013efe34 (search the page for QList). 
-- Andrei
Nov 16 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, 16 November 2015 at 21:47:07 UTC, Andrei Alexandrescu 
wrote:

 On 11/16/2015 04:18 PM, Jonathan M Davis wrote:

 When you can templatize the function on the type that would 
 otherwise be
 inout, then there really isn't any reason to use inout. But 
 what do you
 do when you're dealing with a member function - especially on 
 a class? I
 don't know of any way to templatize a member function on the 
 type of the
 this pointer/reference, but maybe there's a template feature 
 with which
 I'm not familiar enough. But even if there _is_ such a 
 feature, it won't
 work for virtual functions.


 It does. Write one-liners that forward to the template 
 function, as shown in http://dpaste.dzfl.pl/52a3013efe34 
 (search the page for QList). -- Andrei


Well, that does reduce the code duplication, but you're still 
forced to have up to three separate functions to get each of the 
different return types (even if they are then simply wrapper 
functions). And compare that with simply declaring the same 
function once with its implementation internal to itself. It's 
just that you use inout instead of const. How is that worse?

There are cases where inout doesn't work as well as const does 
due to limitations with inout, but in many (most?) cases, the 
only difference between using const and inout is that you're 
typing const instead of inout. So, if anything, that makes it 
sound like fixing inout so that it works in those other cases 
would be better than avoiding it in favor of splitting out the 
implementation into a separate function and having multiple 
wrapper functions in the API.

- Jonathan M Davis
Nov 16 2015
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 5:02 PM, Jonathan M Davis wrote:

 On Monday, 16 November 2015 at 21:47:07 UTC, Andrei Alexandrescu wrote:

 On 11/16/2015 04:18 PM, Jonathan M Davis wrote:

 When you can templatize the function on the type that would otherwise be
 inout, then there really isn't any reason to use inout. But what do you
 do when you're dealing with a member function - especially on a class? I
 don't know of any way to templatize a member function on the type of the
 this pointer/reference, but maybe there's a template feature with which
 I'm not familiar enough. But even if there _is_ such a feature, it won't
 work for virtual functions.


 It does. Write one-liners that forward to the template function, as
 shown in http://dpaste.dzfl.pl/52a3013efe34 (search the page for
 QList). -- Andrei


 Well, that does reduce the code duplication, but you're still forced to
 have up to three separate functions to get each of the different return
 types (even if they are then simply wrapper functions). And compare that
 with simply declaring the same function once with its implementation
 internal to itself. It's just that you use inout instead of const. How
 is that worse?


I'll reiterate what I said elsewhere: inout is better, safer, and easier 
to maintain than the template solution.

Example:

static QList cons(QList)(T head, auto ref QList lst)
     if (is(Unqual!QList == List))

Tell me how cons guarantees not to modify lst? Is it convention or 
compiler guarantees? find the bug:

static QList cons(QList)(T head, auto ref QList lst)
     if (is(Unqual!QList == List))
{
List result;
result._allocator = either(lst.allocator, theAllocator);
import std.conv : emplace;
void[] buf = result.allocator.allocate(Node.sizeof);
auto n = emplace!(const Node)(buf, head, lst.root, 1);
incRef(lst.root);
result.root = n;
static if(!is(QList == const)) lst.root = lst.root.next;
return result;
}

The point of const is to provide a mechanism to those reading the 
signature to say "this function will NOT change the parameter, and the 
compiler guarantees it." The point of inout is the same, but allows 
returning a portion of the parameters without resorting to casts or 
wrappers.

-Steve
Nov 16 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 05:30 PM, Steven Schveighoffer wrote:

 I'll reiterate what I said elsewhere: inout is better, safer, and easier
 to maintain than the template solution.


Do you have a working solution in dpaste? No change to the return types 
please. -- Andrei
Nov 16 2015
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 5:35 PM, Andrei Alexandrescu wrote:

 On 11/16/2015 05:30 PM, Steven Schveighoffer wrote:

 I'll reiterate what I said elsewhere: inout is better, safer, and easier
 to maintain than the template solution.


 Do you have a working solution in dpaste? No change to the return types
 please. -- Andrei


Ah, where it breaks down is emplace uses an internal struct with a T, 
which is inout(const(Node)*).

So you *are* hitting one of the limitations of inout, one that Dmitry 
brought up. I stand corrected.

I think it can be fixed, we need to make structs that contain inout 
member variables legal as long as they only exist on inout function 
stacks. It may be possible to fix emplace for inout by changing the ctor 
of the internal struct to inout instead of typing T as inout, but I'm 
not sure.

In this case, in order to work around, you have to cast when you use 
emplace, somewhat defeating the safety of emplace :(

http://dpaste.dzfl.pl/182e2ac5da2d

The only other weird part is where you see inout(const(Node)*) in the 
fixed ctor. This is because it's a different type than inout(Node*), 
it's like const(immutable(Node)*), the pointer itself is const, but the 
data it points at is still immutable.

-Steve
Nov 16 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 05:02 PM, Jonathan M Davis wrote:

 It's just that you use inout instead of const. How is that worse?


The short answer is my perception is inout is too complicated for what 
it does. -- Andrei
Nov 16 2015
parent reply deadalnix <deadalnix gmail.com> writes:
On Monday, 16 November 2015 at 22:30:55 UTC, Andrei Alexandrescu 
wrote:

 On 11/16/2015 05:02 PM, Jonathan M Davis wrote:

 It's just that you use inout instead of const. How is that 
 worse?


 The short answer is my perception is inout is too complicated 
 for what it does. -- Andrei


I'm happy to read this. inout has the wrong cost/complexity 
ratio. It doesn't solve the problem generally (one want to  
return type depending on argument qualifier in general, not only 
for type qualifiers) while having a high complexity.
Nov 16 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 6:56 PM, deadalnix wrote:

 On Monday, 16 November 2015 at 22:30:55 UTC, Andrei Alexandrescu wrote:

 On 11/16/2015 05:02 PM, Jonathan M Davis wrote:

 It's just that you use inout instead of const. How is that worse?


 The short answer is my perception is inout is too complicated for what
 it does. -- Andrei


 I'm happy to read this. inout has the wrong cost/complexity ratio. It
 doesn't solve the problem generally (one want to return type depending
 on argument qualifier in general, not only for type qualifiers) while
 having a high complexity.


The problem it solves is to provide a mechanism that allows one to 
safely apply the same qualifiers to the return type, but have the inputs 
be constant *throughout the function*.

A templated function doesn't do this, you can have conditional code, or 
unchecked method calls that can modify the data when possible.

Of course, if this isn't important, then the template solution is 
usable. My take is that whenever you use inout is when you would 
normally use const, but const doesn't allow what you need. If your 
function doesn't need const inside the function, then you shouldn't use 
inout.

To me, it feels like inout is simple, but the implementation has warts 
that make it seem inconsistent. There is also the issue that nested 
inout is super-confusing, because now you have layers of inout, each 
layer meaning possibly something different. If we could somehow fix the 
nested part (and allow types with inout members inside there), I think 
inout would be less intimidating.

-Steve
Nov 16 2015
next sibling parent reply Meta <jared771 gmail.com> writes:
On Tuesday, 17 November 2015 at 00:30:39 UTC, Steven 
Schveighoffer wrote:

 The problem it solves is to provide a mechanism that allows one 
 to safely apply the same qualifiers to the return type, but 
 have the inputs be constant *throughout the function*.

 A templated function doesn't do this, you can have conditional 
 code, or unchecked method calls that can modify the data when 
 possible.

 Of course, if this isn't important, then the template solution 
 is usable. My take is that whenever you use inout is when you 
 would normally use const, but const doesn't allow what you 
 need. If your function doesn't need const inside the function, 
 then you shouldn't use inout.

 To me, it feels like inout is simple, but the implementation 
 has warts that make it seem inconsistent. There is also the 
 issue that nested inout is super-confusing, because now you 
 have layers of inout, each layer meaning possibly something 
 different. If we could somehow fix the nested part (and allow 
 types with inout members inside there), I think inout would be 
 less intimidating.

 -Steve


I don't mean to derail this thread, but I also am not really 
crazy about inout in its current form. Its transitive nature is 
one issue (though that can't be changed due to const and 
immutable also being transitive), but also the fact that inout is 
basically a fourth qualifier, which causes a lot of pain when 
you're wrapping other types.

For example, calling opEquals on a wrapped struct inside the 
opEquals of the wrapper struct (which is marked as inout) when 
the wrapped struct does not also define an inout opEquals, will 
not call the mutable opEquals of the wrapped struct. It *will 
not* compile unless the wrapped struct also defines an inout 
opEquals, no matter the constness of the wrapper or the wrappee. 
Basically, wrapper types cannot with inout.

http://stackoverflow.com/questions/31516713/escaping-from-inout-hell
Nov 16 2015
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 8:11 PM, Meta wrote:

 On Tuesday, 17 November 2015 at 00:30:39 UTC, Steven Schveighoffer wrote:

 The problem it solves is to provide a mechanism that allows one to
 safely apply the same qualifiers to the return type, but have the
 inputs be constant *throughout the function*.

 A templated function doesn't do this, you can have conditional code,
 or unchecked method calls that can modify the data when possible.

 Of course, if this isn't important, then the template solution is
 usable. My take is that whenever you use inout is when you would
 normally use const, but const doesn't allow what you need. If your
 function doesn't need const inside the function, then you shouldn't
 use inout.

 To me, it feels like inout is simple, but the implementation has warts
 that make it seem inconsistent. There is also the issue that nested
 inout is super-confusing, because now you have layers of inout, each
 layer meaning possibly something different. If we could somehow fix
 the nested part (and allow types with inout members inside there), I
 think inout would be less intimidating.

 -Steve


 I don't mean to derail this thread, but I also am not really crazy about
 inout in its current form. Its transitive nature is one issue (though
 that can't be changed due to const and immutable also being transitive),
 but also the fact that inout is basically a fourth qualifier, which
 causes a lot of pain when you're wrapping other types.

 For example, calling opEquals on a wrapped struct inside the opEquals of
 the wrapper struct (which is marked as inout) when the wrapped struct
 does not also define an inout opEquals, will not call the mutable
 opEquals of the wrapped struct. It *will not* compile unless the wrapped
 struct also defines an inout opEquals, no matter the constness of the
 wrapper or the wrappee. Basically, wrapper types cannot with inout.

 http://stackoverflow.com/questions/31516713/escaping-from-inout-hell


I think it's quite clear that inout in its current form is a point of 
huge confusion. I want to work to fix this perception (and fix the 
broken corners of the implementation).

What I would ask is for those who at the moment dislike it keep an open 
mind, and hold back on your pitchforks. I need to prepare a suitable 
defense, and it's difficult to shake off the "confusing and complex" 
albatross without having sufficient time to create something that is 
easy to understand/explain for something that is conceptually simple, 
but requires a complex proof.

What I am afraid of is that someone makes a decision that something is 
bad, and by the time a good defense, or workable proposal is mounted, 
the answer is "we already discussed that, it's bad. Let's move on."

At least with this, we have a feature that is part of the language, so 
is unlikely to go away. But I'd hate to see a mob of PR requests that 
remove inout from all of phobos/druntime before I can counter this.

I think inout is worth saving, it needs a few tweaks and a good explanation.

-Steve
Nov 16 2015
next sibling parent Joseph Cassman <jc7919 outlook.com> writes:
On Tuesday, 17 November 2015 at 01:49:05 UTC, Steven 
Schveighoffer wrote:
[...]

 I think inout is worth saving, it needs a few tweaks and a good 
 explanation.

 -Steve


Sounds interesting. Might your ideas help to fix the difficulties 
inout has with composability? That would be excellent.

Joseph
Nov 16 2015
prev sibling parent reply Meta <jared771 gmail.com> writes:
On Tuesday, 17 November 2015 at 01:49:05 UTC, Steven 
Schveighoffer wrote:

 I think it's quite clear that inout in its current form is a 
 point of huge confusion. I want to work to fix this perception 
 (and fix the broken corners of the implementation).

 What I would ask is for those who at the moment dislike it keep 
 an open mind, and hold back on your pitchforks. I need to 
 prepare a suitable defense, and it's difficult to shake off the 
 "confusing and complex" albatross without having sufficient 
 time to create something that is easy to understand/explain for 
 something that is conceptually simple, but requires a complex 
 proof.

 What I am afraid of is that someone makes a decision that 
 something is bad, and by the time a good defense, or workable 
 proposal is mounted, the answer is "we already discussed that, 
 it's bad. Let's move on."

 At least with this, we have a feature that is part of the 
 language, so is unlikely to go away. But I'd hate to see a mob 
 of PR requests that remove inout from all of phobos/druntime 
 before I can counter this.

 I think inout is worth saving, it needs a few tweaks and a good 
 explanation.

 -Steve


Regarding my question on StackOverflow, I understand that I had 
an inaccurate picture of how inout works, which was causing my 
problem. These are also problems with const and immutable to a 
degree. However, inout is like a fourth qualifier that you have 
to deal with that is separate from const and immutable, due to 
how it currently works. In that light, I still don't think it 
pulls its weight. What user will have the presence of mind to 
define their Foobar type with an inout/const/immutable toString 
function? Almost none, and so Nullable!Foobar.opEquals cannot be 
inout. I first encountered this problem trying to get 
Nullable.toString to work with inout, and couldn't. That's my 
main gripe with inout.
Nov 16 2015
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 9:00 PM, Meta wrote:

 On Tuesday, 17 November 2015 at 01:49:05 UTC, Steven Schveighoffer wrote:

 I think it's quite clear that inout in its current form is a point of
 huge confusion. I want to work to fix this perception (and fix the
 broken corners of the implementation).

 What I would ask is for those who at the moment dislike it keep an
 open mind, and hold back on your pitchforks. I need to prepare a
 suitable defense, and it's difficult to shake off the "confusing and
 complex" albatross without having sufficient time to create something
 that is easy to understand/explain for something that is conceptually
 simple, but requires a complex proof.

 What I am afraid of is that someone makes a decision that something is
 bad, and by the time a good defense, or workable proposal is mounted,
 the answer is "we already discussed that, it's bad. Let's move on."

 At least with this, we have a feature that is part of the language, so
 is unlikely to go away. But I'd hate to see a mob of PR requests that
 remove inout from all of phobos/druntime before I can counter this.

 I think inout is worth saving, it needs a few tweaks and a good
 explanation.


 Regarding my question on StackOverflow, I understand that I had an
 inaccurate picture of how inout works, which was causing my problem.
 These are also problems with const and immutable to a degree.


I can understand the confusion.

However, here is the truth: you only need to define opEquals for const 
or mutable. You don't need both (if your wrapped type defines both, then 
the const one can be called in both cases), and you don't need an inout 
version. Here is why: inout is simply *equivalent to const* (but without 
the implicit casting) when there is no inout on the return type. 
Originally this was flagged as an error, but because of templates and 
IFTI, it made writing template functions much harder.

But here is a working system that has no inout:

struct Wrapper(T)
{
     T t;

     static if(is(typeof(const(T).init == const(T).init)))
     {
         bool opEquals(const(Wrapper) other) const
         {
             return t == other.t;
         }
         bool opEquals(const(T) val) const
         {
             return t == val;
         }
     }
     else
     {
         bool opEquals(Wrapper other)
         {
             return t == other.t;
         }
         bool opEquals(T val)
         {
             return t == val;
         }
     }
}

struct Test
{
     bool opEquals(Test t)
     {
         return true;
     }
}

struct Test2
{
     bool opEquals(inout(Test2) t) inout
     {
         return true;
     }
}

struct Test3
{
     bool opEquals(const(Test3) t) const
     {
         return true;
     }
}

void foo(T)()
{
     Wrapper!T a, b;
     assert(a == b);
     assert(a == T());
}

void main()
{
     foo!Test();
     foo!Test2();
     foo!Test3();
}

This doesn't solve the case that has only a mutable and immutable 
opEquals, and no const version, but you get the idea.


 However,
 inout is like a fourth qualifier that you have to deal with that is
 separate from const and immutable, due to how it currently works. In
 that light, I still don't think it pulls its weight. What user will have
 the presence of mind to define their Foobar type with an
 inout/const/immutable toString function? Almost none, and so
 Nullable!Foobar.opEquals cannot be inout.


In almost all cases I've come across, inout isn't another thing that 
needs handling. It's simply an alternative to const (when applicable). 
In cases where it is applicable, you write MUCH LESS code. Where it 
breaks down is composition (i.e. creating a type with an inout member) 
and nested functions.


 I first encountered this
 problem trying to get Nullable.toString to work with inout, and
 couldn't. That's my main gripe with inout.


This may have hit one of the warts of inout.

-Steve
Nov 16 2015
prev sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 8:11 PM, Meta wrote:


 http://stackoverflow.com/questions/31516713/escaping-from-inout-hell


BTW, I cannot post there, but this statement in the second answer is wrong:

"Just remove inout. The compiler infers attributes like const 
automatically for templates"

The compiler does NOT infer const automatically.

Someone should correct that for those looking at these things.

-Steve
Nov 17 2015
prev sibling parent reply deadalnix <deadalnix gmail.com> writes:
On Tuesday, 17 November 2015 at 00:30:39 UTC, Steven 
Schveighoffer wrote:

 On 11/16/15 6:56 PM, deadalnix wrote:

 On Monday, 16 November 2015 at 22:30:55 UTC, Andrei 
 Alexandrescu wrote:

 On 11/16/2015 05:02 PM, Jonathan M Davis wrote:

 It's just that you use inout instead of const. How is that 
 worse?


 The short answer is my perception is inout is too complicated 
 for what
 it does. -- Andrei


 I'm happy to read this. inout has the wrong cost/complexity 
 ratio. It
 doesn't solve the problem generally (one want to return type 
 depending
 on argument qualifier in general, not only for type 
 qualifiers) while
 having a high complexity.


 The problem it solves is to provide a mechanism that allows one 
 to safely apply the same qualifiers to the return type, but 
 have the inputs be constant *throughout the function*.

 A templated function doesn't do this, you can have conditional 
 code, or unchecked method calls that can modify the data when 
 possible.

 Of course, if this isn't important, then the template solution 
 is usable. My take is that whenever you use inout is when you 
 would normally use const, but const doesn't allow what you 
 need. If your function doesn't need const inside the function, 
 then you shouldn't use inout.

 To me, it feels like inout is simple, but the implementation 
 has warts that make it seem inconsistent. There is also the 
 issue that nested inout is super-confusing, because now you 
 have layers of inout, each layer meaning possibly something 
 different. If we could somehow fix the nested part (and allow 
 types with inout members inside there), I think inout would be 
 less intimidating.

 -Steve


Here is, IMO, the point you are missing.

There many qualifier you'd like to have depend on other 
qualifiers. For instance :

void doSomeThingAndCallBack(maybe_pure void function() callback) 
pure_if_maybe_pure_argument_is_pure {
     callback();
}

You'll note that this is the same problem as inout solves. Thing 
is inout is complex, but only solve a small subset of the problem.

Thus, the power/complexity ratio is not good.

Also, yes, the implementation is B0rken :) Still it has gotten 
much better over time (or I learned the hard way to stay into the 
patterns that works ?).
Nov 16 2015
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 8:21 PM, deadalnix wrote:

 On Tuesday, 17 November 2015 at 00:30:39 UTC, Steven Schveighoffer wrote:

 On 11/16/15 6:56 PM, deadalnix wrote:

 On Monday, 16 November 2015 at 22:30:55 UTC, Andrei Alexandrescu wrote:

 On 11/16/2015 05:02 PM, Jonathan M Davis wrote:

 It's just that you use inout instead of const. How is that worse?


 The short answer is my perception is inout is too complicated for what
 it does. -- Andrei


 I'm happy to read this. inout has the wrong cost/complexity ratio. It
 doesn't solve the problem generally (one want to return type depending
 on argument qualifier in general, not only for type qualifiers) while
 having a high complexity.


 The problem it solves is to provide a mechanism that allows one to
 safely apply the same qualifiers to the return type, but have the
 inputs be constant *throughout the function*.

 A templated function doesn't do this, you can have conditional code,
 or unchecked method calls that can modify the data when possible.

 Of course, if this isn't important, then the template solution is
 usable. My take is that whenever you use inout is when you would
 normally use const, but const doesn't allow what you need. If your
 function doesn't need const inside the function, then you shouldn't
 use inout.

 To me, it feels like inout is simple, but the implementation has warts
 that make it seem inconsistent. There is also the issue that nested
 inout is super-confusing, because now you have layers of inout, each
 layer meaning possibly something different. If we could somehow fix
 the nested part (and allow types with inout members inside there), I
 think inout would be less intimidating.


 Here is, IMO, the point you are missing.

 There many qualifier you'd like to have depend on other qualifiers. For
 instance :

 void doSomeThingAndCallBack(maybe_pure void function() callback)
 pure_if_maybe_pure_argument_is_pure {
      callback();
 }


This already works with templates. If all you care about is writing a 
function that has the *ability* to take any kind of input, then 
templates are perfect for that.

What inout solves above templates (and note, you can combine inout AND 
templates), is that during the function call, the parameter is not 
modified -- guaranteed by the compiler (as much as it can). Templates 
cannot offer that. To me the maybe_pure solution doesn't even come close 
to inout's utility (what does it guarantee beside being able to take 
different types of parameters?).

For those who care about const or try to use const (and immutable) to 
provide API guarantees on parameters, it becomes unwieldy to both 
specify "yes! I can take any qualified type of parameter" and "no! I 
promise I won't modify them." Const fills this void, but has the the 
issue of blindly coloring everything const, locking up all your data for 
things like function chaining. Inout is supposed to fix this one 
problem, and should be a seamless replacement for const in those cases. 
It obviously is not.


 Thus, the power/complexity ratio is not good.


inout is for one specific thing, I see it to be unrelated to templates. 
It's more of an extension of const. The complexity, IMO, is not 
necessarily huge (perhaps in the current implementation, I'm not sure), 
but the consistency is terrible. There are things you just should be 
able to do, and the compiler won't do them. Inevitably, the templates 
people write end up trying to do these things (because they are 
logically correct), and the compiler spits out cryptic "cannot call this 
function" errors. These can be difficult to figure out.


 Also, yes, the implementation is B0rken :) Still it has gotten much
 better over time (or I learned the hard way to stay into the patterns
 that works ?).


It has definitely gotten better over time. It used to be that if you 
used any kind of template with an inout parameter, it wouldn't compile.

-Steve
Nov 16 2015
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 3:48 PM, Andrei Alexandrescu wrote:


 I think the main problem is the difficulty of getting from "I want to
 make this method work with mutable and nonconst data" to "I have a
 working solution using inout".


Again, it's not that hard. I have had little trouble with using it 
instead of const where it is appropriate. There are a couple rough 
edges, but you haven't hit them yet.


 The semantics is complex and difficult. Error messages are horrifying.
 Even explaining code that works is hard. Once a solution works, trying
 to change it in meaningful ways again makes the code not work, and again
 with uninformative error messages. So there's resistance to changing
 working code.


I just did the naive thing and slapped inout on your functions. This is 
what I got:

persistent_list2.d(146): Error: cannot implicitly convert expression (( 
List!(immutable(int)) __slList1681 = List(null, null);
  , __slList1681).this(n, this.allocator())) of type 
List!(immutable(int)) to inout(List!(immutable(int)))

WTF!

This is not how it used to be. What the hell is __slList1681? And what 
is List(null, null)?

This has to be some sort of lowering that was added to the compiler, I 
have never seen such horrible messages for inout. How it should look:

Error: cannot implicitly convert expression List(n, allocator) of type 
List!(immutable(int)) to inout(List!(immutable(int)))

Note, this is not an inout problem. If I put immutable(List) as the 
return type, I get:

persistent_list2.d(146): Error: cannot implicitly convert expression (( 
List!(immutable(int)) __slList1681 = List(null, null);
  , __slList1681).this(n, this.allocator())) of type 
List!(immutable(int)) to immutable(List!(immutable(int)))

We can and should fix this. I'll file an issue if none has been filed.


 At the same time, we have a wonderful language ready to help with
 features that didn't exist when we introduced inout. Search
 http://dpaste.dzfl.pl/52a3013efe34 for QList - it's restricted properly,
 works very well, and is easy to explain.


Actually, it's not easier to explain or maintain, and the solution 
existed before inout was introduced (in fact one of the reasons *to* use 
inout was to avoid QList-like solutions).

Example:

static QList cons(QList)(T head, auto ref QList lst)
     if (is(Unqual!QList == List))

Tell me how cons guarantees not to modify lst? Is it convention or 
compiler guarantees? find the bug:

static QList cons(QList)(T head, auto ref QList lst)
     if (is(Unqual!QList == List))
{
List result;
result._allocator = either(lst.allocator, theAllocator);
import std.conv : emplace;
void[] buf = result.allocator.allocate(Node.sizeof);
auto n = emplace!(const Node)(buf, head, lst.root, 1);
incRef(lst.root);
result.root = n;
static if(!is(QList == const)) lst.root = lst.root.next;
return result;
}

The point of const is to provide a mechanism to those reading the 
signature to say "this function will NOT change the parameter, and the 
compiler guarantees it."

I remember reading originally why Walter put const into the language -- 
because C++ developers who used const extensively to provide guarantees 
simply wouldn't use D if it didn't provide a mechanism to do this. I 
don't recall the exact wording, but I'm sure it's somewhere in the ng.

The point of inout was to provide what const does, but allow you to hook 
the output const flavor to the input const flavor. That's all.


 Walter and I think inout didn't turn out well. It became a little
 monster mastering a swamp. Template solutions can drain that swamp, make
 the monster disappear, and build nice things on that field.


I disagree, and appeals to authority is not very convincing, no matter 
how colorful. I think inout works great for what it's good at. It has 
some finishing to do, but the concept is sound and works fine. It's a 
perfect fit for containers in general. In this particular case it's not 
necessary.

We absolutely should fix the error messages, they are not very helpful.


 I think we should slowly marginalize inout - discourage it from new
 code, document and publicize better alternatives, the works.


Because we have a poor error message? I can assure you this is not 
endemic to inout.


 In this case, it appears to work only because of your cast of _allocator
 to mutable whenever you access it via allocator. Other than that, the
 only other member is the node pointer, which is const. Effectively, A
 list's data is always const, so there is no reason to make the struct
 itself const.


 Plenty of reason. The list may be member in an object. Also, if you
 don't have const List you can't compose List with itself.


Huh? Mutable List casts to const List just fine. If I always return a 
mutable List from a composing operation, then it works for const List as 
well (both as the receiver of the return value and as the parameter).

What I meant to say is that a const(List) isn't particularly needed to 
guard the List's data. That is already const.

-Steve
Nov 16 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 04:36 PM, Steven Schveighoffer wrote:

 We can and should fix this. I'll file an issue if none has been filed.


That's great! -- Andrei
Nov 16 2015
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 4:49 PM, Andrei Alexandrescu wrote:

 On 11/16/2015 04:36 PM, Steven Schveighoffer wrote:

 We can and should fix this. I'll file an issue if none has been filed.


 That's great! -- Andrei


https://issues.dlang.org/show_bug.cgi?id=15347

Note that the trigger is the ctor and dtor of the struct. Each adds 
worse layers of error message horror :)

-Steve
Nov 16 2015
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, 16 November 2015 at 21:36:41 UTC, Steven Schveighoffer 
wrote:

 I just did the naive thing and slapped inout on your functions. 
 This is what I got:

 persistent_list2.d(146): Error: cannot implicitly convert 
 expression (( List!(immutable(int)) __slList1681 = List(null, 
 null);
  , __slList1681).this(n, this.allocator())) of type 
 List!(immutable(int)) to inout(List!(immutable(int)))

 WTF!


Wow is that hideous. I don't recall ever seeing error messages 
that obtuse.


 We can and should fix this. I'll file an issue if none has been 
 filed.


Please do.

- Jonathan M Davis
Nov 16 2015
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/16/2015 07:37 PM, Andrei Alexandrescu wrote:

 On 11/16/2015 12:51 PM, Steven Schveighoffer wrote:

      List tail() const


 I'd like tail to be qualifier-idempotent, i.e. return const for const
 and non-const for non-const. -- Andrei


"Qualifier-idempotent" would rather mean that taking the tail once 
results in the same qualifier as taking it twice.

https://en.wikipedia.org/wiki/Idempotence
Nov 16 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 02:07 PM, Timon Gehr wrote:

 On 11/16/2015 07:37 PM, Andrei Alexandrescu wrote:

 On 11/16/2015 12:51 PM, Steven Schveighoffer wrote:

      List tail() const


 I'd like tail to be qualifier-idempotent, i.e. return const for const
 and non-const for non-const. -- Andrei


 "Qualifier-idempotent" would rather mean that taking the tail once
 results in the same qualifier as taking it twice.

 https://en.wikipedia.org/wiki/Idempotence


Jesus. Fine. -- Andrei
Nov 16 2015
prev sibling parent Daniel N <ufo orbiting.us> writes:
On Monday, 16 November 2015 at 18:37:18 UTC, Andrei Alexandrescu 
wrote:

 On 11/16/2015 12:51 PM, Steven Schveighoffer wrote:

      List tail() const


 I'd like tail to be qualifier-idempotent, i.e. return const for 
 const and non-const for non-const. -- Andrei


I don't have a compiler at hand right now, but doesn't this work?

auto tail(this U)() const
{
   assert(root);
   auto n = root.next;
   incRef(n);
   return U(n, allocator);
}
Nov 16 2015
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/14/2015 12:10 AM, Andrei Alexandrescu wrote:

 * Lines 6: By construction the list doesn't work with mutable objects.


=(
Nov 13 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/13/2015 06:41 PM, Timon Gehr wrote:

 On 11/14/2015 12:10 AM, Andrei Alexandrescu wrote:

 * Lines 6: By construction the list doesn't work with mutable objects.


 =(


I've decided persistent lists with mutable elements just too weird to 
endorse. Lisp allows them but every time it mentions that it very 
strongly advises against it.

Other container semantics are better, I think, for mutable elements. 
Let's leave persistent lists have their nice value semantics.


Andrei
Nov 14 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/14/2015 04:45 PM, Andrei Alexandrescu wrote:

 On 11/13/2015 06:41 PM, Timon Gehr wrote:

 On 11/14/2015 12:10 AM, Andrei Alexandrescu wrote:

 * Lines 6: By construction the list doesn't work with mutable objects.


 =(


 I've decided persistent lists with mutable elements just too weird to
 endorse.


Not /enforcing/ _transitive_ immutability is not the same as endorsing 
arbitrary mutation patterns as reasonable.


 Lisp allows them but every time it mentions that it very
 strongly advises against it.
 ...


This is just not true. E.g. lazy thunks are considered fine.


 Other container semantics are better, I think, for mutable elements.


Right, because e.g. whether the elements are reference counted or traced 
should totally completely change the required container semantics for 
the problem at hand! This does not make any sense, unless you are saying 
that nobody should actually use the persistent containers, in which case 
it seems like a waste of time to concentrate efforts on them.

You have not provided a technical argument, so I am going to assume you 
have an irrational fear of bad PR. Forcing transitive immutable on 
people who want persistent container semantics is ultimately a very poor 
choice both from a technical and a PR perspective.


 Let's leave persistent lists have their nice value semantics.
 ...


It does not make sense to conflate transitive immutability and value 
semantics, unless one considers it reasonable to make all struct fields 
transitively tail-immutable.
Nov 14 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/14/2015 03:36 PM, Timon Gehr wrote:

 Right, because e.g. whether the elements are reference counted or traced
 should totally completely change the required container semantics for
 the problem at hand! This does not make any sense, unless you are saying
 that nobody should actually use the persistent containers, in which case
 it seems like a waste of time to concentrate efforts on them.


I'm just as weary of persistent containers of mutable elements using GC. 
It doesn't make a difference.


 You have not provided a technical argument, so I am going to assume you
 have an irrational fear of bad PR. Forcing transitive immutable on
 people who want persistent container semantics is ultimately a very poor
 choice both from a technical and a PR perspective.


The English language has a word I like a lot: "unassuming". I'm not sure 
about its etymology, but a nice theory is "a person who doesn't assume 
bad things about others".

I'm glad to hear about various pros and cons regarding these containers. 
Slinging this kind of stuff is unlikely to further the dialog.


Andrei
Nov 14 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/14/2015 09:42 PM, Andrei Alexandrescu wrote:

 On 11/14/2015 03:36 PM, Timon Gehr wrote:

 Right, because e.g. whether the elements are reference counted or traced
 should totally completely change the required container semantics for
 the problem at hand! This does not make any sense, unless you are saying
 that nobody should actually use the persistent containers, in which case
 it seems like a waste of time to concentrate efforts on them.


 I'm just as weary of persistent containers of mutable elements using GC.
 It doesn't make a difference.
 ...


There must be a misunderstanding here. Fully mutable vs fully transitive 
immutable is a false dichotomy. I'm arguing for allowing at least the 
obviously valid use cases, you are arguing for disallowing at least the 
obviously wrong use cases.


 You have not provided a technical argument, so I am going to assume you
 have an irrational fear of bad PR. Forcing transitive immutable on
 people who want persistent container semantics is ultimately a very poor
 choice both from a technical and a PR perspective.


 The English language has a word I like a lot: "unassuming". I'm not sure
 about its etymology, but a nice theory is "a person who doesn't assume
 bad things about others".
 ...


Assuming this was the definition, your well-meaning intention cannot be 
to say that you assume that I am not entirely unassuming unless you 
consider it a good thing not to be unassuming. Anyway, I don't consider 
appeal to the assumed etymology of words to be a sound principle of 
reasoning.

In case that was unclear, I clearly did not mean to _assert_ that you in 
fact have this fear, as I have no way to know. I was just trying to 
probe what your reasoning was built on and possibly argue against it. 
Furthermore, it wouldn't necessarily be a bad thing.


 I'm glad to hear about various pros and cons regarding these  containers.


We have had the discussion you are asking for before, and you have 
decided to ignore it, with the justification that this was how you 
decided and a vague appeal to emotion. I usually don't operate under the 
assumption that identical experiments lead to different outcomes without 
a good reason.


 Slinging this kind of stuff


(I'm not slinging any kind of stuff.)


 is unlikely to further the dialog.
 ...


Maybe not, but what is? It can't be laying down a well-reasoned 
argument, because as recent history shows it will just be ignored 
without a reasonable justification.

I guess one other good way to proceed would be to just not have the 
dialog for now and instead wait until people who are actually trying to 
use the containers start complaining in blog posts and on reddit.

Feel free to voice any better suggestions you may have.
Nov 14 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/14/2015 05:04 PM, Timon Gehr wrote:

 We have had the discussion you are asking for before, and you have
 decided to ignore it, with the justification that this was how you
 decided and a vague appeal to emotion. I usually don't operate under
 the assumption that identical experiments lead to different outcomes
 without a good reason.


Yah, of course I remember that discussion. Thing is I remained
unconvinced after said discussion.

There's no technical argument being made here. It's a judgment call.

Clearly allowing List!int with the same codebase as
http://dpaste.dzfl.pl/0981640c2835 is possible, and it would allow a
number of additional uses at the cost of somewhat murky semantics (that
list is not a value and not a reference; defining other containers with
similar semantics is tricky).

But there's a distinct possibility: List!(immutable int) is
indistinguishable from a value type - each value is independent from all
others, up to taking address of elements in the list.

So what we could do is define List!int to implement value semantics with
a completely different implementation - COW. That's a very appealing
equation for the user: "List!T is always a value regardless of T."
Optimizations apply depending on T, but that's transparent and the user
doesn't need to care. A List!T is a value. Boom. Done.

Per what you propose, we'd have "List!T is a Lisp-style list. It has
cons cells and atoms, and cons(head, list) creates a new list that
shares its tail with list." etc.

You seem to assert there's no contest, and anyone choosing (1) over (2)
is seriously incompetent. I seem to think there is a real choice there,
and I want to keep it open for the time being. Is this reasonable?


 Maybe not, but what is? It can't be laying down a well-reasoned
 argument, because as recent history shows it will just be ignored
 without a reasonable justification.

 I guess one other good way to proceed would be to just not have the
 dialog for now and instead wait until people who are actually trying
 to use the containers start complaining in blog posts and on reddit.

 Feel free to voice any better suggestions you may have.


One interesting problem Walter and I have as leaders of this community 
is to attract within the core circle people who are literally better 
than ourselves. People whom we can trust with using good judgment in 
complex situation and can lead themselves entire features and parts of 
the language (such as compiler-supported RC etc).

Amaury and you (Timon) may as well be the smartest people hanging out in 
this forum. You both are also very generous with your time. I can't talk 
for Walter, but for all I can tell you two are better than I'll ever be 
at all metrics that matter to language design. The challenge, then, 
becomes in convincing you to put that good expertise and good will 
toward something positive; because, to be blunt, a large chunk of your 
and Amaury's energy is dedicated to picking fights and proving just what 
chowderheads Walter and I are for not doing as you say.

I'm very happy to admit - you're a whole lot better than myself. So 
let's do something constructive.


Andrei
Nov 14 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/14/2015 11:37 PM, Andrei Alexandrescu wrote:

 On 11/14/2015 05:04 PM, Timon Gehr wrote:

 We have had the discussion you are asking for before, and you have
 decided to ignore it, with the justification that this was how you
 decided and a vague appeal to emotion. I usually don't operate under
 the assumption that identical experiments lead to different outcomes
 without a good reason.


 Yah, of course I remember that discussion. Thing is I remained
 unconvinced after said discussion.

 There's no technical argument being made here. It's a judgment call.

 Clearly allowing List!int with the same codebase as
 http://dpaste.dzfl.pl/0981640c2835 is possible, and it would allow a
 number of additional uses at the cost of somewhat murky semantics (that
 list is not a value and not a reference; defining other containers with
 similar semantics is tricky).

 But there's a distinct possibility: List!(immutable int) is
 indistinguishable from a value type - each value is independent from all
 others, up to taking address of elements in the list.

 So what we could do is define List!int to implement value semantics with
 a completely different implementation - COW.


How to implement COW without support for writing?


 That's a very appealing
 equation for the user: "List!T is always a value regardless of T."
 Optimizations apply depending on T, but that's transparent and the user
 doesn't need to care. A List!T is a value. Boom. Done.
 ...


It is awesome if List!T acts like a value type. More precisely, like a 
struct. That in particular means its elements should not always need to 
be transitively immutable.


 Per what you propose, we'd have "List!T is a Lisp-style list.  It has
 cons cells and atoms, and cons(head, list) creates a new list that
 shares its tail with list." etc.
 ...


It's not precisely what I want, but it is a way to get close. Ideal 
semantics would be that List!T is a value type with (by default, unless 
qualified immutable) mutable slots, much like what you get for structs. 
Now the problem is just that D does not support expressing this. 
Allowing mutable reference access is the next most obvious viable thing, 
but maybe we can find another way to get close to the right semantics. 
(I guess we might never support mutating method calls on elements in the 
best fashion possible though.)


 You seem to assert there's no contest, and anyone choosing (1) over (2)
 is seriously incompetent.


There's no contest because there shouldn't need to be a mandated choice. 
Categorically choosing (2) over (1) is not the right course of action 
either. (And (2) is already a suboptimal compromise!)


 I seem to think there is a real choice there,
 and I want to keep it open for the time being. Is this reasonable?
 ...


This is reasonable enough. It's not what "I've decided persistent lists 
with mutable elements just too weird to endorse" communicates though. I 
think it is clear what can be done next time (on both sides) to avoid an 
unproductive subthread like this one.


 Maybe not, but what is? It can't be laying down a well-reasoned
 argument, because as recent history shows it will just be ignored
 without a reasonable justification.

 I guess one other good way to proceed would be to just not have the
 dialog for now and instead wait until people who are actually trying
 to use the containers start complaining in blog posts and on reddit.

 Feel free to voice any better suggestions you may have.


 One interesting problem Walter and I have as leaders of this community
 is to attract within the core circle people who are literally better
 than ourselves. People whom we can trust with using good judgment in
 complex situation and can lead themselves entire features and parts of
 the language (such as compiler-supported RC etc).

 Amaury and you (Timon) may as well be the smartest people hanging out in
 this forum. You both are also very generous with your time. I can't talk
 for Walter, but for all I can tell you two are better than I'll ever be
 at all metrics that matter to language design. The challenge, then,
 becomes in convincing you to put that good expertise and good will
 toward something positive; because, to be blunt, a large chunk of your
 and Amaury's energy is dedicated to picking fights and proving just what
 chowderheads Walter and I are for not doing as you say.

 I'm very happy to admit - you're a whole lot better than myself. So
 let's do something constructive.
...


That's flattering, thanks! But it was not my intention to pick a fight. 
It is just that for my current project, persistent data structures would 
be a great option to have. However, the data structures would be  close 
to useless to me if they were to mandate transitive immutability, and 
mirroring them manually is a PITA.
Nov 14 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/14/2015 06:45 PM, Timon Gehr wrote:

 How to implement COW without support for writing?


That'll be the next topic. -- Andrei
Nov 15 2015
prev sibling next sibling parent reply Jakob Ovrum <jakobovrum gmail.com> writes:
On Friday, 13 November 2015 at 23:10:04 UTC, Andrei Alexandrescu 
wrote:

 * Lines 11-12: I came to terms with the notion that some types 
 cannot be made immutable. We've been trying to do reference 
 counting on immutable objects for a long time. It's time to 
 acknowledge that true immutability (which the immutable keyword 
 models) and reference counting don't mix.


External reference counting should work fine with immutable, i.e. 
RefCounted!(immutable T).
Nov 13 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/13/2015 07:28 PM, Jakob Ovrum wrote:

 On Friday, 13 November 2015 at 23:10:04 UTC, Andrei Alexandrescu wrote:

 * Lines 11-12: I came to terms with the notion that some types cannot
 be made immutable. We've been trying to do reference counting on
 immutable objects for a long time. It's time to acknowledge that true
 immutability (which the immutable keyword models) and reference
 counting don't mix.


 External reference counting should work fine with immutable, i.e.
 RefCounted!(immutable T).


I've been asking this same question myself, vaguely, many times. 
Whenever I want to get work done using that mindset, I can't. Then I 
bring it up to Walter, and he asks again the same. Then I don't know how 
to explain it. Time to nip it in the bud once and for all. Clarify it 
forever so no need to bring it up again, ever.

The general pattern goes like this: "So okay, understood, immutable 
doesn't work with reference counting. Then, clearly what we need is an 
object with an immutable part and a mutable part! Instead of 
immutable(RC!T), we use RC!(immutable T) throughout. It has a mutable 
reference count and an immutable Problem solved!"

Technically, that clearly works. There's a problem with scaling it up:

COMPOSITION

Disallowing immutable(RC!T) in favor of RC!(immutable T) effectively 
disables composition of larger immutable objects from smaller ones.

One obvious thing to do is with a reference counted object it to make it 
a field of a larger object. That effectively makes that larger object 
impossible to be used with immutable, transitively.

That's not a bad thing; it's merely a factual acknowledgment that in the 
D programming language, immutable models (transitively and in a way that 
makes composition possible) true immutability of bits, which makes 
sharing possible at no cost. Reference counting is mutating, therefore 
it does not and cannot work with immutability as defined by D.

So disabling immutable(RC!T) in favor of RC!(immutable T) is a fine way 
to approach things, but not a solution to the general problem of making 
general reference counted D objects mutable. That problem does not have 
a solution.


Andrei
Nov 14 2015
next sibling parent reply Dicebot <public dicebot.lv> writes:
I don't think immutable should be something casual and widespread 
in most designs at all. It is a very restrictive qualifier with 
an extremely narrow use case, trying to retro-fit it to be easy 
to use and compose tends to do more harm than actually going with 
mutable instead.

All trouble comes from trying to use physical immutable as 
logical one while still pretending it gives physical guarantees. 
Even if existing immutability is not widely applicable, I'd 
prefer to have narrow applicability over wide false confidence. 
Right now I know for sure that if I can use immutable data 
without any thread locking and it is not possible to screw it up. 
It is rarely important, but when it is, it is priceless.
Nov 14 2015
next sibling parent Dicebot <public dicebot.lv> writes:
P.S. another problem with `RC!(immutable T)` is that it actually 
must be `shared(RC!(immutable T)` to be provide  safe API.
Nov 14 2015
prev sibling parent reply Observer <dummy dummy.com> writes:
On Saturday, 14 November 2015 at 16:27:17 UTC, Dicebot wrote:

 All trouble comes from trying to use physical immutable as 
 logical one while still pretending it gives physical 
 guarantees. Even if existing immutability is not widely 
 applicable, I'd prefer to have narrow applicability over wide 
 false confidence. Right now I know for sure that if I can use 
 immutable data without any thread locking and it is not 
 possible to screw it up. It is rarely important, but when it 
 is, it is priceless.


I can't say I'm following this discussion in great detail, but
one thing strikes me.  "const"-ness and "immutable"-ility are
at some abstract level flavors of value stability.  And that
suggests to me that perhaps we should not be looking so much
for backdoors as for new terms, leaving the old terms alone.
Perhaps a given old keyword won't work well with RC; so be it.
Perhaps a new keyword such as "stable" could be used to describe
a storage category where the payload fields are unchanging but
any metadata fields are potentially mutable.  Then perhaps const
could mean physically immutable, while stable means logically
immutable.  Or something like that.
Nov 14 2015
parent reply Dicebot <public dicebot.lv> writes:
On Saturday, 14 November 2015 at 21:02:46 UTC, Observer wrote:

 On Saturday, 14 November 2015 at 16:27:17 UTC, Dicebot wrote:

 All trouble comes from trying to use physical immutable as 
 logical one while still pretending it gives physical 
 guarantees. Even if existing immutability is not widely 
 applicable, I'd prefer to have narrow applicability over wide 
 false confidence. Right now I know for sure that if I can use 
 immutable data without any thread locking and it is not 
 possible to screw it up. It is rarely important, but when it 
 is, it is priceless.
 I can't say I'm following this discussion in great detail, but


 one thing strikes me.  "const"-ness and "immutable"-ility are
 at some abstract level flavors of value stability.  And that
 suggests to me that perhaps we should not be looking so much
 for backdoors as for new terms, leaving the old terms alone.
 Perhaps a given old keyword won't work well with RC; so be it.
 Perhaps a new keyword such as "stable" could be used to describe
 a storage category where the payload fields are unchanging but
 any metadata fields are potentially mutable.  Then perhaps const
 could mean physically immutable, while stable means logically
 immutable.  Or something like that.


I simply don't see much value in logical immutability (and only 
small value I n logical const). Recently I had experience of 
porting lot of D1 code (which had const as a storage class) to D2 
and was surprised how fake most of added safety seemed. In most 
case modifying such value wouldn't cause any trouble at all and 
case for real trouble comes from subtle indirectional mutation.

Because of that I am very unhappy with attempts to break the type 
system which had costed considerable part of limited language 
resource for the sake of fake convenience (all  mutable 
speculation)
Nov 15 2015
parent Paolo Invernizzi <paolo.invernizzi no.address> writes:
On Sunday, 15 November 2015 at 13:30:30 UTC, Dicebot wrote:

 Because of that I am very unhappy with attempts to break the 
 type system which had costed considerable part of limited 
 language resource for the sake of fake convenience (all 
  mutable speculation)


+1, same attitude here.

---
/Paolo
Nov 15 2015
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 11/14/2015 05:05 PM, Andrei Alexandrescu wrote:

 Technically, that clearly works. There's a problem with scaling it up:

 COMPOSITION
 ...


Composition matters.


 Disallowing immutable(RC!T) in favor of RC!(immutable T) effectively
 disables composition of larger immutable objects from smaller ones.

 One obvious thing to do is with a reference counted object it to make it
 a field of a larger object. That effectively makes that larger object
 impossible to be used with immutable, transitively.

 That's not a bad thing; it's merely a factual acknowledgment that in the
 D programming language, immutable models (transitively and in a way that
 makes composition possible) true immutability of bits, which makes
 sharing possible at no cost. Reference counting is mutating, therefore
 it does not and cannot work with immutability as defined by D.


Obviously. But RC /does/ work with persistent containers! (Unless the 
author of the container has added a gratuitous compile-time check to 
make it impossible.)
Nov 14 2015
prev sibling parent Jakob Ovrum <jakobovrum gmail.com> writes:
On Saturday, 14 November 2015 at 16:05:10 UTC, Andrei 
Alexandrescu wrote:

 Technically, that clearly works. There's a problem with scaling 
 it up:

 COMPOSITION

 Disallowing immutable(RC!T) in favor of RC!(immutable T) 
 effectively disables composition of larger immutable objects 
 from smaller ones.


Yeah, I totally agree, I by no means think that external 
reference counting is some kind of silver bullet - as proven time 
and again, it is rife with issues when applied generally. I just 
wanted to point out, since a lot of lay people read these 
threads, that it will continue to be an option. I look forward to 
see what kind of memory safe reference counting you PL buffs will 
figure out.


 One obvious thing to do is with a reference counted object it 
 to make it a field of a larger object. That effectively makes 
 that larger object impossible to be used with immutable, 
 transitively.


Random off-topic thought (sorry): maybe the immutable larger 
object could survive if there was a way to make 
immutable(RefCounted!T) behave like immutable(Unique!T). It would 
be uncopyable (non-copyable? Damn you, boost!) but perhaps still 
usable. I guess it would still need a cast for 
`free`/`deallocate` in the destructor.
Nov 14 2015
prev sibling next sibling parent Rikki Cattermole <alphaglosined gmail.com> writes:
Hmm. We can't have immutability and ref counting.
Lets just say, the only time ref counting should come into effect is IF 
it has been removed from the list. This way the list should consider it 
'owned' by it.

This is where I say, immutability by itself isn't the problem. The 
problem is we are unable to attribute new behavior to another type 
without effecting the type system directly.

If we can add new behavior without effecting the payloads immutability, 
we can add e.g. ref counting as needed.

This is where my 'managed memory'[0] idea is coming into play.
In essence, managed memory would allow a mutable addition to any given 
heap allocated type (not including pointers).

So sure the payload is attributed as being immutable, but ref counting 
can still go on safely!

Of course this is a major addition and is no where near ready for DIP 
status, but hey, maybe a solution?

[0] http://wiki.dlang.org/User:Alphaglosined/ManagedMemory
Nov 13 2015
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, 13 November 2015 at 23:10:04 UTC, Andrei Alexandrescu 
wrote:

 * Lines 26-29: The allocator is fundamentally a mutable part of 
 the container. This is an insufficiency of our type system - we 
 can't say "this object may be constant, but this reference is 
 to a mutable part of it". We can't explain that necessity out 
 of existence, and List is part of the proof. So we need to make 
 that cast legal.

 One simple solution is to simply allow the cast. One more 
 involved is to define an attribute  mutable with the following 
 rules: (a)  mutable data is not affected by const; (b) if a 
 type T contains transitively any  mutable member, immutable(T) 
 is illegal. That would allow us to not need a cast in line 28.


The problem (at least with the current cast) is that D's const is 
supposed to be physical const, not logical const, and treating 
any of its parts internally as mutable violates that. When the 
const object could actually be immutable underneath, we really 
have no choice about that, because immutable needs to be physical 
const to do what it does. With immutable out of the picture, it 
becomes a more interesting question.

As it stands, the compiler can assume that a const object doesn't 
mutate if it knows that no other references to that data could 
have mutated it. In theory that's worth something but in practice 
is probably pretty much useless, since it's likely to help only 
when pure member functions are called in succession. But if we 
allow  mutable, then we'll have to ensure that the compiler never 
does any optimizations based on const when  mutable is involved 
(and possibly make it never make optimizations based on const 
anywhere since stuff like pointers and classes are can hide the 
fact that  mutable is involved).

The bigger problem is that it undermines the guarantee that const 
objects can't be mutated via a const reference, since as soon as 
a member variable is  mutable, that's circumvented. As long as 
casting away const and mutating is still undefined behavior, then 
it's only a matter of finding  mutable members, but it basically 
means that we're allowing D's const to go from physical to const 
to logical const (where the mutation isn't even actually 
guaranteed to follow the rules of logical const, since it's the 
programmer that controls it), and that's not a small thing, 
particularly in light of how much Walter prizes the compiler 
guarantees that physical const provides (and I agree that there's 
real value there).

Now, as it stands, D's const is so restrictive that certain 
idioms are just plain impossible with it. Ref-counting is the 
prime example, and your predicament with the container highlights 
another. And aside from immutable, we _can_ choose to change how 
D's const works so that it has backdoors like  mutable. And given 
how many D programmers seem to have pretty much decided that 
const is useless and shouldn't be used precisely because it's too 
restrictive, that may be exactly what we need to do. But 
regardless, we _do_ need to do it in a way that allows const to 
work properly with immutable, and disallowing immutable with 
 mutable and ensuring that the compiler doesn't make assumptions 
about const that don't jive with  mutable when it's possible that 
 mutable is involved should then make it possible for us to make 
a change to const to make it less restrictive.

So, while I don't really like the idea of putting a backdoor in 
const, I think that it's clear that we're either going to have to 
put in that backdoor, or we're going to have to disallow idioms 
like what you're trying to do with the allocator in this 
container.

- Jonathan M Davis
Nov 13 2015
prev sibling next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 14-Nov-2015 02:10, Andrei Alexandrescu wrote:

 I created a simple persistent list with reference counting and custom
 allocation at http://dpaste.dzfl.pl/0981640c2835. It's a good
 illustration of a number of issues. In particular, each cast must be
 properly explained.

 Here's my exegesis:


[snip]

 * Lines 11-12: I came to terms with the notion that some types cannot be
 made immutable. We've been trying to do reference counting on immutable
 objects for a long time. It's time to acknowledge that true immutability
 (which the immutable keyword models) and reference counting don't mix.
 Const does work (more below). But overall I'm at peace with the notion
 that if you can't live without immutable, I'll refer you to the garbage
 collector.

 * Lines 26-29: The allocator is fundamentally a mutable part of the
 container. This is an insufficiency of our type system - we can't say
 "this object may be constant, but this reference is to a mutable part of
 it". We can't explain that necessity out of existence, and List is part
 of the proof. So we need to make that cast legal.


Just don't make it const (see your point at 11-12). I have a feeling 
that ref-count and allocator are in the same mold - fields that must mutate.

So I imagine const/immutable for complex types will only work like this:

struct Layout{
    immutable Core core; //all constness ends here
    // accounting fields
    uint refCount;
    UAllocator alloc;
// ... any tracing and/or stats fit this definition
}

I totally do not understand the whole knee-jerk reaction of "everything 
must be const because it looks good in my code" and bug reports a-la:

const obj = SomeComplexTypeFromStd(....); // doesn't compile!

Well some types can't be transitively const (w/o sacrificing 
functionality/performance). Low-level immutable is a tool to create 
high-level immutable constructs IMHO.

It might make sense to re-purpose final storage class to be write-once 
a-la Java, because this is what folks expect when writing 
`immutable/const x = ...;` everywhere possible.


 * Lines 141-152: I couldn't make tail() work with inout. Generally I'm
 very unhappy about inout. I don't know how to use it. Everything I read
 about it is extremely complicated compared to its power. I wish we
 removed it from the language and replaced it with an understandable idiom.


I can't agree more. Every time dealing with inout when I finally think I 
grok how it works the next instant I see that it doesn't do what I expect.

For me inout inevitably stops at the boundary of being unnable to have 
List!(inout(T)) and the like.


-- 
Dmitry Olshansky
Nov 14 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/14/15 3:42 AM, Dmitry Olshansky wrote:

 On 14-Nov-2015 02:10, Andrei Alexandrescu wrote:



 * Lines 141-152: I couldn't make tail() work with inout. Generally I'm
 very unhappy about inout. I don't know how to use it. Everything I read
 about it is extremely complicated compared to its power. I wish we
 removed it from the language and replaced it with an understandable
 idiom.


 I can't agree more. Every time dealing with inout when I finally think I
 grok how it works the next instant I see that it doesn't do what I expect.

 For me inout inevitably stops at the boundary of being unnable to have
 List!(inout(T)) and the like.


One thing we could allow is types that contain inout member variables, 
but ONLY in the context of inout functions. In other words, you can 
create a type for it, but can only use it in the context of an inout 
function.

A List!(inout(T)) outside an inout function has no meaning. This is why 
we disallowed it.

However, my belief is that it's the lack of a mechanism to apply an 
attribute to the tail of some struct that prevents the most utility 
here. If you returned a List!(inout(T)) there is no way to magically 
convert it to a List!(const(T)) or List!(immutable(T)).

Consider that Node in this code has a "const(Node)* next" as its tail.

I believe we should be able to achieve both.

-Steve
Nov 16 2015
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 16-Nov-2015 19:44, Steven Schveighoffer wrote:

 On 11/14/15 3:42 AM, Dmitry Olshansky wrote:

 On 14-Nov-2015 02:10, Andrei Alexandrescu wrote:



 * Lines 141-152: I couldn't make tail() work with inout. Generally I'm
 very unhappy about inout. I don't know how to use it. Everything I read
 about it is extremely complicated compared to its power. I wish we
 removed it from the language and replaced it with an understandable
 idiom.


 I can't agree more. Every time dealing with inout when I finally think I
 grok how it works the next instant I see that it doesn't do what I
 expect.

 For me inout inevitably stops at the boundary of being unnable to have
 List!(inout(T)) and the like.


 One thing we could allow is types that contain inout member variables,
 but ONLY in the context of inout functions. In other words, you can
 create a type for it, but can only use it in the context of an inout
 function.


inout should be indistinguishable of const but the moment you pass 
inout(T) to a template it becomes murky.

Appender!(inout(int)) - which qualifier to instantiate?


 A List!(inout(T)) outside an inout function has no meaning. This is why
 we disallowed it.

 However, my belief is that it's the lack of a mechanism to apply an
 attribute to the tail of some struct that prevents the most utility
 here. If you returned a List!(inout(T)) there is no way to magically
 convert it to a List!(const(T)) or List!(immutable(T)).

 Consider that Node in this code has a "const(Node)* next" as its tail.

 I believe we should be able to achieve both.


Looks a lot like tail-const problem. That is immutable T!E has no way to 
convert to T!(immutable E) and similarly to T!(const E).

Overall I see const/immutable a fine thing at low-level scope but not 
applicable at all to high-level constructs.

If something is conceptually const - its the task of implementation 
which may rely on physical const qualifier somewhere deep inside.


 -Steve



-- 
Dmitry Olshansky
Nov 16 2015
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/16/15 1:15 PM, Dmitry Olshansky wrote:

 On 16-Nov-2015 19:44, Steven Schveighoffer wrote:

 On 11/14/15 3:42 AM, Dmitry Olshansky wrote:

 On 14-Nov-2015 02:10, Andrei Alexandrescu wrote:



 * Lines 141-152: I couldn't make tail() work with inout. Generally I'm
 very unhappy about inout. I don't know how to use it. Everything I read
 about it is extremely complicated compared to its power. I wish we
 removed it from the language and replaced it with an understandable
 idiom.


 I can't agree more. Every time dealing with inout when I finally think I
 grok how it works the next instant I see that it doesn't do what I
 expect.

 For me inout inevitably stops at the boundary of being unnable to have
 List!(inout(T)) and the like.


 One thing we could allow is types that contain inout member variables,
 but ONLY in the context of inout functions. In other words, you can
 create a type for it, but can only use it in the context of an inout
 function.


 inout should be indistinguishable of const but the moment you pass
 inout(T) to a template it becomes murky.

 Appender!(inout(int)) - which qualifier to instantiate?


The idea is, you would instantiate Appender!(inout(int)) :) Should be 
fine to use inside an inout function.

The problem is, you couldn't use it outside inout, so you couldn't use 
this as the return type. But inside the function, you could use it.

Right now, you can effectively do this with arrays, since inout(T)[] 
works fine, and this can essentially map to some fictional template 
instantiation ArrayStruct!(inout(T)) (or some other way to instantiate 
ArrayStruct!T and wrap this in an attribute that means tail). But arrays 
enjoy both auto casting that tail member to other flavors, and also the 
compiler allows you to create inout arrays inside an inout function.

We can at least solve the latter pretty easily. The closer we can move 
to have an actual ArrayStruct template that works just like a real 
array, the closer we are to having a complete solution.


 A List!(inout(T)) outside an inout function has no meaning. This is why
 we disallowed it.

 However, my belief is that it's the lack of a mechanism to apply an
 attribute to the tail of some struct that prevents the most utility
 here. If you returned a List!(inout(T)) there is no way to magically
 convert it to a List!(const(T)) or List!(immutable(T)).

 Consider that Node in this code has a "const(Node)* next" as its tail.




Note, I think I was wrong with this. The Node has a Node *next, but root 
is labelled as const.

In the end, this code is a bad example of what is wrong with inout, 
because inout shouldn't be used on it anyway.


 Looks a lot like tail-const problem. That is immutable T!E has no way to
 convert to T!(immutable E) and similarly to T!(const E).


It all depends on how E is used in T. Tail-const is a specific problem 
that *could* be solved if we could provide a mechanism to do this, but 
providing the mechanism isn't *required*.

-Steve
Nov 16 2015
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/14/2015 12:10 AM, Andrei Alexandrescu wrote:

 ...
 * Lines 11-12: I came to terms with the notion that some types cannot be
 made immutable. We've been trying to do reference counting on immutable
 objects for a long time. It's time to acknowledge that true immutability
 (which the immutable keyword models) and reference counting don't mix.
 Const does work (more below). But overall I'm at peace with the notion
 that if you can't live without immutable, I'll refer you to the garbage
 collector.
 ...


I.e. you think it is fine that there can be no list of lists.
Anyway, the static assert does not actually do what you intend it to do.


 * Lines 26-29: The allocator is fundamentally a mutable part of the
 container. This is an insufficiency of our type system - we can't say
 "this object may be constant, but this reference is to a mutable part of
 it". We can't explain that necessity out of existence, and List is part
 of the proof. So we need to make that cast legal.
 ...


Just don't make the method const. (This is not C++.)
Nov 14 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/14/2015 03:55 PM, Timon Gehr wrote:

 On 11/14/2015 12:10 AM, Andrei Alexandrescu wrote:

 ...
 * Lines 11-12: I came to terms with the notion that some types cannot be
 made immutable. We've been trying to do reference counting on immutable
 objects for a long time. It's time to acknowledge that true immutability
 (which the immutable keyword models) and reference counting don't mix.
 Const does work (more below). But overall I'm at peace with the notion
 that if you can't live without immutable, I'll refer you to the garbage
 collector.
 ...


 I.e. you think it is fine that there can be no list of lists.


T may be const in List!T, so composing with const should work fine.


 Anyway, the static assert does not actually do what you intend it to do.


The odd thing is it does as far as I can tell, but the error message is 
less than informative. Try it!


 * Lines 26-29: The allocator is fundamentally a mutable part of the
 container. This is an insufficiency of our type system - we can't say
 "this object may be constant, but this reference is to a mutable part of
 it". We can't explain that necessity out of existence, and List is part
 of the proof. So we need to make that cast legal.
 ...


 Just don't make the method const. (This is not C++.)


I want to allow mutable lists and const lists, just not immutable lists. 
It seems to me const has a value even if it doesn't originate from 
immutable.


Andrei
Nov 14 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/14/2015 10:59 PM, Andrei Alexandrescu wrote:

 On 11/14/2015 03:55 PM, Timon Gehr wrote:

 On 11/14/2015 12:10 AM, Andrei Alexandrescu wrote:

 ...
 * Lines 11-12: I came to terms with the notion that some types cannot be
 made immutable. We've been trying to do reference counting on immutable
 objects for a long time. It's time to acknowledge that true immutability
 (which the immutable keyword models) and reference counting don't mix.
 Const does work (more below). But overall I'm at peace with the notion
 that if you can't live without immutable, I'll refer you to the garbage
 collector.
 ...


 I.e. you think it is fine that there can be no list of lists.


 T may be const in List!T, so composing with const should work fine.
 ...


List uses RC internally. I don't think the UB casts will stay for the 
final version, unless you are willing to completely dilute the meaning 
of const in ways that Walter has explicitly expressed will not be done 
in the past.


 Anyway, the static assert does not actually do what you intend it to do.


 The odd thing is it does as far as I can tell, but the error message is
 less than informative. Try it!
 ...


I cannot get the list to compile with 2.069.1 without replacing the 
calls to emplace, which is odd (as it works on dpaste), but in any case, 
the static assert is a no-op. typeof(this) is always unqualified at 
aggregate scope. What is preventing the construction of a non-empty 
immutable list is that there is no immutable non-default constructor.



 * Lines 26-29: The allocator is fundamentally a mutable part of the
 container. This is an insufficiency of our type system - we can't say
 "this object may be constant, but this reference is to a mutable part of
 it". We can't explain that necessity out of existence, and List is part
 of the proof. So we need to make that cast legal.
 ...


 Just don't make the method const. (This is not C++.)


 I want to allow mutable lists and const lists, just not immutable lists.
 It seems to me const has a value even if it doesn't originate from
 immutable.
 ...


It's supposed to guarantee that the given reference is not used to 
transitively mutate the object. The casts violate this.
Nov 14 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/14/15 5:49 PM, Timon Gehr wrote:

 It's supposed to guarantee that the given reference is not used to
 transitively mutate the object. The casts violate this.


I think that semantics needs to change. Specifically, either we add a 
 mutable attribute (which means const doesn't apply to fields marked as 
such and immutable objects cannot be created); or we could just decree 
that if a const object originates in a mutable object, casts should be 
well-defined. -- Andrei
Nov 14 2015
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/15/2015 12:20 AM, Andrei Alexandrescu wrote:

 On 11/14/15 5:49 PM, Timon Gehr wrote:

 It's supposed to guarantee that the given reference is not used to
 transitively mutate the object. The casts violate this.


 I think that semantics needs to change. Specifically, either we add a
  mutable attribute (which means const doesn't apply to fields marked as
 such and immutable objects cannot be created); or we could just decree
 that if a const object originates in a mutable object, casts should be
 well-defined. -- Andrei


There's also this closely related situation:
https://issues.dlang.org/show_bug.cgi?id=9149

(I.e. delegates with mutable context pointer can be implicitly converted 
to delegates with const context pointer, but when type checking the 
delegate, a mutable context pointer is assumed.)
Nov 14 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/14/2015 06:48 PM, Timon Gehr wrote:

 On 11/15/2015 12:20 AM, Andrei Alexandrescu wrote:

 On 11/14/15 5:49 PM, Timon Gehr wrote:

 It's supposed to guarantee that the given reference is not used to
 transitively mutate the object. The casts violate this.


 I think that semantics needs to change. Specifically, either we add a
  mutable attribute (which means const doesn't apply to fields marked as
 such and immutable objects cannot be created); or we could just decree
 that if a const object originates in a mutable object, casts should be
 well-defined. -- Andrei


 There's also this closely related situation:
 https://issues.dlang.org/show_bug.cgi?id=9149

 (I.e. delegates with mutable context pointer can be implicitly converted
 to delegates with const context pointer, but when type checking the
 delegate, a mutable context pointer is assumed.)


That's a hole straight into the middle of things. We need to fix that. 
-- Andrei
Nov 15 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 11/15/2015 01:57 PM, Andrei Alexandrescu wrote:

 On 11/14/2015 06:48 PM, Timon Gehr wrote:

 On 11/15/2015 12:20 AM, Andrei Alexandrescu wrote:

 On 11/14/15 5:49 PM, Timon Gehr wrote:

 It's supposed to guarantee that the given reference is not used to
 transitively mutate the object. The casts violate this.


 I think that semantics needs to change. Specifically, either we add a
  mutable attribute (which means const doesn't apply to fields marked as
 such and immutable objects cannot be created); or we could just decree
 that if a const object originates in a mutable object, casts should be
 well-defined. -- Andrei


 There's also this closely related situation:
 https://issues.dlang.org/show_bug.cgi?id=9149

 (I.e. delegates with mutable context pointer can be implicitly converted
 to delegates with const context pointer, but when type checking the
 delegate, a mutable context pointer is assumed.)


 That's a hole straight into the middle of things. We need to fix that.
 -- Andrei


Given your recent efforts to change the meaning of const, I think it is 
no longer as clear-cut as it was when I reported the bug. Those 
delegates can only mutate const objects that were constructed as mutable.
Nov 15 2015
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, 14 November 2015 at 23:20:08 UTC, Andrei 
Alexandrescu wrote:

 On 11/14/15 5:49 PM, Timon Gehr wrote:

 It's supposed to guarantee that the given reference is not 
 used to
 transitively mutate the object. The casts violate this.


 I think that semantics needs to change. Specifically, either we 
 add a  mutable attribute (which means const doesn't apply to 
 fields marked as such and immutable objects cannot be created); 
 or we could just decree that if a const object originates in a 
 mutable object, casts should be well-defined. -- Andrei


Either way, we'd be throwing away the idea that const is physical 
const and provides actual guarantees against mutation via const 
references. We'd essentially be going the route of having C++'s 
const except that it's transitive, which is a definite loss IMHO, 
but at the same time, with D's const, you frequently have to give 
up on using const, because physical const is so restrictive as to 
be unusable in many cases.

I honestly don't know if it's better to just say that you can't 
use const if you want to do something like reference counting or 
using an allocator or to gut the guarantees that D's const 
provides. Ideally, we'd keep the guarantees, but they often seem 
to end up being completely impractical in practice. And they 
don't jive at all with the recent push to support RC.

That being said, if we are going to make a change like this, I'm 
not sure if we even _can_ do it. immutable throws a serious 
wrench in any attempt have something like C++'s const in D.

As it stands, the only thing that really ensures that immutable 
objects aren't mutated is the type system. As I understand it, if 
an immutable object gets put into ROM (or memory that's being 
treated as ROM), then mutating it will cause a segfault, but the 
only case where that might happen right now AFAIK is if the 
object was created at compile time and stored as part of the 
program's data. Certainly, any immutable objects created at 
runtime are only protected from mutation by the type system. So, 
even if the compiler makes _zero_ assumptions based on const, 
casting away const and mutating is very dangerous, because you 
risk mutating an immutable object and violating all of the 
guarantees associated with that. The only time that casting away 
const and mutating could work would be in cases where you could 
somehow guarantee that the object you're mutating is actually a 
mutable variable underneath the hood. That would be possible in a 
restricted setting, but in a large program or in a public API, 
it's a lot less likely that you can guarantee that the object 
isn't actually immutable. There would have to be some way for the 
type system to guarantee that the object isn't actually immutable 
- which either means making it so that the type in question can't 
be immutable for some reason or having an attribute other than 
const for non-physical const.

Your  mutable suggestion/proposal does step in that direction by 
basically making it so that a const type which contains a 
 mutable member isn't really const. It's some other attribute 
that's not explicitly named (cpp_const, logical_const, 
 mutable_const, or whatever we'd want to call it). And that seems 
like it would work to a point. It would even allow for implicit 
casts instead of explicit ones and make the whole thing far safer 
in general than simply allowing arbitrary casting would. However, 
 mutable still isn't an attribute on the type. It's an attribute 
on a member. So, as soon as you have an opaque pointer or a base 
class reference, the compiler doesn't know that the object is 
actually  mutable_const. So, it can't know that it's not legit to 
have the object be immutable. Now, the compiler would have to 
know that when the object is created, and presumably an 
 mutable_const derived class couldn't convert to an immutable 
base class, so maybe this would actually work, but it seems like 
we're at serious risk of a loophole if we're not really careful 
here. It feels like each time work through this I flip-flop as to 
whether I think that it can work or not.

And of course, even if we do make  mutable work, it would 
basically mean that const doesn't necessarily guarantee much of 
anything anymore other than preventing accidental mutation, since 
unless the compiler can guarantee that no  mutable_const is 
involved, it can't assume much of anything about const (though 
what it can assume about const is already pretty limited - 
particularly when pure isn't involved), and programmers can't 
assume that a const object will really not be mutated by const 
member functions (though in practice, it's unlikely that anyone 
is going to slap  mutable on everything). But even then, we'd 
still be ahead of C++'s const if we have transitivity and 
disallow casting away const to mutate.

I'm torn on the whole thing. On the one hand, I think that D's 
guarantees with physical const have been great. On the other 
hand, too much stuff doesn't work with it. And system programming 
stuff like ref-counting, mutexes, and allocators definitely don't 
work with it.

- Jonathan M Davis
Nov 14 2015
parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Sunday, 15 November 2015 at 02:49:49 UTC, Jonathan M Davis 
wrote:

 the program's data. Certainly, any immutable objects created at 
 runtime are only protected from mutation by the type system.


That would be a bad assumption. It could be read only pages with 
MMU protection. (files, shared memory etc)
Nov 15 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 15 November 2015 at 08:59:52 UTC, Ola Fosheim Grøstad 
wrote:

 On Sunday, 15 November 2015 at 02:49:49 UTC, Jonathan M Davis 
 wrote:

 the program's data. Certainly, any immutable objects created 
 at runtime are only protected from mutation by the type system.


 That would be a bad assumption. It could be read only pages 
 with MMU protection. (files, shared memory etc)


Well, that's news to me, but my understanding of stuff that low 
level isn't very good. Regardless, my point is that there's no 
guarantee that anything other than the type system protects 
immutable variables against mutation. For instance, this code 
compiles and runs just fine.

     void main()
     {
         auto i = new immutable int(5);
         assert(*i == 5);
         auto j = cast(int*)i;
         *j = 42;
         assert(*i == 42);
     }

And there's this bug about how non-shared static constructors 
routinely mutate immutable variables:

https://issues.dlang.org/show_bug.cgi?id=4923

So, while there _are_ cases where mutating immutable memory will 
cause a segfault, there is no guarantee that casting and mutating 
an immutable variable will cause any obvious problems at all.

So, allowing const to be cast away for the purposes of mutation 
becomes _very_ dangerous, because it's very easy to screw up and 
mutate immutable objects, and given how differently the compiler 
treats immutable objects (e.g. they're implicitly shared and 
allow for eliding function calls when used in conjunction with 
pure) on top of the guarantees that the compiler gives about 
immutable objects never mutating, the consequences of mutating an 
object variable are far worse than they are with mutating a 
mutable object being via a const reference, even when doing that 
via a cast is currently undefined behavior.

So, if we choose to put a backdoor in const, it would be far 
better to do so with something like  mutable than to treat 
casting away const from an object and mutating it as defined 
behavior - though I think that we should be _very_ sure that 
we're willing to pay the cost of that backdoor before we make 
that choice.

- Jonathan M Davis
Nov 15 2015
parent reply Dicebot <public dicebot.lv> writes:
 For instance, this code compiles and runs just fine.

     void main()
     {
         auto i = new immutable int(5);
         assert(*i == 5);
         auto j = cast(int*)i;
         *j = 42;
         assert(*i == 42);
     }


AFAIK this is UB already (in practice), you will get different 
results depending on compiler and optimization flags.
Nov 15 2015
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 15 November 2015 at 14:21:18 UTC, Dicebot wrote:

 For instance, this code compiles and runs just fine.

     void main()
     {
         auto i = new immutable int(5);
         assert(*i == 5);
         auto j = cast(int*)i;
         *j = 42;
         assert(*i == 42);
     }


 AFAIK this is UB already (in practice), you will get different 
 results depending on compiler and optimization flags.


Oh, it's definitely undefined behavior. As far as the compiler is 
concerned, casting away either const or immutable means that it's 
up to _you_ to uphold the guarantee that they won't be mutated 
(whereas the compiler can guarantee it as long as you don't cast 
away const or immutable).

My point is that there's nothing actually stopping you from doing 
it, and you don't necessarily get a segfault or any other obvious 
problems when you do it. So, if the language were changed so that 
casting away const and mutating was defined behavior (at least as 
long as the underlying object is actually mutable), the only 
thing protecting folks against not accidentally casting away 
const on an object that is actually immutable is themselves. 
There is no compiler help, and the program will not necessarily 
blow up when you screw it up. So, you run a very real risk of 
introducing very subtle bugs into your programs with regards to 
immutable objects when you cast away const and mutate - even if 
the language is changed so that that is well-defined when the 
object is actually mutable.

At least with  mutable as Andrei proposed it, the compiler would 
be able to guarantee that an immutable object wasn't treated as 
mutable, even if it then allowed const references to mutate 
objects in a limited manner. So, while we'd lose out on the 
guarantee that const references could never mutate objects, at 
least that mutation would be limited and controlled with some 
compiler guarantees left intact, whereas making it well-defined 
to cast away const and mutate would be throwing pretty much all 
of the guarantees out the window (on top of being very 
error-prone).

- Jonathan M Davis
Nov 15 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/14/2015 05:49 PM, Timon Gehr wrote:

 List uses RC internally. I don't think the UB casts will stay for the
 final version, unless you are willing to completely dilute the meaning
 of const in ways that Walter has explicitly expressed will not be done
 in the past.


As I mentioned, he's okay with changing the language to make the casts 
well defined. -- Andrei
Nov 15 2015
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 15 November 2015 at 12:56:27 UTC, Andrei Alexandrescu 
wrote:

 On 11/14/2015 05:49 PM, Timon Gehr wrote:

 List uses RC internally. I don't think the UB casts will stay 
 for the
 final version, unless you are willing to completely dilute the 
 meaning
 of const in ways that Walter has explicitly expressed will not 
 be done
 in the past.


 As I mentioned, he's okay with changing the language to make 
 the casts well defined. -- Andrei


Well, that's a big change, since it pretty much means that D's 
const isn't physical const anymore, and Walter has been _very_ 
insistent about that in the past - to the point that he's argued 
that C++'s const is outright useless because it isn't physical 
const. If casting away const and mutating is well-defined 
behavior, then we basically have C++'s const except that it's 
transitive, and you have to be careful to make sure that the 
object isn't actually immutable underneath the hood instead of 
mutable, whereas C++ doesn't have immutable.

But if we go that route, personally, I think that it would be far 
better to do something like  mutable and leave mutating const and 
undefined outside of  mutable, particularly since if we can 
implement  mutable properly, then the compiler can guarantee that 
the object being mutated isn't actually immutable, and it avoids 
the need for casting altogether, which reduces the risk of bugs 
even when immutable isn't involved. It also means that the 
programmer can determine whether an object is really only 
logically const rather than physically const by looking at its 
member variables rather than having to dig through all of its 
code to see whether it ever casts away const.

- Jonathan M Davis
Nov 15 2015
parent reply Dicebot <public dicebot.lv> writes:
On Sunday, 15 November 2015 at 14:23:05 UTC, Jonathan M Davis 
wrote:

 As I mentioned, he's okay with changing the language to make 
 the casts well defined. -- Andrei


 Well, that's a big change, since it pretty much means that D's 
 const isn't physical const anymore, and Walter has been _very_ 
 insistent about that in the past - to the point that he's 
 argued that C++'s const is outright useless because it isn't 
 physical const. If casting away const and mutating is 
 well-defined behavior, then we basically have C++'s const 
 except that it's transitive ...


Casting away _const_ is already legal if programmer can himself 
guarantee underlying object has mutable origin (i.e. not 
available via immutable reference), by the very definition of 
const. It is casting away immutable and mutating that is strictly 
UB.
Nov 15 2015
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 15 November 2015 at 14:34:45 UTC, Dicebot wrote:

 On Sunday, 15 November 2015 at 14:23:05 UTC, Jonathan M Davis 
 wrote:

 As I mentioned, he's okay with changing the language to make 
 the casts well defined. -- Andrei


 Well, that's a big change, since it pretty much means that D's 
 const isn't physical const anymore, and Walter has been _very_ 
 insistent about that in the past - to the point that he's 
 argued that C++'s const is outright useless because it isn't 
 physical const. If casting away const and mutating is 
 well-defined behavior, then we basically have C++'s const 
 except that it's transitive ...


 Casting away _const_ is already legal if programmer can himself 
 guarantee underlying object has mutable origin (i.e. not 
 available via immutable reference), by the very definition of 
 const. It is casting away immutable and mutating that is 
 strictly UB.


No. As it stands, casting away const and mutating is _always_ 
considered undefined behavior, regardless of whether the object 
being referred to is actually mutable, const, or immutable. In 
fact, there was a discussion on that not long ago, and the spec 
was updated to be clearer on that count - with approval from 
Walter. AFAIK, it has never been the case that casting away const 
and mutating was defined behavior in D2 (I have no idea what the 
deal with D1 and const is other than the fact that it was quite 
different).

- Jonathan M Davis
Nov 15 2015
parent reply Dicebot <public dicebot.lv> writes:
On Sunday, 15 November 2015 at 14:42:25 UTC, Jonathan M Davis 
wrote:

 Casting away _const_ is already legal if programmer can 
 himself guarantee underlying object has mutable origin (i.e. 
 not available via immutable reference), by the very definition 
 of const. It is casting away immutable and mutating that is 
 strictly UB.


 No. As it stands, casting away const and mutating is _always_ 
 considered undefined behavior, regardless of whether the object 
 being referred to is actually mutable, const, or immutable. In 
 fact, there was a discussion on that not long ago, and the spec 
 was updated to be clearer on that count - with approval from 
 Walter. AFAIK, it has never been the case that casting away 
 const and mutating was defined behavior in D2 (I have no idea 
 what the deal with D1 and const is other than the fact that it 
 was quite different).


How was it justified to fit definition of `const`? It is in 
direct contradiction, because const is supposed to mean "can be 
either mutable or immutable, can't make any assumptions about it".

My understanding from previous discussions was that mutating 
const is UB is general because mutating immutable is UB and const 
_may_ be a view to immutable data. And if this can be proved to 
not be the case, const is not really const anymore. In fact, 
major chunk of our ported code relies on this.

(D1 is irrelevant here as const isn't a type qualifier there and 
this cant be part of cast)
Nov 15 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 15 November 2015 at 14:55:36 UTC, Dicebot wrote:

 On Sunday, 15 November 2015 at 14:42:25 UTC, Jonathan M Davis 
 wrote:

 Casting away _const_ is already legal if programmer can 
 himself guarantee underlying object has mutable origin (i.e. 
 not available via immutable reference), by the very 
 definition of const. It is casting away immutable and 
 mutating that is strictly UB.


 No. As it stands, casting away const and mutating is _always_ 
 considered undefined behavior, regardless of whether the 
 object being referred to is actually mutable, const, or 
 immutable. In fact, there was a discussion on that not long 
 ago, and the spec was updated to be clearer on that count - 
 with approval from Walter. AFAIK, it has never been the case 
 that casting away const and mutating was defined behavior in 
 D2 (I have no idea what the deal with D1 and const is other 
 than the fact that it was quite different).


 How was it justified to fit definition of `const`? It is in 
 direct contradiction, because const is supposed to mean "can be 
 either mutable or immutable, can't make any assumptions about 
 it".

 My understanding from previous discussions was that mutating 
 const is UB is general because mutating immutable is UB and 
 const _may_ be a view to immutable data. And if this can be 
 proved to not be the case, const is not really const anymore. 
 In fact, major chunk of our ported code relies on this.


const in D guarantees that the object will not be mutated via 
that reference regardless of what that reference refers to. And 
there _are_ cases where the compiler can make assumptions based 
purely on const, though they're not common. e.g.

auto bar(const Foo) pure;

auto foo = new Foo;
auto result = bar(foo);

After the call to bar, the compiler can guarantee that the value 
of foo has not changed, because it's not possible for bar to 
access foo except via a const reference, and it can clearly see 
that, because it can see that it's not possible for bar to access 
foo except via the reference that's passed to it. In fact, with 
the following code

auto bar(const Foo) pure;

auto foo = new Foo;
auto result1 = bar(foo);
auto result2 = bar(foo);

it would be possible for the compiler to know that result1 and 
result2 are identical and elide the function call like it could 
if bar were given an immutable object. AFAIK, the compiler 
doesn't do anything like that currently, but const is enough for 
it to do so in this case. So, const my itself can provide 
guarantees, even though usually the compiler doesn't have enough 
information to do much with const alone (since it has to be able 
to know that the object is not mutated via another, mutable 
reference, which it usually can't).

Whenever this has come up, Walter has been adamant that D's const 
is physical const and that it's guaranteed by the compiler that 
you an object is not mutated via a  const reference - regardless 
of whether the object referred to is actually mutable, const, or 
immutable.

Now, realistically, you're going to get away with casting away 
const and mutating almost all of the time, because the 
assumptions that the compiler can make on const alone are pretty 
limited, but it's still undefined behavior.

- Jonathan M Davis
Nov 15 2015
next sibling parent reply Dicebot <public dicebot.lv> writes:
On Sunday, 15 November 2015 at 15:09:25 UTC, Jonathan M Davis 
wrote:

 After the call to bar, the compiler can guarantee that the 
 value of foo has not changed, because it's not possible for bar 
 to access foo except via a const reference, and it can clearly 
 see that, because it can see that it's not possible for bar to 
 access foo except via the reference that's passed to it.


Note that it can only do so if escape analysis is able to prove 
no other reference escapes to the same data. Otherwise it can be 
mutated even during that function call in other thread. All 
together it makes benefits of such deduction absolutely not worth 
UB limitation in my opinion.

For pure functions it is quite different story though and I agree 
that demanding it to be UB there is totally legitimate.
Nov 15 2015
next sibling parent Dicebot <public dicebot.lv> writes:
On Sunday, 15 November 2015 at 15:20:24 UTC, Dicebot wrote:

 On Sunday, 15 November 2015 at 15:09:25 UTC, Jonathan M Davis 
 wrote:

 After the call to bar, the compiler can guarantee that the 
 value of foo has not changed, because it's not possible for 
 bar to access foo except via a const reference, and it can 
 clearly see that, because it can see that it's not possible 
 for bar to access foo except via the reference that's passed 
 to it.


 Note that it can only do so if escape analysis is able to prove 
 no other reference escapes to the same data. Otherwise it can 
 be mutated even during that function call in other thread. All 
 together it makes benefits of such deduction absolutely not 
 worth UB limitation in my opinion.

 For pure functions it is quite different story though and I 
 agree that demanding it to be UB there is totally legitimate.


Probably also worth mentioning that I don't consider use case 
like in Andrei example (casting away const to mutate 
allocator/refcount of const argument) a legitimate example as it 
is public API and guarantees of mutability of underlying object 
are actually impossible.

Use case I had myself it to cast away const inside invariants but 
this was only ok because we know for sure to never use immutable 
objects _within out own code_. In Phobos such casting is very 
unlikely to be future-proof.
Nov 15 2015
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 15 November 2015 at 15:20:24 UTC, Dicebot wrote:

 On Sunday, 15 November 2015 at 15:09:25 UTC, Jonathan M Davis 
 wrote:

 After the call to bar, the compiler can guarantee that the 
 value of foo has not changed, because it's not possible for 
 bar to access foo except via a const reference, and it can 
 clearly see that, because it can see that it's not possible 
 for bar to access foo except via the reference that's passed 
 to it.


 Note that it can only do so if escape analysis is able to prove 
 no other reference escapes to the same data. Otherwise it can 
 be mutated even during that function call in other thread.


Except that shared isn't involved here. The objects are 
thread-local, so other threads don't matter. The combination of 
TLS and pure does make it so that the compiler could 
theoretically do optimizations based on const. immutable is not 
actually required, though it obviously provides far better 
guarantees.

However, even with full-on escape analysis, the compiler is 
pretty limited in where it can guarantee that a const object 
isn't mutated by another reference. So, it really doesn't mean 
much. But my point was that there _are_ cases when the compiler 
can do optimizations based on const without immutable being 
involved, even if they're rare.


  All together it makes benefits of such deduction absolutely 
 not worth UB limitation in my opinion.


The primary benefit of making it undefined behavior to cast away 
const and mutate is that then you actually have the guarantee 
that an object will not be mutated via a const reference. You get 
actual, physical const. As long as there's a backdoor out of 
const, const provides no real guarantees. Rather, it just 
prevents accidental mutation and serves as documentation for 
which functions are supposed to be able to mutate the logical 
state on of an object - which is why (as I understand it at 
least) Walter has typically argued that C++'s const is useless.

Now, given how incredibly limiting physical const is, maybe we 
should be more lax with D's const, but if we are, we lose out on 
the compiler guarantees that we currently get and basically end 
up with a transitive version of C++'s const (except that we have 
the added risk of mutating an immutable object if we're not 
careful).

- Jonathan M Davis
Nov 15 2015
parent Dicebot <public dicebot.lv> writes:
On Sunday, 15 November 2015 at 17:42:24 UTC, Jonathan M Davis 
wrote:

 On Sunday, 15 November 2015 at 15:20:24 UTC, Dicebot wrote:

 On Sunday, 15 November 2015 at 15:09:25 UTC, Jonathan M Davis 
 wrote:

 After the call to bar, the compiler can guarantee that the 
 value of foo has not changed, because it's not possible for 
 bar to access foo except via a const reference, and it can 
 clearly see that, because it can see that it's not possible 
 for bar to access foo except via the reference that's passed 
 to it.


 Note that it can only do so if escape analysis is able to 
 prove no other reference escapes to the same data. Otherwise 
 it can be mutated even during that function call in other 
 thread.


 Except that shared isn't involved here. The objects are 
 thread-local, so other threads don't matter. The combination of 
 TLS and pure does make it so that the compiler could 
 theoretically do optimizations based on const. immutable is not 
 actually required, though it obviously provides far better 
 guarantees.


Ok, agreed about threading part (though does currently spec 
require all non-TLS data to be qualified as shared?). But same 
applies to fiber context switches too (within same thread). 
Basically anything that can cause extra code to be executed 
between target function start and finish requires escape analysis 
to justify such optimization.


 But my point was that there _are_ cases when the compiler can 
 do optimizations based on const without immutable being 
 involved, even if they're rare.


If they are that rare, probably they are not worth the trouble :) 
Or should be mentioned in spec explicitly (i.e. pure case)


 The primary benefit of making it undefined behavior to cast 
 away const and mutate is that then you actually have the 
 guarantee that an object will not be mutated via a const 
 reference. You get actual, physical const. As long as there's a 
 backdoor out of const, const provides no real guarantees.


No, not at all. It vast majority of cases (and pretty much all 
library code) you must assume that const can be immutable and 
thus is must be treated as physical const (because immutability 
is physical). In rare cases where it is possible to prove/ensure 
mutability of the data it makes no difference because you can 
have the backdoor via cast anyway, it will only affect how 
reliable result will be across different compilers.


 Now, given how incredibly limiting physical const is, maybe we 
 should be more lax with D's const, but if we are, we lose out 
 on the compiler guarantees that we currently get and basically 
 end up with a transitive version of C++'s const (except that we 
 have the added risk of mutating an immutable object if we're 
 not careful).


No, I think concept of physical const/immutable is fine as it is. 
Limiting but valuable for multi-threading, requiring to build 
whole design of your application around it. It just happens that 
language sometimes forces handling const even in cases you don't 
need to care about immutability (earlier invariant example) which 
makes casting it away (at least temporarily) only practical 
option - and it would be very unpleasant to have that UB.
Nov 15 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/15/2015 10:09 AM, Jonathan M Davis wrote:

 const in D guarantees that the object will not be mutated via that
 reference regardless of what that reference refers to.


We need to change that if we want things like composable containers that 
work with const. And I think it's a good thing to want. -- Andrei
Nov 15 2015
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 15 November 2015 at 17:38:10 UTC, Andrei Alexandrescu 
wrote:

 On 11/15/2015 10:09 AM, Jonathan M Davis wrote:

 const in D guarantees that the object will not be mutated via 
 that
 reference regardless of what that reference refers to.


 We need to change that if we want things like composable 
 containers that work with const. And I think it's a good thing 
 to want. -- Andrei


Basically, we have to decide between having physical const with 
the guarantees that it provides (but losing out on being able to 
use const in a _lot_ of places) and having a transitive version 
of C++'s const (which means losing out on the solid compiler 
guarantees).

The guarantees that we get with physical const are really nice, 
but yes, they do come at the cost of not being able to use const 
in a _lot_ cases. So, it could very well be that we'd better off 
losing physical const. And one thing to consider is that there 
are plenty of folks who mistakenly think that it's okay to cast 
away const and mutate an object as long as the object isn't 
actually immutable, so there's plenty of code out there that 
already does that. It almost certainly works, because the 
optimizations that the compiler can make based on const alone are 
extremely limited, but it _is_ undefined behavior, and if it's 
that easy for folks to misunderstand and end up relying on UB, 
maybe we should just change it so that it's defined behavior.

I don't know. I like physical const as it is, but it so often 
seems too limiting to actually be useful, which ultimately 
probably means that we need to change it (in order to take into 
account human behavior if nothing else, since const is clearly 
being misunderstood and misused as-is).

That being said, even if we make it defined behavior to mutate a 
mutable object via a const reference via casting, I think that 
having  mutable like you suggested would still be a good idea, 
because it would cover one of the primary use cases where casting 
would be required and eliminate the need for that cast and 
disallowing immutable where it would be violated if it were used, 
making such idioms safer.

The other major use case that I can think of would be lazy 
initialization, and  mutable doesn't seem like the appropriate 
thing for that, but maybe we can add something else for it if 
we're already loosening the restrictions/guarantees on const (I 
think that someone just created a DIP for that too, though I 
haven't looked at it yet).

Regardless, we need to be very careful about what we do with 
casts involving const because of how easy it is to screw up and 
mutate an immutable objects in the process.

- Jonathan M Davis
Nov 15 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Nov 15 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
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. And if bar is pure, and I 
didn't pass another reference to foo in via one of the function 
arguments, then I know that foo won't have been mutated by bar. 
The same goes if I foo was created inside the current function 
and had no chance to be assigned somewhere where bar could get at 
even if it weren't pure. It's only when an object gets passed 
around a bit that there's really even the possibility that it 
will be mutated by a function that treats it as const, and the 
combination of TLS and pure reduces that risk considerably. So, 
in general, you really can rely on a const object not being 
mutated when you call a const member function or even pass it to 
a function which takes it as const.

However, if we make it so that casting away const and mutating is 
defined behavior or allow any other kind of backdoor to const, 
then all bets are off. Without looking at the implementation of 
every function that an object gets passed to, you can't know 
whether it's actually being mutated or not even though it's 
const. So, where's a definite loss there. Putting backdoors into 
const costs us the guarantees that we get with const now. We go 
from treating const as physically const to treating it as 
logically const (and logically const can't actually be guaranteed 
by the compiler).

Now, that puts us in a place that's similar to C++, and that 
works, but it definitely does not provide the same guarantees 
that we have now and is worse in the cases where backdoors aren't 
needed.

- Jonathan M Davis
Nov 15 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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!

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.


Andrei
Nov 15 2015
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/15/2015 08:57 PM, 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;
 }
 ...



This is the exact exception he described i.e. "unless I have another, 
mutable reference to foo somewhere that bar somehow accessed."

(Also, 'bar' should be 'const'.)


 In other words, you truly need access to the implementation of getFoo()
 in order to claim anything about the changeability of stuff.


No, e.g., make either 'getFoo' or 'bar' pure.


 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. 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.
Nov 15 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/15/2015 03:17 PM, Timon Gehr wrote:

 On 11/15/2015 08:57 PM, 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;
 }
 ...



 This is the exact exception he described i.e. "unless I have another,
 mutable reference to foo somewhere that bar somehow accessed."


Nope. He doesn't have a reference; the implementation has 
surreptitiously, without the caller's knowledge.

Big difference! That means the modular typechecker cannot make any 
assumption about the immutability of that object.

Let me repeat: const is already as weak as some fear it might be. 
(Immutable is fine.)


 (Also, 'bar' should be 'const'.)


Right.


 In other words, you truly need access to the implementation of getFoo()
 in order to claim anything about the changeability of stuff.


 No, e.g., make either 'getFoo' or 'bar' pure.


Well but it's not. Keep the goalposts where they are. This is about 
"const". 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".


 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. Today. With no compiler bugs in sight.


 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.


Andrei
Nov 15 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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
}



 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.
Nov 15 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Nov 15 2015
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
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.
Nov 15 2015
prev sibling parent reply Marc =?UTF-8?B?U2Now7x0eg==?= <schuetzm gmx.net> writes:
On Monday, 16 November 2015 at 02:26:29 UTC, Andrei Alexandrescu 
wrote:

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


Glad to here that. I think the current transitive const system is 
really good and shouldn't be watered down beyond necessity. And a 
 mutable keyword, too, shouldn't just mean "immutability or 
const-ness end here", thus allowing any kind of mutation. What we 
actually need for immutable/const refcounting etc. is 
_non-observable mutation_, i.e. physical mutability, but without 
observable effects outside of the type's implementation (better 
yet, restricted to very short parts of it, just like  trusted).
Nov 16 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 08:51 AM, Marc Schütz wrote:

 On Monday, 16 November 2015 at 02:26:29 UTC, Andrei Alexandrescu wrote:

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


 Glad to here that. I think the current transitive const system is really
 good and shouldn't be watered down beyond necessity. And a  mutable
 keyword, too, shouldn't just mean "immutability or const-ness end here",
 thus allowing any kind of mutation. What we actually need for
 immutable/const refcounting etc. is _non-observable mutation_, i.e.
 physical mutability, but without observable effects outside of the
 type's implementation (better yet, restricted to very short parts of it,
 just like  trusted).


The challenge is proving that a mutation is not observable. Got an 
attack on that? -- Andrei
Nov 16 2015
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, 16 November 2015 at 14:45:35 UTC, Andrei Alexandrescu 
wrote:

 On 11/16/2015 08:51 AM, Marc Schütz wrote:

 On Monday, 16 November 2015 at 02:26:29 UTC, Andrei 
 Alexandrescu wrote:

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


 Glad to here that. I think the current transitive const system 
 is really
 good and shouldn't be watered down beyond necessity. And a 
  mutable
 keyword, too, shouldn't just mean "immutability or const-ness 
 end here",
 thus allowing any kind of mutation. What we actually need for
 immutable/const refcounting etc. is _non-observable mutation_, 
 i.e.
 physical mutability, but without observable effects outside of 
 the
 type's implementation (better yet, restricted to very short 
 parts of it,
 just like  trusted).


 The challenge is proving that a mutation is not observable. Got 
 an attack on that? -- Andrei


That would be a neat trick. As I recall, previous discussions on 
logical const concluded that there was no way to implement it in 
a way that guaranteed that it was actually logical const as 
opposed to just being mutated in spite of being const. But it 
would be _very_ cool if someone figured out how to do it.

Still, even without that guarantee, using something like  mutable 
rather than casting would be far safer - especially if the type 
system can guarantee that such an object can't be immutable.

- Jonathan M Davis
Nov 16 2015
prev sibling next sibling parent reply Lionello Lunesu <lionello lunesu.remove.com> writes:
On 16/11/15 22:45, Andrei Alexandrescu wrote:

 On 11/16/2015 08:51 AM, Marc Schütz wrote:

 On Monday, 16 November 2015 at 02:26:29 UTC, Andrei Alexandrescu wrote:

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


 Glad to here that. I think the current transitive const system is really
 good and shouldn't be watered down beyond necessity. And a  mutable
 keyword, too, shouldn't just mean "immutability or const-ness end here",
 thus allowing any kind of mutation. What we actually need for
 immutable/const refcounting etc. is _non-observable mutation_, i.e.
 physical mutability, but without observable effects outside of the
 type's implementation (better yet, restricted to very short parts of it,
 just like  trusted).


 The challenge is proving that a mutation is not observable. Got an
 attack on that? -- Andrei


Forgive me, I haven't followed the RC discussions closely, so I miss a 
lot of context. Feel free to point me to existing threads/articles.

If it's RC we want, then  mutable is an axe when what we need is a scalpel.

The non-observability comes from the fact the refcount is changed when 
the caller has lost its (const) reference and constness is a moot point. 
Changing refcount is fine now, provided the object is not immutable. As 
far as other outstanding const references go, these already expect 
changes to happen.

This is what makes refcount special and provably safe to mutate. As long 
as we can ensure the object is not immutable, the object is allowed to 
change its own refcount. But refcount needs to be special cased, 
somehow, or else we'll end up with some C++ like `mutable`.

Perhaps const-but-not-pure is the solution here. The object must be able 
to store (and have stored) a mutable reference, so it can use that 
reference to change the refcount. (This could be optimized to be a flag, 
since the mutable and const reference would refer to the same instance.) 
It means keeping track of const-but-mutable vs const-and-immutable 
references, and somehow telling the compiler that refcount is special.

L.
Nov 16 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 11:58 AM, Lionello Lunesu wrote:

 On 16/11/15 22:45, Andrei Alexandrescu wrote:

 On 11/16/2015 08:51 AM, Marc Schütz wrote:

 On Monday, 16 November 2015 at 02:26:29 UTC, Andrei Alexandrescu
 wrote:

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


 Glad to here that. I think the current transitive const system
 is really good and shouldn't be watered down beyond necessity.
 And a  mutable keyword, too, shouldn't just mean "immutability
 or const-ness end here", thus allowing any kind of mutation. What
 we actually need for immutable/const refcounting etc. is
 _non-observable mutation_, i.e. physical mutability, but without
 observable effects outside of the type's implementation (better
 yet, restricted to very short parts of it, just like  trusted).


 The challenge is proving that a mutation is not observable. Got an
  attack on that? -- Andrei


 Forgive me, I haven't followed the RC discussions closely, so I miss
 a lot of context. Feel free to point me to existing
 threads/articles.


The best place to start for absorbing context is look at the casts in
http://dpaste.dzfl.pl/52a3013efe34, understand the necessity of each,
and figure out how they can be either made legal or (preferably) eliminated.


 If it's RC we want, then  mutable is an axe when what we need is a
 scalpel.


There's more than RC in there.


Andrei
Nov 16 2015
prev sibling next sibling parent Observer <dummy dummy.com> writes:
On Monday, 16 November 2015 at 16:58:24 UTC, Lionello Lunesu 
wrote:

 If it's RC we want, then  mutable is an axe when what we need 
 is a scalpel.

 The non-observability comes from the fact the refcount is 
 changed when the caller has lost its (const) reference and 
 constness is a moot point. Changing refcount is fine now, 
 provided the object is not immutable. As far as other 
 outstanding const references go, these already expect changes 
 to happen.

 This is what makes refcount special and provably safe to 
 mutate. As long as we can ensure the object is not immutable, 
 the object is allowed to change its own refcount. But refcount 
 needs to be special cased, somehow, or else we'll end up with 
 some C++ like `mutable`.


I'm not a compiler or language-design guy, but something strikes
me as odd about this whole discussion.  It seems to me that a lot
of it depends on a presumption that one wants the refcount field
to be user-visible, and that therefore it must also have some
user-visible type and perhaps some attributes.  But at bottom,
doesn't a refcount field behave more like a vptr for a class
instance, which is there in the underlying storage model but is
not directly user-visible?  Or similar to whatever metadata is
used for the start/end pointers of a dynamic array?  As such, is
there any reason for a refcount to be user-visible in the first
place, other than to the compiler-internals implementor?  I have
to wonder whether a refcount field could be appended to the data
payload via some sort of  rc attribute instead of as an explicit
class/struct member, and perhaps referenced via some implicit
pseudo member when the field needs to be manipulated.  Then there
perhaps wouldn't need to be any requirement to define any new
kinds of storage categories for this field, in the same way that
there isn't an explicit storage category for a vptr field.

I could be all wet here with such ideas, but I'm just wondering 
...
Nov 16 2015
prev sibling parent reply Marc =?UTF-8?B?U2Now7x0eg==?= <schuetzm gmx.net> writes:
On Monday, 16 November 2015 at 16:58:24 UTC, Lionello Lunesu 
wrote:

 On 16/11/15 22:45, Andrei Alexandrescu wrote:

 The challenge is proving that a mutation is not observable. 
 Got an
 attack on that? -- Andrei


 Forgive me, I haven't followed the RC discussions closely, so I 
 miss a lot of context. Feel free to point me to existing 
 threads/articles.

 If it's RC we want, then  mutable is an axe when what we need 
 is a scalpel.


It has additional uses, though, e.g. memoizing and  lazy 
initialization of members.


 The non-observability comes from the fact the refcount is 
 changed when the caller has lost its (const) reference and 
 constness is a moot point. Changing refcount is fine now, 
 provided the object is not immutable. As far as other 
 outstanding const references go, these already expect changes 
 to happen.


Refcount also needs to change when you get an additional 
reference. But it is non-observable, because the caller can't 
access the refcount directly (or we could allow it, but as 
 system). The only potentially observable side-effect would be if 
the object is destroyed, but this only happens if there are no 
references left. Then the only way this can be achieved is if the 
destructor modifies state that is otherwise accessible (global, 
or by references), which however is not a problem, because the 
normal rules of const-ness apply to it.


 This is what makes refcount special and provably safe to 
 mutate. As long as we can ensure the object is not immutable, 
 the object is allowed to change its own refcount. But refcount 
 needs to be special cased, somehow, or else we'll end up with 
 some C++ like `mutable`.


But the point is that we _want_ to have refcounted immutables, 
too, not just refcounted consts.
Nov 17 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/17/2015 04:47 AM, Marc Schütz wrote:

 Refcount also needs to change when you get an additional reference. But
 it is non-observable, because the caller can't access the refcount
 directly (or we could allow it, but as  system). The only potentially
 observable side-effect would be if the object is destroyed, but this
 only happens if there are no references left. Then the only way this can
 be achieved is if the destructor modifies state that is otherwise
 accessible (global, or by references), which however is not a problem,
 because the normal rules of const-ness apply to it.


I think it would be very difficult to prove at the type system level 
that the reference count is not observable. Humanly, sure, what you say 
makes sense. For a static checker, I don't think that's an approachable 
angle. -- Andrei
Nov 17 2015
prev sibling parent reply Dicebot <public dicebot.lv> writes:
On Tuesday, 17 November 2015 at 09:47:24 UTC, Marc Schütz wrote:

 On Monday, 16 November 2015 at 16:58:24 UTC, Lionello Lunesu

 If it's RC we want, then  mutable is an axe when what we need 
 is a scalpel.


 It has additional uses, though, e.g. memoizing and  lazy 
 initialization of members.


Hiding memoization behind fake const is one of more unpleasant 
C++ multi-threading abominations I have encountered during my C++ 
says. Resulting races are so subtle (because only happen once) 
and so inevitable (because it is subconsciously reasoned about as 
physical const) that debugging them becomes real pain.

This thread is really scary because of that. It is pretty much 
saying that D attempt to rethink multi-threading data model that 
caused trouble in C++ has failed completely and we back to square 
one. Even if it isn't technical disaster, it is marketing one for 
sure.
Nov 17 2015
parent Marc =?UTF-8?B?U2Now7x0eg==?= <schuetzm gmx.net> writes:
On Tuesday, 17 November 2015 at 14:40:13 UTC, Dicebot wrote:

 On Tuesday, 17 November 2015 at 09:47:24 UTC, Marc Schütz wrote:

 On Monday, 16 November 2015 at 16:58:24 UTC, Lionello Lunesu

 If it's RC we want, then  mutable is an axe when what we need 
 is a scalpel.


 It has additional uses, though, e.g. memoizing and  lazy 
 initialization of members.


 Hiding memoization behind fake const is one of more unpleasant 
 C++ multi-threading abominations I have encountered during my 
 C++ says. Resulting races are so subtle (because only happen 
 once) and so inevitable (because it is subconsciously reasoned 
 about as physical const) that debugging them becomes real pain.

 This thread is really scary because of that. It is pretty much 
 saying that D attempt to rethink multi-threading data model 
 that caused trouble in C++ has failed completely and we back to 
 square one. Even if it isn't technical disaster, it is 
 marketing one for sure.


I don't think this is a concern for D, because we still have 
thread-awareness in the type system. We can distinguish between 
` mutable` and `shared  mutable`, just as we distinguish between 
`const` and `shared const`.
Nov 17 2015
prev sibling parent reply Marc =?UTF-8?B?U2Now7x0eg==?= <schuetzm gmx.net> writes:
On Monday, 16 November 2015 at 14:45:35 UTC, Andrei Alexandrescu 
wrote:

 The challenge is proving that a mutation is not observable. Got 
 an attack on that? -- Andrei


Here's what I wrote a few days ago, without having read the 
current discussion, so it's not a perfect fit:
http://wiki.dlang.org/DIP85

For the case of lazy initialization, assigning a member exactly 
once is safe, if it hasn't been read and returned before. The 
compiler can check this by automatically inserting a few asserts. 
The rules in the DIP aren't completely water-tight, but they are 
a good approximation.

But for members that have to be mutated several times (e.g. 
refcount), this obviously isn't useful. I think we can make this 
 system, thereby forcing implementors to write  trusted code and 
(hopefully) consider the consequences thoroughly. But the 
compiler can also assist with that. For example, it could detect 
whether a "privately mutable" value, or something depending on 
it, is returned from the function, and reject that.

Maybe the implementation for the two kinds of use-cases (write 
once vs write multiple times) can be unified, too.
Nov 17 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/17/2015 04:43 AM, Marc Schütz wrote:

 On Monday, 16 November 2015 at 14:45:35 UTC, Andrei Alexandrescu wrote:

 The challenge is proving that a mutation is not observable. Got an
 attack on that? -- Andrei


 Here's what I wrote a few days ago, without having read the current
 discussion, so it's not a perfect fit:
 http://wiki.dlang.org/DIP85

 For the case of lazy initialization, assigning a member exactly once is
 safe, if it hasn't been read and returned before. The compiler can check
 this by automatically inserting a few asserts. The rules in the DIP
 aren't completely water-tight, but they are a good approximation.

 But for members that have to be mutated several times (e.g. refcount),
 this obviously isn't useful. I think we can make this  system, thereby
 forcing implementors to write  trusted code and (hopefully) consider the
 consequences thoroughly. But the compiler can also assist with that. For
 example, it could detect whether a "privately mutable" value, or
 something depending on it, is returned from the function, and reject that.

 Maybe the implementation for the two kinds of use-cases (write once vs
 write multiple times) can be unified, too.


Thanks for the DIP, I saw it since a couple days ago. 
Dynamically-verified lazy initialization is difficult, but doesn't cover:

1. Reference count updates (as you mention)

2. The reference to the allocator is essentially a mutable part of an 
object that's otherwise constant.

So it seems to be DIP85 is solving a quite narrow problem, and one that 
doesn't address the issue at hand.


Andrei
Nov 17 2015
parent reply Marc =?UTF-8?B?U2Now7x0eg==?= <schuetzm gmx.net> writes:
On Tuesday, 17 November 2015 at 14:29:53 UTC, Andrei Alexandrescu 
wrote:

 Thanks for the DIP, I saw it since a couple days ago. 
 Dynamically-verified lazy initialization is difficult, but 
 doesn't cover:

 1. Reference count updates (as you mention)

 2. The reference to the allocator is essentially a mutable part 
 of an object that's otherwise constant.

 So it seems to be DIP85 is solving a quite narrow problem, and 
 one that doesn't address the issue at hand.


I know, I wrote the DIP before I read this thread, and it was 
originally only supposed to address lazy initialization 
specifically. Maybe some of the ideas can be reused for a more 
general un-const concept, though.
Nov 17 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/17/15 1:01 PM, Marc Schütz wrote:

 On Tuesday, 17 November 2015 at 14:29:53 UTC, Andrei Alexandrescu wrote:

 Thanks for the DIP, I saw it since a couple days ago.
 Dynamically-verified lazy initialization is difficult, but doesn't cover:

 1. Reference count updates (as you mention)

 2. The reference to the allocator is essentially a mutable part of an
 object that's otherwise constant.

 So it seems to be DIP85 is solving a quite narrow problem, and one
 that doesn't address the issue at hand.


 I know, I wrote the DIP before I read this thread, and it was originally
 only supposed to address lazy initialization specifically. Maybe some of
 the ideas can be reused for a more general un-const concept, though.


Yes, it's a great building block for something more general. It is well 
done. -- Andrei
Nov 17 2015
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Nov 15 2015
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/15/2015 06:38 PM, Andrei Alexandrescu wrote:

 On 11/15/2015 10:09 AM, Jonathan M Davis wrote:

 const in D guarantees that the object will not be mutated via that
 reference regardless of what that reference refers to.


 We need to change that if we want things like composable containers that
 work with const. And I think it's a good thing to want. -- Andrei


I don't think so.
Nov 15 2015
parent reply Dicebot <public dicebot.lv> writes:
On Sunday, 15 November 2015 at 19:44:27 UTC, Timon Gehr wrote:

 On 11/15/2015 06:38 PM, Andrei Alexandrescu wrote:

 On 11/15/2015 10:09 AM, Jonathan M Davis wrote:

 const in D guarantees that the object will not be mutated via 
 that
 reference regardless of what that reference refers to.


 We need to change that if we want things like composable 
 containers that
 work with const. And I think it's a good thing to want. -- 
 Andrei


 I don't think so.


I support this statement.
Nov 15 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/15/2015 02:47 PM, Dicebot wrote:

 On Sunday, 15 November 2015 at 19:44:27 UTC, Timon Gehr wrote:

 On 11/15/2015 06:38 PM, Andrei Alexandrescu wrote:

 On 11/15/2015 10:09 AM, Jonathan M Davis wrote:

 const in D guarantees that the object will not be mutated via that
 reference regardless of what that reference refers to.


 We need to change that if we want things like composable containers that
 work with const. And I think it's a good thing to want. -- Andrei


 I don't think so.


 I support this statement.


Just to clarify - is that referring to the part "We need to change that 
if we want things like composable containers that work with const." or 
to the "I think it's a good thing to want" part? -- Andrei
Nov 15 2015
parent reply Dicebot <public dicebot.lv> writes:
On Sunday, 15 November 2015 at 19:51:09 UTC, Andrei Alexandrescu 
wrote:

 Just to clarify - is that referring to the part "We need to 
 change that if we want things like composable containers that 
 work with const." or to the "I think it's a good thing to want" 
 part? -- Andrei


Second part. I don't see a case for const containers at all. 
Fully immutable functional style ones - sure, I have actually 
experimented implementing cache this way in 
https://github.com/Dicebot/mood/blob/master/source/mood/storage/generic_cache.d
(thing that powers blog.dicebot.lv). But what would you use const containers
for? Mixing mutable and immutable elements in one container? That sounds like a
source of much trouble.
Nov 15 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/15/2015 03:11 PM, Dicebot wrote:

 On Sunday, 15 November 2015 at 19:51:09 UTC, Andrei Alexandrescu wrote:

 Just to clarify - is that referring to the part "We need to change
 that if we want things like composable containers that work with
 const." or to the "I think it's a good thing to want" part? -- Andrei


 Second part. I don't see a case for const containers at all. Fully
 immutable functional style ones - sure, I have actually experimented
 implementing cache this way in
 https://github.com/Dicebot/mood/blob/master/source/mood/storage/generic_cache.d
 (thing that powers blog.dicebot.lv). But what would you use const
 containers for?


Passing arguments to functions that aren't supposed to change the 
containers. -- Andrei
Nov 15 2015
parent reply Dicebot <public dicebot.lv> writes:
On Sunday, 15 November 2015 at 21:00:40 UTC, Andrei Alexandrescu 
wrote:

 On 11/15/2015 03:11 PM, Dicebot wrote:

 Second part. I don't see a case for const containers at all. 
 Fully
 immutable functional style ones - sure, I have actually 
 experimented
 implementing cache this way in
 https://github.com/Dicebot/mood/blob/master/source/mood/storage/generic_cache.d
 (thing that powers blog.dicebot.lv). But what would you use 
 const
 containers for?


 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.
Nov 15 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/15/2015 04:45 PM, Dicebot wrote:

 On Sunday, 15 November 2015 at 21:00:40 UTC, Andrei Alexandrescu wrote:

 On 11/15/2015 03:11 PM, Dicebot wrote:

 Second part. I don't see a case for const containers at all. Fully
 immutable functional style ones - sure, I have actually experimented
 implementing cache this way in
 https://github.com/Dicebot/mood/blob/master/source/mood/storage/generic_cache.d

 (thing that powers blog.dicebot.lv). But what would you use const
 containers for?


 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.


This illustrates a simple procedural problem. The entire point of my 
posting a simple example of a complete container was to avoid 
hypotheticals such as this. The code is there and shows that no, 
physical const does not suffice. At least I don't know how to do it. If 
you think it does there's one way to show it, it's easy - write the code 
that does it.

We could sit on our testes all day long, speculate how things ought to 
work, and feel awfully smart in the process. It's very easy to do. Hell, 
I've done it more than too many times. What's more difficult is have a 
positive, constructive approach that builds on a weak solution to 
improve it. This is the kind of dialog we need to foster.


Andrei
Nov 15 2015
parent reply Dicebot <public dicebot.lv> writes:
On Monday, 16 November 2015 at 00:00:18 UTC, Andrei Alexandrescu 
wrote:

 This illustrates a simple procedural problem. The entire point 
 of my posting a simple example of a complete container was to 
 avoid hypotheticals such as this. The code is there and shows 
 that no, physical const does not suffice. At least I don't know 
 how to do it. If you think it does there's one way to show it, 
 it's easy - write the code that does it.

 We could sit on our testes all day long, speculate how things 
 ought to work, and feel awfully smart in the process. It's very 
 easy to do. Hell, I've done it more than too many times. What's 
 more difficult is have a positive, constructive approach that 
 builds on a weak solution to improve it. This is the kind of 
 dialog we need to foster.


Sadly, design I would love to see also doesn't seem to be 
implementable but because of different issue - missing scope 
control. I gave a quick go to implement something that shows my 
desired semantics - 
https://gist.github.com/mihails-strasuns-sociomantic/1d7529eef723b1132564 (only
essential functionality to show stuff). As you may see it is totally different
from your initial proposal - this is why making constructive feedback is rather
hard :)

But chosing between breaking physical const via  mutable and 
waiting until we finally get lond wanted scope control tools I am 
very much in favor of the latter.
Nov 16 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/17/2015 04:50 AM, Dicebot wrote:

 ...
 https://gist.github.com/mihails-strasuns-sociomantic/1d7529eef723b1132564


Again, this idiom does not do anything:

static assert(
     !is(typeof(this) == immutable),
     "PersistentList itself must be mutable for allocation / RC purposes"
);

The condition is always true.

Anyway, any design that does not allow e.g. nested lists is inadequate IMO.
Nov 17 2015
parent reply Dicebot <public dicebot.lv> writes:
On Tuesday, 17 November 2015 at 12:32:03 UTC, Timon Gehr wrote:

 On 11/17/2015 04:50 AM, Dicebot wrote:

 ...
 https://gist.github.com/mihails-strasuns-sociomantic/1d7529eef723b1132564


 Again, this idiom does not do anything:

 static assert(
     !is(typeof(this) == immutable),
     "PersistentList itself must be mutable for allocation / RC 
 purposes"
 );

 The condition is always true.


Acknowledged, I have simply copied it from original sample to 
show that intention os the same. It isn't as critical in my case 
though as the code simply won't compile as immutable (no const 
casts).


 Anyway, any design that does not allow e.g. nested lists is 
 inadequate IMO.


But here I have to disagree. There simply isn't anything generic 
in immutable containers with RC, each requires own tweaked 
solution. It all works nice with GC because all memory tracking 
becomes exclusively external - trying to ignore and hide that 
fact makes no sense to me.

Main use case for such containers is efficient thread sharing and 
that totally justifies specialized container (or even allocator) 
for each dataset.
Nov 17 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 11/17/2015 02:38 PM, Dicebot wrote:

 Anyway, any design that does not allow e.g. nested lists is inadequate
 IMO.


 But here I have to disagree. There simply isn't anything generic in
 immutable containers with RC, each requires own tweaked solution. It all
 works nice with GC because all memory tracking becomes exclusively
 external - trying to ignore and hide that fact makes no sense to me.

 Main use case for such containers is efficient thread sharing and that
 totally justifies specialized container (or even allocator) for each
 dataset.


Persistent containers are useful even if only a single thread is 
involved, as they can speed up some algorithms.

Having the library provide List!T, but not List!(List!T) is a ridiculous 
situation. More generally, types shouldn't need to satisfy any 
additional constraints (beyond abstract container specific ones) to be 
allowed to place their instances in containers.

I don't think the cases where writing a new specialized version from 
scratch is justified are what the new container module will be about.
Nov 17 2015
parent reply Dicebot <public dicebot.lv> writes:
On Tuesday, 17 November 2015 at 23:50:13 UTC, Timon Gehr wrote:

 Main use case for such containers is efficient thread sharing 
 and that
 totally justifies specialized container (or even allocator) 
 for each
 dataset.


 Persistent containers are useful even if only a single thread 
 is involved, as they can speed up some algorithms.

 Having the library provide List!T, but not List!(List!T) is a 
 ridiculous situation. More generally, types shouldn't need to 
 satisfy any additional constraints (beyond abstract container 
 specific ones) to be allowed to place their instances in 
 containers.


In my opinion it is perfectly reasonable to require GC for such 
"casual" usage and require narrow specialization from RC based 
solutions. Physical immutability requires external memory 
tracking - GC provides that naturally and trying to ignore that 
fact with RC model feels like cheating yourself to me.

It may be possible to provide more generic solution if you place 
reference counting into allocator itself. But I trust Andrei 
expertise in this domain so if he decided to not pursue this 
approach there must be good reasons.


 I don't think the cases where writing a new specialized version 
 from scratch is justified are what the new container module 
 will be about.


Yes, indeed. That is why I don't think non-GC version of such 
containers belongs to such standard package at all. It is not 
worth the proposed costs.
Nov 21 2015
parent reply Dicebot <public dicebot.lv> writes:
On Sunday, 22 November 2015 at 00:38:19 UTC, Dicebot wrote:

 In my opinion it is perfectly reasonable to require GC for such 
 "casual" usage and require narrow specialization from RC based 
 solutions. Physical immutability requires external memory 
 tracking - GC provides that naturally and trying to ignore that 
 fact with RC model feels like cheating yourself to me.


On a related topic - are there any pure functional languages that 
don't use GC internally? Those could be worth looking at.
Nov 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/21/2015 07:48 PM, Dicebot wrote:

 On Sunday, 22 November 2015 at 00:38:19 UTC, Dicebot wrote:

 In my opinion it is perfectly reasonable to require GC for such
 "casual" usage and require narrow specialization from RC based
 solutions. Physical immutability requires external memory tracking -
 GC provides that naturally and trying to ignore that fact with RC
 model feels like cheating yourself to me.


 On a related topic - are there any pure functional languages that don't
 use GC internally? Those could be worth looking at.


I don't know of any, but that's beside the point. RC can be integrated 
with purity relatively easily if it's done automatically by the 
compiler. The problem is library-level RC does not work with 
immutability. -- Andrei
Nov 22 2015
parent reply Dicebot <public dicebot.lv> writes:
On Sunday, 22 November 2015 at 15:25:28 UTC, Andrei Alexandrescu 
wrote:

 I don't know of any, but that's beside the point. RC can be 
 integrated with purity relatively easily if it's done 
 automatically by the compiler. The problem is library-level RC 
 does not work with immutability. -- Andrei


Not entirely. If there are any one can have a look how compiler 
organizes rc management internally there and what are current D 
limitations of doing so in a library. But I don't know any either 
and suspect it isn't coincidental.
Nov 22 2015
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Monday, 23 November 2015 at 04:40:08 UTC, Dicebot wrote:

 Not entirely. If there are any one can have a look how compiler 
 organizes rc management internally there and what are current D 
 limitations of doing so in a library. But I don't know any 
 either and suspect it isn't coincidental.


They exist:

1. reactive programming language that don't do allocation

2. languages that forbid circular references

3. languages that allow memory leaks in the case of circular 
references

In addition you have runtimes that use region allocators.

However, keep in mind that mark-sweep was invented for Lisp.
Nov 23 2015
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Nov 15 2015
next sibling parent reply rsw0x <anonymous anonymous.com> writes:
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
Nov 15 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Nov 16 2015
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, 16 November 2015 at 08:18:55 UTC, Jonathan M Davis 
wrote:

 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.


Actually, with regards to immutable, it looks like you can 
already copy immutable objects with postblit constructors. You 
just can't copy it and get a mutable value out of it. But copying 
and creating another immutable value or a const value both work 
just fine. So, it looks like the only thing we're missing with 
regards to immutable and postblits is the ability to get a 
mutable copy, but that's not really much of a loss as far as I 
can think of at the moment.

So, really it's just the issue with const and postblit that 
really needs fixing, and allowing the mutation of const to be 
defined behavior when the underlying object isn't immutable could 
give us the out we need to fix that problem.

- Jonathan M Davis
Nov 16 2015
prev sibling parent reply Joseph Cassman <jc7919 outlook.com> writes:
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
Nov 16 2015
parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
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.
Nov 16 2015
parent reply Atila Neves <atila.neves gmail.com> writes:
On Monday, 16 November 2015 at 09:42:43 UTC, Ola Fosheim Grøstad 
wrote:

 On Monday, 16 November 2015 at 09:04:33 UTC, Joseph Cassman 
 wrote:

 [...]


 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.


You described immutable, not const. If one thread has a const 
reference, it's entirely possible another thread has a mutable 
reference.

Atila
Nov 16 2015
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, 16 November 2015 at 14:08:23 UTC, Atila Neves wrote:

 You described immutable, not const. If one thread has a const 
 reference, it's entirely possible another thread has a mutable 
 reference.


Only if it's shared, or you've screwed up with casting and ended 
up with an object which is actually shared being treated as TLS. 
A const, non-shared object can't possibly be mutated while you're 
doing stuff to it unless that same code somehow has access to a 
mutable reference to the same data. And in most cases 
(particularly if you're using pure heavily), it won't have access 
to any other references to the same data, so you can usually rely 
on a const object not being mutated while you operate on it.

- Jonathan M Davis
Nov 16 2015
prev sibling parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Monday, 16 November 2015 at 14:08:23 UTC, Atila Neves wrote:

 You described immutable, not const. If one thread has a const 
 reference, it's entirely possible another thread has a mutable 
 reference.


Are you sure that this is a well defined situation? What is the 
point of having "const" if "shared const" is the exact same thing?

Immutable should never ever change for any reason, because the 
compiler should be able to cache derived values.
Nov 16 2015
prev sibling parent deadalnix <deadalnix gmail.com> writes:
On Sunday, 15 November 2015 at 20:11:02 UTC, Dicebot wrote:

 On Sunday, 15 November 2015 at 19:51:09 UTC, Andrei 
 Alexandrescu wrote:

 Just to clarify - is that referring to the part "We need to 
 change that if we want things like composable containers that 
 work with const." or to the "I think it's a good thing to 
 want" part? -- Andrei


 Second part. I don't see a case for const containers at all. 
 Fully immutable functional style ones - sure, I have actually 
 experimented implementing cache this way in 
 https://github.com/Dicebot/mood/blob/master/source/mood/sto
age/generic_cache.d (thing that powers blog.dicebot.lv). But what would you use
const containers for? Mixing mutable and immutable elements in one container?
That sounds like a source of much trouble.


For the variance. If you wan't write in the container, you make 
make it so that

ConstContainer<B> implicitly convert to ConstContainer<A> if B 
inherit from A.

You can have code that accept mutable and const container as 
well, which is useful, because you can cram immutable container 
in the ro section.
Nov 16 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/15/2015 09:34 AM, Dicebot wrote:

 On Sunday, 15 November 2015 at 14:23:05 UTC, Jonathan M Davis wrote:

 As I mentioned, he's okay with changing the language to make the
 casts well defined. -- Andrei


 Well, that's a big change, since it pretty much means that D's const
 isn't physical const anymore, and Walter has been _very_ insistent
 about that in the past - to the point that he's argued that C++'s
 const is outright useless because it isn't physical const. If casting
 away const and mutating is well-defined behavior, then we basically
 have C++'s const except that it's transitive ...


 Casting away _const_ is already legal if programmer can himself
 guarantee underlying object has mutable origin (i.e. not available via
 immutable reference), by the very definition of const. It is casting
 away immutable and mutating that is strictly UB.


Correct. I'm not sure whether that's clarified in the language 
documentation yet. -- Andrei
Nov 15 2015
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 15 November 2015 at 14:54:51 UTC, Andrei Alexandrescu 
wrote:

 On 11/15/2015 09:34 AM, Dicebot wrote:

 On Sunday, 15 November 2015 at 14:23:05 UTC, Jonathan M Davis 
 wrote:

 As I mentioned, he's okay with changing the language to make 
 the
 casts well defined. -- Andrei


 Well, that's a big change, since it pretty much means that 
 D's const
 isn't physical const anymore, and Walter has been _very_ 
 insistent
 about that in the past - to the point that he's argued that 
 C++'s
 const is outright useless because it isn't physical const. If 
 casting
 away const and mutating is well-defined behavior, then we 
 basically
 have C++'s const except that it's transitive ...


 Casting away _const_ is already legal if programmer can himself
 guarantee underlying object has mutable origin (i.e. not 
 available via
 immutable reference), by the very definition of const. It is 
 casting
 away immutable and mutating that is strictly UB.


 Correct. I'm not sure whether that's clarified in the language 
 documentation yet. -- Andrei


Quite the opposite in fact. Walter recently approved an update to 
the spec which clarified that it _is_ undefined behavior to cast 
away const and mutate even if the object being referred to isn't 
immutable underneath the hood:

https://github.com/D-Programming-Language/dlang.org/pull/1047

And from what I've seen, Walter has always been adamant that D's 
const is physical const and that casting away const and mutating 
is undefined behavior, arguing that if it weren't, it would be 
like C++'s const and that C++'s const is pretty much useless, 
because it doesn't provide actual guarantees. So, if he's now 
willing to have casting away const and mutating be well-defined 
behavior, that's a big shift.

- Jonathan M Davis
Nov 15 2015
parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Sunday, 15 November 2015 at 15:14:38 UTC, Jonathan M Davis 
wrote:

 mutating is undefined behavior, arguing that if it weren't, it 
 would be like C++'s const and that C++'s const is pretty much 
 useless, because it doesn't provide actual guarantees.


Hm, I think C++ const requires that the object isn't modified, 
but you can cast away const in order to call functions that are 
erroneously missing a const specifier.

C++'s solution is to have a "mutable" specifier for fields like 
that can be mutated without affecting the type's state externally 
(mutexes etc).

 From the C++ faq:

«NOTE: there is an extremely unlikely error that can occur with 
const_cast. It only happens when three very rare things are 
combined at the same time: a data member that ought to be mutable 
(such as is discussed above), a compiler that doesn’t support the 
mutable keyword and/or a programmer who doesn’t use it, and an 
object that was originally defined to be const (as opposed to a 
normal, non-const object that is pointed to by a 
pointer-to-const). Although this combination is so rare that it 
may never happen to you, if it ever did happen, the code may not 
work (the Standard says the behavior is undefined).»

So const_casting away const followed by mutation is undefined 
behaviour.
Nov 15 2015
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, 15 November 2015 at 18:26:56 UTC, Ola Fosheim Grøstad 
wrote:

 On Sunday, 15 November 2015 at 15:14:38 UTC, Jonathan M Davis 
 wrote:

 mutating is undefined behavior, arguing that if it weren't, it 
 would be like C++'s const and that C++'s const is pretty much 
 useless, because it doesn't provide actual guarantees.


 Hm, I think C++ const requires that the object isn't modified, 
 but you can cast away const in order to call functions that are 
 erroneously missing a const specifier.

 C++'s solution is to have a "mutable" specifier for fields like 
 that can be mutated without affecting the type's state 
 externally (mutexes etc).

 From the C++ faq:

 «NOTE: there is an extremely unlikely error that can occur with 
 const_cast. It only happens when three very rare things are 
 combined at the same time: a data member that ought to be 
 mutable (such as is discussed above), a compiler that doesn’t 
 support the mutable keyword and/or a programmer who doesn’t use 
 it, and an object that was originally defined to be const (as 
 opposed to a normal, non-const object that is pointed to by a 
 pointer-to-const). Although this combination is so rare that it 
 may never happen to you, if it ever did happen, the code may 
 not work (the Standard says the behavior is undefined).»

 So const_casting away const followed by mutation is undefined 
 behaviour.


As I understand it, the only time that casting away const and 
mutating is undefined behavior in C++ is when the object was 
specifically constructed as const such that no mutable reference 
to it even can exist without a cast - which would be the bit from 
that quote where it talks about "an object that was originally 
defined to be const". And in general, _very_ few objects are 
likely to be constructed as const. So, in general, in C++, you 
can cast away const and mutate as much as you'd like. It's just 
that that's generally considered bad practice, and folks usually 
behave themselves and try to use const as a "logical" const such 
that no member variables which would normally be considered part 
of the state of the object have a different value after a const 
function call than what they had before the function call. So, 
for the most part, const works by convention.

- Jonathan M Davis
Nov 15 2015
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Sunday, 15 November 2015 at 18:36:20 UTC, Jonathan M Davis 
wrote:

 was originally defined to be const". And in general, _very_ few 
 objects are likely to be constructed as const.


It is common in constructors.


 So, in general, in C++, you can cast away const and mutate as 
 much as you'd like.


Well, since it is "shared const", the compiler cannot assume that 
another thread does not write to the object without whole program 
analysis. Which leaves the compiler writer with less incentive to 
do things differently because the object is const locally. Not 
sure if the FAQ reflects the standard or what current compilers 
do.

I would expect it to change in the future though, since whole 
program analysis is becoming more and more realistic. The FAQ 
also end with this statement:

«Please don’t write saying version X of compiler Y on machine Z 
lets you change a non-mutable member of a const object. I don’t 
care — it is illegal according to the language and your code will 
probably fail on a different compiler or even a different version 
(an upgrade) of the same compiler. Just say no. Use mutable 
instead. Write code that is guaranteed to work, not code that 
doesn’t seem to break.»
Nov 15 2015
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/15/15 9:54 AM, Andrei Alexandrescu wrote:

 On 11/15/2015 09:34 AM, Dicebot wrote:

 On Sunday, 15 November 2015 at 14:23:05 UTC, Jonathan M Davis wrote:

 As I mentioned, he's okay with changing the language to make the
 casts well defined. -- Andrei


 Well, that's a big change, since it pretty much means that D's const
 isn't physical const anymore, and Walter has been _very_ insistent
 about that in the past - to the point that he's argued that C++'s
 const is outright useless because it isn't physical const. If casting
 away const and mutating is well-defined behavior, then we basically
 have C++'s const except that it's transitive ...


 Casting away _const_ is already legal if programmer can himself
 guarantee underlying object has mutable origin (i.e. not available via
 immutable reference), by the very definition of const. It is casting
 away immutable and mutating that is strictly UB.


 Correct. I'm not sure whether that's clarified in the language
 documentation yet. -- Andrei


I argued this way, and eventually lost. I don't think it's feasible to 
have a const that can be cast away, and have optimizations based on 
const or pure.

See this discussion:

forum.dlang.org/post/riiehqozpkyluhhifwha forum.dlang.org

One thing, however, is that if you can mark an island of space within an 
object as ALWAYS mutable, the compiler can know this and avoid 
optimizing away access to those pieces. It would have to be clearly 
marked as such, so the optimizations on non-marked data could still happen.

I think it could be done, because logical const is possible via a global 
lookup table. Any time you go through a cast, however, this could easily 
break down. I hate to say it, but you would likely need another modifier 
like "tainted const" or something in order for that to work.

-Steve
Nov 16 2015
parent reply Marc =?UTF-8?B?U2Now7x0eg==?= <schuetzm gmx.net> writes:
On Monday, 16 November 2015 at 17:12:06 UTC, Steven Schveighoffer 
wrote:

 One thing, however, is that if you can mark an island of space 
 within an object as ALWAYS mutable, the compiler can know this 
 and avoid optimizing away access to those pieces. It would have 
 to be clearly marked as such, so the optimizations on 
 non-marked data could still happen.


Yes, that's a necessity, simply to stop the compiler from 
applying breaking optimizations. However, then we would lose the 
guarantees immutable provides, in particular implicit sharing, 
and the implications for purity. That's why this mutability needs 
to be restricted, so that it has no observable effects.


 I think it could be done, because logical const is possible via 
 a global lookup table. Any time you go through a cast, however, 
 this could easily break down.


That's a really good argument: We don't actually introduce new 
semantics, we only want make existing techniques more accessible 
and efficient.
Nov 17 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 11/17/2015 10:54 AM, Marc Schütz wrote:

 On Monday, 16 November 2015 at 17:12:06 UTC, Steven Schveighoffer wrote:

 ...
 I think it could be done, because logical const is possible via a
 global lookup table. Any time you go through a cast, however, this
 could easily break down.


 That's a really good argument: We don't actually introduce new
 semantics, we only want make existing techniques more accessible and
 efficient.


That's only strictly true if access to  mutable members is impure.
One also needs to be careful about 'shared'.
Nov 17 2015
prev sibling parent reply deadalnix <deadalnix gmail.com> writes:
On Sunday, 15 November 2015 at 12:56:27 UTC, Andrei Alexandrescu 
wrote:

 On 11/14/2015 05:49 PM, Timon Gehr wrote:

 List uses RC internally. I don't think the UB casts will stay 
 for the
 final version, unless you are willing to completely dilute the 
 meaning
 of const in ways that Walter has explicitly expressed will not 
 be done
 in the past.


 As I mentioned, he's okay with changing the language to make 
 the casts well defined. -- Andrei


Ok Here is what I propose as a spec. This is rough brain dump, 
but that is something I think can be a good start.

There are mutable data that are thread local and immutable data 
that are shared. const is a wildcard type qualifier that can 
refers to mutable or immutable data.

immutable is supposed to be effectively immutable. This means 
that the compiler is allowed to store these data in ro segments 
and optimize redundant loads without having to prove that no 
aliasing write occur in between.

One can cast away const or immutable. It is a  system operation 
and this cast needs to be explicit.

If the underlying data is in ro segment, any write is effectively 
undefined behavior (most likely a fault).
If the underlying data is allocated on the head (using the GC or 
malloc for instance) then writing to it will effectively update 
the underlying memory.

Any read from a const or immutable reference after these write 
can is undefined.
Granted the write was not UB :
1/ Any read from a mutable reference in another thread is 
undefined behavior unless the writing thread release after write 
and the reading one acquire (or any stronger memory barrier).
2/ Any read from a mutable reference in the same thread will see 
the updates in a sequentially consistent manner.

Sounds good ? This definitively allow to do RC for 
const/immutable without throwing away optimization opportunities.
Nov 16 2015
parent deadalnix <deadalnix gmail.com> writes:
On Tuesday, 17 November 2015 at 01:58:54 UTC, deadalnix wrote:

 On Sunday, 15 November 2015 at 12:56:27 UTC, Andrei 
 Alexandrescu wrote:

 On 11/14/2015 05:49 PM, Timon Gehr wrote:

 List uses RC internally. I don't think the UB casts will stay 
 for the
 final version, unless you are willing to completely dilute 
 the meaning
 of const in ways that Walter has explicitly expressed will 
 not be done
 in the past.


 As I mentioned, he's okay with changing the language to make 
 the casts well defined. -- Andrei


 Ok Here is what I propose as a spec. This is rough brain dump, 
 but that is something I think can be a good start.

 There are mutable data that are thread local and immutable data 
 that are shared. const is a wildcard type qualifier that can 
 refers to mutable or immutable data.

 immutable is supposed to be effectively immutable. This means 
 that the compiler is allowed to store these data in ro segments 
 and optimize redundant loads without having to prove that no 
 aliasing write occur in between.

 One can cast away const or immutable. It is a  system operation 
 and this cast needs to be explicit.

 If the underlying data is in ro segment, any write is 
 effectively undefined behavior (most likely a fault).
 If the underlying data is allocated on the head (using the GC 
 or malloc for instance) then writing to it will effectively 
 update the underlying memory.

 Any read from a const or immutable reference after these write 
 can is undefined.
 Granted the write was not UB :
 1/ Any read from a mutable reference in another thread is 
 undefined behavior unless the writing thread release after 
 write and the reading one acquire (or any stronger memory 
 barrier).
 2/ Any read from a mutable reference in the same thread will 
 see the updates in a sequentially consistent manner.

 Sounds good ? This definitively allow to do RC for 
 const/immutable without throwing away optimization 
 opportunities.


Just quoting myself. In case someone is interested...
Nov 17 2015
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/13/2015 06:10 PM, Andrei Alexandrescu wrote:
[snip]

Thanks all for the feedback. I've uploaded an updated version to 
http://dpaste.dzfl.pl/52a3013efe34. It doesn't use "inout", but doesn't 
duplicate code either; instead, it relies on private internal functions 
to do the deed.

While revising feedback I realized I'd missed Steve's version that works 
with inout: http://dpaste.dzfl.pl/3fbc786a50c1. It works and the 
inout-related parts don't look difficult; the only thing is making sure 
the right incantations are in place, and that's the difficult part.

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.


Andrei
Nov 15 2015
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Nov 15 2015
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/15/15 2:09 PM, Andrei Alexandrescu wrote:

 On 11/13/2015 06:10 PM, Andrei Alexandrescu wrote:
 [snip]

 Thanks all for the feedback. I've uploaded an updated version to
 http://dpaste.dzfl.pl/52a3013efe34. It doesn't use "inout", but doesn't
 duplicate code either; instead, it relies on private internal functions
 to do the deed.


This still doesn't compile for me.


 While revising feedback I realized I'd missed Steve's version that works
 with inout: http://dpaste.dzfl.pl/3fbc786a50c1. It works and the
 inout-related parts don't look difficult; the only thing is making sure
 the right incantations are in place, and that's the difficult part.


I would say the difficult part is figuring out the incantations from the 
given error messages. When you are depending on something to compile 
because it can call a template function, it's often difficult to figure 
out where it went wrong. The error messages are frequently unhelpful.

inout is actually pretty simple to use. It has a couple of severe 
limitations that make it difficult to work with in certain situations -- 
one of them being composition (you can't compose a type with inout 
members). We can work on fixing these problems.


 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.


I disagree. inout is no more complex than const in most cases. In my 
experience changing to inout is simply changing the term "const" to 
"inout", and everything pretty much works. This was my experience when 
updating dcollections after inout was finally made to work.

I'm going to work on writing an article about inout. It frequently 
confuses the shit out of everyone who uses it, and I don't think it should.

-Steve
Nov 16 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/16/2015 11:58 AM, Steven Schveighoffer wrote:

 On 11/15/15 2:09 PM, Andrei Alexandrescu wrote:

 On 11/13/2015 06:10 PM, Andrei Alexandrescu wrote:
 [snip]

 Thanks all for the feedback. I've uploaded an updated version to
 http://dpaste.dzfl.pl/52a3013efe34. It doesn't use "inout", but doesn't
 duplicate code either; instead, it relies on private internal functions
 to do the deed.


 This still doesn't compile for me.


You need my emplace bugfixes, so get the latest toolchain. -- Andrei
Nov 16 2015
prev sibling next sibling parent reply Dicebot <public dicebot.lv> writes:
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?
Nov 15 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 11/15/2015 03:23 PM, 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?


I don't think we can make that work with current language semantics. 
I'll post more about that soonish. -- Andrei
Nov 15 2015
prev sibling parent Marc =?UTF-8?B?U2Now7x0eg==?= <schuetzm gmx.net> writes:
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()`).
Nov 16 2015
prev sibling parent Dicebot <public dicebot.lv> writes:
Also, on a related topic - is there any reason why you are trying 
to put rc in container itself here instead of making it part of 
dedicated allocator?
Nov 17 2015