www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Can we get rid of opApply?

reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
When looking at ranges, it seems like a much better model for iteration than 
opApply.  It seems like it could be a whole replacement for opApply.  But 
when looking at the current usage of opApply, there are some holes.

foreach(i, x; range)
{
}

What exactly happens?  Do you have to return a tuple from a range with 
head()?

Also, another thing that was nice about opApply, if you had multiple ways to 
iterate over an aggregate, you simply altered your arguments to foreach. 
How can this be implemented with ranges?

class Aggregate
{
   int opApply(int delegate(ref int idx, ref int value) dg) {...}
   int opApply(int delegate(ref int value) dg) {...}
}

Aggregate A = new Aggregate;
foreach(i, ref x; A) {...}
foreach(x; A) {...}

Maybe ranges need some more functionality to do this.  I can't see how to do 
it with Tuples, as you'd have to be able to overload head() based on return 
value.  Or if a proposed opRange is supported from Aggregate (opRange is 
called if it exists, otherwise if the aggregate is a range use that, 
otherwise look for opApply), you'd have to overload the range type returned 
based on usage.

The only thing I could think of is to change head and toe to take reference 
parameters instead of using the return value, although that's ugly.  Maybe 
it could be supported in addition to returning a value?

e.g.:

struct R
{
   int head() { ...}
   void head(int *i, int *x) {...}
   void head(int *i, int **x) { ... }
}

foo(R r)
{
   foreach(x; r)
   {
   }
   foreach(i, x; r)
   {
   }
   foreach(i, ref x; r)
   {
   }
}

// foo translates to:

foo(R r)
{
   for(auto __r = r; !__r.empty(); __r.next())
   {
       auto x = __r.head();
   }
   for(auto __r = r; !__r.empty(); __r.next())
   {
       int i, x; // compiler figures out from signature of head()
       __r.head(&i, &x);
   }
   for(auto __r = r; !__r.empty(); __r.next())
   {
      int i; // compiler figures out from signature of head()
      int *__x; // only here for explanation, compiler would optimize this 
extra variable out.
      __r.head(&i, &x);
      ref int x = *__x; // ditto
   }
}

This is ugly, and requires some compiler magic, but do you see another way 
to do it?  I didn't know if "ref ref" would work, so that's why I use 
pointers instead.  Since ref is a storage class, I don't know if the 
compiler would overload anyways...

Even with all this, I still think it's prettier than opApply with the 
delegate signature :)  And probably it performs better.

-Steve
Jan 19 2009
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Steven Schveighoffer" wrote

 // foo translates to:

 foo(R r)
 {
   for(auto __r = r; !__r.empty(); __r.next())
   {
       auto x = __r.head();
   }
   for(auto __r = r; !__r.empty(); __r.next())
   {
       int i, x; // compiler figures out from signature of head()
       __r.head(&i, &x);
   }
   for(auto __r = r; !__r.empty(); __r.next())
   {
      int i; // compiler figures out from signature of head()
      int *__x; // only here for explanation, compiler would optimize this 
 extra variable out.



      __r.head(&i, &x);


Oops, that should have been:

      __r.head(&i, &__x);


      ref int x = *__x; // ditto
   }
 }
Jan 19 2009
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Steven Schveighoffer wrote:

 When looking at ranges, it seems like a much better model for iteration than 
 opApply.  It seems like it could be a whole replacement for opApply.  But 
 when looking at the current usage of opApply, there are some holes.
 
 foreach(i, x; range)
 {
 }
 
 What exactly happens?  Do you have to return a tuple from a range with 
 head()?


One possibility I'd discussed with Walter is that for the usage above, 
the compiler asks for the .key property in addition to .head. If more 
keys are specified, .key1, .key2... are required. Probably an array 
would be a nicer solution.


 Also, another thing that was nice about opApply, if you had multiple ways to 
 iterate over an aggregate, you simply altered your arguments to foreach. 
 How can this be implemented with ranges?
 
 class Aggregate
 {
    int opApply(int delegate(ref int idx, ref int value) dg) {...}
    int opApply(int delegate(ref int value) dg) {...}
 }
 
 Aggregate A = new Aggregate;
 foreach(i, ref x; A) {...}
 foreach(x; A) {...}


Keys will take care of that too. The "ref" thing will generate different 
code by taking the address of head (not sure if Walter implemented that).


 Maybe ranges need some more functionality to do this.  I can't see how to do 
 it with Tuples, as you'd have to be able to overload head() based on return 
 value.  Or if a proposed opRange is supported from Aggregate (opRange is 
 called if it exists, otherwise if the aggregate is a range use that, 
 otherwise look for opApply), you'd have to overload the range type returned 
 based on usage.


Yes, I'm afraid type deduction will be harmed with ranges.


 The only thing I could think of is to change head and toe to take reference 
 parameters instead of using the return value, although that's ugly.  Maybe 
 it could be supported in addition to returning a value?


[snip]


 This is ugly, and requires some compiler magic, but do you see another way 
 to do it?  I didn't know if "ref ref" would work, so that's why I use 
 pointers instead.  Since ref is a storage class, I don't know if the 
 compiler would overload anyways...


One simple solution to the overloading by return type would be to have 
head be a template. Then if you say:

foreach (int e; range) {}

the corresponding assignment for e will be:

int e = __r.head!(int)();

There are a few more wrinkles to fill with Botox though :o).


Andrei
Jan 19 2009
next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Andrei Alexandrescu" wrote

 Steven Schveighoffer wrote:

 When looking at ranges, it seems like a much better model for iteration 
 than opApply.  It seems like it could be a whole replacement for opApply. 
 But when looking at the current usage of opApply, there are some holes.

 foreach(i, x; range)
 {
 }

 What exactly happens?  Do you have to return a tuple from a range with 
 head()?


 One possibility I'd discussed with Walter is that for the usage above, the 
 compiler asks for the .key property in addition to .head. If more keys are 
 specified, .key1, .key2... are required.


I'd say labeling them "key" would be slightly biased.  The arguments to 
opApply might not always be considered a key.  I'd label them .head1, 
.head2, etc.

Also, how do you recreate this case:

struct S
{
   int opApply(int delegate(ref int idx, ref int v) dg) {...}
   int opApply(int delegate(ref string k, ref int v) dg) {...}
   int opApply(int delegate(ref int idx, ref string k, ref int v) dg) {...}
}

Think of S as a container that can look up values by index or by string 
(like a sorted dictionary).


 Probably an array would be a nicer solution.


I'm interested to hear what you mean by that.


 Also, another thing that was nice about opApply, if you had multiple ways 
 to iterate over an aggregate, you simply altered your arguments to 
 foreach. How can this be implemented with ranges?

 class Aggregate
 {
    int opApply(int delegate(ref int idx, ref int value) dg) {...}
    int opApply(int delegate(ref int value) dg) {...}
 }

 Aggregate A = new Aggregate;
 foreach(i, ref x; A) {...}
 foreach(x; A) {...}


 Keys will take care of that too. The "ref" thing will generate different 
 code by taking the address of head (not sure if Walter implemented that).


