www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - Variadic Delegate

reply "Tony" <talktotony email.com> writes:
The following code works as expected and returns 42:

import std.stdio;

void main() {
   int delegate() dp = setup(42);
   writefln(dp());
}

int delegate() setup(int n) {
   int delegate() dp = delegate int(){ return n; };
   return dp;
}

The following code (with a variadic delegate) does not work as expected and
returns what appears to be a nonsense value of 4202561:

import std.stdio;

void main() {
   int delegate(...) dp = setup(42);
   writefln(dp());
}

int delegate(...) setup(int n) {
   int delegate(...) dp = delegate int(...){ return n; };
   return dp;
}

Am I doing something silly or is this a bug?

Tony
Melbourne, Australia
Jul 02 2005
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Tony wrote:

 The following code works as expected and returns 42:
 
 import std.stdio;
 
 void main() {
    int delegate() dp = setup(42);
    writefln(dp());
 }
 
 int delegate() setup(int n) {
    int delegate() dp = delegate int(){ return n; };
    return dp;
 }


You can't return a delegate literal, like you do in setup() here, if 
that delegate literal uses any stack variables.  That's because, as soon 
as you return from the function, the stack variable becomes invalid. 
Sometimes, it works...but only if you're lucky.  Looks like in this 
example, you were lucky.


 The following code (with a variadic delegate) does not work as expected and
 returns what appears to be a nonsense value of 4202561:


Most likely, the code below fails because, in this case, the stack 
happens to get corrupted.

It's all luck.  Your code above might not have worked if it was compiled 
on some other platform, by some other D compiler, or perhaps even by 
some other version of dmd.

