www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Rust switches to external iteration

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Evidence we've done the right thing by emphasizing ranges instead of 
opApply.

http://www.reddit.com/r/programming/comments/1hl2qr/rust_07_released/
https://mail.mozilla.org/pipermail/rust-dev/2013-June/004599.html

Andrei
Jul 03 2013
next sibling parent reply Russel Winder <russel winder.org.uk> writes:
On Wed, 2013-07-03 at 22:04 -0700, Andrei Alexandrescu wrote:

 Evidence we've done the right thing by emphasizing ranges instead of=20
 opApply.
=20
 http://www.reddit.com/r/programming/comments/1hl2qr/rust_07_released/
 https://mail.mozilla.org/pipermail/rust-dev/2013-June/004599.html


I am not sure you can make that deduction. The question of internal vs.
external iterators is not black and white. Both are needed. The question
is what is the balance of usage, and it depends on which level of the
programming "stack " you are at. People working on implementing
frameworks and APIs often need explicit iteration to realize their
abstractions, but can also use some internal iteration as that
abstraction works for them at that point. For applications programmers,
I would expect most of them to benefit from using internal iteration as
much as possible since they are users of frameworks and APIs, but the
availability=20

The difficulty is that we have some serious inertia in the system.

Many programmers are still using 1970s approaches to programming, even
though they may be 20-something, because that is what they have been
taught to do. As long as they use sequence, selection and iteration that
is all they need.

At the other extreme there are the Lambda Calculus purists who try to
instil that you have to undertake the Category Theory analysis to
construction the point-free function compositions prior to writing any
code.

And neither of these groups worry about test coverage that much.

The goal has to be to write code that is appropriate to the task,
readable, comprehensible, testable and tested. It is all about Domain
Specific Languages (DSL). Any program that uses functions and procedures
is creating a DSL. Abstraction and DSL go hand in hand. We are giving a
concept a label and a meaning.

By trying to make internal vs external a black and white type argument,
we lose something from our toolkit. By trying to work on where is
internal appropriate, where is external appropriate, we move software
development on further. The whole object-oriented vs. generic vs.
functional vs. logic models, especially the OO vs. functional just now
is an important move of programming into the future.

FOOPLOG may have failed but Scala has brought programming to functional
AND object-oriented. Groovy, Kotlin, Ceylon, etc. are pushing at this as
well. It is all about the balance of use of internal and external
iteration not treating it as warfare. Python had its own consideration
of these issues in the Python 2 =E2=86=92 Python 3 change.

Native still seems to be in the 1990s OO vs. functional war: internal OR


My current hypothesis is that the more abstract the DSL the more
internal iteration. Moving from implementation focus to goal focus
naturally introduces more implicit as the DSL becomes more abstract.=20
=20
But I get too serious and philosophical. It is perhaps because I have
just finished a two day workshop guiding people to consider these
questions in a very practical way so as to improve their software
development.
--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
Jul 04 2013
next sibling parent reply "Paulo Pinto" <pjmlp progtools.org> writes:
On Thursday, 4 July 2013 at 07:20:18 UTC, Russel Winder wrote:

 [..]
 Many programmers are still using 1970s approaches to 
 programming, even
 though they may be 20-something, because that is what they have 
 been
 taught to do. As long as they use sequence, selection and 
 iteration that
 is all they need.


Even on the work environment.

Every time I see the usual shell and vi/emacs combo it brings me
back memories of when my home computer was a Timex 2068.

Or as someone puts it,

http://andrewbrookins.com/tech/one-year-later-an-epic-review-of-pycharm-2-7-from-a-vim-users-perspective/



 And neither of these groups worry about test coverage that much.


To be honest in the fortune 500 companies very few do. We always
try to push for it in our consulting projects, but not all 
customers
buy into it, specially if the project requires interaction with 
the
in-house developers.


 FOOPLOG may have failed but Scala has brought programming to 
 functional
 AND object-oriented. Groovy, Kotlin, Ceylon, etc. are pushing 
 at this as
 well. It is all about the balance of use of internal and 
 external
 iteration not treating it as warfare. Python had its own 
 consideration
 of these issues in the Python 2 → Python 3 change.


