Before I begin, I want to say that a lot of this has come from reading other ideas that other people have had.  I know for instance that Janice has proposed something along these same lines using templates.  I think this proposal has not been posted quite exactly the same by anyone else, and the underlying themes are different than other proposals I or others have had regarding const and logical const.  In any case, credit should go to all those ideas posted that led me to this proposal.

D2's const system is centered around functional programming.  Without it, the grand view of Walter and Andrei to have a compiler that optimizes for multi-core systems with little effort from developers cannot be realized. However, there is another reason to have const, which Walter at least acknowledges.  That reason is for specifying contracts for functions.  That goal is partially realized, but since the const system is more focused on FP, it does not completely provide ways to specify all possible functionally sound constructs.  This post is aimed at outlining a way that D2's const system could be extended to provide const specification for both pure functions and function contracts, in as easy to use fashion as possible.

We begin by thinking about defining const.  Const is an attribute applied to a type.  The attribute doesn't change the data that is described by the type, it only changes the type, and rules for accessing the data.  We have four rules for const:

1. A variable that is typed as const or invariant cannot be changed.

2. A variable that is typed as const or invariant that has references to data cannot change that data through the references. (const is transitive)

3. A variable that is typed as invariant is guaranteed that all data that can be referenced through the variable will not change by any other references to the same data.

4. One can implicitly cast a data type to the same data type with different constancy if the newly modified type provides at least all the same protections to the same data that the original type provided.

In the current D2 scheme, we have the following two rules which implement
rule 4:
A. mutable or invariant data can implicitly be casted to const.
B. No other implicit casts are possible.

But let's think about how constancy is applied to an aggregate data type. The current granularity of applying const is to an entire aggregate.  One cannot selectively apply const to pieces of an aggregate.  However, if one could do so, one does not violate any of the rules.  Here is an example, keep in mind that X and X' are meant to be the same data type but with a different constancy applied:

class X
{
   int m;
   int m2;
}

class X'
{
   int m;
   const int m2;
}

Since X and X' are the same data type, but with different constancy, one can implicitly cast a variable of type X to a variable of type X' without violating rules 1-4.

So the question now becomes, how does one go about specifying a syntax for providing this functionality such that one has as much expressiveness as possible without violating the rules, and without making the syntax or specification cumbersome?

First, we specify a way to tag members of an aggregate such that they can be referred to in groups.  This one piece of grammar is the only crufty part of the solution, but could be easily alleviated by introducing a new keyword. In any case, using existing keywords, you create a 'tag group', which is scoped like any other symbol.  Using existing syntax, this looks like:

const alias A;

If this appears in a module or class, or even function, it only exists within that scope, just like a variable symbol.  How does one use such a tag?

class X
{
   int m;
   A int m2;
}

Now, m2 is in the tag group identified as A.  Now we need a syntax in order to affect just the constancy of the A tag group of X.  If we think of casting only the A group to const as parameterizing const's scope, it's similar to a parameter to a template.  So let's use the same syntax:

const!(A)(X) x;

So const!(A) means 'Apply const only to the group A', and X is the type to apply this rule to.  So now, x.m is mutable, x.m2 is const.  Now, we can cast a plain X to a const!(A)(X) implicitly, because this does not break any rules 1-4 above.  However, we cannot implicitly cast a const!(A)(X) back to an X because it would break rule 4.

Let us also define a special compiler-builtin tag group called __const_ALL. This tag group is special in that all members of any aggregate, regardless of the tag that is applied to them, also are tagged with __const_ALL.  This special group is used when applying const or invariant without parameterization, this group is implied.  i.e., const(X) is equivalent to const!(__const_ALL)(X), and invariant(X) is equivalent to invariant!(__const_ALL)(X).  Using class X above, a const!(__const_ALL)(X) has all const members, even though m2 is tagged with A.

This allows us to implement a logical const scheme, and also allow data to be transitively invariant in order to be used in pure functions.  We get the best of all worlds.

However, there are some more problems to solve.

First, it should be explicitly stated that a parameterized const is just as powerful as an unparameterized const with regards to pointers and arrays. i.e., you can parameterize only what a pointer points to, or only the elements of an array:

const!(A)(X) *x;
const!(A)(X)[] x2;

x and x2 are mutable, but the data pointed to is typed as const!(A)(X).

It is very unlikely that tag groups will have short names like 'A', they will be something more descriptive.  Utilizing these tag group names everywhere would be very cumbersome:

const alias logic_const;

const!(logic_const)(X) x2 = x;

So we allow aliases for these parameterized type modifiers:

const alias logic_const;

alias const!(logic_const) lconst;

lconst(X) x2 = x;

This syntax is more readable, easier to use and understand.

The next problem is being able to tag members as NOT being affected by a parameterized const statement.  For example, C++, through the mutable keyword, allows you to define members that are not casted to const when the aggregate is casted to const.  This is like a 'reverse' tag group.  Without something similar, one must tag all the members that SHOULD be casted to const when logical const is applied.  So we borrow the bitwise not operator for this purpose:

const alias mutable;

alias const!(~mutable) lconst;

class X
{
   mutable int m;
   int m2;
}

auto x = new X;
lconst(X) lx = x; // ok, not weakening constancy
lx.m = 2; // ok
lx.m2 = 3; // error, m2 was not tagged by mutable, so was cast to const

Next, we try to reduce the code for parameterizing const on multiple parameters.  For example, if you have two tag groups A and B in an aggregate, and you want to cast both of them to const, it would be:

const!(A)(const!(B)(X)) x;

Let's allow this kind of multiple specification to be shorthanded as:

const!(A, B)(X);

Next we tackle the chaining problem.  Let's say you have a linked list, and you want to specify a sorting function for that linked list.  The sorting function will not change any values pointed to by that linked list, but can change the order of the nodes in the linked list.  How does one specify this contract?  Using the rules we have so far:

const alias linkdata;

class Link(T)
{
    Link!(T) next;
    linkdata T data;
}

If we pass the head of the link list as const!(linkdata)(Link!(T)) to the function, what happens?  Upon traversing to the next link, the function is able to modify the data in the next link.  We need a way to specify a recursive linkdata constancy.  In order to do this, we need a second tag group, and recursive definition:

const alias linkdata;
const alias link;

class Link(T)
{
   link Link!(T) next;
   linkdata T data;
}

alias const!(linkdata)(dataconst(link)) dataconst;

Note that we use dataconst inside the definition for dataconst, just like we could have a pointer to a type within the definition of the type.  Note also that we need to define this as an alias so we can name the parameterized const definition in order to use it within the definition.  Therefore, you cannot specify this type of constancy without an alias statement.

dataconst(Link!(T)) x;

Now, x.next is of type dataconst(Link!(T)), and x.data is of type const(T).

The one problem we cannot solve is head-const.  For example, if you wanted to allow someone to traverse a link list and not change the structure of the links, but allow them to change the data, it is not possible without breaking rule 2, as you cannot have a constant pointer that points to mutable data.  However, this kind of thing could be solved with generic tagging (not just for const) combined with function overloading, or by using interfaces that enforce these requirements.

There is one final bonus problem that can be solved using these ideas.  If you think of the data that a class reference points to being of type <classname>_data, then you can think of a class reference as a pointer:

class X {};

alias X_data * X; // implicitly defined

Let's define another builtin tag group called __class_data_ref;  We can now redefine a class reference to X to be:

alias __class_data_ref(X_data) * X;

Now, we can define an alias to make x1 tail-const:

alias const!(__class_data_ref) tconst;

tconst(X) x1;

Now, x1 is rebindable, but the data x1 points to is const.

So in conclusion, I think this extension has the following benefits:

1. The existing ideas for pure functions requiring invariant are not broken
2. Logical const is possible for people who want const-contract
specification
3. Logical const can be recursive, allowing for contract specifications that
are not available in any other language AFAIK.
4. The syntax is powerful enough to allow specification of any const
casting, but easy enough to be usable and readable.

I understand that this proposal might be difficult to implement in the compiler, and it might just be not worth the effort.  There are a lot of problems that can be solved by not using const or using interfaces, instead of these constructs.  However, this proposal represents what I think is the most lenient and flexible proposal that is also const-correct from those I have read, and allows for almost any const contract specification (excluding head-const).  Whether it gets implemented or not, it was interesting to think about how to solve all these problems, and I enjoyed the challenge.

I would really like to hear people's opinions, especially Walter's.

-Steve

This is a hard problem. But if there's anything that I've learned from this whole const thing, it's that const is a hard concept for people to get. In order for a const system to be usable, it has to be very simple.

With functional languages, everything is const, so it is trivially understandable. Perl has invariant strings, but they are implicitly invariant and so nobody notices it, they just work.