The solution to this (which is really rather hackish, but we don't have 
a better one yet) is to create a simple struct, which has a variable (to 
store the 'n' value you need, and a member function.  Create a copy of 
the struct on the stack, and return the delegate which points to the 
member function:

struct setup_struct {
   int n;
   int the_function(...) { return this.n; }
};
int delegate(...) setup(int n) {
   setup_struct *ret = new setup_struct;
   ret.n = n;
   return &ret.the_function;
}

The 'n' inside the struct, since it is on the heap, will last even when 
the function has returned.  The struct will stay on the heap until you 
have finished with the delegate; when the delegate no longer exists, the 
struct will get automatically garbage collected.

Russ


 import std.stdio;
 
 void main() {
    int delegate(...) dp = setup(42);
    writefln(dp());
 }
 
 int delegate(...) setup(int n) {
    int delegate(...) dp = delegate int(...){ return n; };
    return dp;
 }
 
 Am I doing something silly or is this a bug?
Jul 03 2005
next sibling parent reply "Tony" <talktotony email.com> writes:
Hi Russ,

Thanks for your reply.

I was under the impression that delegates could be used to provide closures
in D.  This is why I thought it was valid to reference the "n" parameter
from the delegate.

I evidently don't understand how closures work in D.  I don't suppose anyone
could offer a few examples of how they should be used?

I should have posted this under D.learn :(

Thanks,

Tony
Melbourne, Australia

"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:daacci$2ri1$1 digitaldaemon.com...

 Tony wrote:

 The following code works as expected and returns 42:

 import std.stdio;

 void main() {
    int delegate() dp = setup(42);
    writefln(dp());
 }

 int delegate() setup(int n) {
    int delegate() dp = delegate int(){ return n; };
    return dp;
 }


 You can't return a delegate literal, like you do in setup() here, if
 that delegate literal uses any stack variables.  That's because, as soon
 as you return from the function, the stack variable becomes invalid.
 Sometimes, it works...but only if you're lucky.  Looks like in this
 example, you were lucky.


 The following code (with a variadic delegate) does not work as expected




and

 returns what appears to be a nonsense value of 4202561:


 Most likely, the code below fails because, in this case, the stack
 happens to get corrupted.

 It's all luck.  Your code above might not have worked if it was compiled
 on some other platform, by some other D compiler, or perhaps even by
 some other version of dmd.

 The solution to this (which is really rather hackish, but we don't have
 a better one yet) is to create a simple struct, which has a variable (to
 store the 'n' value you need, and a member function.  Create a copy of
 the struct on the stack, and return the delegate which points to the
 member function:

 struct setup_struct {
    int n;
    int the_function(...) { return this.n; }
 };
 int delegate(...) setup(int n) {
    setup_struct *ret = new setup_struct;
    ret.n = n;
    return &ret.the_function;
 }

 The 'n' inside the struct, since it is on the heap, will last even when
 the function has returned.  The struct will stay on the heap until you
 have finished with the delegate; when the delegate no longer exists, the
 struct will get automatically garbage collected.

 Russ


 import std.stdio;

 void main() {
    int delegate(...) dp = setup(42);
    writefln(dp());
 }

 int delegate(...) setup(int n) {
    int delegate(...) dp = delegate int(...){ return n; };
    return dp;
 }

 Am I doing something silly or is this a bug?
Jul 03 2005
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Tony wrote:

 Hi Russ,
 
 Thanks for your reply.
 
 I was under the impression that delegates could be used to provide closures
 in D.  This is why I thought it was valid to reference the "n" parameter
 from the delegate.
 
 I evidently don't understand how closures work in D.  I don't suppose anyone
 could offer a few examples of how they should be used?
 
 I should have posted this under D.learn :(
 
 Thanks,
 
 Tony
 Melbourne, Australia


To be perfectly frank, I haven't used a language with closures, so I'm 
not 100% clear on how they are used.  But, from what I've read on the 
web, "a closure is formed when [a nested] function is made accessible 
outside of the function in which it was contained, so that it may be 
executed after the outer function has returned."

Right now, the best way to do this in D is with structs (or classes). 
Unfortunately, this is only somewhat more elegant than the old C way.

If you have a simple closure (you run the closure only once after 
creating it, or else you can run the same closure time many times - it 
never changes), then it's pretty easy.  Just define a struct with a 
single member function, and return it like I showed you.

If, however, you want something that will get called multiple times, and 
  you will need different functions to be called, then it's harder.  The 
key problem is that you can't build a recursive delegate, that is a 
delegate which returns its own type.  Thus, you have to store the 
delegate someplace within the struct.  You can do this by storing the 
delegate directly, or by encoding a state variable and then doing a 
switch on it.  Imagine that you wanted to have a closure which would do 
parsing; it would read 1 or more 'a's, followed by an equal number of 
'b's, followed by an EOF character.  You could build structs like this:

   int EOF=-1;
   struct Parser {
     int count;
     bool delegate(int c) curState;

     bool ParseA(int c) {
       if(c == 'a') {
         count++;
         return true;
       }
       if(c == 'b') {
         if(count == 0);
           return false;
         else {
           curState = &this.ParseB;
           count--;
           return true;
         }
       }
       return false;
     }
     bool ParseB(int c) {
       if(c == EOF)
         return count == 0;
       if(c == 'b')
         if(count == 0)
           return false;
         count--;
         return true;
       }
       return true;
     }

     bool Driver(int c) {
       return curState(c);
     }
   }

   bool delegate(int) BuildParser {
     Parser *ret = new Parser;
     ret.count = 0;
     ret.curState = &ret.ParseA;
     return &ret.Driver;
   }



Ugly, isn't it?  Well, at least the old C way (using function pointers, 
instead of delegates) would have been a little worse.

Russ
Jul 05 2005
parent reply "Tony" <talktotony email.com> writes:
"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:daedtd$eng$1 digitaldaemon.com...

 Tony wrote:

 Hi Russ,

 Thanks for your reply.

 I was under the impression that delegates could be used to provide




closures

 in D.  This is why I thought it was valid to reference the "n" parameter
 from the delegate.

 I evidently don't understand how closures work in D.  I don't suppose




anyone

 could offer a few examples of how they should be used?

 I should have posted this under D.learn :(

 Thanks,

 Tony
 Melbourne, Australia


 To be perfectly frank, I haven't used a language with closures, so I'm
 not 100% clear on how they are used.  But, from what I've read on the
 web, "a closure is formed when [a nested] function is made accessible
 outside of the function in which it was contained, so that it may be
 executed after the outer function has returned."

 Right now, the best way to do this in D is with structs (or classes).
 Unfortunately, this is only somewhat more elegant than the old C way.

 If you have a simple closure (you run the closure only once after
 creating it, or else you can run the same closure time many times - it
 never changes), then it's pretty easy.  Just define a struct with a
 single member function, and return it like I showed you.

 If, however, you want something that will get called multiple times, and
   you will need different functions to be called, then it's harder.  The
 key problem is that you can't build a recursive delegate, that is a
 delegate which returns its own type.  Thus, you have to store the
 delegate someplace within the struct.  You can do this by storing the
 delegate directly, or by encoding a state variable and then doing a
 switch on it.  Imagine that you wanted to have a closure which would do
 parsing; it would read 1 or more 'a's, followed by an equal number of
 'b's, followed by an EOF character.  You could build structs like this:

    int EOF=-1;
    struct Parser {
      int count;
      bool delegate(int c) curState;

      bool ParseA(int c) {
        if(c == 'a') {
          count++;
          return true;
        }
        if(c == 'b') {
          if(count == 0);
            return false;
          else {
            curState = &this.ParseB;
            count--;
            return true;
          }
        }
        return false;
      }
      bool ParseB(int c) {
        if(c == EOF)
          return count == 0;
        if(c == 'b')
          if(count == 0)
            return false;
          count--;
          return true;
        }
        return true;
      }

      bool Driver(int c) {
        return curState(c);
      }
    }

    bool delegate(int) BuildParser {
      Parser *ret = new Parser;
      ret.count = 0;
      ret.curState = &ret.ParseA;
      return &ret.Driver;
    }



 Ugly, isn't it?  Well, at least the old C way (using function pointers,
 instead of delegates) would have been a little worse.

 Russ


My understanding of closures is that they are simply the combination of a
function (delegate in D?) and a "snapshot" of the functions lexical
environment.

Referring to my previous example:

import std.stdio;

void main() {
   int delegate() dp = setup(42);
   writefln(dp());
}

int delegate() setup(int n) {
   int delegate() dp = delegate int(){ return n; };
   return dp;
}

It should be valid for the delegate to reference the "n".  The reason being
that:
1. a structure containing a copy of the referenced parts of the lexical
environment should have been made by the compiler when the delegate was
created,
2. that structure should have the same lifetime as the delegate,
3. the "n" within the delegate is actually referring to the "n" in this
hidden structure rather than the "n" on the stack.

The above points assume that delegates are the mechanism that provides
closures in D.  I notice in the D documentation that Walter uses the term
"dynamic closure" rather than just closure, and I'm not sure of the
significance of the "dynamic" part.

Assuming that what I have said above is correct (I'm open to any
corrections!), then I can't see why the variadic delegate example I used
earlier would not work.

Tony
Melbourne, Australia
Jul 05 2005
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Tony wrote:

 Referring to my previous example:
 
 import std.stdio;
 
 void main() {
    int delegate() dp = setup(42);
    writefln(dp());
 }
 
 int delegate() setup(int n) {
    int delegate() dp = delegate int(){ return n; };
    return dp;
 }
 
 It should be valid for the delegate to reference the "n".  The reason being
 that:
 1. a structure containing a copy of the referenced parts of the lexical
 environment should have been made by the compiler when the delegate was
 created,
 2. that structure should have the same lifetime as the delegate,
 3. the "n" within the delegate is actually referring to the "n" in this
 hidden structure rather than the "n" on the stack.
 
 The above points assume that delegates are the mechanism that provides
 closures in D.  I notice in the D documentation that Walter uses the term
 "dynamic closure" rather than just closure, and I'm not sure of the
 significance of the "dynamic" part.
 
 Assuming that what I have said above is correct (I'm open to any
 corrections!), then I can't see why the variadic delegate example I used
 earlier would not work.
 
 Tony
 Melbourne, Australia


The problem here is that sometimes you don't want the compiler to make a 
copy of 'n'.  I have written code that looks like this before:

int foo() {
   int i = 0;
   bar(delegate void() { i++; });
   return i;
}

void bar(void delegate() dg) {
   <do stuff>
   <call dg() some amount of times>
   return;
}

In the above code, of course, we want the delegate to be using the 
original 'i', not a copy.

The question, of course, is why doesn't the compiler automatically do 
the right thing - make a copy when needed, and don't when it's not?  The 
problem, of course, is that it's not possible for the compiler to know 
which is the right thing, at least not in all cases.  See my response to 
Manfred in this same thread for a discussion of that.
Jul 06 2005
parent "Tony" <talktotony email.com> writes:
Thanks Russ.

I shall have to have a bit of a think about this.

Tony
Melbourne, Australia

"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:dagoun$2a4v$1 digitaldaemon.com...

 Tony wrote:

 Referring to my previous example:

 import std.stdio;

 void main() {
    int delegate() dp = setup(42);
    writefln(dp());
 }

 int delegate() setup(int n) {
    int delegate() dp = delegate int(){ return n; };
    return dp;
 }

 It should be valid for the delegate to reference the "n".  The reason




being

 that:
 1. a structure containing a copy of the referenced parts of the lexical
 environment should have been made by the compiler when the delegate was
 created,
 2. that structure should have the same lifetime as the delegate,
 3. the "n" within the delegate is actually referring to the "n" in this
 hidden structure rather than the "n" on the stack.

 The above points assume that delegates are the mechanism that provides
 closures in D.  I notice in the D documentation that Walter uses the




term

 "dynamic closure" rather than just closure, and I'm not sure of the
 significance of the "dynamic" part.

 Assuming that what I have said above is correct (I'm open to any
 corrections!), then I can't see why the variadic delegate example I used
 earlier would not work.

 Tony
 Melbourne, Australia


 The problem here is that sometimes you don't want the compiler to make a
 copy of 'n'.  I have written code that looks like this before:

 int foo() {
    int i = 0;
    bar(delegate void() { i++; });
    return i;
 }

 void bar(void delegate() dg) {
    <do stuff>
    <call dg() some amount of times>
    return;
 }

 In the above code, of course, we want the delegate to be using the
 original 'i', not a copy.

 The question, of course, is why doesn't the compiler automatically do
 the right thing - make a copy when needed, and don't when it's not?  The
 problem, of course, is that it's not possible for the compiler to know
 which is the right thing, at least not in all cases.  See my response to
 Manfred in this same thread for a discussion of that.
Jul 06 2005
prev sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Russ Lewis <spamhole-2001-07-16 deming-os.org> wrote:
[...]

 You can't return a delegate literal, like you do in setup()
 here, if that delegate literal uses any stack variables.  That's
 because, as soon as you return from the function, the stack
 variable becomes invalid.


[...]

As your reasoning shows the compiler should be able to conclude the 
same thing on its own, but it does not.

I do not see the deeper reason why the compiler has to act this way. 
Would you pleas egive me a hint.

-manfred
Jul 05 2005
parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Manfred Nowak wrote:

 Russ Lewis <spamhole-2001-07-16 deming-os.org> wrote:
 [...]
 

You can't return a delegate literal, like you do in setup()
here, if that delegate literal uses any stack variables.  That's
because, as soon as you return from the function, the stack
variable becomes invalid.


 
 [...]
 
 As your reasoning shows the compiler should be able to conclude the 
 same thing on its own, but it does not.
 
 I do not see the deeper reason why the compiler has to act this way. 
 Would you pleas egive me a hint.
 
 -manfred


Let's first think about what has to be done, then I'll explain why I 
think it's problematic for the compiler to do this automatically.  Then 
I'll explain what I think would be the "Right Way" compiler feature to 
handle such circumstances.

Basically, if you want to return a delegate literal which can reference 
stack variables, you have to make a copy of the stack variables on the heap.

It's not clear when the copy should be made.  Should the copy be made 
when the delegate is created, or when the function starts, or some other 
time?  At first blush, you might think that it wouldn't matter, but what 
happens if you have code like this:
   int delegate() foo(int a,int b,int c) {
     return bar(delegate int() {...}, &c);
   }
   int delegate() bar(int delegate() arg, int *c) {
     (*c)++;
     return arg;
   }
So should the copied version of the delegate get the modified version of 
c or not?

Second, in order for the compiler to do this automatically, you have to 
assume that the compiler is going to analyze the full chain of all calls 
and figure out in what cases a delegate literal might be returned. 
Imagine this code:
   int delegate() baz(int a,int b,int c) {
     return fred(delegate int() {...});
   }
Is the delegate literal here the same thing that is returned?  You don't 
know, unless you expect the compiler to analyze fred() completely.  What 
if fred() converts the delegate to a pair of pointers (a function 
pointer and a void* pointer, probably), and calls into a C library to 
which we have no visibility?  Further assume that the C library returns 
another function pointer and another void* pointer, and fred() 
constructs a new delegate and returns that.  Is the new delegate the 
same as the old?  Does it reference the old?  We can't expect the D 
compiler to know.

Therefore, (as I have suggested before), it seems to me that the "Right 
Way" to do this is to have a syntax which allows you to make a copy of 
the stack frame at a very specific point in time, and then to define a 
delegate from that.  My suggested syntax is/was:
   int delegate() wilma(int a,int b,int c) {
     return stack_frame.dup.delegate int() {...};
   }
But I don't know if this syntax (or equivalent functionality) will ever 
make it into the official D language.

Russ
Jul 05 2005