www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - opApply/opApplyReverse return value types

reply Max Samuha <samukha maxter.com.ua> writes:
The question might seem idle but why opApply/opApplyReverse return int
instead of bool, anyway?
Oct 17 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Max Samuha wrote:

 The question might seem idle but why opApply/opApplyReverse return int
 instead of bool, anyway?


Actually, why do they have to return anything?  It seems like it should 
be possible to make this work:

void opApply(void delegate(inout ArgT) dg)
{
    for (int i=0; i<length; i++)
    {
       if (dg(array[i]))
         break;
    }
}

I haven't totally grokked the code, but I see the magic is happening in 
statement.c, ForeachStatement::semantic somewhere.  That function is 
constructing the delegate that wraps the loop body.  I don't see why the 
delegate wrapper can't just store the value it returns to me so I don't 
have to keep track of it.  It seems weirdly low-level for me to have to 
be the shephard of some value who's meaning is totally opaque to me.

--bb
Oct 17 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Bill Baxter wrote:

 Max Samuha wrote:

 The question might seem idle but why opApply/opApplyReverse return int
 instead of bool, anyway?


 
 Actually, why do they have to return anything?  It seems like it should 
 be possible to make this work:
 
 void opApply(void delegate(inout ArgT) dg)
 {
    for (int i=0; i<length; i++)
    {
       if (dg(array[i]))
         break;
    }
 }
 
 I haven't totally grokked the code, but I see the magic is happening in 
 statement.c, ForeachStatement::semantic somewhere.  That function is 
 constructing the delegate that wraps the loop body.  I don't see why the 
 delegate wrapper can't just store the value it returns to me so I don't 
 have to keep track of it.  It seems weirdly low-level for me to have to 
 be the shephard of some value who's meaning is totally opaque to me.


I tried a little more to figure out statement.c, but it's definitely 
over my head for now without studying more about the internals of the 
compiler.  Still, I'd like to understand how this foreach/opApply 
business works, so let me explain how I think it works in principle, and 
hopefully someone can tell me where I'm wrong.

I'm thinking that basically when you write:

   foreach( T val; aggregate )
      /loopBody/

Conceptually what happens is that d makes some wrapper around your loop 
body:

class loopWrapper(T)
{
     int doOneLoop(T val)
     {
        /setup code/
        /loopBody/
        /cleanup code/
        return ret;
     }
}

And then it calls your opApply passing it a delegate to that wrapper.

    wrap = new loopWrapper();
    int ret = aggregate.opApply( &wrap.doOneLoop );

Then my opApply does something like the standard:

int opApply(int delegate(inout ArgT) doOneLoop)
{
    int ret;
    for (int i=0; i<length; i++)
    {
       ret = doOneLoop(myArray[i]);
       if (ret)
         break;
    }
    return ret;
}

But D owns the loopWrapper and controls what goes into doOneLoop's 
/setup code/ and /cleanup code/, so D should know what its return value 
is without having to ask the aggregate to return it.    Why not stash 
the return value in the loopWrapper so the user doesn't have to worry 
about it?  Like this:

class loopWrapper(T)
{
     void doOneLoop(T val)
     {
        /setup code/
        /loopBody/
        /cleanup code/
        retCode = ret;  // ADDED
        return;
     }
     int retCode;  // ADDED
}

Then D could just get the return code from the wrapper:

    wrap = new loopWrapper();
    aggregate.opApply( &wrap.doOneLoop );
    int ret = wrap.retCode;

and not bother every opApply function with having to handle it with 
boiler plate code that a) they can easily mess up, and b) obfuscates the 
underlying idea.

So why wouldn't that work?

