View mode: basic / threaded / horizontal-split · Log in · Help
October 03, 2002
One More Vote for 'foreach'
Now that I'm actually doing D programming, I must say that I think
"foreach" to be a nearly essential programming construct.  D's arrays
really change the way I go about things...now almost everything that
isn't structured data ends up in an array or associative array.  That
means I iterate through my arrays A LOT.  That's where foreach would be
great.

Sometimes, you want to also want to actually manipulate the array you're
"foreach"ing through, though.  It would be very nice to be able to
extract the array index of your current "foreach" variable from it.  My
thought is to add a special property, returning uint, that only applies
to variables defined by "foreach" constructs: 'foreach_index'.

   MyClass[] array;
   foreach(cur in array)
   {
       if(cur.stuff())
           printf("Index %d matched 'stuff'.\n", cur.foreach_index);
   }

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
October 03, 2002
Re: One More Vote for 'foreach'
I vote in favor of all iteration features.  STL offers foreach as an algorithm.
Walter mentioned that he is brewing ideas for STL-like iterators.

The proposed foreach corresponds to Mathematica's MapIndexed.  One of the major
reasons I use Mathematica in daily work is this sort of facility with data
arrays.  Mathematica's Map functions are one of its major benefits.  (Some
people like MATLAB / O-Matrix / Octave for similar reasons.)

I don't say that D should incorporate these features as they exist in other
languages, but only that array manipulation / iteration / indexing is a very
critical capability.  The more of it the better. It is not limited to numerical
work. It applies everywhere. Arrays are universal data structures.

Mathematica is expression-based so the Map functions all return a modified array
expression.  The language offers Scan to perform in-place array modifications.

I won't even delve into Table, Range, Array, Part, Nest, Fold, Select, Cases,
and other marvelous contraptions.  Flatten and Partition are worthy of note.
They effectively re-dimension arrays.

All this power makes me feel homesick when I'm stuck with STL.  Mathematica is
interpreted and I know not whether a compiled language can approach such
expressive power.  I do know that these features let me walk on water in
comparison to STL.  I would fall in love with D if it had them.

Mark

===============================================
?Map
"Map[f, expr] ... applies f to each element on the first level in 
expr. Map[f, expr, levelspec] applies f to parts of expr specified by 
levelspec."


?MapAll
"MapAll[f, expr] ... applies f to every subexpression in expr."


?MapAt
"MapAt[f, expr, n] applies f to the element at position n in expr. If n is 
negative, the position is counted from the end. MapAt[f, expr, {i, j, ... }] 
applies f to the part of expr at position {i, j, ... }. MapAt[f, expr, {{i1, 
j1, ... }, {i2, j2, ... }, ... }] applies f to parts of expr at several 
positions."


?MapIndexed
"MapIndexed[f, expr] applies f to the elements of expr, giving the part 
specification of each element as a second argument to f. MapIndexed[f, expr, 
levspec] applies f to all parts of expr on levels specified by levspec."


?MapThread
"MapThread[f, {{a1, a2, ... }, {b1, b2, ... }, ... }] gives {f[a1, b1, ... ], 
f[a2, b2, ... ], ... }. MapThread[f, {expr1, expr2, ... }, n] applies f to 
the parts of the expri at level n."


Level specifications

The level in an expression corresponding to a non-negative integer n is defined
to consist of parts specified by n indices. A negative level number -n
represents all parts of an expression that have depth n. The depth of an
expression, Depth[expr], is the maximum number of indices needed to specify any
part, plus one. Levels do not include heads of expressions, except with the
option setting Heads -> True. Level 0 is the whole expression. Level -1 contains
all symbols and other objects that have no subparts.

Functions with level specifications visit different subexpressions in an order
that corresponds to depth-first traversal of the expression tree, with leaves
visited before roots. The subexpressions visited have part specifications which
occur in an order which is lexicographic, except that longer sequences appear
before shorter ones.   

n = levels 1 through n
Infinity = levels 1 through Infinity
{n} = level n only
{n1,n2} = levels n1 through n2
October 03, 2002
Re: One More Vote for 'foreach'
Definitely some kind of foreach is crucial.

Maybe a more pointer-like syntax.  Or a more for-like syntax.

What we want is the equivalent of

for (uint i=0; i<a.size; ++i) expr(a[i]);

where expr is any functional expression which can make any use of the
supplied a[i] that it wants.  a and b are arrays, i and j are index
pointers.

Clean that up and make the index automatic.  Note that inside expr, i refers
to a[i]

for (i in a) i = sqrt(i-a);