You mean taking the address of the return value from head?  Or using a 
delegate?  I'm not sure what you mean...  I'd be wary of performance if you 
mean take a delegate.


 Maybe ranges need some more functionality to do this.  I can't see how to 
 do it with Tuples, as you'd have to be able to overload head() based on 
 return value.  Or if a proposed opRange is supported from Aggregate 
 (opRange is called if it exists, otherwise if the aggregate is a range 
 use that, otherwise look for opApply), you'd have to overload the range 
 type returned based on usage.


 Yes, I'm afraid type deduction will be harmed with ranges.


BAD BAD BAD!  I love being able to do type deduction in foreach...  Not 
having that would be a real hard pill to swallow...


 The only thing I could think of is to change head and toe to take 
 reference parameters instead of using the return value, although that's 
 ugly.  Maybe it could be supported in addition to returning a value?


 [snip]


 This is ugly, and requires some compiler magic, but do you see another 
 way to do it?  I didn't know if "ref ref" would work, so that's why I use 
 pointers instead.  Since ref is a storage class, I don't know if the 
 compiler would overload anyways...


 One simple solution to the overloading by return type would be to have 
 head be a template. Then if you say:

 foreach (int e; range) {}

 the corresponding assignment for e will be:

 int e = __r.head!(int)();

 There are a few more wrinkles to fill with Botox though :o).


Yuck.  I'd much rather see this implemented with ref parameters.  It seems 
like a waste to have to use templates for overloading in my range struct 
when a perfectly good type system is available.  Just my opinion.

-Steve
Jan 19 2009
next sibling parent reply Chad J <gamerchad __spam.is.bad__gmail.com> writes:
Steven Schveighoffer wrote:

 "Andrei Alexandrescu" wrote=

 Yes, I'm afraid type deduction will be harmed with ranges.


 
 BAD BAD BAD!  I love being able to do type deduction in foreach...  Not 
 having that would be a real hard pill to swallow...
 


I'm going to have to butt in and agree.  That type deduction in foreach
loops is really nice.  I'd hate to see it go.
Jan 19 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Chad J wrote:

 Steven Schveighoffer wrote:

 "Andrei Alexandrescu" wrote=

 Yes, I'm afraid type deduction will be harmed with ranges.


 BAD BAD BAD!  I love being able to do type deduction in foreach...  Not 
 having that would be a real hard pill to swallow...


 
 I'm going to have to butt in and agree.  That type deduction in foreach
 loops is really nice.  I'd hate to see it go.


I agree. We need to make it come back.

Andrei
Jan 19 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Steven Schveighoffer wrote:

 "Andrei Alexandrescu" wrote

 Steven Schveighoffer wrote:

 When looking at ranges, it seems like a much better model for iteration 
 than opApply.  It seems like it could be a whole replacement for opApply. 
 But when looking at the current usage of opApply, there are some holes.

 foreach(i, x; range)
 {
 }

 What exactly happens?  Do you have to return a tuple from a range with 
 head()?


 One possibility I'd discussed with Walter is that for the usage above, the 
 compiler asks for the .key property in addition to .head. If more keys are 
 specified, .key1, .key2... are required.


 
 I'd say labeling them "key" would be slightly biased.  The arguments to 
 opApply might not always be considered a key.  I'd label them .head1, 
 .head2, etc.


I agree.


 Also, how do you recreate this case:
 
 struct S
 {
    int opApply(int delegate(ref int idx, ref int v) dg) {...}
    int opApply(int delegate(ref string k, ref int v) dg) {...}
    int opApply(int delegate(ref int idx, ref string k, ref int v) dg) {...}
 }
 
 Think of S as a container that can look up values by index or by string 
 (like a sorted dictionary).
 

 Probably an array would be a nicer solution.


 
 I'm interested to hear what you mean by that.


Just that an array would be nicer than numbered properties.


 Also, another thing that was nice about opApply, if you had multiple ways 
 to iterate over an aggregate, you simply altered your arguments to 
 foreach. How can this be implemented with ranges?

 class Aggregate
 {
    int opApply(int delegate(ref int idx, ref int value) dg) {...}
    int opApply(int delegate(ref int value) dg) {...}
 }

 Aggregate A = new Aggregate;
 foreach(i, ref x; A) {...}
 foreach(x; A) {...}


 Keys will take care of that too. The "ref" thing will generate different 
 code by taking the address of head (not sure if Walter implemented that).


 
 You mean taking the address of the return value from head?  Or using a 
 delegate?  I'm not sure what you mean...  I'd be wary of performance if you 
 mean take a delegate.


No delegate, just something like:

auto addr = &(__r.head);

then replace *addr throughout whenever the element is being used.


 Maybe ranges need some more functionality to do this.  I can't see how to 
 do it with Tuples, as you'd have to be able to overload head() based on 
 return value.  Or if a proposed opRange is supported from Aggregate 
 (opRange is called if it exists, otherwise if the aggregate is a range 
 use that, otherwise look for opApply), you'd have to overload the range 
 type returned based on usage.


 Yes, I'm afraid type deduction will be harmed with ranges.


 
 BAD BAD BAD!  I love being able to do type deduction in foreach...  Not 
 having that would be a real hard pill to swallow...


I hear ya. Please note that as far as this extension goes I'm just 
making things up as I go while juggling one one-month-old kid on one 
hand, two visiting parents on another hand, and one thesis on yet 
another hand (paper accepted today... yay!).

It would be great if you and/or others came with good proposals on how 
to make ranges work well. For now, ranges only allow one iterated object 
and one type, and I agree that that's a step backwards from opApply's 
nice behavior. So far ref parameters and tuples have been mentioned. 
Both have merit, and ref parameters have the additional advantage that 
overloading and type deduction works with them.