--bb
Oct 17 2006
parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
news:eh3taa$1c98$1 digitaldaemon.com...

 I tried a little more to figure out statement.c, but it's definitely over 
 my head for now without studying more about the internals of the compiler. 
 Still, I'd like to understand how this foreach/opApply business works, so 
 let me explain how I think it works in principle, and hopefully someone 
 can tell me where I'm wrong.

 I'm thinking that basically when you write:

   foreach( T val; aggregate )
      /loopBody/

 Conceptually what happens is that d makes some wrapper around your loop 
 body:

 class loopWrapper(T)
 {
     int doOneLoop(T val)
     {
        /setup code/
        /loopBody/
        /cleanup code/
        return ret;
     }
 }

 And then it calls your opApply passing it a delegate to that wrapper.

    wrap = new loopWrapper();
    int ret = aggregate.opApply( &wrap.doOneLoop );

 Then my opApply does something like the standard:

 int opApply(int delegate(inout ArgT) doOneLoop)
 {
    int ret;
    for (int i=0; i<length; i++)
    {
       ret = doOneLoop(myArray[i]);
       if (ret)
         break;
    }
    return ret;
 }


You're right, although it does it a bit more efficiently by just turning 
your loop body into a  nested function, and translating all "break"s into 
"return 1"s and "continue"s into "return 0"s and sticks a "return 0" at the 
end.  So..

foreach(int x; a)
{
    if(x == 6)
        break;

    if(x == 3)
        continue;

    writefln(x);
}

Becomes:

a.opApply(delegate int(inout int x)
{
    if(x == 6)
        return 1;

    if(x == 3)
        return 0;

    writefln(x);
    return 0;
});

In fact, the latter is entirely valid code and works fine.


 But D owns the loopWrapper and controls what goes into doOneLoop's /setup 
 code/ and /cleanup code/, so D should know what its return value is 
 without having to ask the aggregate to return it.    Why not stash the 
 return value in the loopWrapper so the user doesn't have to worry about 
 it?  Like this:

 class loopWrapper(T)
 {
     void doOneLoop(T val)
     {
        /setup code/
        /loopBody/
        /cleanup code/
        retCode = ret;  // ADDED
        return;
     }
     int retCode;  // ADDED
 }

 Then D could just get the return code from the wrapper:

    wrap = new loopWrapper();
    aggregate.opApply( &wrap.doOneLoop );
    int ret = wrap.retCode;

 and not bother every opApply function with having to handle it with boiler 
 plate code that a) they can easily mess up, and b) obfuscates the 
 underlying idea.

 So why wouldn't that work?


You know, out of curiosity:

class A
{
 int[] arr;

 this()
 {
  arr = new int[10];

  foreach(int i, inout int v; arr)
   v = i;
 }

 int opApply(int delegate(inout int) dg)
 {
  foreach(int v; arr)
  {
   if(dg(v))
    break;
  }

  return -49;
 }
}

void main()
{
 A a = new A();

 foreach(int v; a)
  writefln(v);

 writefln("done");
}

