October 26, 2006 Re: DMD 0.170 release (foreach_reverse) | ||||
---|---|---|---|---|

| ||||

Posted in reply to Tomas Lindquist Olsen | Tomas Lindquist Olsen wrote: > Seems this discussion will never end. I feel sad that Walter has to listen to this every day. Yeh, sorry about that. This one probably could have rested as it was -- the points were already made. Anyway the ultimate goal is just to try to make D the best D it can be at the end of the day. I argue my point of view, and you argue yours, and we see what holds up under scrutiny. > I for one really like foreach_reverse and IMHO the proposed alternatives seem much more hackish. It also creates a standardized syntax for reverse iteration. And it seems like you're not alone in liking it. > D is not C++! Hooray for that. --bb |

October 26, 2006 Re: DMD 0.170 release | ||||
---|---|---|---|---|

| ||||

Posted in reply to Sean Kelly | Sean Kelly wrote: > Bruno Medeiros wrote: >> >> 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 Do you have something against methods?... :p x = vector.filter( (int t){return t>5;} ); // subset of vector vector.apply( (inout int x) { x += 100;} ); // update all members -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D |

October 26, 2006 Re: DMD 0.170 release | ||||
---|---|---|---|---|

| ||||

Posted in reply to Bruno Medeiros | ```
Bruno Medeiros wrote:
> Sean Kelly wrote:
>
>> Bruno Medeiros wrote:
>>
>>>
>>> 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
>
>
> Do you have something against methods?... :p
>
> x = vector.filter( (int t){return t>5;} ); // subset of vector
> vector.apply( (inout int x) { x += 100;} ); // update all members
>
>
Looks good to me. I do have .filter implemented in CashewUtils, and might just add a .apply now that you mention it.
-- Chris Nicholson-Sauls
``` |

October 29, 2006 Re: DMD 0.170 release | ||||
---|---|---|---|---|

| ||||

Posted in reply to Sean Kelly | On Tue, 24 Oct 2006 08:42:13 -0700, Sean Kelly wrote: >> >> 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 > This is very close to the vectorization syntax http://www.all-technology.com/eigenpolls/dwishlist/index.php?it=10 x=[i in 0..length](if (vector[i]>5) return vector[i]); [i in 0..length](vector[i]+=100); maybe a slight change of notation. x=[i in 0..length]{if (vector[i]>5) return vector[i]}; [i in 0..length]{vector[i]+=100}; > 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 29, 2006 Re: DMD 0.170 release | ||||
---|---|---|---|---|

| ||||

Posted in reply to Chris Nicholson-Sauls | Chris Nicholson-Sauls wrote: > Bruno Medeiros wrote: >> Sean Kelly wrote: >> >>> Bruno Medeiros wrote: >>> >>>> >>>> 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 >> >> >> Do you have something against methods?... :p >> >> x = vector.filter( (int t){return t>5;} ); // subset of vector >> vector.apply( (inout int x) { x += 100;} ); // update all members >> >> > > Looks good to me. I do have .filter implemented in CashewUtils, and might just add a ..apply now that you mention it. > > -- Chris Nicholson-Sauls If that's so, then you should check for Oskar Linde's array utility code. He's the one I first recall talking about array (list) comprehensions in D, and he posted quite some arrays lib code with that, but unfortunately I don't know exactly which post was it, so I can't find it. -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D |

November 03, 2006 foreach vs. iterators | ||||
---|---|---|---|---|

| ||||

Posted in reply to Walter Bright | ```
Walter Bright wrote:
> Sean Kelly wrote:
>> I think I agree, but for the sake of argument, how would D handle 'find' operations on sequences that don't support opIndex? At some point, a generalizable bookmark is almost necessary for a faithful implementation of some C++ algorithms. Also, many of these algorithms also require iteration across two sequences simultaneously, which doesn't map very cleanly into foreach. Consider a substring-style find operation (std::search), for example, where both the pattern and target types do not support opIndex or opSlice. I might argue that it's a bit silly or unrealistic to desire such an operation, but the C++ algorithm library does support it.
>
> I think the target types will have to support opIndex or opSlice.
Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators.
For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N. By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N). In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets.
In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead. With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees? The complexity for such an operation would be M(log(M)) + N(log(N)).
From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used. What alternatives do we have? So far, iterator variants are all I've been able to come up with.
Sean
``` |

November 03, 2006 Re: foreach vs. iterators | ||||
---|---|---|---|---|

| ||||

Posted in reply to Sean Kelly | ```
Sean Kelly wrote:
> Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators.
>
> For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N. By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N). In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets.
>
> In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead. With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees? The complexity for such an operation would be M(log(M)) + N(log(N)).
>
> From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used. What alternatives do we have? So far, iterator variants are all I've been able to come up with.
You are correct in regards to looping across multiple aggregates simultaneously.
On the other hand, C++ iterators aren't a general substitute for opApply. For example, it is not at all easy to turn a recursive data structure (i.e. binary tree) into a linearized iterator.
``` |

