Sergey Gromov wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>> Sergey Gromov wrote:
>>> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>>> Given that in D const is transitive, we can't operate with const the same way C++ does. Consider something as trivial as a copy:
>>>>
>>>> Tgt copy(Src, Tgt)(Src src, Tgt tgt)
>>>> {
>>>>      for (; !src.done; src.next) tgt.put(src.tip);
>>>> }
>>>>
>>>> Problem is, you won't be able to copy e.g. an int[][] to another because the types aren't compatible.
>>> If Src is an input range you must make a deep copy.  This holds true for your current design also.  So this algorithm is flawed and it's good if it won't compile.
>> Great point. I need to sleep on this some more.
> 
> Then I'll continue to think aloud.
[snip]

Thanks for the code samples, they're cool. I hit a problem related to the return type of head. Consider writing a range that iterates two other ranges in lockstep. A very useful generic range. I started coding it like this:

struct Lockstep(R0, R1)
{
    private R0 _r0;
    private R1 _r1;
    this(R0 r0, R1 r1)
    {
       _r0 = r0;
       _r1 = r1;
    }

    bool empty()
    {
        return _r0.empty || _r1.empty;
    }

    Tuple!(ElementType!(R0), ElementType!(R1)) head()
    {
        return tuple(_r0.head, _r1.head);
    }

    void next()
    {
        _r0.next;
        _r1.next;
    }
}

Before long I realized that the type of head was wrong. Along the way, the fact that the two ranges return by REFERENCE was irretrivably lost. Returning a ref Tuple!(ElementType!(R0), ElementType!(R1)) won't work either, because how do you move the references of the _r0.head and _r1._head in a common tuple?

The type Tuple!(ref ElementType!(R0), ref ElementType!(R1)) does not exist because ref is not a type constructor.

This is quite a pickle because it reveals that ref is not composable. I have a few ideas on how to handle this, but I don't want to bias anyone. If you have ideas, please fire them up!


Andrei

Andrei Alexandrescu Wrote:

> Dave wrote:
> > 
> > "Andrei Alexandrescu" <SeeWebsiteForEmail@erdani.org> wrote in message news:gadn7c$oe5$4@digitalmars.com...
> >> Pablo Ripolles wrote:
> >>> Andrei Alexandrescu Wrote:
> >>>
> >>>> In wake of the many excellent comments and suggestions made here, I made one more pass through the draft proposal for ranges.
> >>>>
> >>>> http://ssli.ee.washington.edu/~aalexand/d/tmp/std_range.html
> >>>>
> >>>> There are some comments in red illustrating some uncertainties (not all), and the names of the primitives have been updated. Bicycle shed galore! But don't forget to comment on the reactor as well :o).
> >>>>
> >>>>
> >>>> Andrei
> >>>
> >>>
> >>> Well, it looks prety clean! :D
> >>>
> >>> However, I'm not completely sure I like these "head" and "toe" names selection.  It projects to much on it, doesn't it?  couldn't it be more neutral?  perhaps more conceptual?  I haven't been able to read the last days' comments... but my last impressions were that this "head" was not the best choice.
> >>>
> >>> If "head" is the header item, why not call it "header"?
> >>>
> >>> If ''toe" is the last item, why not call it "last"?
> >>>
> >>> Other comment goes for the "done" property, for the seek of consistence shouldn't it better be named "isDone"?
> >>>
> >>> Cheers!
> >>
> >> Thanks. One problem in coding with first and last was that sometimes the code looks unnatural, especially when your range exposes a few more functions. In a stream parser, dealing with the "first" element is not the most natural way to think of it. But I agree that first and last are definitely palatable and natural most of the time. But then again, shouldn't any design have the inevitable cutesy that makes it memorable? :o)
> >>
> >> Andrei
> > 
> >  From the limited posts I've had the time to read, it seems this topic
> > has probably been already beaten to death, but how about "tail" instead
> > of "toe".
> > 
> > And instead of the "yellow" primitive, why not "intersect(r,s)" , "intersection(r,s)", "r.contains(s)" , "r.intersect(s)" , etc.
> > 
> > Wasn't "intersect" the original?
> 
> Intersect is good but doesn't reveal an important detail: the operation is not commutative.

What about wedge(r, s) or r.wedge(s)? Perhaps meet(r, s) or r.meet(s)?