This works fine.  I am returning -49 from opApply and it works fine.  I can 
return 0 from opApply and it works fine.  I honestly have no idea what the 
return from opApply is for.
Oct 17 2006
next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Jarrett Billingsley wrote:

 "Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
 news:eh3taa$1c98$1 digitaldaemon.com...

 I tried a little more to figure out statement.c, but it's definitely over 
 my head for now without studying more about the internals of the compiler. 
 Still, I'd like to understand how this foreach/opApply business works, so 
 let me explain how I think it works in principle, and hopefully someone 
 can tell me where I'm wrong.

 I'm thinking that basically when you write:

   foreach( T val; aggregate )
      /loopBody/

 Conceptually what happens is that d makes some wrapper around your loop 
 body:

 class loopWrapper(T)
 {
     int doOneLoop(T val)
     {
        /setup code/
        /loopBody/
        /cleanup code/
        return ret;
     }
 }

 And then it calls your opApply passing it a delegate to that wrapper.

    wrap = new loopWrapper();
    int ret = aggregate.opApply( &wrap.doOneLoop );

 Then my opApply does something like the standard:

 int opApply(int delegate(inout ArgT) doOneLoop)
 {
    int ret;
    for (int i=0; i<length; i++)
    {
       ret = doOneLoop(myArray[i]);
       if (ret)
         break;
    }
    return ret;
 }


 
 You're right, although it does it a bit more efficiently by just turning 
 your loop body into a  nested function, and translating all "break"s into 
 "return 1"s and "continue"s into "return 0"s and sticks a "return 0" at the 
 end.  So..
 
 foreach(int x; a)
 {
     if(x == 6)
         break;
 
     if(x == 3)
         continue;
 
     writefln(x);
 }
 
 Becomes:
 
 a.opApply(delegate int(inout int x)
 {
     if(x == 6)
         return 1;
 
     if(x == 3)
         return 0;
 
     writefln(x);
     return 0;
 });
 
 In fact, the latter is entirely valid code and works fine.
 

 But D owns the loopWrapper and controls what goes into doOneLoop's /setup 
 code/ and /cleanup code/, so D should know what its return value is 
 without having to ask the aggregate to return it.    Why not stash the 
 return value in the loopWrapper so the user doesn't have to worry about 
 it?  Like this:

 class loopWrapper(T)
 {
     void doOneLoop(T val)
     {
        /setup code/
        /loopBody/
        /cleanup code/
        retCode = ret;  // ADDED
        return;
     }
     int retCode;  // ADDED
 }

 Then D could just get the return code from the wrapper:

    wrap = new loopWrapper();
    aggregate.opApply( &wrap.doOneLoop );
    int ret = wrap.retCode;

 and not bother every opApply function with having to handle it with boiler 
 plate code that a) they can easily mess up, and b) obfuscates the 
 underlying idea.

 So why wouldn't that work?


 
 You know, out of curiosity:
 
 class A
 {
  int[] arr;
 
  this()
  {
   arr = new int[10];
 
   foreach(int i, inout int v; arr)
    v = i;
  }
 
  int opApply(int delegate(inout int) dg)
  {
   foreach(int v; arr)
   {
    if(dg(v))
     break;
   }
 
   return -49;
  }
 }
 
 void main()
 {
  A a = new A();
 
  foreach(int v; a)
   writefln(v);
 
  writefln("done");
 }
 
 This works fine.  I am returning -49 from opApply and it works fine.  I can 
 return 0 from opApply and it works fine.  I honestly have no idea what the 
 return from opApply is for. 


Wow, you're right!  Maybe it's for the vague and mysterious "future"??

I wonder if it's really legit?

--bb
Oct 17 2006
prev sibling parent reply BCS <BCS pathlink.com> writes:
Jarrett Billingsley wrote:

 
 This works fine.  I am returning -49 from opApply and it works fine.  I can 
 return 0 from opApply and it works fine.  I honestly have no idea what the 
 return from opApply is for. 
 
 


I would assume that the generated delegate different return value for 
each goto and the return;

void main(char argv[][])
{
	int i = argv.length;
	foreach(a; new ForeachClass)
	{
		switch(i)
		{
			case 0: goto a;
			case 1: goto b;
			case 2: goto c;
			case 3: goto d;
			default: i/=4;

			case 76: return;
		}
	}

	a:	writef("hi\n"); return;
	b:	writef("Wee\n"); return;
	c:	writef("Zzzz\n"); return;
	d:	writef("Hrumph\n"); return;
}
Oct 18 2006
next sibling parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"BCS" <BCS pathlink.com> wrote in message 
news:eh5mvh$11t$7 digitaldaemon.com...

 I would assume that the generated delegate different return value for each 
 goto and the return;


By gum, you're right.  I just tested it, and returning a bogus value causes 
gotos from inside the foreach not to work.  But returning the correct value 
makes them work.

Would be nice if that were documented somewhere, though.
Oct 18 2006
prev sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
BCS wrote:

 Jarrett Billingsley wrote:

 This works fine.  I am returning -49 from opApply and it works fine.  
 I can return 0 from opApply and it works fine.  I honestly have no 
 idea what the return from opApply is for.


 
 I would assume that the generated delegate different return value for 
 each goto and the return;
 
 void main(char argv[][])
 {
     int i = argv.length;
     foreach(a; new ForeachClass)
     {
         switch(i)
         {
             case 0: goto a;
             case 1: goto b;
             case 2: goto c;
             case 3: goto d;
             default: i/=4;
 
             case 76: return;
         }
     }
 
     a:    writef("hi\n"); return;
     b:    writef("Wee\n"); return;
     c:    writef("Zzzz\n"); return;
     d:    writef("Hrumph\n"); return;
 }


