digitalmars.D - Automatic opApply iteration counter

bearophile (134/134) Apr 13 2010 I have not written this as enhancement request on Bugzilla because while...

Steven Schveighoffer (6/31) Apr 13 2010 No. This is how I do it in dcollections (for optional keys in map conta...

Steven Schveighoffer (6/7) Apr 13 2010 Oh, and don't forget to always make opApply take a scope delegate!

bearophile (71/75) Apr 14 2010 Right, I forget it often... I will keep in mind your example, thank you.

bearophile <bearophileHUGS lycos.com> writes:

I have not written this as enhancement request on Bugzilla because while I have
a clear (small) problem, I think my possible solution is bad (see at the
bottom).

This is how I can use opApply() to create a lazy generator of the first
Fibonacci numbers, inside opApply there can be a good amount of code:


import std.stdio: writeln;
struct Xfibonacci {
    long max;
    this(long inmax) { max = inmax; }
    int opApply(int delegate(ref long) dg) {
        int result;
        long a=0, b=1;
        while (a < max) {
            result = dg(b);
            if (result) break;
            a += b;
            result = dg(a);
            if (result) break;
            b += a;
        }
        return result;
    }
}
void main() {
    foreach (f; Xfibonacci(200))
        writeln(f);
}



But in many situations it's good to have an interation counter too, to index
the given item:
foreach (i, f; Xfibonacci(2_000))

To allow both the foreach version with and without index I have to duplicate
the body of the opApply, but this code duplication is bad:


import std.stdio: writeln;
struct Xfibonacci {
    long max;
    this(long inmax) { max = inmax; }
    int opApply(int delegate(ref long) dg) {
        int result;
        long a=0, b=1;
        while (a < max) {
            result = dg(b);
            if (result) break;
            a += b;
            result = dg(a);
            if (result) break;
            b += a;
        }
        return result;
    }
    int opApply(int delegate(ref int, ref long) dg) {
        int result, index;
        long a=0, b=1;
        while (a < max) {
            result = dg(index, b);
            if (result) break;
            index++;
            a += b;
            result = dg(index, a);
            if (result) break;
            b += a;
            index++;
        }
        return result;
    }
}
void main() {
    foreach (i, f; Xfibonacci(2_000))
        writeln(i, " ", f);
}



To avoid the code duplication I can define a generic Enumerate (with its helper
function 'enumerate'), very similar to the enumerate() present in Python for
the same purpose:


import std.stdio: writeln;
import std.traits: ReturnType;

struct Xfibonacci {
    long max;
    this(long inmax) { max = inmax; }
    int opApply(int delegate(ref long) dg) {
        int result;
        long a=0, b=1;
        while (a < max) {
            result = dg(b);
            if (result) break;
            a += b;
            result = dg(a);
            if (result) break;
            b += a;
        }
        return result;
    }
}

struct Enumerate(Iter) {
    Iter iterable;
    int index;
    alias ReturnType!(typeof({foreach(x; iterable) return x; assert(0); }))
ItemType;

    int opApply(int delegate(ref int, ref ItemType) dg) {
        int result;
        foreach (el; iterable) {
            result = dg(index, el);
            if (result) break;
            index++;
        }
        return result;
    }
}

Enumerate!Iter enumerate(Iter)(Iter iterable, int start=0) {
    return Enumerate!Iter(iterable, start);
}

void main() {
    foreach (i, f; enumerate(Xfibonacci(2_000)))
        writeln(i, " ", f);
}


This is not too much bad, but the Fibonacci numbers now come out of two
opApply, so the compiler fail in optimizing the code well.

So I propose the automatic generation of the indexed version:


import std.stdio: writeln;
struct Xfibonacci {
    long max;
    this(long inmax) { max = inmax; }
    int opApply(int delegate(ref long) dg) {
        int result;
        long a=0, b=1;
        while (a < max) {
            result = dg(b);
            if (result) break;
            a += b;
            result = dg(a);
            if (result) break;
            b += a;
        }
        return result;
    }
}
void main() {
    foreach (f; Xfibonacci(200)) // OK
        writeln(f);
    foreach (i, f; Xfibonacci(200)) // OK
        writeln(f);        
}


This can cause problems if Xfibonacci already contains an OpApply that yields
two or more items... To me it seems to lead to a messy situation... If you have
alternative solutions please tell me.

Bye,
bearophile

Apr 13 2010

Steven Schveighoffer <schveiguy yahoo.com> writes:

bearophile Wrote:

 I have not written this as enhancement request on Bugzilla because while I
have a clear (small) problem, I think my possible solution is bad (see at the
bottom).
 

[snip]
 To allow both the foreach version with and without index I have to duplicate
the body of the opApply, but this code duplication is bad:

No.  This is how I do it in dcollections (for optional keys in map containers):


 import std.stdio: writeln;
 struct Xfibonacci {
     long max;
     this(long inmax) { max = inmax; }
     int opApply(int delegate(ref long) dg) {

           int _dg(ref int i, ref long l) { return dg(l); }
           return opApply(&_dg);
     }
     int opApply(int delegate(ref int, ref long) dg) {
         int result, index;
         long a=0, b=1;
         while (a < max) {
             result = dg(index, b);
             if (result) break;
             index++;
             a += b;
             result = dg(index, a);
             if (result) break;
             b += a;
             index++;
         }
         return result;
     }
 }

Don't forget, opApply is just a function, you can use it as such :)

Apr 13 2010

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

On Tue, 13 Apr 2010 06:13:37 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:

 Don't forget, opApply is just a function, you can use it as such :)

Oh, and don't forget to always make opApply take a scope delegate!   
Otherwise, it allocates the calling function's frame on the heap (in D2 at  
least).

