www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - ch-ch-changes

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I've worked valiantly on defining the range infrastructure and making 
std.algorithm work with it. I have to say that I'm even more pleased 
with the result than I'd ever expected when I started. Ranges and 
concepts really make for beautiful code, and I am sure pretty darn 
efficient too.

There's a lot to sink one's teeth in, but unfortunately the code hinges 
on a compiler fix that Walter was kind enough to send me privately. I 
did document the work, but the documentation doesn't really make justice 
to the extraordinary possibilities that lay ahead of us. Anyhow, here's 
a sneak preview into the up-and-coming ranges and their algorithms.

http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

Ranges are easy to define and compose efficiently. It was, however, a 
pig to get a zip(r1, r2, ...) working that can mutate back the ranges it 
iterates on. With that, it's very easy to e.g. sort multiple arrays in 
parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. random 
iteration if all components offer it, which means that you can do crazy 
things like sorting data that sits partially in one array and partially 
in another.

Singly-linked list ranges are in, and to my soothing I found an answer 
to the container/range dichotomy in the form of a topology policy. A 
range may or may not be able to modify the topology of the data it's 
iterating over; if it can, it's a free-standing range, much like 
built-in arrays are. If it can't, it's a limited range tied to a 
container (of which I defined none so far, but give me time) and it's 
only the container that can mess with the topology in controlled ways. 
More on that later.

Feedback welcome.


Andrei
Jan 27 2009
next sibling parent reply Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Tue, Jan 27, 2009 at 11:15 PM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:
 I've worked valiantly on defining the range infrastructure and making
 std.algorithm work with it. I have to say that I'm even more pleased with
 the result than I'd ever expected when I started. Ranges and concepts really
 make for beautiful code, and I am sure pretty darn efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code hinges on a
 compiler fix that Walter was kind enough to send me privately. I did
 document the work, but the documentation doesn't really make justice to the
 extraordinary possibilities that lay ahead of us. Anyhow, here's a sneak
 preview into the up-and-coming ranges and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

 Ranges are easy to define and compose efficiently. It was, however, a pig to
 get a zip(r1, r2, ...) working that can mutate back the ranges it iterates
 on. With that, it's very easy to e.g. sort multiple arrays in parallel.
 Similarly, chain(r1, r2, ...) is able to offer e.g. random iteration if all
 components offer it, which means that you can do crazy things like sorting
 data that sits partially in one array and partially in another.

 Singly-linked list ranges are in, and to my soothing I found an answer to
 the container/range dichotomy in the form of a topology policy. A range may
 or may not be able to modify the topology of the data it's iterating over;
 if it can, it's a free-standing range, much like built-in arrays are. If it
 can't, it's a limited range tied to a container (of which I defined none so
 far, but give me time) and it's only the container that can mess with the
 topology in controlled ways. More on that later.

 Feedback welcome.

This is some awesome stuff. std.range and std.algorithm are really coming together into a compelling whole. I don't know what else to say - _you_ seem to know what you're doing! It's a minor point, but in the docs, with all the templating madness it gets very hard to find the name of the symbol actually being documented. For example: Filter!(unaryFun!(pred),Chain!(Ranges)) filter(alias pred, Ranges...)(Ranges rs); "filter" gets lost in the middle. Could it be highlighted, or moved to the front (using a Pascal-like "func(params) : returntype" syntax instead)? Also - "toe" is still a stupid name. ;) "first" and "last" would have been my first choices, they seem so obvious.
Jan 27 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Jarrett Billingsley wrote:
 On Tue, Jan 27, 2009 at 11:15 PM, Andrei Alexandrescu

 Feedback welcome.

This is some awesome stuff. std.range and std.algorithm are really coming together into a compelling whole. I don't know what else to say - _you_ seem to know what you're doing! It's a minor point, but in the docs, with all the templating madness it gets very hard to find the name of the symbol actually being documented. For example: Filter!(unaryFun!(pred),Chain!(Ranges)) filter(alias pred, Ranges...)(Ranges rs); "filter" gets lost in the middle. Could it be highlighted, or moved to the front (using a Pascal-like "func(params) : returntype" syntax instead)?

Good point. Actually I've been experimenting with using "auto" for the return type. That does work most of the time, but unfortunately ddoc doesn't understand it. Then,
 Also - "toe" is still a stupid name.  ;)  "first" and "last" would
 have been my first choices, they seem so obvious.

Turns out toe isn't half bad when I was coding with it - all I needed was something short and memorable. One problem with "first" is that it sometimes suggests something else. For example, if I have a generator for the numbers 1 to 10 and have advanced it a bit, gen.first suggests I'm looking back to the very first element, not the state of the iteration. I agree that gen.head isn't terribly evocative either, but then at least it doesn't evoke something wrong :o). Anyhow, how about doing what Haskell does? They use "head" and "last". And at least we'd be able to blame *them* if anyone doesn't like the names :o). Thoughts? Andrei
Jan 27 2009
next sibling parent Yigal Chripun <yigal100 gmail.com> writes:
Andrei Alexandrescu wrote:
 Jarrett Billingsley wrote:
 On Tue, Jan 27, 2009 at 11:15 PM, Andrei Alexandrescu

 Feedback welcome.

This is some awesome stuff. std.range and std.algorithm are really coming together into a compelling whole. I don't know what else to say - _you_ seem to know what you're doing! It's a minor point, but in the docs, with all the templating madness it gets very hard to find the name of the symbol actually being documented. For example: Filter!(unaryFun!(pred),Chain!(Ranges)) filter(alias pred, Ranges...)(Ranges rs); "filter" gets lost in the middle. Could it be highlighted, or moved to the front (using a Pascal-like "func(params) : returntype" syntax instead)?

Good point. Actually I've been experimenting with using "auto" for the return type. That does work most of the time, but unfortunately ddoc doesn't understand it. Then,
 Also - "toe" is still a stupid name. ;) "first" and "last" would
 have been my first choices, they seem so obvious.

Turns out toe isn't half bad when I was coding with it - all I needed was something short and memorable. One problem with "first" is that it sometimes suggests something else. For example, if I have a generator for the numbers 1 to 10 and have advanced it a bit, gen.first suggests I'm looking back to the very first element, not the state of the iteration. I agree that gen.head isn't terribly evocative either, but then at least it doesn't evoke something wrong :o). Anyhow, how about doing what Haskell does? They use "head" and "last". And at least we'd be able to blame *them* if anyone doesn't like the names :o). Thoughts? Andrei

in that case, maybe have "current" and "last"? also, I don't like the "empty" because it's a negative test and I'm a positive person :) I prefer something like Tango's "more" or Java's longer "hasNext".
Jan 27 2009
prev sibling next sibling parent Daniel Keep <daniel.keep.lists gmail.com> writes:
Bill Baxter wrote:
 [snip]
 
 Well Haskell has a commonly used "tail", so it has an excuse for not
 making head/last match up.
 
 
 There's the C++-ish names:  front/back   Anything wrong with those?
 
 --bb

"back" sounds like an action. -- Daniel
Jan 27 2009
prev sibling next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:gloppm$1vog$1 digitalmars.com...
 Jarrett Billingsley wrote:
 On Tue, Jan 27, 2009 at 11:15 PM, Andrei Alexandrescu

 Feedback welcome.

This is some awesome stuff. std.range and std.algorithm are really coming together into a compelling whole. I don't know what else to say - _you_ seem to know what you're doing! It's a minor point, but in the docs, with all the templating madness it gets very hard to find the name of the symbol actually being documented. For example: Filter!(unaryFun!(pred),Chain!(Ranges)) filter(alias pred, Ranges...)(Ranges rs); "filter" gets lost in the middle. Could it be highlighted, or moved to the front (using a Pascal-like "func(params) : returntype" syntax instead)?

Good point. Actually I've been experimenting with using "auto" for the return type. That does work most of the time, but unfortunately ddoc doesn't understand it. Then,
 Also - "toe" is still a stupid name.  ;)  "first" and "last" would
 have been my first choices, they seem so obvious.

Turns out toe isn't half bad when I was coding with it - all I needed was something short and memorable. One problem with "first" is that it sometimes suggests something else. For example, if I have a generator for the numbers 1 to 10 and have advanced it a bit, gen.first suggests I'm looking back to the very first element, not the state of the iteration. I agree that gen.head isn't terribly evocative either, but then at least it doesn't evoke something wrong :o). Anyhow, how about doing what Haskell does? They use "head" and "last". And at least we'd be able to blame *them* if anyone doesn't like the names :o). Thoughts? Andrei

Isn't "tail" the standard counterpart to "head"? ("toe" just doesn't sound good)
Jan 28 2009
next sibling parent Don <nospam nospam.com> writes:
Denis Koroskin wrote:
 On Wed, 28 Jan 2009 12:07:16 +0300, Nick Sabalausky <a a.a> wrote:
 
 "Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message
 news:gloppm$1vog$1 digitalmars.com...
 Jarrett Billingsley wrote:
 On Tue, Jan 27, 2009 at 11:15 PM, Andrei Alexandrescu

 Feedback welcome.

This is some awesome stuff. std.range and std.algorithm are really coming together into a compelling whole. I don't know what else to say - _you_ seem to know what you're doing! It's a minor point, but in the docs, with all the templating madness it gets very hard to find the name of the symbol actually being documented. For example: Filter!(unaryFun!(pred),Chain!(Ranges)) filter(alias pred, Ranges...)(Ranges rs); "filter" gets lost in the middle. Could it be highlighted, or moved to the front (using a Pascal-like "func(params) : returntype" syntax instead)?

Good point. Actually I've been experimenting with using "auto" for the return type. That does work most of the time, but unfortunately ddoc doesn't understand it. Then,
 Also - "toe" is still a stupid name.  ;)  "first" and "last" would
 have been my first choices, they seem so obvious.

Turns out toe isn't half bad when I was coding with it - all I needed was something short and memorable. One problem with "first" is that it sometimes suggests something else. For example, if I have a generator for the numbers 1 to 10 and have advanced it a bit, gen.first suggests I'm looking back to the very first element, not the state of the iteration. I agree that gen.head isn't terribly evocative either, but then at least it doesn't evoke something wrong :o). Anyhow, how about doing what Haskell does? They use "head" and "last". And at least we'd be able to blame *them* if anyone doesn't like the names :o). Thoughts? Andrei

Isn't "tail" the standard counterpart to "head"? ("toe" just doesn't sound good)

Tail is often used to denote anything but head (imagine snake).

It's those Lisp programmers. It's a bit deranged, I reckon. I'm going to call them tadpoles from now on.
Jan 28 2009
prev sibling next sibling parent "Nick Sabalausky" <a a.a> writes:
"Bill Baxter" <wbaxter gmail.com> wrote in message 
news:mailman.530.1233135120.22690.digitalmars-d puremagic.com...
 On Wed, Jan 28, 2009 at 6:07 PM, Nick Sabalausky <a a.a> wrote:

 Isn't "tail" the standard counterpart to "head"? ("toe" just doesn't 
 sound
 good)

Tail has a history of being used to mean "everything but head" in functional programming languages like Haskel and ML. So of back, last, end, tail, rear, foot, toe, it seems every one has some strike against it. back - could be mistaken for an action last - doesn't pair well with "head", and "first" sounds too much like item #1 overall end - in C++ usually means "one past the end" tail - in FP langs means "everything but head" rear - makes Walter thing unhappy thoughts toe - sounds silly, doesn't make so much sense for a range that represents a tree structure. Toe is sounding pretty ok. Actually I think the critique that it doesn't make sense for a non-linear range should be thrown out. Linearizing is the whole purpose of a range. So even if it wasn't linear before, a range effective is providing a linearized view of it. So that leaves "it sounds silly", which is a pretty weak subjective argument against. --bb

How about "it sounds really, really silly"? ;)
Jan 28 2009
prev sibling next sibling parent Chad J <gamerchad __spam.is.bad__gmail.com> writes:
Bill Baxter wrote:
 On Wed, Jan 28, 2009 at 6:07 PM, Nick Sabalausky <a a.a> wrote:
 
 Isn't "tail" the standard counterpart to "head"? ("toe" just doesn't sound
 good)

Tail has a history of being used to mean "everything but head" in functional programming languages like Haskel and ML. So of back, last, end, tail, rear, foot, toe, it seems every one has some strike against it. back - could be mistaken for an action last - doesn't pair well with "head", and "first" sounds too much like item #1 overall end - in C++ usually means "one past the end" tail - in FP langs means "everything but head" rear - makes Walter thing unhappy thoughts toe - sounds silly, doesn't make so much sense for a range that represents a tree structure. Toe is sounding pretty ok. Actually I think the critique that it doesn't make sense for a non-linear range should be thrown out. Linearizing is the whole purpose of a range. So even if it wasn't linear before, a range effective is providing a linearized view of it. So that leaves "it sounds silly", which is a pretty weak subjective argument against. --bb

The parts totally need to be barrel, stock, and butt! ... Anyhow, aft (opposed to fore) terminal/terminus stern (opposed to bow) cathode (opposed to anode) Have these been mentioned or dismissed? With something like "toe" on the table, nautical and electrical analogies don't seem so far fetched anymore. I think the reason why a lot of us are uncomfortable with "toe" is because it takes even a little bit of thinking to understand its relation to "head;" at that point we'd be better off calling it a "foot." This kind of analogy shouldn't require thought to understand (guess this makes cathode sort of inadequate)-- that is, it has to be intuitive, brief, and (ideally) catchy. - Chad
Jan 28 2009
prev sibling parent reply Yigal Chripun <yigal100 gmail.com> writes:
Bill Baxter wrote:
 On Wed, Jan 28, 2009 at 6:07 PM, Nick Sabalausky<a a.a>  wrote:

 Isn't "tail" the standard counterpart to "head"? ("toe" just doesn't sound
 good)

Tail has a history of being used to mean "everything but head" in functional programming languages like Haskel and ML. So of back, last, end, tail, rear, foot, toe, it seems every one has some strike against it. back - could be mistaken for an action last - doesn't pair well with "head", and "first" sounds too much like item #1 overall end - in C++ usually means "one past the end" tail - in FP langs means "everything but head" rear - makes Walter thing unhappy thoughts toe - sounds silly, doesn't make so much sense for a range that represents a tree structure. Toe is sounding pretty ok. Actually I think the critique that it doesn't make sense for a non-linear range should be thrown out. Linearizing is the whole purpose of a range. So even if it wasn't linear before, a range effective is providing a linearized view of it. So that leaves "it sounds silly", which is a pretty weak subjective argument against. --bb

I disagree with the above reasoning. "Language X has different meaning for word Y" is not a valid argument IMO. One of D's stated goals is to break backward compatability when needed in order to get a better language design, yet we constantly keep getting back to " but in C++ ...". if people want to use a backward compatible language they already have C++ for that, and they don't need D. I for one, prefer to change when the change makes sense and brings more clarity. Yes, it'll be initially confusing for former C++ programmers, but IMO it's worth it in the long run. head/toe is not just silly, it's also non intuitive for non-English speakers. (I'd be confused by this, had i seen this for the first time) When I write D code I think in D, not any other language and I'm sure that applies to most people. making the switch to "D mode" is easier IMO than trying to remember confusing terms, just because some other language has slightly different meaning for the deafult terms. Hack, I don't even know haskel, why should I care about haskell's definitions? I already asked in a previous post - would a chinese programmer intuitivly think that toe is the last item in a range?
Jan 28 2009
next sibling parent Derek Parnell <derek psych.ward> writes:
On Wed, 28 Jan 2009 22:31:04 +0200, Yigal Chripun wrote:

 I already asked in a previous post - would a chinese programmer 
 intuitivly think that toe is the last item in a range?

I am a native English speaker (well ... Australian okay) and I do not think intuitively of 'toe' as the last item in a range. It seems really, really odd; rather contrived actually. I think intutive words for the first and last items in a range would be 'first' and 'last'. -- Derek Parnell Melbourne, Australia skype: derek.j.parnell
Jan 28 2009
prev sibling next sibling parent Yigal Chripun <yigal100 gmail.com> writes:
Bill Baxter wrote:
 On Thu, Jan 29, 2009 at 5:31 AM, Yigal Chripun<yigal100 gmail.com>  wrote:
 Bill Baxter wrote:
 On Wed, Jan 28, 2009 at 6:07 PM, Nick Sabalausky<a a.a>   wrote:

 Isn't "tail" the standard counterpart to "head"? ("toe" just doesn't
 sound
 good)

functional programming languages like Haskel and ML. So of back, last, end, tail, rear, foot, toe, it seems every one has some strike against it. back - could be mistaken for an action last - doesn't pair well with "head", and "first" sounds too much like item #1 overall end - in C++ usually means "one past the end" tail - in FP langs means "everything but head" rear - makes Walter thing unhappy thoughts toe - sounds silly, doesn't make so much sense for a range that represents a tree structure. Toe is sounding pretty ok. Actually I think the critique that it doesn't make sense for a non-linear range should be thrown out. Linearizing is the whole purpose of a range. So even if it wasn't linear before, a range effective is providing a linearized view of it. So that leaves "it sounds silly", which is a pretty weak subjective argument against. --bb