Damn, is that the only reason?  Goto from inside a foreach must 
constitute less than 1% of all use cases.  It just doesn't seem right to 
expose the user to that kind of implementation detail in a core language 
construct.  And probably 99% of those goto usages have a simple 
workaround in the form of
     bool done = false;
     foreach(a; new ForeachClass)
     {
         switch(i)
         {
             ...
             default:
                done = true;
                //goto FINISH; not from a block!

             case 76: return;
         }
     }
     if (done) goto FINISH;

And there's probably even something cleaner using exceptions or scope 
statements.

I wonder, can you goto out of an inner function?  If not, why should you 
be able to goto out of a foreach block?

Everyone raves about ruby blocks.  Do they have gotos?
I'm guessing no.  It seems D is /this/ close to being able to do 
everything that Ruby blocks can do.

The main difference between ruby blocks and D's foreach seems to be that 
in ruby, opApply effectively IS the foreach.  So in pseudo ruby:

     foreach(int i, &list.opApply)
        /block/

Is something like
     list.opApply()(int i)
       /block/

That makes a lot of sense.  Get rid of the foreach keyword.  In truth 
'foreach' knows nothing about 'foreach-ing'.  All it knows is how to 
call a delegate that knows how to foreach something.  But that delegate 
has no obligation to 'foreach'.  It can just as easily return one random 
item and stop.  So the terminology in D is *backwards*.  'foreach' is 
really something that knows how to apply a block-enclosing loop 
construct to a block.  'opApply' is really a method that knows how to go 
through the elements one-by-one.  'apply' should really be the D 
keyword.  'foreach' should be the method name:

     apply(int i, &list.foreach)
        /block/

Wow.  This makes so much sense to me now.  That's why it seems so odd to 
have both foreach and foreach_reverse to me.  Because neither one really 
knows anything about iterating in the first place(*).  It's the methods 
that have that knowledge.  Everyone who doesn't know how ruby blocks 
work should really go take 30 minutes and read up on it and compare with 
how D does it. I found this link useful:
    http://excastle.com/blog/archive/2005/05/18/1019.aspx


(*) Except for this pesky business about the special cases for arrays. 
And honestly, to me, I don't think the overhead is that serious an 
issue.  It's ok to say you pay a little penalty for using foreach on an 
array.  If you want the fastest speed, use the for loop.  But even with 
foreach, you're still going to have performance 10x better than the best 
foreach ruby or python can come up with.

--bb
Oct 18 2006
parent reply BCS <BCS pathlink.com> writes:
Bill Baxter wrote:

 BCS wrote:
 

 Jarrett Billingsley wrote:


 This works fine.  I am returning -49 from opApply and it works fine.  
 I can return 0 from opApply and it works fine.  I honestly have no 
 idea what the return from opApply is for.


 I would assume that the generated delegate different return value for 
 each goto and the return;

 void main(char argv[][])
 {
     int i = argv.length;
     foreach(a; new ForeachClass)
     {
         switch(i)
         {
             case 0: goto a;
             case 1: goto b;
             case 2: goto c;
             case 3: goto d;
             default: i/=4;

             case 76: return;
         }
     }

     a:    writef("hi\n"); return;
     b:    writef("Wee\n"); return;
     c:    writef("Zzzz\n"); return;
     d:    writef("Hrumph\n"); return;
 }


 
 
 Damn, is that the only reason?  Goto from inside a foreach must 
 constitute less than 1% of all use cases.  It just doesn't seem right to 
 expose the user to that kind of implementation detail in a core language 
 construct.


also labeled breaks and continues:

l1: foreach(i; obj1)
{
	l2: foreach(j; obj2)
	{
		if(j.foo) continue l1;
		if(j.bar) break l1;
		if(j.can) goto skip;
	}
	// something
	skip:
	// something else
}


OTOH the block is a delegate so it could stuff that value into a 
variable local to the outer scope and then return a "quit" value.

void foo()
{
	Obj obj1,  obj2;

	obj1.opApply((i){
		int returnAction;
		if(!obj1.opApply((j){
			if(j.foo)
			{
				returnAction = 1;
				return false;
			}
			if(j.bar) break l1;
			{
				returnAction = 2;
				return false;
			}
			if(j.can)
			{
				returnAction = 3;
				return false;
			}
		
		}))
		switch(returnAction)
		{
			case 1:
				return true;
			case 2:
				return false;
			case 3:
				goto skip;
		}
		// something
		skip:
		// something else
	});
}


