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 reply 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
parent reply "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
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 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 reply 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
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 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 reply "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
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 parent reply 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

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
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

 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

 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

 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 parent reply 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

 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
next sibling parent reply 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)


 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

 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'.
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?
Jan 28 2009
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

 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

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?



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 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 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
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 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 reply 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
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!


 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


Ah, thanks for the explanation!
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 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 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 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


adjustHeap is used to restore the heap invariant after the value of a 
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 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 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 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.


 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


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.


 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.


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);


 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. 


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);


 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.


 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 reply 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
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 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 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
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)


Does that mean that we'll be able to do this:

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)


 Does that mean that we'll be able to do this:
 
 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)


 Does that mean that we'll be able to do this:
 
 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)


 Does that mean that we'll be able to do this:

 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.
   


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)


 Does that mean that we'll be able to do this:

 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.
   


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.
 


[snip]

 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 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 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 reply Jason House <jason.james.house gmail.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


I think algorithm signatures should not be made unnecessarily complex, and
instead rely on other utilities for complex behavior.  For example
map!("a*a")(r1,r2) can be implemented as map!("a*a")(chain(r1,r2))

I also see in the docs that the structs returned are documented, complete with
all the functions that they include.  I'd hope that we could somehow document
this stuff simpler... 

Maybe the following?
outputRangeType!(r) map!(fun)(r)

note also how accepting only one range also makes documenting the return type
easier ;)
Jan 28 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Jason House wrote:

 I think algorithm signatures should not be made unnecessarily
 complex, and instead rely on other utilities for complex behavior.
 For example map!("a*a")(r1,r2) can be implemented as
 map!("a*a")(chain(r1,r2))


Yah, good point. I'm ambivalent about that. On one hand composition is 
nice, on the other hand map is likely to be used very often so a 
shortcut is welcome. What do others think?


 I also see in the docs that the structs returned are documented,
 complete with all the functions that they include.  I'd hope that we
 could somehow document this stuff simpler...
 
 Maybe the following? outputRangeType!(r) map!(fun)(r)
 
 note also how accepting only one range also makes documenting the
 return type easier ;)


I'm waiting for that "auto" return feature to work with ddoc...


Andrei
Jan 28 2009
next sibling parent reply Jason House <jason.james.house gmail.com> writes:
Andrei Alexandrescu Wrote:


 Jason House wrote:

 I think algorithm signatures should not be made unnecessarily
 complex, and instead rely on other utilities for complex behavior.
 For example map!("a*a")(r1,r2) can be implemented as
 map!("a*a")(chain(r1,r2))


 
 Yah, good point. I'm ambivalent about that. On one hand composition is 
 nice, on the other hand map is likely to be used very often so a 
 shortcut is welcome. What do others think?


Very often with multiple ranges? I wonder how well dmd will inline/optimize
when composing simple things like that.

 


 I also see in the docs that the structs returned are documented,
 complete with all the functions that they include.  I'd hope that we
 could somehow document this stuff simpler...
 
 Maybe the following? outputRangeType!(r) map!(fun)(r)
 
 note also how accepting only one range also makes documenting the
 return type easier ;)


 
 I'm waiting for that "auto" return feature to work with ddoc...


That really has very little to do with the point I was trying to make. The
return type will conform to a certain range type, which is all I will ever want
to know as a user.
Jan 28 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Jason House wrote:

 Andrei Alexandrescu Wrote:
 

 Jason House wrote:

 I think algorithm signatures should not be made unnecessarily
 complex, and instead rely on other utilities for complex behavior.
 For example map!("a*a")(r1,r2) can be implemented as
 map!("a*a")(chain(r1,r2))


 Yah, good point. I'm ambivalent about that. On one hand composition is 
 nice, on the other hand map is likely to be used very often so a 
 shortcut is welcome. What do others think?


 
 Very often with multiple ranges? I wonder how well dmd will inline/optimize
when composing simple things like that.
 
  
 

 I also see in the docs that the structs returned are documented,
 complete with all the functions that they include.  I'd hope that we
 could somehow document this stuff simpler...

 Maybe the following? outputRangeType!(r) map!(fun)(r)

 note also how accepting only one range also makes documenting the
 return type easier ;)


 I'm waiting for that "auto" return feature to work with ddoc...


 
 That really has very little to do with the point I was trying to make. The