The source of these proposals is based on the symbols and terms used in the field of algebraic topology.  The meet operation in commutative topologies is the standard intersection, whereas in noncommutative topologies it is implemented employing noncommutative intersection.  In both cases the term (meet) and the symbol (wedge) are used.

Cheers!

Andrei Alexandrescu wrote:
> Dave wrote:
>>
>> "Andrei Alexandrescu" <SeeWebsiteForEmail@erdani.org> wrote in message news:gadn7c$oe5$4@digitalmars.com...
>>> Pablo Ripolles wrote:
>>>> Andrei Alexandrescu Wrote:
>>>>
>>>>> In wake of the many excellent comments and suggestions made here, I made one more pass through the draft proposal for ranges.
>>>>>
>>>>> http://ssli.ee.washington.edu/~aalexand/d/tmp/std_range.html
>>>>>
>>>>> There are some comments in red illustrating some uncertainties (not all), and the names of the primitives have been updated. Bicycle shed galore! But don't forget to comment on the reactor as well :o).
>>>>>
>>>>>
>>>>> Andrei
>>>>
>>>>
>>>> Well, it looks prety clean! :D
>>>>
>>>> However, I'm not completely sure I like these "head" and "toe" names selection.  It projects to much on it, doesn't it?  couldn't it be more neutral?  perhaps more conceptual?  I haven't been able to read the last days' comments... but my last impressions were that this "head" was not the best choice.
>>>>
>>>> If "head" is the header item, why not call it "header"?
>>>>
>>>> If ''toe" is the last item, why not call it "last"?
>>>>
>>>> Other comment goes for the "done" property, for the seek of consistence shouldn't it better be named "isDone"?
>>>>
>>>> Cheers!
>>>
>>> Thanks. One problem in coding with first and last was that sometimes the code looks unnatural, especially when your range exposes a few more functions. In a stream parser, dealing with the "first" element is not the most natural way to think of it. But I agree that first and last are definitely palatable and natural most of the time. But then again, shouldn't any design have the inevitable cutesy that makes it memorable? :o)
>>>
>>> Andrei
>>
>>  From the limited posts I've had the time to read, it seems this topic has probably been already beaten to death, but how about "tail" instead of "toe".
>>
>> And instead of the "yellow" primitive, why not "intersect(r,s)" , "intersection(r,s)", "r.contains(s)" , "r.intersect(s)" , etc.
>>
>> Wasn't "intersect" the original?
> 
> Intersect is good but doesn't reveal an important detail: the operation is not commutative.
> 
> Andrei

.cross ?
.across ?
.join ?
.onlyAlso ?

By the way, how does "yellow" not commutative?

KennyTM~ wrote:
> Andrei Alexandrescu wrote:
>> Dave wrote:
>>>
>>> "Andrei Alexandrescu" <SeeWebsiteForEmail@erdani.org> wrote in message news:gadn7c$oe5$4@digitalmars.com...
>>>> Pablo Ripolles wrote:
>>>>> Andrei Alexandrescu Wrote:
>>>>>
>>>>>> In wake of the many excellent comments and suggestions made here, I made one more pass through the draft proposal for ranges.
>>>>>>
>>>>>> http://ssli.ee.washington.edu/~aalexand/d/tmp/std_range.html
>>>>>>
>>>>>> There are some comments in red illustrating some uncertainties (not all), and the names of the primitives have been updated. Bicycle shed galore! But don't forget to comment on the reactor as well :o).
>>>>>>
>>>>>>
>>>>>> Andrei
>>>>>
>>>>>
>>>>> Well, it looks prety clean! :D
>>>>>
>>>>> However, I'm not completely sure I like these "head" and "toe" names selection.  It projects to much on it, doesn't it?  couldn't it be more neutral?  perhaps more conceptual?  I haven't been able to read the last days' comments... but my last impressions were that this "head" was not the best choice.
>>>>>
>>>>> If "head" is the header item, why not call it "header"?
>>>>>
>>>>> If ''toe" is the last item, why not call it "last"?
>>>>>
>>>>> Other comment goes for the "done" property, for the seek of consistence shouldn't it better be named "isDone"?
>>>>>
>>>>> Cheers!
>>>>
>>>> Thanks. One problem in coding with first and last was that sometimes the code looks unnatural, especially when your range exposes a few more functions. In a stream parser, dealing with the "first" element is not the most natural way to think of it. But I agree that first and last are definitely palatable and natural most of the time. But then again, shouldn't any design have the inevitable cutesy that makes it memorable? :o)
>>>>
>>>> Andrei
>>>
>>>  From the limited posts I've had the time to read, it seems this topic has probably been already beaten to death, but how about "tail" instead of "toe".
>>>
>>> And instead of the "yellow" primitive, why not "intersect(r,s)" , "intersection(r,s)", "r.contains(s)" , "r.intersect(s)" , etc.
>>>
>>> Wasn't "intersect" the original?
>>
>> Intersect is good but doesn't reveal an important detail: the operation is not commutative.
>>
>> Andrei
> 
> .cross ?
> .across ?
> .join ?
> .onlyAlso ?
> 
> By the way, how does "yellow" not commutative?