word Y" is not a valid argument IMO. One of D's stated goals is to break backward compatability when needed in order to get a better language design, yet we constantly keep getting back to " but in C++ ...". if people want to use a backward compatible language they already have C++ for that, and they don't need D. I for one, prefer to change when the change makes sense and brings more clarity. Yes, it'll be initially confusing for former C++ programmers, but IMO it's worth it in the long run. head/toe is not just silly, it's also non intuitive for non-English speakers. (I'd be confused by this, had i seen this for the first time) When I write D code I think in D, not any other language and I'm sure that applies to most people. making the switch to "D mode" is easier IMO than trying to remember confusing terms, just because some other language has slightly different meaning for the deafult terms. Hack, I don't even know haskel, why should I care about haskell's definitions?

If you port code from C++ or Haskell to D it will become an issue. I ported a largeish C++ library with lots of iterators and it was only natural to use the same terminology as C++ there (begin/end). If D co-opted those terms I'm not sure what I'd call the ported C++ ones to differentiate, and it would just end up being confusing to both D and C++ users. I think making it easy to port C++ code is a good goal. Not so sure about Haskell, though. D may never be functional enough for porting Haskell to make much sense.
 I already asked in a previous post - would a chinese programmer intuitivly
 think that toe is the last item in a range?

Does it really matter if it's used everywhere and consistently throughout D? It's like saying "char" is unintuitive. Yeh, it is unintuitive, but once you know it's short for "character" it's easy to remember. Surely a Chinese programmer once he learns toe is the last item will have no problem remembering what it means, given the relationship between head and toe on a person's body. --bb

I guess you completely missed my point. If we are choosing terms that are going to be used everywhere and consistently throughout D, we should pick the intuitive words for the first and last items in a range - 'first' and 'last'. to rephrase what you've said: Surely a C++ programmer once he learns 'last' is the last item in a D range (simple, isn't it?) will have no problem remembering what it means. in other words - if a Chinese programmer can learn an unintuitive term so can a C++ programmer. the only difference is that with the former option we all get stuck with a bad name for good, while with the latter it's only a temporary inconvenience since [hopefully] the C++ programmer will become a D programmer. as already pointed by others [read Chad's reply] - there is no relationship between head and toe on a person's body, and you might as well use 'foot'. regarding porting code - while I agree that this can help, porting code is a minor and secondary objective. both C code and a subset of C++ (in D2) can be directly linked with D code, so porting isn't that important and isn't the main goal of the language. besides, your argument would apply to most other C-family languages - there's a lot of Java code ported to D, for example, so maybe we should prefer Java's semantics over the C++ ones? or maybe C#'s or javascript, or ..?
Jan 28 2009
prev sibling parent reply Sandeep Kakarlapudi <sandeep.iitkgpspammenot gmail.com> writes:
Bill Baxter Wrote:

 Does it really matter if it's used everywhere and consistently
 throughout D?  It's like saying "char" is unintuitive.  Yeh, it is
 unintuitive, but once you know it's short for "character" it's easy to
 remember.  Surely a Chinese programmer once he learns toe is the last
 item will have no problem remembering what it means, given the
 relationship between head and toe on a person's body.
 
 --bb

"toe" is flat out silly and such names that pollute everything. If one doesn't get the proper unambigious name for something atleast invent a new one, do not borrow it and flat out confuse a newbie coming to the language or make decisions like this that everyone is going to be stuck with! There are 10 toes for every head! Other mistakes that still irritate quite a few: C++ vector vs a mathematical vector In real time computer graphics, using binormal inplace of the bitangent. Curves have a binormal and surfaces have bitangents! No matter how many times binormal is used it still is wrong and sounds counter intiutive! Perhaps Stackoverflow and reddit might give a representative feedback on what a large section of programmers think and whatever their preference might be it could be give some weight in case a new term is not being coined.
Jan 28 2009
next sibling parent reply Chad J <gamerchad __spam.is.bad__gmail.com> writes:
Sandeep Kakarlapudi wrote:
 Other mistakes that still irritate quite a few:
 C++ vector vs a mathematical vector
 In real time computer graphics, using binormal inplace of the bitangent.
Curves have a binormal and surfaces have bitangents! 
 No matter how many times binormal is used it still is wrong and sounds counter
intiutive! 

I don't know if those are right or not, but curves having binormals and surfaces having bitangents seems inconsistent with other mathematical terminology, since curves tend to have tangents and surfaces tend to have normals.
Jan 28 2009
parent Chad J <gamerchad __spam.is.bad__gmail.com> writes:
Bill Baxter wrote:
 On Thu, Jan 29, 2009 at 9:44 AM, Chad J
 <gamerchad __spam.is.bad__gmail.com> wrote:
 Sandeep Kakarlapudi wrote:
 Other mistakes that still irritate quite a few:
 C++ vector vs a mathematical vector
 In real time computer graphics, using binormal inplace of the bitangent.
Curves have a binormal and surfaces have bitangents!
 No matter how many times binormal is used it still is wrong and sounds counter
intiutive!

surfaces having bitangents seems inconsistent with other mathematical terminology, since curves tend to have tangents and surfaces tend to have normals.

The classic "Frenet frame" used to describe differential properties of spatial curves include a tangent, normal, and binormal. Note that with a curve in 3-space there are two independent directions which are normal to the curve. With a surface in 3D this is not the case. There are two independent directions which are tangent to the surface (which you could call tangent and bi-tangent), and a single normal. I have O'Neill's book on differential geometry, and while it mentions binormals of curves, it says nothing about binormals or bitangents for surfaces. So I think the problem is there was just a terminology vacuum that the graphics guys needed filled, and they filled it in a somewhat illogical way. --bb

Ah, thanks for the explanation!
Jan 28 2009
prev sibling next sibling parent Sandeep Kakarlapudi <sandeep.iitkgpspammenot gmail.com> writes:
Bill Baxter Wrote:

 On Thu, Jan 29, 2009 at 9:32 AM, Sandeep Kakarlapudi
 <sandeep.iitkgpspammenot gmail.com> wrote:
 "toe" is flat out silly and such names that pollute everything.

Just curious -- do you find "head" and "tail" to be silly too? If not, what is it that makes them not silly? Is there anything more to it than just being used to them?

No, I don't find them silly, because head-tail is very common not just in common english use but also in programming although there might be some ambiguity. If I use toe (or anything else for that matter) for some time I'm sure I will get used to it. Moreover to me both expressions "head to toe" and "head to tail" mean the same. But when thinking about getting an element tail feels better than toe. Getting the toe element somehow does not compile in my head :/ Even better might be rhead or simply first-last!
Jan 28 2009
prev sibling parent Don <nospam nospam.com> writes:
Sandeep Kakarlapudi wrote:
 Bill Baxter Wrote:
 
 Does it really matter if it's used everywhere and consistently
 throughout D?  It's like saying "char" is unintuitive.  Yeh, it is
 unintuitive, but once you know it's short for "character" it's easy to
 remember.  Surely a Chinese programmer once he learns toe is the last
 item will have no problem remembering what it means, given the
 relationship between head and toe on a person's body.

 --bb

"toe" is flat out silly and such names that pollute everything. If one doesn't get the proper unambigious name for something atleast invent a new one, do not borrow it and flat out confuse a newbie coming to the language or make decisions like this that everyone is going to be stuck with! There are 10 toes for every head! Other mistakes that still irritate quite a few: C++ vector vs a mathematical vector

Someone should have been shot for that.
 In real time computer graphics, using binormal inplace of the bitangent.
Curves have a binormal and surfaces have bitangents! 
 No matter how many times binormal is used it still is wrong and sounds counter
intiutive! 
 
 Perhaps Stackoverflow and reddit might give a representative feedback on what
a large section of programmers think and whatever their preference might be it
could be give some weight in case a new term is not being coined. 

Jan 29 2009
prev sibling parent "Joel C. Salomon" <joelcsalomon gmail.com> writes:
Jarrett Billingsley wrote:
 I was thinking about making D ranges be to D arrays as C++ iterators
 are to C++ pointers: r[0] is head and r[$ - 1] is toe.  But that has
 problems, since you can't make an infinite range, since you can't say
 that r[0] is legal while r[$ - 1] is not.  (D also doesn't allow
 overloading $, an irritating limitation, but one that could be fixed
 in order to implement such a paradigm.)

IIRC, Python uses negative indices to iterate from the end. Or is this=20 entirely not what is under discussion? =97Joel Salomon
Jan 28 2009
prev sibling next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 I've worked valiantly on defining the range infrastructure and making
 std.algorithm work with it. I have to say that I'm even more pleased
 with the result than I'd ever expected when I started. Ranges and
 concepts really make for beautiful code, and I am sure pretty darn
 efficient too.
 There's a lot to sink one's teeth in, but unfortunately the code hinges
 on a compiler fix that Walter was kind enough to send me privately. I
 did document the work, but the documentation doesn't really make justice
 to the extraordinary possibilities that lay ahead of us. Anyhow, here's
 a sneak preview into the up-and-coming ranges and their algorithms.
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html
 Ranges are easy to define and compose efficiently. It was, however, a
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges it
 iterates on. With that, it's very easy to e.g. sort multiple arrays in
 parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. random
 iteration if all components offer it, which means that you can do crazy
 things like sorting data that sits partially in one array and partially
 in another.
 Singly-linked list ranges are in, and to my soothing I found an answer
 to the container/range dichotomy in the form of a topology policy. A
 range may or may not be able to modify the topology of the data it's
 iterating over; if it can, it's a free-standing range, much like
 built-in arrays are. If it can't, it's a limited range tied to a
 container (of which I defined none so far, but give me time) and it's
 only the container that can mess with the topology in controlled ways.
 More on that later.
 Feedback welcome.
 Andrei

Wow. That looks truly amazing! I can't wait until it's released so I can try it out! At first glance, my only constructive criticism is that, in Proxy, I'd ideally like to see standard D tuples used, meaning: auto foo = a[0]; // instead of: auto bar = a.at!(0); This might require a few changes to the core language to support. However, it would give the power of the builtin tuples to Proxy structs, such as iterating over the members with foreach and passing a tuple to a function.
Jan 27 2009
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 I've worked valiantly on defining the range infrastructure and making
 std.algorithm work with it. I have to say that I'm even more pleased
 with the result than I'd ever expected when I started. Ranges and
 concepts really make for beautiful code, and I am sure pretty darn
 efficient too.
 There's a lot to sink one's teeth in, but unfortunately the code hinges
 on a compiler fix that Walter was kind enough to send me privately. I
 did document the work, but the documentation doesn't really make justice
 to the extraordinary possibilities that lay ahead of us. Anyhow, here's
 a sneak preview into the up-and-coming ranges and their algorithms.
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html
 Ranges are easy to define and compose efficiently. It was, however, a
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges it
 iterates on. With that, it's very easy to e.g. sort multiple arrays in
 parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. random
 iteration if all components offer it, which means that you can do crazy
 things like sorting data that sits partially in one array and partially
 in another.
 Singly-linked list ranges are in, and to my soothing I found an answer
 to the container/range dichotomy in the form of a topology policy. A
 range may or may not be able to modify the topology of the data it's
 iterating over; if it can, it's a free-standing range, much like
 built-in arrays are. If it can't, it's a limited range tied to a
 container (of which I defined none so far, but give me time) and it's
 only the container that can mess with the topology in controlled ways.
 More on that later.
 Feedback welcome.
 Andrei

Wow. That looks truly amazing! I can't wait until it's released so I can try it out! At first glance, my only constructive criticism is that, in Proxy, I'd ideally like to see standard D tuples used, meaning: auto foo = a[0]; // instead of: auto bar = a.at!(0); This might require a few changes to the core language to support. However, it would give the power of the builtin tuples to Proxy structs, such as iterating over the members with foreach and passing a tuple to a function.

Yes, I find it jarring as well. I will submit an enhancement request. Andrei
Jan 27 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:
   At first glance, my only constructive criticism is that, in Proxy, I'd
 ideally like to see standard D tuples used, meaning:
 
 auto foo = a[0];  // instead of:
 auto bar = a.at!(0);
 
 This might require a few changes to the core language to support.  However, it
 would give the power of the builtin tuples to Proxy structs, such as iterating
 over the members with foreach and passing a tuple to a function.

Ok, you all may want to direct further ideas on this topic to http://d.puremagic.com/issues/show_bug.cgi?id=2628. Andrei
Jan 27 2009
prev sibling next sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Wed, Jan 28, 2009 at 2:01 PM, Jarrett Billingsley
<jarrett.billingsley gmail.com> wrote:
 On Tue, Jan 27, 2009 at 11:15 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 I've worked valiantly on defining the range infrastructure and making
 std.algorithm work with it. I have to say that I'm even more pleased with
 the result than I'd ever expected when I started. Ranges and concepts really
 make for beautiful code, and I am sure pretty darn efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code hinges on a
 compiler fix that Walter was kind enough to send me privately. I did
 document the work, but the documentation doesn't really make justice to the
 extraordinary possibilities that lay ahead of us. Anyhow, here's a sneak
 preview into the up-and-coming ranges and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

 Ranges are easy to define and compose efficiently. It was, however, a pig to
 get a zip(r1, r2, ...) working that can mutate back the ranges it iterates
 on. With that, it's very easy to e.g. sort multiple arrays in parallel.
 Similarly, chain(r1, r2, ...) is able to offer e.g. random iteration if all
 components offer it, which means that you can do crazy things like sorting
 data that sits partially in one array and partially in another.

 Singly-linked list ranges are in, and to my soothing I found an answer to
 the container/range dichotomy in the form of a topology policy. A range may
 or may not be able to modify the topology of the data it's iterating over;
 if it can, it's a free-standing range, much like built-in arrays are. If it
 can't, it's a limited range tied to a container (of which I defined none so
 far, but give me time) and it's only the container that can mess with the
 topology in controlled ways. More on that later.

 Feedback welcome.

This is some awesome stuff. std.range and std.algorithm are really coming together into a compelling whole. I don't know what else to say - _you_ seem to know what you're doing!

Indeed. It makes me wish the porting fairy would visit my D1 code repositories tonight while I sleep.
 Also - "toe" is still a stupid name.  ;)  "first" and "last" would
 have been my first choices, they seem so obvious.

It's especially strange given the description: "toe -- returns the rightmost element" I don't usually think of my toes as being my rightmost element... What is the argument against "first" and "last", anyway? Just that they're boring? --bb
Jan 27 2009
prev sibling next sibling parent Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Wed, Jan 28, 2009 at 12:17 AM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:
 Also - "toe" is still a stupid name.  ;)  "first" and "last" would
 have been my first choices, they seem so obvious.

Turns out toe isn't half bad when I was coding with it - all I needed was something short and memorable.

Heh. What about "a" and "z" then? ;))
 One problem with "first" is that it sometimes suggests something else. For
 example, if I have a generator for the numbers 1 to 10 and have advanced it
 a bit, gen.first suggests I'm looking back to the very first element, not
 the state of the iteration. I agree that gen.head isn't terribly evocative
 either, but then at least it doesn't evoke something wrong :o).

I was thinking about making D ranges be to D arrays as C++ iterators are to C++ pointers: r[0] is head and r[$ - 1] is toe. But that has problems, since you can't make an infinite range, since you can't say that r[0] is legal while r[$ - 1] is not. (D also doesn't allow overloading $, an irritating limitation, but one that could be fixed in order to implement such a paradigm.)
 Anyhow, how about doing what Haskell does? They use "head" and "last". And
 at least we'd be able to blame *them* if anyone doesn't like the names :o).
 Thoughts?

Without the "first" to provide contrast, "last" potentially takes on the confusingly-overloaded English meaning of "previous". Which isn't the kind of ambiguity you'd want in ranges, I'll bet. Naming is a pain in the butt. Fine, I'll live with "head" and "toe" ;)
Jan 27 2009
prev sibling next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 Feedback welcome.

Awesome work! Props to bearophile, too.
Jan 27 2009
prev sibling next sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Wed, Jan 28, 2009 at 2:17 PM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:
 Jarrett Billingsley wrote:
 On Tue, Jan 27, 2009 at 11:15 PM, Andrei Alexandrescu

[...]
 Feedback welcome.

This is some awesome stuff. std.range and std.algorithm are really coming together into a compelling whole. I don't know what else to say - _you_ seem to know what you're doing! It's a minor point, but in the docs, with all the templating madness it gets very hard to find the name of the symbol actually being documented. For example: Filter!(unaryFun!(pred),Chain!(Ranges)) filter(alias pred, Ranges...)(Ranges rs); "filter" gets lost in the middle. Could it be highlighted, or moved to the front (using a Pascal-like "func(params) : returntype" syntax instead)?

Good point. Actually I've been experimenting with using "auto" for the return type. That does work most of the time, but unfortunately ddoc doesn't understand it. Then,
 Also - "toe" is still a stupid name.  ;)  "first" and "last" would
 have been my first choices, they seem so obvious.