Clean.  But take that up a notch to:

for (i in a,b) a[i] = sqrt(b[i]);

Tangled, back into explicit indexing.

Something explicitly parallel can have no knowledge of any other unit of
work done to any other part of the array.  If it does you have filters or
data moves.  But those are usually highly sensitive to the order you
traverse.

However lots of stuff doesn't care what order you do it in.

So there are several kinds of foreach, either unordered, forward, or
backward

We also want to be able to represent multidimensional foreach like so:

for (i in a,c[*][])
   for (j in b,c[][*])

So that's a pretty complicated problem, how to turn for into something
that'll handle anything either forward or backward, any range or subslice,
in and across any number of dimensions.  That's going to be interesting to
see.

What would it look like?

for (a[i], b[j], out c[i][j])
   c[i][j] = a[i] * b[j];

I don't know why I threw the out in there.  Maybe that makes sense.  Maybe
it doesn't.  Anyway I think I'm getting off track.

for (i,j)
   c[i][j] = a[i] * b[j];

That's what we want, I think.

For loop variables with no type or range use the capacity of the array[s]
they're used to index within the controlled expression.  For these type of
for loops, the control index variables must be used as array indices within
the controlled expression.

What about direction?

An upward memory move:

for (i++)
   a[i] = a[i-1]; // oops.. range access violation!!!

Ok maybe a safer one:

for (i : a.size-1 to 1)
   a[i] = a[i-1];

Syntax design is hard.  I should probably start with the semantics.  ;)

But you get the idea.  Something as powerful as for, just easier to use.
For the cases where you wouldn't need to fill in all the blanks in a normal
for statement, or would use a standard pattern such as

for (uint i=0; i<a.size; ++i) expr(a[i]);

or

for (int i = a.size; --i >= 0; ) expr(a[i]);

or STL's way:

for (a[].type* p = a[0], e = a[a.size]; p < e; ++p) expr(*p);

We want D's pattern for this to be MUCH more elegant.

And a way to concisely write a multidimensional matrix operation would be
nice.  Vector and matrix operations.

template(int x)
{
   float inner(float[x] a, float[x] b)
   {
       float f = 0;
       for (i : 0 .. x-1)
           f += a[i] * b[i];
       return f;
   }
   void outer(out float[x][x] c, float[x] a, float[x] b)
   {
       for (i,j)
           c[i][j] = a[i] * b[j];
   }
}

Why do we have to use indexes at all in the expression why can't we just
name the iterating dimensions?

for (a[i],b[j],c[i][j])
   c = a * b;

I guess dimensions used more than once have to match in size.  Being able to
quickly construct an array that's got compatible dimensions with some other
array might be a nice feature.

Most out-of-bounds array accesses could be caught at compile time with a
nice enough for construct, one that knew the sizes of everything used and
could choose the ones with the smallest constraints on the resulting range.

int a[2], b[3];
for (i) a[i] = b[i]; // should this be an error, or should it use a's
smaller range?

Maybe one of those syntactic experiments will gel with somebody.  ;)

Sean

"Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message
news:3D9BC26F.C26DBE8E@deming-os.org...
> Now that I'm actually doing D programming, I must say that I think
> "foreach" to be a nearly essential programming construct.  D's arrays
> really change the way I go about things...now almost everything that
> isn't structured data ends up in an array or associative array.  That
> means I iterate through my arrays A LOT.  That's where foreach would be
> great.
>
> Sometimes, you want to also want to actually manipulate the array you're
> "foreach"ing through, though.  It would be very nice to be able to
> extract the array index of your current "foreach" variable from it.  My
> thought is to add a special property, returning uint, that only applies
> to variables defined by "foreach" constructs: 'foreach_index'.
>
>     MyClass[] array;
>     foreach(cur in array)
>     {
>         if(cur.stuff())
>             printf("Index %d matched 'stuff'.\n", cur.foreach_index);
>     }
>
> --
> The Villagers are Online! http://villagersonline.com
>
> .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
> .[ (a version.of(English).(precise.more)) is(possible) ]
> ?[ you want.to(help(develop(it))) ]
October 03, 2002
Re: One More Vote for 'foreach'
I'll second or third or n-th this suggestion.  Sean's ideas about syntax 
are interesting, but I'm not sure that I would vote for any particular 
one.  There needs to be something, and for what I would be using it for, 
a simple foreach that addressed directionality of access in some way 
would be sufficient.  Hashes would be harder, especially when it comes 
to performance.  I'm most comfortable with the perl idiom of pulling out 
a list of keys (with the option of sorting it in some arbitrary manner) 
and then iterating through that to get at the values of the hash, but I 
know that it's dog slow, so if that knid of thing even makes it into the 
language, I wouldn't want it to be the default, by any means.  For the 
records, I'm a game developer, so I fall in the middle of the road in 
terms of the coding speed vs. performance debate, perhaps tipped a 
little towards performance.

