View mode: basic / threaded / horizontal-split · Log in · Help
October 19, 2006
Re: DMD 0.170 release
Sean Kelly wrote:
> Walter Bright wrote:
>> Oskar Linde wrote:
>>> One example of a generalizing addition is Tomasz' suggestion for 
>>> trailing delegates. It generalizes foreach, foreach_reverse and even 
>>> the while-loop. Such an addition would not only make libraries 
>>> simpler and more powerful.
>>
>> foreach_reverse is about as simple as one can get, from a user 
>> standpoint. It also works efficiently with arrays, which is hugely 
>> important because most of the time it will be used for arrays.
> 
> For what it's worth, I think iterative operation requirements all fall 
> into one of three categories: forward, reverse, and unordered.  Forward 
> iteration is by far the most common, so if semantic differences are 
> involved, it should obviously be the prettiest ;-)  Reverse iteration is 
> not terribly common, but it does find occasional use in search-oriented 
> algorithms.  Unordered (for lack of a better term) can be used to 
> describe any operation which has no ordering requirement and simply must 
> be applied to all elements in a sequence.
> 
> I believe it is important that the compiler be able to recognize forward 
> and reverse iteration at compile-time so optimizations may be applied. 
> After all, that's the entire point of a built-in foreach in the first 
> place.  Also, the compiler should be allowed to degenerate both forward 
> and reverse iteration to the third category, unordered, when it can 
> determine that visitation order has no impact on the operations being 
> performed.  Some criteria for this may be if the statement block does 
> not contain break, continue, or goto statements, and if all operations 
> on sequence data are commutative.  Optionally, in instances where a 
> statement block may not qualify for auto-degeneration, the user should 
> be able to specify that it should be used anyway.  This would also allow 
> user-defined types to implement unordered operations in non-trivial 
> situations.  So we have something like this:
> 
> foreach() // the default: forward iteration, compiler may degenerate
> foreach!(fwd)() // forward iteration, compiler may degenerate
> foreach!(rev)() // reverse iteration, compiler may degenerate
> foreach!(any)() // unordered: SSE ops may be used, concurrency, etc
> foreach!(fwd,strict)() // forward iteration, compiler may not degenerate
> foreach!(rev,strict)() // reverse iteration, compiler may not degenerate
> foreach!(any,strict)() // unordered, same as without strict
> 
> (the above code above isn't intended to suggest syntax so much as to 
> describe the operations and restrictions I think may eventually be useful)
> 
> Does this sound reasonable?  And can anyone suggest a cleaner syntax?
> 
> 
> Sean