Turns out toe isn't half bad when I was coding with it - all I needed was something short and memorable. One problem with "first" is that it sometimes suggests something else. For example, if I have a generator for the numbers 1 to 10 and have advanced it a bit, gen.first suggests I'm looking back to the very first element, not the state of the iteration. I agree that gen.head isn't terribly evocative either, but then at least it doesn't evoke something wrong :o). Anyhow, how about doing what Haskell does? They use "head" and "last". And at least we'd be able to blame *them* if anyone doesn't like the names :o). Thoughts?

Well Haskell has a commonly used "tail", so it has an excuse for not making head/last match up. There's the C++-ish names: front/back Anything wrong with those? --bb
Jan 27 2009
prev sibling next sibling parent reply Don <nospam nospam.com> writes:
Andrei Alexandrescu wrote:
 I've worked valiantly on defining the range infrastructure and making 
 std.algorithm work with it. I have to say that I'm even more pleased 
 with the result than I'd ever expected when I started. Ranges and 
 concepts really make for beautiful code, and I am sure pretty darn 
 efficient too.
 
 There's a lot to sink one's teeth in, but unfortunately the code hinges 
 on a compiler fix that Walter was kind enough to send me privately. I 
 did document the work, but the documentation doesn't really make justice 
 to the extraordinary possibilities that lay ahead of us. Anyhow, here's 
 a sneak preview into the up-and-coming ranges and their algorithms.
 
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html
 
 Ranges are easy to define and compose efficiently. It was, however, a 
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges it 
 iterates on. With that, it's very easy to e.g. sort multiple arrays in 
 parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. random 
 iteration if all components offer it, which means that you can do crazy 
 things like sorting data that sits partially in one array and partially 
 in another.
 
 Singly-linked list ranges are in, and to my soothing I found an answer 
 to the container/range dichotomy in the form of a topology policy. A 
 range may or may not be able to modify the topology of the data it's 
 iterating over; if it can, it's a free-standing range, much like 
 built-in arrays are. If it can't, it's a limited range tied to a 
 container (of which I defined none so far, but give me time) and it's 
 only the container that can mess with the topology in controlled ways. 
 More on that later.
 
 Feedback welcome.
 
 
 Andrei

Awesome stuff. Will take some time to adjust my thought processes for this. Some minor comments: * Is Repeat simply a single-parameter form of Cycle? I can't see any difference between them. * Uniq docs should at least add one word: Iterates [[consecutively]] unique elements of the given range. * find: To find the last element of [[a bidirectional]] haystack satisfying pred, call find!(pred)(retro(haystack)). (unless Retro also works for forward ranges, which seems unlikely). * There's no pushHeap. Is it planned?
Jan 28 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Don wrote:
 Andrei Alexandrescu wrote:
 I've worked valiantly on defining the range infrastructure and making 
 std.algorithm work with it. I have to say that I'm even more pleased 
 with the result than I'd ever expected when I started. Ranges and 
 concepts really make for beautiful code, and I am sure pretty darn 
 efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code 
 hinges on a compiler fix that Walter was kind enough to send me 
 privately. I did document the work, but the documentation doesn't 
 really make justice to the extraordinary possibilities that lay ahead 
 of us. Anyhow, here's a sneak preview into the up-and-coming ranges 
 and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

 Ranges are easy to define and compose efficiently. It was, however, a 
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges 
 it iterates on. With that, it's very easy to e.g. sort multiple arrays 
 in parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. 
 random iteration if all components offer it, which means that you can 
 do crazy things like sorting data that sits partially in one array and 
 partially in another.

 Singly-linked list ranges are in, and to my soothing I found an answer 
 to the container/range dichotomy in the form of a topology policy. A 
 range may or may not be able to modify the topology of the data it's 
 iterating over; if it can, it's a free-standing range, much like 
 built-in arrays are. If it can't, it's a limited range tied to a 
 container (of which I defined none so far, but give me time) and it's 
 only the container that can mess with the topology in controlled ways. 
 More on that later.

 Feedback welcome.


 Andrei

Awesome stuff. Will take some time to adjust my thought processes for this. Some minor comments: * Is Repeat simply a single-parameter form of Cycle? I can't see any difference between them.

Cycle takes a range and essentially provides a (potentially mutable!) way of iterating it. Repeat just gives one element. At the moment that element is also mutable, so the difference is moot. I'll consider removing Repeat.
 * Uniq docs should at least add one word:  Iterates [[consecutively]] 
 unique elements of the given range.
 * find:
 To find the last element of [[a bidirectional]] haystack satisfying 
 pred, call find!(pred)(retro(haystack)).
 
 (unless Retro also works for forward ranges, which seems unlikely).

Thanks (and correct).
 * There's no pushHeap. Is it planned?

I plan to do something nicer: make Heap an entity of its own instead of a collection of disparate functions. I'm unsure about the name because I mean "the computer science heap" as opposed to "the heap for allocating memory". Andrei
Jan 28 2009
next sibling parent reply Don <nospam nospam.com> writes:
Andrei Alexandrescu wrote:
 Don wrote:
 Andrei Alexandrescu wrote:
 I've worked valiantly on defining the range infrastructure and making 
 std.algorithm work with it. I have to say that I'm even more pleased 
 with the result than I'd ever expected when I started. Ranges and 
 concepts really make for beautiful code, and I am sure pretty darn 
 efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code 
 hinges on a compiler fix that Walter was kind enough to send me 
 privately. I did document the work, but the documentation doesn't 
 really make justice to the extraordinary possibilities that lay ahead 
 of us. Anyhow, here's a sneak preview into the up-and-coming ranges 
 and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

 Ranges are easy to define and compose efficiently. It was, however, a 
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges 
 it iterates on. With that, it's very easy to e.g. sort multiple 
 arrays in parallel. Similarly, chain(r1, r2, ...) is able to offer 
 e.g. random iteration if all components offer it, which means that 
 you can do crazy things like sorting data that sits partially in one 
 array and partially in another.

 Singly-linked list ranges are in, and to my soothing I found an 
 answer to the container/range dichotomy in the form of a topology 
 policy. A range may or may not be able to modify the topology of the 
 data it's iterating over; if it can, it's a free-standing range, much 
 like built-in arrays are. If it can't, it's a limited range tied to a 
 container (of which I defined none so far, but give me time) and it's 
 only the container that can mess with the topology in controlled 
 ways. More on that later.

 Feedback welcome.


 Andrei

Awesome stuff. Will take some time to adjust my thought processes for this. Some minor comments: * Is Repeat simply a single-parameter form of Cycle? I can't see any difference between them.

Cycle takes a range and essentially provides a (potentially mutable!) way of iterating it. Repeat just gives one element. At the moment that element is also mutable, so the difference is moot. I'll consider removing Repeat.
 * Uniq docs should at least add one word:  Iterates [[consecutively]] 
 unique elements of the given range.
 * find:
 To find the last element of [[a bidirectional]] haystack satisfying 
 pred, call find!(pred)(retro(haystack)).

 (unless Retro also works for forward ranges, which seems unlikely).

Thanks (and correct).
 * There's no pushHeap. Is it planned?

I plan to do something nicer: make Heap an entity of its own instead of a collection of disparate functions. I'm unsure about the name because I mean "the computer science heap" as opposed to "the heap for allocating memory".

Even better. You might consider including adjustHeap, which is used in eg Dijkstra's algorithm. Stepanov said it was intended to have been public in the STL, but got dropped for political reasons <g>.
Jan 28 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Don wrote:
 Andrei Alexandrescu wrote:
 Don wrote:
 Andrei Alexandrescu wrote:
 I've worked valiantly on defining the range infrastructure and 
 making std.algorithm work with it. I have to say that I'm even more 
 pleased with the result than I'd ever expected when I started. 
 Ranges and concepts really make for beautiful code, and I am sure 
 pretty darn efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code 
 hinges on a compiler fix that Walter was kind enough to send me 
 privately. I did document the work, but the documentation doesn't 
 really make justice to the extraordinary possibilities that lay 
 ahead of us. Anyhow, here's a sneak preview into the up-and-coming 
 ranges and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

 Ranges are easy to define and compose efficiently. It was, however, 
 a pig to get a zip(r1, r2, ...) working that can mutate back the 
 ranges it iterates on. With that, it's very easy to e.g. sort 
 multiple arrays in parallel. Similarly, chain(r1, r2, ...) is able 
 to offer e.g. random iteration if all components offer it, which 
 means that you can do crazy things like sorting data that sits 
 partially in one array and partially in another.

 Singly-linked list ranges are in, and to my soothing I found an 
 answer to the container/range dichotomy in the form of a topology 
 policy. A range may or may not be able to modify the topology of the 
 data it's iterating over; if it can, it's a free-standing range, 
 much like built-in arrays are. If it can't, it's a limited range 
 tied to a container (of which I defined none so far, but give me 
 time) and it's only the container that can mess with the topology in 
 controlled ways. More on that later.

 Feedback welcome.


 Andrei

Awesome stuff. Will take some time to adjust my thought processes for this. Some minor comments: * Is Repeat simply a single-parameter form of Cycle? I can't see any difference between them.

Cycle takes a range and essentially provides a (potentially mutable!) way of iterating it. Repeat just gives one element. At the moment that element is also mutable, so the difference is moot. I'll consider removing Repeat.
 * Uniq docs should at least add one word:  Iterates [[consecutively]] 
 unique elements of the given range.
 * find:
 To find the last element of [[a bidirectional]] haystack satisfying 
 pred, call find!(pred)(retro(haystack)).

 (unless Retro also works for forward ranges, which seems unlikely).

Thanks (and correct).
 * There's no pushHeap. Is it planned?

I plan to do something nicer: make Heap an entity of its own instead of a collection of disparate functions. I'm unsure about the name because I mean "the computer science heap" as opposed to "the heap for allocating memory".

Even better. You might consider including adjustHeap, which is used in eg Dijkstra's algorithm. Stepanov said it was intended to have been public in the STL, but got dropped for political reasons <g>.

(Sorry, this fell through the cracks.) What does adjustHeap do? I have heap adjustment as part of pop() and the constructor. Andrei
Jan 31 2009
parent Don <nospam nospam.com> writes:
Andrei Alexandrescu wrote:
 Don wrote:
 Andrei Alexandrescu wrote:
 Don wrote:
 Andrei Alexandrescu wrote:
 I've worked valiantly on defining the range infrastructure and 
 making std.algorithm work with it. I have to say that I'm even more 
 pleased with the result than I'd ever expected when I started. 
 Ranges and concepts really make for beautiful code, and I am sure 
 pretty darn efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code 
 hinges on a compiler fix that Walter was kind enough to send me 
 privately. I did document the work, but the documentation doesn't 
 really make justice to the extraordinary possibilities that lay 
 ahead of us. Anyhow, here's a sneak preview into the up-and-coming 
 ranges and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html 


 Ranges are easy to define and compose efficiently. It was, however, 
 a pig to get a zip(r1, r2, ...) working that can mutate back the 
 ranges it iterates on. With that, it's very easy to e.g. sort 
 multiple arrays in parallel. Similarly, chain(r1, r2, ...) is able 
 to offer e.g. random iteration if all components offer it, which 
 means that you can do crazy things like sorting data that sits 
 partially in one array and partially in another.

 Singly-linked list ranges are in, and to my soothing I found an 
 answer to the container/range dichotomy in the form of a topology 
 policy. A range may or may not be able to modify the topology of 
 the data it's iterating over; if it can, it's a free-standing 
 range, much like built-in arrays are. If it can't, it's a limited 
 range tied to a container (of which I defined none so far, but give 
 me time) and it's only the container that can mess with the 
 topology in controlled ways. More on that later.

 Feedback welcome.


 Andrei

Awesome stuff. Will take some time to adjust my thought processes for this. Some minor comments: * Is Repeat simply a single-parameter form of Cycle? I can't see any difference between them.

Cycle takes a range and essentially provides a (potentially mutable!) way of iterating it. Repeat just gives one element. At the moment that element is also mutable, so the difference is moot. I'll consider removing Repeat.
 * Uniq docs should at least add one word:  Iterates 
 [[consecutively]] unique elements of the given range.
 * find:
 To find the last element of [[a bidirectional]] haystack satisfying 
 pred, call find!(pred)(retro(haystack)).

 (unless Retro also works for forward ranges, which seems unlikely).

Thanks (and correct).
 * There's no pushHeap. Is it planned?

I plan to do something nicer: make Heap an entity of its own instead of a collection of disparate functions. I'm unsure about the name because I mean "the computer science heap" as opposed to "the heap for allocating memory".

Even better. You might consider including adjustHeap, which is used in eg Dijkstra's algorithm. Stepanov said it was intended to have been public in the STL, but got dropped for political reasons <g>.

(Sorry, this fell through the cracks.) What does adjustHeap do? I have heap adjustment as part of pop() and the constructor. Andrei

single element has been changed.
Jan 31 2009
prev sibling next sibling parent reply Denis Koroskin <2korden gmail.com> writes:
Andrei Alexandrescu Wrote:

 Don wrote:
 Andrei Alexandrescu wrote:
 I've worked valiantly on defining the range infrastructure and making 
 std.algorithm work with it. I have to say that I'm even more pleased 
 with the result than I'd ever expected when I started. Ranges and 
 concepts really make for beautiful code, and I am sure pretty darn 
 efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code 
 hinges on a compiler fix that Walter was kind enough to send me 
 privately. I did document the work, but the documentation doesn't 
 really make justice to the extraordinary possibilities that lay ahead 
 of us. Anyhow, here's a sneak preview into the up-and-coming ranges 
 and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

 Ranges are easy to define and compose efficiently. It was, however, a 
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges 
 it iterates on. With that, it's very easy to e.g. sort multiple arrays 
 in parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. 
 random iteration if all components offer it, which means that you can 
 do crazy things like sorting data that sits partially in one array and 
 partially in another.

 Singly-linked list ranges are in, and to my soothing I found an answer 
 to the container/range dichotomy in the form of a topology policy. A 
 range may or may not be able to modify the topology of the data it's 
 iterating over; if it can, it's a free-standing range, much like 
 built-in arrays are. If it can't, it's a limited range tied to a 
 container (of which I defined none so far, but give me time) and it's 
 only the container that can mess with the topology in controlled ways. 
 More on that later.

 Feedback welcome.


 Andrei

Awesome stuff. Will take some time to adjust my thought processes for this. Some minor comments: * Is Repeat simply a single-parameter form of Cycle? I can't see any difference between them.

Cycle takes a range and essentially provides a (potentially mutable!) way of iterating it. Repeat just gives one element. At the moment that element is also mutable, so the difference is moot. I'll consider removing Repeat.
 * Uniq docs should at least add one word:  Iterates [[consecutively]] 
 unique elements of the given range.
 * find:
 To find the last element of [[a bidirectional]] haystack satisfying 
 pred, call find!(pred)(retro(haystack)).
 
 (unless Retro also works for forward ranges, which seems unlikely).

Thanks (and correct).
 * There's no pushHeap. Is it planned?

I plan to do something nicer: make Heap an entity of its own instead of a collection of disparate functions. I'm unsure about the name because I mean "the computer science heap" as opposed to "the heap for allocating memory". Andrei

Heap is often called a "pyramid" in russian literature, but I'm not sure if it is a worldwide-used term.
Jan 28 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Denis Koroskin wrote:
 Heap is often called a "pyramid" in russian literature, but I'm not
 sure if it is a worldwide-used term.

Better yet, let's use "Madoff". Andrei
Jan 28 2009
prev sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 I plan to do something nicer: make Heap an entity of its own instead of 
 a collection of disparate functions. I'm unsure about the name because I 
 mean "the computer science heap" as opposed to "the heap for allocating 
 memory".

I really like the use in the documentation of informational links to wikipedia and other sources so the user who is unfamiliar with the terms can easily learn more about them. Perhaps a link for what you mean by heap would solve the problem.
Jan 28 2009
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Wed, 28 Jan 2009 12:07:16 +0300, Nick Sabalausky <a a.a> wrote:

 "Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message
 news:gloppm$1vog$1 digitalmars.com...
 Jarrett Billingsley wrote:
 On Tue, Jan 27, 2009 at 11:15 PM, Andrei Alexandrescu

 Feedback welcome.

This is some awesome stuff. std.range and std.algorithm are really coming together into a compelling whole. I don't know what else to say - _you_ seem to know what you're doing! It's a minor point, but in the docs, with all the templating madness it gets very hard to find the name of the symbol actually being documented. For example: Filter!(unaryFun!(pred),Chain!(Ranges)) filter(alias pred, Ranges...)(Ranges rs); "filter" gets lost in the middle. Could it be highlighted, or moved to the front (using a Pascal-like "func(params) : returntype" syntax instead)?

Good point. Actually I've been experimenting with using "auto" for the return type. That does work most of the time, but unfortunately ddoc doesn't understand it. Then,
 Also - "toe" is still a stupid name.  ;)  "first" and "last" would
 have been my first choices, they seem so obvious.