In the forward ranges realm, if you start from the wrong range, you
never get to compute the "yellow".

Andrei

Dave wrote:
> And instead of the "yellow" primitive, why not "intersect(r,s)" , "intersection(r,s)", "r.contains(s)" , "r.intersect(s)" , etc.

When I first read this, I thought it said
	yellow = intersect(r,g)
which, of course, only works in the RGB scheme.

:)

Andrei Alexandrescu wrote:
> Dave wrote:
>> And instead of the "yellow" primitive, why not "intersect(r,s)" , "intersection(r,s)", "r.contains(s)" , "r.intersect(s)" , etc.
>>
>> Wasn't "intersect" the original?
> 
> Intersect is good but doesn't reveal an important detail: the operation is not commutative.

How about 'overlap', then? Still not perfect, but at least it doesn't carry the name of an inherently commutative mathematical operation.

-Lars

Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Sergey Gromov wrote:
> > Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> >> Sergey Gromov wrote:
> >>> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> >>>> Given that in D const is transitive, we can't operate with const the same way C++ does. Consider something as trivial as a copy:
> >>>>
> >>>> Tgt copy(Src, Tgt)(Src src, Tgt tgt)
> >>>> {
> >>>>      for (; !src.done; src.next) tgt.put(src.tip);
> >>>> }
> >>>>
> >>>> Problem is, you won't be able to copy e.g. an int[][] to another because the types aren't compatible.
> >>> If Src is an input range you must make a deep copy.  This holds true for your current design also.  So this algorithm is flawed and it's good if it won't compile.
> >> Great point. I need to sleep on this some more.
> > 
> > Then I'll continue to think aloud.
> [snip]
> 
> Thanks for the code samples, they're cool. I hit a problem related to the return type of head. Consider writing a range that iterates two other ranges in lockstep. A very useful generic range. I started coding it like this:
> 
> struct Lockstep(R0, R1)
> {
>      private R0 _r0;
>      private R1 _r1;
>      this(R0 r0, R1 r1)
>      {
>         _r0 = r0;
>         _r1 = r1;
>      }
> 
>      bool empty()
>      {
>          return _r0.empty || _r1.empty;
>      }
> 
>      Tuple!(ElementType!(R0), ElementType!(R1)) head()
>      {
>          return tuple(_r0.head, _r1.head);
>      }
> 
>      void next()
>      {
>          _r0.next;
>          _r1.next;
>      }
> }

Thinking aloud is fun.  :P

What you basically want to achieve is that

	Lockstep l1, l2;
	l1.head = l2.head;

translates into

	l1._r0.head = l2._r0.head;
	l1._r1.head = l2._r1.head;

all by itself.  Umm...  The simplest for a programmer would be compiler- supported multiple return values and multiple assignment:

	ref typeof(R0.head), ref typeof(R1.head) head()
	{
	  return _r0.head, _r1.head;
	}

then

	l1.head = l2.head

is actually

	l1._r0.head, l1._r1.head = l2._r0.head, l2._r1.head;

I'm not expecting this to be implemented though.  Other methods, including returning a Tulpe!(), all return a struct.  There's no use in returning references there, even if we could, as long as structs are bit-copied.  All the tricks with reference fields rely substantially on the compiler performing specific actions on a per-field basis.