Andrei
Jan 19 2009
next sibling parent Jason House <jason.james.house gmail.com> writes:
Andrei Alexandrescu Wrote:


 Steven Schveighoffer wrote:

 "Andrei Alexandrescu" wrote

 Steven Schveighoffer wrote:

 When looking at ranges, it seems like a much better model for iteration 
 than opApply.  It seems like it could be a whole replacement for opApply. 
 But when looking at the current usage of opApply, there are some holes.

 foreach(i, x; range)
 {
 }

 What exactly happens?  Do you have to return a tuple from a range with 
 head()?


 One possibility I'd discussed with Walter is that for the usage above, the 
 compiler asks for the .key property in addition to .head. If more keys are 
 specified, .key1, .key2... are required.


 
 I'd say labeling them "key" would be slightly biased.  The arguments to 
 opApply might not always be considered a key.  I'd label them .head1, 
 .head2, etc.


 
 I agree.
 

 Also, how do you recreate this case:
 
 struct S
 {
    int opApply(int delegate(ref int idx, ref int v) dg) {...}
    int opApply(int delegate(ref string k, ref int v) dg) {...}
    int opApply(int delegate(ref int idx, ref string k, ref int v) dg) {...}
 }
 
 Think of S as a container that can look up values by index or by string 
 (like a sorted dictionary).
 

 Probably an array would be a nicer solution.


 
 I'm interested to hear what you mean by that.


 
 Just that an array would be nicer than numbered properties.
 

 Also, another thing that was nice about opApply, if you had multiple ways 
 to iterate over an aggregate, you simply altered your arguments to 
 foreach. How can this be implemented with ranges?

 class Aggregate
 {
    int opApply(int delegate(ref int idx, ref int value) dg) {...}
    int opApply(int delegate(ref int value) dg) {...}
 }

 Aggregate A = new Aggregate;
 foreach(i, ref x; A) {...}
 foreach(x; A) {...}


 Keys will take care of that too. The "ref" thing will generate different 
 code by taking the address of head (not sure if Walter implemented that).


 
 You mean taking the address of the return value from head?  Or using a 
 delegate?  I'm not sure what you mean...  I'd be wary of performance if you 
 mean take a delegate.


 
 No delegate, just something like:
 
 auto addr = &(__r.head);
 
 then replace *addr throughout whenever the element is being used.
 

 Maybe ranges need some more functionality to do this.  I can't see how to 
 do it with Tuples, as you'd have to be able to overload head() based on 
 return value.  Or if a proposed opRange is supported from Aggregate 
 (opRange is called if it exists, otherwise if the aggregate is a range 
 use that, otherwise look for opApply), you'd have to overload the range 
 type returned based on usage.


 Yes, I'm afraid type deduction will be harmed with ranges.


 
 BAD BAD BAD!  I love being able to do type deduction in foreach...  Not 
 having that would be a real hard pill to swallow...


 
 I hear ya. Please note that as far as this extension goes I'm just 
 making things up as I go while juggling one one-month-old kid on one 
 hand, two visiting parents on another hand, and one thesis on yet 
 another hand (paper accepted today... yay!).


Congratulations. I find that babies require at least 3 hands to preserve sanity.

 

 It would be great if you and/or others came with good proposals on how 
 to make ranges work well. For now, ranges only allow one iterated object 
 and one type, and I agree that that's a step backwards from opApply's 
 nice behavior. So far ref parameters and tuples have been mentioned. 
 Both have merit, and ref parameters have the additional advantage that 
 overloading and type deduction works with them.
 
 
 Andrei
Jan 20 2009
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Andrei Alexandrescu" wrote

 Steven Schveighoffer wrote:



 "Andrei Alexandrescu" wrote

 Probably an array would be a nicer solution.


 I'm interested to hear what you mean by that.


 Just that an array would be nicer than numbered properties.


Ah, ok.  I still would be concerned with cases where you had more than one 
key and wanted a subset.  I suppose a different struct per key combination 
would be a solution, but it would be nice if the types played into it 
somehow.


 Also, another thing that was nice about opApply, if you had multiple 
 ways to iterate over an aggregate, you simply altered your arguments to 
 foreach. How can this be implemented with ranges?

 class Aggregate
 {
    int opApply(int delegate(ref int idx, ref int value) dg) {...}
    int opApply(int delegate(ref int value) dg) {...}
 }

 Aggregate A = new Aggregate;
 foreach(i, ref x; A) {...}
 foreach(x; A) {...}


 Keys will take care of that too. The "ref" thing will generate different 
 code by taking the address of head (not sure if Walter implemented 
 that).


 You mean taking the address of the return value from head?  Or using a 
 delegate?  I'm not sure what you mean...  I'd be wary of performance if 
 you mean take a delegate.


 No delegate, just something like:

 auto addr = &(__r.head);

 then replace *addr throughout whenever the element is being used.


OK, that is what I was thinking, sounds good.


 Maybe ranges need some more functionality to do this.  I can't see how 
 to do it with Tuples, as you'd have to be able to overload head() based 
 on return value.  Or if a proposed opRange is supported from Aggregate 
 (opRange is called if it exists, otherwise if the aggregate is a range 
 use that, otherwise look for opApply), you'd have to overload the range 
 type returned based on usage.


 Yes, I'm afraid type deduction will be harmed with ranges.


 BAD BAD BAD!  I love being able to do type deduction in foreach...  Not 
 having that would be a real hard pill to swallow...


 I hear ya. Please note that as far as this extension goes I'm just making 
 things up as I go while juggling one one-month-old kid on one hand, two 
 visiting parents on another hand, and one thesis on yet another hand 
 (paper accepted today... yay!).


No worries.  My first just turned 8 months today :)  So I hear ya too. 
Congrats!


 It would be great if you and/or others came with good proposals on how to 
 make ranges work well. For now, ranges only allow one iterated object and 
 one type, and I agree that that's a step backwards from opApply's nice 
 behavior. So far ref parameters and tuples have been mentioned. Both have 
 merit, and ref parameters have the additional advantage that overloading 
 and type deduction works with them.


However, the disdavantage to ref parameters is that you cannot have a ref 
ref parameter (i.e. one where you set a ref local inside the head method). 
A double pointer is all I could come up with.

My preference is for ref parameters since that is the most straightforward 
solution, and requires less code duplication, but there would have to be 
some help from the compiler.  We probably don't want to use double-pointer 
args as that would be illegal in SafeD, perhaps we need a new type 
constructor that is like ref?  Or maybe a library solution could give us a 
double-ref, as long as the compiler optimized out the wrapper.

-Steve
Jan 20 2009
prev sibling parent Daniel Keep <daniel.keep.lists gmail.com> writes:
Andrei Alexandrescu wrote:

 Steven Schveighoffer wrote:

 When looking at ranges, it seems like a much better model for
 iteration than opApply.  It seems like it could be a whole replacement
 for opApply.  But when looking at the current usage of opApply, there
 are some holes.

 foreach(i, x; range)
 {
 }

 What exactly happens?  Do you have to return a tuple from a range with
 head()?


 
 One possibility I'd discussed with Walter is that for the usage above,
 the compiler asks for the .key property in addition to .head. If more
 keys are specified, .key1, .key2... are required. Probably an array
 would be a nicer solution.


That's a pretty ugly solution.  It also means writing more boilerplate
to support multiple values.

I still think the simplest and cleanest way of doing this is to just let
us return tuples, already!  Hell, make the compiler explode any struct
with a .tuple member, if you have to.  I'd take that.

As for arrays... last time I checked, all the elements had to be the
same type.


 Also, another thing that was nice about opApply, if you had multiple
 ways to iterate over an aggregate, you simply altered your arguments
 to foreach. How can this be implemented with ranges?

 class Aggregate
 {
    int opApply(int delegate(ref int idx, ref int value) dg) {...}
    int opApply(int delegate(ref int value) dg) {...}
 }

 Aggregate A = new Aggregate;
 foreach(i, ref x; A) {...}
 foreach(x; A) {...}


 
 Keys will take care of that too. The "ref" thing will generate different
 code by taking the address of head (not sure if Walter implemented that).


