October 19, 2006
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
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
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
You're welcome!
October 23, 2006
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
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
Fixed. Thanks.
October 23, 2006
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
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
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
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Top | Discussion index | About this forum | D home