I think Microsoft plays a big role here. By sponsoring OCaml,

enterprise via LINQ.



 Native still seems to be in the 1990s OO vs. functional war: 
 internal OR



The main issue is that this is very human related.

Sometimes you really need a few generations to make people adopt 
new ideas.

--
Paulo
Jul 04 2013
parent Russel Winder <russel winder.org.uk> writes:
On Thu, 2013-07-04 at 11:35 +0200, Paulo Pinto wrote:
[=E2=80=A6]

 Every time I see the usual shell and vi/emacs combo it brings me
 back memories of when my home computer was a Timex 2068.
=20
 Or as someone puts it,
=20
 http://andrewbrookins.com/tech/one-year-later-an-epic-review-of-pycharm-2=


-7-from-a-vim-users-perspective/

I think the USP for IDEs is when you have to debug, otherwise it is just
a matter of personal taste.  I tend to use Emacs because it can reformat
just comment blocks in a file, none of the IDE editors can do this, and
for me this is an important thing.=20
=20

 And neither of these groups worry about test coverage that much.


=20
 To be honest in the fortune 500 companies very few do. We always
 try to push for it in our consulting projects, but not all=20
 customers
 buy into it, specially if the project requires interaction with=20
 the
 in-house developers.


Perhaps stock prices should be linked to code coverage statistics for
that company. It is about as good a measure as the gamblers, sorry
traders, use =E2=80=93 which seems to rely most on whether the CEO sneezed =
at
the time the traders specified they should.


 I think Microsoft plays a big role here. By sponsoring OCaml,

 enterprise via LINQ.


Agreed, and I hate to give Microsoft credit for anything positive, but
here they definitely have. Sad they dropped IronPython and IronRuby
though.


 The main issue is that this is very human related.
=20
 Sometimes you really need a few generations to make people adopt=20
 new ideas.


Not if ideas are reified in the programming language. Java brought
shared memory multi-threading front and centre (or should that be
center?) and it remains the biggest barrier to quality software we have.
Programmers see the feature and use it despite the fact that it had been
known for 20 years prior to 1995 that it was the wrong way forward for
applications development. Actors, dataflow, CSP, data parallelism,
masses of great high level models for concurrency and parallelism all
ignore. And now C++11 nearly did almost the same thing. At least thanks
to the UK vote C++ includes asynchronous function call and futures. All
the rest of C++ threads stuff, like Java, is already 40 years behind
well tried and trusted approaches.

--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
Jul 04 2013
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/4/13 12:20 AM, Russel Winder wrote:

 On Wed, 2013-07-03 at 22:04 -0700, Andrei Alexandrescu wrote:

 Evidence we've done the right thing by emphasizing ranges instead of
 opApply.

 http://www.reddit.com/r/programming/comments/1hl2qr/rust_07_released/
 https://mail.mozilla.org/pipermail/rust-dev/2013-June/004599.html


 I am not sure you can make that deduction. The question of internal vs.
 external iterators is not black and white.


One might have said I thought so if I wrote e.g. "completely eliminated 
opApply in favor of ranges". D is a multi-paradigm language. That being 
said, there is value in Occam reduction of the core/preferred 
abstractions to be used throughout. D put its bet on ranges (i.e. 
external iteration), not opApply (internal iteration).


 Native still seems to be in the 1990s OO vs. functional war: internal OR



I think this characterization is a tad unfair to D. We clearly and 
deliberately espouse interoperation of paradigms: the const/immutable 
qualifiers bridge mutability with immutability, safe/system/trusted 
allow interoperation of system and safe code, opApply complements 
ranges. At each step we foster seamless integration of major paradigms, 
not forcing a choice between them.


 But I get too serious and philosophical. It is perhaps because I have
 just finished a two day workshop guiding people to consider these
 questions in a very practical way so as to improve their software
 development.


Those can be real fun.


Andrei
Jul 04 2013
prev sibling next sibling parent reply "w0rp" <devw0rp gmail.com> writes:
 In the future, Rust can have generators using a `yield` 

  compiling down to a fast state machine without requiring 
 context switches,
  virtual functions or even closures. This would eliminate the 
 difficulty of
  coding recursive traversals by-hand with external iterators.