C++ manages to hide the complexity, at the cost of const being ineffective.

D has a minimal system that is effective - const and invariant. The fact that it still seems to cause such misunderstanding is enough evidence for me to be very, very wary of adding more complexity to it.

Steven Schveighoffer, el 24 de junio a las 13:30 me escribiste:
> I understand that this proposal might be difficult to implement in the compiler, and it might just be not worth the effort.  There are a lot of problems that can be solved by not using const or using interfaces, instead of these constructs.  However, this proposal represents what I think is the most lenient and flexible proposal that is also const-correct from those I have read, and allows for almost any const contract specification (excluding head-const).  Whether it gets implemented or not, it was interesting to think about how to solve all these problems, and I enjoyed the challenge.

I agree with this. I think it´s wonderful, well thought proposal, which seems to address almost all the const issues in an elegant way, but I find it a little too complex and hard to understand/explain to worth it (besides the possible complex implementation).

But I think this proposal is very rich in terms of understanding the "const problem" and things that can or can´t be done using const.

-- 
Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/
----------------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------------
SE CUMPLEN 1345 DIAS DESDE QUE NOS ROBARON NUESTRA CAMARA
	-- Crónica TV

"Walter Bright" wrote
> D has a minimal system that is effective - const and invariant. The fact that it still seems to cause such misunderstanding is enough evidence for me to be very, very wary of adding more complexity to it.

Effective only for a feature that doesn't exist yet (pure functions).

From my experience, the D const system as it stands now does not cause such misunderstanding.  Everything is quite clear.  What seems to cause some misunderstanding:

- Why all string library functions require invariant arguments (probably #1
complaint on NG for newbies trying out D2)
- The concept of tail-const pointers and arrays
- Why you cannot have tail-const class references
- Why you cannot have logical const structures.

Explaining const and invariant by itself is easy.  And understandable.  It's the usages of them which are confusing.

But I look at this extension as a sort of 'meta' const.  It's like templates and mixins.  Some people (not me!) can do magic with these that would not be possible if templates weren't so wonderfully complex.  But to use a template that someone wrote isn't even close to as difficult.  For example, the conversion template to(T).  To use it I just do:

auto str = to!(string)(5);

and I don't have to know how or why it works.

Similarly, if a library implements const groups such as lconst like:

const alias mutable;
alias const!(~mutable) lconst;
alias invariant!(~mutable) linvariant;

One does not have to understand exactly what they mean.  All they have to know is 'declare a member mutable if you want it to be mutable when the class is lconst or linvariant.'  This kind of thing is easy to document and explain.  One does not HAVE to know all the details of how these magic generic const structures work, all they have to know is how to use them.  In fact, they do not need to know much more than what they already must learn for the current const.  Except that the last two points of confusion I identified above are removed.

In any case, like I said, if you find that it would be difficult to implement in the compiler, then so be it.  But assuming that you can't add a feature because it would complicate the language, in light of the fact that you already complicated the language too much, seems to be a contradictory argument.  We already have a complicated language by your measure.  Why not make it a complete language?

-Steve

"Leandro Lucarella" wrote
> Steven Schveighoffer, el 24 de junio a las 13:30 me escribiste:
>> I understand that this proposal might be difficult to implement in the
>> compiler, and it might just be not worth the effort.  There are a lot of
>> problems that can be solved by not using const or using interfaces,
>> instead
>> of these constructs.  However, this proposal represents what I think is
>> the
>> most lenient and flexible proposal that is also const-correct from those
>> I
>> have read, and allows for almost any const contract specification
>> (excluding
>> head-const).  Whether it gets implemented or not, it was interesting to
>> think about how to solve all these problems, and I enjoyed the challenge.
>
> I agree with this. I think it´s wonderful, well thought proposal, which seems to address almost all the const issues in an elegant way, but I find it a little too complex and hard to understand/explain to worth it (besides the possible complex implementation).

Well, at least you agree :)  I also agree it is complex to explain, but as I replied to Walter, an average developer doesn't have to know about how it works to use it, if the library writer has already set up the appropriate const groups.

Thanks for the reply!

-Steve