Evan



Russ Lewis wrote:
> Now that I'm actually doing D programming, I must say that I think
> "foreach" to be a nearly essential programming construct.  D's arrays
> really change the way I go about things...now almost everything that
> isn't structured data ends up in an array or associative array.  That
> means I iterate through my arrays A LOT.  That's where foreach would be
> great.
> 
> Sometimes, you want to also want to actually manipulate the array you're
> "foreach"ing through, though.  It would be very nice to be able to
> extract the array index of your current "foreach" variable from it.  My
> thought is to add a special property, returning uint, that only applies
> to variables defined by "foreach" constructs: 'foreach_index'.
> 
>     MyClass[] array;
>     foreach(cur in array)
>     {
>         if(cur.stuff())
>             printf("Index %d matched 'stuff'.\n", cur.foreach_index);
>     }
October 04, 2002
Re: One More Vote for 'foreach'
"Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message
news:3D9BC26F.C26DBE8E@deming-os.org...
> Now that I'm actually doing D programming, I must say that I think
> "foreach" to be a nearly essential programming construct.  D's arrays
> really change the way I go about things...now almost everything that
> isn't structured data ends up in an array or associative array.  That
> means I iterate through my arrays A LOT.  That's where foreach would be
> great.

I think you're right. I've been thinking about adding it in. I was thinking
along the lines of:

   foo a[];    // foo is some type
   foo v;

   for (v in a)
   {
       .. do something with v ..
   }

Initially, 'a' could be arrays only. Later, 'a' could be a class that
supports an Iterator interface. If 'a' has an order, the values are returned
in that order, otherwise the order is unspecified (regular arrays have an
order, associative arrays do not). It would be illegal to add or remove
objects from 'a' within the loop.


> Sometimes, you want to also want to actually manipulate the array you're
> "foreach"ing through, though.  It would be very nice to be able to
> extract the array index of your current "foreach" variable from it.  My
> thought is to add a special property, returning uint, that only applies
> to variables defined by "foreach" constructs: 'foreach_index'.
>
>     MyClass[] array;
>     foreach(cur in array)
>     {
>         if(cur.stuff())
>             printf("Index %d matched 'stuff'.\n", cur.foreach_index);
>     }

I think that if you're using foreach, you shouldn't be dependent on the
order or on the particular lookup mechanism of the array/collection/whatever
being looped on.
October 04, 2002
Re: One More Vote for 'foreach'
>I think that if you're using foreach, you shouldn't be dependent on the
>order or on the particular lookup mechanism of the array/collection/whatever
>being looped on.

Walter - sometimes the index itself is an encoded piece of information, and has
utility as such.  I use such a trick in Mathematica and in C all the time.

Mark
October 04, 2002
Re: One More Vote for 'foreach'
Walter wrote:
> 
> I think that if you're using foreach, you shouldn't be dependent on the
> order or on the particular lookup mechanism of the array/collection/whatever
> being looped on.
>

Not a terribly experience programmer, but:

A lot of people seem to place significance on the ordering of the index 
of an associative array.  My example is the common Perl code
foreach $foo (sort keys %aHash ) { ... }

But maybe Perl features aren't what people are looking for in D.

Chris
October 04, 2002
Re: One More Vote for 'foreach'
"Mark Evans" <Mark_member@pathlink.com> wrote in message
news:aniroq$26ea$1@digitaldaemon.com...
> >I think that if you're using foreach, you shouldn't be dependent on the
> >order or on the particular lookup mechanism of the
array/collection/whatever
> >being looped on.
> Walter - sometimes the index itself is an encoded piece of information,
and has
> utility as such.  I use such a trick in Mathematica and in C all the time.

Yes, I agree, but I suggest that using a regular for loop would be more
appropriate for that purpose. I have a good reason for saying that. Many
people transform loops like:

   for (int i = 0; i < a.length; i++)
       v = a[i];
       ...

into:

   foo *pmax = &a[a.length];
   for (foo *p = &a[0]; p < pmax; p++)
       v = *p;
       ...

for runtime efficiency purposes. There is no index used (yes you can derive
one from (p - &a[0])). Using the foreach instead:

   for (v in a)
       ...