more or less what you proposed

   And probably 99% of those goto usages have a simple

 workaround in the form of
     bool done = false;
     foreach(a; new ForeachClass)
     {
         switch(i)
         {
             ...
             default:
                done = true;
                //goto FINISH; not from a block!
 
             case 76: return;
         }
     }
     if (done) goto FINISH;
 
 And there's probably even something cleaner using exceptions or scope 
 statements.
 


Who cares about clean? The compiler's doing it, all that I want is fast 
code.


 I wonder, can you goto out of an inner function?  If not, why should you 
 be able to goto out of a foreach block?'


because it shouldn't act any different than an if block in that respect.
Oct 19 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
BCS wrote:

 Bill Baxter wrote:
 

 BCS wrote:


 Jarrett Billingsley wrote:


 This works fine.  I am returning -49 from opApply and it works 
 fine.  I can return 0 from opApply and it works fine.  I honestly 
 have no idea what the return from opApply is for.


 I would assume that the generated delegate different return value for 
 each goto and the return;


 Damn, is that the only reason?  Goto from inside a foreach must 
 constitute less than 1% of all use cases.  It just doesn't seem right 
 to expose the user to that kind of implementation detail in a core 
 language construct.


 
 
 also labeled breaks and continues:
 [...]
 OTOH the block is a delegate so it could stuff that value into a 
 variable local to the outer scope and then return a "quit" value.
 [...]
 
 
 more or less what you proposed


I think that is indeed mostly what I was proposing.  The compiler is 
rewriting the block anyway, translating gotos into returns, etc, so why 
not have it just translate goto's into:
      outerscope_var = /value/;
      return true;

Then at least then I can write code without worrying about *what* I 
should return.

void opApply(void delegate(inout uint) dg)
{
    for (int i = 0; i < array.length; i++)
    {
        if(dg(array[i])) return;
    }
}

Not quite is lovely as the ideal:

void opApply(void delegate(inout uint) dg)
{
    for (int i = 0; i < array.length; i++)
    {
        dg(array[i]);
    }
}

but the ideal requires magically jumping from dg's scope back to the 
outer scope without bothering opApply to check what's going on.  It's 
not clear to me how to do that.  (But I also don't think it's clear that 
it would be impossible to achieve).


 And there's probably even something cleaner using exceptions or scope 
 statements.


 
 Who cares about clean? The compiler's doing it, all that I want is fast 
 code.


I agree that foreach shouldn't induce excessive overhead.  But maybe I 
differ in that I'd gladly take a small speed hit for improved 
readability/usability/maintainablility.  I don't think foreach needs to 
compile down to the exact same code as the best possible for loop.

My perspective on foreach is similar to virtual functions.  Virtual 
functions offer me a way to make my code cleaner and easier to maintain, 
but there is a small penalty to pay for that convenience.  In most cases 
that penalty is not significant enough to give up the convenience.  I 
woudn't mind if foreach came with that same level of penalty.


 I wonder, can you goto out of an inner function?  If not, why should 
 you be able to goto out of a foreach block?'





 because it shouldn't act any different than an if block in that respect.


Yeh, agreed.  It looks like a normal controlled block, so it should 
behave like one.

--bb
Oct 20 2006
parent BCS <BCS pathlink.com> writes:
Bill Baxter wrote:

 BCS wrote:
 

 Bill Baxter wrote:

 And there's probably even something cleaner using exceptions or scope 
 statements.


 Who cares about clean? The compiler's doing it, all that I want is 
 fast code.


 
 
 I agree that foreach shouldn't induce excessive overhead.  But maybe I 
 differ in that I'd gladly take a small speed hit for improved 
 readability/usability/maintainablility.  I don't think foreach needs to 
 compile down to the exact same code as the best possible for loop.
 


Actually, I was referring to clean/messy code generation. Clean source 
code is a must. What the compiler does with it... Who cares? Sort of 
like lex/yacc, the derived code is so ugly that nobody wants to maintain 
it by hand, but nobody has to.


 
 --bb
Oct 20 2006