Steven Schveighoffer wrote:
> "Walter Bright" wrote
>> D has a minimal system that is effective - const and invariant. The fact that it still seems to cause such misunderstanding is enough evidence for me to be very, very wary of adding more complexity to it.
> 
> Effective only for a feature that doesn't exist yet (pure functions).
> 
> From my experience, the D const system as it stands now does not cause such misunderstanding.  Everything is quite clear.  What seems to cause some misunderstanding:
> 
> - Why all string library functions require invariant arguments (probably #1 complaint on NG for newbies trying out D2)
> - The concept of tail-const pointers and arrays
> - Why you cannot have tail-const class references
> - Why you cannot have logical const structures.
> 
> Explaining const and invariant by itself is easy.  And understandable.  It's the usages of them which are confusing.

If one doesn't understand the usages (and the consequences of) const, then I don't agree that one understands it.


> But I look at this extension as a sort of 'meta' const.  It's like templates and mixins.  Some people (not me!) can do magic with these that would not be possible if templates weren't so wonderfully complex.  But to use a template that someone wrote isn't even close to as difficult.  For example, the conversion template to(T).  To use it I just do:
> 
> auto str = to!(string)(5);
> 
> and I don't have to know how or why it works.

I don't agree that it's ok for library features to be complicated because only advanced users will write libraries. For one thing, it impedes writing libraries (and we all know that proliferation of libraries is essential for D's success) and it presumes that application code is somehow at a level that doesn't need those features.

For example, it's really hard to write reusable libraries in C++, and look at the consequences - few reusable libraries exist compared with other languages.


> Similarly, if a library implements const groups such as lconst like:
> 
> const alias mutable;
> alias const!(~mutable) lconst;
> alias invariant!(~mutable) linvariant;
> 
> One does not have to understand exactly what they mean.

As an engineer, I prefer to understand my tools completely :-)
If they aren't understood, and there's an error message, one has no idea what to do.

> All they have to know is 'declare a member mutable if you want it to be mutable when the class is lconst or linvariant.'  This kind of thing is easy to document and explain.  One does not HAVE to know all the details of how these magic generic const structures work, all they have to know is how to use them.  In fact, they do not need to know much more than what they already must learn for the current const.  Except that the last two points of confusion I identified above are removed.
> 
> In any case, like I said, if you find that it would be difficult to implement in the compiler, then so be it.  But assuming that you can't add a feature because it would complicate the language, in light of the fact that you already complicated the language too much, seems to be a contradictory argument.  We already have a complicated language by your measure.  Why not make it a complete language?

I worry about the complexity all the time. The idea is not to make a complicated language, but to find a way to make a simpler language that can do everything we need done. Complexity should only come with a benefit that outweighs the cost of it.

Steven Schveighoffer wrote:
> I would really like to hear people's opinions, especially Walter's.

What I like:
* Sticking to fundamental principles
* The const!(A,B)(T) syntax looks quite clean
* The ability for mixed const (AKA restricted mutability)

What I don't like:
* const!(~mutable)(T) syntax.  While a mutable keyword may be kind of nice,
the syntax is starting to get clunky and also become the only syntax
for "not const"
* No discussion of how to define const/invariant functions


A lot of times, when I think about tail const/mixed const/mutable/..., I
start thinking about arrays.
AKA:
  T[] vs. array!(T)
  const(T)[] vs. array!(const(T)) vs. const!(element)(array!(T))

> Well, at least you agree :)  I also agree it is complex to explain, but as I replied to Walter, an average developer doesn't have to know about how it works to use it, if the library writer has already set up the appropriate const groups.

I write libraries in C++ and I strongly agree.  I would rather have a complicated way of doing something than to not be able to do it at all. Even if it is a pain in the ass to get working, it works, and it's usable.

-Craig 

