Bill Baxter <wbaxter@gmail.com> wrote:
> On Fri, Sep 12, 2008 at 11:22 PM, Sergey Gromov <snake.scaly@gmail.com> wrote:
> > Bill Baxter <wbaxter@gmail.com> wrote:
> >> But I do have some suggestions nonetheless!  Marked with ==> below.
> >>
> >> -- Universal --
> >> r.done
> >> r.init
> >>
> >> --- Input : Universal ---
> >> e=r.head
> >> e=r.next
> >> r1=r.release  ==> r.transfer?  Release sounds like ref counting (e.g. in COM)
> >>                           Also seems like r.transfer(r1) could make
> >> implementation more efficient.
> >>                           Or perhaps make it a .swap like STL.  Maybe
> >> you have something against .swap?
> >>
> >> -- Output : Universal --
> >> r.put(e)
> >>
> >> -- Forward : Input, (optional) Output  --
> >> r1 = r
> >> r.head = e
> >> t=r.after(s)
> >>
> >> -- Bidirectional : Forward --
> >> e = r.toe
> >> r.toe = e
> >> r.reduce           ==> r.retreat  -- aka "pull back"
> >> t = r.before(s)
> >>
> >> -- Random access : Bidirectional --
> >> l = r.length
> >> e = r[n]
> >> r[n] = e
> >> r1 = r[n1..n2]
> >> ------------
> >>
> >> Just those two!
> >
> > I've got a bit of insight!  XD
> >
> > -- Common
> > r.empty
> >
> > -- InOut
> > v = r.next;     => T R.next();
> > r.next = v;     => T R.next(T v);
> >
> > -- Forward: InOut, copyable
> > v = r.tip
> > r.tip = v
> > r1 = r.before(s)
> > r1 = r.after(s)
> >
> > -- Bidir: Forward
> > v = r.prev
> > r.prev = v
> > v = r.toe
> > r.toe = v
> >
> > -- Random: Bidir
> > no changes
> >
> > prev() seems very misleading, otherwise I like it.
> >
> 
> So basically you changed
> done ==> empty
> head ==> tip
> retreat ==> prev
> ?

The insight was about get/put ==> next.  That's the most significant change, others are merely renames as you rightfully point out.  Hence the "prev" which should mean both "get at the end" and "put to the end".

> "prev" is horrible.  I still like "retreat" best so far.  We need the contrapositive of "next" not the "opposite".  :-)  And since that doesn't exist we should just go for a word that sorta means the right thing and won't be  confused with being the opposite (or with being something else entirely like "reduce").

v = r.retreat
r.retreat = v

It's definitely better than prev.  Thank you for proposing.  I'm not a native speaker so inventing names could be a tricky business for me.

Bill Baxter wrote:
> On Fri, Sep 12, 2008 at 11:22 PM, Sergey Gromov <snake.scaly@gmail.com> wrote:
> I'm actually ok with either "done" or "empty".  "Done" is weird on a
> random access range, but "empty" is weird on file input range, or a
> generator.  Or on the HMM example which is "done" when it reaches an
> end state, but is not really "empty".

That's exactly right. "Empty" is a state, and "done", while also a state, also evokes process. I found it very nice to write stream ranges that become "done" after some point. "Empty" was less clear because it suggested e.g. the underlying file is empty.

On the other hand it's odd to receive a fresh new range and ask yourself whether it's "done".

