View mode: basic / threaded / horizontal-split · Log in · Help
October 26, 2006
Re: DMD 0.170 release (foreach_reverse)
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
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
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
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
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
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
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
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
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
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
10 11 12 13 14 15 16 17
Top | Discussion index | About this forum | D home