October 18, 2006
Bill Baxter wrote:
> Tom S wrote:
>> Bill Baxter wrote:
>>> Bill Baxter wrote:
>>>> Is there any reason for not allowing a function to be used too?
>>>> Then you could also use a closure as the thing that does the iteration:
>>>
>>> Ok, I just realized that "delegate" can also be pointer to a non-static nested function...  Duh.  So my question should have been -- why doesn't this work?
>>>
>>> int delegate(int delegate(inout ElemT))
>>> reversed(AggregateT,ElemT)(AggregateT array)
>>> {
>>>     int _innerFunc(int delegate(inout ElemT) loopBody)
>>>     {
>>>         int done = 0;
>>>         for (int i = array.length-1; i >=0; i--)
>>>         {
>>>             done = loopBody(array[i]);
>>>             if (done)
>>>                 break;
>>>         }
>>>         return done;
>>>     }
>>>     return &_innerFunc;
>>> }
>>>   ...
>>> foreach(real r; reversed!(real[],real)(areal))
>>> {...}
>>>
>>> Compiles but gives:
>>> "Error: Access Violation"
>>>
>>> I'm not totally clear on how pointers/objects are handled in D.  It looks the call to reversed() is maybe creating a copy of the data?  If I put in printfs the pointer value is different from that of the original int[].
>>
>> Basically, when you leave 'reversed', any stack data defined within that function becomes invalid, as D doesn't support real closures. What you're aiming for can be achieved without the new feature anyway, e.g. through:
>>
>> ----
>> import std.stdio;
>>
>>
>> struct reverse__(AggregType) {
>>     alias typeof(AggregType[0]) ElemType;
>>     AggregType arr;
>>     int opApply(int delegate(inout ElemType) dg) {
>>         int ret = 0;
>>         for (int i = arr.length -1; i >= 0; --i){
>>             ret = dg(arr[i]);
>>             if (ret) break;
>>         }
>>         return ret;
>>     }
>> }
>>
>> reverse__!(T) reverse(T)(T x) {
>>     reverse__!(T) res;
>>     res.arr = x;
>>     return res;
>> }
>>
>>
>> void main() {
>>     char[] foo = "foo bar";
>>     foreach (c; foo.reverse) {
>>         writefln(c);
>>     }
>> }
> 
> Did you mean
>    foreach (c; reverse(foo)) ??
> I guess so.  it does seem to compile that way.

Actually I meant foo.reverse. It compiles and runs fine on .169


> I think this falls into Walter's "dummy classes and hackish stuff" category though.

It's not that bad. There's just one small dummy struct that resides on the stack. The rest is a function that returns it and a generic implementation of 'reverse' that will work on any array type.


> Is there no way to make something similar work with a nested function? If my reversed function above could just get the pointer to the actual array then it seems like it should work.  Is there some way to declare the AggregateT array parameter so that that happens?


Not without dummy classes and hackish stuff <g>


--
Tomasz Stachowiak
October 18, 2006
Tom S wrote:
> Bill Baxter wrote:
>> Did you mean
>>    foreach (c; reverse(foo)) ??
>> I guess so.  it does seem to compile that way.
> 
> Actually I meant foo.reverse. It compiles and runs fine on .169

Uh, sorry about that... I forgot about the built-in .reverse for arrays and it seems that it was being used in this case. Indeed, it should be reverse(foo).
October 18, 2006
Bill Baxter wrote:
> I don't see how it helps.  If you can already do:
>    foreach(T item; &collection.reversed()) { }

That doesn't work for arrays.
October 18, 2006
Tom S wrote:
> Bill Baxter wrote:
>> Tom S wrote:
>>> Bill Baxter wrote:
>>>> Bill Baxter wrote:
 ----
>>> import std.stdio;
>>>
>>>
>>> struct reverse__(AggregType) {
>>>     alias typeof(AggregType[0]) ElemType;
>>>     AggregType arr;
>>>     int opApply(int delegate(inout ElemType) dg) {
>>>         int ret = 0;
>>>         for (int i = arr.length -1; i >= 0; --i){
>>>             ret = dg(arr[i]);
>>>             if (ret) break;
>>>         }
>>>         return ret;
>>>     }
>>> }
>>>
>>> reverse__!(T) reverse(T)(T x) {
>>>     reverse__!(T) res;
>>>     res.arr = x;
>>>     return res;
>>> }
>>>
>>>
>>> void main() {
>>>     char[] foo = "foo bar";
>>>     foreach (c; foo.reverse) {
>>>         writefln(c);
>>>     }
>>> }
>>
>> Did you mean
>>    foreach (c; reverse(foo)) ??
>> I guess so.  it does seem to compile that way.
> 
> Actually I meant foo.reverse. It compiles and runs fine on .169