As I wrote Walter and Bartosz a while ago, this all reminds me of a funny dialog in Alice in Wonderland (http://www.cs.indiana.edu/metastuff/wonder/ch7.html):

`Take some more tea,' the March Hare said to Alice, very earnestly.

`I've had nothing yet,' Alice replied in an offended tone, `so I can't take more.'

`You mean you can't take LESS,' said the Hatter: `it's very easy to take MORE than nothing.'

> "head to toe" is a perfectly common expression, at least in American
> English.  Not sure why you don't like it.  But tip to toe is kinda
> cool for being 1 less letter!  And no less clear.

I like "tip" too. And as Pablo said, it's less anthropocentric than head+toe.

You know what's the name of Sergey's empty range that lies right at the end of a range? Toenail! :o)

> "prev" is horrible.  I still like "retreat" best so far.  We need the
> contrapositive of "next" not the "opposite".  :-)  And since that
> doesn't exist we should just go for a word that sorta means the right
> thing and won't be  confused with being the opposite (or with being
> something else entirely like "reduce").

Retreat is a great word. I replaced reduce with it. That was easy because this time I had the foresight of defining ddoc macros for all primitive names :o). Thanks!


Andrei

On Fri, Sep 12, 2008 at 11:39 PM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Pablo Ripolles wrote:
>>
>> What about "isDone"?
>
> isDone is great, I just wanted to keep the one-word streak going. Let's see what everyone else says.

Hmm.  std.algorithm does have an "isSorted" function.  So I guess I agree it would be more consistent if you call it isDone or isEmpty.

Or rename "isSorted" to "sorted".  :-)  But then you have to face the consequences later when you want to have a predicate that is ambiguous without the "is".    Probably a lot of noun predicates are in that category -- i.e. checking  isSomeNoun(x).  Like "isRange(x)" to see if x is a range.  That would have to just become "range(x)" which is a bit ambiguous.

So I agree. Stick the "is" in there.

--bb

Bill Baxter wrote:
> On Fri, Sep 12, 2008 at 11:39 PM, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>> Pablo Ripolles wrote:
>>> What about "isDone"?
>> isDone is great, I just wanted to keep the one-word streak going. Let's see
>> what everyone else says.
> 
> Hmm.  std.algorithm does have an "isSorted" function.  So I guess I
> agree it would be more consistent if you call it isDone or isEmpty.
> 
> Or rename "isSorted" to "sorted".  :-)  But then you have to face the
> consequences later when you want to have a predicate that is ambiguous
> without the "is".    Probably a lot of noun predicates are in that
> category -- i.e. checking  isSomeNoun(x).  Like "isRange(x)" to see if
> x is a range.  That would have to just become "range(x)" which is a
> bit ambiguous.
> 
> So I agree. Stick the "is" in there.

Thing is, people will call isSorted much less often than (isD|d)one. In std.algorithm clearly the one-word paradigm can't scale. But for a handful of heavily-used names I'd be willing to take the Pepsi challenge.

Andrei

P.S. The more I think of it, the more I like "tip" of the range. Short, poignant, easy to remember. Not pressing the red button just yet.

On Sat, Sep 13, 2008 at 12:03 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Bill Baxter wrote:
>>
>> On Fri, Sep 12, 2008 at 11:39 PM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>>>
>>> Pablo Ripolles wrote:
>>>>
>>>> What about "isDone"?
>>>
>>> isDone is great, I just wanted to keep the one-word streak going. Let's
>>> see
>>> what everyone else says.
>>
>> Hmm.  std.algorithm does have an "isSorted" function.  So I guess I agree it would be more consistent if you call it isDone or isEmpty.
>>
>> Or rename "isSorted" to "sorted".  :-)  But then you have to face the consequences later when you want to have a predicate that is ambiguous without the "is".    Probably a lot of noun predicates are in that category -- i.e. checking  isSomeNoun(x).  Like "isRange(x)" to see if x is a range.  That would have to just become "range(x)" which is a bit ambiguous.
>>
>> So I agree. Stick the "is" in there.
>
> Thing is, people will call isSorted much less often than (isD|d)one. In std.algorithm clearly the one-word paradigm can't scale. But for a handful of heavily-used names I'd be willing to take the Pepsi challenge.
>
> Andrei
>
> P.S. The more I think of it, the more I like "tip" of the range. Short, poignant, easy to remember. Not pressing the red button just yet.

Hmm.  One semantic issue I have is that the tip usually refers to the infinitessimal point at the end.  Not a thing with substance.  I'm having trouble feeling like I'm going to get an item back when I look at "x.tip".  Head has huge history being used for the item at the front of a list, so I think that's much less likely to cause anyone looking at D code to scratch their heads.  It will be obvious what it means even in relative isolation.  head/tip will often appear without "toe" in forward range algos.  So you need to be able to easily recognize what "tip" means without seeing that "toe" to give context. Toe on the other hand will probably almost always appear with his mate.

Ooh, another scale thing, but a head is obviously a very different scale than a toe.  A foot is closer to the same scale.  Maybe head/foot is better than head/toe.  The connection between retreating / feet is stronger that retreating / toes, too!

--bb

Andrei Alexandrescu Wrote:

> Bill Baxter wrote:
> > On Fri, Sep 12, 2008 at 11:39 PM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> >> Pablo Ripolles wrote:
> >>> What about "isDone"?
> >> isDone is great, I just wanted to keep the one-word streak going. Let's see what everyone else says.
> > 
> > Hmm.  std.algorithm does have an "isSorted" function.  So I guess I agree it would be more consistent if you call it isDone or isEmpty.
> > 
> > Or rename "isSorted" to "sorted".  :-)  But then you have to face the consequences later when you want to have a predicate that is ambiguous without the "is".    Probably a lot of noun predicates are in that category -- i.e. checking  isSomeNoun(x).  Like "isRange(x)" to see if x is a range.  That would have to just become "range(x)" which is a bit ambiguous.
> > 
> > So I agree. Stick the "is" in there.
> 
> Thing is, people will call isSorted much less often than (isD|d)one. In std.algorithm clearly the one-word paradigm can't scale. But for a handful of heavily-used names I'd be willing to take the Pepsi challenge.
> 
> Andrei
> 
> P.S. The more I think of it, the more I like "tip" of the range. Short, poignant, easy to remember. Not pressing the red button just yet.

brilliant! I think "tip" is just fantastic!

"head" and "tip" wonderful couple.

yes, *this* one is as neutral as it can be! besides, the tip of something is unique! if you hold something by its toe, which one of how many are you holding? :)

when I name boolean identifiers, I kind follow these "rules":

*properties:
the instance is the grammatical subject, so it is very natural to use "is" as in self.isDone

*scalar variables:
I tend to append the "whether" as in whetherDone

*array variables:
here you have that the index to access the value is related to the grammatical subject, then I use something as visited[i]

*functions:
here you have that the argument to be passed to the function might be the grammatical subject, then I use something as searched(x) or pointIsInCell(P, C)

Its always nice that a std library is as regular as it can be, perhaps as your own library.  for special, particular words we already have the keywords, right?

Cheers!

Sergey Gromov wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> 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).
> 
> I've got a heap of virtual sticky notes all over my monitor while reading the edited version, so here they are.
> 
> *)
> done/next/head thing got even more confusing.  Range is not a process, you cannot be done with it.  If you call a spade a spade, then done() is actually a safe, guarded prefetch, head is, well, sort of what it claims to be, and next() just relaxes done's guard.

The art is to find something that's reasonably evocative without being too long. I doubt safeGuardedPrefetch will fare very well, although I agree it's very precise. Inevitably a shorter word will also be less precise.

> The look ahead/fetch next approach was much more intuitive.  I don't understand why you dropped it.  I remember you saying that Bill convinced you it was wrong but I either missed the arguments themselves or hadn't understood them.
> 
> *)
> How do you enforce noncopyable/release semantics over a range?  I don't think D got any means for that.  Also if an input range is a class passed by reference, will you allow it?

Walter is working on adding that feature now.

> *)
> before() is valid for a single-linked list, forward iterators should support it.

This is subtle. Consider a singly-linked list that uses a Node* as a range. Condition for termination is p.next == null.

Now to build list.before(another) you'd have to express a fragment of a list, so the one-Node* representation is insufficient. You have to return a range with TWO Node* objects, one pointing to the beginning and the other to the end of the fragment.

That can be done, but it also means that the before operation is not closed under your Range type. You'd have to return a different Range type, a fatter one.

Or we could impose that all lists use fat ranges to start with. But I don't want that. I hate people discussing, "Oh you want a list? use std.slist, it's cool. But beware, if you want a really fast list you better do it yourself." This is a no-go because whenever you're in the mood of using a singly-linked list, it being lightweight is invariably the main concern.

So I want to write a singly-linked list that is as fast as the classic singly-linked list implemented by hand from first principles. If we fail to do so, we can as well go home. If we want to achieve that, we need to model the slist fundamentals properly. Part of that proper modeling is that slist is not closed under the "before" operation.

> *)
> You've replaced tail with toe because people may think tail could contain many elements.  But it doesn't pair well with head, and besides, if I split a list in the middle I'd call the halves a head and a tail which form a logical pair.  Maybe you consider tip-toe, or top-toe, from the top of my head? ;)

Head to toe is culturally appealing for English speakers. But tip to toe is also cool. Nice tip, thanks. :o)

> *)
> A typo: in Output range sample:
> 	for (; !src.done; src.head)
> should be
> 	for (; !src.done; src.next)

Fixed, thanks.

> *)
> next() is specified to return a value, but reduce() is not.  This is probably a typo.  I'd prefer them both be implemented as (done(), head) and (reduce(), toe) respectively, but I don't know what your intention was.

Neither of next and retreat should return a value. In wake of constructors/destructors, we shouldn't return by-value lightly.

> *)
> Still uncertain support for shrink-on-read, no support for shrink-on-
> write and slicing forward and bidirectional ranges.  Are they going into a library?

Yes, excellent point. The document on ranges tells what they must define. The standard library can and will define convenience functions using those primitives. This is appealing because there will be many range implementations and you don't want to burden everyone with implementing a ton of non-orthogonal stuff.


Andrei

Bill Baxter wrote:
> On Fri, Sep 12, 2008 at 2:44 PM, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> 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).
>>
> 
> Looking better!
> 
> I disagree with this:
> """
> User code may pair iterators wrongly to create meaningless ranges. For
> example, given collections a and b of the same type, a.begin to
> b.begin makes no sense as a range, yet both the compiler and the
> runtime are hard-pressed in rejecting such mistakes. Such problems are
> often (though not always) avoided if range is the primitive.
> """
> 
> You can just as easily create nonsensical ranges using before() and
> after().  And I don't recall ever making the mistake of mixing up one
> container's begin() with another's end().
> 
> I disagree here too:
> """
> A bidirectional range models the natural way of iterating a doubly-linked list.
> """
> It maybe provides an efficient way to implement many algorithms on a
> doubly linked list.  But to say it implements the natural way of
> iterating one is a big stretch.

I hear you! I'll amend the doc later.

> r1=r.release  ==> r.transfer?  Release sounds like ref counting (e.g. in COM)
>                           Also seems like r.transfer(r1) could make
> implementation more efficient.
>                           Or perhaps make it a .swap like STL.  Maybe
> you have something against .swap?

Are you kidding? I wrote the best swap in the world. Check the source of std.algorithm.

You'll have to convince Bartosz about dropping the name "release". He held a gun to my head, and five of the six chambers were loaded. Couldn't take the risk. As far as efficiency goes, Walter has RVO down and all so I'm not worried.


Andrei

Steven Schveighoffer 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).
> 
> You know my position ;)  But here are some things:
> 
> 1. I like the new names of things much better.  This is a much prettier bicycle shed :)  And in this case, I think the bicycle shed is a little closer to the heart of the design than the nuclear reactor.  Maybe the core is better described as a bicycle shop :)
> 
> 2. Saw this typo in the section on input range:
> 
> e=r.head Returns the element at the current position, which is of type ElementType!(R). 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...

Fixed, thanks. You see, it's your influence :o).

> 3. In output iterator (more bicycle shed stuff):
> 
> writing one object and moving to the next one are an organic operation
> 
> What's an organic operation?  I'm assuming it means 'coupled' like you can't do one without the other?  I've never heard that term before.

http://www.merriam-webster.com/dictionary/organic

(2): of, relating to, yielding, or involving the use of food produced with the use of feed or fertilizer of plant or animal origin without employment of chemically formulated fertilizers, growth stimulants, antibiotics, or pesticides

Just wanted to throw you off :o). This one:

4 a: forming an integral element of a whole : fundamental <incidental music rather than organic parts of the action — Francis Fergusson> b: having systematic coordination of parts : organized <an organic whole>


Andrei

Jason House 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).
> 
> The colorful diagram is nice, but it doesn't belong at the top of the
> article.  Is it possible to find a better spot?  It may be best
> following the "Coding with ranges also has disadvatages" paragraph.

I agree. I just plopped it in there in an intermediate revision and left
it there. Moved it now.

> PS: You're missing an n in disadvantages.  I read past it several
> times, but my spell checker caught it.

Thanks, fixed. I keep on hoping someone develops a simple way for emacs to spellcheck comments...


Andrei