Ok, now I get why using Unqual to get tail const wouldn't work.  My silly oversight:

// The following doesn't work, though the natural tail
// const for const(Cycle!(int[])) is Cycle!(const(int)[]),
// because Unqual!(const(Cycle!(int[]))) == Cycle!(int[]).
import std.range, std.traits;

void main() {
    const myRange = cycle([1,2,3,4]);
    pragma(msg, typeof(myRange));

    Unqual!(typeof(myRange)) myRangeMutable = myRange;
    pragma(msg, typeof(myRange));
}


On Thu, Aug 12, 2010 at 11:37 AM, Steve Schveighoffer <schveiguy at yahoo.com>wrote:

> Tail-const is doable, but does not enjoy the implicit conversion that T[] has.
>
> Without the implicit conversion, tail-const relies on unsafe casting, and
> that
> sucks.
>
> I agree with Andrei we need a language solution.  The question really is
> not
> what the solution should do, that much is clear -- apply const to a subset
> of
> the members (either all references or members designated by some
> identifier).
> The question is, what does the syntax look like.  That was the major
> stumbling
> block that flipped Walter's switch to "tail-const doesn't work".
>
> I think we should concentrate on structs and not class references, since
> class
> references have no syntax that separates the reference from the data.  At
> least
> with structs, you can identify the parts to apply const to.  We have a
> somewhat
> clunky solution in Rebindable for classes, so it would be nice to include
> them,
> but past experience has shown that to be a big rat hole.
>
> -Steve
>
> >
> >From: David Simcha <dsimcha at gmail.com>
> >To: Discuss the phobos library for D <phobos at puremagic.com>
> >Sent: Thu, August 12, 2010 11:28:24 AM
> >Subject: Re: [phobos] is*Range + Qualified Types
> >
> >
> >
> >
> >On Thu, Aug 12, 2010 at 1:43 AM, Andrei Alexandrescu <andrei at erdani.com>
> wrote:
> >
> >
> >>
> I think the main argument is that currently most of std.algorithm doesn't
> work
> with const arrays, which have a simple "tail-const" version. const(T[]) is
> implicitly convertible to const(T)[].
> >>
> >>That doesn't apply to most other ranges, which don't have an obvious "tail-const" version.
> >>
> >>David, I think we need to think through a bit more before proceeding. The
> way I
> >
> >>assume you want to proceed is to essentially add a special function
> signature
> >>for each algorithm and have it forward to the peeled version. Perhaps we
> could
>
> >>look at a simpler solution, e.g. one that would involve a language
> change.
> >>
>
> Fair enough.  If you think this might be better solved at the language
> level,
> that's a worthwhile discussion to have.  I do believe, though, that most
> ranges
> besides T[] do have an obvious "tail-const" version, since in practice most
> ranges are structs that have the iteration state stored inline and only use
> indirection to store the payload, if anywhere.
>
> At any rate, I think this is a must-solve problem.  Despite its theoretical beauty, I find D's const/immutable system to be utterly useless (and I've made a
>
> serious attempt to use it in a real multithreaded program) for all but the simplest cases in practice, for three reasons:
>
> 1.   It's too hard to create non-trivial immutable data structures,
> especially
> without relying on unchecked casts during construction.
>
> 2.  So many things in Phobos (even things as simple as std.math.pow()
> before I
> recently fixed it) behave incorrectly when given const/immutable data.
>  This
> also applies to other libraries I use, including ones that I'm the main
> author
> of, so I'm just as guilty of it as anyone.  Given that noone, including me,
> seems to be able to get this right in generic code, perhaps this does point
> to
> the need for a language-level solution.
>
> 3.  inout is currently so bug-ridden it's not even funny.
>
>
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/phobos/attachments/20100812/94b62c66/attachment-0001.html>

Steve Schveighoffer <schveiguy at yahoo.com> wrote:
> I agree with Andrei we need a language solution.  The question really is not what the solution should do, that much is clear -- apply const to a subset of the members (either all references or members designated by some identifier). The question is, what does the syntax look like.  That was the major stumbling block that flipped Walter's switch to "tail-const doesn't work".

I can think of a similar syntax as the inout for functions:

wild struct Range
{
    wild(Node)* cur;
    @property wild(V) front() wild { return cur.value; }
    void popFront() wild { cur = cur.next; }
    @property bool empty() wild { return next !is null; }
}

This wouldn't work with nested structs though.


Shin

Exactly. I vividly remember our (Bartosz, Walter, me) discussion that settled this - the competing approach was to define distinct syntactic constructs for "head const", "tail const", and "all const".

Back then we decided that three flavors of const (and three of immutable) would be unacceptable as too complex. We decided that tail const for arrays was already possible syntactically (const(T[]) vs. const(T)[]) and that we'll leave libraries to define their own const(Artifact!T) vs. Artifact!(const T) if they so need.