Turns out toe isn't half bad when I was coding with it - all I needed was something short and memorable. One problem with "first" is that it sometimes suggests something else. For example, if I have a generator for the numbers 1 to 10 and have advanced it a bit, gen.first suggests I'm looking back to the very first element, not the state of the iteration. I agree that gen.head isn't terribly evocative either, but then at least it doesn't evoke something wrong :o). Anyhow, how about doing what Haskell does? They use "head" and "last". And at least we'd be able to blame *them* if anyone doesn't like the names :o). Thoughts? Andrei

Isn't "tail" the standard counterpart to "head"? ("toe" just doesn't sound good)

Tail is often used to denote anything but head (imagine snake).
Jan 28 2009
prev sibling next sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Wed, Jan 28, 2009 at 6:07 PM, Nick Sabalausky <a a.a> wrote:

 Isn't "tail" the standard counterpart to "head"? ("toe" just doesn't sound
 good)

Tail has a history of being used to mean "everything but head" in functional programming languages like Haskel and ML. So of back, last, end, tail, rear, foot, toe, it seems every one has some strike against it. back - could be mistaken for an action last - doesn't pair well with "head", and "first" sounds too much like item #1 overall end - in C++ usually means "one past the end" tail - in FP langs means "everything but head" rear - makes Walter thing unhappy thoughts toe - sounds silly, doesn't make so much sense for a range that represents a tree structure. Toe is sounding pretty ok. Actually I think the critique that it doesn't make sense for a non-linear range should be thrown out. Linearizing is the whole purpose of a range. So even if it wasn't linear before, a range effective is providing a linearized view of it. So that leaves "it sounds silly", which is a pretty weak subjective argument against. --bb
Jan 28 2009
prev sibling next sibling parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Wed, 28 Jan 2009 07:15:25 +0300, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

 I've worked valiantly on defining the range infrastructure and making  
 std.algorithm work with it. I have to say that I'm even more pleased  
 with the result than I'd ever expected when I started. Ranges and  
 concepts really make for beautiful code, and I am sure pretty darn  
 efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code hinges  
 on a compiler fix that Walter was kind enough to send me privately. I  
 did document the work, but the documentation doesn't really make justice  
 to the extraordinary possibilities that lay ahead of us. Anyhow, here's  
 a sneak preview into the up-and-coming ranges and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

 Ranges are easy to define and compose efficiently. It was, however, a  
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges it  
 iterates on. With that, it's very easy to e.g. sort multiple arrays in  
 parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. random  
 iteration if all components offer it, which means that you can do crazy  
 things like sorting data that sits partially in one array and partially  
 in another.

 Singly-linked list ranges are in, and to my soothing I found an answer  
 to the container/range dichotomy in the form of a topology policy. A  
 range may or may not be able to modify the topology of the data it's  
 iterating over; if it can, it's a free-standing range, much like  
 built-in arrays are. If it can't, it's a limited range tied to a  
 container (of which I defined none so far, but give me time) and it's  
 only the container that can mess with the topology in controlled ways.  
 More on that later.

 Feedback welcome.


 Andrei

Sweet! One note - "move" has a precondition: "!pointsTo(source, source)". Shouldn't it be "!pointsTo(source, target)"?
Jan 28 2009
next sibling parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Wed, 28 Jan 2009 12:52:03 +0300, Denis Koroskin <2korden gmail.com> wrote:

 On Wed, 28 Jan 2009 07:15:25 +0300, Andrei Alexandrescu  
 <SeeWebsiteForEmail erdani.org> wrote:

 I've worked valiantly on defining the range infrastructure and making  
 std.algorithm work with it. I have to say that I'm even more pleased  
 with the result than I'd ever expected when I started. Ranges and  
 concepts really make for beautiful code, and I am sure pretty darn  
 efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code hinges  
 on a compiler fix that Walter was kind enough to send me privately. I  
 did document the work, but the documentation doesn't really make  
 justice to the extraordinary possibilities that lay ahead of us.  
 Anyhow, here's a sneak preview into the up-and-coming ranges and their  
 algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

 Ranges are easy to define and compose efficiently. It was, however, a  
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges  
 it iterates on. With that, it's very easy to e.g. sort multiple arrays  
 in parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. random  
 iteration if all components offer it, which means that you can do crazy  
 things like sorting data that sits partially in one array and partially  
 in another.

 Singly-linked list ranges are in, and to my soothing I found an answer  
 to the container/range dichotomy in the form of a topology policy. A  
 range may or may not be able to modify the topology of the data it's  
 iterating over; if it can, it's a free-standing range, much like  
 built-in arrays are. If it can't, it's a limited range tied to a  
 container (of which I defined none so far, but give me time) and it's  
 only the container that can mess with the topology in controlled ways.  
 More on that later.

 Feedback welcome.


 Andrei

Sweet! One note - "move" has a precondition: "!pointsTo(source, source)". Shouldn't it be "!pointsTo(source, target)"?

The following sentence doesn't sound well to me: template isForwardRange(R) "The semantics of a forward range (...) are the same as for a forward range, ..." Recursive definition? Should it say "are the same as for an input range"?
Jan 28 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Denis Koroskin wrote:
 On Wed, 28 Jan 2009 12:52:03 +0300, Denis Koroskin <2korden gmail.com> 
 wrote:
 
 On Wed, 28 Jan 2009 07:15:25 +0300, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> wrote:

 I've worked valiantly on defining the range infrastructure and making 
 std.algorithm work with it. I have to say that I'm even more pleased 
 with the result than I'd ever expected when I started. Ranges and 
 concepts really make for beautiful code, and I am sure pretty darn 
 efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code 
 hinges on a compiler fix that Walter was kind enough to send me 
 privately. I did document the work, but the documentation doesn't 
 really make justice to the extraordinary possibilities that lay ahead 
 of us. Anyhow, here's a sneak preview into the up-and-coming ranges 
 and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

 Ranges are easy to define and compose efficiently. It was, however, a 
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges 
 it iterates on. With that, it's very easy to e.g. sort multiple 
 arrays in parallel. Similarly, chain(r1, r2, ...) is able to offer 
 e.g. random iteration if all components offer it, which means that 
 you can do crazy things like sorting data that sits partially in one 
 array and partially in another.

 Singly-linked list ranges are in, and to my soothing I found an 
 answer to the container/range dichotomy in the form of a topology 
 policy. A range may or may not be able to modify the topology of the 
 data it's iterating over; if it can, it's a free-standing range, much 
 like built-in arrays are. If it can't, it's a limited range tied to a 
 container (of which I defined none so far, but give me time) and it's 
 only the container that can mess with the topology in controlled 
 ways. More on that later.

 Feedback welcome.


 Andrei

Sweet! One note - "move" has a precondition: "!pointsTo(source, source)". Shouldn't it be "!pointsTo(source, target)"?

The following sentence doesn't sound well to me: template isForwardRange(R) "The semantics of a forward range (...) are the same as for a forward range, ..." Recursive definition? Should it say "are the same as for an input range"?

Whoa! I stack overflowed just re-reading that! :o) Thanks. Andrei
Jan 28 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Denis Koroskin wrote:
 On Wed, 28 Jan 2009 07:15:25 +0300, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> wrote:
 
 I've worked valiantly on defining the range infrastructure and making 
 std.algorithm work with it. I have to say that I'm even more pleased 
 with the result than I'd ever expected when I started. Ranges and 
 concepts really make for beautiful code, and I am sure pretty darn 
 efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code 
 hinges on a compiler fix that Walter was kind enough to send me 
 privately. I did document the work, but the documentation doesn't 
 really make justice to the extraordinary possibilities that lay ahead 
 of us. Anyhow, here's a sneak preview into the up-and-coming ranges 
 and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

 Ranges are easy to define and compose efficiently. It was, however, a 
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges 
 it iterates on. With that, it's very easy to e.g. sort multiple arrays 
 in parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. 
 random iteration if all components offer it, which means that you can 
 do crazy things like sorting data that sits partially in one array and 
 partially in another.

 Singly-linked list ranges are in, and to my soothing I found an answer 
 to the container/range dichotomy in the form of a topology policy. A 
 range may or may not be able to modify the topology of the data it's 
 iterating over; if it can, it's a free-standing range, much like 
 built-in arrays are. If it can't, it's a limited range tied to a 
 container (of which I defined none so far, but give me time) and it's 
 only the container that can mess with the topology in controlled ways. 
 More on that later.

 Feedback welcome.


 Andrei

Sweet! One note - "move" has a precondition: "!pointsTo(source, source)". Shouldn't it be "!pointsTo(source, target)"?

Source must not point to itself because after the move the moved object will point to an empty shell. It may point to target because after the move the moved object will point to itself. Andrei
Jan 28 2009
prev sibling next sibling parent reply grauzone <none example.net> writes:
One thing about std.algorithm: you really seem to like using 
compile-time strings as literals. However, this makes the use of 
delegates harder. For example, to use a delegate, you need to do this 
(quoted from your docs):

 int[] a = ...;
 static bool greater(int a, int b)
 {
     return a > b;
 }
 sort!(greater)(a);  // predicate as alias

In my opinion, doing something like
 sort(a, (int a, int b) { return a > b; });

would be simpler and more intuitive than passing a delegate name as template parameter. (The delegate literal syntax still could be improved, though.) Does std.algorithm work with closures at all? I see that the greater() function in your example is marked as static. (Sorry, I didn't test it myself.) Using string mixins messes up syntax highlighting and the code is more obfuscated. If you make an error in your predicate, random funny things internal to the library implementation could happen, and the compiler will spurt out indecipherable error messages for random modules (I guess in this case, std.algorithm or std.functional). How will runtime debugging work? Will the debugger be smart enough to point me to the correct source code location, if there happens a segfault in my predicate? I'm sure it could, if you used delegates instead. Why did you make this so complex? What's your position on this? Do you agree that there are problems, or are you happy with how it is? Why did you choose to do it like this? Because it is shorter, or for performance (avoid delegate call)? Does it enable some weird use cases, which wouldn't be possible when using delegates? Regarding performance: I don't think performance justifies all these problems. Standard library functions should be as fast as possible, but this goal should come second after robustness and simplicity. Another problem is, that using string mixins seems to be quite problematic, because they are mixed in in a different scope. If I'm not mistaken, you can't do this:
 int foo(...) {...}
 sort!("foo(a, b);");

You might think that "sort!("a>b", a);" is elegant and short, but this probably only works out in toy-examples. And macros, which are supposed to magically cure all those problems, were postponed to D3.0. I'm also worried about compile times. You use nested templates with string mixins, which only can be slower to compile than using e.g. the builtin .sort. I don't know if this a problem, but in my opinion, compile times are already high enough. Times will add up! For one, I'm sure that this will generate an additional gazillion of nearly useless linker symbols with very long names.
Jan 28 2009
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
grauzone:
 Why did you choose to do it like this? Because it is shorter, or for 
 performance (avoid delegate call)?

I agree with the general points you have made. Alex has used aliases for performance. My dlibs (for D1) use closures, I like them. Extensive benchmarking of mine have shown me they are often fast enough. In the spots of the program where you need max performance I just don't use them, and I use normal D code. The good thing is that such critical spots are often 2-5-20% of the lines of the whole program, so for me improving safety and syntax was a win. Bye, bearophile
Jan 28 2009
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
bearophile:
 My dlibs (for D1) use closures,

I meant function pointers or delegates, sorry. Also note that two of the most commonly used higher-order functions, that is map/xmap/filter/xfilter can be replaced by a more handy (and often more efficient) lazy/eager array/iterable compr. I hope eventually D developers will understand this simple thing, but it may take few more months/years. Bye, bearophile
Jan 28 2009
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
bearophile wrote:
 grauzone:
 Why did you choose to do it like this? Because it is shorter, or
 for performance (avoid delegate call)?

I agree with the general points you have made. Alex has used aliases for performance. My dlibs (for D1) use closures, I like them. Extensive benchmarking of mine have shown me they are often fast enough. In the spots of the program where you need max performance I just don't use them, and I use normal D code. The good thing is that such critical spots are often 2-5-20% of the lines of the whole program, so for me improving safety and syntax was a win.

It is hard to hit just the right tradeoff between performance and simplicity. One motivating issue, however, is we don't want to leave an excuse or desire to go back to C or C++ for performance reasons, even if those reasons are not reality. On the other hand, I really like the string mixin approach, I think it works simply and elegantly for most predicates.
Jan 28 2009
next sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Walter Bright (newshound1 digitalmars.com)'s article
 It is hard to hit just the right tradeoff between performance and
 simplicity. One motivating issue, however, is we don't want to leave an
 excuse or desire to go back to C or C++ for performance reasons, even if
 those reasons are not reality.

...or to rolling your own ad-hoc versions of the stuff in std.algorithm.
Jan 28 2009
prev sibling parent reply grauzone <none example.net> writes:
Walter Bright wrote:
 bearophile wrote:
 grauzone:
 Why did you choose to do it like this? Because it is shorter, or
 for performance (avoid delegate call)?

I agree with the general points you have made. Alex has used aliases for performance. My dlibs (for D1) use closures, I like them. Extensive benchmarking of mine have shown me they are often fast enough. In the spots of the program where you need max performance I just don't use them, and I use normal D code. The good thing is that such critical spots are often 2-5-20% of the lines of the whole program, so for me improving safety and syntax was a win.

It is hard to hit just the right tradeoff between performance and simplicity. One motivating issue, however, is we don't want to leave an excuse or desire to go back to C or C++ for performance reasons, even if those reasons are not reality.

But they can always roll their own versions of trivial functions like map() and so on. Isn't the point of these standard libraries to provide something simple and generic? Of course, you can't make everyone happy, but why are the performance freaks the one we need to make happy? If you need high performance code, you'll probably always write your own, and won't trust the standard library. Just like you rewrite critical parts of code in assembler, and you don't trust the compiler.
 On the other hand, I really like the string mixin approach, I think it 
 works simply and elegantly for most predicates.

Consider you have this code:
 map!("a*3")(a)

Now you see that you forgot something! For some reason, you actually need to return absolute values! Uh-oh, let's fix that:
 map!("fabs(a*3)")(a)

Oops, this doesn't work. fabs() isn't available, because the code is compiled inside the standard library, and not the module, where the code was written. This is confusing and non-intuitive. Even more, you don't have _any_ way to access fabs() in this code (except if std.algorithm imports std.math). You'll have to rewrite this line of code somehow. Maybe turn it into a delegate. But then you lose the performance benefit you had before. What to do now? Looks like this simple issue caused more work than you thought! And all this even though the predicate is simple and trivial! I don't see how this is simple and elegant. Looks more like a hack. It reminds me a bit of C++, where things first look simple, but actually... they really aren't. But I get Don's and Andrei's points. End of discussion, I guess. By the way: thinking about this, it always comes to my mind that D really needs AST macros!
Jan 29 2009
next sibling parent Max Samukha <samukha voliacable.com.removethis> writes:
On Thu, 29 Jan 2009 10:59:53 +0100, grauzone <none example.net> wrote:

Walter Bright wrote:
 bearophile wrote:
 grauzone:
 Why did you choose to do it like this? Because it is shorter, or
 for performance (avoid delegate call)?

I agree with the general points you have made. Alex has used aliases for performance. My dlibs (for D1) use closures, I like them. Extensive benchmarking of mine have shown me they are often fast enough. In the spots of the program where you need max performance I just don't use them, and I use normal D code. The good thing is that such critical spots are often 2-5-20% of the lines of the whole program, so for me improving safety and syntax was a win.

It is hard to hit just the right tradeoff between performance and simplicity. One motivating issue, however, is we don't want to leave an excuse or desire to go back to C or C++ for performance reasons, even if those reasons are not reality.

But they can always roll their own versions of trivial functions like map() and so on. Isn't the point of these standard libraries to provide something simple and generic? Of course, you can't make everyone happy, but why are the performance freaks the one we need to make happy? If you need high performance code, you'll probably always write your own, and won't trust the standard library. Just like you rewrite critical parts of code in assembler, and you don't trust the compiler.
 On the other hand, I really like the string mixin approach, I think it 
 works simply and elegantly for most predicates.

Consider you have this code:
 map!("a*3")(a)

Now you see that you forgot something! For some reason, you actually need to return absolute values! Uh-oh, let's fix that:
 map!("fabs(a*3)")(a)

Oops, this doesn't work. fabs() isn't available, because the code is compiled inside the standard library, and not the module, where the code was written. This is confusing and non-intuitive. Even more, you don't have _any_ way to access fabs() in this code (except if std.algorithm imports std.math). You'll have to rewrite this line of code somehow. Maybe turn it into a delegate. But then you lose the performance benefit you had before. What to do now? Looks like this simple issue caused more work than you thought! And all this even though the predicate is simple and trivial!

You don't lose the performance benefit. The delegate literal is called directly.
I don't see how this is simple and elegant. Looks more like a hack. It 
reminds me a bit of C++, where things first look simple, but actually... 
they really aren't.

But I get Don's and Andrei's points. End of discussion, I guess.

By the way: thinking about this, it always comes to my mind that D 
really needs AST macros!

Jan 29 2009
prev sibling next sibling parent reply Don <nospam nospam.com> writes:
grauzone wrote:
 Walter Bright wrote:
 bearophile wrote:
 grauzone:
 Why did you choose to do it like this? Because it is shorter, or
 for performance (avoid delegate call)?

I agree with the general points you have made. Alex has used aliases for performance. My dlibs (for D1) use closures, I like them. Extensive benchmarking of mine have shown me they are often fast enough. In the spots of the program where you need max performance I just don't use them, and I use normal D code. The good thing is that such critical spots are often 2-5-20% of the lines of the whole program, so for me improving safety and syntax was a win.

It is hard to hit just the right tradeoff between performance and simplicity. One motivating issue, however, is we don't want to leave an excuse or desire to go back to C or C++ for performance reasons, even if those reasons are not reality.

But they can always roll their own versions of trivial functions like map() and so on. Isn't the point of these standard libraries to provide something simple and generic? Of course, you can't make everyone happy, but why are the performance freaks the one we need to make happy? If you need high performance code, you'll probably always write your own, and won't trust the standard library. Just like you rewrite critical parts of code in assembler, and you don't trust the compiler.
 On the other hand, I really like the string mixin approach, I think it 
 works simply and elegantly for most predicates.

Consider you have this code: > map!("a*3")(a) Now you see that you forgot something! For some reason, you actually need to return absolute values! Uh-oh, let's fix that: > map!("fabs(a*3)")(a) Oops, this doesn't work. fabs() isn't available, because the code is compiled inside the standard library, and not the module, where the code was written. This is confusing and non-intuitive. Even more, you don't have _any_ way to access fabs() in this code (except if std.algorithm imports std.math). You'll have to rewrite this line of code somehow. Maybe turn it into a delegate. But then you lose the performance benefit you had before. What to do now?

map!("((a>0)?a:-a)*3")(a); It's a good point though. Actually, I think abs(), and possibly max() and min(), should be in std.object. They're just as fundamental as division. I think that would leave sqrt() as the only function which is fast enough that the delegate overhead would be significant. And DMD should be able to inline simple delegates anyway. Looks like this simple issue caused more
 work than you thought! And all this even though the predicate is simple 
 and trivial!
 
 I don't see how this is simple and elegant. Looks more like a hack. It 
 reminds me a bit of C++, where things first look simple, but actually... 
 they really aren't.
 
 But I get Don's and Andrei's points. End of discussion, I guess.
 
 By the way: thinking about this, it always comes to my mind that D 
 really needs AST macros!

Agreed.
Jan 29 2009
parent reply Sean Kelly <sean invisibleduck.org> writes:
Don wrote:
 
 It's a good point though. Actually, I think abs(), and possibly max() 
 and min(), should be in std.object. They're just as fundamental as 
 division.

That's actually a good idea. They don't really fit anywhere else, and as you say, they're incredibly common to use. Not sure if people would object to these symbols being an implicit part of the namespace of every module though. Sean
Jan 29 2009
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Sean Kelly (sean invisibleduck.org)'s article
 Don wrote:
 It's a good point though. Actually, I think abs(), and possibly max()
 and min(), should be in std.object. They're just as fundamental as
 division.

as you say, they're incredibly common to use. Not sure if people would object to these symbols being an implicit part of the namespace of every module though. Sean

Agreed. These are things that are so often used and so basic that even the overhead of having to remember to import something to use them is sometimes too much. As far as namespace pollution, what reasonable person would ever name something max(), min() or abs() if it doesn't do what the standard max(), min() and abs() functions in Phobos do?
Jan 29 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
grauzone wrote:
 Consider you have this code:
 
  > map!("a*3")(a)
 
 Now you see that you forgot something! For some reason, you actually 
 need to return absolute values! Uh-oh, let's fix that:
 
  > map!("fabs(a*3)")(a)
 
 Oops, this doesn't work. fabs() isn't available, because the code is 
 compiled inside the standard library, and not the module, where the code 
 was written. This is confusing and non-intuitive. Even more, you don't 
 have _any_ way to access fabs() in this code (except if std.algorithm 
 imports std.math). You'll have to rewrite this line of code somehow. 
 Maybe turn it into a delegate. But then you lose the performance benefit 
 you had before. What to do now? Looks like this simple issue caused more 
 work than you thought! And all this even though the predicate is simple 
 and trivial!

Lest a misunderstanding arises, the code: auto r = map!((float a) { return fabs(a); })(a); does *not* involve a delegate; it's still a direct call. This code doesn't currently compile because of a bug in the compiler, but this equivalent code does: float fun(float a) { return fabs(a); } auto r = map!(fun)(a); and again it does not involve a delegate.
 I don't see how this is simple and elegant. Looks more like a hack. It 
 reminds me a bit of C++, where things first look simple, but actually... 
 they really aren't.
 
 But I get Don's and Andrei's points. End of discussion, I guess.

Whereas I reckon in the beginning you weren't fully aware of the flexibility offered by pass-by-alias, you brought some good points. The functionality afforded by strings can be improved by importing more modules inside std.functional. I just added std.math and std.contracts. At the end of the day std.functional could include the entire Phobos (you'd be surprised how fast that compiles). I agree that that's not elegant, but let's not forget that strings are just that - an *additional* convenience to the many conveniences that pass-by-alias imparts. Andrei
Jan 29 2009
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 Lest a misunderstanding arises, the code:
 auto r = map!((float a) { return fabs(a); })(a);
 does *not* involve a delegate; it's still a direct call. This code
 doesn't currently compile because of a bug in the compiler, but this
 equivalent code does:
 float fun(float a) { return fabs(a); }
 auto r = map!(fun)(a);
 and again it does not involve a delegate.