return type will conform to a certain range type, which is all I will ever want
to know as a user.


Oh, I see now. Well, we don't have that in D today.

Andrei
Jan 28 2009
parent Jason House <jason.james.house gmail.com> writes:
Andrei Alexandrescu Wrote:


 Jason House wrote:

 Andrei Alexandrescu Wrote:
 

 Jason House wrote: 


  
 

 I also see in the docs that the structs returned are documented,
 complete with all the functions that they include.  I'd hope that we
 could somehow document this stuff simpler...

 Maybe the following? outputRangeType!(r) map!(fun)(r)

 note also how accepting only one range also makes documenting the
 return type easier ;)


 I'm waiting for that "auto" return feature to work with ddoc...


 
 That really has very little to do with the point I was trying to make. The
return type will conform to a certain range type, which is all I will ever want
to know as a user.


 
 Oh, I see now. Well, we don't have that in D today.
 
 Andrei


When has that ever stopped the D community? :)
Jan 28 2009
prev sibling parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Andrei Alexandrescu wrote:

 Jason House wrote:

 I think algorithm signatures should not be made unnecessarily
 complex, and instead rely on other utilities for complex behavior.
 For example map!("a*a")(r1,r2) can be implemented as
 map!("a*a")(chain(r1,r2))


 
 Yah, good point. I'm ambivalent about that. On one hand composition is
 nice, on the other hand map is likely to be used very often so a
 shortcut is welcome. What do others think?


Actually, my first instinct looking at this is to assume that it should
be this:

map!("a*b")(r1,r2);

Every time I've used map, multiple sequences translated to multiple
arguments of the operation.

It's really a question of style, but I think in this case it might be
worth disallowing multiple arguments since it's not clear which
behaviour it has.

(That or change it to use the behaviour -I- expect, but that's just
being selfish :D )


 I also see in the docs that the structs returned are documented,
 complete with all the functions that they include.  I'd hope that we
 could somehow document this stuff simpler...

 Maybe the following? outputRangeType!(r) map!(fun)(r)

 note also how accepting only one range also makes documenting the
 return type easier ;)


 
 I'm waiting for that "auto" return feature to work with ddoc...


Me, I prefer cheating like a bastard...

version( DDoc )
{
    /// Stuff!  Information!  Cookies!
    RangeOf!(R) map!(Predicate)(RangeOf!(R));
}
else
{
    ReallyLongHorriblyComplex!(TemplateWithNested!(R,ThingsIn!(It))) ...
}

  -- Daniel
Jan 28 2009
parent reply Brian <digitalmars brianguertin.com> writes:
 Actually, my first instinct looking at this is to assume that it should
 be this:
 
 map!("a*b")(r1,r2);


same here, i would much prefer it to be explicit.
Jan 29 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Brian wrote:

 Actually, my first instinct looking at this is to assume that it should
 be this:

 map!("a*b")(r1,r2);


 
 same here, i would much prefer it to be explicit.


Alrighty then, I'll operate the change. I'll leave the ability to 
specify multiple functions though, that's rather verbose when expanded.

auto r = map!("a*b", "a/b")(chain(r1, r2));

returns a range of 2-tuples.


Andrei
Jan 29 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 parent reply Denis Koroskin <2korden gmail.com> writes:
dsimcha Wrote:


 == 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.


 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


 
 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?


std.range could publically import std.algorithm and std.math. This should solve
the problem without putting min/max/abs and others into global namespace.
Jan 29 2009
parent Don <nospam nospam.com> writes:
Denis Koroskin wrote:

 dsimcha Wrote:
 

 == 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.


 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


 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?


 
 std.range could publically import std.algorithm and std.math. This should
solve the problem without putting min/max/abs and others into global namespace.


Yes, but they are really general functions. IMHO, you shouldn't have to 
import std.math to do abs() of an integer. It's been a single, trivial 
asm instruction on just about every CPU ever made.
Jan 29 2009