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:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 external. cf. C++, Go, D, Rust, Haskell, OCaml, F#, etc. 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
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
 external. cf. C++, Go, D, Rust, Haskell, OCaml, F#, etc.

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 "w0rp" <devw0rp gmail.com> writes:
 In the future, Rust can have generators using a `yield` 
 statement like C#,
  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
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 next 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
next sibling 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
parent 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
prev sibling next sibling parent "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
prev sibling next sibling parent "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)



 list(g)



 def gen():



... yield i * i ...
 g = gen()
 list(g)



 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
prev sibling next 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 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 parent Russel Winder <russel winder.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 "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
prev sibling next sibling parent "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, Haskel and F# development, as well as, introducing FP to the enterprise via LINQ.
 Native still seems to be in the 1990s OO vs. functional war: 
 internal OR
 external. cf. C++, Go, D, Rust, Haskell, OCaml, F#, etc.

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
prev sibling next sibling parent Russel Winder <russel winder.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=

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.

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,
 Haskel and F# development, as well as, introducing FP to the
 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 next sibling 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 "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
prev sibling next sibling parent 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
prev sibling next 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 "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
prev sibling 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 next sibling 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).

Of course. C#, its history and coding probably is a starting point to assess how much complexity causes this addition. Bye, bearophile
Jul 04 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