But, for the truly performance obsessed, it's still a non-static nested function that doesn't access any local variables in the outer scope. Isn't it still taking a pointer to the outer scope as an implicit argument, kind of like a this pointer, or are real-world compilers sufficiently smart to optimize that out if you never use any of the variables in the outer scope? Yes, I know this is nitpicking, but I'm asking primarily out of curiosity rather than out of practical concern. I also realize that, if you really care that much, you can declare fun() as static and get rid of the implicit pointer to the outer scope. This is kind of ugly, but I guess code that's this micro-optimized is going to be ugly any way you cut it.
Jan 29 2009
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from dsimcha (dsimcha yahoo.com)'s article
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 Lest a misunderstanding arises, the code:
 auto r = map!((float a) { return fabs(a); })(a);
 does *not* involve a delegate; it's still a direct call. This code
 doesn't currently compile because of a bug in the compiler, but this
 equivalent code does:
 float fun(float a) { return fabs(a); }
 auto r = map!(fun)(a);
 and again it does not involve a delegate.

that doesn't access any local variables in the outer scope. Isn't it still taking a pointer to the outer scope as an implicit argument, kind of like a this pointer, or are real-world compilers sufficiently smart to optimize that out if you never use any of the variables in the outer scope? Yes, I know this is nitpicking, but I'm asking primarily out of curiosity rather than out of practical concern. I also realize that, if you really care that much, you can declare fun() as static and get rid of the implicit pointer to the outer scope. This is kind of ugly, but I guess code that's this micro-optimized is going to be ugly any way you cut it.

To answer my own question, I benchmarked this using a sorting function, and it doesn't matter in practice, probably because DMD is smart enough to inline simple nested functions. As a positive control (to make sure the benchmark is valid), when I explicitly made the alias a function _pointer_ instead of a function _name_, this made a fairly large difference.
Jan 29 2009
prev sibling next sibling parent reply Don <nospam nospam.com> writes:
grauzone wrote:
 One thing about std.algorithm: you really seem to like using 
 compile-time strings as literals. However, this makes the use of 
 delegates harder. For example, to use a delegate, you need to do this 
 (quoted from your docs):
 
  > int[] a = ...;
  > static bool greater(int a, int b)
  > {
  >     return a > b;
  > }
  > sort!(greater)(a);  // predicate as alias
 
 In my opinion, doing something like
 
  > sort(a, (int a, int b) { return a > b; });
 
 would be simpler and more intuitive than passing a delegate name as 
 template parameter. (The delegate literal syntax still could be 
 improved, though.)
 
 Does std.algorithm work with closures at all? I see that the greater() 
 function in your example is marked as static. (Sorry, I didn't test it 
 myself.)
 
 Using string mixins messes up syntax highlighting 

I think the argument that a language should be designed around the limitations of an IDE designed for a different language is a weak one. Especially with the greatly improved support for string mixins which just got added in the last version of Descent.
 and the code is more 
 obfuscated. If you make an error in your predicate, random funny things 
 internal to the library implementation could happen, and the compiler 
 will spurt out indecipherable error messages for random modules (I guess 
 in this case, std.algorithm or std.functional).