"Walter Bright" wrote
> Steven Schveighoffer wrote:
>> "Walter Bright" wrote
>>> D has a minimal system that is effective - const and invariant. The fact that it still seems to cause such misunderstanding is enough evidence for me to be very, very wary of adding more complexity to it.
>>
>> Effective only for a feature that doesn't exist yet (pure functions).
>>
>> From my experience, the D const system as it stands now does not cause such misunderstanding.  Everything is quite clear.  What seems to cause some misunderstanding:
>>
>> - Why all string library functions require invariant arguments (probably
>> #1 complaint on NG for newbies trying out D2)
>> - The concept of tail-const pointers and arrays
>> - Why you cannot have tail-const class references
>> - Why you cannot have logical const structures.
>>
>> Explaining const and invariant by itself is easy.  And understandable. It's the usages of them which are confusing.
>
> If one doesn't understand the usages (and the consequences of) const, then I don't agree that one understands it.

That is a fair point.  But still, there are plenty of features in D already that one does not need to understand the syntax of fully in order to use.

>
>
>> But I look at this extension as a sort of 'meta' const.  It's like templates and mixins.  Some people (not me!) can do magic with these that would not be possible if templates weren't so wonderfully complex.  But to use a template that someone wrote isn't even close to as difficult. For example, the conversion template to(T).  To use it I just do:
>>
>> auto str = to!(string)(5);
>>
>> and I don't have to know how or why it works.
>
> I don't agree that it's ok for library features to be complicated because only advanced users will write libraries. For one thing, it impedes writing libraries (and we all know that proliferation of libraries is essential for D's success) and it presumes that application code is somehow at a level that doesn't need those features.

I think you may have missed my point.  Yes, library proliferation is essential for success.  But libraries can be complicated without the need for the user of the library to understand them.  Libraries don't have to be complicated.  Libraries don't have to use parameterized const for anything. But the ability is there if you need it.  I view this no differently than templates.  Templates can be complex and very abstract, but very powerful and useful.  They also do not need to be fully understood to be used.

> For example, it's really hard to write reusable libraries in C++, and look at the consequences - few reusable libraries exist compared with other languages.

I'd say you are wrong here.

>> Similarly, if a library implements const groups such as lconst like:
>>
>> const alias mutable;
>> alias const!(~mutable) lconst;
>> alias invariant!(~mutable) linvariant;
>>
>> One does not have to understand exactly what they mean.
>
> As an engineer, I prefer to understand my tools completely :-)
> If they aren't understood, and there's an error message, one has no idea
> what to do.

Sure, so learn the concepts.  I don't think there is any way to create a const system that does not require some learning.  Not everyone has read the dmd source code, or phobos source code, to find out exactly how it works, so not everyone needs to understand the tools they use completely.  In fact, I think you would be in the minority.

But my point above is, if you wish to not worry about what const!(X) means, you can read the library documentation and only use mutable, lconst, and linvariant.

>> All they have to know is 'declare a member mutable if you want it to be mutable when the class is lconst or linvariant.'  This kind of thing is easy to document and explain.  One does not HAVE to know all the details of how these magic generic const structures work, all they have to know is how to use them.  In fact, they do not need to know much more than what they already must learn for the current const.  Except that the last two points of confusion I identified above are removed.
>>
>> In any case, like I said, if you find that it would be difficult to implement in the compiler, then so be it.  But assuming that you can't add a feature because it would complicate the language, in light of the fact that you already complicated the language too much, seems to be a contradictory argument.  We already have a complicated language by your measure.  Why not make it a complete language?
>
> I worry about the complexity all the time. The idea is not to make a complicated language, but to find a way to make a simpler language that can do everything we need done. Complexity should only come with a benefit that outweighs the cost of it.

And that is a judgement call you will have to make.  I already get the feeling you believe it is not worth it, and that's ok.  At least I put the idea out there :)

-Steve

"Jason House" wrote
> Steven Schveighoffer wrote:
>> I would really like to hear people's opinions, especially Walter's.
>
> What I like:
> * Sticking to fundamental principles
> * The const!(A,B)(T) syntax looks quite clean
> * The ability for mixed const (AKA restricted mutability)
>
> What I don't like:
> * const!(~mutable)(T) syntax.  While a mutable keyword may be kind of
> nice,
> the syntax is starting to get clunky and also become the only syntax
> for "not const"

Yes, it is clunky, but also hidden :)  All you ever have to do is use 'mutable', 'lconst', and 'linvariant.'  Compare it to mixins or templates.

import std.mutable;

class myclass
{
   mutable int x;
   int y;
}

void f(lconst(myclass) input)
{
    input.y = 2; // error, input.y is const
    input.x = 3; // ok.
}

> * No discussion of how to define const/invariant functions

I did leave this out.  Since const!(T) is analogous to const, it would be the same:

class myclass
{
   lconst void f() { /* 'this' is lconst */}
   void f2() lconst {/* same thing */}
}

> A lot of times, when I think about tail const/mixed const/mutable/..., I
> start thinking about arrays.
> AKA:
>  T[] vs. array!(T)
>  const(T)[] vs. array!(const(T)) vs. const!(element)(array!(T))

or const!(element)(T)[]

or

alias const!(element) eleconst;

eleconst(T)[]

-Steve