means that the compiler can select the optimal loop traversal algorithm
based on the target machine. Requiring it to produce an index means that
people will go back to the ugly pointer optimization loop. Note that the
pointer optimization version loses all array bounds checking help. Note also
that the foreach version *does not need to do* array bounds checking in the
loop body!
October 04, 2002
Re: One More Vote for 'foreach'
"Chris" <cl@nopressedmeat.tinfoilhat.ca> wrote in message
news:3D9D39D6.2040400@nopressedmeat.tinfoilhat.ca...
> Walter wrote:
> >
> > I think that if you're using foreach, you shouldn't be dependent on the
> > order or on the particular lookup mechanism of the
array/collection/whatever
> > being looped on.
> >
>
> Not a terribly experience programmer, but:
>
> A lot of people seem to place significance on the ordering of the index
> of an associative array.  My example is the common Perl code
> foreach $foo (sort keys %aHash ) { ... }
>
> But maybe Perl features aren't what people are looking for in D.
>

I think this example show exactly what is require/expected,
foreach should iterate an array forward there is not need for an assoc array
foreach
my reason is simple, this covers both cases; those who don't care and those
who do

I would like to see 'foreach' used and not 'for' reused.
foreach ( <var> in <array_expr> ) <block>

to iterate backwards you an use
foreach( item in array.reverse ) { ... }
which I assume should be quite easy for the optimiser to detect and
shortcut.

for hashtables/assoc arrays by key
foreach( item in hash.keys ) { ... } if your not bothered by order
foreach( item in hash.keys.sort ) { ... } if you are bothered by order
or by value
foreach( item in hash.values) { ... } if your not bothered by order
foreach( item in hash.values.sort ) { ... } if you are bothered by order

again the optimiser should be able to detect some (if not all) of these
conditions and rearrange them
foreach( item in hash.keys ) { ... }can be reordered such in to the order
most efficient order for the hashtable (this does not contradict my later
statement about determanism because hash table key order IS ALWAYS non
determanistic (unlike array item order)).

if you want values in key order then you'll have the below code with
`hash[item]` to get the required item.
foreach( item in hash.keys.sort ) { hash[item] ... } if you are bothered by
order

I am not a fan of language features where the compiler has a chose on how to
order things, that does not mean I disagree with instruction reordering
within basic blocks, but that the result of code should be fully
determanistic.

as an example here is some C/C++/Java code
a = 2;
if ( (c<9) || ((a = b) > 8) ) { b = 3; }

with old C compilers the value of a, if c was less than 9 was undefined, the
|| could be fully evaluated
with C++ (i belive) and Java || much only evaluate the rhs IFF the lhs is
false.

Mike.
October 04, 2002
Re: One More Vote for 'foreach'
Looks like a good way of doing this, I never though of using it with
associative arrays. Parhaps it could be multi-leveled...

foo a[][];
foo z[];
foo v;

for(v in z in a) ...

"Walter" <walter@digitalmars.com> wrote in message
news:aniqq3$25km$1@digitaldaemon.com...
>
> "Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message
> news:3D9BC26F.C26DBE8E@deming-os.org...
> > Now that I'm actually doing D programming, I must say that I think
> > "foreach" to be a nearly essential programming construct.  D's arrays
> > really change the way I go about things...now almost everything that
> > isn't structured data ends up in an array or associative array.  That
> > means I iterate through my arrays A LOT.  That's where foreach would be
> > great.
>
> I think you're right. I've been thinking about adding it in. I was
thinking
> along the lines of:
>
>     foo a[];    // foo is some type
>     foo v;
>
>     for (v in a)
>     {
>         .. do something with v ..
>     }
>
> Initially, 'a' could be arrays only. Later, 'a' could be a class that
> supports an Iterator interface. If 'a' has an order, the values are
returned
> in that order, otherwise the order is unspecified (regular arrays have an
> order, associative arrays do not). It would be illegal to add or remove
> objects from 'a' within the loop.
>
>
> > Sometimes, you want to also want to actually manipulate the array you're
> > "foreach"ing through, though.  It would be very nice to be able to
> > extract the array index of your current "foreach" variable from it.  My
> > thought is to add a special property, returning uint, that only applies
> > to variables defined by "foreach" constructs: 'foreach_index'.
> >
> >     MyClass[] array;
> >     foreach(cur in array)
> >     {
> >         if(cur.stuff())
> >             printf("Index %d matched 'stuff'.\n", cur.foreach_index);
> >     }
>
> I think that if you're using foreach, you shouldn't be dependent on the
> order or on the particular lookup mechanism of the
array/collection/whatever
> being looped on.
>
>
>
>
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home