-Steve

Apr 13 2010

bearophile <bearophileHUGS lycos.com> writes:

This thread is now fit for D.learn, but I answer it here to not split it up.

Steven Schveighoffer:

 Don't forget, opApply is just a function, you can use it as such :)

Right, I forget it often... I will keep in mind your example, thank you.


 Oh, and don't forget to always make opApply take a scope delegate!  
 Otherwise, it allocates the calling function's frame on the heap (in D2 at  
 least).

To test it, I have compiled this program with and without the two scope
annotations (I use printf to remove lot of noise from the resulting asm,
because writeln adds tons of functions):


import std.c.stdio: printf;
alias int Int;
struct Xfibonacci {
    Int max;

    int opApply(scope int delegate(ref Int) dg) {
         int _dg(ref int i, ref Int l) { return dg(l); }
         return opApply(&_dg);
    }

    int opApply(scope int delegate(ref int, ref Int) dg) {
        int result, index;
        Int a=0, b=1;
        while (a < max) {
            result = dg(index, b);
            if (result) break;
            index++;
            a += b;
            result = dg(index, a);
            if (result) break;
            b += a;
            index++;
        }
        return result;
    }
}

void main() {
    foreach (f; Xfibonacci(200))
        printf("%d\n", f);
    printf("\n");

    foreach (i, f; Xfibonacci(200))
        printf("%d %d\n", i, f);
}



This is one of the functions, using the scope attributes:

_D11xfibonacci210Xfibonacci7opApplyMFMDFKiZiZi:
    push EAX
    mov ECX,offset FLAT:_D11xfibonacci210Xfibonacci7opApplyMFMDFKiZiZi3_dgMFKiKiZi
    mov EAX,0[ESP]
    push ECX
    lea EDX,4[ESP]
    push EDX
    call near ptr _D11xfibonacci210Xfibonacci7opApplyMFMDFKiKiZiZi
    pop ECX
    ret 8


The same function, not using the scope attributes:

_D11xfibonacci210Xfibonacci7opApplyMFDFKiZiZi:
    push EAX
    push EBX
    push ESI
    push 010h
    call near ptr __d_allocmemory
    mov EBX,EAX
    mov EAX,0Ch[ESP]
    mov [EBX],EAX
    mov EDX,018h[ESP]
    mov ESI,014h[ESP]
    mov 8[EBX],ESI
    mov ECX,offset FLAT:_D11xfibonacci210Xfibonacci7opApplyMFDFKiZiZi3_dgMFKiKiZi
    mov 0Ch[EBX],EDX
    add ESP,4
    push ECX
    push EBX
    call near ptr _D11xfibonacci210Xfibonacci7opApplyMFDFKiKiZiZi
    pop ESI
    pop EBX
    pop ECX
    ret 8

Bye,
bearophile

Apr 14 2010

D Programming

C/C++ Programming

Other

digitalmars.D - Automatic opApply iteration counter