It would be nice to beat them to the punch on this. Yield is a 
great tool. You can implement not so bad yield-like behaviour 
yourself in D, though. I have an old example that I baked up a 
while ago.

http://pastebin.com/EGqLHk0U

I'd prioritise important matters like improving the garbage 
collector and other non-language changing, but definitely 
beneficial improvements, over a big language addition like yield, 
though.
Jul 04 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
w0rp:


 It would be nice to beat them to the punch on this. Yield is a 
 great tool. You can implement not so bad yield-like behaviour 
 yourself in D, though. I have an old example that I baked up a 
 while ago.

 http://pastebin.com/EGqLHk0U

 I'd prioritise important matters like improving the garbage 
 collector and other non-language changing, but definitely 
 beneficial improvements, over a big language addition like 
 yield, though.


+1

Bye,
bearophile
Jul 04 2013
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 07/04/2013 07:04 AM, Andrei Alexandrescu wrote:

 Evidence we've done the right thing by emphasizing ranges instead of
 opApply.

 http://www.reddit.com/r/programming/comments/1hl2qr/rust_07_released/
 https://mail.mozilla.org/pipermail/rust-dev/2013-June/004599.html

 Andrei


Well, probably, but implementing ranges is still too tedious.
It is very likely that rust is going to fix that.

It should be as simple as:

auto map(alias a,R)(R r){
     foreach(x;r)
         yield a(x);
}

auto filter(alias a,R)(R r){
     foreach(x;r)
         if(a(x))
             yield x;
}

auto take(R)(R r,size_t i){
     while(i--&&!r.empty){
         yield r.front;
         r.popFront();
     }
}

auto joiner(R,S)(R r,S s){
     if(r.empty) break;
     foreach(x;r.front)
         yield x;
     r.popFront();
     foreach(rr;r){
         yield s;
         foreach(x;rr)
             yield x;
     }
}

auto cprod(R,S)(R r,S s){
     foreach(x;r)
         foreach(y;s)
             yield tuple(x,y);
}

One can get painfully close with basically no effort (DMD regressed on 
it though):
http://dpaste.dzfl.pl/baa538af


Ideally the compiler would automatically turn definitions similar to 
those above into auto return function templates that create instances of 
range types.

The issue is how to design it to make it useful for generic wrapper 
ranges that should forward the source range capabilities.
Jul 04 2013
next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Thursday, 4 July 2013 at 08:18:22 UTC, Timon Gehr wrote:

 It should be as simple as:

 auto map(alias a,R)(R r){
     foreach(x;r)
         yield a(x);
 }


... if all you care about is input ranges ...

I don't think there's any way to automatically infer and 
implement random access, bidirectionality etc. on ranges from an 
internal iteration definition.
Jul 04 2013
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 07/04/2013 11:49 AM, Peter Alexander wrote:

 On Thursday, 4 July 2013 at 08:18:22 UTC, Timon Gehr wrote:

 It should be as simple as:

 auto map(alias a,R)(R r){
     foreach(x;r)
         yield a(x);
 }


 ... if all you care about is input ranges ...

 I don't think there's any way to automatically infer and implement
 random access, bidirectionality etc. on ranges from an internal
 iteration definition.


There is no way that works in the general case, but it should be easy 
enough to infer from eg. the above implementation.
Jul 04 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/4/13 1:18 AM, Timon Gehr wrote:

 On 07/04/2013 07:04 AM, Andrei Alexandrescu wrote:

 Evidence we've done the right thing by emphasizing ranges instead of
 opApply.

 http://www.reddit.com/r/programming/comments/1hl2qr/rust_07_released/
 https://mail.mozilla.org/pipermail/rust-dev/2013-June/004599.html

 Andrei


 Well, probably, but implementing ranges is still too tedious.
 It is very likely that rust is going to fix that.


Let's see.


 It should be as simple as:

 auto map(alias a,R)(R r){
 foreach(x;r)
 yield a(x);
 }


Nonono. This gives you an input range. The current map() gives a range 
of the same category as the range passed. This is a major issue with 
yield. It does make it easy to implement input ranges, but I'm glad we 
did not build with it.