How does taking the address of head allow you to have multiple iteration
signatures?

I think there should be a solution to this, but it's not the end of the
world if there isn't.  Python manages to make do with, for example:

  dict = {}

  foreach k in dict: pass
  foreach k in dict.iterkeys(): pass
  foreach v in dict.itervalues(): pass
  foreach k,v in dict.iteritems(): pass

Of course, that requires us to think very carefully about what the
default iteration is.  Perhaps this could be helped by allowing foreach
to simply omit leading and/or trailing values in a tuple result.

That said, the above solution would make it impossible to write
something with the same functionality as the built-in AAs.


 Maybe ranges need some more functionality to do this.  I can't see how
 to do it with Tuples, as you'd have to be able to overload head()
 based on return value.  Or if a proposed opRange is supported from
 Aggregate (opRange is called if it exists, otherwise if the aggregate
 is a range use that, otherwise look for opApply), you'd have to
 overload the range type returned based on usage.


 
 Yes, I'm afraid type deduction will be harmed with ranges.


I just about exploded with this sentence, but I'm not sure I'm following
you.  To me, type deduction is this:

foreach( e ; s ) ...;

Steven's comment seems to be about having multiple iteration signatures.

Incidentally, if you ARE saying that type inference won't work with
ranges, then I'm afraid I'm going to have to take you for a scrape
'round to Dinsdale's...


 The only thing I could think of is to change head and toe to take
 reference parameters instead of using the return value, although
 that's ugly.  Maybe it could be supported in addition to returning a
 value?


 
 [snip]
 

 This is ugly, and requires some compiler magic, but do you see another
 way to do it?  I didn't know if "ref ref" would work, so that's why I
 use pointers instead.  Since ref is a storage class, I don't know if
 the compiler would overload anyways...


 
 One simple solution to the overloading by return type would be to have
 head be a template. Then if you say:
 
 foreach (int e; range) {}
 
 the corresponding assignment for e will be:
 
 int e = __r.head!(int)();
 
 There are a few more wrinkles to fill with Botox though :o).
 
 
 Andrei


How do you then know what iteration signatures something supports, then?

-- 5 minutes later --

Thinking on this a bit before posting, I've come up with the following:

struct Tuple(T...)
{
    T tuple;
}

struct Range(T...)
{
    bool empty();
    static if( T.length == 1 )
        ref T head();
    else
        ref Tuple!(T) head();
    void next();
}

class Aggregate
{
    void opRange(out Range!(int));
    void opRange(out Range!(string));
    void opRange(out Range!(int, string));
}

void main()
{
    Aggregate z;

    foreach( ref int a ; z ) ...;
    foreach( string b ; z ) ...;
    foreach( a, b ; z ) ...;
}

Assuming the following extra conditions:

* we can use "ref T head()" to allow the values to be changed,
* opRange works (obviously), and
* the compiler will try to explode any value which has a 'tuple' member
(or any other random name you happen to like; opExplode, even) that is a
tuple of values,

that looks like it might solve the above issues.  The out-param opRange
is a bit ugly, but at least it's squirreled away in an operator overload
which users won't normally be calling.

One thing I'm worried about is that we won't be able to pass out a
direct reference to internal data; even with the "ref T head()" thing,
the range struct would need to check for a modified value, then copy it
back into its proper place. [1]

  -- Daniel

[1] I'd have said "let us return tuples" again, but I suspect that's
starting to sound like a broken record at this point.  :D
Jan 19 2009
prev sibling parent reply "Denis Koroskin" <2korden gmail.com> writes:
One nice thing that opApply capable of is it can avoid heap activity by
stack-allocating data during iteration.

For example, given an array of ints, iterate over string representations of
them:

struct IntegersAsString
{
    void opAplly(int delegate(string s) dg)
    {
        char[16] temp;

        foreach (i; array) {
            int len = sprintf(temp, "%d", i);
            int result = dg(temp[0..len]);
            if (result != 0) {
                return result;
            }
        }

        return 0;
    }

    private int[] array;
}

int array = [1, 1, 2, 3, 5, 8, 13];

// no heap allocation take place
foreach (string s; IntegersAsString(array)) {
    writeln(s);
}

How would you do that with ranges?
Jan 20 2009
next sibling parent reply Max Samukha <samukha voliacable.com.removethis> writes:
On Tue, 20 Jan 2009 12:23:58 +0300, "Denis Koroskin"
<2korden gmail.com> wrote:


One nice thing that opApply capable of is it can avoid heap activity by
stack-allocating data during iteration.

For example, given an array of ints, iterate over string representations of
them:

struct IntegersAsString
{
    void opAplly(int delegate(string s) dg)
    {
        char[16] temp;

        foreach (i; array) {
            int len = sprintf(temp, "%d", i);
            int result = dg(temp[0..len]);
            if (result != 0) {
                return result;
            }
        }

        return 0;
    }

    private int[] array;
}

int array = [1, 1, 2, 3, 5, 8, 13];

// no heap allocation take place
foreach (string s; IntegersAsString(array)) {
    writeln(s);
}

How would you do that with ranges?


struct IntegersAsString
{
    private
    {
      int[] array;
      char[16] temp;
    }

    char[] head()
    {
        int len = sprintf(temp.ptr, "%d", array[0]);
        return temp[0..len];
    }

    void next()
    {
        array = array[1..$];
    }

    bool empty()
    {
        return array.length == 0;
    }
}

void main()
{
    int[] array = [1, 1, 2, 3, 5, 8, 13];

    // no heap allocation take place
    foreach (char[] s; IntegersAsString(array))
        writefln(s);
}
Jan 20 2009
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Max Samukha (samukha voliacable.com.removethis)'s article

 On Tue, 20 Jan 2009 12:23:58 +0300, "Denis Koroskin"
 <2korden gmail.com> wrote:

One nice thing that opApply capable of is it can avoid heap activity by




stack-allocating data during iteration.

For example, given an array of ints, iterate over string representations of
them:

struct IntegersAsString
{
    void opAplly(int delegate(string s) dg)
    {
        char[16] temp;

        foreach (i; array) {
            int len = sprintf(temp, "%d", i);
            int result = dg(temp[0..len]);
            if (result != 0) {
                return result;
            }
        }

        return 0;
    }

    private int[] array;
}

int array = [1, 1, 2, 3, 5, 8, 13];

// no heap allocation take place
foreach (string s; IntegersAsString(array)) {
    writeln(s);
}