Here's an idea:

  foreach(foo, aggregate) {  // Unordered, so compiler may optmize
  foreach(foo, &aggregate.iterForward) { // Ordered and strict
  foreach(foo, &aggregate.iterReverse) { // Ordered and strict

This way the strictness cannot be specified. Is it necessary? That is, 
is there a case where one wants an *ordered* iteration, but the compiler 
can optimize into an unordered (parallel) iteration? That does not seem 
to make sense.
One issue here is that one cannot specify an unordered iterator (i.e., 
an iterator for the case where the order does not matter), so it 
defaults to one only. Could there be a structure where there would be 
more than one meaningful unordered iterator?

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
October 19, 2006
Re: DMD 0.170 release
Bruno Medeiros wrote:
> 
> Here's an idea:
> 
>   foreach(foo, aggregate) {  // Unordered, so compiler may optmize
>   foreach(foo, &aggregate.iterForward) { // Ordered and strict
>   foreach(foo, &aggregate.iterReverse) { // Ordered and strict
> 
> This way the strictness cannot be specified. Is it necessary? That is, 
> is there a case where one wants an *ordered* iteration, but the compiler 
> can optimize into an unordered (parallel) iteration?

If the involved data is volatile and being monitored by another thread, 
then yes.  But in that case some sort of memory barriers would probably 
be involved and the compiler could detect those and not optimize, so I'm 
not sure.


Sean
October 20, 2006
Re: DMD 0.170 release
Walter Bright wrote:
> Added foreach_reverse, which addresses a serious shortcoming.
> 
> http://www.digitalmars.com/d/changelog.html

I've been in the middle of a move, and therefore without internet for a while, so pardon 
me for responding late, but... Thank you, thank you, thank you, for adding 
delegate-as-aggregate!  I can now send all my multi-iterator boilerplate code to /dev/null 
and do the happy joy dance.  :)  And all the other fixes, etc.

-- Chris Nicholson-Sauls
October 20, 2006
Re: DMD 0.170 release
You're welcome!
October 23, 2006
Re: DMD 0.170 release
Walter Bright wrote:
<snip>
>> So can ordinary foreach.
> 
> All you really need is if and goto!

Actually, all you really need is while.

Stewart.

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/M d- s:-@ C++@ a->--- UB@ P+ L E@ W++@ N+++ o K-@ w++@ O? M V? PS- 
PE- Y? PGP- t- 5? X? R b DI? D G e++++ h-- r-- !y
------END GEEK CODE BLOCK------

My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
October 23, 2006
Re: DMD 0.170 release (website BUG)
Walter Bright wrote:
> Added foreach_reverse, which addresses a serious shortcoming.
> 
> http://www.digitalmars.com/d/changelog.html

Missing link on:
http://www.digitalmars.com/d/phobos/std_outofmemory.html

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
October 23, 2006
Re: DMD 0.170 release (website BUG)
Fixed. Thanks.
October 23, 2006
Re: DMD 0.170 release
Bruno Medeiros wrote:
> Sean Kelly wrote:
>> Walter Bright wrote:
>>> Oskar Linde wrote:
>>>> One example of a generalizing addition is Tomasz' suggestion for 
>>>> trailing delegates. It generalizes foreach, foreach_reverse and even 
>>>> the while-loop. Such an addition would not only make libraries 
>>>> simpler and more powerful.
>>>
>>> foreach_reverse is about as simple as one can get, from a user 
>>> standpoint. It also works efficiently with arrays, which is hugely 
>>> important because most of the time it will be used for arrays.
>>
>> For what it's worth, I think iterative operation requirements all fall 
>> into one of three categories: forward, reverse, and unordered.  
>> Forward iteration is by far the most common, so if semantic 
>> differences are involved, it should obviously be the prettiest ;-)  
>> Reverse iteration is not terribly common, but it does find occasional 
>> use in search-oriented algorithms.  Unordered (for lack of a better 
>> term) can be used to describe any operation which has no ordering 
>> requirement and simply must be applied to all elements in a sequence.
>>
>> I believe it is important that the compiler be able to recognize 
>> forward and reverse iteration at compile-time so optimizations may be 
>> applied. After all, that's the entire point of a built-in foreach in 
>> the first place.  Also, the compiler should be allowed to degenerate 
>> both forward and reverse iteration to the third category, unordered, 
>> when it can determine that visitation order has no impact on the 
>> operations being performed.  Some criteria for this may be if the 
>> statement block does not contain break, continue, or goto statements, 
>> and if all operations on sequence data are commutative.  Optionally, 
>> in instances where a statement block may not qualify for 
>> auto-degeneration, the user should be able to specify that it should 
>> be used anyway.  This would also allow user-defined types to implement 
>> unordered operations in non-trivial situations.  So we have something 
>> like this:
>>
>> foreach() // the default: forward iteration, compiler may degenerate
>> foreach!(fwd)() // forward iteration, compiler may degenerate
>> foreach!(rev)() // reverse iteration, compiler may degenerate
>> foreach!(any)() // unordered: SSE ops may be used, concurrency, etc
>> foreach!(fwd,strict)() // forward iteration, compiler may not degenerate
>> foreach!(rev,strict)() // reverse iteration, compiler may not degenerate
>> foreach!(any,strict)() // unordered, same as without strict
>>
>> (the above code above isn't intended to suggest syntax so much as to 
>> describe the operations and restrictions I think may eventually be 
>> useful)
>>
>> Does this sound reasonable?  And can anyone suggest a cleaner syntax?
>>
>>
>> Sean
> 
> Here's an idea:
> 
>   foreach(foo, aggregate) {  // Unordered, so compiler may optmize
>   foreach(foo, &aggregate.iterForward) { // Ordered and strict
>   foreach(foo, &aggregate.iterReverse) { // Ordered and strict
> 
> This way the strictness cannot be specified. Is it necessary? That is, 
> is there a case where one wants an *ordered* iteration, but the compiler 
> can optimize into an unordered (parallel) iteration? That does not seem 
> to make sense.
> One issue here is that one cannot specify an unordered iterator (i.e., 
> an iterator for the case where the order does not matter), so it 
> defaults to one only. Could there be a structure where there would be 
> more than one meaningful unordered iterator?
> 

Scrap that, duh. Non-ordered 'iteration' is, kinda like you said, 
without breaks or gotos, and thus applied to all elements. So one can 
use regular functions with delegate parameters to do this 'iteration'. 
These non-ordered, complete 'iterations' are actually the 
list/collection 'comprehensions' 
(http://www.digitalmars.com/d/archives/digitalmars/D/39313.html , which 
we knew already, but didn't remember?) which are very easy to 
parallelize (think Google MapReduce). Doesn't this solve the issue, in 
quite cleaner syntax and semantics?

I gotta start opinionating less and coding more...


-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
October 24, 2006
Re: DMD 0.170 release
Bruno Medeiros wrote:
> Bruno Medeiros wrote:
>> Sean Kelly wrote:
>>> Walter Bright wrote:
>>>> Oskar Linde wrote:
>>>>> One example of a generalizing addition is Tomasz' suggestion for 
>>>>> trailing delegates. It generalizes foreach, foreach_reverse and 
>>>>> even the while-loop. Such an addition would not only make libraries 
>>>>> simpler and more powerful.
>>>>
>>>> foreach_reverse is about as simple as one can get, from a user 
>>>> standpoint. It also works efficiently with arrays, which is hugely 
>>>> important because most of the time it will be used for arrays.
>>>
>>> For what it's worth, I think iterative operation requirements all 
>>> fall into one of three categories: forward, reverse, and unordered.  
>>> Forward iteration is by far the most common, so if semantic 
>>> differences are involved, it should obviously be the prettiest ;-)  
>>> Reverse iteration is not terribly common, but it does find occasional 
>>> use in search-oriented algorithms.  Unordered (for lack of a better 
>>> term) can be used to describe any operation which has no ordering 
>>> requirement and simply must be applied to all elements in a sequence.
>>>
>>> I believe it is important that the compiler be able to recognize 
>>> forward and reverse iteration at compile-time so optimizations may be 
>>> applied. After all, that's the entire point of a built-in foreach in 
>>> the first place.  Also, the compiler should be allowed to degenerate 
>>> both forward and reverse iteration to the third category, unordered, 
>>> when it can determine that visitation order has no impact on the 
>>> operations being performed.  Some criteria for this may be if the 
>>> statement block does not contain break, continue, or goto statements, 
>>> and if all operations on sequence data are commutative.  Optionally, 
>>> in instances where a statement block may not qualify for 
>>> auto-degeneration, the user should be able to specify that it should 
>>> be used anyway.  This would also allow user-defined types to 
>>> implement unordered operations in non-trivial situations.  So we have 
>>> something like this:
>>>
>>> foreach() // the default: forward iteration, compiler may degenerate
>>> foreach!(fwd)() // forward iteration, compiler may degenerate
>>> foreach!(rev)() // reverse iteration, compiler may degenerate
>>> foreach!(any)() // unordered: SSE ops may be used, concurrency, etc
>>> foreach!(fwd,strict)() // forward iteration, compiler may not degenerate
>>> foreach!(rev,strict)() // reverse iteration, compiler may not degenerate
>>> foreach!(any,strict)() // unordered, same as without strict
>>>
>>> (the above code above isn't intended to suggest syntax so much as to 
>>> describe the operations and restrictions I think may eventually be 
>>> useful)
>>>
>>> Does this sound reasonable?  And can anyone suggest a cleaner syntax?
>>>
>>>
>>> Sean
>>
>> Here's an idea:
>>
>>   foreach(foo, aggregate) {  // Unordered, so compiler may optmize
>>   foreach(foo, &aggregate.iterForward) { // Ordered and strict
>>   foreach(foo, &aggregate.iterReverse) { // Ordered and strict
>>
>> This way the strictness cannot be specified. Is it necessary? That is, 
>> is there a case where one wants an *ordered* iteration, but the 
>> compiler can optimize into an unordered (parallel) iteration? That 
>> does not seem to make sense.
>> One issue here is that one cannot specify an unordered iterator (i.e., 
>> an iterator for the case where the order does not matter), so it 
>> defaults to one only. Could there be a structure where there would be 
>> more than one meaningful unordered iterator?
> 
> Scrap that, duh. Non-ordered 'iteration' is, kinda like you said, 
> without breaks or gotos, and thus applied to all elements. So one can 
> use regular functions with delegate parameters to do this 'iteration'. 
> These non-ordered, complete 'iterations' are actually the 
> list/collection 'comprehensions' 
> (http://www.digitalmars.com/d/archives/digitalmars/D/39313.html , which 
> we knew already, but didn't remember?) which are very easy to 
> parallelize (think Google MapReduce). Doesn't this solve the issue, in 
> quite cleaner syntax and semantics?

It's a cool idea:

x = vector[ (int t){return t>5;} ]; // subset of vector
vector[] = (inout int x) { x += 100; }; // update all members of vector

However, the second example above seems like it wouldn't work for an 
array of delegates, since this is a legal 'copy' syntax.


Sean
October 25, 2006
Re: DMD 0.170 release (website BUG)
Walter Bright wrote:
> Fixed. Thanks.

Also, (in case you haven't noticed) the dmd zips also don't have that 
html file, so the (current or future) releases will need updating too.

-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
8 9 10 11 12 13 14 15 16
Top | Discussion index | About this forum | D home