Not necessarily. Andrei can just add: static if(__traits(compiles, mixin(comp) )) { mixin(comp); } else { // static assert is a bit broken, // better to do it this way to provide a backtrace. pragma(msg, "Bad predicate: " ~ comp); deliberate_error_message; // t } into std.functional. Which will generate a very controlled error message. (Doesn't work if the predicate contains mismatched parentheses, but that's fixable). The language changes required to give a perfect solution to this are pretty small (just get static assert() to give the instantiation point of each template which instantiated it, create a version of traits which , given a string, tells you if it would compile if it were mixed in). Then we get: static assert(__traits(mixincompiles, comp), "Predicate: " ~ comp ~ " does not compile"); mxin(comp); How will runtime
 debugging work? Will the debugger be smart enough to point me to the 
 correct source code location, if there happens a segfault in my 
 predicate? I'm sure it could, if you used delegates instead.
 
 Why did you make this so complex? What's your position on this? Do you 
 agree that there are problems, or are you happy with how it is?
 
 Why did you choose to do it like this? Because it is shorter, or for 
 performance (avoid delegate call)? 

It's a LOT faster than delegates. Does it enable some weird use cases,
 which wouldn't be possible when using delegates?
 
 Regarding performance: I don't think performance justifies all these 
 problems. Standard library functions should be as fast as possible, but 
 this goal should come second after robustness and simplicity.
 
 Another problem is, that using string mixins seems to be quite 
 problematic, because they are mixed in in a different scope. If I'm not 
 mistaken, you can't do this:
 
  > int foo(...) {...}
  > sort!("foo(a, b);");
 
 You might think that "sort!("a>b", a);" is elegant and short, but this 
 probably only works out in toy-examples.

String mixins are only intended to be used in simple cases. If it's not simple, you can use a delegate, because the overhead becomes a small part of the cost.
 
 And macros, which are supposed to magically cure all those problems, 
 were postponed to D3.0.
 
 I'm also worried about compile times. You use nested templates with 
 string mixins, which only can be slower to compile than using e.g. the 
 builtin .sort. I don't know if this a problem, but in my opinion, 
 compile times are already high enough. Times will add up!

The CTFE bug still needs to be fixed.
 
 For one, I'm sure that this will generate an additional gazillion of 
 nearly useless linker symbols with very long names.

No. That happens with templates, not CTFE. Excluding the CTFE bug, of course.
Jan 28 2009
next sibling parent reply Christopher Wright <dhasenan gmail.com> writes:
Don wrote:
 grauzone wrote:
 and the code is more obfuscated. If you make an error in your 
 predicate, random funny things internal to the library implementation 
 could happen, and the compiler will spurt out indecipherable error 
 messages for random modules (I guess in this case, std.algorithm or 
 std.functional).

Not necessarily. Andrei can just add: static if(__traits(compiles, mixin(comp) )) { mixin(comp); } else { // static assert is a bit broken, // better to do it this way to provide a backtrace. pragma(msg, "Bad predicate: " ~ comp); deliberate_error_message; // t } into std.functional. Which will generate a very controlled error message. (Doesn't work if the predicate contains mismatched parentheses, but that's fixable).

template MixinThrowHelper(char[] comp) { // if your string mixin requires context, provide it here // though this implies code duplication mixin (comp); enum MixinThrowHelper = true; } template Error(char[] msg) { pragma (msg, msg); error; } static if (__traits (compiles, MixinThrowHelper!(comp))) { mixin (comp); } else { Error!("Bad predicate: " ~ comp); }
 The language changes required to give a perfect solution to this are 
 pretty small (just get static assert() to give the instantiation point 
 of each template which instantiated it, create a version of traits which 
 , given a string, tells you if it would compile if it were mixed in).
 
 Then we get:
 static assert(__traits(mixincompiles, comp), "Predicate: " ~ comp ~ " 
 does not compile");
 
 mxin(comp);

That's certainly prettier.
Jan 28 2009
parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Christopher Wright wrote:
 Don wrote:
 [snip]

 Then we get:
 static assert(__traits(mixincompiles, comp), "Predicate: " ~ comp ~ "
 does not compile");

 mxin(comp);

That's certainly prettier.

Still doesn't give the user a reason for WHY their predicate didn't compile... It's a pity we can't do this (or something similar): template Something(string comp) { static assert( __traits(mixincompiles, comp), "Predicate q{"~comp~"} does not compile, because:\n" ~__traits(mixinerrors, comp, Something.instantiationFile, Something.instantiationLine) ); } -- Daniel
Jan 28 2009
parent reply "Nick Sabalausky" <a a.a> writes:
"Daniel Keep" <daniel.keep.lists gmail.com> wrote in message 
news:glqu65$15pi$1 digitalmars.com...
 Christopher Wright wrote:
 Don wrote:
 [snip]

 Then we get:
 static assert(__traits(mixincompiles, comp), "Predicate: " ~ comp ~ "
 does not compile");

 mxin(comp);

That's certainly prettier.

Still doesn't give the user a reason for WHY their predicate didn't compile... It's a pity we can't do this (or something similar): template Something(string comp) { static assert( __traits(mixincompiles, comp), "Predicate q{"~comp~"} does not compile, because:\n" ~__traits(mixinerrors, comp, Something.instantiationFile, Something.instantiationLine) ); } -- Daniel

I'd much rather see errors and static asserts inside of a template cause the compiler to automatically output a template instantiation "stack trace" (for lack of a better term). Ie, list files/lines starting with the deepest file/line, and then the file/line that instantiated that template, and if that was also inside a template, then the file/line that instantiated that, etc.
Jan 28 2009
parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Nick Sabalausky wrote:
 "Daniel Keep" <daniel.keep.lists gmail.com> wrote in message 
 news:glqu65$15pi$1 digitalmars.com...
 Christopher Wright wrote:
 Don wrote:
 [snip]

 Then we get:
 static assert(__traits(mixincompiles, comp), "Predicate: " ~ comp ~ "
 does not compile");

 mxin(comp);


compile... It's a pity we can't do this (or something similar): template Something(string comp) { static assert( __traits(mixincompiles, comp), "Predicate q{"~comp~"} does not compile, because:\n" ~__traits(mixinerrors, comp, Something.instantiationFile, Something.instantiationLine) ); } -- Daniel

I'd much rather see errors and static asserts inside of a template cause the compiler to automatically output a template instantiation "stack trace" (for lack of a better term). Ie, list files/lines starting with the deepest file/line, and then the file/line that instantiated that template, and if that was also inside a template, then the file/line that instantiated that, etc.

I'd certainly like to see better error reporting for template errors, but I think the ultimate goal should be to be able to write template that, when they do something wrong, can tell the user SPECIFICALLY what they did wrong. Error foo.d line 53: (*vomits template backtrace at the user for a page or two *) -or- Error foo.d line 53: Foo!("blah") expected an int, not a char[4]. -- Daniel
Jan 28 2009
parent "Nick Sabalausky" <a a.a> writes:
"Daniel Keep" <daniel.keep.lists gmail.com> wrote in message 
news:glrlgi$2bu4$1 digitalmars.com...
 Nick Sabalausky wrote:
 "Daniel Keep" <daniel.keep.lists gmail.com> wrote in message
 news:glqu65$15pi$1 digitalmars.com...
 Christopher Wright wrote:
 Don wrote:
 [snip]

 Then we get:
 static assert(__traits(mixincompiles, comp), "Predicate: " ~ comp ~ "
 does not compile");

 mxin(comp);


compile... It's a pity we can't do this (or something similar): template Something(string comp) { static assert( __traits(mixincompiles, comp), "Predicate q{"~comp~"} does not compile, because:\n" ~__traits(mixinerrors, comp, Something.instantiationFile, Something.instantiationLine) ); } -- Daniel

I'd much rather see errors and static asserts inside of a template cause the compiler to automatically output a template instantiation "stack trace" (for lack of a better term). Ie, list files/lines starting with the deepest file/line, and then the file/line that instantiated that template, and if that was also inside a template, then the file/line that instantiated that, etc.

I'd certainly like to see better error reporting for template errors, but I think the ultimate goal should be to be able to write template that, when they do something wrong, can tell the user SPECIFICALLY what they did wrong.

I would think those two things would compliment each other nicely. To modify your examples: template Something(string comp) { static assert( __traits(mixincompiles, comp), "Predicate q{"~comp~"} does not compile, because:\n" ~__traits(mixinerrors, comp) ); } Result: Predicate blah does not compile, because: blah file/line of static assert file/line where Something was actually instantiated My main original point is just that the writer of the meaningful diagnostic message shouldn't have to manually deal with the file/line that attempted the failed instatiation. It should just simply get shown by the compiler saying "Error or static asset failure inside a template? I'd better spit out *both* relevant files/lines along with the error/assert message". The programmer shouldn't have to do that manually.
Jan 28 2009
prev sibling next sibling parent reply grauzone <none example.net> writes:
Don wrote:
 Using string mixins messes up syntax highlighting 

I think the argument that a language should be designed around the limitations of an IDE designed for a different language is a weak one. Especially with the greatly improved support for string mixins which just got added in the last version of Descent.

So all IDEs should contain a D compiler? But let's forget this, it's a minor issue, and it will/can be fixed with magic AST macros or special kinds of string literals.
 and the code is more obfuscated. If you make an error in your 
 predicate, random funny things internal to the library implementation 
 could happen, and the compiler will spurt out indecipherable error 
 messages for random modules (I guess in this case, std.algorithm or 
 std.functional).

Not necessarily. Andrei can just add:

Then he should do it. If not, it becomes a theoretically-fixable-but-in-reality-ignored issue, which causes unnecessary frustration to innocent programmers.
 For one, I'm sure that this will generate an additional gazillion of 
 nearly useless linker symbols with very long names.

No. That happens with templates, not CTFE. Excluding the CTFE bug, of course.

Has nothing to do with CTFE. For example, the following code
 void foo(char[] T)(int x) {}
 void main() {    foo!("hello")(3);   }

Will produce an object files, which contains the following symbol:
 _D1g25__T3fooVG5aa5_68656c6c6fZ3fooFiZv

I don't know if this will ever become an issue, but optlink.exe already crashes often enough.
Jan 29 2009
next sibling parent Fawzi Mohamed <fmohamed mac.com> writes:
Hi Andreii,

I like your present interface/modules, the normal iterators now are not 
forgotten :)
Nice work, and quite comprehensive... a nice addition to D 2.0.

A small correction in
http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
"The semantics of a forward range (not checkable during compilation) 
are the same as for *an input* range,..."

ciao

Fawzi
Jan 29 2009
prev sibling next sibling parent Daniel Keep <daniel.keep.lists gmail.com> writes:
grauzone wrote:
 Don wrote:
 grauzone wrote:
 For one, I'm sure that this will generate an additional gazillion of
 nearly useless linker symbols with very long names.

No. That happens with templates, not CTFE. Excluding the CTFE bug, of course.

Has nothing to do with CTFE. For example, the following code
 void foo(char[] T)(int x) {}
 void main() {    foo!("hello")(3);   }

Will produce an object files, which contains the following symbol:
 _D1g25__T3fooVG5aa5_68656c6c6fZ3fooFiZv

I don't know if this will ever become an issue, but optlink.exe already crashes often enough.

That symbol isn't "nearly useless," it has the code for foo!("hello") attached to it... I mean, it has to go *somewhere*. That said, D does tend to generate a fair number of spurious symbols. I personally think that D's linker should learn how to clean up after it's messy compiler cousin, but then I don't have time to write a linker. If you're complaining that the symbol is hard to read then, yes, it is. But that's what happens when you encode the full type signature of the template into the symbol. In any case, if the name is too long to fit within the limits of OMF, I believe D deflate-compresses the symbol to shorten it. As far as I'm aware, there's no way around this. At the end of the day, you have to store this stuff. -- Daniel
Jan 29 2009
prev sibling next sibling parent Don <nospam nospam.com> writes:
grauzone wrote:
 Don wrote:
 Using string mixins messes up syntax highlighting 

I think the argument that a language should be designed around the limitations of an IDE designed for a different language is a weak one. Especially with the greatly improved support for string mixins which just got added in the last version of Descent.

So all IDEs should contain a D compiler?

Of course they should contain a D front-end. Otherwise, you might as well use a text editor. Most IDEs at present are using a Java front-end with minor modifications, so of course they are not going to support things properly. But let's forget this, it's a
 minor issue, and it will/can be fixed with magic AST macros or special 
 kinds of string literals.

Indeed.
 
 and the code is more obfuscated. If you make an error in your 
 predicate, random funny things internal to the library implementation 
 could happen, and the compiler will spurt out indecipherable error 
 messages for random modules (I guess in this case, std.algorithm or 
 std.functional).

Not necessarily. Andrei can just add:

Then he should do it. If not, it becomes a theoretically-fixable-but-in-reality-ignored issue, which causes unnecessary frustration to innocent programmers.

It really deserves a couple of compiler fixes. Note that metaprogramming error messages in D are generally NOT as terrible as the ones in C++, anyway.
 For one, I'm sure that this will generate an additional gazillion of 
 nearly useless linker symbols with very long names.

No. That happens with templates, not CTFE. Excluding the CTFE bug, of course.

Has nothing to do with CTFE. For example, the following code > void foo(char[] T)(int x) {} > void main() { foo!("hello")(3); } Will produce an object files, which contains the following symbol: > _D1g25__T3fooVG5aa5_68656c6c6fZ3fooFiZv

Yes, that's a template!
 
 I don't know if this will ever become an issue, but optlink.exe already 
 crashes often enough.

Jan 29 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
grauzone wrote:
 Don wrote:
 Using string mixins messes up syntax highlighting 

I think the argument that a language should be designed around the limitations of an IDE designed for a different language is a weak one. Especially with the greatly improved support for string mixins which just got added in the last version of Descent.

So all IDEs should contain a D compiler? But let's forget this, it's a minor issue, and it will/can be fixed with magic AST macros or special kinds of string literals.
 and the code is more obfuscated. If you make an error in your 
 predicate, random funny things internal to the library implementation 
 could happen, and the compiler will spurt out indecipherable error 
 messages for random modules (I guess in this case, std.algorithm or 
 std.functional).

Not necessarily. Andrei can just add:

Then he should do it.

I did, and credited Don in a comment. Thanks Don. Andrei
Jan 29 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Don wrote:
 Not necessarily. Andrei can just add:
 
 static if(__traits(compiles, mixin(comp) )) {
   mixin(comp);
 } else {
    // static assert is a bit broken,
    // better to do it this way to provide a backtrace.
    pragma(msg, "Bad predicate: " ~ comp);
    deliberate_error_message; // t
 }
 
 into std.functional. Which will generate a very controlled error message.
 (Doesn't work if the predicate contains mismatched parentheses, but 
 that's fixable).

I tried the above and didn't quite work. The deliberate_error_message would trigger an error even for valid expressions. What I have now is this: ... inside binaryFunction ... enum testAsExpression = "{"~ElementType1.stringof ~" "~parm1Name~"; "~ElementType2.stringof ~" "~parm2Name~"; return ("~fun~");}()"; static if (__traits(compiles, mixin(testAsExpression))) { enum string code = "return (" ~ fun ~ ");"; alias typeof(mixin(testAsExpression)) ReturnType; } else { static assert( false, "Bad binary function: " ~ fun ~ " for types " ~ ElementType1.stringof ~ " and " ~ ElementType2.stringof ~ ". You need to use an expression using symbols " ~parm1Name~" and "~parm2Name~"."); } This seems to work well but does not provide the line in the instantiating code. Any ideas on how to do it better? Andrei
Jan 31 2009
next sibling parent Christopher Wright <dhasenan gmail.com> writes:
Andrei Alexandrescu wrote:
 Don wrote:
 Not necessarily. Andrei can just add:

 static if(__traits(compiles, mixin(comp) )) {
   mixin(comp);
 } else {
    // static assert is a bit broken,
    // better to do it this way to provide a backtrace.
    pragma(msg, "Bad predicate: " ~ comp);
    deliberate_error_message; // t
 }

 into std.functional. Which will generate a very controlled error message.
 (Doesn't work if the predicate contains mismatched parentheses, but 
 that's fixable).

I tried the above and didn't quite work. The deliberate_error_message would trigger an error even for valid expressions. What I have now is this:

Use a string mixin for deliberate_error_message.
Jan 31 2009
prev sibling parent reply Max Samukha <samukha voliacable.com.removethis> writes:
On Sat, 31 Jan 2009 11:28:07 -0800, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

Don wrote:
 Not necessarily. Andrei can just add:
 
 static if(__traits(compiles, mixin(comp) )) {
   mixin(comp);
 } else {
    // static assert is a bit broken,
    // better to do it this way to provide a backtrace.
    pragma(msg, "Bad predicate: " ~ comp);
    deliberate_error_message; // t
 }
 
 into std.functional. Which will generate a very controlled error message.
 (Doesn't work if the predicate contains mismatched parentheses, but 
 that's fixable).

I tried the above and didn't quite work. The deliberate_error_message would trigger an error even for valid expressions. What I have now is this: ... inside binaryFunction ... enum testAsExpression = "{"~ElementType1.stringof ~" "~parm1Name~"; "~ElementType2.stringof ~" "~parm2Name~"; return ("~fun~");}()"; static if (__traits(compiles, mixin(testAsExpression))) { enum string code = "return (" ~ fun ~ ");"; alias typeof(mixin(testAsExpression)) ReturnType; } else { static assert( false, "Bad binary function: " ~ fun ~ " for types " ~ ElementType1.stringof ~ " and " ~ ElementType2.stringof ~ ". You need to use an expression using symbols " ~parm1Name~" and "~parm2Name~"."); } This seems to work well but does not provide the line in the instantiating code. Any ideas on how to do it better? Andrei

static assert should at least print the location of the instantiating code or better the entire backtrace. This has been asked for several times.
Feb 01 2009
parent reply Christian Kamm <kamm-incasoftware shift-at-left.de> writes:
Max Samukha wrote:
 static assert should at least print the location of the instantiating
 code or better the entire backtrace. This has been asked for several
 times.


Jarrett Billingsley Wrote:
 The code to do this is already in the frontend, DMD and it used to do
 it.  It's just been disabled.  LDC already prints template
 instantiation traces.

Yes, it wasn't hard to output a template instantiation trace when a static assert is hit. LDC produces errors like this: templatecode.d(9): Error: static assert "first arg must be numeric" instantiatied in templatecode.d(4): impldetail!(void,void[],int) instantiatied in myhugefile.d(4109): uservisible!(void) Support for these traces is not exhaustive - there is none for fatal errors, for instance - but since it's guaranteed to work for static asserts it is already very useful if the library author detected the error. I emailed Walter about it at the time, but either he missed it or is still of the opinion that instantiation traces are too verbose and confuse the programmer. While I agree that they aren't ideal, they are still a huge time saver when using and writing template libraries and should be enabled until D introduces a better way to do template error handling. In order to avoid showing too much implementation details in the error message, the compiler could make an educated guess about what part of the instantiation chain is of interest to the user. For instance, template instantiations in imported modules could be skipped (if they're private?). I didn't think about that when I added the traces, so LDC currently just prints up to six steps or all if -v is given.
Feb 02 2009
parent reply Don <nospam nospam.com> writes:
Christian Kamm wrote:
 Max Samukha wrote:
 static assert should at least print the location of the instantiating
 code or better the entire backtrace. This has been asked for several
 times.


Jarrett Billingsley Wrote:
 The code to do this is already in the frontend, DMD and it used to do
 it.  It's just been disabled.  LDC already prints template
 instantiation traces.

Yes, it wasn't hard to output a template instantiation trace when a static assert is hit. LDC produces errors like this: templatecode.d(9): Error: static assert "first arg must be numeric" instantiatied in templatecode.d(4): impldetail!(void,void[],int) instantiatied in myhugefile.d(4109): uservisible!(void) Support for these traces is not exhaustive - there is none for fatal errors, for instance - but since it's guaranteed to work for static asserts it is already very useful if the library author detected the error. I emailed Walter about it at the time, but either he missed it or is still of the opinion that instantiation traces are too verbose and confuse the programmer. While I agree that they aren't ideal, they are still a huge time saver when using and writing template libraries and should be enabled until D introduces a better way to do template error handling. In order to avoid showing too much implementation details in the error message, the compiler could make an educated guess about what part of the instantiation chain is of interest to the user. For instance, template instantiations in imported modules could be skipped (if they're private?). I didn't think about that when I added the traces, so LDC currently just prints up to six steps or all if -v is given.

Ideally, it would also detect recursive template instantiations -- only show (say) the first and the last instantiation of templates with the same name. You always want to see the initial template instantiation.
Feb 02 2009
parent Christian Kamm <kamm-incasoftware removethis.de> writes:
Christian Kamm wrote:
 In order to avoid showing too much implementation details in the error
 message, the compiler could make an educated guess about what part of the
 instantiation chain is of interest to the user. For instance, template
 instantiations in imported modules could be skipped (if they're
 private?). I didn't think about that when I added the traces, so LDC
 currently just prints up to six steps or all if -v is given.


Don wrote:
 Ideally, it would also detect recursive template instantiations -- only
 show (say) the first and the last instantiation of templates with the
 same name. You always want to see the initial template instantiation.

Yep, logic like that may keep the list of instantiations readable. Anyone interested in improving these error messages in LDC should check out this commit: http://www.dsource.org/projects/ldc/changeset/561%3Ad4e95db0e62b
Feb 02 2009
prev sibling next sibling parent Max Samukha <samukha voliacable.com.removethis> writes:
On Wed, 28 Jan 2009 11:57:43 +0100, grauzone <none example.net> wrote:

One thing about std.algorithm: you really seem to like using 
compile-time strings as literals. However, this makes the use of 
delegates harder. For example, to use a delegate, you need to do this 
(quoted from your docs):

 int[] a = ...;
 static bool greater(int a, int b)
 {
     return a > b;
 }
 sort!(greater)(a);  // predicate as alias

In my opinion, doing something like
 sort(a, (int a, int b) { return a > b; });

would be simpler and more intuitive than passing a delegate name as template parameter. (The delegate literal syntax still could be improved, though.)

D2 accepts delegate literals for alias template parameters: sort!((int a, int b) { return a > b; })(a);
Does std.algorithm work with closures at all? I see that the greater() 
function in your example is marked as static. (Sorry, I didn't test it 
myself.)

You could use a temporary: bool delegate(int, int) getGreater() { return (int a, int b){ return a > b; }; } auto pred = getGreater(); sort!(pred)(a);
Using string mixins messes up syntax highlighting and the code is more 
obfuscated. If you make an error in your predicate, random funny things 
internal to the library implementation could happen, and the compiler 
will spurt out indecipherable error messages for random modules (I guess 
in this case, std.algorithm or std.functional). How will runtime 
debugging work? Will the debugger be smart enough to point me to the 
correct source code location, if there happens a segfault in my 
predicate? I'm sure it could, if you used delegates instead.

Why did you make this so complex? What's your position on this? Do you 
agree that there are problems, or are you happy with how it is?

Why did you choose to do it like this? Because it is shorter, or for 
performance (avoid delegate call)? Does it enable some weird use cases, 
which wouldn't be possible when using delegates?

Regarding performance: I don't think performance justifies all these 
problems. Standard library functions should be as fast as possible, but 
this goal should come second after robustness and simplicity.

Another problem is, that using string mixins seems to be quite 
problematic, because they are mixed in in a different scope. If I'm not 
mistaken, you can't do this:

 int foo(...) {...}
 sort!("foo(a, b);");

You might think that "sort!("a>b", a);" is elegant and short, but this probably only works out in toy-examples. And macros, which are supposed to magically cure all those problems, were postponed to D3.0. I'm also worried about compile times. You use nested templates with string mixins, which only can be slower to compile than using e.g. the builtin .sort. I don't know if this a problem, but in my opinion, compile times are already high enough. Times will add up! For one, I'm sure that this will generate an additional gazillion of nearly useless linker symbols with very long names.

That's a good question. But I still prefer Andrei's solution over bearophile's because if I wanted to save a couple of template instantiations I could wrap the algorithms to use a delegate reference/function pointer. With bearophile's implementation, the oposite seems to be impossible.
Jan 28 2009
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
grauzone wrote:
 One thing about std.algorithm: you really seem to like using 
 compile-time strings as literals. However, this makes the use of 
 delegates harder. For example, to use a delegate, you need to do this 
 (quoted from your docs):
 
  > int[] a = ...;
  > static bool greater(int a, int b)
  > {
  >     return a > b;
  > }
  > sort!(greater)(a);  // predicate as alias
 
 In my opinion, doing something like
 
  > sort(a, (int a, int b) { return a > b; });
 
 would be simpler and more intuitive than passing a delegate name as 
 template parameter. (The delegate literal syntax still could be 
 improved, though.)

Don and Max addressed many of these points, so allow me just to add a couple of comments. The use above is valid but at the time I first implemented std.algorithm and wrote the documentation, bugs in the compiler prevented your syntax from happening. Certain bugs still disallow your syntax for certain cases; I submitted those bugs as well.
 Does std.algorithm work with closures at all? I see that the greater() 
 function in your example is marked as static. (Sorry, I didn't test it 
 myself.)

Yes, it does.
 Using string mixins messes up syntax highlighting and the code is more 
 obfuscated. If you make an error in your predicate, random funny things 
 internal to the library implementation could happen, and the compiler 
 will spurt out indecipherable error messages for random modules (I guess 
 in this case, std.algorithm or std.functional). How will runtime 
 debugging work? Will the debugger be smart enough to point me to the 
 correct source code location, if there happens a segfault in my 
 predicate? I'm sure it could, if you used delegates instead.

String mixins are meant to be used for short functions, which at least in my code there are plenty of. You can e.g. sort by a field by writing sort!("a.name < b.name")(vec) without so much as thinking about it. If you want syntax highlighting, sort!(q{a.name < b.name})(vec) may do (it does in my editor). But then again: almost by definition, if you feel like needing syntax highlighting in a string mixin, that string has outgrown its charter. Use a delegate.
 Why did you make this so complex? What's your position on this? Do you 
 agree that there are problems, or are you happy with how it is?

 Why did you choose to do it like this? Because it is shorter, or for 
 performance (avoid delegate call)? Does it enable some weird use cases, 
 which wouldn't be possible when using delegates?

(If "this" is std.algorithm, I have no idea how to make it simpler.) The thing is, passing by alias allows you a host of options: * string for short functions * function name * delegate literal * delegate object (there's a bug in the compiler related to that, that Walter knows how to fix) * some struct object that implements opCall() Really, you have *all* options and *no* disadvantage. It would have been silly to not put that straight in the standard library. I've looked at the way other languages do higher-order functions and inevitably they leave something on the table. Either you don't have enough flexibility, or the speed kills you, or the syntax kills you. Solutions that are genuinely superior are few and far apart. Going with aliases really puts D ahead of all other languages. The way D instantiates templates locally is a killer and a funny tidbit of information is that Walter put that great idea in almost by mistake, not really knowing what the consequences might be. At some point I figured how awesome that is and really pushed it through. I recall there was a discussion here - Dee Girl figured that out, too, there was a long thread about it. (Where's Dee? Where's Janice? We seem to treat our women badly.)
 Regarding performance: I don't think performance justifies all these 
 problems. Standard library functions should be as fast as possible, but 
 this goal should come second after robustness and simplicity.

I hope I can change your mind that the problem does not exist.
 Another problem is, that using string mixins seems to be quite 
 problematic, because they are mixed in in a different scope. If I'm not 
 mistaken, you can't do this:
 
  > int foo(...) {...}
  > sort!("foo(a, b);");
 
 You might think that "sort!("a>b", a);" is elegant and short, but this 
 probably only works out in toy-examples.

You can call sort!(foo)(...). I completely disagree about the toy examples assessment. In my daily work I use probably 70-80% of std.algorithm. A large percentage of time I use string mixins no problem to solve rather real problems.
 And macros, which are supposed to magically cure all those problems, 
 were postponed to D3.0.
 
 I'm also worried about compile times. You use nested templates with 
 string mixins, which only can be slower to compile than using e.g. the 
 builtin .sort. I don't know if this a problem, but in my opinion, 
 compile times are already high enough. Times will add up!
 
 For one, I'm sure that this will generate an additional gazillion of 
 nearly useless linker symbols with very long names.

I haven't perceived that as a problem yet, but indeed it's a good thing to keep one's eye on. Probably the solution I'd suggest would be improved compiler technology (a trend that Walter has relentlessly demonstrated for a good while now). Andrei
Jan 28 2009
next sibling parent reply Max Samukha <samukha voliacable.com.removethis> writes:
On Wed, 28 Jan 2009 06:01:29 -0800, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

The thing is, passing by alias allows you a host of options:

* string for short functions
* function name
* delegate literal
* delegate object (there's a bug in the compiler related to that, that 
Walter knows how to fix)

struct S { bool foo(int a, int b) { return a > b; } } sort!(&S().foo)(a); ?
* some struct object that implements opCall()

Jan 28 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Max Samukha wrote:
 On Wed, 28 Jan 2009 06:01:29 -0800, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 
 The thing is, passing by alias allows you a host of options:

 * string for short functions
 * function name
 * delegate literal
 * delegate object (there's a bug in the compiler related to that, that 
 Walter knows how to fix)

struct S { bool foo(int a, int b) { return a > b; } } sort!(&S().foo)(a); ?

That I'm not sure about. Andrei
Jan 28 2009
parent reply Max Samukha <samukha voliacable.com.removethis> writes:
On Wed, 28 Jan 2009 06:46:29 -0800, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

Max Samukha wrote:
 On Wed, 28 Jan 2009 06:01:29 -0800, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 
 The thing is, passing by alias allows you a host of options:

 * string for short functions
 * function name
 * delegate literal
 * delegate object (there's a bug in the compiler related to that, that 
 Walter knows how to fix)

struct S { bool foo(int a, int b) { return a > b; } } sort!(&S().foo)(a); ?

That I'm not sure about. Andrei

Compiler probably could create hidden locals for expressions not evaluatable at compile time and then alias those into the template? We can do that manually, but maybe the compiler could help here? Anyway, it's a petty issue.
Jan 28 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Max Samukha wrote:
 On Wed, 28 Jan 2009 06:46:29 -0800, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 
 Max Samukha wrote:
 On Wed, 28 Jan 2009 06:01:29 -0800, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 The thing is, passing by alias allows you a host of options:

 * string for short functions
 * function name
 * delegate literal
 * delegate object (there's a bug in the compiler related to that, that 
 Walter knows how to fix)

struct S { bool foo(int a, int b) { return a > b; } } sort!(&S().foo)(a); ?

Andrei

Compiler probably could create hidden locals for expressions not evaluatable at compile time and then alias those into the template? We can do that manually, but maybe the compiler could help here? Anyway, it's a petty issue.

It isn't. I do plan to push Walter for automatically creating aliases for at least certain expressions. This strategy turned out to be tremendously useful for string literals (previously you couldn't pass string literals as aliases, which doubled the number of deadbeat signatures I had to define). After all, it is silly to have to write: auto wtf = &fun; sort!(wtf)(array); because this is not allowed: sort!(&fun)(array); This is drudgery that should be taken care of automatically. Andrei
Jan 28 2009
parent Max Samukha <samukha voliacable.com.removethis> writes:
On Wed, 28 Jan 2009 09:25:05 -0800, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

Max Samukha wrote:
 On Wed, 28 Jan 2009 06:46:29 -0800, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 
 Max Samukha wrote:
 On Wed, 28 Jan 2009 06:01:29 -0800, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 The thing is, passing by alias allows you a host of options:

 * string for short functions
 * function name
 * delegate literal
 * delegate object (there's a bug in the compiler related to that, that 
 Walter knows how to fix)

struct S { bool foo(int a, int b) { return a > b; } } sort!(&S().foo)(a); ?

Andrei

Compiler probably could create hidden locals for expressions not evaluatable at compile time and then alias those into the template? We can do that manually, but maybe the compiler could help here? Anyway, it's a petty issue.

It isn't. I do plan to push Walter for automatically creating aliases for at least certain expressions. This strategy turned out to be tremendously useful for string literals (previously you couldn't pass string literals as aliases, which doubled the number of deadbeat signatures I had to define). After all, it is silly to have to write: auto wtf = &fun; sort!(wtf)(array); because this is not allowed: sort!(&fun)(array); This is drudgery that should be taken care of automatically. Andrei

That would be great!
Feb 05 2009
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:
 I hope I can change your mind that the problem does not exist.

I see. Thank you for your patience in explaining things. I'll try those things when I can. Bye, bearophile
Jan 28 2009
prev sibling parent reply Yigal Chripun <yigal100 gmail.com> writes:
Andrei Alexandrescu wrote:

[snipped where appropriate]

 String mixins are meant to be used for short functions, which at least
 in my code there are plenty of. You can e.g. sort by a field by writing
 sort!("a.name < b.name")(vec) without so much as thinking about it. If
 you want syntax highlighting, sort!(q{a.name < b.name})(vec) may do (it
 does in my editor). But then again: almost by definition, if you feel
 like needing syntax highlighting in a string mixin, that string has
 outgrown its charter. Use a delegate.

that's a good point but I don't like string mixin to be used for that. Actually, string mixins should be deprecated in favor of better tools. IIRC, ada has expression generics, which in D would be like: sort!(a.name < b.name)(vec) // instead of the above the difference is that it's not a string but an expression in the language itself. I want to clarify one point here - the problem with this for IDEs (compared to text editors) is not highlighting, this is merely a symptom. Unlike a text editor, an IDE understands the code (it works on the AST level) and therefore the type of the above is a string and is treated as such - it's not treated as the AST representation of the expression.
 (If "this" is std.algorithm, I have no idea how to make it simpler.) The
 thing is, passing by alias allows you a host of options:

 * string for short functions
 * function name
 * delegate literal
 * delegate object (there's a bug in the compiler related to that, that
 Walter knows how to fix)
 * some struct object that implements opCall()

 Really, you have *all* options and *no* disadvantage. It would have been
 silly to not put that straight in the standard library. I've looked at
 the way other languages do higher-order functions and inevitably they
 leave something on the table. Either you don't have enough flexibility,
 or the speed kills you, or the syntax kills you. Solutions that are
 genuinely superior are few and far apart. Going with aliases really puts
 D ahead of all other languages.

 The way D instantiates templates locally is a killer and a funny tidbit
 of information is that Walter put that great idea in almost by mistake,
 not really knowing what the consequences might be. At some point I
 figured how awesome that is and really pushed it through. I recall there
 was a discussion here - Dee Girl figured that out, too, there was a long
 thread about it. (Where's Dee? Where's Janice? We seem to treat our
 women badly.)

you forget that Dee girl doesn't exist.
 For one, I'm sure that this will generate an additional gazillion of
 nearly useless linker symbols with very long names.

I haven't perceived that as a problem yet, but indeed it's a good thing to keep one's eye on. Probably the solution I'd suggest would be improved compiler technology (a trend that Walter has relentlessly demonstrated for a good while now). Andrei

I too prefer this implementation and agree with all the reasons already given, But I agree with the original poster from an interface POV. I'd want ideally to have: vec.sort(a.name < b.name); instead of the above. for this to happen we need several things: 1) a.foo(b, c, ...) == foo(a, b, c, ...) 2) instead of template syntax, use regular function syntax 3) to make it compile-time this needs to be an AST macro instead of a template 4) AST macro's accept expressions of course. string mixins are obsolete. 5) struct interfaces about aliases in D: Ruby (and other languages) have a Symbol type. D aliases are similar (but compile time only). I think D would benefit from having something similar, this will be a more general way and less a special case in the language. similar to this is also having Type type. keep on the good work, and keep pushing Walter to fix those bugs you mentioned.
Jan 28 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Yigal Chripun wrote:
 that's a good point but I don't like string mixin to be used for that. 
 Actually, string mixins should be deprecated in favor of better tools.
 IIRC, ada has expression generics, which in D would be like:
 sort!(a.name < b.name)(vec) // instead of the above
 the difference is that it's not a string but an expression in the 
 language itself.

Where would tbe names a and b be looked at? Andrei
Jan 28 2009
parent Yigal Chripun <yigal100 gmail.com> writes:
Andrei Alexandrescu wrote:
 Yigal Chripun wrote:
 that's a good point but I don't like string mixin to be used for that.
 Actually, string mixins should be deprecated in favor of better tools.
 IIRC, ada has expression generics, which in D would be like:
 sort!(a.name < b.name)(vec) // instead of the above
 the difference is that it's not a string but an expression in the
 language itself.

Where would tbe names a and b be looked at? Andrei

inside the macro scope.
Jan 30 2009
prev sibling parent Don <nospam nospam.com> writes:
Yigal Chripun wrote:
 Andrei Alexandrescu wrote:
 
 [snipped where appropriate]
 
 String mixins are meant to be used for short functions, which at least
 in my code there are plenty of. You can e.g. sort by a field by writing
 sort!("a.name < b.name")(vec) without so much as thinking about it. If
 you want syntax highlighting, sort!(q{a.name < b.name})(vec) may do (it
 does in my editor). But then again: almost by definition, if you feel
 like needing syntax highlighting in a string mixin, that string has
 outgrown its charter. Use a delegate.

that's a good point but I don't like string mixin to be used for that. Actually, string mixins should be deprecated in favor of better tools. IIRC, ada has expression generics, which in D would be like: sort!(a.name < b.name)(vec) // instead of the above the difference is that it's not a string but an expression in the language itself.

And you can't do nearly as much with it.
 I want to clarify one point here - the problem with this for IDEs 
 (compared to text editors) is not highlighting, this is merely a 
 symptom. Unlike a text editor,  an IDE understands the code (it works on 
 the AST level) and therefore the type of the above is a string and is 
 treated as such - it's not treated as the AST representation of the 
 expression.
 

 4) AST macro's accept expressions of course. string mixins are obsolete.

I don't believe that an AST macro is ever going to be able to reproduce the composition power of string mixins. But I agree that we'd like to remove strings from public interfaces.
Jan 29 2009
prev sibling next sibling parent "Simen Kjaeraas" <simen.kjaras gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:

 My dlibs (for D1)

As has been mentioned in earlier threads, please supply a link when mentioning these (http://www.fantascienza.net/leonardo/so/). Having to search feels rather unnecessary. -- Simen
Jan 28 2009
prev sibling next sibling parent Sean Kelly <sean invisibleduck.org> writes:
== Quote from grauzone (none example.net)'s article
 One thing about std.algorithm: you really seem to like using
 compile-time strings as literals. However, this makes the use of
 delegates harder. For example, to use a delegate, you need to do this
 (quoted from your docs):
  > int[] a = ...;
  > static bool greater(int a, int b)
  > {
  >     return a > b;
  > }
  > sort!(greater)(a);  // predicate as alias
 In my opinion, doing something like
  > sort(a, (int a, int b) { return a > b; });
 would be simpler and more intuitive than passing a delegate name as
 template parameter. (The delegate literal syntax still could be
 improved, though.)

One issue with delegates is that they don't work in compile-time code. I found a way around this in Tango by using structs with opApply, but it still tosses out the ability to use delegate literals for predicates, which is kind of annoying. Another issue is that delegates are currently much slower than using the alias approach because DMD doesn't inline delegates, even when it theoretically could. I'd considered the idea of providing overloads in tango.core.Array which allow the alias approach to be used, but D1 support for this just wasn't there the last time I looked into it. Also, this would work by converting the aliases to delegates, which isn't ideal from a performance perspective. In short, if the target is D2 then I think the alias approach is the correct one. Delegates are more portable across versions, but I don't think they offer much over aliases in terms of functionality.
 Another problem is, that using string mixins seems to be quite
 problematic, because they are mixed in in a different scope. If I'm not
 mistaken, you can't do this:
  > int foo(...) {...}
  > sort!("foo(a, b);");
 You might think that "sort!("a>b", a);" is elegant and short, but this
 probably only works out in toy-examples.

I'm pretty sure that nested functions can be aliased in D2 (and perhaps in D1 now as well). This may not be quite as succinct as using delegate literals, but I wouldn't use delegate literals for complex comparisons anyway. Sean
Jan 28 2009
prev sibling next sibling parent Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Thu, Jan 29, 2009 at 6:29 AM, Daniel Keep
<daniel.keep.lists gmail.com> wrote:
 In any case, if the name is too long to fit within the limits of OMF, I
 believe D deflate-compresses the symbol to shorten it.

And if _that_ doesn't work, DMD then MD5 hashes the symbol, in which case you lose the info, unless it stores that in a separate object section. Unfortunately, while this mechanism solves the "symbol too long" errors, OPTLINK still crashes with too many fixups in one object, making things like Pyd all but unusable with DMDWin..
Jan 29 2009
prev sibling parent Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Sun, Feb 1, 2009 at 4:01 AM, Max Samukha
<samukha voliacable.com.removethis> wrote:
 static assert should at least print the location of the instantiating
 code or better the entire backtrace. This has been asked for several
 times.

The code to do this is already in the frontend, DMD and it used to do it. It's just been disabled. LDC already prints template instantiation traces.
Feb 01 2009
prev sibling next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 I've worked valiantly on defining the range infrastructure and making
 std.algorithm work with it. I have to say that I'm even more pleased
 with the result than I'd ever expected when I started. Ranges and
 concepts really make for beautiful code, and I am sure pretty darn
 efficient too.
 There's a lot to sink one's teeth in, but unfortunately the code hinges
 on a compiler fix that Walter was kind enough to send me privately. I
 did document the work, but the documentation doesn't really make justice
 to the extraordinary possibilities that lay ahead of us. Anyhow, here's
 a sneak preview into the up-and-coming ranges and their algorithms.
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html
 Ranges are easy to define and compose efficiently. It was, however, a
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges it
 iterates on. With that, it's very easy to e.g. sort multiple arrays in
 parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. random
 iteration if all components offer it, which means that you can do crazy
 things like sorting data that sits partially in one array and partially
 in another.
 Singly-linked list ranges are in, and to my soothing I found an answer
 to the container/range dichotomy in the form of a topology policy. A
 range may or may not be able to modify the topology of the data it's
 iterating over; if it can, it's a free-standing range, much like
 built-in arrays are. If it can't, it's a limited range tied to a
 container (of which I defined none so far, but give me time) and it's
 only the container that can mess with the topology in controlled ways.
 More on that later.
 Feedback welcome.
 Andrei

Andrei, Here's a good one for std.range that I thought of and implemented this morning while waiting for some code to run. It's a random access range struct that takes another random access range and creates a strided version of it. It also has the ability to make a random access range of structs look like a random access range of one element of the struct. http://dsource.org/projects/scrapple/browser/trunk/stride/stride.d For example: uint[] foo = [0U, 1, 2, 3, 4, 5]; // Make a range of every even-indexed element of foo: auto fooEven = Strided!(uint[])(foo, 2); assert(foo[0] == 0); assert(foo[1] == 2); assert(foo[2] == 4);
Jan 28 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 I've worked valiantly on defining the range infrastructure and making
 std.algorithm work with it. I have to say that I'm even more pleased
 with the result than I'd ever expected when I started. Ranges and
 concepts really make for beautiful code, and I am sure pretty darn
 efficient too.
 There's a lot to sink one's teeth in, but unfortunately the code hinges
 on a compiler fix that Walter was kind enough to send me privately. I
 did document the work, but the documentation doesn't really make justice
 to the extraordinary possibilities that lay ahead of us. Anyhow, here's
 a sneak preview into the up-and-coming ranges and their algorithms.
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html
 Ranges are easy to define and compose efficiently. It was, however, a
 pig to get a zip(r1, r2, ...) working that can mutate back the ranges it
 iterates on. With that, it's very easy to e.g. sort multiple arrays in
 parallel. Similarly, chain(r1, r2, ...) is able to offer e.g. random
 iteration if all components offer it, which means that you can do crazy
 things like sorting data that sits partially in one array and partially
 in another.
 Singly-linked list ranges are in, and to my soothing I found an answer
 to the container/range dichotomy in the form of a topology policy. A
 range may or may not be able to modify the topology of the data it's
 iterating over; if it can, it's a free-standing range, much like
 built-in arrays are. If it can't, it's a limited range tied to a
 container (of which I defined none so far, but give me time) and it's
 only the container that can mess with the topology in controlled ways.
 More on that later.
 Feedback welcome.
 Andrei

Andrei, Here's a good one for std.range that I thought of and implemented this morning while waiting for some code to run. It's a random access range struct that takes another random access range and creates a strided version of it. It also has the ability to make a random access range of structs look like a random access range of one element of the struct. http://dsource.org/projects/scrapple/browser/trunk/stride/stride.d For example: uint[] foo = [0U, 1, 2, 3, 4, 5]; // Make a range of every even-indexed element of foo: auto fooEven = Strided!(uint[])(foo, 2); assert(foo[0] == 0); assert(foo[1] == 2); assert(foo[2] == 4);

I was working on stride just this minute. Guess I should check this group more often :o). A stride is a great way to get a good pivot into a large array when sorting. You sort the stride and then get its median. Andrei
Jan 28 2009
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 I was working on stride just this minute. Guess I should check this
 group more often :o).
 A stride is a great way to get a good pivot into a large array when
 sorting. You sort the stride and then get its median.
 Andrei

So there's still more to come? Even better. I thought that what's posted at the URL you gave was all that was planned for the initial release, and stride seemed like a very conspicuous omission.
Jan 28 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 I was working on stride just this minute. Guess I should check this
 group more often :o).
 A stride is a great way to get a good pivot into a large array when
 sorting. You sort the stride and then get its median.
 Andrei

So there's still more to come? Even better.

Oh you ain't seen nothing yet...
 I thought that what's posted at the
 URL you gave was all that was planned for the initial release, and stride
seemed
 like a very conspicuous omission.

Indeed. In contrast, Radial seems a rather exotic choice but I needed that before strides. Andrei
Jan 28 2009
prev sibling parent reply Christopher Wright <dhasenan gmail.com> writes:
Andrei Alexandrescu wrote:
 A stride is a great way to get a good pivot into a large array when 
 sorting. You sort the stride and then get its median.

I'm not so sure about that. If the array is in fact large, you're dealing with an external memory situation, and sorting the stride means you have to touch every single block of the array. If your stride is even larger than a block, you could change this, but caches are all designed around sequential access, so they'll defeat you even if you are that clever. So, using the stride of an array to find a pivot will double the amount of time it takes to sort the array in the worst case.
Jan 28 2009
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Christopher Wright wrote:
 Andrei Alexandrescu wrote:
 A stride is a great way to get a good pivot into a large array when 
 sorting. You sort the stride and then get its median.

I'm not so sure about that. If the array is in fact large, you're dealing with an external memory situation, and sorting the stride means you have to touch every single block of the array. If your stride is even larger than a block, you could change this, but caches are all designed around sequential access, so they'll defeat you even if you are that clever. So, using the stride of an array to find a pivot will double the amount of time it takes to sort the array in the worst case.

Good point. Andrei
Jan 28 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Christopher Wright wrote:
 Andrei Alexandrescu wrote:
 A stride is a great way to get a good pivot into a large array when 
 sorting. You sort the stride and then get its median.

I'm not so sure about that. If the array is in fact large, you're dealing with an external memory situation, and sorting the stride means you have to touch every single block of the array. If your stride is even larger than a block, you could change this, but caches are all designed around sequential access, so they'll defeat you even if you are that clever. So, using the stride of an array to find a pivot will double the amount of time it takes to sort the array in the worst case.

I thought about it some more and figured an exponential stride (e.g. 1, 16, 32, 64 ...) might do the trick. It's easy to compute, spans the entire array, and the number of cache blocks fetched grows with log N. Andrei
Jan 28 2009
prev sibling next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
General comment: Please, when replying, consider editing down the quoted 
text!
Jan 28 2009
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Andrei Alexandrescu" wrote
 I've worked valiantly on defining the range infrastructure and making 
 std.algorithm work with it. I have to say that I'm even more pleased with 
 the result than I'd ever expected when I started. Ranges and concepts 
 really make for beautiful code, and I am sure pretty darn efficient too.

 There's a lot to sink one's teeth in, but unfortunately the code hinges on 
 a compiler fix that Walter was kind enough to send me privately. I did 
 document the work, but the documentation doesn't really make justice to 
 the extraordinary possibilities that lay ahead of us. Anyhow, here's a 
 sneak preview into the up-and-coming ranges and their algorithms.

 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
 http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html

Andrei, It looks like you've done a lot of good work here, it gives me even more incentive to try moving to D2 :) Keep it up!
 Singly-linked list ranges are in, and to my soothing I found an answer to 
 the container/range dichotomy in the form of a topology policy. A range 
 may or may not be able to modify the topology of the data it's iterating 
 over; if it can, it's a free-standing range, much like built-in arrays 
 are. If it can't, it's a limited range tied to a container (of which I 
 defined none so far, but give me time) and it's only the container that 
 can mess with the topology in controlled ways. More on that later.

A very excellent idea! -Steve
Jan 28 2009
prev sibling next sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Thu, Jan 29, 2009 at 5:31 AM, Yigal Chripun <yigal100 gmail.com> wrote:
 Bill Baxter wrote:
 On Wed, Jan 28, 2009 at 6:07 PM, Nick Sabalausky<a a.a>  wrote:

 Isn't "tail" the standard counterpart to "head"? ("toe" just doesn't
 sound
 good)

Tail has a history of being used to mean "everything but head" in functional programming languages like Haskel and ML. So of back, last, end, tail, rear, foot, toe, it seems every one has some strike against it. back - could be mistaken for an action last - doesn't pair well with "head", and "first" sounds too much like item #1 overall end - in C++ usually means "one past the end" tail - in FP langs means "everything but head" rear - makes Walter thing unhappy thoughts toe - sounds silly, doesn't make so much sense for a range that represents a tree structure. Toe is sounding pretty ok. Actually I think the critique that it doesn't make sense for a non-linear range should be thrown out. Linearizing is the whole purpose of a range. So even if it wasn't linear before, a range effective is providing a linearized view of it. So that leaves "it sounds silly", which is a pretty weak subjective argument against. --bb

I disagree with the above reasoning. "Language X has different meaning for word Y" is not a valid argument IMO. One of D's stated goals is to break backward compatability when needed in order to get a better language design, yet we constantly keep getting back to " but in C++ ...". if people want to use a backward compatible language they already have C++ for that, and they don't need D. I for one, prefer to change when the change makes sense and brings more clarity. Yes, it'll be initially confusing for former C++ programmers, but IMO it's worth it in the long run. head/toe is not just silly, it's also non intuitive for non-English speakers. (I'd be confused by this, had i seen this for the first time) When I write D code I think in D, not any other language and I'm sure that applies to most people. making the switch to "D mode" is easier IMO than trying to remember confusing terms, just because some other language has slightly different meaning for the deafult terms. Hack, I don't even know haskel, why should I care about haskell's definitions?

If you port code from C++ or Haskell to D it will become an issue. I ported a largeish C++ library with lots of iterators and it was only natural to use the same terminology as C++ there (begin/end). If D co-opted those terms I'm not sure what I'd call the ported C++ ones to differentiate, and it would just end up being confusing to both D and C++ users. I think making it easy to port C++ code is a good goal. Not so sure about Haskell, though. D may never be functional enough for porting Haskell to make much sense.
 I already asked in a previous post - would a chinese programmer intuitivly
 think that toe is the last item in a range?

Does it really matter if it's used everywhere and consistently throughout D? It's like saying "char" is unintuitive. Yeh, it is unintuitive, but once you know it's short for "character" it's easy to remember. Surely a Chinese programmer once he learns toe is the last item will have no problem remembering what it means, given the relationship between head and toe on a person's body. --bb
Jan 28 2009
prev sibling next sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Thu, Jan 29, 2009 at 7:38 AM, Yigal Chripun <yigal100 gmail.com> wrote:
 Bill Baxter wrote:
 On Thu, Jan 29, 2009 at 5:31 AM, Yigal Chripun<yigal100 gmail.com>  wrote:
 Bill Baxter wrote:
 On Wed, Jan 28, 2009 at 6:07 PM, Nick Sabalausky<a a.a>   wrote:

 Isn't "tail" the standard counterpart to "head"? ("toe" just doesn't
 sound
 good)