I think it's okay to change the compiler to automatically convert const(T[]) to const(T)[] upon any function call. The function's parameter is private anyway. There's hardly any loss of information - I doubt a function could actually be interested in that distinction.


Andrei

David Simcha wrote:
> Ok, now I get why using Unqual to get tail const wouldn't work.  My silly oversight:
> 
> // The following doesn't work, though the natural tail
> // const for const(Cycle!(int[])) is Cycle!(const(int)[]),
> // because Unqual!(const(Cycle!(int[]))) == Cycle!(int[]).
> import std.range, std.traits;
> 
> void main() {
>     const myRange = cycle([1,2,3,4]);
>     pragma(msg, typeof(myRange));
> 
>     Unqual!(typeof(myRange)) myRangeMutable = myRange;
>     pragma(msg, typeof(myRange));
> }
> 
> 
> On Thu, Aug 12, 2010 at 11:37 AM, Steve Schveighoffer <schveiguy at yahoo.com <mailto:schveiguy at yahoo.com>> wrote:
> 
>     Tail-const is doable, but does not enjoy the implicit conversion
>     that T[] has.
> 
>     Without the implicit conversion, tail-const relies on unsafe
>     casting, and that
>     sucks.
> 
>     I agree with Andrei we need a language solution.  The question
>     really is not
>     what the solution should do, that much is clear -- apply const to a
>     subset of
>     the members (either all references or members designated by some
>     identifier).
>     The question is, what does the syntax look like.  That was the major
>     stumbling
>     block that flipped Walter's switch to "tail-const doesn't work".
> 
>     I think we should concentrate on structs and not class references,
>     since class
>     references have no syntax that separates the reference from the
>     data.  At least
>     with structs, you can identify the parts to apply const to.  We have
>     a somewhat
>     clunky solution in Rebindable for classes, so it would be nice to
>     include them,
>     but past experience has shown that to be a big rat hole.
> 
>     -Steve
> 
>      >
>      >From: David Simcha <dsimcha at gmail.com <mailto:dsimcha at gmail.com>>
>      >To: Discuss the phobos library for D <phobos at puremagic.com
>     <mailto:phobos at puremagic.com>>
>      >Sent: Thu, August 12, 2010 11:28:24 AM
>      >Subject: Re: [phobos] is*Range + Qualified Types
>      >
>      >
>      >
>      >
>      >On Thu, Aug 12, 2010 at 1:43 AM, Andrei Alexandrescu
>     <andrei at erdani.com <mailto:andrei at erdani.com>> wrote:
>      >
>      >
>      >>
>     I think the main argument is that currently most of std.algorithm
>     doesn't work
>     with const arrays, which have a simple "tail-const" version.
>     const(T[]) is
>     implicitly convertible to const(T)[].
>      >>
>      >>That doesn't apply to most other ranges, which don't have an obvious
>      >>"tail-const" version.
>      >>
>      >>David, I think we need to think through a bit more before
>     proceeding. The way I
>      >
>      >>assume you want to proceed is to essentially add a special
>     function signature
>      >>for each algorithm and have it forward to the peeled version.
>     Perhaps we could
> 
>      >>look at a simpler solution, e.g. one that would involve a
>     language change.
>      >>
> 
>     Fair enough.  If you think this might be better solved at the
>     language level,
>     that's a worthwhile discussion to have.  I do believe, though, that
>     most ranges
>     besides T[] do have an obvious "tail-const" version, since in
>     practice most
>     ranges are structs that have the iteration state stored inline and
>     only use
>     indirection to store the payload, if anywhere.
> 
>     At any rate, I think this is a must-solve problem.  Despite its
>     theoretical
>     beauty, I find D's const/immutable system to be utterly useless (and
>     I've made a
> 
>     serious attempt to use it in a real multithreaded program) for all
>     but the
>     simplest cases in practice, for three reasons:
> 
>     1.   It's too hard to create non-trivial immutable data structures,
>     especially
>     without relying on unchecked casts during construction.
> 
>     2.  So many things in Phobos (even things as simple as
>     std.math.pow() before I
>     recently fixed it) behave incorrectly when given const/immutable
>     data.  This
>     also applies to other libraries I use, including ones that I'm the
>     main author
>     of, so I'm just as guilty of it as anyone.  Given that noone,
>     including me,
>     seems to be able to get this right in generic code, perhaps this
>     does point to
>     the need for a language-level solution.
> 
>     3.  inout is currently so bug-ridden it's not even funny.
> 
> 
> 
>     _______________________________________________
>     phobos mailing list
>     phobos at puremagic.com <mailto:phobos at puremagic.com>
>     http://lists.puremagic.com/mailman/listinfo/phobos
> 
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

Where does this leave custom range structs, such as those for containers or wrapped ranges such as retro?  Most interesting ranges are not arrays.

There is currently no way to implicitly cast or match an overload based on how you parameterize your range, and inout will not work with it.

-Steve