Andrei
Jul 04 2013
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 07/04/2013 03:42 PM, Andrei Alexandrescu wrote:

 On 7/4/13 1:18 AM, Timon Gehr wrote:

 On 07/04/2013 07:04 AM, Andrei Alexandrescu wrote:

 Evidence we've done the right thing by emphasizing ranges instead of
 opApply.

 http://www.reddit.com/r/programming/comments/1hl2qr/rust_07_released/
 https://mail.mozilla.org/pipermail/rust-dev/2013-June/004599.html

 Andrei


 Well, probably, but implementing ranges is still too tedious.
 It is very likely that rust is going to fix that.


 Let's see.


 It should be as simple as:

 auto map(alias a,R)(R r){
     foreach(x;r)
         yield a(x);
 }


 Nonono. This gives you an input range.


(Note: I was stating a requirement on simplicity.)

I haven't specified that it will give you an input range. If the 
programmer can figure out the length etc. the compiler will often be 
able to do so as well. Maybe it's too much magic to make yield just work 
though.

Another possibility is to implement a DSEL in a library, but all my 
experiments in this direction pretty much fail quite early because DMD 
does not know how to deal with moderately complex analysis dependencies 
(yet?), and has gotten a lot worse recently. I think this issue needs 
more attention. DMD makes it seem legitimate by spitting out 'forward 
reference errors' whenever its rather poor heuristic fails. Are there 
plans for fixing that? (I have ideas and a proof-of-concept 
implementation that will go open source soon. Incidentally it is 
currently locked to DMD 2.060 because of the aforementioned regressions.)


 The current map() gives a range of the same category as the range passed.


I'm pretty well aware of that. :o)


 This is a major issue with
 yield. It does make it easy to implement input ranges, but I'm glad we
 did not build with it.

 Andrei
Jul 04 2013
parent reply "w0rp" <devw0rp gmail.com> writes:
I see yield as a tool only for when you only want to create input 
ranges easily. There is a definite value in the other range 
types, but yield is useful for when you just want to produce an 
input range quickly.
Jul 04 2013
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, July 04, 2013 19:28:29 w0rp wrote:

 I see yield as a tool only for when you only want to create input
 ranges easily. There is a definite value in the other range
 types, but yield is useful for when you just want to produce an
 input range quickly.


And given how useless pure input ranges are, I really don't see much value in 
that. About all they give you is the ability to iterate over a set of values 
once. The other range types are _far_ more powerful, and pure input ranges 
should be avoided as much as possible IMHO.

- Jonathan M Davis
Jul 04 2013
next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Thursday, 4 July 2013 at 18:06:51 UTC, Jonathan M Davis wrote:

 On Thursday, July 04, 2013 19:28:29 w0rp wrote:

 I see yield as a tool only for when you only want to create 
 input
 ranges easily. There is a definite value in the other range
 types, but yield is useful for when you just want to produce an
 input range quickly.


 And given how useless pure input ranges are, I really don't see 
 much value in
 that. About all they give you is the ability to iterate over a 
 set of values
 once. The other range types are _far_ more powerful, and pure 
 input ranges
 should be avoided as much as possible IMHO.

 - Jonathan M Davis


To be fair, most of the time all you want to do is iterate over 
the range, so while they aren't powerful, they are sufficient 
most of the time.
Jul 04 2013
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Jul 04, 2013 at 08:23:01PM +0200, Peter Alexander wrote:

 On Thursday, 4 July 2013 at 18:06:51 UTC, Jonathan M Davis wrote:

On Thursday, July 04, 2013 19:28:29 w0rp wrote:

I see yield as a tool only for when you only want to create input
ranges easily. There is a definite value in the other range types,
but yield is useful for when you just want to produce an input range
quickly.


And given how useless pure input ranges are, I really don't see much
value in that. About all they give you is the ability to iterate over
a set of values once. The other range types are _far_ more powerful,
and pure input ranges should be avoided as much as possible IMHO.




[...]