How would you do that with ranges?


 struct IntegersAsString
 {
     private
     {
       int[] array;
       char[16] temp;
     }
     char[] head()
     {
         int len = sprintf(temp.ptr, "%d", array[0]);
         return temp[0..len];
     }
     void next()
     {
         array = array[1..$];
     }
     bool empty()
     {
         return array.length == 0;
     }
 }
 void main()
 {
     int[] array = [1, 1, 2, 3, 5, 8, 13];
     // no heap allocation take place
     foreach (char[] s; IntegersAsString(array))
         writefln(s);
 }


Yet another argument for some kind of opRange to syntactically sugar this up.
Jan 20 2009
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
dsimcha:

 Yet another argument for some kind of opRange to syntactically sugar this up.


Lot of people have already commented about such that, this is what I have said:

http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=82443

Bye,
bearophile
Jan 20 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:

 == Quote from Max Samukha (samukha voliacable.com.removethis)'s article

 On Tue, 20 Jan 2009 12:23:58 +0300, "Denis Koroskin"
 <2korden gmail.com> wrote:

 One nice thing that opApply capable of is it can avoid heap activity by




 stack-allocating data during iteration.

 For example, given an array of ints, iterate over string representations of
them:

 struct IntegersAsString
 {
    void opAplly(int delegate(string s) dg)
    {
        char[16] temp;

        foreach (i; array) {
            int len = sprintf(temp, "%d", i);
            int result = dg(temp[0..len]);
            if (result != 0) {
                return result;
            }
        }

        return 0;
    }

    private int[] array;
 }

 int array = [1, 1, 2, 3, 5, 8, 13];

 // no heap allocation take place
 foreach (string s; IntegersAsString(array)) {
    writeln(s);
 }

 How would you do that with ranges?


 struct IntegersAsString
 {
     private
     {
       int[] array;
       char[16] temp;
     }
     char[] head()
     {
         int len = sprintf(temp.ptr, "%d", array[0]);
         return temp[0..len];
     }
     void next()
     {
         array = array[1..$];
     }
     bool empty()
     {
         return array.length == 0;
     }
 }
 void main()
 {
     int[] array = [1, 1, 2, 3, 5, 8, 13];
     // no heap allocation take place
     foreach (char[] s; IntegersAsString(array))
         writefln(s);
 }


 
 Yet another argument for some kind of opRange to syntactically sugar this up.


Where would that be useful in this example?

Andrei
Jan 20 2009
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 dsimcha wrote:

 == Quote from Max Samukha (samukha voliacable.com.removethis)'s article

 On Tue, 20 Jan 2009 12:23:58 +0300, "Denis Koroskin"
 <2korden gmail.com> wrote:

 One nice thing that opApply capable of is it can avoid heap activity by




 stack-allocating data during iteration.

 For example, given an array of ints, iterate over string representations of








them:

 struct IntegersAsString
 {
    void opAplly(int delegate(string s) dg)
    {
        char[16] temp;

        foreach (i; array) {
            int len = sprintf(temp, "%d", i);
            int result = dg(temp[0..len]);
            if (result != 0) {
                return result;
            }
        }

        return 0;
    }

    private int[] array;
 }

 int array = [1, 1, 2, 3, 5, 8, 13];

 // no heap allocation take place
 foreach (string s; IntegersAsString(array)) {
    writeln(s);
 }

 How would you do that with ranges?


 struct IntegersAsString
 {
     private
     {
       int[] array;
       char[16] temp;
     }
     char[] head()
     {
         int len = sprintf(temp.ptr, "%d", array[0]);
         return temp[0..len];
     }
     void next()
     {
         array = array[1..$];
     }
     bool empty()
     {
         return array.length == 0;
     }
 }
 void main()
 {
     int[] array = [1, 1, 2, 3, 5, 8, 13];
     // no heap allocation take place
     foreach (char[] s; IntegersAsString(array))
         writefln(s);
 }


 Yet another argument for some kind of opRange to syntactically sugar this up.


 Where would that be useful in this example?
 Andrei


foreach(char[] s; array) vs.
foreach(char[] s; IntegersAsString(array))

I think a lot of stuff is going to need some kind of extra struct like this to
make it work.  When this is the case, it needs to be possible to have a default
iteration method that "just works."  The opDot overload, I guess, could do this,
but it's a rather blunt tool, since then you can't use opDot for other stuff and
you'd have to forward _everything_ to the opDot object.
Jan 20 2009
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:

 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 dsimcha wrote:

 == Quote from Max Samukha (samukha voliacable.com.removethis)'s article

 On Tue, 20 Jan 2009 12:23:58 +0300, "Denis Koroskin"
 <2korden gmail.com> wrote:

 One nice thing that opApply capable of is it can avoid heap activity by




 stack-allocating data during iteration.

 For example, given an array of ints, iterate over string representations of








 them:

 struct IntegersAsString
 {
    void opAplly(int delegate(string s) dg)
    {
        char[16] temp;

        foreach (i; array) {
            int len = sprintf(temp, "%d", i);
            int result = dg(temp[0..len]);
            if (result != 0) {
                return result;
            }
        }

        return 0;
    }

    private int[] array;
 }

 int array = [1, 1, 2, 3, 5, 8, 13];

 // no heap allocation take place
 foreach (string s; IntegersAsString(array)) {
    writeln(s);
 }

 How would you do that with ranges?


 struct IntegersAsString
 {
     private
     {
       int[] array;
       char[16] temp;
     }
     char[] head()
     {
         int len = sprintf(temp.ptr, "%d", array[0]);
         return temp[0..len];
     }
     void next()
     {
         array = array[1..$];
     }
     bool empty()
     {
         return array.length == 0;
     }
 }
 void main()
 {
     int[] array = [1, 1, 2, 3, 5, 8, 13];
     // no heap allocation take place
     foreach (char[] s; IntegersAsString(array))
         writefln(s);
 }


 Yet another argument for some kind of opRange to syntactically sugar this up.


 Where would that be useful in this example?
 Andrei


 
 foreach(char[] s; array) vs.
 foreach(char[] s; IntegersAsString(array))


Oh, that's not opRange helping, it's head() with parameterized return type.


 I think a lot of stuff is going to need some kind of extra struct like this to
 make it work.  When this is the case, it needs to be possible to have a default
 iteration method that "just works."  The opDot overload, I guess, could do
this,
 but it's a rather blunt tool, since then you can't use opDot for other stuff
and
 you'd have to forward _everything_ to the opDot object.


How does opDot intervene here?


Andrei
Jan 20 2009
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"dsimcha" wrote

 foreach(char[] s; array) vs.
 foreach(char[] s; IntegersAsString(array))

 I think a lot of stuff is going to need some kind of extra struct like 
 this to
 make it work.  When this is the case, it needs to be possible to have a 
 default
 iteration method that "just works."  The opDot overload, I guess, could do 
 this,
 but it's a rather blunt tool, since then you can't use opDot for other 
 stuff and
 you'd have to forward _everything_ to the opDot object.


opRange doesn't help here.  array is a (non-extendable) primitive, so the 
compiler needs to be told how to convert integers to strings.