Sergey Gromov wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>> Sergey Gromov wrote:
>>> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>>> Sergey Gromov wrote:
>>>>> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>>>>> Given that in D const is transitive, we can't operate with const the same way C++ does. Consider something as trivial as a copy:
>>>>>>
>>>>>> Tgt copy(Src, Tgt)(Src src, Tgt tgt)
>>>>>> {
>>>>>>      for (; !src.done; src.next) tgt.put(src.tip);
>>>>>> }
>>>>>>
>>>>>> Problem is, you won't be able to copy e.g. an int[][] to another because the types aren't compatible.
>>>>> If Src is an input range you must make a deep copy.  This holds true for your current design also.  So this algorithm is flawed and it's good if it won't compile.
>>>> Great point. I need to sleep on this some more.
>>> Then I'll continue to think aloud.
>> [snip]
>>
>> Thanks for the code samples, they're cool. I hit a problem related to the return type of head. Consider writing a range that iterates two other ranges in lockstep. A very useful generic range. I started coding it like this:
>>
>> struct Lockstep(R0, R1)
>> {
>>      private R0 _r0;
>>      private R1 _r1;
>>      this(R0 r0, R1 r1)
>>      {
>>         _r0 = r0;
>>         _r1 = r1;
>>      }
>>
>>      bool empty()
>>      {
>>          return _r0.empty || _r1.empty;
>>      }
>>
>>      Tuple!(ElementType!(R0), ElementType!(R1)) head()
>>      {
>>          return tuple(_r0.head, _r1.head);
>>      }
>>
>>      void next()
>>      {
>>          _r0.next;
>>          _r1.next;
>>      }
>> }
> 
> Thinking aloud is fun.  :P
> 
> What you basically want to achieve is that
> 
> 	Lockstep l1, l2;
> 	l1.head = l2.head;
> 
> translates into
> 
> 	l1._r0.head = l2._r0.head;
> 	l1._r1.head = l2._r1.head;
> 
> all by itself.  Umm...  The simplest for a programmer would be compiler-
> supported multiple return values and multiple assignment:
> 
> 	ref typeof(R0.head), ref typeof(R1.head) head()
> 	{
> 	  return _r0.head, _r1.head;
> 	}
> 
> then
> 
> 	l1.head = l2.head
> 
> is actually
> 
> 	l1._r0.head, l1._r1.head = l2._r0.head, l2._r1.head;
> 
> I'm not expecting this to be implemented though.  Other methods, including returning a Tulpe!(), all return a struct.  There's no use in returning references there, even if we could, as long as structs are bit-copied.  All the tricks with reference fields rely substantially on the compiler performing specific actions on a per-field basis.

I figured a deceptively simple(r) solution. With apologies to Abba, I let the code speak:

/**
Defines a range that moves two given ranges in lockstep.
*/
struct Lockstep(R0, R1)
{
    struct ElementType
    {
        private R0 _r0;
        private R1 _r1;
        auto _0() { return _r0.head; }
        auto _1() { return _r1.head; }
    }
    private ElementType _e;

    this(R0 r0, R1 r1)
    {
       _e._r0 = r0;
       _e._r1 = r1;
    }

    bool empty()
    {
        return _e._r0.empty || _e._r1.empty;
    }

    ref ElementType head()
    {
        return _e;
    }

    void next()
    {
        _e._r0.next;
        _e._r1.next;
    }
}

Now when I write:

Lockstep.(RA, RB) r;
auto x = r.head._0;

then I simply access whatever RA.head returns, be it by reference or value. Problem solved.


Andrei

Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Sergey Gromov wrote:
> > What you basically want to achieve is that
> > 
> > 	Lockstep l1, l2;
> > 	l1.head = l2.head;
> > 
> > translates into
> > 
> > 	l1._r0.head = l2._r0.head;
> > 	l1._r1.head = l2._r1.head;
> > 
> > all by itself.  Umm...  The simplest for a programmer would be compiler- supported multiple return values and multiple assignment:
> > 
> > 	ref typeof(R0.head), ref typeof(R1.head) head()
> > 	{
> > 	  return _r0.head, _r1.head;
> > 	}
> > 
> > then
> > 
> > 	l1.head = l2.head
> > 
> > is actually
> > 
> > 	l1._r0.head, l1._r1.head = l2._r0.head, l2._r1.head;
> > 
> > I'm not expecting this to be implemented though.  Other methods, including returning a Tulpe!(), all return a struct.  There's no use in returning references there, even if we could, as long as structs are bit-copied.  All the tricks with reference fields rely substantially on the compiler performing specific actions on a per-field basis.
> 
> I figured a deceptively simple(r) solution. With apologies to Abba, I let the code speak:
> 
> /**
> Defines a range that moves two given ranges in lockstep.
> */
> struct Lockstep(R0, R1)
> {
>      struct ElementType
>      {
>          private R0 _r0;
>          private R1 _r1;
>          auto _0() { return _r0.head; }
>          auto _1() { return _r1.head; }
>      }
>      private ElementType _e;
> 
>      this(R0 r0, R1 r1)
>      {
>         _e._r0 = r0;
>         _e._r1 = r1;
>      }
> 
>      bool empty()
>      {
>          return _e._r0.empty || _e._r1.empty;
>      }
> 
>      ref ElementType head()
>      {
>          return _e;
>      }
> 
>      void next()
>      {
>          _e._r0.next;
>          _e._r1.next;
>      }
> }