I disagree. Most of the time you only want to iterate over a set of
values once, and input ranges are perfectly suited for that. I'm a
stickler for requiring the minimum to be functional -- if a function
only needs to iterate the range once, then it should only require an
input range, nothing more.



 To be fair, most of the time all you want to do is iterate over the
 range, so while they aren't powerful, they are sufficient most of the
 time.


+1. That's not to say other range types aren't useful; they are very
useful (and necessary) in certain contexts. But more often than not,
what I do with a range requires nothing more than an input range.


T

-- 
It's bad luck to be superstitious. -- YHL
Jul 04 2013
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, July 04, 2013 20:23:01 Peter Alexander wrote:

 To be fair, most of the time all you want to do is iterate over
 the range, so while they aren't powerful, they are sufficient
 most of the time.


ll pure input ranges are really good for is simple iteration, because it's 
_frequently_ the case you need at least a forward range in order to do much in 
the way of algorithms with ranges, so unless you're just not using 
std.algorithm and its ilk much, I don't see how you could possibly think that 
pure input ranges weren't anything but annoying. There's just so limiting in 
comparison to every other range type that I think that they should be avoided 
as much as possible.

Sometimes, you're stuck, because the nature of the type that you're dealing 
with forces it to be a pure input range, but you just can't take advantage of 
many algorithms with pure input ranges, which means that you have to write a 
lot more code or use std.array.array in order to use the various algorithms, 
forcing you to allocate when it should be completely unnecessary.

If all you're doing with ranges is iteration, then you're under-utilizing them 
IMHO.

- Jonathan m Davis
Jul 04 2013
parent reply "w0rp" <devw0rp gmail.com> writes:
On Thursday, 4 July 2013 at 19:26:43 UTC, Jonathan M Davis wrote:

 Sometimes, you're stuck, because the nature of the type that 
 you're dealing
 with forces it to be a pure input range, but you just can't 
 take advantage of
 many algorithms with pure input ranges, which means that you 
 have to write a
 lot more code or use std.array.array in order to use the 
 various algorithms,
 forcing you to allocate when it should be completely 
 unnecessary.


That is exactly why yield is useful, because without yield, you 
have two options.

1. Write a lot of code to create an InputRange. (Cost in time 
taken to write it.)
2. Allocate and lose on performance. (Cost in runtime 
performance.)

Yield gives you option 3.

3. Write very little code while also saving on performance.
Jul 04 2013
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, July 04, 2013 21:40:23 w0rp wrote:

 On Thursday, 4 July 2013 at 19:26:43 UTC, Jonathan M Davis wrote:

 Sometimes, you're stuck, because the nature of the type that
 you're dealing
 with forces it to be a pure input range, but you just can't
 take advantage of
 many algorithms with pure input ranges, which means that you
 have to write a
 lot more code or use std.array.array in order to use the
 various algorithms,
 forcing you to allocate when it should be completely
 unnecessary.


 
 That is exactly why yield is useful, because without yield, you
 have two options.
 
 1. Write a lot of code to create an InputRange. (Cost in time
 taken to write it.)
 2. Allocate and lose on performance. (Cost in runtime
 performance.)
 
 Yield gives you option 3.
 
 3. Write very little code while also saving on performance.