November 03, 2006 Re: foreach vs. iterators | ||||
---|---|---|---|---|

| ||||

Posted in reply to Walter Bright | ```
Walter Bright wrote:
> Sean Kelly wrote:
>> Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators.
>>
>> For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N. By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N). In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets.
>>
>> In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead. With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees? The complexity for such an operation would be M(log(M)) + N(log(N)).
>>
>> From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used. What alternatives do we have? So far, iterator variants are all I've been able to come up with.
>
> You are correct in regards to looping across multiple aggregates simultaneously.
>
> On the other hand, C++ iterators aren't a general substitute for opApply. For example, it is not at all easy to turn a recursive data structure (i.e. binary tree) into a linearized iterator.
Agreed. I think both approaches have merit. I suppose I was merely hoping that foreach would work for everything.
Sean
``` |

November 03, 2006 Re: foreach vs. iterators | ||||
---|---|---|---|---|

| ||||

Posted in reply to Sean Kelly | ```
Sean Kelly wrote:
> Walter Bright wrote:
>
>> Sean Kelly wrote:
>>
>>> I think I agree, but for the sake of argument, how would D handle 'find' operations on sequences that don't support opIndex? At some point, a generalizable bookmark is almost necessary for a faithful implementation of some C++ algorithms. Also, many of these algorithms also require iteration across two sequences simultaneously, which doesn't map very cleanly into foreach. Consider a substring-style find operation (std::search), for example, where both the pattern and target types do not support opIndex or opSlice. I might argue that it's a bit silly or unrealistic to desire such an operation, but the C++ algorithm library does support it.
>>
>>
>> I think the target types will have to support opIndex or opSlice.
>
>
> Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators.
>
> For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N. By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N). In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets.
>
> In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead. With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees? The complexity for such an operation would be M(log(M)) + N(log(N)).
>
> From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used. What alternatives do we have? So far, iterator variants are all I've been able to come up with.
It would be sufficient if D had coroutines and opApply were implemented using them.
The problem is that once you call an opApply function right now, it has to run to completion. The only way I can see to have multiple opApply style iterators going simultaneously if you could truly suspend execution of one opApply temporarily and run another one for an iteration.
In other words, if you're going to use the stack and function state to store iterator state, then the only way to have multiple iterators in different states simultaneously is to be able to have multiple stacks active simultaneously, aka coroutines.
--bb
``` |

November 03, 2006 Re: foreach vs. iterators | ||||
---|---|---|---|---|

| ||||

Posted in reply to Bill Baxter | ```
Bill Baxter wrote:
> Sean Kelly wrote:
>
>> Walter Bright wrote:
>>
>>> Sean Kelly wrote:
>>>
>>>> I think I agree, but for the sake of argument, how would D handle 'find' operations on sequences that don't support opIndex? At some point, a generalizable bookmark is almost necessary for a faithful implementation of some C++ algorithms. Also, many of these algorithms also require iteration across two sequences simultaneously, which doesn't map very cleanly into foreach. Consider a substring-style find operation (std::search), for example, where both the pattern and target types do not support opIndex or opSlice. I might argue that it's a bit silly or unrealistic to desire such an operation, but the C++ algorithm library does support it.
>>>
>>>
>>>
>>> I think the target types will have to support opIndex or opSlice.
>>
>>
>>
>> Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators.
>>
>> For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N. By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N). In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets.
>>
>> In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead. With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees? The complexity for such an operation would be M(log(M)) + N(log(N)).
>>
>> From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used. What alternatives do we have? So far, iterator variants are all I've been able to come up with.
>
>
> It would be sufficient if D had coroutines and opApply were implemented using them.
>
> The problem is that once you call an opApply function right now, it has to run to completion. The only way I can see to have multiple opApply style iterators going simultaneously if you could truly suspend execution of one opApply temporarily and run another one for an iteration.
>
> In other words, if you're going to use the stack and function state to store iterator state, then the only way to have multiple iterators in different states simultaneously is to be able to have multiple stacks active simultaneously, aka coroutines.
>
> --bb
Just a thought I had. Would it be possible to emulate this behavior with delegate-as-aggregate? What I'm thinking of (and bear in mind I just rolled out of bed, so I'm at quarter-speed right now ;)) is pass foreach a "driver" delegate that then calls step iterator delegates you've provided. The driver and step iterators would be responsible for maintaining state, and would probably need a reset case (at least the iterators).
-- Chris Nicholson-Sauls
``` |