----- Original Message ----
> From: Andrei Alexandrescu <andrei at erdani.com>
> To: Discuss the phobos library for D <phobos at puremagic.com>
> Sent: Thu, August 12, 2010 11:54:35 AM
> Subject: Re: [phobos] is*Range + Qualified Types
> 
> Exactly. I vividly remember our (Bartosz, Walter, me) discussion that settled
>this - the competing approach was to define distinct syntactic constructs for "head const", "tail const", and "all const".
> 
> Back then we decided that  three flavors of const (and three of immutable)
>would be unacceptable as too  complex. We decided that tail const for arrays was already possible  syntactically (const(T[]) vs. const(T)[]) and that we'll leave libraries to  define their own const(Artifact!T) vs. Artifact!(const T) if they so  need.
> 
> I think it's okay to change the compiler to automatically convert  const(T[])
>to const(T)[] upon any function call. The function's parameter is  private anyway. There's hardly any loss of information - I doubt a function  could actually be interested in that distinction.
> 
> 
> Andrei
> 
> David  Simcha wrote:
> > Ok, now I get why using Unqual to get tail const wouldn't  work.  My silly
>oversight:
> > 
> > // The following doesn't work,  though the natural tail
> > // const for const(Cycle!(int[])) is  Cycle!(const(int)[]),
> > // because Unqual!(const(Cycle!(int[]))) ==  Cycle!(int[]).
> > import std.range, std.traits;
> > 
> > void  main() {
> >     const myRange = cycle([1,2,3,4]);
> >      pragma(msg, typeof(myRange));
> > 
> >      Unqual!(typeof(myRange)) myRangeMutable = myRange;
> >      pragma(msg, typeof(myRange));
> > }
> > 
> > 
> > On Thu, Aug  12, 2010 at 11:37 AM, Steve Schveighoffer <schveiguy at yahoo.com
><mailto:schveiguy at yahoo.com>> wrote:
> > 
> >     Tail-const is doable, but does not enjoy the implicit  conversion
> >     that T[] has.
> > 
> >      Without the implicit conversion, tail-const relies on unsafe
> >      casting, and that
> >     sucks.
> > 
> >      I agree with Andrei we need a language solution.  The  question
> >     really is not
> >     what the  solution should do, that much is clear -- apply const to a
> >      subset of
> >     the members (either all references or members  designated by some
> >     identifier).
> >     The  question is, what does the syntax look like.  That was the  major
> >     stumbling
> >     block that flipped  Walter's switch to "tail-const doesn't work".
> > 
> >     I  think we should concentrate on structs and not class references,
> >      since class
> >     references have no syntax that  separates the reference from the
> >     data.  At  least
> >     with structs, you can identify the parts to apply  const to.  We have
> >     a somewhat
> >      clunky solution in Rebindable for classes, so it would be nice to
> >      include them,
> >     but past experience has shown that  to be a big rat hole.
> > 
> >     -Steve
> > 
> >      >
> >      >From: David  Simcha <dsimcha at gmail.com <mailto:dsimcha at gmail.com>>
> >       >To: Discuss the phobos library for D <phobos at puremagic.com
> >      <mailto:phobos at puremagic.com>>
> >       >Sent: Thu, August 12, 2010 11:28:24 AM
> >       >Subject: Re: [phobos] is*Range + Qualified Types
> >       >
> >      >
> >       >
> >      >
> >      >On Thu,  Aug 12, 2010 at 1:43 AM, Andrei Alexandrescu
> >     <andrei at erdani.com <mailto:andrei at erdani.com>>  wrote:
> >      >
> >       >
> >      >>
> >     I think the main  argument is that currently most of std.algorithm
> >     doesn't  work
> >     with const arrays, which have a simple "tail-const"  version.
> >     const(T[]) is
> >     implicitly  convertible to const(T)[].
> >      >>
> >       >>That doesn't apply to most other ranges, which don't have  an
obvious
> >      >>"tail-const"  version.
> >      >>
> >       >>David, I think we need to think through a bit more before
> >      proceeding. The way I
> >      >
> >       >>assume you want to proceed is to essentially add a  special
> >     function signature
> >       >>for each algorithm and have it forward to the peeled  version.
> >     Perhaps we could
> > 
> >       >>look at a simpler solution, e.g. one that would involve  a
> >     language change.
> >       >>
> > 
> >     Fair enough.  If you think this  might be better solved at the
> >     language  level,
> >     that's a worthwhile discussion to have.  I do  believe, though, that
> >     most ranges
> >      besides T[] do have an obvious "tail-const" version, since in
> >      practice most
> >     ranges are structs that have the  iteration state stored inline and
> >     only use
> >      indirection to store the payload, if anywhere.
> > 
> >      At any rate, I think this is a must-solve problem.  Despite  its
> >     theoretical
> >     beauty, I find D's  const/immutable system to be utterly useless (and
> >     I've  made a
> > 
> >     serious attempt to use it in a real  multithreaded program) for all
> >     but the
> >      simplest cases in practice, for three reasons:
> > 
> >      1.   It's too hard to create non-trivial immutable data  structures,
> >     especially
> >     without  relying on unchecked casts during construction.
> > 
> >      2.  So many things in Phobos (even things as simple as
> >      std.math.pow() before I
> >     recently fixed it) behave  incorrectly when given const/immutable
> >     data.   This
> >     also applies to other libraries I use, including ones  that I'm the
> >     main author
> >     of, so I'm  just as guilty of it as anyone.  Given that noone,
> >      including me,
> >     seems to be able to get this right in  generic code, perhaps this
> >     does point to
> >      the need for a language-level solution.
> > 
> >      3.  inout is currently so bug-ridden it's not even funny.
> > 
> > 
> > 
> >      _______________________________________________
> >     phobos  mailing list
> >    phobos at puremagic.com <mailto:phobos at puremagic.com>
> >      http://lists.puremagic.com/mailman/listinfo/phobos
> > 
> > 
> > 
> >  ------------------------------------------------------------------------
> > 
> > _______________________________________________
> > phobos mailing  list
> > phobos at puremagic.com
> > http://lists.puremagic.com/mailman/listinfo/phobos
> _______________________________________________
> phobos  mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
> 

