www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Two cases showing imperfection of the const system

reply "SiegeLord" <none none.com> writes:
Firstly, let me preface this... if you use templates to get 
around the const system's imperfections, you are admitting that 
the const system is broken. Now, on with the program.

My unique experience in using D2 without Phobos lead me to 
encounter two cases that show how the D2 const system is just a 
pain in the behind for some really reasonable tasks.

First case:

You want to sort an array of strings using a function. Strings 
can be all of these types: char[], const(char)[] and 
immutable(char)[]. What would be the signature of such a function?

It can't be sort(const(char)[][]) because it's unsafe to case 
char[][] and immutable(char)[][] to that argument type (see 
http://d.puremagic.com/issues/show_bug.cgi?id=4251 ).
It can't be sort(const(char[])[]) because you can't actually sort 
that!

The only good way I found is to use a cast inside the function 
with the second signature. Obviously I'm glad there's a 
workabout, but surely a cast isn't a good thing.

Second case:

inout was meant to solve issues with functions that return slices 
of inputs. What about a class that is dedicated to the same 
functionality?

E.g. this works fine:

inout(char)[] half(inout(char)[]);

But what about this:

struct Slicer
{
   char[] a;
   char[] half();
}

Note that the type of the input (the member 'a') must be the same 
as the output of the half method. I don't know how to accomplish 
this without templates. But as I said in the preface, you 
shouldn't need templates for such a simple task. Note that doing 
this isn't satisfactory:

struct Slicer
{
   char[] a;
   inout(char)[] half() inout;
}

because there may be other members inside that struct that may 
need to remain mutable.

This is very relevant, incidentally, for the planned library 
implementation of associative arrays. How would this be 
implemented when an associative array is a struct?

inout(char)[] test(inout(char)[])
{
   inout(char)[][int] a;
}

It doesn't even compile now (in dmd 2.058).

I don't have any solutions to these problems, incidentally... I 
think they are complex, but definitely worthy of having a 
reasonable solution that doesn't involve needless (in this case) 
templates.

-SiegeLord
Feb 16 2012
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 02/16/2012 10:48 PM, SiegeLord wrote:

 Firstly, let me preface this... if you use templates to get around the
 const system's imperfections, you are admitting that the const system is
 broken. Now, on with the program.

 My unique experience in using D2 without Phobos lead me to encounter two
 cases that show how the D2 const system is just a pain in the behind for
 some really reasonable tasks.

 First case:

 You want to sort an array of strings using a function. Strings can be
 all of these types: char[], const(char)[] and immutable(char)[]. What
 would be the signature of such a function?

 It can't be sort(const(char)[][]) because it's unsafe to case char[][]
 and immutable(char)[][] to that argument type (see
 http://d.puremagic.com/issues/show_bug.cgi?id=4251 ).
 It can't be sort(const(char[])[]) because you can't actually sort that!


The correct signature is
void sort(inout(char)[][]);

This is currently illegal, see:
http://d.puremagic.com/issues/show_bug.cgi?id=7105




 The only good way I found is to use a cast inside the function with the
 second signature. Obviously I'm glad there's a workabout, but surely a
 cast isn't a good thing.


A type-safe workaround is to use the signature
inout(void) sort(inout(char)[][]);


 Second case:

 inout was meant to solve issues with functions that return slices of
 inputs. What about a class that is dedicated to the same functionality?

 E.g. this works fine:

 inout(char)[] half(inout(char)[]);

 But what about this:

 struct Slicer
 {
 char[] a;
 char[] half();
 }

 Note that the type of the input (the member 'a') must be the same as the
 output of the half method. I don't know how to accomplish this without
 templates. But as I said in the preface, you shouldn't need templates
 for such a simple task. Note that doing this isn't satisfactory:

 struct Slicer
 {
 char[] a;
 inout(char)[] half() inout;
 }

 because there may be other members inside that struct that may need to
 remain mutable.


For this example, there is no problem. But I see what you mean. Seems 
like it would require some kind of parametric polymorphism. Ideally we'd 
get Scala-like Generics with Java Wildcards ;)

struct Slicer[+T <: const(char)[]]{ // not a template!
     T a;
     int[] someOtherMember;
     inout(T) half() inout;
}

void main(){
     Slicer![char] sl1;
     sl1.a = "string".dup;
     char[] arr1 = sl1.half();
     Slicer![immutable(char)] sl2;
     sl2.a = "string";
     string arr2 = sl2.half();
     Slicer![const(char)] sl3;
     sl3.a = "string".dup;
     sl3.a = "string";
     const(char)[] arr3 = sl3.half();

     sl3 = sl1;
     sl3 = sl2;
}



 This is very relevant, incidentally, for the planned library
 implementation of associative arrays. How would this be implemented when
 an associative array is a struct?

 inout(char)[] test(inout(char)[])
 {
 inout(char)[][int] a;
 }

 It doesn't even compile now (in dmd 2.058).


It does. The problem is that your function is missing a return 
statement. Anyway, when an associative array is a template struct then 
there is basically no non-magical way to implement what you want. 
However, if we introduce generics, the solution would look similar to 
this sketch:

struct AssocArray(S, T)[K <: const(S), V <: const(T)]{
     V lookup(K);
     ...
}

'test' would be rewritten by the compiler as:

inout(char)[] test(inout(char)[]) {
     AssocArray!(int,char[])![int,inout(char)[]] a;
     // ...
}



 I don't have any solutions to these problems, incidentally... I think
 they are complex, but definitely worthy of having a reasonable solution
 that doesn't involve needless (in this case) templates.

 -SiegeLord


The first problem is trivial, solving the second one in a type safe way 
would require adding parametric polymorphism to D. (Which I'd love to have!)
Feb 16 2012
next sibling parent reply James Miller <james aatch.net> writes:
 The first problem is trivial, solving the second one in a type safe way
 would require adding parametric polymorphism to D. (Which I'd love to have!)


Can't you emulate type-safe parametric polymorphism with template constraints?
Feb 16 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 02/17/2012 12:08 AM, James Miller wrote:

 The first problem is trivial, solving the second one in a type safe way
 would require adding parametric polymorphism to D. (Which I'd love to have!)


 Can't you emulate type-safe parametric polymorphism with template constraints?


In general, no.

class A{
     T foo[T](T x){ ... }
}
class B{
     override T foo[T](T x){ ... }
}

Often you can, but then you get unnecessary code duplication, which is 
presumably why SiegeLord dislikes templates.

T test(T)(T x) if(is(T:const(char[])){
     T[int] a;
}
Feb 16 2012
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 02/17/2012 12:36 AM, Timon Gehr wrote:

 On 02/17/2012 12:08 AM, James Miller wrote:

 The first problem is trivial, solving the second one in a type safe way
 would require adding parametric polymorphism to D. (Which I'd love to
 have!)


 Can't you emulate type-safe parametric polymorphism with template
 constraints?


 In general, no.

 class A{
 T foo[T](T x){ ... }
 }
 class B{
 override T foo[T](T x){ ... }
 }

 Often you can, but then you get unnecessary code duplication, which is
 presumably why SiegeLord dislikes templates.

 T test(T)(T x) if(is(T:const(char[])){
 T[int] a;
 }


This is closer to the wanted semantics:
T[] test(T)(T[] x) if(is(T[]:const(char[])){
     T[][int] a;
}
Feb 16 2012
prev sibling parent reply "SiegeLord" <none none.com> writes:
 It does. The problem is that your function is missing a return 
 statement.


Try it with the return statement, it doesn't compile anyway.

-SiegeLord
Feb 16 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 02/17/2012 01:19 AM, SiegeLord wrote:

 It does. The problem is that your function is missing a return statement.


 Try it with the return statement, it doesn't compile anyway.

 -SiegeLord


This compiles with DMD 2.057 and DMD 2.058:

import std.stdio;
inout(char)[] test(inout(char)[] x){
     inout(char)[][int] a;
     a[1]=x;
     return a[1];
}

void main(){
     writeln(test(['a']));
}
Feb 16 2012
parent "SiegeLord" <none none.com> writes:
On Friday, 17 February 2012 at 00:34:41 UTC, Timon Gehr wrote:

 This compiles with DMD 2.057 and DMD 2.058:

 import std.stdio;
 inout(char)[] test(inout(char)[] x){
    inout(char)[][int] a;
    a[1]=x;
    return a[1];
 }

 void main(){
    writeln(test(['a']));
 }


Whoops, nevermind then on it not working now. I look forward to 
seeing how it will work when AA's are templates.

-SiegeLord
Feb 16 2012
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/16/12 3:48 PM, SiegeLord wrote:

 Firstly, let me preface this... if you use templates to get around the
 const system's imperfections, you are admitting that the const system is
 broken. Now, on with the program.


Hold them horses. I disagree. You're just saying it, but what's your basis?


 My unique experience in using D2 without Phobos lead me to encounter two
 cases that show how the D2 const system is just a pain in the behind for
 some really reasonable tasks.

 First case:

 You want to sort an array of strings using a function. Strings can be
 all of these types: char[], const(char)[] and immutable(char)[]. What
 would be the signature of such a function?


This boils down to: "You want to sort an array of T[], U[], or V[], 
where the three types are loosely-related, except U is a supertype of 
both T and V and the three have the same layout. What would be the 
signature of such a function?"

The answer is (to a reasonable approximation) simple:

sort(X)(X[] data) if (is(X : U) && X.sizeof == U.sizeof);

This has nothing to do with qualifiers. Qualified types are distinct, 
and obey the classic subtyping and layout rules known since the dawn of 
humankind: const is a supertype of mutable and immutable, and they all 
have the same layout. Complaining about that equates to complaining 
about subtyping.


 It can't be sort(const(char)[][]) because it's unsafe to case char[][]
 and immutable(char)[][] to that argument type (see
 http://d.puremagic.com/issues/show_bug.cgi?id=4251 ).
 It can't be sort(const(char[])[]) because you can't actually sort that!

 The only good way I found is to use a cast inside the function with the
 second signature. Obviously I'm glad there's a workabout, but surely a
 cast isn't a good thing.


You'd do the same if you wanted to sort arrays of base and arrays of 
derived with the same routine.


 Second case:

 inout was meant to solve issues with functions that return slices of
 inputs. What about a class that is dedicated to the same functionality?

 E.g. this works fine:

 inout(char)[] half(inout(char)[]);

 But what about this:

 struct Slicer
 {
 char[] a;
 char[] half();
 }

 Note that the type of the input (the member 'a') must be the same as the
 output of the half method. I don't know how to accomplish this without
 templates.


I don't know how to swim with a hand tied to my back, either. The 
correct approach is to integrate templates in the discussion and analyze 
_that_ context, not the artificial context that precludes templates. D 
is not Go.


 But as I said in the preface, you shouldn't need templates
 for such a simple task.


char and const char are different types. The embedded presupposition is 
that they are somewhat similar, the qualifier being some sort of 
attribute of the type. That's not the case.


 Note that doing this isn't satisfactory:

 struct Slicer
 {
 char[] a;
 inout(char)[] half() inout;
 }

 because there may be other members inside that struct that may need to
 remain mutable.


Agreed.


 This is very relevant, incidentally, for the planned library
 implementation of associative arrays. How would this be implemented when
 an associative array is a struct?

 inout(char)[] test(inout(char)[])
 {
 inout(char)[][int] a;
 }

 It doesn't even compile now (in dmd 2.058).


Associative arrays must be templates.


 I don't have any solutions to these problems, incidentally... I think
 they are complex, but definitely worthy of having a reasonable solution
 that doesn't involve needless (in this case) templates.


Again, we must make templates a part of the setup and discuss what's 
going on.


Andrei
Feb 16 2012
parent reply "SiegeLord" <none none.com> writes:
On Thursday, 16 February 2012 at 23:14:54 UTC, Andrei 
Alexandrescu wrote:

 Hold them horses. I disagree. You're just saying it, but what's 
 your basis?


Because some cases (as shown below) trivially work within the 
const system, while some closely related ones don't. You're not 
going to be able to convince me of a demarcation that requires 
some const issues to require templates, and some not.


 This boils down to: "You want to sort an array of T[], U[], or 
 V[], where the three types are loosely-related, except U is a 
 supertype of both T and V and the three have the same layout. 
 What would be the signature of such a function?"

 The answer is (to a reasonable approximation) simple:

 sort(X)(X[] data) if (is(X : U) && X.sizeof == U.sizeof);

 This has nothing to do with qualifiers.


Because you removed them. While I agree with the type argument to 
a point, qualifiers have more meaning than just arbitrary type 
creation: they talk about mutability. The desired function 
signature states that the contents of the strings that are in the 
array will not be modified, your generic version does not have 
that stipulation. I can make up a body for that sort function 
which will work for types which fit your description, but fail 
for const(char)[], char[] and immutable(char)[].


 Second case:

 inout was meant to solve issues with functions that return 
 slices of
 inputs. What about a class that is dedicated to the same 
 functionality?

 E.g. this works fine:

 inout(char)[] half(inout(char)[]);

 But what about this:

 struct Slicer
 {
 char[] a;
 char[] half();
 }

 Note that the type of the input (the member 'a') must be the 
 same as the
 output of the half method. I don't know how to accomplish this 
 without
 templates.


 I don't know how to swim with a hand tied to my back, either. 
 The correct approach is to integrate templates in the 
 discussion and analyze _that_ context, not the artificial 
 context that precludes templates. D is not Go.


As much as you might prefer D to be 100% about templates, it is 
not, and there is a subset of it which is usable without them. 
This subset is the subject of this thread. There is no a priori 
reason why the first case should work and second should not 
within the confines of the const system.


 Associative arrays must be templates.


That's fine, but please try to compile this:

struct AAType(T)
{
   T[] Elems;
}

inout(char)[] test(inout(char)[] a)
{
    AAType!(inout(char)[]) b;
    return a;
}

-SiegeLord
Feb 16 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/16/12 6:49 PM, SiegeLord wrote:

 On Thursday, 16 February 2012 at 23:14:54 UTC, Andrei Alexandrescu wrote:

 Hold them horses. I disagree. You're just saying it, but what's your
 basis?


 Because some cases (as shown below) trivially work within the const
 system, while some closely related ones don't. You're not going to be
 able to convince me of a demarcation that requires some const issues to
 require templates, and some not.


Some cases also work trivially with subtyping, while some closely 
related ones don't.


 This boils down to: "You want to sort an array of T[], U[], or V[],
 where the three types are loosely-related, except U is a supertype of
 both T and V and the three have the same layout. What would be the
 signature of such a function?"

 The answer is (to a reasonable approximation) simple:

 sort(X)(X[] data) if (is(X : U) && X.sizeof == U.sizeof);

 This has nothing to do with qualifiers.


 Because you removed them. While I agree with the type argument to a
 point, qualifiers have more meaning than just arbitrary type creation:
 they talk about mutability.


That's a given. But that doesn't confer them infinite powers otherwise 
inaccessible; you seem to require any flexibility that seems reasonable 
within a context, and that's simply put impossible. There is a point 
where inout's powers stop (inout can be considered a special case 
designed for a few common cases).

I should confess that the subtyping relation (const(T) is a supertype of 
both T and immutable(T)) has from day 1 been a guiding design principle 
for us, so that shouldn't be taken lightly. There is a relation between 
types that is somewhere in between simple subtyping and qualified types: 
subtype with layout conservation, i.e. you know that T is a supertype of 
U and both T and U have identical layout. For such types we could 
accommodate special capabilities in the type system; they'd be 
applicable beyond qualified types.


 The desired function signature states that
 the contents of the strings that are in the array will not be modified,
 your generic version does not have that stipulation.
 I can make up a
 body for that sort function which will work for types which fit your
 description, but fail for const(char)[], char[] and immutable(char)[].


I think it's well worth trying this exercise. Given

class Base {}
class D1 : Base {}
class D2 : Base {}

define a non-template function that sorts Base[], D1[] and D2[] without 
casts.


 I don't know how to swim with a hand tied to my back, either. The
 correct approach is to integrate templates in the discussion and
 analyze _that_ context, not the artificial context that precludes
 templates. D is not Go.


 As much as you might prefer D to be 100% about templates,


(let's stay on topic and not make this ad hominem, thanks)


 it is not, and
 there is a subset of it which is usable without them.


This calls for the obvious answer that there's a subset of D that's 
usable without const.


 This subset is the
 subject of this thread. There is no a priori reason why the first case
 should work and second should not within the confines of the const system.


I understand your complaint, but I don't know how to design a type 
system that is at the same time reasonably small and simple and allows 
all of your examples and some related ones. We have "inout" which is 
helpful but at the end of the day a special case for a category of 
situations. We can't expect it to do miracles.


Andrei
Feb 16 2012
parent reply "SiegeLord" <none none.com> writes:
On Friday, 17 February 2012 at 02:39:29 UTC, Andrei Alexandrescu 
wrote:

 That's a given. But that doesn't confer them infinite powers 
 otherwise inaccessible; you seem to require any flexibility 
 that seems reasonable within a context, and that's simply put 
 impossible. There is a point where inout's powers stop (inout 
 can be considered a special case designed for a few common 
 cases).


And can this not be a special case with a new type too? The issue 
is of moving the elements in an array while retaining the const 
correctness on the contents of the elements. Something like a 
rebindable reference to a constant memory?


 I think it's well worth trying this exercise. Given

 class Base {}
 class D1 : Base {}
 class D2 : Base {}

 define a non-template function that sorts Base[], D1[] and D2[] 
 without casts.


Naturally you can't, but that wasn't my point. My point was that 
I could do this:

sort(X)(X[] data) if (is(X : const(char)[]) && X.sizeof == 
(const(char)[]).sizeof)
{
      data[0][0] = 1;
}

This would compile just fine if you passed it a char[][]. Your 
templated function doesn't describe the semantics of the function 
(it shouldn't change the elements of the array, just their 
order). Is there a way around it? Is it better than casting?


 This calls for the obvious answer that there's a subset of D 
 that's usable without const.


Yes, but it doesn't have these bizzarities.

I like having const correctness in my code, I like the assurance 
that my memory isn't being mutated. Once I start using templates, 
it seems that that assurance can go out of the window sometimes 
because the template system is defined on the level of types, not 
on the level of const qualifiers.

-SiegeLord
Feb 16 2012
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, February 17, 2012 06:54:44 SiegeLord wrote:

 On Friday, 17 February 2012 at 02:39:29 UTC, Andrei Alexandrescu
 
 wrote:

 That's a given. But that doesn't confer them infinite powers
 otherwise inaccessible; you seem to require any flexibility
 that seems reasonable within a context, and that's simply put
 impossible. There is a point where inout's powers stop (inout
 can be considered a special case designed for a few common
 cases).


 
 And can this not be a special case with a new type too? The issue
 is of moving the elements in an array while retaining the const
 correctness on the contents of the elements. Something like a
 rebindable reference to a constant memory?


If the elements are really const, then you can't move them. Period. Doing so 
would violate const. Now, you can have references or pointers to const and 
move _those_ around, but then the elements themselves aren't really const. If 
you're dealing with objects, you can use std.typecons.Rebindable, though there 
is a pull request (which has been around a while and may never get merged in) 
which adds syntax for references to const, in which case Rebindable wouldn't 
be needed anymore.


 This calls for the obvious answer that there's a subset of D
 that's usable without const.


 
 Yes, but it doesn't have these bizzarities.
 
 I like having const correctness in my code, I like the assurance
 that my memory isn't being mutated. Once I start using templates,
 it seems that that assurance can go out of the window sometimes
 because the template system is defined on the level of types, not
 on the level of const qualifiers.


Templates can't violate const anymore than other code can. Templates don't 
strip constness. If you're passing const variables to a templated function, 
they're const in the templated function. And if the templated function wants 
to guarantee that what you pass in doesn't get altered, then it can mark its 
parameters const just like any other function can. Templates do nothing to 
screw up const.

- Jonathan M Davis
Feb 16 2012
parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Jonathan M Davis" <jmdavisProg gmx.com> wrote in message 
news:mailman.457.1329458451.20196.digitalmars-d puremagic.com...

 there is a pull request (which has been around a while and may never get 
 merged in)


It or something like it will most likely get merged in eventually.
Feb 16 2012
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 02/17/2012 06:54 AM, SiegeLord wrote:

 On Friday, 17 February 2012 at 02:39:29 UTC, Andrei Alexandrescu wrote:

 That's a given. But that doesn't confer them infinite powers otherwise
 inaccessible; you seem to require any flexibility that seems
 reasonable within a context, and that's simply put impossible. There
 is a point where inout's powers stop (inout can be considered a
 special case designed for a few common cases).


 And can this not be a special case with a new type too? The issue is of
 moving the elements in an array while retaining the const correctness on
 the contents of the elements. Something like a rebindable reference to a
 constant memory?


 I think it's well worth trying this exercise. Given

 class Base {}
 class D1 : Base {}
 class D2 : Base {}

 define a non-template function that sorts Base[], D1[] and D2[]
 without casts.


 Naturally you can't, but that wasn't my point. My point was that I could
 do this:

 sort(X)(X[] data) if (is(X : const(char)[]) && X.sizeof ==
 (const(char)[]).sizeof)
 {
 data[0][0] = 1;
 }

 This would compile just fine if you passed it a char[][]. Your templated
 function doesn't describe the semantics of the function (it shouldn't
 change the elements of the array, just their order). Is there a way
 around it? Is it better than casting?


As I suggested in my other post, use inout(void) sort(inout(char)[][]) 
for the semantics you want.


 This calls for the obvious answer that there's a subset of D that's
 usable without const.


 Yes, but it doesn't have these bizzarities.

 I like having const correctness in my code, I like the assurance that my
 memory isn't being mutated. Once I start using templates, it seems that
 that assurance can go out of the window sometimes because the template
 system is defined on the level of types, not on the level of const
 qualifiers.

 -SiegeLord


Template functions cannot violate const correctness any more than normal 
functions can.
Feb 17 2012
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 16 Feb 2012 16:48:27 -0500, SiegeLord <none none.com> wrote:


 Firstly, let me preface this... if you use templates to get around the  
 const system's imperfections, you are admitting that the const system is  
 broken. Now, on with the program.

 My unique experience in using D2 without Phobos lead me to encounter two  
 cases that show how the D2 const system is just a pain in the behind for  
 some really reasonable tasks.


inout should solve all these problems.  As Timon says, there are bugs with  
it.  Bugs do not mean the design is not sound.

Also note that you are not unique in that experience, I tried to port  
Tango to D2 a long time ago, and the bug report 1961 was a direct result  
of trying that porting.  In other words, inout was *designed* to allow  
Tango to be ported to D2.

-Steve
Feb 17 2012