Even opApply wouldn't get you here.

I actually think something cool would be a toRange struct:

foreach(s; toRange!(string)(array))

Which would be like the to! template.

-Steve
Jan 20 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Steven Schveighoffer wrote:

 "dsimcha" wrote

 foreach(char[] s; array) vs.
 foreach(char[] s; IntegersAsString(array))

 I think a lot of stuff is going to need some kind of extra struct like 
 this to
 make it work.  When this is the case, it needs to be possible to have a 
 default
 iteration method that "just works."  The opDot overload, I guess, could do 
 this,
 but it's a rather blunt tool, since then you can't use opDot for other 
 stuff and
 you'd have to forward _everything_ to the opDot object.


 
 opRange doesn't help here.  array is a (non-extendable) primitive, so the 
 compiler needs to be told how to convert integers to strings.
 
 Even opApply wouldn't get you here.
 
 I actually think something cool would be a toRange struct:
 
 foreach(s; toRange!(string)(array))
 
 Which would be like the to! template.
 
 -Steve 


With the new std.algorithm:

foreach (s; map!(to!string)(array)) { ... }


Andrei
Jan 20 2009
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Andrei Alexandrescu" wrote

 Steven Schveighoffer wrote:

 "dsimcha" wrote

 foreach(char[] s; array) vs.
 foreach(char[] s; IntegersAsString(array))

 I think a lot of stuff is going to need some kind of extra struct like 
 this to
 make it work.  When this is the case, it needs to be possible to have a 
 default
 iteration method that "just works."  The opDot overload, I guess, could 
 do this,
 but it's a rather blunt tool, since then you can't use opDot for other 
 stuff and
 you'd have to forward _everything_ to the opDot object.


 opRange doesn't help here.  array is a (non-extendable) primitive, so the 
 compiler needs to be told how to convert integers to strings.

 Even opApply wouldn't get you here.

 I actually think something cool would be a toRange struct:

 foreach(s; toRange!(string)(array))

 Which would be like the to! template.

 -Steve


 With the new std.algorithm:

 foreach (s; map!(to!string)(array)) { ... }


That's cool :D

-Steve
Jan 20 2009
prev sibling parent Max Samukha <samukha voliacable.com.removethis> writes:
On Tue, 20 Jan 2009 09:08:03 -0800, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:


Steven Schveighoffer wrote:

 "dsimcha" wrote

 foreach(char[] s; array) vs.
 foreach(char[] s; IntegersAsString(array))

 I think a lot of stuff is going to need some kind of extra struct like 
 this to
 make it work.  When this is the case, it needs to be possible to have a 
 default
 iteration method that "just works."  The opDot overload, I guess, could do 
 this,
 but it's a rather blunt tool, since then you can't use opDot for other 
 stuff and
 you'd have to forward _everything_ to the opDot object.


 
 opRange doesn't help here.  array is a (non-extendable) primitive, so the 
 compiler needs to be told how to convert integers to strings.
 
 Even opApply wouldn't get you here.
 
 I actually think something cool would be a toRange struct:
 
 foreach(s; toRange!(string)(array))
 
 Which would be like the to! template.
 
 -Steve 


With the new std.algorithm:

foreach (s; map!(to!string)(array)) { ... }


Andrei


I have to use an updated version of that algorithm:

1. Wake up

2. Get coffee

3. Read _all_ posts

4. Post only if necessary and think before posting
Jan 20 2009
prev sibling parent reply Max Samukha <samukha voliacable.com.removethis> writes:
On Tue, 20 Jan 2009 11:36:47 -0500, "Steven Schveighoffer"
<schveiguy yahoo.com> wrote:


"dsimcha" wrote

 foreach(char[] s; array) vs.
 foreach(char[] s; IntegersAsString(array))

 I think a lot of stuff is going to need some kind of extra struct like 
 this to
 make it work.  When this is the case, it needs to be possible to have a 
 default
 iteration method that "just works."  The opDot overload, I guess, could do 
 this,
 but it's a rather blunt tool, since then you can't use opDot for other 
 stuff and
 you'd have to forward _everything_ to the opDot object.


opRange doesn't help here.  array is a (non-extendable) primitive, so the 
compiler needs to be told how to convert integers to strings.

Even opApply wouldn't get you here.

I actually think something cool would be a toRange struct:

foreach(s; toRange!(string)(array))

Which would be like the to! template.

-Steve 


That could be easily implemented with the lazy map:

auto toRange(T, R)(R r)
{
  alias ElementType!(R) E;
  return mapLazy!((E a){ return to!(T)(a); })(r);
}

BTW, is there a way to alias a function template instantiation?
Jan 20 2009
next sibling parent reply "Jarrett Billingsley" <jarrett.billingsley gmail.com> writes:
On Tue, Jan 20, 2009 at 12:21 PM, Max Samukha
<samukha voliacable.com.removethis> wrote:

 BTW, is there a way to alias a function template instantiation?


A full instantiation can be.

alias Foo!(Bar, Baz) FooBarBaz;

A partial instantiation can't be, but you can do it using a proxy template.

template FooBar(U)
{
    alias Foo!(Bar, U) FooBar;
}
Jan 20 2009
parent reply Max Samukha <samukha voliacable.com.removethis> writes:
On Tue, 20 Jan 2009 12:30:27 -0500, "Jarrett Billingsley"
<jarrett.billingsley gmail.com> wrote:


On Tue, Jan 20, 2009 at 12:21 PM, Max Samukha
<samukha voliacable.com.removethis> wrote:

 BTW, is there a way to alias a function template instantiation?


A full instantiation can be.

alias Foo!(Bar, Baz) FooBarBaz;

A partial instantiation can't be, but you can do it using a proxy template.

template FooBar(U)
{
    alias Foo!(Bar, U) FooBar;
}


Thanks. My confusion came from 'to' being declared as

template to(Source)
{
  Target to(Target)(Target t);
}

instead of

Target to(Source, Target)(Target t)
{
}
Jan 20 2009
parent Max Samukha <samukha voliacable.com.removethis> writes:
On Wed, 21 Jan 2009 09:35:19 +0200, Max Samukha
<samukha voliacable.com.removethis> wrote:


On Tue, 20 Jan 2009 12:30:27 -0500, "Jarrett Billingsley"
<jarrett.billingsley gmail.com> wrote:


On Tue, Jan 20, 2009 at 12:21 PM, Max Samukha
<samukha voliacable.com.removethis> wrote:

 BTW, is there a way to alias a function template instantiation?


A full instantiation can be.

alias Foo!(Bar, Baz) FooBarBaz;

A partial instantiation can't be, but you can do it using a proxy template.

template FooBar(U)
{
    alias Foo!(Bar, U) FooBar;
}


Thanks. My confusion came from 'to' being declared as

template to(Source)
{
  Target to(Target)(Target t);
}


