October 26, 2006
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
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
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
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
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
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
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
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
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
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