I think a possible approach is this:

struct Container(T)
{
     struct Range(U) { ... }
     Range(T) opSlice() { ... }
     Range(const T) opSlice() const { ... }
}

This is rather new territory. We'll need to find the best idioms.


Andrei

On 08/12/2010 11:03 AM, Steve Schveighoffer wrote:
> Where does this leave custom range structs, such as those for containers or wrapped ranges such as retro?  Most interesting ranges are not arrays.
>
> There is currently no way to implicitly cast or match an overload based on how you parameterize your range, and inout will not work with it.
>
> -Steve
>
>
>
> ----- Original Message ----
>> From: Andrei Alexandrescu<andrei at erdani.com>
>> To: Discuss the phobos library for D<phobos at puremagic.com>
>> Sent: Thu, August 12, 2010 11:54:35 AM
>> Subject: Re: [phobos] is*Range + Qualified Types
>>
>> Exactly. I vividly remember our (Bartosz, Walter, me) discussion that settled this - the competing approach was to define distinct syntactic constructs for "head const", "tail const", and "all const".
>>
>> Back then we decided that  three flavors of const (and three of immutable)
>> would be unacceptable as too  complex. We decided that tail const for arrays was
>> already possible  syntactically (const(T[]) vs. const(T)[]) and that we'll leave
>> libraries to  define their own const(Artifact!T) vs. Artifact!(const T) if they
>> so  need.
>>
>> I think it's okay to change the compiler to automatically convert  const(T[]) to const(T)[] upon any function call. The function's parameter is  private anyway. There's hardly any loss of information - I doubt a function  could actually be interested in that distinction.
>>
>>
>> Andrei
>>
>> David  Simcha wrote:
>>> Ok, now I get why using Unqual to get tail const wouldn't  work.  My silly
>> oversight:
>>>
>>> // The following doesn't work,  though the natural tail
>>> // const for const(Cycle!(int[])) is  Cycle!(const(int)[]),
>>> // because Unqual!(const(Cycle!(int[]))) ==  Cycle!(int[]).
>>> import std.range, std.traits;
>>>
>>> void  main() {
>>>      const myRange = cycle([1,2,3,4]);
>>>       pragma(msg, typeof(myRange));
>>>
>>>       Unqual!(typeof(myRange)) myRangeMutable = myRange;
>>>       pragma(msg, typeof(myRange));
>>> }
>>>
>>>
>>> On Thu, Aug  12, 2010 at 11:37 AM, Steve Schveighoffer<schveiguy at yahoo.com
>> <mailto:schveiguy at yahoo.com>>  wrote:
>>>
>>>      Tail-const is doable, but does not enjoy the implicit  conversion
>>>      that T[] has.
>>>
>>>       Without the implicit conversion, tail-const relies on unsafe
>>>       casting, and that
>>>      sucks.
>>>
>>>       I agree with Andrei we need a language solution.  The  question
>>>      really is not
>>>      what the  solution should do, that much is clear -- apply const to a
>>>       subset of
>>>      the members (either all references or members  designated by some
>>>      identifier).
>>>      The  question is, what does the syntax look like.  That was the  major
>>>      stumbling
>>>      block that flipped  Walter's switch to "tail-const doesn't work".
>>>
>>>      I  think we should concentrate on structs and not class references,
>>>       since class
>>>      references have no syntax that  separates the reference from the
>>>      data.  At  least
>>>      with structs, you can identify the parts to apply  const to.  We have
>>>      a somewhat
>>>       clunky solution in Rebindable for classes, so it would be nice to
>>>       include them,
>>>      but past experience has shown that  to be a big rat hole.
>>>
>>>      -Steve
>>>
>>>       >
>>>       >From: David  Simcha<dsimcha at gmail.com<mailto:dsimcha at gmail.com>>
>>>        >To: Discuss the phobos library for D<phobos at puremagic.com
>>>       <mailto:phobos at puremagic.com>>
>>>        >Sent: Thu, August 12, 2010 11:28:24 AM
>>>        >Subject: Re: [phobos] is*Range + Qualified Types
>>>        >
>>>       >
>>>        >
>>>       >
>>>       >On Thu,  Aug 12, 2010 at 1:43 AM, Andrei Alexandrescu
>>>      <andrei at erdani.com<mailto:andrei at erdani.com>>   wrote:
>>>       >
>>>        >
>>>       >>
>>>      I think the main  argument is that currently most of std.algorithm
>>>      doesn't  work
>>>      with const arrays, which have a simple "tail-const"  version.
>>>      const(T[]) is
>>>      implicitly  convertible to const(T)[].
>>>       >>
>>>        >>That doesn't apply to most other ranges, which don't have  an
> obvious
>>>       >>"tail-const"  version.
>>>       >>
>>>        >>David, I think we need to think through a bit more before
>>>       proceeding. The way I
>>>       >
>>>        >>assume you want to proceed is to essentially add a  special
>>>      function signature
>>>        >>for each algorithm and have it forward to the peeled  version.
>>>      Perhaps we could
>>>
>>>        >>look at a simpler solution, e.g. one that would involve  a
>>>      language change.
>>>        >>
>>>
>>>      Fair enough.  If you think this  might be better solved at the
>>>      language  level,
>>>      that's a worthwhile discussion to have.  I do  believe, though, that
>>>      most ranges
>>>       besides T[] do have an obvious "tail-const" version, since in
>>>       practice most
>>>      ranges are structs that have the  iteration state stored inline and
>>>      only use
>>>       indirection to store the payload, if anywhere.
>>>
>>>       At any rate, I think this is a must-solve problem.  Despite  its
>>>      theoretical
>>>      beauty, I find D's  const/immutable system to be utterly useless (and
>>>      I've  made a
>>>
>>>      serious attempt to use it in a real  multithreaded program) for all
>>>      but the
>>>       simplest cases in practice, for three reasons:
>>>
>>>       1.   It's too hard to create non-trivial immutable data  structures,
>>>      especially
>>>      without  relying on unchecked casts during construction.
>>>
>>>       2.  So many things in Phobos (even things as simple as
>>>       std.math.pow() before I
>>>      recently fixed it) behave  incorrectly when given const/immutable
>>>      data.   This
>>>      also applies to other libraries I use, including ones  that I'm the
>>>      main author
>>>      of, so I'm  just as guilty of it as anyone.  Given that noone,
>>>       including me,
>>>      seems to be able to get this right in  generic code, perhaps this
>>>      does point to
>>>       the need for a language-level solution.
>>>
>>>       3.  inout is currently so bug-ridden it's not even funny.
>>>
>>>
>>>
>>>       _______________________________________________
>>>      phobos  mailing list
>>>     phobos at puremagic.com<mailto:phobos at puremagic.com>
>>>       http://lists.puremagic.com/mailman/listinfo/phobos
>>>
>>>
>>>
>>>   ------------------------------------------------------------------------
>>>
>>> _______________________________________________
>>> phobos mailing  list
>>> phobos at puremagic.com
>>> http://lists.puremagic.com/mailman/listinfo/phobos
>> _______________________________________________
>> phobos  mailing list
>> phobos at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/phobos
>>
>
>
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