Ok, sure it compiles, but if you're just going to reverse the array in-place, then you don't need all that reverse__ stuff up there.  I'm confused... :-?   But anyway the reverse__ stuff *is* what I was looking to do and it does compile, too, and it does manage to iterate over the array without modifying it.

>> I think this falls into Walter's "dummy classes and hackish stuff" category though.
> 
> It's not that bad. There's just one small dummy struct that resides on the stack. The rest is a function that returns it and a generic implementation of 'reverse' that will work on any array type.

Any array type, or anything that has a .length property and overloads opIndex, right?

>> Is there no way to make something similar work with a nested function? If my reversed function above could just get the pointer to the actual array then it seems like it should work.  Is there some way to declare the AggregateT array parameter so that that happens?
> 
> 
> Not without dummy classes and hackish stuff <g>

Seriously?  Is there no way to write the function below so that the program prints out the same value twice?

void print_addr( ??? arg )
{
   writefln(&arg);
}

void main()
{
    int[] arr = [1,2,3,4,5];
    writefln(&arr);
    print_addr(arr);
}

--bb
October 18, 2006
Bill Baxter wrote:
>> Actually I meant foo.reverse. It compiles and runs fine on .169
> 
> Ok, sure it compiles, but if you're just going to reverse the array in-place, then you don't need all that reverse__ stuff up there.  I'm confused... :-?   But anyway the reverse__ stuff *is* what I was looking to do and it does compile, too, and it does manage to iterate over the array without modifying it.

Hey, I said I was sorry in a more recent post :P


> Any array type, or anything that has a .length property and overloads opIndex, right?

Hmmm... yup, that should be enough



> Seriously?  Is there no way to write the function below so that the program prints out the same value twice?
> 
> void print_addr( ??? arg )
> {
>    writefln(&arg);
> }
> 
> void main()
> {
>     int[] arr = [1,2,3,4,5];
>     writefln(&arr);
>     print_addr(arr);
> }

Sure it's possible, but in the earlier case, you were trying to access stack variables after returning from the function. In the same manner, 'arg' is no longer a valid variable after print_addr returns, you'd be referencing junk on the stack. You could store it in a static variable, but I consider it hackish, as it's not thread safe :)
October 18, 2006
Walter Bright wrote:
> Bill Baxter wrote:
>> I don't see how it helps.  If you can already do:
>>    foreach(T item; &collection.reversed()) { }
> 
> That doesn't work for arrays.

I see.  I didn't realize the compiler special-cased arrays with foreach.
I see that also extends to every built-in behavior that can be mimicked by operator overloading.   That's disappointing.

It would be much more consistent if something[4] could *always* be substituted with something.opIndex(4).  Or if foreach(a; something) could *always* be substituted with foreach(a; &something.opApply).  That doesn't mean that arrays have to be classes, just that it has to look like one to the user.  Same way they now have .length, but that doesn't mean they are classes/structs.  You can still use whatever optimizations or special cases you want in the compiler to speed it up.

Hmmm.  Well anyway, even if array.reversed() isn't going to work, I still think

   foreach(T item; reversed(collection)) { }

could be the solution.  In any case you've got to have a reasonable story for how to handle specific iteration strategies being bolted on after the fact.  I.e. I've got a BorgCollection class and I want an iterator that returns only the borg's which are of type KlingonBorg. Unfortunately the BorgCollection designer didn't foresee this need. There should be a reasonable way for me to write a klingonBorgIter function so I can say

   foreach(KlingonBorg b; klingonBorgIter(borg_collection)) {
   }

I can do that now.  Tom S showed how.  But you say that requires "dummy classes and hackish stuff" and so is not good enough as a solution for the core iteration implementation.  So *make* it good enough! Figure out how to make it work, then apply that one technique mercilessly and consistently everywhere.