Except that in most cases, you should have been writing a range type with more 
capabilites than an input range. IMHO, something like yield would pretty much 
only be of value in situations where you just need to iterate over something 
(so you're not taking advantage of much in the way of algorithms) and where 
you need a range type specific to your program which will never be reused 
anywhere. And that implies that you're not writing very reusable code. 
Sometimes, that's the way things go, but ranges and algorithms are such that 
most of the time, you should be able to write range-based functions which are 
reusable. And if you're doing that, you should be writing ranges with the full 
set of capabilites that they can have, not just input ranges.

- Jonathan M Davis
Jul 04 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/4/13 12:40 PM, w0rp wrote:

 On Thursday, 4 July 2013 at 19:26:43 UTC, Jonathan M Davis wrote:

 Sometimes, you're stuck, because the nature of the type that you're
 dealing
 with forces it to be a pure input range, but you just can't take
 advantage of
 many algorithms with pure input ranges, which means that you have to
 write a
 lot more code or use std.array.array in order to use the various
 algorithms,
 forcing you to allocate when it should be completely unnecessary.


 That is exactly why yield is useful, because without yield, you have two
 options.

 1. Write a lot of code to create an InputRange. (Cost in time taken to
 write it.)
 2. Allocate and lose on performance. (Cost in runtime performance.)

 Yield gives you option 3.

 3. Write very little code while also saving on performance.


That would be a win if input ranges are very frequent. One possibility 
to assess that would be to figure how many algorithms in std.algorithm 
work with input ranges, how many generators in std.range create input 
ranges, and then assess the potential code savings. A consideration is 
also the cost of adding yield to the language (somehow this often gets 
neglected in the excitement of adding stuff).


Andrei
Jul 04 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:


 That would be a win if input ranges are very frequent.


As I have explained in one of my recent answers in this thread in 
Python "input ranges" are used all the time.

So in your analysis you should also hypothesize how frequent 
input ranges are going to appear in D if you offer a handy and 
compact built-in syntax to create them.



 A consideration is also the cost of adding yield to the 
 language (somehow this often gets neglected in the excitement 
 of adding stuff).



point to assess how much complexity causes this addition.

Bye,
bearophile
Jul 04 2013
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday, July 04, 2013 11:37:15 H. S. Teoh wrote:

 if a function
 only needs to iterate the range once, then it should only require an
 input range, nothing more.


Agreed, but it's freuently the case that an input range isn't enough, and even 
if it is for a particular function, odds are than the result of that function 
is going to need to be fed to another function which _does_ require more than 
an input range. And far too often, it's the case that people think that an 
input range is enough when in fact a forward range is required, but the 
implicit save that many ranges do makes it so that the function works without 
calling save much of the time, even though it really does need to save.

Whenever I have to deal with pure input ranges, I find it to be extremely 
annoying. The simple fact that you can't even save its state is just way too 
limiting for a lot of algorithms to be able to be implemented in any kind of 
sane way, if at all, and too much of Phobos becomes unavailable either because 
what it's trying to do just can't be done with an input range or because it 
would consume the range when you can't afford for it to be consumed.

- Jonathan M Davis
Jul 04 2013
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


 And given how useless pure input ranges are, I really don't see 
 much value in
 that. About all they give you is the ability to iterate over a 
 set of values
 once. The other range types are _far_ more powerful, and pure 
 input ranges
 should be avoided as much as possible IMHO.


Python generators are essentially input ranges, you can go only 
forward, and they yield their results only once:



 g = (i ** 2 for i in xrange(5))
 list(g)






[0, 1, 4, 9, 16]

 list(g)






[]

 def gen():






...     for i in xrange(5):
...         yield i * i
...

 g = gen()
 list(g)






[0, 1, 4, 9, 16]

 list(g)






[]


Yet in Python they are used everywhere. I define input ranges 
often in D and I think they are useful.

Having a built-in "yield" in a language is quite handy. Take a 
look at the Python and the second D solutions here:
http://rosettacode.org/wiki/Same_Fringe

Bye,
bearophile
Jul 04 2013
next sibling parent Russel Winder <russel winder.org.uk> writes:
On Thu, 2013-07-04 at 20:27 +0200, bearophile wrote:
[=E2=80=A6]

 Yet in Python they are used everywhere. I define input ranges=20
 often in D and I think they are useful.
=20
 Having a built-in "yield" in a language is quite handy. Take a=20
 look at the Python and the second D solutions here:
 http://rosettacode.org/wiki/Same_Fringe


cf. Scala which has for comprehensions and a yield. It is used a lot.

Assuming yield means the same thing in all these emails!
--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
Jul 05 2013
prev sibling parent Artur Skawina <art.08.09 gmail.com> writes:
On 07/04/13 20:27, bearophile wrote:

 Having a built-in "yield" in a language is quite handy. Take a look at the
Python and the second D solutions here:
 http://rosettacode.org/wiki/Same_Fringe


Would tuples really be the ideal tree representation when dealing
with mutable data in /real/ code?

Anyway, let's see... Right now, D will let you do this:

   struct Fringe(T) {
      struct State { T* root; HeapRange!Fringe subtree; };
      mixin GeneratorT!(State, q{
            if (root.l) 
               for (subtree = Fringe(root.l); !subtree.empty;
subtree.popFront() )
                  yield subtree.front;
            if (root.isLeaf())
               yield root.v;
            if (root.r)
               for (subtree = Fringe(root.r); !subtree.empty;
subtree.popFront() )
                  yield subtree.front;
         }, typeof(T.v));
   }
   Fringe!TREE fringe(TREE)(TREE* tree) { return Fringe!TREE(tree); }

   auto sameFringe(R1, R2)(R1 r1, R2 r2) {
      import std.algorithm : equal; return equal(fringe(r1), fringe(r2));
   }

   void fringetest() {
      auto t1 = tree(tree(tree(1), 2, tree(3)), 4, tree(tree(5), 6, tree(7)));
      auto t2 = tree(tree(tree(1), 8, tree(3)), 9, tree(tree(5), 0, tree(7)));
      auto t3 = tree(tree(tree(1), 2, tree(3)), 4, tree(tree(5), 6, tree(8)));
      auto t4 = tree(tree(tree(1), 2, tree(3)), 4, tree(tree(5), 6, tree(null,
8, tree(7))));
      
      assert(sameFringe(t1, t2));
      assert(!sameFringe(t1, t3));
      assert(sameFringe(t1, t4));
   }

It really can't be made much simpler, it's just a few extra characters
of boilerplate. Modulo certain other language issues, like no IFTI on
constructors, and an imperfect compiler (the explicit "typeof(T.v)" is
only required to work around forward ref errors)

The problem with encouraging this style is that people will use this approach,
and then not expose the other range properties. It will result in less 
efficient code, which is harder and more bug-prone to improve (because the
internal state has to be handled too).

Having input ranges be as simple to define as:

   auto iota(T)(T start, T end) {
      struct State { T start, end, i; }
      return Generator!(State, q{
                           for (i=start; i<end; ++i)
                              yield state.i;
                        })
                        (start, end);
   }

   auto map(alias F, R)(R r) {
      struct State { R r; alias F MF; }
      return Generator!(State, q{
                           for(; !r.empty; r.popFront())
                              yield MF(r.front);
                        })
                        (r);
   }

is nice, but has downsides. A DSL like this one is probably enough,
there's not that much to gain from adding "yield" to the core language. [1]

artur

[1] A bit compiler support would make it /safer/, though; right now it's
    too easy to lose part of the state. But having implicit allocations
    (closure-like) wouldn't be a good solution; better diagnostics might
    be enough.
Jul 05 2013
prev sibling parent "w0rp" <devw0rp gmail.com> writes:
On Thursday, 4 July 2013 at 18:06:51 UTC, Jonathan M Davis wrote:

 On Thursday, July 04, 2013 19:28:29 w0rp wrote:

 I see yield as a tool only for when you only want to create 
 input
 ranges easily. There is a definite value in the other range
 types, but yield is useful for when you just want to produce an
 input range quickly.


 And given how useless pure input ranges are, I really don't see 
 much value in
 that. About all they give you is the ability to iterate over a 
 set of values
 once. The other range types are _far_ more powerful, and pure 
 input ranges
 should be avoided as much as possible IMHO.

 - Jonathan M Davis


InputRanges aren't useless, that's just wrong. When chaining 
ranges together, you are locked to the most limited range 
available. If you use network IO, database access, and many other 
comment tasks, you are left with InputRanges.

While the other range types are certainly more powerful, and a 
definite path to take when implementing libraries, like 
std.algorithm, sometimes you just don't need all of that power. 
Yield is much simpler, and when that's all you need, why 
complicate matters?
Jul 04 2013
prev sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Thursday, 4 July 2013 at 05:04:59 UTC, Andrei Alexandrescu 
wrote:

 Evidence we've done the right thing by emphasizing ranges 
 instead of opApply.


One downside is with opApply, you have a little more control over 
escaping references. Suppose you take a range to view a 
container, then .save it somewhere and keep that copy. Then when 
the container dies, your range points at invalid memory.

The Rust people must have solved that though. Probably not so 
hard there since their compiler has a borrow check, whereas in D 
I was trying to do it with library hacks...
Jul 04 2013