So the crux of the matter is not operating on constant ranges (which I believe we can safely drop), but obtaining non-constant ranges from constant containers.

The idea that we could use a symbolic name for the qualifier is, I think, workable, but Walter has resisted it on account of exacerbated complexity in the implementation. We should explore other means for the time being.

Right now a typical container implementation goes like this:

struct Container(T)
{
     ...
     struct Range { ... }
     Range opSlice() { ... }
}

A container might define several ranges, but c[] yields the container's primary, most prominent range. Now if we have a const Container!Widget object, we need to find an idiomatic way to extract a range from it. Here's some code that compiles and runs as expected:

#!/bin/env rdmd
import std.stdio;

struct Container(T)
{
     static struct Node { T payload; Node * next; }
     Node * root;
     struct Range(N) {
         private N * n;
         @property T front() { return n.payload; }
         @property bool empty() { return n is null; }
         void popFront() { n = n.next; }
     }
     Range!Node opSlice() {
         return typeof(return)(root);
     }
     Range!(const Node) opSlice() const {
         return typeof(return)(root);
     }
}

void main() {
     Container!int c1;
     c1.root = new c1.Node;
     c1.root.payload = 5;
     c1.root.next = new c1.Node;
     c1.root.next.payload = 7;
     foreach (i; c1[]) writeln(i);

     foo(c1);
}