template to(Target)
{
    Target to(Source)(Source value)
    {
    }
}


instead of

Target to(Source, Target)(Target t)
{
} 


Target to(Target, Source)(Source t)
{
}
Jan 20 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Max Samukha wrote:

 On Tue, 20 Jan 2009 11:36:47 -0500, "Steven Schveighoffer"
 <schveiguy yahoo.com> wrote:
 

 "dsimcha" wrote

 foreach(char[] s; array) vs.
 foreach(char[] s; IntegersAsString(array))

 I think a lot of stuff is going to need some kind of extra struct like 
 this to
 make it work.  When this is the case, it needs to be possible to have a 
 default
 iteration method that "just works."  The opDot overload, I guess, could do 
 this,
 but it's a rather blunt tool, since then you can't use opDot for other 
 stuff and
 you'd have to forward _everything_ to the opDot object.


 opRange doesn't help here.  array is a (non-extendable) primitive, so the 
 compiler needs to be told how to convert integers to strings.

 Even opApply wouldn't get you here.

 I actually think something cool would be a toRange struct:

 foreach(s; toRange!(string)(array))

 Which would be like the to! template.

 -Steve 


 
 That could be easily implemented with the lazy map:
 
 auto toRange(T, R)(R r)
 {
   alias ElementType!(R) E;
   return mapLazy!((E a){ return to!(T)(a); })(r);
 }
 
 BTW, is there a way to alias a function template instantiation?


template toRange(T) { alias map!(to!T) toRange; }

Andrei
Jan 20 2009
parent Max Samukha <samukha voliacable.com.removethis> writes:
On Tue, 20 Jan 2009 09:32:01 -0800, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:


Max Samukha wrote:

 On Tue, 20 Jan 2009 11:36:47 -0500, "Steven Schveighoffer"
 <schveiguy yahoo.com> wrote:
 

 "dsimcha" wrote

 foreach(char[] s; array) vs.
 foreach(char[] s; IntegersAsString(array))

 I think a lot of stuff is going to need some kind of extra struct like 
 this to
 make it work.  When this is the case, it needs to be possible to have a 
 default
 iteration method that "just works."  The opDot overload, I guess, could do 
 this,
 but it's a rather blunt tool, since then you can't use opDot for other 
 stuff and
 you'd have to forward _everything_ to the opDot object.


 opRange doesn't help here.  array is a (non-extendable) primitive, so the 
 compiler needs to be told how to convert integers to strings.

 Even opApply wouldn't get you here.

 I actually think something cool would be a toRange struct:

 foreach(s; toRange!(string)(array))

 Which would be like the to! template.

 -Steve 


 
 That could be easily implemented with the lazy map:
 
 auto toRange(T, R)(R r)
 {
   alias ElementType!(R) E;
   return mapLazy!((E a){ return to!(T)(a); })(r);
 }
 
 BTW, is there a way to alias a function template instantiation?


template toRange(T) { alias map!(to!T) toRange; }

Andrei


Nice!
Jan 20 2009
prev sibling parent reply Fawzi Mohamed <fmohamed mac.com> writes:
I think that opApply should stay

1) range (iterators, whatever) hide the iteration step, this allows to 
iterate several of them in lockstep (nice)

2) opApply hides the iteration loop this allows one to make parallel 
loops (nice)

I have successfully used opApply as follow

auto a=zeros([100,100]);
foreach (ref i;a.pLoop){
  i+=4+i;
}

This can be dangerous (the loop content cannot have non synchronized 
sequential dependencies), but I find it quite nice...

So I think that both solutions have their place.

Fawzi
Jan 20 2009
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Fawzi Mohamed" wrote

I think that opApply should stay

 1) range (iterators, whatever) hide the iteration step, this allows to 
 iterate several of them in lockstep (nice)

 2) opApply hides the iteration loop this allows one to make parallel loops 
 (nice)

 I have successfully used opApply as follow

 auto a=zeros([100,100]);
 foreach (ref i;a.pLoop){
  i+=4+i;
 }

 This can be dangerous (the loop content cannot have non synchronized 
 sequential dependencies), but I find it quite nice...

 So I think that both solutions have their place.


Probably the best argument for opApply that I've seen.

The other possibly sensible reason to keep opApply is for 
interfaces/classes.  Ranges as a class would be slower than even opApply, as 
each loop iteration would call a virtual function.  However, how do you 
define an interface that says "you must define a range with these 
parameters"?

opApply makes that easy:

interface I
{
  int opApply(int delegate(ref int x));
}

With a range, you'd have some weird stuff, like a predefined range struct 
which calls virtual functions on the interface, or a range class instead of 
a struct (Yuck!)

So maybe the answer is that we keep opApply for parallelization and 
polymorphism, but use ranges for structs and compile-time parameterization.

At the very least, we can get rid of the term opApply, and just use opCall 
instead (see bugzilla issue 2498 for my thoughts on that).

-Steve
Jan 20 2009
parent reply Robert Fraser <fraserofthenight gmail.com> writes:
Steven Schveighoffer wrote:

 The other possibly sensible reason to keep opApply is for 
 interfaces/classes.  Ranges as a class would be slower than even opApply, as 
 each loop iteration would call a virtual function. 


There would only need to be one vtable lookup for each function (since 
every iteration would use the same head(), next(), etc.) So it would be 
the same price as opApply (a function pointer call). Well, 3 times the 
price, since 3 functions need to be called.
Jan 20 2009
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Robert Fraser" wrote

 Steven Schveighoffer wrote:

 The other possibly sensible reason to keep opApply is for 
 interfaces/classes.  Ranges as a class would be slower than even opApply, 
 as each loop iteration would call a virtual function.


 There would only need to be one vtable lookup for each function (since 
 every iteration would use the same head(), next(), etc.) So it would be 
 the same price as opApply (a function pointer call). Well, 3 times the 
 price, since 3 functions need to be called.


You could technically cache the vtable lookup, but a vtable call costs more 
than a delegate call (one lookup for vtable, then function + pointer call 
vs. just function + pointer call).  But besides that, yes, it would be 3 
functions called per iteration.  So still slower...

-Steve
Jan 20 2009
parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Steven Schveighoffer wrote:

 "Robert Fraser" wrote

 Steven Schveighoffer wrote:

 The other possibly sensible reason to keep opApply is for 
 interfaces/classes.  Ranges as a class would be slower than even opApply, 
 as each loop iteration would call a virtual function.


 There would only need to be one vtable lookup for each function (since 
 every iteration would use the same head(), next(), etc.) So it would be 
 the same price as opApply (a function pointer call). Well, 3 times the 
 price, since 3 functions need to be called.


 
 You could technically cache the vtable lookup, but a vtable call costs more 
 than a delegate call (one lookup for vtable, then function + pointer call 
 vs. just function + pointer call).  But besides that, yes, it would be 3 
 functions called per iteration.  So still slower...
 
 -Steve 