Tail has a history of being used to mean "everything but head" in functional programming languages like Haskel and ML. So of back, last, end, tail, rear, foot, toe, it seems every one has some strike against it. back - could be mistaken for an action last - doesn't pair well with "head", and "first" sounds too much like item #1 overall end - in C++ usually means "one past the end" tail - in FP langs means "everything but head" rear - makes Walter thing unhappy thoughts toe - sounds silly, doesn't make so much sense for a range that represents a tree structure. Toe is sounding pretty ok. Actually I think the critique that it doesn't make sense for a non-linear range should be thrown out. Linearizing is the whole purpose of a range. So even if it wasn't linear before, a range effective is providing a linearized view of it. So that leaves "it sounds silly", which is a pretty weak subjective argument against. --bb

I disagree with the above reasoning. "Language X has different meaning for word Y" is not a valid argument IMO. One of D's stated goals is to break backward compatability when needed in order to get a better language design, yet we constantly keep getting back to " but in C++ ...". if people want to use a backward compatible language they already have C++ for that, and they don't need D. I for one, prefer to change when the change makes sense and brings more clarity. Yes, it'll be initially confusing for former C++ programmers, but IMO it's worth it in the long run. head/toe is not just silly, it's also non intuitive for non-English speakers. (I'd be confused by this, had i seen this for the first time) When I write D code I think in D, not any other language and I'm sure that applies to most people. making the switch to "D mode" is easier IMO than trying to remember confusing terms, just because some other language has slightly different meaning for the deafult terms. Hack, I don't even know haskel, why should I care about haskell's definitions?