Yes it should work.  I wish it were less complex though.  BTW here's another variant of your solution:

> struct Lockstep(R0, R1)
> {
>      private R0 _r0;
>      private R1 _r1;
>
>      private alias typeof(this) this_type;
>
>      struct ElementType
>      {
>          private this_type outer;
>          typeof(outer._r0.head) _0() { return outer._r0.head; }
>          typeof(outer._r0.head) _1() { return outer._r1.head; }
>      }
> 
>      this(R0 r0, R1 r1)
>      {
>         _r0 = r0;
>         _r1 = r1;
>      }
> 
>      bool empty()
>      {
>          return _r0.empty || _r1.empty;
>      }
> 
>      ElementType head()
>      {
>          return ElementType(this);
>      }
> 
>      void next()
>      {
>          _r0.next;
>          _r1.next;
>      }
> }

Andrei Alexandrescu wrote:
> Benji Smith wrote:
>> Andrei Alexandrescu wrote:
>>> In wake of the many excellent comments and suggestions made here, I made one more pass through the draft proposal for ranges.
>>>
>>> http://ssli.ee.washington.edu/~aalexand/d/tmp/std_range.html
>>>
>>> There are some comments in red illustrating some uncertainties (not all), and the names of the primitives have been updated. Bicycle shed galore! But don't forget to comment on the reactor as well :o).
>>
>> Well done. I think the design has come together very nicely. I'm especially happy with all the new names, which make a big difference for me in being able to visualize how the proposal works. The old names (fromLeft, etc) were very opaque to me.
>>
>> (btw: head & toe? i love it!)
>>
>> In its current state, this actually gets me pretty excited about D2. Maybe even enough to finally slog my way through all the const stuff.
>>
>> One tiny typo, though: In the "Forward range" section, the code sample still uses "left" instead of "head".
> 
> Fixed, thanks.
> 
>> And, there are two sections (which I think are related to one another) that left me scratching my head:
>>
>> Input Ranges:
>> "In case ElementType!(R) has aliases (such as a reference, pointer, or array type), the iterator is free to recycle it it upon the call to r.next, so client code must do a deep copy if preserving the value is needed. [NOTE: This is a weakness in the design. A better way of figuring recycling should be found.] The call is defined only right after r.done returned false."
>>
>> Forward Ranges:
>> "Also, forward ranges iterate over "real" elements, which makes in-place mutation of r.head possible."
>>
>> Those paragraphs are completely greek to me. Can you elaborate?
> 
> Consider iterating over an array of int[], specifically an int[][]. Then when you call r.head you see the current int[]. You can store it and use it a few steps later or even after the iteration is done for as long as the array is around.
> 
> Contrast that with iterating a file containing lines of integers. The file has a buffer of type int[]. Every time you call r.next, the file range reads a new line, parses the integers, and REFILLS the array with them. If if generated a new array every line, that would cause a great deal of allocations.
> 
> Same about the in-place thing. If you modify elements in the array, they stay modified. If you modify the buffer of a file, your changes get overwritten upon r.next.
> 
> 
> Andrei

How about having the element type of the file-containing-lines-of-integers range be const(int[]) instead of int[]?
I think it would solve the ownership problem, but it might introduce other problems, such as, how to make InputRange!(int[]) be covariant with InputRange!(const(int[]).

-- 
Bruno Medeiros - Software Developer, MSc. in CS/E graduate
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D