void foo(const Container!int c1) {
     foreach (i; c1[]) writeln(i);
}

The basic idea is that the qualifier is propagated from the container to the range together with the type of the representation held inside the range.

I'm not sure how generalizable this is, but it's a start. There is also the remaining nagging issue of duplicating the line

         return typeof(return)(root);

which in other cases might expand to more lines.

Any thoughts would be appreciated.


Andrei

On 8/12/10 7:52 CDT, Steve Schveighoffer wrote:
> ----- Original Message ----
>
>> From: Shin Fujishiro<rsinfu at gmail.com>
>>
>> David Simcha<dsimcha at gmail.com>  wrote:
>>> I'm  looking to go on a major debugging spree and make std.range work with  const ranges.  For example, the following should work:
>>>
>>>   import std.range, std.algorithm;
>>>
>>> void main() {
>>>        const foo = map!"a ^^ 2"([1,2,3,4,5]);
>>>        auto myRetro = retro(foo);
>>> }
>>
>> Could you elaborate  why?
>>
>> Ranges with const elements must be common; but what's the point  of const ranges?  Const random access ranges are usable, but other  const ranges seem to be useless since popFront and popBack can't be  const.
>
> This seems to point at a larger issue.
>
> With the de-facto range T[], we get an implicit cast to a range of const
> elements, const(T)[].
>
> But we cannot get this with any user-defined type.  I think we will need to address this eventually.  It's one of the main reasons dcollections is not const-aware, because I don't want to create several types of ranges/cursors, and then all the duplicated functions that go with it.  I'd rather use inout and have it designate the return type.
>
> I think Janice proposed something a long long time ago that allowed a template parameter to represent a const factor of a type, a-la:
>
> SList(V)
> {
>      struct node
>      {
>         V value;
>         node *next;
>      }
>      node *head;
>
>      struct range(const C)
>      {
>          C(node)* cur;
>          @property C(V) front() {return cur.value;}
>          void popFront() {next = cur.next;}
>          @property bool empty() {return next !is null;}
>      }
>
>      range!(inout) opSlice() inout {range!(inout) result;  result.cur = head;
> return result;}
> }
>
> So basically, the way it works is C is substituted for a const factor (const,
> immutable, or nothing).  And more importantly, the compiler allows implicit
> conversion from a range!(???) to a range!(const).  Also, we can apply inout
> rules.  (Note, I don't know what to put as a const parameter for mutable, since
> that's not a keyword, hence the ???).
>
> Does this seem complex?  Yes.  But it's not as complex/hard to read/hard to implement as 3 copies of all functions with 3 different range types.  It's akin to the savings/clarity of inout.
>
> What I'm unsure about is if we need to do it this way.  I don't like using a user-defined parameter as the const factor, it makes it #1 hard to read, and #2 every person's const factor symbol may be different.  Most likely, you will have one const template parameter.  Do we need to support multiple parameters?  inout avoids requiring templates, because the code generation is identical.  Can we do something similar to inout?
>
> We're going to need something like this to avoid rediculous code repetition for any type that uses custom range types.  Essentially what we need to duplicate is the "apply const only to one member" feature of builtin arrays.
>
> -Steve
>
>
>
>
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos

  On 9/17/2010 3:08 AM, Andrei Alexandrescu wrote:
> So the crux of the matter is not operating on constant ranges (which I believe we can safely drop), but obtaining non-constant ranges from constant containers.

I agree we need to drop operating on constant ranges for the general case, but I think it's trivial to fix for a lot of common cases by just adding Unqual.  This would fix arrays, iota and everything else that has a "natural" tail const.

>
> The idea that we could use a symbolic name for the qualifier is, I think, workable, but Walter has resisted it on account of exacerbated complexity in the implementation. We should explore other means for the time being.
>
> Right now a typical container implementation goes like this:
>
> struct Container(T)
> {
>     ...
>     struct Range { ... }
>     Range opSlice() { ... }
> }
>
> A container might define several ranges, but c[] yields the container's primary, most prominent range. Now if we have a const Container!Widget object, we need to find an idiomatic way to extract a range from it. Here's some code that compiles and runs as expected:
>
> #!/bin/env rdmd
> import std.stdio;
>
> struct Container(T)
> {
>     static struct Node { T payload; Node * next; }
>     Node * root;
>     struct Range(N) {
>         private N * n;
>         @property T front() { return n.payload; }
>         @property bool empty() { return n is null; }
>         void popFront() { n = n.next; }
>     }
>     Range!Node opSlice() {
>         return typeof(return)(root);
>     }
>     Range!(const Node) opSlice() const {
>         return typeof(return)(root);
>     }
> }
>
> void main() {
>     Container!int c1;
>     c1.root = new c1.Node;
>     c1.root.payload = 5;
>     c1.root.next = new c1.Node;
>     c1.root.next.payload = 7;
>     foreach (i; c1[]) writeln(i);
>
>     foo(c1);
> }
>
> void foo(const Container!int c1) {
>     foreach (i; c1[]) writeln(i);
> }
>
> The basic idea is that the qualifier is propagated from the container to the range together with the type of the representation held inside the range.

This would solve the case where the range and the container are truly distinct animals, but in a lot of cases they aren't.
>
> I'm not sure how generalizable this is, but it's a start. There is also the remaining nagging issue of duplicating the line
>
>         return typeof(return)(root);
>
> which in other cases might expand to more lines.

Shouldn't inout solve this once it's fully implemented?  Or maybe template this parameters + auto return types?

Range!(inout Node) opSlice() inout {
      return typeof(return)(root);
}

or

auto opSlice(this This)() {
     return Range!(typeof(root))(root);
}

That is one solution, but it still fails the implicit conversion test. Essentially, I should be able to convert a non-const range into a const range implicitly.

I'd also like to avoid a template solution if possible, since it seems like a hack to force you to template your range when you wouldn't normally need to. You also forgot about this awkwardness:

struct Range(N) {
   ...
   static if(!is(N == const))
   {
      @property void front(T newval) { n.payload = newval; }
   }
}


I don't have the answers however, tail const really is the best option, but I think there's a tail-const vein in Walter's forehead that throbs whenever he sees the words ;)

-Steve


----- Original Message ----
> From: Andrei Alexandrescu <andrei at erdani.com>
> To: Discuss the phobos library for D <phobos at puremagic.com>
> Sent: Fri, September 17, 2010 3:08:55 AM
> Subject: Re: [phobos] is*Range + Qualified Types
> 
> So the crux of the matter is not operating on constant ranges (which I believe
>we can safely drop), but obtaining non-constant ranges from constant containers.
> 
> The idea that we could use a symbolic name for the qualifier  is, I think,
>workable, but Walter has resisted it on account of exacerbated  complexity in the implementation. We should explore other means for the time  being.
> 
> Right now a typical container implementation goes like  this:
> 
> struct Container(T)
> {
>     ...
>      struct Range { ... }
>     Range opSlice() { ... }
> }
> 
> A  container might define several ranges, but c[] yields the container's
>primary,  most prominent range. Now if we have a const Container!Widget object, we need to  find an idiomatic way to extract a range from it. Here's some code that compiles  and runs as expected:
> 
> #!/bin/env rdmd
> import std.stdio;
> 
> struct  Container(T)
> {
>     static struct Node { T payload; Node * next;  }
>     Node * root;
>     struct Range(N) {
>          private N * n;
>         @property T  front() { return n.payload; }
>         @property bool  empty() { return n is null; }
>         void popFront() { n  = n.next; }
>     }
>     Range!Node opSlice() {
>          return typeof(return)(root);
>     }
>      Range!(const Node) opSlice() const {
>          return typeof(return)(root);
>     }
> }
> 
> void main()  {
>     Container!int c1;
>     c1.root = new  c1.Node;
>     c1.root.payload = 5;
>     c1.root.next =  new c1.Node;
>     c1.root.next.payload = 7;
>     foreach  (i; c1[]) writeln(i);
> 
>     foo(c1);
> }
> 
> void foo(const  Container!int c1) {
>     foreach (i; c1[])  writeln(i);
> }
> 
> The basic idea is that the qualifier is propagated from  the container to the
>range together with the type of the representation held  inside the range.
> 
> I'm not sure how generalizable this is, but it's a  start. There is also the
>remaining nagging issue of duplicating the  line
> 
>         return  typeof(return)(root);
> 
> which in other cases might expand to more  lines.
> 
> Any thoughts would be appreciated.
> 
> 
> Andrei
> 
> On  8/12/10 7:52 CDT, Steve Schveighoffer wrote:
> > ----- Original Message  ----
> > 
> >> From: Shin Fujishiro<rsinfu at gmail.com>
> >> 
> >>  David Simcha<dsimcha at gmail.com>   wrote:
> >>> I'm  looking to go on a major debugging spree and  make std.range work with  const ranges.  For example,  the following should work:
> >>> 
> >>>   import  std.range, std.algorithm;
> >>> 
> >>> void main()  {
> >>>        const foo = map!"a ^^  2"([1,2,3,4,5]);
> >>>        auto myRetro =  retro(foo);
> >>> }
> >> 
> >> Could you elaborate   why?
> >> 
> >> Ranges with const elements must be common; but  what's the point  of const ranges?  Const random access  ranges are usable, but other  const ranges seem to be useless  since popFront and popBack can't be  const.
> > 
> > This seems to  point at a larger issue.
> > 
> > With the de-facto range T[], we get an  implicit cast to a range of const
> > elements, const(T)[].
> > 
> >  But we cannot get this with any user-defined type.  I think we will need
to
> > address this eventually.  It's one of the main reasons  dcollections is not const-aware, because I don't want to create several  types of ranges/cursors,
>and
> > then all the duplicated functions that go  with it.  I'd rather use inout
and
> > have it designate the return  type.
> > 
> > I think Janice proposed something a long long time ago  that allowed a
>template
> > parameter to represent a const factor of a type,  a-la:
> > 
> > SList(V)
> > {
> >      struct  node
> >      {
> >         V  value;
> >         node *next;
> >       }
> >      node *head;
> > 
> >       struct range(const C)
> >      {
> >           C(node)* cur;
> >           @property C(V) front() {return cur.value;}
> >           void popFront() {next = cur.next;}
> >           @property bool empty() {return next !is null;}
> >       }
> > 
> >      range!(inout) opSlice() inout  {range!(inout) result;  result.cur =
>head;
> > return result;}
> >  }
> > 
> > So basically, the way it works is C is substituted for a  const factor
>(const,
> > immutable, or nothing).  And more importantly,  the compiler allows implicit
> > conversion from a range!(???) to a  range!(const).  Also, we can apply inout
> > rules.  (Note, I  don't know what to put as a const parameter for mutable,
>since
> > that's  not a keyword, hence the ???).
> > 
> > Does this seem complex?   Yes.  But it's not as complex/hard to read/hard to implement as 3  copies of all functions with 3 different range types.  It's
>akin
> > to  the savings/clarity of inout.
> > 
> > What I'm unsure about is if we  need to do it this way.  I don't like using
a
> > user-defined  parameter as the const factor, it makes it #1 hard to read, and
>#2
> > every  person's const factor symbol may be different.  Most likely, you will
>have
> > one const template parameter.  Do we need to support multiple  parameters?
>inout
> > avoids requiring templates, because the code  generation is identical.  Can
>we do
> > something similar to  inout?
> > 
> > We're going to need something like this to avoid  rediculous code repetition
>for
> > any type that uses custom range  types.  Essentially what we need to
>duplicate is
> > the "apply const  only to one member" feature of builtin arrays.
> > 
> > -Steve
> > 
> > 
> > 
> > 
> >  _______________________________________________
> > phobos mailing  list
> > phobos at puremagic.com
> >  http://lists.puremagic.com/mailman/listinfo/phobos
> _______________________________________________
> phobos  mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
> 

----- Original Message ----
> From: David Simcha <dsimcha at gmail.com>
> 
> On 9/17/2010 3:08 AM, Andrei Alexandrescu wrote:
> > 
> > I'm not sure how generalizable this is,  but it's a start. There is also the
>remaining nagging issue of duplicating the  line
> > 
> >         return  typeof(return)(root);
> > 
> > which in other cases might expand to more  lines.
> 
> Shouldn't inout solve this once it's fully implemented?  Or  maybe template
>this parameters + auto return types?

inout inside templates isn't really supported.  I'm not sure how it should work.  I know that inout is not supposed to be valid on a member variable because how does this work?

struct S
{
    inout int x; // what does this mean?
}

So how would this work?

struct S(T)
{
   T x;
}

S!(inout int) s;

The crux of this whole problem is that implicit conversions that make sense to a person are illegal to the compiler.  For example, it would make sense to a person that you could convert a Range!(N) into a Range!(const N), but the compiler sees them as distinct types.  I don't know the right answer of how to fix this except to revisit trying to define tail-const.

-Steve

  I just wanted to note that this problem is a heck of a lot worse than
it looks now, and IMHO really requires changes to IFTI to deal with at
all reasonably.  Also note that it's not even a problem specific to
ranges, as things as simple as pow() were broken and required some ugly
kludges to fix, due to similar issues.

I've discovered that huge amounts of code in Phobos are relying on Bug 3534 (http://d.puremagic.com/issues/show_bug.cgi?id=3534) to work, since this allows calling popFront()/popBack() on const/immutable arrays.  I tried to change popFront() and popBack() to explicitly prevent them from being called on const/immutable arrays, thinking/hoping that not too much code would be relying on this bug and that I could fix whatever does.  It ended up having ripple effects all over Phobos, breaking modules from std.string to std.algorithm to std.xml, so I gave up for now.

I realize D isn't getting tail const, so a perfect general solution is out of the question.  However, I do think that a lot of important cases (arrays and stuff without mutable indirection) can be solved by making IFTI implicitly instantiate with Unqual!T when passed a T, iff T is implicitly convertible to Unqual!T.  For example:

struct S {
     int[] arr;
     int i;
}

immutable str = "abc";
immutable num = 1;
immutable S s;

void doStuff(T1, T2, T3)(T1 t1, T2 t2, T3 t3) {}

doStuff(str, num, s);

This would call doStuff!(immutable(char)[], int, immutable(S)). immutable(char[]) can implicitly convert to immutable(char)[], so the implicit conversion is done. immutable(int) can implicitly convert to int, so the conversion is done. immutable(S) cannot implicitly convert to S, so the conversion is not done.