--bb
October 18, 2006
Tom S wrote:
> Bill Baxter wrote:
>> Seriously?  Is there no way to write the function below so that the program prints out the same value twice?
>>
>> void print_addr( ??? arg )
>> {
>>    writefln(&arg);
>> }
>>
>> void main()
>> {
>>     int[] arr = [1,2,3,4,5];
>>     writefln(&arr);
>>     print_addr(arr);
>> }
> 
> Sure it's possible, but in the earlier case, you were trying to access stack variables after returning from the function. In the same manner, 'arg' is no longer a valid variable after print_addr returns, you'd be referencing junk on the stack. You could store it in a static variable, but I consider it hackish, as it's not thread safe :)

Right, but really I don't want to access 'arg' I want to access the 'arr' in the outer scope.

In C++ I would just make it a reference parameter, and take the address:

void print_addr( IntArrayType& arg )
{
    writefln(&arg);
}
void main()
{
    int[] arr = [1,2,3,4,5];
    writefln(&arr);
    print_addr(arr);
}

Then aside from the fact that D is not C++, it would print the same value for both, and it wouldn't be accessing a static variable.  And it would be perfectly thread safe.

--bb
October 18, 2006
Walter Bright wrote:
> 
> So I've been interested in having D algorithms and collections not need iterator types at all. I've been experimenting with doing STL's algorithms in D, and it became clear that to make them complete, reverse iteration was necessary. foreach handles forward iteration, and opIndex handles random access. Various ways of doing reverse traversal without core support always seemed to involve creating dummy classes and other hackish stuff. Promoting it to a supported statement makes it pretty clean for the user to understand and use.
> 
> Essentially, I think foreach_reverse is the missing piece to be able to implement all of STL's algorithms code for D.

I think I agree, but for the sake of argument, how would D handle 'find'  operations on sequences that don't support opIndex?  At some point, a generalizable bookmark is almost necessary for a faithful implementation of some C++ algorithms.  Also, many of these algorithms also require iteration across two sequences simultaneously, which doesn't map very cleanly into foreach.  Consider a substring-style find operation (std::search), for example, where both the pattern and target types do not support opIndex or opSlice.  I might argue that it's a bit silly or unrealistic to desire such an operation, but the C++ algorithm library does support it.


Sean
October 18, 2006
Bill Baxter wrote:
> In C++ I would just make it a reference parameter, and take the address:
> 
> void print_addr( IntArrayType& arg )
> {
>     writefln(&arg);
> }
> void main()
> {
>     int[] arr = [1,2,3,4,5];
>     writefln(&arr);
>     print_addr(arr);
> }
> 
> Then aside from the fact that D is not C++, it would print the same value for both, and it wouldn't be accessing a static variable.  And it would be perfectly thread safe.


Heh, that's not the same case. You can do that it D, except that you'd use inout for the reference. The problem arises when you try to return a delegate literal from a function, it then references stack data which is invalid after the function returns. Speaking of C++ analogies, it is just like returning pointers to stack data. Most compilers complain about it because it's simply wrong. There is one solution - actually embed that data in the returned value - just what I did with the struct. An alternative that I dont like very much would be to create a local class and an object thereof, then return a delegate pointing to a method of that object. It works, because objects live on the heap. It might be shorter implementation-wise than my previous solution, but it involves an object allocation and unnecessarily bothers the GC.

If you want to use objects nevertheless, iirc an 'AdvancedDelegate' class once announced in this NG allowed a shortcut for this. My Bind library ( http://www-users.mat.uni.torun.pl/~h3r3tic/bind.rar ) could also be used to associate partial parameters with a function or a delegate. But it still requires an object.
October 18, 2006
Sean Kelly wrote:
> I think I agree, but for the sake of argument, how would D handle 'find'  operations on sequences that don't support opIndex?  At some point, a generalizable bookmark is almost necessary for a faithful implementation of some C++ algorithms.  Also, many of these algorithms also require iteration across two sequences simultaneously, which doesn't map very cleanly into foreach.  Consider a substring-style find operation (std::search), for example, where both the pattern and target types do not support opIndex or opSlice.  I might argue that it's a bit silly or unrealistic to desire such an operation, but the C++ algorithm library does support it.

I think the target types will have to support opIndex or opSlice.