www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Ranges - Question about desing choices

reply "Michal Minich" <michal.minich gmail.com> writes:
I'm thinking about ranges I can think of similar design of the 
input range, but with different pros and cons. Obviously not 
for/in D. Currently ranges has 3 primitive operations, and they 
can be translated from foreach like:

for (auto __r = range; !__r.empty; __r.popFront())
{
     auto e = __r.front;
     ...
}

I'm thinking of design where range  would have only 2 primitive 
operations:

    bool popFront()  // returns true if current will have an 
element
    front            // it may be called only if popFrount (would) 
have returned true

foreach would be translated to:

while (auto r = r.popFront())
{
     auto e = __r.front;
     ...
}

This design results in following differences

1) 2 primitive operations (empty and popFront) are merge into one 
less primitive

2) it will result in less calls per item (2 instead for 3)

3) it is not possible to "ask" a range if it's empty more times 
per iteration of one item

4) it does _not_ requires range to be in "ready" state 
immediately after construction. That means that popFront needs to 
be called firstly, before front can be. This I feel is biggest 
change. Since D ranges are required to have front ready 
immediately after their construction. Which for some non trivial 
ranges can seem as less effective/convenient/expected.

I would be interested what do you think about this possible 
design. Does it have some special flaws in general, or 
specifically for D. What are the advantages of current design. Do 
you think it would be reasonable in some other language? What do 
you think is better in practice from point of view of 
implementors and users of range: that range has ready front 
immediately, or better to have it ready only after first popFront 
call.

Thank you.
Aug 24 2015
next sibling parent reply "Adam D. Ruppe" <destructionator gmail.com> writes:
On Monday, 24 August 2015 at 15:09:14 UTC, Michal Minich wrote:

 What are the advantages of current design.


One advantage of the current design is you can statically 
determine if something is an infinite range by seeing if empty is 
a constant false. With your change, you could never be sure if 
something was infinite or not since popFront would just keep 
returning true.

It is also sometimes useful to see if something is empty without 
modifying it, like when doing a wrapper.
Aug 24 2015
next sibling parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Mon, Aug 24, 2015 at 03:16:10PM +0000, Adam D. Ruppe via Digitalmars-d-learn
wrote:

 On Monday, 24 August 2015 at 15:09:14 UTC, Michal Minich wrote:

What are the advantages of current design.


 
 One advantage of the current design is you can statically determine if
 something is an infinite range by seeing if empty is a constant false.
 With your change, you could never be sure if something was infinite or
 not since popFront would just keep returning true.
 
 It is also sometimes useful to see if something is empty without
 modifying it, like when doing a wrapper.


[...]

It's also useful in parsing algorithms to look at the current item in
the input without also consuming it.


T

-- 
Right now I'm having amnesia and deja vu at the same time. I think I've
forgotten this before.
Aug 24 2015
parent "Michal Minich" <michal.minich gmail.com> writes:
On Monday, 24 August 2015 at 15:23:09 UTC, H. S. Teoh wrote:

 It's also useful in parsing algorithms to look at the current 
 item in the input without also consuming it.


I design I outlined the 'front' property could still be called 
multiple times. It is the 'empty' property that would be merged 
into 'bool popFront'.
Aug 24 2015
prev sibling next sibling parent "Michal Minich" <michal.minich gmail.com> writes:
On Monday, 24 August 2015 at 15:16:12 UTC, Adam D. Ruppe wrote:


 One advantage of the current design is you can statically 
 determine if something is an infinite range by seeing if empty 
 is a constant false.


That is important aspect! By having this information at compile 
or runtime, you can enforce that algorithms which consume entire 
range, and are expected to finish, would not accept this range as 
an argument, for example saveToFile(randomNumbersRange).

I see two possible way to model this:

1) provide another property 'bool isInifinite'. This of course 
causes dependency on empty property: when isInfinte is false, 
empty also needs to be false. This can be complex to enforce.

2) instead of empty property, have state property, returning enum 
{ empty, full, infinite }. This might complicate algorithms 
implementation, and of course this enum could not be never 
extended, since it would be breaking change. For example if 
algorithm ask currently for !empty, it would ask for just state 
== full, so it might not complicate many algorithms