If you port code from C++ or Haskell to D it will become an issue. I ported a largeish C++ library with lots of iterators and it was only natural to use the same terminology as C++ there (begin/end). If D co-opted those terms I'm not sure what I'd call the ported C++ ones to differentiate, and it would just end up being confusing to both D and C++ users. I think making it easy to port C++ code is a good goal. Not so sure about Haskell, though. D may never be functional enough for porting Haskell to make much sense.
 I already asked in a previous post - would a chinese programmer
 intuitivly
 think that toe is the last item in a range?

Does it really matter if it's used everywhere and consistently throughout D? It's like saying "char" is unintuitive. Yeh, it is unintuitive, but once you know it's short for "character" it's easy to remember. Surely a Chinese programmer once he learns toe is the last item will have no problem remembering what it means, given the relationship between head and toe on a person's body. --bb

I guess you completely missed my point. If we are choosing terms that are going to be used everywhere and consistently throughout D, we should pick the intuitive words for the first and last items in a range - 'first' and 'last'.

No I didn't miss your point. I don't think anyone has said anything against "last". Last is a great word, and comes with no conflicting baggage. But "first" does have baggage. It so strongly suggests that it is item #1 that it would seem odd to say .next and still be looking at the first item. That's the argument anyway. Realistically, I think there are about 5 reasonable word pairs we could choose, and all of them have something against them, but any of them would work.
 to rephrase what you've said:
 Surely a C++ programmer once he learns 'last' is the last
 item in a D range (simple, isn't it?) will have no problem remembering what
 it means.
 in other words - if a Chinese programmer can learn an unintuitive term so
 can a C++ programmer. the only difference is that with the former option we
 all get stuck with a bad name for good, while with the latter it's only a
 temporary inconvenience since [hopefully] the C++ programmer will become a D
 programmer.

"Last" is perfectly fine. It's "first" that's got issues in that pair.
 as already pointed by others [read Chad's reply] - there is no relationship
 between head and toe on a person's body, and you might as well use 'foot'.

Yep, foot would be ok too. But toe is one letter shorter.
 regarding porting code - while I agree that this can help, porting code is a
 minor and secondary objective. both C code and a subset of C++ (in D2) can
 be directly linked with D code, so porting isn't that important and isn't
 the main goal of the language. besides, your argument would apply to most
 other C-family languages - there's a lot of Java code ported to D, for
 example, so maybe we should prefer Java's semantics over the C++ ones?
 or maybe C#'s or javascript, or ..?

I just don't know what the conventions are in those other languages. If there are such pre-established conventions in those languages, I'd like to know about them and take them into consideration as well. Java at least, given it's popularity and the large opportunity for porting Java code to D (e.g. DWT). But my impression is that Java uses fairly different conventions for iterators that don't really conflict with any of the current proposals on the table. --bb
Jan 28 2009
prev sibling next sibling parent Jarrett Billingsley <jarrett.billingsley gmail.com> writes:
On Wed, Jan 28, 2009 at 6:00 PM, Joel C. Salomon <joelcsalomon gmail.com> wrote:
 Jarrett Billingsley wrote:
 I was thinking about making D ranges be to D arrays as C++ iterators
 are to C++ pointers: r[0] is head and r[$ - 1] is toe.  But that has
 problems, since you can't make an infinite range, since you can't say
 that r[0] is legal while r[$ - 1] is not.  (D also doesn't allow
 overloading $, an irritating limitation, but one that could be fixed
 in order to implement such a paradigm.)

IIRC, Python uses negative indices to iterate from the end. Or is this entirely not what is under discussion?

Not really. With the range interface the way it is now, you can make a forward-only or infinite range by leaving out the "toe" and "retreat" methods. If "head" and "toe" were merged into a single indexing operation, you wouldn't be able to do one-ended ranges like that.
Jan 28 2009
prev sibling next sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Thu, Jan 29, 2009 at 9:32 AM, Sandeep Kakarlapudi
<sandeep.iitkgpspammenot gmail.com> wrote:
 "toe" is flat out silly and such names that pollute everything.

Just curious -- do you find "head" and "tail" to be silly too? If not, what is it that makes them not silly? Is there anything more to it than just being used to them? --bb
Jan 28 2009
prev sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Thu, Jan 29, 2009 at 9:44 AM, Chad J
<gamerchad __spam.is.bad__gmail.com> wrote:
 Sandeep Kakarlapudi wrote:
 Other mistakes that still irritate quite a few:
 C++ vector vs a mathematical vector
 In real time computer graphics, using binormal inplace of the bitangent.
Curves have a binormal and surfaces have bitangents!
 No matter how many times binormal is used it still is wrong and sounds counter
intiutive!

I don't know if those are right or not, but curves having binormals and surfaces having bitangents seems inconsistent with other mathematical terminology, since curves tend to have tangents and surfaces tend to have normals.

The classic "Frenet frame" used to describe differential properties of spatial curves include a tangent, normal, and binormal. Note that with a curve in 3-space there are two independent directions which are normal to the curve. With a surface in 3D this is not the case. There are two independent directions which are tangent to the surface (which you could call tangent and bi-tangent), and a single normal. I have O'Neill's book on differential geometry, and while it mentions binormals of curves, it says nothing about binormals or bitangents for surfaces. So I think the problem is there was just a terminology vacuum that the graphics guys needed filled, and they filled it in a somewhat illogical way. --bb
Jan 28 2009