Add opRange and allow it to return a struct.

 -- Daniel
Jan 20 2009
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Daniel Keep" wrote

 Steven Schveighoffer wrote:

 "Robert Fraser" wrote

 Steven Schveighoffer wrote:

 The other possibly sensible reason to keep opApply is for
 interfaces/classes.  Ranges as a class would be slower than even 
 opApply,
 as each loop iteration would call a virtual function.


 There would only need to be one vtable lookup for each function (since
 every iteration would use the same head(), next(), etc.) So it would be
 the same price as opApply (a function pointer call). Well, 3 times the
 price, since 3 functions need to be called.


 You could technically cache the vtable lookup, but a vtable call costs 
 more
 than a delegate call (one lookup for vtable, then function + pointer call
 vs. just function + pointer call).  But besides that, yes, it would be 3
 functions called per iteration.  So still slower...

 -Steve


 Add opRange and allow it to return a struct.


How do you define that in an interface?  You must pre-define the struct, 
which means the struct must have implementation details before the class is 
even written.

-Steve
Jan 20 2009
parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Wed, 21 Jan 2009 01:38:50 +0300, Steven Schveighoffer <schveiguy yahoo.com>
wrote:


 "Daniel Keep" wrote

 Steven Schveighoffer wrote:

 "Robert Fraser" wrote

 Steven Schveighoffer wrote:

 The other possibly sensible reason to keep opApply is for
 interfaces/classes.  Ranges as a class would be slower than even
 opApply,
 as each loop iteration would call a virtual function.


 There would only need to be one vtable lookup for each function (since
 every iteration would use the same head(), next(), etc.) So it would  
 be
 the same price as opApply (a function pointer call). Well, 3 times the
 price, since 3 functions need to be called.


 You could technically cache the vtable lookup, but a vtable call costs
 more
 than a delegate call (one lookup for vtable, then function + pointer  
 call
 vs. just function + pointer call).  But besides that, yes, it would be  
 3
 functions called per iteration.  So still slower...

 -Steve


 Add opRange and allow it to return a struct.


 How do you define that in an interface?  You must pre-define the struct,
 which means the struct must have implementation details before the class  
 is
 even written.

 -Steve


Interface implies virtual methods. As such, you can use the following:

interface IRange(T)
{
    T head();
    bool empty();
    void next();

    IRange!(T) opRange();
}
Jan 20 2009
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Denis Koroskin" wrote

 On Wed, 21 Jan 2009 01:38:50 +0300, Steven Schveighoffer 
 <schveiguy yahoo.com> wrote:


 "Daniel Keep" wrote

 Steven Schveighoffer wrote:

 "Robert Fraser" wrote

 Steven Schveighoffer wrote:

 The other possibly sensible reason to keep opApply is for
 interfaces/classes.  Ranges as a class would be slower than even
 opApply,
 as each loop iteration would call a virtual function.


 There would only need to be one vtable lookup for each function (since
 every iteration would use the same head(), next(), etc.) So it would 
 be
 the same price as opApply (a function pointer call). Well, 3 times the
 price, since 3 functions need to be called.


 You could technically cache the vtable lookup, but a vtable call costs
 more
 than a delegate call (one lookup for vtable, then function + pointer 
 call
 vs. just function + pointer call).  But besides that, yes, it would be 
 3
 functions called per iteration.  So still slower...

 -Steve


 Add opRange and allow it to return a struct.


 How do you define that in an interface?  You must pre-define the struct,
 which means the struct must have implementation details before the class 
 is
 even written.

 -Steve


 Interface implies virtual methods. As such, you can use the following:

 interface IRange(T)
 {
    T head();
    bool empty();
    void next();

    IRange!(T) opRange();
 }


Interfaces can only be implemented by classes.  So your IRange!(T) still is 
using virtual functions for the range methods.  The performance benefit from 
ranges comes from when the range is a struct.  I think that for interfaces, 
opApply has better performance.

-Steve
Jan 20 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Max Samukha wrote:

 On Tue, 20 Jan 2009 12:23:58 +0300, "Denis Koroskin"
 <2korden gmail.com> wrote:
 

 One nice thing that opApply capable of is it can avoid heap activity by
stack-allocating data during iteration.

 For example, given an array of ints, iterate over string representations of
them:

 struct IntegersAsString
 {
    void opAplly(int delegate(string s) dg)
    {
        char[16] temp;

        foreach (i; array) {
            int len = sprintf(temp, "%d", i);
            int result = dg(temp[0..len]);
            if (result != 0) {
                return result;
            }
        }

        return 0;
    }

    private int[] array;
 }

 int array = [1, 1, 2, 3, 5, 8, 13];

 // no heap allocation take place
 foreach (string s; IntegersAsString(array)) {
    writeln(s);
 }

 How would you do that with ranges?


 
 struct IntegersAsString
 {
     private
     {
       int[] array;
       char[16] temp;
     }
 
     char[] head()
     {
         int len = sprintf(temp.ptr, "%d", array[0]);
         return temp[0..len];
     }
 
     void next()
     {
         array = array[1..$];
     }
 
     bool empty()
     {
         return array.length == 0;
     }
 }
 
 void main()
 {
     int[] array = [1, 1, 2, 3, 5, 8, 13];
 
     // no heap allocation take place
     foreach (char[] s; IntegersAsString(array))
         writefln(s);
 }


One of these days I need to learn the algorithm:

1. Wake up

2. Get coffee

3. Read _all_ posts

4. Post only if necessary


Andrei
Jan 20 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Denis Koroskin wrote:

 One nice thing that opApply capable of is it can avoid heap activity by 
 stack-allocating data during iteration.
 
 For example, given an array of ints, iterate over string representations 
 of them:
 
 struct IntegersAsString
 {
    void opAplly(int delegate(string s) dg)
    {
        char[16] temp;
 
        foreach (i; array) {
            int len = sprintf(temp, "%d", i);
            int result = dg(temp[0..len]);
            if (result != 0) {
                return result;
            }
        }
 
        return 0;
    }
 
    private int[] array;
 }
 
 int array = [1, 1, 2, 3, 5, 8, 13];
 
 // no heap allocation take place
 foreach (string s; IntegersAsString(array)) {
    writeln(s);
 }
 
 How would you do that with ranges?


Note that at some point you need to do a cast somewhere because you 
operate on mutable chars yet the delegate takes a string.

The range solution is very similar and just as simple. The only care 
must be taken to not fill the buffer unnecessarily as head() may be 
accessed a number of times before next().

struct IntegersAsString
{
private:
     size_t i;
     char[16] buffer;
     int[] array;
public:
     void next() { ++i; buffer[0] = 0; }
     bool empty() { return i >= array.length; }
     const(char)[] head()
     {
         if (buffer[0] == 0)
         {
             sprintf(buffer, "%d", array[i]);
         }
         return buffer;
     }
}


Andrei
Jan 20 2009