Any more insights? :)
Aug 24 2015
prev sibling parent "Michal Minich" <michal.minich gmail.com> writes:
Looking at the random access range, if the indexing must be done 
just by numeric value, or also by other type, like string 
(typically used for dictionaries) or also custom object?
Aug 24 2015
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 8/24/15 11:09 AM, Michal Minich wrote:

 I'm thinking about ranges I can think of similar design of the input
 range, but with different pros and cons. Obviously not for/in D.
 Currently ranges has 3 primitive operations, and they can be translated
 from foreach like:

 for (auto __r = range; !__r.empty; __r.popFront())
 {
      auto e = __r.front;
      ...
 }

 I'm thinking of design where range  would have only 2 primitive operations:

     bool popFront()  // returns true if current will have an element
     front            // it may be called only if popFrount (would) have
 returned true

 foreach would be translated to:

 while (auto r = r.popFront())
 {
      auto e = __r.front;
      ...
 }

 This design results in following differences

 1) 2 primitive operations (empty and popFront) are merge into one less
 primitive

 2) it will result in less calls per item (2 instead for 3)

 3) it is not possible to "ask" a range if it's empty more times per
 iteration of one item


This isn't very composable. If I call a function that consumes some 
number of items from a range, that function needs to forward the 
information back to me of whether the range is now empty or not.


 4) it does _not_ requires range to be in "ready" state immediately after
 construction. That means that popFront needs to be called firstly,
 before front can be. This I feel is biggest change. Since D ranges are
 required to have front ready immediately after their construction. Which
 for some non trivial ranges can seem as less effective/convenient/expected.


So on the flip side, ranges that *could* be ready as soon as they are 
created, must store some state that says popFront hasn't yet been 
called. I find this requirement to be a wash implementation-wise, and 
actually a negative API wise, since you as the consumer of the range 
must carry the burden of storing whether it was empty the last time 
popFront was called.

I would challenge you to write a wrapper for an array slice (yes, you 
would need a wrapper, not just simple UFCS functions) and see whether 
you think it's still worth it.

-Steve
Aug 24 2015
parent reply "Michal Minich" <michal.minich gmail.com> writes:
On Monday, 24 August 2015 at 17:17:16 UTC, Steven Schveighoffer 
wrote:

 3) it is not possible to "ask" a range if it's empty more 
 times per
 iteration of one item


 This isn't very composable. If I call a function that consumes 
 some number of items from a range, that function needs to 
 forward the information back to me of whether the range is now 
 empty or not.


That is a very good point. Non-existence of 'empty' property 
would have negative impact on composability and convenience of 
use if range is shared between alogorithms (For example in a 
parser). As you say that information would need to be transferred 
in program using another means. I see this composability aspect 
as critical, and for me it alone makes 100% case for the 
existence of 'empty' property.

 4) it does _not_ requires range to be in "ready" state 
 immediately after
 construction. That means that popFront needs to be called 
 firstly,
 before front can be. This I feel is biggest change. Since D 
 ranges are
 required to have front ready immediately after their 
 construction. Which
 for some non trivial ranges can seem as less 
 effective/convenient/expected.


 So on the flip side, ranges that *could* be ready as soon as 
 they are created, must store some state that says popFront 
 hasn't yet been called. I find this requirement to be a wash 
 implementation-wise, and actually a negative API wise, since 
 you as the consumer of the range must carry the burden of 
 storing whether it was empty the last time popFront was called.

 I would challenge you to write a wrapper for an array slice 
 (yes, you would need a wrapper, not just simple UFCS functions) 
 and see whether you think it's still worth it.

 -Steve


Ok. What about this: there exactly the same 3 primitives as in D 
range, but popFront is requred to be called first, before calling 
front, or empty properties. Why current approach against this?
Aug 24 2015
parent "cym13" <cpicard openmailbox.org> writes:
On Monday, 24 August 2015 at 17:59:00 UTC, Michal Minich wrote:

 Ok. What about this: there exactly the same 3 primitives as in 
 D range, but popFront is requred to be called first, before 
 calling front, or empty properties. Why current approach 
 against this?


Wouldn't that mean a null placeholder for the first popFront? 
That could be done though.

However I'm not certain I understand what you wrote, do you mean 
that in foreach loops popFront would be called first or do you 
mean that each time you call front or empty the popFront method 
is called beforehand?

I don't have much opinion about the former, but the later would 
be very problematic.
Aug 25 2015