www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - The future of lambda delegates

reply "Mikola Lysenko" <mclysenk mtu.edu> writes:
D's delegates are great.  They are vastly superior to C++'s confused 
pointer-to-member functions, and much more useful than Java's adapter 
classes.  In the world of system programs, nothing comes close.  One 
interesting type of delegate is the anonymous-nested-delegate-literal, or 
"lambda" delegate.  For those unacquainted with such niceties, here are the 
documentation links:
http://www.digitalmars.com/d/function.html#nested
http://www.digitalmars.com/d/expression.html#FunctionLiteral

Recent D releases (notably 0.161) have updated the syntax and improved the 
overall usability of lambda delegates. All the syntactic sugar is nice, but 
it also lays a few traps for the unwary.  Here is a simple example:

// The Fibonacci numbers are an integer sequence such that
//        F(n) = F(n - 1) + F(n - 2)
//        And F(0) = 0, F(1) = 1
int delegate() fibs()
{
    int a = 0;            // Initialize the last two terms of the Fibonacci 
sequence
    int b = 1;

    return
    {
        int c = a + b;     // Calculate the next term in the sequence
        a = b;               // Shift the previous terms back
        b = c;
        return c;            // Return the result
    };
}

This function returns a function which will sequentially evaluate all of the 
Fibonacci numbers.  Notice that the inner delegate modifies the variables a 
and b in fibs() scope.  Because of this, it is not guaranteed to work after 
fibs returns.  This is most irritating, and it greatly restricts the use of 
this technique. Another potential use for lambda delegates is to create 
one-line adapter methods.  Consider the following attempt to create a button 
which will display an arbitrary message when clicked:

Button createButton(char[] click_msg)
{
    Button b = new Button();
    b.mouseClickCallback = { MsgBox(click_msg); };
    return b;
}

Once more, this sort of method relies on access to the outer function scope 
from within the lambda delegate.  Given the current semantics, this code is 
doomed to fail in any number of random ways.  As a final example, suppose we 
want to perform a lengthy calculation in a separate thread, and only wait 
for the value once it is needed.  In this case, one could try to do the 
following:

int[] delegate() sort_threaded(int[] array)
{
    int[] result = array.dup;

    //Create and run a worker thread to perform an expensive operation, (in 
this case a sort)
    Thread tsort = new Thread(
     {
        result.sort;
        return 0;
     });
    tsort.start();

    //The returned lambda delegate waits for the thread's calculation to 
finish, then returns the result.
    return { tsort.wait; return result; };
}

In this situation, we can let the thread execute in the background while the 
program performs other tasks, and only wait for the result once we need it. 
This type of deferred calculation can be very useful for improving the 
amount of parallelism within an application without adding much 
synchronization overhead.  It is very sad that none of these examples work, 
since there are so many nice solutions just like them.

One possible solution is to allocate the frame for each function containing 
nested-functions on the heap.  This allows any returned delegates to use the 
member variables freely.  One could think of it as translating the function 
into a class with a thunk.  Here is above Fibonacci function rewritten in 
this way:

class fibs_
{
    int a = 0;
    int b = 1;

    int lambda1()
    {
        int c = a + b;
        a = b;
        b = c;
        return c;
    }

    int delegate() func()
    {
        return &lambda1;
    }
}

int delegate() fibs()
{
    return (new fibs_()).func();
}

Such a translation is possible for any of these examples, albeit quite 
tedious.  From what I gather C# applies a similar technique with its lambda 
delegates and inner classes.  For a machine code compiler, such a rewrite is 
not even necessary, since it could simply overwrite the frame pointer at the 
start of the function with a GC allocated block.  This would preserve 
frame-based addressing for arguments and variables, requiring no change in 
any of the internally generated machine code.  The run time overhead is 
fairly low, only on the order of one extra memory allocation per function 
call.  Practically, such an implementation would be extremely simple.

Any thoughts or comments?

-Mikola Lysenko 
Aug 16 2006
next sibling parent Lars Ivar Igesund <larsivar igesund.net> writes:
Mikola Lysenko wrote:

 D's delegates are great.  They are vastly superior to C++'s confused
 pointer-to-member functions, and much more useful than Java's adapter
 classes.  In the world of system programs, nothing comes close.  One
 interesting type of delegate is the anonymous-nested-delegate-literal, or
 "lambda" delegate.  For those unacquainted with such niceties, here are
 the documentation links:
 http://www.digitalmars.com/d/function.html#nested
 http://www.digitalmars.com/d/expression.html#FunctionLiteral
 
 Recent D releases (notably 0.161) have updated the syntax and improved the
 overall usability of lambda delegates. All the syntactic sugar is nice,
 but
 it also lays a few traps for the unwary.  Here is a simple example:
 
 // The Fibonacci numbers are an integer sequence such that
 //        F(n) = F(n - 1) + F(n - 2)
 //        And F(0) = 0, F(1) = 1
 int delegate() fibs()
 {
     int a = 0;            // Initialize the last two terms of the
     Fibonacci
 sequence
     int b = 1;
 
     return
     {
         int c = a + b;     // Calculate the next term in the sequence
         a = b;               // Shift the previous terms back
         b = c;
         return c;            // Return the result
     };
 }
 
 This function returns a function which will sequentially evaluate all of
 the
 Fibonacci numbers.  Notice that the inner delegate modifies the variables
 a
 and b in fibs() scope.  Because of this, it is not guaranteed to work
 after
 fibs returns.  This is most irritating, and it greatly restricts the use
 of this technique. Another potential use for lambda delegates is to create
 one-line adapter methods.  Consider the following attempt to create a
 button which will display an arbitrary message when clicked:
 
 Button createButton(char[] click_msg)
 {
     Button b = new Button();
     b.mouseClickCallback = { MsgBox(click_msg); };
     return b;
 }
 
 Once more, this sort of method relies on access to the outer function
 scope
 from within the lambda delegate.  Given the current semantics, this code
 is
 doomed to fail in any number of random ways.  As a final example, suppose
 we want to perform a lengthy calculation in a separate thread, and only
 wait
 for the value once it is needed.  In this case, one could try to do the
 following:
 
 int[] delegate() sort_threaded(int[] array)
 {
     int[] result = array.dup;
 
     //Create and run a worker thread to perform an expensive operation,
     (in
 this case a sort)
     Thread tsort = new Thread(
      {
         result.sort;
         return 0;
      });
     tsort.start();
 
     //The returned lambda delegate waits for the thread's calculation to
 finish, then returns the result.
     return { tsort.wait; return result; };
 }
 
 In this situation, we can let the thread execute in the background while
 the program performs other tasks, and only wait for the result once we
 need it. This type of deferred calculation can be very useful for
 improving the amount of parallelism within an application without adding
 much
 synchronization overhead.  It is very sad that none of these examples
 work, since there are so many nice solutions just like them.
 
 One possible solution is to allocate the frame for each function
 containing
 nested-functions on the heap.  This allows any returned delegates to use
 the
 member variables freely.  One could think of it as translating the
 function
 into a class with a thunk.  Here is above Fibonacci function rewritten in
 this way:
 
 class fibs_
 {
     int a = 0;
     int b = 1;
 
     int lambda1()
     {
         int c = a + b;
         a = b;
         b = c;
         return c;
     }
 
     int delegate() func()
     {
         return &lambda1;
     }
 }
 
 int delegate() fibs()
 {
     return (new fibs_()).func();
 }
 
 Such a translation is possible for any of these examples, albeit quite
 tedious.  From what I gather C# applies a similar technique with its
 lambda
 delegates and inner classes.  For a machine code compiler, such a rewrite
 is not even necessary, since it could simply overwrite the frame pointer
 at the
 start of the function with a GC allocated block.  This would preserve
 frame-based addressing for arguments and variables, requiring no change in
 any of the internally generated machine code.  The run time overhead is
 fairly low, only on the order of one extra memory allocation per function
 call.  Practically, such an implementation would be extremely simple.
 
 Any thoughts or comments?
 
 -Mikola Lysenko

I agree that the current spec allows you to very easily write very elegant code that will be broken. Your proposed solution seems to me to be a well thought out (and acceptable) solution to make them actually work (and keep D as a language ahead of the pack, as the other alternatives most probably are to either create not-so-elegant syntax, or disallow them altogether). -- Lars Ivar Igesund blog at http://larsivi.net DSource & #D: larsivi
Aug 16 2006
prev sibling next sibling parent BCS <BCS pathlink.com> writes:
Mikola Lysenko wrote:
[...]
 All the syntactic sugar is nice, but 
 it also lays a few traps for the unwary.

 Another potential use for lambda delegates is to create 
 one-line adapter methods.  Consider the following attempt to create a button 
 which will display an arbitrary message when clicked:
 
 Button createButton(char[] click_msg)
 {
     Button b = new Button();
     b.mouseClickCallback = { MsgBox(click_msg); };
     return b;
 }
 

 As a final example, suppose we 
 want to perform a lengthy calculation in a separate thread, and only wait 
 for the value once it is needed.  In this case, one could try to do the 
 following:
 
 int[] delegate() sort_threaded(int[] array)
 {
     int[] result = array.dup;
 
     //Create and run a worker thread to perform an expensive operation, (in 
 this case a sort)
     Thread tsort = new Thread(
      {
         result.sort;
         return 0;
      });
     tsort.start();
 
     //The returned lambda delegate waits for the thread's calculation to 
 finish, then returns the result.
     return { tsort.wait; return result; };
 }
 

 It is very sad that none of these examples work, 
 since there are so many nice solutions just like them.
 
 One possible solution is to allocate the frame for each function containing 
 nested-functions on the heap.  

 Such a translation is possible for any of these examples, albeit quite 
 tedious.  

 
 Any thoughts or comments?
 
 -Mikola Lysenko 
 
 

Interesting ideas, however using a struct rather than a class would be faster. Maybe what is needed is some way to define the context pointer of a delegate literal. int[] delegate() sort_threaded(int[] array) { auto foo = new struct // this might need new syntax { int[] result; Thread tsort; }; with(foo) { result = array.dup; // delegate with alt context tsort = new Thread(foo.{ result.sort; return 0; }); tsort.start(); } // delegate with alt context return foo.{ // array[0]; // not in scope tsort.wait; return result; }; } This would also work on another of the examples: Button createButton(char[] click_msg) { Button b = new Button(); b.mouseClickCallback = click_msg.{ MsgBox(this); }; return b; } for the first example some sort of joining of the anon struct deceleration and with statement might make this vary elegant int[] delegate() sort_threaded(int[] array) { // (using mixin for lack of a better syntax) // inject these into the namespace, //but put them on the heep mixin foo = new struct { int[] result; Thread tsort; }; result = array.dup; tsort = new Thread(foo.{ result.sort; return 0; }); tsort.start(); return foo.{ tsort.wait; return result; }; }
Aug 16 2006
prev sibling next sibling parent reply kris <foo bar.com> writes:
Mikola Lysenko wrote:
 D's delegates are great.  They are vastly superior to C++'s confused 
 pointer-to-member functions, and much more useful than Java's adapter 
 classes.  In the world of system programs, nothing comes close.  One 
 interesting type of delegate is the anonymous-nested-delegate-literal, or 
 "lambda" delegate.  For those unacquainted with such niceties, here are the 
 documentation links:
 http://www.digitalmars.com/d/function.html#nested
 http://www.digitalmars.com/d/expression.html#FunctionLiteral
 
 Recent D releases (notably 0.161) have updated the syntax and improved the 
 overall usability of lambda delegates. All the syntactic sugar is nice, but 
 it also lays a few traps for the unwary.  Here is a simple example:
 
 // The Fibonacci numbers are an integer sequence such that
 //        F(n) = F(n - 1) + F(n - 2)
 //        And F(0) = 0, F(1) = 1
 int delegate() fibs()
 {
     int a = 0;            // Initialize the last two terms of the Fibonacci 
 sequence
     int b = 1;
 
     return
     {
         int c = a + b;     // Calculate the next term in the sequence
         a = b;               // Shift the previous terms back
         b = c;
         return c;            // Return the result
     };
 }
 
 This function returns a function which will sequentially evaluate all of the 
 Fibonacci numbers.  Notice that the inner delegate modifies the variables a 
 and b in fibs() scope.  Because of this, it is not guaranteed to work after 
 fibs returns.  This is most irritating, and it greatly restricts the use of 
 this technique. Another potential use for lambda delegates is to create 
 one-line adapter methods.  Consider the following attempt to create a button 
 which will display an arbitrary message when clicked:
 
 Button createButton(char[] click_msg)
 {
     Button b = new Button();
     b.mouseClickCallback = { MsgBox(click_msg); };
     return b;
 }
 
 Once more, this sort of method relies on access to the outer function scope 
 from within the lambda delegate.  Given the current semantics, this code is 
 doomed to fail in any number of random ways.  As a final example, suppose we 
 want to perform a lengthy calculation in a separate thread, and only wait 
 for the value once it is needed.  In this case, one could try to do the 
 following:
 
 int[] delegate() sort_threaded(int[] array)
 {
     int[] result = array.dup;
 
     //Create and run a worker thread to perform an expensive operation, (in 
 this case a sort)
     Thread tsort = new Thread(
      {
         result.sort;
         return 0;
      });
     tsort.start();
 
     //The returned lambda delegate waits for the thread's calculation to 
 finish, then returns the result.
     return { tsort.wait; return result; };
 }
 
 In this situation, we can let the thread execute in the background while the 
 program performs other tasks, and only wait for the result once we need it. 
 This type of deferred calculation can be very useful for improving the 
 amount of parallelism within an application without adding much 
 synchronization overhead.  It is very sad that none of these examples work, 
 since there are so many nice solutions just like them.
 
 One possible solution is to allocate the frame for each function containing 
 nested-functions on the heap.  This allows any returned delegates to use the 
 member variables freely.  One could think of it as translating the function 
 into a class with a thunk.  Here is above Fibonacci function rewritten in 
 this way:
 
 class fibs_
 {
     int a = 0;
     int b = 1;
 
     int lambda1()
     {
         int c = a + b;
         a = b;
         b = c;
         return c;
     }
 
     int delegate() func()
     {
         return &lambda1;
     }
 }
 
 int delegate() fibs()
 {
     return (new fibs_()).func();
 }
 
 Such a translation is possible for any of these examples, albeit quite 
 tedious.  From what I gather C# applies a similar technique with its lambda 
 delegates and inner classes.  For a machine code compiler, such a rewrite is 
 not even necessary, since it could simply overwrite the frame pointer at the 
 start of the function with a GC allocated block.  This would preserve 
 frame-based addressing for arguments and variables, requiring no change in 
 any of the internally generated machine code.  The run time overhead is 
 fairly low, only on the order of one extra memory allocation per function 
 call.  Practically, such an implementation would be extremely simple.
 
 Any thoughts or comments?
 
 -Mikola Lysenko 
 
 

Yeah, this is a serious trap for the unwary and, unfortunately, prohibits the use of such delegates in the one place where the elegance would be most notable: as gui callbacks, per your example. As you say, the way around it (currently) is to create a class to house the 'scope' content, or otherwise refer to it. That's unweildy, even with anonymous-class syntax. If, as you suggest, D had some means to indicate that the scope should be placed on the heap instead of the stack, it would resolve the concern nicely. Perhaps that indication might be lambda syntax itself? For example, in C# the lambda indicator is the symbol '=>' Either way, if D could safely utilize lambda delegates for, say, gui work (or any design based around callbacks) it would be immediately noticable as both an elegant solution & a big step up from C++ Good idea, Mikola
Aug 16 2006
parent reply Oskar Linde <olREM OVEnada.kth.se> writes:
kris wrote:

 Yeah, this is a serious trap for the unwary and, unfortunately,
 prohibits the use of such delegates in the one place where the elegance
 would be most notable: as gui callbacks, per your example. As you say,
 the way around it (currently) is to create a class to house the 'scope'
 content, or otherwise refer to it. That's unweildy, even with
 anonymous-class syntax.
 
 If, as you suggest, D had some means to indicate that the scope should
 be placed on the heap instead of the stack, it would resolve the concern
 nicely. Perhaps that indication might be lambda syntax itself? For
 example, in C# the lambda indicator is the symbol '=>'

I don't think any special syntax is needed. I believe the compiler could be able to automatically identify whether a function may have escaping delegates referring to local variables. /Oskar
Aug 16 2006
parent reply kris <foo bar.com> writes:
Oskar Linde wrote:
 kris wrote:
 
 
Yeah, this is a serious trap for the unwary and, unfortunately,
prohibits the use of such delegates in the one place where the elegance
would be most notable: as gui callbacks, per your example. As you say,
the way around it (currently) is to create a class to house the 'scope'
content, or otherwise refer to it. That's unweildy, even with
anonymous-class syntax.

If, as you suggest, D had some means to indicate that the scope should
be placed on the heap instead of the stack, it would resolve the concern
nicely. Perhaps that indication might be lambda syntax itself? For
example, in C# the lambda indicator is the symbol '=>'

I don't think any special syntax is needed. I believe the compiler could be able to automatically identify whether a function may have escaping delegates referring to local variables. /Oskar

Yes, that's certainly one way. But the suggestion was to "take advantage" of an even simpler form of lambda delegates; one that C# 3.0 is moving toward. It's worth taking a look at, just for comparitive purposes? Two random links: http://www.interact-sw.co.uk/iangblog/2005/09/30/expressiontrees http://www.developer.com/net/csharp/article.php/3598381 On the other hand, one of the great things about the D compiler is it's voracious speed. If it turns out that automagically trying to figure out where the 'escapees' are will noticably slow the compiler down, then a bit of syntactic sugar might make all the difference :)
Aug 16 2006
parent reply Oskar Linde <olREM OVEnada.kth.se> writes:
kris wrote:

 Oskar Linde wrote:
 kris wrote:
 
 
Yeah, this is a serious trap for the unwary and, unfortunately,
prohibits the use of such delegates in the one place where the elegance
would be most notable: as gui callbacks, per your example. As you say,
the way around it (currently) is to create a class to house the 'scope'
content, or otherwise refer to it. That's unweildy, even with
anonymous-class syntax.

If, as you suggest, D had some means to indicate that the scope should
be placed on the heap instead of the stack, it would resolve the concern
nicely. Perhaps that indication might be lambda syntax itself? For
example, in C# the lambda indicator is the symbol '=>'

I don't think any special syntax is needed. I believe the compiler could be able to automatically identify whether a function may have escaping delegates referring to local variables.


I felt kind of stupid after posting this and finding out that everything (and much more) had already been posted two hours earlier.
 Yes, that's certainly one way. But the suggestion was to "take
 advantage" of an even simpler form of lambda delegates; one that C# 3.0
 is moving toward. It's worth taking a look at, just for comparitive
 purposes? Two random links:
 
 http://www.interact-sw.co.uk/iangblog/2005/09/30/expressiontrees
 http://www.developer.com/net/csharp/article.php/3598381

Interesting. I always found the original D delegate syntax a bit too wordy, and with the new delegate syntax, I think many of us noticed how a little difference in typing overhead and clarity made the language feature much more compelling. The reason is probably purely psychological, but the result is there. Anyway, if you give a mouse a cookie... :) If you want named and typed delegate arguments and a void return type, the current syntax is probably close to optimal, but most of the delegates I write are single expression functions. I think it is for those the C#3.0 lambda expression syntax was conceived. What in D is: (int a, int b) { return a + b; } is in C#: (a, b) => a + b; You could theoretically go further if you were willing to accept anonymous arguments. Something like: $1 + $2 And some languages would even accept: '+ While I really like how the short, concise C# lambda expression syntax looks, I can't help but feel it is out of style with the rest of the language. (It is probably just a very temporary feeling though). The => brings two features D's delegates doesn't have. 1. The short form for the single expression case. 2. Implicitly typed arguments. #1 is the easy part. #2 is not.
 On the other hand, one of the great things about the D compiler is it's
 voracious speed. If it turns out that automagically trying to figure out
 where the 'escapees' are will noticably slow the compiler down, then a
 bit of syntactic sugar might make all the difference :)

From what little I know of compiler construction, escape analysis is something that is done to all variables anyways. My guess is that most delegate literals will end up escaping in some way or another, with the most common case being passed as arguments to an external function. The problem here is that the compiler can never know if that function intents to keep the delegate reference till after the instantiating function has returned. Finding out which local or enclosing variables are referred to by escaping delegates can't be that much harder, so I doubt compilation speed is an issue. What could be an issue though is the fact that the compiler defensively would have to heap allocate all variables any escaping delegates refer to even though they in many cases never would be referenced after the enclosing function returns. What could improve things is if there was a no-immigrants (only visitors) declaration for function arguments that guaranteed that any escaping delegate passed to one such function argument would never be stored after that function returns or be passed as argument to any other immigration friendly function: void update(int[] arr, visitor void delegate(inout int a) updater) { foreach(inout i;arr) updater(i); } ... int b = ...; myarr.update((inout int a) { a += b; }); // would not count as an escape and would not need b to be stack allocated /Oskar
Aug 16 2006
next sibling parent Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Oskar Linde wrote:
 
 What could improve things is if there was a no-immigrants (only visitors)
 declaration for function arguments that guaranteed that any escaping
 delegate passed to one such function argument would never be stored after
 that function returns or be passed as argument to any other immigration
 friendly function:
 
 void update(int[] arr, visitor void delegate(inout int a) updater) {
         foreach(inout i;arr)
                 updater(i);
 }
 
 ....
 int b = ...; 
 myarr.update((inout int a) { a += b; }); 
 // would not count as an escape and would not need b to be stack allocated
 
 /Oskar
 

Whoa... if I'm not mistaken that is kinda like the converse of const(read-only): it is a write-only (or use-only) variable. It's value cannot be read (at least directly) : mydg = updater; // cannot be read! updater(i); // but can use; updater = xpto; // and can assign to? :D -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 16 2006
prev sibling parent kris <foo bar.com> writes:
Oskar Linde wrote:
 kris wrote:
 
 
Oskar Linde wrote:

kris wrote:



Yeah, this is a serious trap for the unwary and, unfortunately,
prohibits the use of such delegates in the one place where the elegance
would be most notable: as gui callbacks, per your example. As you say,
the way around it (currently) is to create a class to house the 'scope'
content, or otherwise refer to it. That's unweildy, even with
anonymous-class syntax.

If, as you suggest, D had some means to indicate that the scope should
be placed on the heap instead of the stack, it would resolve the concern
nicely. Perhaps that indication might be lambda syntax itself? For
example, in C# the lambda indicator is the symbol '=>'

I don't think any special syntax is needed. I believe the compiler could be able to automatically identify whether a function may have escaping delegates referring to local variables.


I felt kind of stupid after posting this and finding out that everything (and much more) had already been posted two hours earlier.
Yes, that's certainly one way. But the suggestion was to "take
advantage" of an even simpler form of lambda delegates; one that C# 3.0
is moving toward. It's worth taking a look at, just for comparitive
purposes? Two random links:

http://www.interact-sw.co.uk/iangblog/2005/09/30/expressiontrees
http://www.developer.com/net/csharp/article.php/3598381

Interesting. I always found the original D delegate syntax a bit too wordy, and with the new delegate syntax, I think many of us noticed how a little difference in typing overhead and clarity made the language feature much more compelling. The reason is probably purely psychological, but the result is there. Anyway, if you give a mouse a cookie... :) If you want named and typed delegate arguments and a void return type, the current syntax is probably close to optimal, but most of the delegates I write are single expression functions. I think it is for those the C#3.0 lambda expression syntax was conceived. What in D is: (int a, int b) { return a + b; } is in C#: (a, b) => a + b; You could theoretically go further if you were willing to accept anonymous arguments. Something like: $1 + $2 And some languages would even accept: '+ While I really like how the short, concise C# lambda expression syntax looks, I can't help but feel it is out of style with the rest of the language. (It is probably just a very temporary feeling though). The => brings two features D's delegates doesn't have. 1. The short form for the single expression case. 2. Implicitly typed arguments. #1 is the easy part. #2 is not.
On the other hand, one of the great things about the D compiler is it's
voracious speed. If it turns out that automagically trying to figure out
where the 'escapees' are will noticably slow the compiler down, then a
bit of syntactic sugar might make all the difference :)

From what little I know of compiler construction, escape analysis is something that is done to all variables anyways. My guess is that most delegate literals will end up escaping in some way or another, with the most common case being passed as arguments to an external function. The problem here is that the compiler can never know if that function intents to keep the delegate reference till after the instantiating function has returned. Finding out which local or enclosing variables are referred to by escaping delegates can't be that much harder, so I doubt compilation speed is an issue. What could be an issue though is the fact that the compiler defensively would have to heap allocate all variables any escaping delegates refer to even though they in many cases never would be referenced after the enclosing function returns. What could improve things is if there was a no-immigrants (only visitors) declaration for function arguments that guaranteed that any escaping delegate passed to one such function argument would never be stored after that function returns or be passed as argument to any other immigration friendly function: void update(int[] arr, visitor void delegate(inout int a) updater) { foreach(inout i;arr) updater(i); } ... int b = ...; myarr.update((inout int a) { a += b; }); // would not count as an escape and would not need b to be stack allocated /Oskar

aye ... we posted similar concerns and solutions :)
Aug 16 2006
prev sibling next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Mikola Lysenko wrote:
 Such a translation is possible for any of these examples, albeit quite 
 tedious.  From what I gather C# applies a similar technique with its lambda 
 delegates and inner classes.  For a machine code compiler, such a rewrite is 
 not even necessary, since it could simply overwrite the frame pointer at the 
 start of the function with a GC allocated block.  This would preserve 
 frame-based addressing for arguments and variables, requiring no change in 
 any of the internally generated machine code.  The run time overhead is 
 fairly low, only on the order of one extra memory allocation per function 
 call.  Practically, such an implementation would be extremely simple.
 
 Any thoughts or comments?

Yes, I'm aware of this, and want to fix it for D 2.0. The way to fix it is, as you suggest, allocating the frame on the heap rather than on the stack. The drawback with that is that heap allocation is far, far more expensive than stack allocation. An ideal solution would be if the compiler could statically detect if a nested class reference can 'escape' the stack frame, and only then allocate on the heap. Otherwise, the current (very efficient) method of just passing a frame pointer would be employed. Of course, then there's the problem of nested functions within nested functions, that then escape and try to reference multiple nesting levels back on the stack.
Aug 16 2006
next sibling parent reply BCS <BCS pathlink.com> writes:
Walter Bright wrote:
 Mikola Lysenko wrote:
 
 Such a translation is possible for any of these examples, albeit quite 
 tedious.  From what I gather C# applies a similar technique with its 
 lambda delegates and inner classes.  For a machine code compiler, such 
 a rewrite is not even necessary, since it could simply overwrite the 
 frame pointer at the start of the function with a GC allocated block.  
 This would preserve frame-based addressing for arguments and 
 variables, requiring no change in any of the internally generated 
 machine code.  The run time overhead is fairly low, only on the order 
 of one extra memory allocation per function call.  Practically, such 
 an implementation would be extremely simple.

 Any thoughts or comments?

Yes, I'm aware of this, and want to fix it for D 2.0. The way to fix it is, as you suggest, allocating the frame on the heap rather than on the stack. The drawback with that is that heap allocation is far, far more expensive than stack allocation.

because this is so much slower, I would hate to see it happen silently. Having a function use a heap-frame just because I add a delegate could cause some hard to track down performance hits. I would advocate making the escaping delegate illegal unless the code explicitly says to put /part/ or all of the frame on the heap.
 
 An ideal solution would be if the compiler could statically detect if a 
 nested class reference can 'escape' the stack frame, and only then 
 allocate on the heap. Otherwise, the current (very efficient) method of 
 just passing a frame pointer would be employed.
 

BTW how do you construct a delegate literal inside of a class method that uses "this" as it's context, rather than the frame pointer? class Foo { int i; int delegate() fig(){ return {return i;}; } // int delegate() fig(){ return this.{return i;}; } // this maybe? } void main() { auto foo = new Foo; auto farm = foo.fig; foo.i = 5; auto i = farm(); // valid if context is "foo" assert(i == 5); }
Aug 16 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
BCS wrote:
 BTW how do you construct a delegate literal inside of a class method 
 that uses "this" as it's context, rather than the frame pointer?
 
 class Foo
 {
     int i;
     int delegate() fig(){ return {return i;}; }

It uses the frame pointer of fig() to access fig()'s this. Of course, though, this will currently fail because fig() is exited before the delegate is called.
 //    int delegate() fig(){ return this.{return i;}; }  // this maybe?
 }
 
 void main()
 {
     auto foo = new Foo;
     auto farm = foo.fig;
 
     foo.i = 5;
     auto i = farm(); // valid if context is "foo"
     assert(i == 5);
 }

Aug 16 2006
parent reply BCS <BCS pathlink.com> writes:
Walter Bright wrote:
 BCS wrote:
 
 BTW how do you construct a delegate literal inside of a class method 
 that uses "this" as it's context, rather than the frame pointer?

 class Foo
 {
     int i;
     int delegate() fig(){ return {return i;}; }

It uses the frame pointer of fig() to access fig()'s this. Of course, though, this will currently fail because fig() is exited before the delegate is called.

a.k.a. It can't be done?
 //    int delegate() fig(){ return this.{return i;}; }  // this maybe?
 }

 void main()
 {
     auto foo = new Foo;
     auto farm = foo.fig;

     foo.i = 5;
     auto i = farm(); // valid if context is "foo"
     assert(i == 5);
 }


Aug 16 2006
parent Walter Bright <newshound digitalmars.com> writes:
BCS wrote:
 Walter Bright wrote:
 BCS wrote:

 BTW how do you construct a delegate literal inside of a class method 
 that uses "this" as it's context, rather than the frame pointer?

 class Foo
 {
     int i;
     int delegate() fig(){ return {return i;}; }

It uses the frame pointer of fig() to access fig()'s this. Of course, though, this will currently fail because fig() is exited before the delegate is called.

a.k.a. It can't be done?

It's the same problem as elsewhere returning a delegate that accesses the frame of the function that returns it.
Aug 16 2006
prev sibling parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
BCS wrote:

 because this is so much slower, I would hate to see it happen silently. 
 Having a function use a heap-frame just because I add a delegate could 
 cause some hard to track down performance hits. I would advocate making 
 the escaping delegate illegal unless the code explicitly says to put 
 /part/ or all of the frame on the heap.

Wow, the concept of putting only *part* of the frame on the heap really blew my mind. It suggests the following syntax: void foo() { int a; // on stack heap { // all variables in this scope on the heap ...stuff... } }
Aug 24 2006
prev sibling next sibling parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 Mikola Lysenko wrote:
 Such a translation is possible for any of these examples, albeit quite 
 tedious.  From what I gather C# applies a similar technique with its 
 lambda delegates and inner classes.  For a machine code compiler, such 
 a rewrite is not even necessary, since it could simply overwrite the 
 frame pointer at the start of the function with a GC allocated block.  
 This would preserve frame-based addressing for arguments and 
 variables, requiring no change in any of the internally generated 
 machine code.  The run time overhead is fairly low, only on the order 
 of one extra memory allocation per function call.  Practically, such 
 an implementation would be extremely simple.

 Any thoughts or comments?

Yes, I'm aware of this, and want to fix it for D 2.0. The way to fix it is, as you suggest, allocating the frame on the heap rather than on the stack. The drawback with that is that heap allocation is far, far more expensive than stack allocation.

In the general case, yes, but it doesn't have to be. An allocator with per-thread heaps could allocate without the need for a mutex, and special cases like this could force an allocation if the heap is full instead of triggering a collection. That said, I agree with your motivation here.
 An ideal solution would be if the compiler could statically detect if a 
 nested class reference can 'escape' the stack frame, and only then 
 allocate on the heap. Otherwise, the current (very efficient) method of 
 just passing a frame pointer would be employed.

Agreed. As well as detect whether the delegates reference any local stack data in the first place. The alternative would be to use a separate keyword for these delegates, 'closure' or 'lambda' or some such, but that's potentially confusing, and leaves anonymous delegates in an odd position.
 Of course, then there's the problem of nested functions within nested 
 functions, that then escape and try to reference multiple nesting levels 
 back on the stack.

I would expect the compiler to just put as much data on the heap as necessary, be it for a single nesting level or for multiple levels. I suppose it would be ideal for this to be contiguous, but it wouldn't have to be. I grant that the code generation may be a bit of a pain, but it doesn't sound impossible. Sean
Aug 16 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:
 The alternative would be to use a 
 separate keyword for these delegates, 'closure' or 'lambda' or some 
 such, but that's potentially confusing, and leaves anonymous delegates 
 in an odd position.

I *really* want to avoid having to do this. It's almost guaranteed that it'll be a rich source of bugs.
Aug 16 2006
parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 Sean Kelly wrote:
 The alternative would be to use a separate keyword for these 
 delegates, 'closure' or 'lambda' or some such, but that's potentially 
 confusing, and leaves anonymous delegates in an odd position.

I *really* want to avoid having to do this. It's almost guaranteed that it'll be a rich source of bugs.

As an alternative, since it's really how the delegate is used that's at issue, perhaps the programmer could simply be given a way to manually "archive" the stack frame used by a delegate if he knows it will need to be called asynchronously? From the original example: Button createButton(char[] click_msg) { Button b = new Button(); b.mouseClickCallback = { MsgBox(click_msg); }; return b; } Let's assume mouseClickCallback is written like so: void mouseClickCallback( void delegate() dg ) { clickHandler = dg; } Following my suggestion, it would be changed to this: void mouseClickCallback( void delegate() dg ) { dg.archive; clickHandler = dg; } The archive routine would check dg's stack frame to see if a heap copy of the frame exists (assume it's stored as a pointer at this[0]). If not then memory is allocated, the pointer is set, the frame is copied, and dg's 'this' pointer is updated to refer to the dynamic frame. Returning a delegate from a function would just implicitly call this 'archive' routine. This could still cause errors, as a programmer may forget to call "dg.archive" before storing the delegate, but I think this is an acceptable risk and is far better than having the compiler try to "figure out" whether such a dynamic allocation is needed. It also seems fairly easy to implement compared to the alternatives, and offering the feature through a property method would eliminate the need for a new keyword. Sean
Aug 16 2006
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 Sean Kelly wrote:
 The alternative would be to use a separate keyword for these 
 delegates, 'closure' or 'lambda' or some such, but that's potentially 
 confusing, and leaves anonymous delegates in an odd position.

I *really* want to avoid having to do this. It's almost guaranteed that it'll be a rich source of bugs.

As an alternative, since it's really how the delegate is used that's at issue, perhaps the programmer could simply be given a way to manually "archive" the stack frame used by a delegate if he knows it will need to be called asynchronously?

Upon further reflection (and some helpful criticism) this doesn't seem like it may not work so well with delegates from structs and classes. But I do like the general idea better than that of flagging the delegates upon declaration or something like that. I don't suppose the idea could be somehow refined to eliminate these problems? Sean
Aug 16 2006
parent Sean Kelly <sean f4.ca> writes:
Sean Kelly wrote:
 
 Upon further reflection (and some helpful criticism) this doesn't seem 
 like it may not work so well with delegates from structs and classes. 
 But I do like the general idea better than that of flagging the 
 delegates upon declaration or something like that.  I don't suppose the 
 idea could be somehow refined to eliminate these problems?

Forget I suggested this idea :-p I forgot about problems like self-referent stack data and such where a simple copy wouldn't work. Not to mention that the surrounding function may not return right away and would be working on a different copy of the data than any delegates it may have passed. Sean
Aug 16 2006
prev sibling next sibling parent reply pragma <ericanderton yahoo.com> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 Sean Kelly wrote:
 The alternative would be to use a separate keyword for these 
 delegates, 'closure' or 'lambda' or some such, but that's potentially 
 confusing, and leaves anonymous delegates in an odd position.

I *really* want to avoid having to do this. It's almost guaranteed that it'll be a rich source of bugs.

As an alternative, since it's really how the delegate is used that's at issue, perhaps the programmer could simply be given a way to manually "archive" the stack frame used by a delegate if he knows it will need to be called asynchronously? From the original example: Button createButton(char[] click_msg) { Button b = new Button(); b.mouseClickCallback = { MsgBox(click_msg); }; return b; } Let's assume mouseClickCallback is written like so: void mouseClickCallback( void delegate() dg ) { clickHandler = dg; } Following my suggestion, it would be changed to this: void mouseClickCallback( void delegate() dg ) { dg.archive; clickHandler = dg; } The archive routine would check dg's stack frame to see if a heap copy of the frame exists (assume it's stored as a pointer at this[0]). If not then memory is allocated, the pointer is set, the frame is copied, and dg's 'this' pointer is updated to refer to the dynamic frame. Returning a delegate from a function would just implicitly call this 'archive' routine. This could still cause errors, as a programmer may forget to call "dg.archive" before storing the delegate, but I think this is an acceptable risk and is far better than having the compiler try to "figure out" whether such a dynamic allocation is needed. It also seems fairly easy to implement compared to the alternatives, and offering the feature through a property method would eliminate the need for a new keyword. Sean

I haven't read the entire thread yet, but I think something like this might be the right ticket. Although the '.archive' property might cause collisions with user code on the return type. Wouldn't it be better if we were to overload the use of 'new' on delegates/functions to do this instead? void mouseClickCallback( void delegate() dg ) { clickHandler = new dg; // } ... or do we require the use of a delegate type instead of an instance? Either way, as 'new' is implied to do heap allocation with classes, we're now doing the same on a given delegate for it's frame.
Aug 16 2006
parent Sean Kelly <sean f4.ca> writes:
pragma wrote:
 Sean Kelly wrote:
 Walter Bright wrote:
 Sean Kelly wrote:
 The alternative would be to use a separate keyword for these 
 delegates, 'closure' or 'lambda' or some such, but that's 
 potentially confusing, and leaves anonymous delegates in an odd 
 position.

I *really* want to avoid having to do this. It's almost guaranteed that it'll be a rich source of bugs.

As an alternative, since it's really how the delegate is used that's at issue, perhaps the programmer could simply be given a way to manually "archive" the stack frame used by a delegate if he knows it will need to be called asynchronously? From the original example: Button createButton(char[] click_msg) { Button b = new Button(); b.mouseClickCallback = { MsgBox(click_msg); }; return b; } Let's assume mouseClickCallback is written like so: void mouseClickCallback( void delegate() dg ) { clickHandler = dg; } Following my suggestion, it would be changed to this: void mouseClickCallback( void delegate() dg ) { dg.archive; clickHandler = dg; } The archive routine would check dg's stack frame to see if a heap copy of the frame exists (assume it's stored as a pointer at this[0]). If not then memory is allocated, the pointer is set, the frame is copied, and dg's 'this' pointer is updated to refer to the dynamic frame. Returning a delegate from a function would just implicitly call this 'archive' routine. This could still cause errors, as a programmer may forget to call "dg.archive" before storing the delegate, but I think this is an acceptable risk and is far better than having the compiler try to "figure out" whether such a dynamic allocation is needed. It also seems fairly easy to implement compared to the alternatives, and offering the feature through a property method would eliminate the need for a new keyword.

I haven't read the entire thread yet, but I think something like this might be the right ticket. Although the '.archive' property might cause collisions with user code on the return type. Wouldn't it be better if we were to overload the use of 'new' on delegates/functions to do this instead? void mouseClickCallback( void delegate() dg ) { clickHandler = new dg; // } ... or do we require the use of a delegate type instead of an instance? Either way, as 'new' is implied to do heap allocation with classes, we're now doing the same on a given delegate for it's frame.

I do like this idea the best, but here are some of the problems that occurred to me: void setCallback( void delegate() dg ) { callback = new dg; } void evilFn1() { int callCount = 0; void dg() { callCount++; } setCallback( &dg ); while( true ) { Thread.sleep( 1000 ); printf( "Called %d times.\n", callCount ); } } void evilFn2() { int[10] buf; int* cur = &buf[0]; void dg() { printf( "%d\n", *cur ); if( ++cur > &buf[9] ) cur = &buf[0]; } initBuf( buf ); setCallback( &dg ); } Since my original proposal was to create a dynamic copy of the stack frame for delegates as needed after the original stack frame had been created, it assumed that the original stack frame would be gone or irrelevant when the delegate was called. In evilFn1, such behavior would result in "Called 0 times." being printed regardless of the number of times the delegate is called. evilFn2 demonstrates that a memcpy of the stack frame may not be sufficient to preserve intended behavior. I do think both of these could probably be overcome with fancier code generation, but they would make the code complex and somewhat non-obvious to a debugger. I still like this idea the best because it allows the programmer aware that the frame must be preserved to do so, but someone would have to resolve the above problems to make it correct and safe. And I didn't even mention the problems with passing a delegate from a struct on the stack or a class constructed in-place on the stack with alloca. Sean
Aug 17 2006
prev sibling parent Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:
 The archive routine would check dg's stack frame to see if a heap copy 
 of the frame exists (assume it's stored as a pointer at this[0]).  If 
 not then memory is allocated, the pointer is set, the frame is copied, 
 and dg's 'this' pointer is updated to refer to the dynamic frame. 
 Returning a delegate from a function would just implicitly call this 
 'archive' routine.  This could still cause errors, as a programmer may 
 forget to call "dg.archive" before storing the delegate, but I think 
 this is an acceptable risk and is far better than having the compiler 
 try to "figure out" whether such a dynamic allocation is needed.  It 
 also seems fairly easy to implement compared to the alternatives, and 
 offering the feature through a property method would eliminate the need 
 for a new keyword.

It's not the new keyword that's the problem - it's the fact that the programmer has to identify the delegate as special.
Aug 16 2006
prev sibling parent Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Sean Kelly wrote:
 An ideal solution would be if the compiler could statically detect if 
 a nested class reference can 'escape' the stack frame, and only then 
 allocate on the heap. Otherwise, the current (very efficient) method 
 of just passing a frame pointer would be employed.

Agreed. As well as detect whether the delegates reference any local stack data in the first place. The alternative would be to use a separate keyword for these delegates, 'closure' or 'lambda' or some such, but that's potentially confusing, and leaves anonymous delegates in an odd position.

Uh, shouldn't such keyword be applied to the function whose frame *is used*, rather than the function(delegate) that uses the outer frame? -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 16 2006
prev sibling parent reply "Mikola Lysenko" <mclysenk mtu.edu> writes:
"Walter Bright" <newshound digitalmars.com> wrote in message 
news:ebvl5s$2k03$1 digitaldaemon.com...
 An ideal solution would be if the compiler could statically detect if a 
 nested class reference can 'escape' the stack frame, and only then 
 allocate on the heap. Otherwise, the current (very efficient) method of 
 just passing a frame pointer would be employed.

Well, in general it is not decidable if a given nested function escapes. Here is a trivial example: void delegate() func(void delegate() F) { F(); return { F(); }; } This function will only return a delegate when F halts. One conservative strategy is to simply look for any nested function declarations in the function's lexical extent. If such a declaration exists, then that function must be heap allocated. I suspect that this is how C# handles the problem. Another possibility is to add a special attribute modifier to the declaration of the initial function. This places the burden of determining 'escapism' on the programmer instead of the compiler, and is probably the simplest to implement. Perhaps the most flexible solution would be a combination of both approaches. By default, any function containing a nested function declaration gets marked as heap allocated - unless it is declared by the programmer to be stack-based. For this purpose, we could recycle the deprecated 'volatile' keyword. Here is an example: volatile void listBATFiles(char[][] files) { foreach(char[] filename; filter(files, (char[] fname) { return fname[$-3..$] == "BAT"; }) writefln("%s", filename); } In this case, we know that the anonymous delegate will never leave the function's scope, so it could be safely stack allocated. Philosophically, this fits with D's design. It makes the default behavior safe, while still allowing the more dangerous behavior when appropriate.
Aug 16 2006
next sibling parent reply kris <foo bar.com> writes:
Mikola Lysenko wrote:
 "Walter Bright" <newshound digitalmars.com> wrote in message 
 news:ebvl5s$2k03$1 digitaldaemon.com...
 
An ideal solution would be if the compiler could statically detect if a 
nested class reference can 'escape' the stack frame, and only then 
allocate on the heap. Otherwise, the current (very efficient) method of 
just passing a frame pointer would be employed.

Well, in general it is not decidable if a given nested function escapes. Here is a trivial example: void delegate() func(void delegate() F) { F(); return { F(); }; } This function will only return a delegate when F halts. One conservative strategy is to simply look for any nested function declarations in the function's lexical extent. If such a declaration exists, then that function must be heap allocated. I suspect that this is how C# handles the problem. Another possibility is to add a special attribute modifier to the declaration of the initial function. This places the burden of determining 'escapism' on the programmer instead of the compiler, and is probably the simplest to implement. Perhaps the most flexible solution would be a combination of both approaches. By default, any function containing a nested function declaration gets marked as heap allocated - unless it is declared by the programmer to be stack-based. For this purpose, we could recycle the deprecated 'volatile' keyword. Here is an example: volatile void listBATFiles(char[][] files) { foreach(char[] filename; filter(files, (char[] fname) { return fname[$-3..$] == "BAT"; }) writefln("%s", filename); } In this case, we know that the anonymous delegate will never leave the function's scope, so it could be safely stack allocated. Philosophically, this fits with D's design. It makes the default behavior safe, while still allowing the more dangerous behavior when appropriate.

A definition --------------- It's worth making a distinction between the two types of delegate. There's what I'll call the synchronous and asynchronous versions, where the scope of the former is live only for the duration of its "host" function (frame needs no preservation; how D works today). Asynchronous delegates can be invoked beyond the lifespan of their original host, and thus their frame may need to be preserved. I say 'may' because it needs to be preserved only if referenced. A couple of observations ------------------------ 1) seems like the use of "volatile" (above) is more attuned to an asynchronous invocation rather than a synchronous one? The above listBatFiles() example is of a synchronous nature, yes? 2) the 'qualifier' in the above example is placed upon the host, where in fact it is the *usage* of the delegate that is at stake. Not the fact that it simply exists. For example: # foo(char[] s) # { # bool isNumeric(char c) {return c >= 0 && c <= '9';} # # foreach (c; s) # if (isNumeric(c)) # // do something # ; # } In the above case, the nested isNumeric() function is clearly of the synchronous variety. It should use the stack, as it does today. Whereas this variation # foo(Gui gui, char[] s) # { # bool isNumeric(char c) {return c >= 0 && c <= '9';} # # bool somethingElse() {return s ~ ": something else";} # # foreach (c; s) # if (isNumeric(c)) # // do something # ; # else # { # funcWrittenBySomeoneElse (somethingElse); # break; # } # } How do you know what the else clause will do with the provided delegate? Is the usage-context synchronous, or will it wind up asynchronous? You just don't know what the function will do with the delegate, because we don't have any indication of the intended usage. (please refrain from comments about indentation in these examples <g>) Yet another strategy -------------------- Consider attaching the qualifier to the usage point. For example, the decl of setButtonHandler() could be as follows: # void setButtonHandler (volatile delegate() handler); ... indicating that the scope of an argument would need to be preserved. For the case of returned delegates, the decl would need to be applied to the return value and to the assigned lValue: # alias volatile delegate() Handler; # # Handler getButtonHandler(); # # auto handler = getButtonHandler(); This is clearly adding to the type system (and would be type-checked), but it does seem to catch all cases appropriately. The other example (above) would be declared in a similar manner, if it were to use its argument in an asynchronous manner: # void funcWrittenBySomeoneElse (delegate() other); # # or # # void funcWrittenBySomeoneElse (volatile delegate() other); C# gets around all this by (it's claimed) *always* using a heap-based frame for delegates. That is certainly safe, but would be inappropriate for purely synchronous usage of nexted functions, due to the overhead of frame allocation. It depends very much on the context involved ~ how the delegates are actually used.
Aug 16 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
kris wrote:
 C# gets around all this by (it's claimed) *always* using a heap-based 
 frame for delegates.

That's the copout solution. I find more and more nifty uses for (synchronous) delegates, and having to allocate the frames on the heap is too high a price to pay. Paying that price would preclude D from having a viable alternative to C++ expression templates, for example. Static escape analysis can yield 3 results: 1) guaranteed to not escape 2) might escape 3) does escape If most of the (1) cases in actual use can be reliably detected as (1), then a reasonable strategy is to do so and allocate on the stack only those proven as (1).
Aug 16 2006
next sibling parent reply kris <foo bar.com> writes:
Walter Bright wrote:
 kris wrote:
 
 C# gets around all this by (it's claimed) *always* using a heap-based 
 frame for delegates.

That's the copout solution. I find more and more nifty uses for (synchronous) delegates, and having to allocate the frames on the heap is too high a price to pay. Paying that price would preclude D from having a viable alternative to C++ expression templates, for example.

I wholeheartedly agree :)
 
 Static escape analysis can yield 3 results:
 
 1) guaranteed to not escape
 2) might escape
 3) does escape
 
 If most of the (1) cases in actual use can be reliably detected as (1), 
 then a reasonable strategy is to do so and allocate on the stack only 
 those proven as (1).

Aye, but doesn't that imply a heap-frame when passing a delegate to another function, when you explicitly know all callbacks will be synchronous only? That would not be good at all, so I hope that wouldn't be the case :(
Aug 16 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
kris wrote:
 Static escape analysis can yield 3 results:

 1) guaranteed to not escape
 2) might escape
 3) does escape

 If most of the (1) cases in actual use can be reliably detected as 
 (1), then a reasonable strategy is to do so and allocate on the stack 
 only those proven as (1).

Aye, but doesn't that imply a heap-frame when passing a delegate to another function, when you explicitly know all callbacks will be synchronous only?

If the source to that function is not known to the compiler, then yes.
Aug 16 2006
parent reply kris <foo bar.com> writes:
Walter Bright wrote:
 kris wrote:
 
 Static escape analysis can yield 3 results:

 1) guaranteed to not escape
 2) might escape
 3) does escape

 If most of the (1) cases in actual use can be reliably detected as 
 (1), then a reasonable strategy is to do so and allocate on the stack 
 only those proven as (1).

Aye, but doesn't that imply a heap-frame when passing a delegate to another function, when you explicitly know all callbacks will be synchronous only?

If the source to that function is not known to the compiler, then yes.

Aye; that's a tough one. On the one hand it's certainly 'safer' to rely on analysis only. On the other, there's a lot of good reason to support a means to disable the analysis (for known cases) thus ensuring a stack-frame instead. The latter could be fraught with issue, though; just like the former. I'm hoping there's another option, better than both the above (or the above combination) ~ it's seems apparent that neither present an ideal resolution
Aug 16 2006
next sibling parent reply Lionello Lunesu <lio lunesu.remove.com> writes:
kris wrote:
 I'm hoping there's another option, better than both the above (or the 
 above combination) ~ it's seems apparent that neither present an ideal 
 resolution

Delegates are a pretty advanced programming technique. I don't think it would be bad solution to just let the programmer mark the exceptional cases. At least until a fail-safe general solution becomes available. L.
Aug 17 2006
next sibling parent "Mikola Lysenko" <mclysenk mtu.edu> writes:
"Lionello Lunesu" <lio lunesu.remove.com> wrote in message 
news:ec1a8l$19ab$1 digitaldaemon.com...
 kris wrote:
 I'm hoping there's another option, better than both the above (or the 
 above combination) ~ it's seems apparent that neither present an ideal 
 resolution

Delegates are a pretty advanced programming technique. I don't think it would be bad solution to just let the programmer mark the exceptional cases. At least until a fail-safe general solution becomes available.

Well, I think everyone can agree that the best possible solution would be an omniscient static escape analyzer. It would guarantee that programs use the stack as much as possible, and only resort to the heap when absolutely necessary. Sadly, such a program is an abomination of logic - its very existence a paradox. So, we will have to settle for whatever escape analysis logic is available. Real world analyzers have that unfortunate "maybe" case. If we want to automate everything, then we need to assume heap allocation for all of the places where the implementation could fail. As Kris pointed out, this is not good enough. Here is what I propose: 1. The default frame-type is determined through static escape analysis. 2. Functions can be declared to explicitly contain a stack based frame. 3. If the escape analyzer determines that a function declared with a stack frame contains an escaping delegate, then it may raise an error. With these rules, we use all the information an escape analyzer can tell us. As Walter posted,
Static escape analysis can yield 3 results:

1) guaranteed to not escape
2) might escape
3) does escape

Simply marking everything except the first case as heap allocated does not distinguish between cases 2 and 3. Nor does adding an "ultimate" override, since it could overpower the analyzer even in case 3. This weaker override can only be applied to cases 1 and 2. In case 1, it is merely redundant, but should be legal. In case 3, it is blatantly wrong, so the compiler should say so. In case 2, it is impossible for the compiler to determine whether the human was right or wrong, so we can allow the usage. This allows the programmer to effectively use each piece of information. Here is a visual representation of this argument using ascii-tables: [monospace] Omniscient analyzer: +-------------------------+----------------+ | Escape Analyzer Result | Interpretation | +-------------------------+----------------+ | No Escape | Stack | | Does Escape | Heap | +-------------------------+----------------+ 2 total cases: {Stack, Heap} Without an override (non-omniscient): +-------------------------+----------------+ | Escape Analyzer Result | Interpretation | +-------------------------+----------------+ | No Escape | Stack | | Might Escape | Heap | | Does Escape | Heap | +-------------------------+----------------+ 2 total cases: {Stack, Heap} With an ultimate override: +-------------------------+-------------+----------+ | Escape Analyzer Result | No Override | Override | +-------------------------+-------------+----------+ | No Escape | Stack | Stack | | Might Escape | Heap | Stack | | Does Escape | Heap | Stack | +-------------------------+-------------+----------+ 2 total cases: {(Stack, Stack), (Heap, Stack)} With an weak override: +-------------------------+-------------+----------+ | Escape Analyzer Result | No Override | Override | +-------------------------+-------------+----------+ | No Escape | Stack | Stack | | Might Escape | Heap | Stack | | Does Escape | Heap | Error | +-------------------------+-------------+----------+ 3 total cases: {(Stack, Stack), (Heap, Stack), (Heap, Error)} [/monospace] Moreover, this strategy is independent of the type of escape analyzer used. The quality of the static checking could become a quality of implementation issue, much like the optimizer. Picking one specific strategy would require integrating it into the core specification, which will create headaches for future generations of D compilers. This method is flexible enough to allow a short-term simple implementation, which can later be extended into a more powerful and accurate system.
Aug 17 2006
prev sibling parent BCS <BCS pathlink.com> writes:
Lionello Lunesu wrote:
 kris wrote:
 
 I'm hoping there's another option, better than both the above (or the 
 above combination) ~ it's seems apparent that neither present an ideal 
 resolution

Delegates are a pretty advanced programming technique. I don't think it would be bad solution to just let the programmer mark the exceptional cases. At least until a fail-safe general solution becomes available. L.

At some point you have to just let the man shoot himself in the foot. You can't stop him. So the best we can do is stop the easy cases and put big warning labels on the hard ones. That is, make them official undefined behavior cases. If I wanted a really robust systems, I would use a language that only uses heap frames. And has runtime type checking. And a load of other time hogging safety features. All of which I'm glad D *doesn't* have. Alternative solution: Requirer the programmer to write "correct" programs. Then, in debug builds, check for errors at run time. One options for doing this check is this: In debug builds, put a guard word at the start of each stack frame for every function with delegates. When the function returns, clear the guard. All delegates are now replaced with something that looks like this (in sudo code): &( class { int guard; // storage for the guard R delegate(A...) dg; // storage for the actual delegate // whatever args are needed R test(A... args) { // test the guard assert(guard == dg.this.__guard); // chain to the delegate return dg(args); } } ).test The guard word is pulled from a counter so it will be unique.
Aug 17 2006
prev sibling next sibling parent Sean Kelly <sean f4.ca> writes:
kris wrote:
 
 On the one hand it's certainly 'safer' to rely on analysis only. On the 
 other, there's a lot of good reason to support a means to disable the 
 analysis (for known cases) thus ensuring a stack-frame instead. The 
 latter could be fraught with issue, though; just like the former.
 
 I'm hoping there's another option, better than both the above (or the 
 above combination) ~ it's seems apparent that neither present an ideal 
 resolution

This is what prompted my 'archive' solution that turned out to be problematic, but I'm hoping the same thing. I don't find any of the other suggestions terribly appealing. Sean
Aug 17 2006
prev sibling parent Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
kris wrote:
 Walter Bright wrote:
 kris wrote:

 Static escape analysis can yield 3 results:

 1) guaranteed to not escape
 2) might escape
 3) does escape

 If most of the (1) cases in actual use can be reliably detected as 
 (1), then a reasonable strategy is to do so and allocate on the 
 stack only those proven as (1).

Aye, but doesn't that imply a heap-frame when passing a delegate to another function, when you explicitly know all callbacks will be synchronous only?

If the source to that function is not known to the compiler, then yes.

Aye; that's a tough one. On the one hand it's certainly 'safer' to rely on analysis only. On the other, there's a lot of good reason to support a means to disable the analysis (for known cases) thus ensuring a stack-frame instead. The latter could be fraught with issue, though; just like the former.

Hum, taking a clue that this problem is very similar to object(and data) allocation, one possibility is for both work the same way: Outer variables be heap-allocated by default (like new), and stack-allocated when escape analysis determines that is safe, or when the user explicitly states it with the auto(raii) keyword: void func() { auto int x; // x is not heap-allocated, no matter what. int y; // y is stack-allocated, as it is not an outer var doSomething( { return x++; } ); //thus this dg literal is synchronous } -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 17 2006
prev sibling parent reply Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Walter Bright wrote:
 kris wrote:
 C# gets around all this by (it's claimed) *always* using a heap-based 
 frame for delegates.


Note: C# doesn't allocate the *whole* (outer) frame on the stack or on the heap. It will allocate on the heap only those variables that are accessed by a delegate literal, which are called outer variables (and are said to be "captured" or "lifted"). The delegate's (own) frame, is normal I believe, unless it also has delegate literals.
 That's the copout solution. I find more and more nifty uses for 
 (synchronous) delegates, and having to allocate the frames on the heap 
 is too high a price to pay. Paying that price would preclude D from 
 having a viable alternative to C++ expression templates, for example.
 
 Static escape analysis can yield 3 results:
 
 1) guaranteed to not escape
 2) might escape
 3) does escape
 
 If most of the (1) cases in actual use can be reliably detected as (1), 
 then a reasonable strategy is to do so and allocate on the stack only 
 those proven as (1).

Also, such analysis would also be useful for object (and data) allocation, as the concept (and the compiler checking method too, I think) is pretty much the same. (A new'ed object can be allocated on the stack, if it is determined that it does not escape). -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 17 2006
parent Walter Bright <newshound digitalmars.com> writes:
Bruno Medeiros wrote:
 Also, such analysis would also be useful for object (and data) 
 allocation, as the concept (and the compiler checking method too, I 
 think) is pretty much the same. (A new'ed object
 can be allocated on the stack, if it is determined that it does not 
 escape).

That's correct, escape analysis can open the door for lots of cool improvements.
Aug 17 2006
prev sibling parent reply Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Mikola Lysenko wrote:
 "Walter Bright" <newshound digitalmars.com> wrote in message 
 news:ebvl5s$2k03$1 digitaldaemon.com...
 An ideal solution would be if the compiler could statically detect if a 
 nested class reference can 'escape' the stack frame, and only then 
 allocate on the heap. Otherwise, the current (very efficient) method of 
 just passing a frame pointer would be employed.

Well, in general it is not decidable if a given nested function escapes. Here is a trivial example: void delegate() func(void delegate() F) { F(); return { F(); }; } This function will only return a delegate when F halts. One conservative

I do not understand why or how this is undecidable. It seems clear that a delegate escapes (the literal delegate).
 strategy is to simply look for any nested function declarations in the 
 function's lexical extent.  If such a declaration exists, then that function 
 must be heap allocated.  I suspect that this is how C# handles the problem.
 

Yes, that's idea that should be effective enough, if one wants language auto-detection of heaped functions.
 Another possibility is to add a special attribute modifier to the 
 declaration of the initial function.  This places the burden of determining 
 'escapism' on the programmer instead of the compiler, and is probably the 
 simplest to implement.
 
 Perhaps the most flexible solution would be a combination of both 
 approaches.  By default, any function containing a nested function 
 declaration gets marked as heap allocated - unless it is declared by the 
 programmer to be stack-based.  For this purpose, we could recycle the 
 deprecated 'volatile' keyword.  Here is an example:
 
 volatile void listBATFiles(char[][] files)
 {
     foreach(char[] filename; filter(files,  (char[] fname)  { return 
 fname[$-3..$] == "BAT"; })
         writefln("%s", filename);
 }
 
 In this case, we know that the anonymous delegate will never leave the 
 function's scope, so it could be safely stack allocated.  Philosophically, 
 this fits with D's design.  It makes the default behavior safe, while still 
 allowing the more dangerous behavior when appropriate.
 
 

'volatile' is a crappy name IMO. Consider this function: volatile void delegate() func(int b); is func "heaped"(volatile), or is the return value dg type heaped? This may lend to some ambiguities. Another option is for the specifier to be postfixed. Supose that NEW means heaped, and AUTO means stack framed: void delegate() AUTO func(int b) NEW; (note AUTO is default and thus redundant) I do not know for sure the implications in terms of grammar parsing for each of these alternatives, Walter should know better. -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 16 2006
parent Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
Bruno Medeiros wrote:
 Another option is for the specifier to be postfixed. Supose that NEW 
 means heaped, and AUTO means stack framed:
   void delegate() AUTO func(int b) NEW;
 (note AUTO is default and thus redundant)

Forget this idea, it is crappy, for several reasons. -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 17 2006
prev sibling next sibling parent reply nobody <nobody mailinator.com> writes:
Mikola Lysenko wrote:

 Recent D releases (notably 0.161) have updated the syntax and improved the 
 overall usability of lambda delegates. All the syntactic sugar is nice, but 
 it also lays a few traps for the unwary.  Here is a simple example:
 
 // The Fibonacci numbers are an integer sequence such that
 //        F(n) = F(n - 1) + F(n - 2)
 //        And F(0) = 0, F(1) = 1
 int delegate() fibs()
 {
     int a = 0;            // Initialize the last two terms of the Fibonacci 
     int b = 1;
 
     return
     {
         int c = a + b;     // Calculate the next term in the sequence
         a = b;               // Shift the previous terms back
         b = c;
         return c;            // Return the result
     };
 }
 
 This function returns a function which will sequentially evaluate all of the 
 Fibonacci numbers.  Notice that the inner delegate modifies the variables a 
 and b in fibs() scope.  Because of this, it is not guaranteed to work after 
 fibs returns.  This is most irritating, and it greatly restricts the use of 
 this technique. Another potential use for lambda delegates is to create 
 one-line adapter methods.  Consider the following attempt to create a button 
 which will display an arbitrary message when clicked:

It took me awhile to get what you were doing but it is elegant -- or would be if it worked. I am sure I am missing something however so I hope you might explain why using static storage is not sufficient: int delegate() fibs() { return { static int a = 0; static int b = 1; int c = a + b; a = b; b = c ; return c; }; }
Aug 16 2006
parent reply Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
nobody wrote:
 Mikola Lysenko wrote:
 
 Recent D releases (notably 0.161) have updated the syntax and improved 
 the overall usability of lambda delegates. All the syntactic sugar is 
 nice, but it also lays a few traps for the unwary.  Here is a simple 
 example:

 // The Fibonacci numbers are an integer sequence such that
 //        F(n) = F(n - 1) + F(n - 2)
 //        And F(0) = 0, F(1) = 1
 int delegate() fibs()
 {
     int a = 0;            // Initialize the last two terms of the 
 Fibonacci     int b = 1;

     return
     {
         int c = a + b;     // Calculate the next term in the sequence
         a = b;               // Shift the previous terms back
         b = c;
         return c;            // Return the result
     };
 }

 This function returns a function which will sequentially evaluate all 
 of the Fibonacci numbers.  Notice that the inner delegate modifies the 
 variables a and b in fibs() scope.  Because of this, it is not 
 guaranteed to work after fibs returns.  This is most irritating, and 
 it greatly restricts the use of this technique. Another potential use 
 for lambda delegates is to create one-line adapter methods.  Consider 
 the following attempt to create a button which will display an 
 arbitrary message when clicked:

It took me awhile to get what you were doing but it is elegant -- or would be if it worked. I am sure I am missing something however so I hope you might explain why using static storage is not sufficient: int delegate() fibs() { return { static int a = 0; static int b = 1; int c = a + b; a = b; b = c ; return c; }; }

For starters, a delegate can access the outer function arguments, but those arguments cannot be made static. And then there will only be one "instance" of the returned delegate (think of the delegate as an object). Any call to it will update only one single sequence: auto dg1 = fibs(); auto dg2 = fibs(); dg1(); // 1 dg1(); // 2 dg2(); // 3 dg2(); // 5 However, with proper "heaped" frames, there are many delegate (outer frame) "instances": auto dg1 = fibs(); auto dg2 = fibs(); dg1(); // 1 dg1(); // 2 dg1(); // 3 dg2(); // 1 dg2(); // 2 dg2(); // 3 -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 16 2006
next sibling parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Thu, 17 Aug 2006 01:15:15 +0100, Bruno Medeiros  
<brunodomedeirosATgmail SPAM.com> wrote:
 nobody wrote:
 Mikola Lysenko wrote:

 Recent D releases (notably 0.161) have updated the syntax and improved  
 the overall usability of lambda delegates. All the syntactic sugar is  
 nice, but it also lays a few traps for the unwary.  Here is a simple  
 example:

 // The Fibonacci numbers are an integer sequence such that
 //        F(n) = F(n - 1) + F(n - 2)
 //        And F(0) = 0, F(1) = 1
 int delegate() fibs()
 {
     int a = 0;            // Initialize the last two terms of the  
 Fibonacci     int b = 1;

     return
     {
         int c = a + b;     // Calculate the next term in the sequence
         a = b;               // Shift the previous terms back
         b = c;
         return c;            // Return the result
     };
 }

 This function returns a function which will sequentially evaluate all  
 of the Fibonacci numbers.  Notice that the inner delegate modifies the  
 variables a and b in fibs() scope.  Because of this, it is not  
 guaranteed to work after fibs returns.  This is most irritating, and  
 it greatly restricts the use of this technique. Another potential use  
 for lambda delegates is to create one-line adapter methods.  Consider  
 the following attempt to create a button which will display an  
 arbitrary message when clicked:

would be if it worked. I am sure I am missing something however so I hope you might explain why using static storage is not sufficient: int delegate() fibs() { return { static int a = 0; static int b = 1; int c = a + b; a = b; b = c ; return c; }; }

For starters, a delegate can access the outer function arguments, but those arguments cannot be made static. And then there will only be one "instance" of the returned delegate (think of the delegate as an object). Any call to it will update only one single sequence: auto dg1 = fibs(); auto dg2 = fibs(); dg1(); // 1 dg1(); // 2 dg2(); // 3 dg2(); // 5 However, with proper "heaped" frames, there are many delegate (outer frame) "instances": auto dg1 = fibs(); auto dg2 = fibs(); dg1(); // 1 dg1(); // 2 dg1(); // 3 dg2(); // 1 dg2(); // 2 dg2(); // 3

So, the other option is: import std.stdio; // The Fibonacci numbers are an integer sequence such that // F(n) = F(n - 1) + F(n - 2) // And F(0) = 0, F(1) = 1 int delegate(inout int,inout int) fibs() { return (inout int a, inout int b) { int c = a + b; // Calculate the next term in the sequence a = b; // Shift the previous terms back b = c; return c; // Return the result }; } void main() { int a = 0,b = 1; writefln(fibs()(a,b)); writefln(fibs()(a,b)); writefln(fibs()(a,b)); writefln(fibs()(a,b)); writefln(fibs()(a,b)); writefln(fibs()(a,b)); writefln(fibs()(a,b)); } Right? Passing the storage location to the calls. Regan
Aug 16 2006
parent nobody <nobody mailinator.com> writes:
Regan Heath wrote:
 On Thu, 17 Aug 2006 01:15:15 +0100, Bruno Medeiros 
 <brunodomedeirosATgmail SPAM.com> wrote:
 For starters, a delegate can access the outer function arguments, but 
 those arguments cannot be made static.

 And then there will only be one "instance" of the returned delegate 
 (think of the delegate as an object). Any call to it will update only 
 one single sequence:

    auto dg1 = fibs();
    auto dg2 = fibs();
    dg1(); // 1
    dg1(); // 2
    dg2(); // 3
    dg2(); // 5

 However, with proper "heaped" frames, there are many delegate (outer 
 frame) "instances":

    auto dg1 = fibs();
    auto dg2 = fibs();
    dg1(); // 1
    dg1(); // 2
    dg1(); // 3
    dg2(); // 1
    dg2(); // 2
    dg2(); // 3

So, the other option is: import std.stdio; // The Fibonacci numbers are an integer sequence such that // F(n) = F(n - 1) + F(n - 2) // And F(0) = 0, F(1) = 1 int delegate(inout int,inout int) fibs() { return (inout int a, inout int b) { int c = a + b; // Calculate the next term in the sequence a = b; // Shift the previous terms back b = c; return c; // Return the result }; } ... Right? Passing the storage location to the calls. Regan

Not sure if you figured it out on your own but I thought maybe someone else might have the same question. The short answer is that the delegate Mikola Lysenko was attempting to define evaluates the first time it is called to the first number in a sequence, S(1), and thereafter the Nth evaluation yields S(N). The delegate you defined starts with two arbitrary params -- which can but needn't be the start of the sequence. This implementation requires somebody using your function to know what magic numbers start the whole thing off and requires you to test for strange values. The entire challenge is really that there is no reason to pass arguments to Mikola Lysenko's function because it should know where it starts, how to progress from any N to N+1 and finally remember the last N for which it was evaluated.
Aug 17 2006
prev sibling parent nobody <nobody mailinator.com> writes:
Bruno Medeiros wrote:
 nobody wrote:
 Mikola Lysenko wrote:

 Recent D releases (notably 0.161) have updated the syntax and 
 improved the overall usability of lambda delegates. All the syntactic 
 sugar is nice, but it also lays a few traps for the unwary.  Here is 
 a simple example:

 // The Fibonacci numbers are an integer sequence such that
 //        F(n) = F(n - 1) + F(n - 2)
 //        And F(0) = 0, F(1) = 1
 int delegate() fibs()
 {
     int a = 0;            // Initialize the last two terms of the 
 Fibonacci     int b = 1;

     return
     {
         int c = a + b;     // Calculate the next term in the sequence
         a = b;               // Shift the previous terms back
         b = c;
         return c;            // Return the result
     };
 }

 This function returns a function which will sequentially evaluate all 
 of the Fibonacci numbers.  Notice that the inner delegate modifies 
 the variables a and b in fibs() scope.  Because of this, it is not 
 guaranteed to work after fibs returns.  This is most irritating, and 
 it greatly restricts the use of this technique. Another potential use 
 for lambda delegates is to create one-line adapter methods.  Consider 
 the following attempt to create a button which will display an 
 arbitrary message when clicked:

It took me awhile to get what you were doing but it is elegant -- or would be if it worked. I am sure I am missing something however so I hope you might explain why using static storage is not sufficient: int delegate() fibs() { return { static int a = 0; static int b = 1; int c = a + b; a = b; b = c ; return c; }; }

For starters, a delegate can access the outer function arguments, but those arguments cannot be made static. And then there will only be one "instance" of the returned delegate (think of the delegate as an object). Any call to it will update only one single sequence: auto dg1 = fibs(); auto dg2 = fibs(); dg1(); // 1 dg1(); // 2 dg2(); // 3 dg2(); // 5 However, with proper "heaped" frames, there are many delegate (outer frame) "instances": auto dg1 = fibs(); auto dg2 = fibs(); dg1(); // 1 dg1(); // 2 dg1(); // 3 dg2(); // 1 dg2(); // 2 dg2(); // 3

Thanks for the reply. Your reply certainly helped me see the issues more clearly. I took some time and played with static storage just a bit more to see where its limits are. It is possible to get scoped vars into static fields. The real problem is somehow getting individual delegates to recognize which index is theirs. You should notice that in addition to making tables for multiple values there is also a table which stores all the delegates made. If there were a way to scan the table for the delegate within the delegate when everytime it is run then the problem would be solved. const int MAX_CONSECUTIVE_FIBS = 8; int delegate() fibs() { int a = 0; int b = 1; int delegate() fibs_dg_wrapper() { static int[MAX_CONSECUTIVE_FIBS] a_table; static int[MAX_CONSECUTIVE_FIBS] b_table; static int delegate()[MAX_CONSECUTIVE_FIBS] d_table; static int last_index = -1; last_index += 1; a_table[last_index] = a; // a valid in this wrapper func b_table[last_index] = b; // b valid in this wrapper func d_table[last_index] = // keep reference to each dg { // would work if I could scan table for this dg // no idea how to do that and hence the printfs int my_index = last_index; int c = a_table[my_index] + b_table[my_index]; a_table[my_index] = b_table[my_index]; b_table[my_index] = c; dout.printf("fibs_dg %X\n",d_table[my_index]); dout.printf("fibs_dg.c %X\n\n",&c); return c; }; return d_table[last_index]; }; return fibs_dg_wrapper(); } int main(char[][] args) int delegate() fibsdg1 = fibs_multi(); dout.printf("%d\n",fibsdg1()); dout.printf("%d\n",fibsdg1()); dout.printf("%d\n",fibsdg1()); dout.printf("%d\n",fibsdg1()); dout.printf("%d\n",fibsdg1()); dout.printf("\n"); int delegate() fibsdg2 = fibs_multi(); dout.printf("%d\n",fibsdg2()); dout.printf("%d\n",fibsdg2()); dout.printf("%d\n",fibsdg2()); dout.printf("%d\n",fibsdg2()); dout.printf("%d\n",fibsdg2()); dout.printf("\n"); }
Aug 17 2006
prev sibling next sibling parent S. Chancellor <dnewsgr mephit.kicks-ass.org> writes:
On 2006-08-16 07:55:38 -0700, "Mikola Lysenko" <mclysenk mtu.edu> said:

 D's delegates are great.  They are vastly superior to C++'s confused 
 pointer-to-member functions, and much more useful than Java's adapter 
 classes.  In the world of system programs, nothing comes close.  One 
 interesting type of delegate is the anonymous-nested-delegate-literal, 
 or "lambda" delegate.  For those unacquainted with such niceties, here 
 are the documentation links:
 http://www.digitalmars.com/d/function.html#nested
 http://www.digitalmars.com/d/expression.html#FunctionLiteral
 
 Recent D releases (notably 0.161) have updated the syntax and improved 
 the overall usability of lambda delegates. All the syntactic sugar is 
 nice, but it also lays a few traps for the unwary.  Here is a simple 
 example:
 
 // The Fibonacci numbers are an integer sequence such that
 //        F(n) = F(n - 1) + F(n - 2)
 //        And F(0) = 0, F(1) = 1
 int delegate() fibs()
 {
     int a = 0;            // Initialize the last two terms of the 
 Fibonacci sequence
     int b = 1;
 
     return
     {
         int c = a + b;     // Calculate the next term in the sequence
         a = b;               // Shift the previous terms back
         b = c;
         return c;            // Return the result
     };
 }
 
 This function returns a function which will sequentially evaluate all 
 of the Fibonacci numbers.  Notice that the inner delegate modifies the 
 variables a and b in fibs() scope.  Because of this, it is not 
 guaranteed to work after fibs returns.  This is most irritating, and it 
 greatly restricts the use of this technique. Another potential use for 
 lambda delegates is to create one-line adapter methods.  Consider the 
 following attempt to create a button which will display an arbitrary 
 message when clicked:
 
 Button createButton(char[] click_msg)
 {
     Button b = new Button();
     b.mouseClickCallback = { MsgBox(click_msg); };
     return b;
 }
 
 Once more, this sort of method relies on access to the outer function 
 scope from within the lambda delegate.  Given the current semantics, 
 this code is doomed to fail in any number of random ways.  As a final 
 example, suppose we want to perform a lengthy calculation in a separate 
 thread, and only wait for the value once it is needed.  In this case, 
 one could try to do the following:
 
 int[] delegate() sort_threaded(int[] array)
 {
     int[] result = array.dup;
 
     //Create and run a worker thread to perform an expensive operation, 
 (in this case a sort)
     Thread tsort = new Thread(
      {
         result.sort;
         return 0;
      });
     tsort.start();
 
     //The returned lambda delegate waits for the thread's calculation 
 to finish, then returns the result.
     return { tsort.wait; return result; };
 }
 
 In this situation, we can let the thread execute in the background 
 while the program performs other tasks, and only wait for the result 
 once we need it. This type of deferred calculation can be very useful 
 for improving the amount of parallelism within an application without 
 adding much synchronization overhead.  It is very sad that none of 
 these examples work, since there are so many nice solutions just like 
 them.
 
 One possible solution is to allocate the frame for each function 
 containing nested-functions on the heap.  This allows any returned 
 delegates to use the member variables freely.  One could think of it as 
 translating the function into a class with a thunk.  Here is above 
 Fibonacci function rewritten in this way:
 
 class fibs_
 {
     int a = 0;
     int b = 1;
 
     int lambda1()
     {
         int c = a + b;
         a = b;
         b = c;
         return c;
     }
 
     int delegate() func()
     {
         return &lambda1;
     }
 }
 
 int delegate() fibs()
 {
     return (new fibs_()).func();
 }
 
 Such a translation is possible for any of these examples, albeit quite 
 tedious.  From what I gather C# applies a similar technique with its 
 lambda delegates and inner classes.  For a machine code compiler, such 
 a rewrite is not even necessary, since it could simply overwrite the 
 frame pointer at the start of the function with a GC allocated block.  
 This would preserve frame-based addressing for arguments and variables, 
 requiring no change in any of the internally generated machine code.  
 The run time overhead is fairly low, only on the order of one extra 
 memory allocation per function call.  Practically, such an 
 implementation would be extremely simple.
 
 Any thoughts or comments?
 
 -Mikola Lysenko

Perl has this same problem. May be of use to look at how perl solves it.
Aug 16 2006
prev sibling next sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
Mikola Lysenko wrote:
<snip>
     return
     {
         int c = a + b;     // Calculate the next term in the sequence
         a = b;               // Shift the previous terms back
         b = c;
         return c;            // Return the result
     };

Is it my imagination, or does this create yet another ambiguity in the D syntax? { ... } + 69; Is this one ExpressionStatement containing an AddExpression, or a BlockStatement followed by an ExpressionStatement containing a UnaryExpression? OK, so neither makes semantic sense, but it still needs defining at the syntactic level. Stewart.
Aug 17 2006
prev sibling next sibling parent reply BCS <BCS pathlink.com> writes:
1) What happens when a heap based function calls a stack based function? 
Will the code try to extend the heap frame? How would this be prevented? 
Use another register for the heap-frame-pointer? (stack-frame, 
heap-frame, stack, how many register are left?) Have a stub stack-frame 
to put it in? (makes fn calls more costly.)

2) heap frames only tackles the case where the "lost" scope is the 
function it's self. What about where the scope is a if block?

void fn()
{
	int i;
	auto dg = {return i;};

	if(i);
	{
		int j;
		dg = {return i+j;};
	}

	if(i)
	{
		int k = 3;
		k = dg();	// j overlaps k
	}
}
Aug 17 2006
parent reply "Mikola Lysenko" <mclysenk mtu.edu> writes:
"BCS" <BCS pathlink.com> wrote in message 
news:ec2581$74o$2 digitaldaemon.com...
 1) What happens when a heap based function calls a stack based function? 
 Will the code try to extend the heap frame? How would this be prevented? 
 Use another register for the heap-frame-pointer? (stack-frame, heap-frame, 
 stack, how many register are left?) Have a stub stack-frame to put it in? 
 (makes fn calls more costly.)

This would not present any sort of problem. Here is what a stack based prolog looks like: push EBP; //Save old frame pointer on the stack mov EBP, ESP; //Set the new frame pointer & save stack pointer sub ESP, frame_size; //Allocate the new frame from the stack And when we exit, we use the following epilog: mov ESP, EBP; //Restore old stack pointer pop EBP; //Restore old frame pointer ret; //Resume execution from the previous frame In this case, it does not matter what EBP was before we entered the function. It could even be an invalid memory location for all we care. So, calling a stack based function from a heap based function does not create any sort of problem.
 2) heap frames only tackles the case where the "lost" scope is the 
 function it's self. What about where the scope is a if block?

 void fn()
 {
 int i;
 auto dg = {return i;};

 if(i);
 {
 int j;
 dg = {return i+j;};
 }

 if(i)
 {
 int k = 3;
 k = dg(); // j overlaps k
 }
 }

Typically all the variables used in a given function would get allocated in the same frame. In this case, the frame would look something like: EBP[4] = return address EBP[0] = previous frame pointer EBP[-4] = i EBP[-8] = j EBP[-12] = k If this is the situation, then i, j and k are all allocated at once when the function first gets called. They are only initialized once they enter scope. When considering the semantics of heap allocated frames, I would try to think of it like the class example given in the original post. In that case, all of the variables and arguments are copied into a container class, which also has methods for every nested function. Hopefully this makes things clearer.
Aug 17 2006
parent BCS <BCS pathlink.com> writes:
Mikola Lysenko wrote:
 "BCS" <BCS pathlink.com> wrote in message 
 news:ec2581$74o$2 digitaldaemon.com...
 
1) What happens when a heap based function calls a stack based function? 
Will the code try to extend the heap frame? [...]

This would not present any sort of problem. Here is what a stack based prolog looks like: push EBP; //Save old frame pointer on the stack mov EBP, ESP; //Set the new frame pointer & save stack pointer sub ESP, frame_size; //Allocate the new frame from the stack And when we exit, we use the following epilog: mov ESP, EBP; //Restore old stack pointer pop EBP; //Restore old frame pointer ret; //Resume execution from the previous frame In this case, it does not matter what EBP was before we entered the function. [...]

That may be so but IIRC EBP is generally modified by the function as it executes. This is done to make room for temporaries and such. This will present a problem because it will create a "phantom" stack frame. This could be dealt with by removing the EBP adjustment code from the function, but that would require changes to the code generator.
 
2) heap frames only tackles the case where the "lost" scope is the 
function it's self. What about where the scope is a if block?

void fn()
{
int i;
auto dg = {return i;};
if(i);
{
int j;
dg = {return i+j;};
}
if(i)
{
int k = 3;
k = dg(); // j overlaps k
}
}

the same frame. In this case, the frame would look something like: EBP[4] = return address EBP[0] = previous frame pointer EBP[-4] = i EBP[-8] = j EBP[-12] = k

This presents a problem, consider: void fn() { { int[BIG] big; use big } { float[HUGE] huge; use huge; } } In the general case (stack frames) these /should/ overlap. Otherwise the stack frame will become overly large. Heap frames could us a different layout, but again that will require changes the to code generator. (BTW, I am now working on a machine that won't allow an int[1000] on the stack. So mandating that all stack variables be non overlapping in not an option.) Both problems can be overcome, but I really don't like the idea of having the code generator produce different code for heap-frames and stack-frames.
Aug 17 2006
prev sibling parent reply xs0 <xs0 xs0.com> writes:
Mikola Lysenko wrote:
 [snip]
 Any thoughts or comments?

Well, to me it seems that anything the compiler will try to do automatically will be wrong (or at least needlessly slow) in many cases. And a lot of the problem seems to be simply that one can't attach storage to a delegate without creating a whole class/struct, and doing that is too verbose to be used easily/often. So, why not simply have some syntax sugar for that? int delegate() fibs() { int a=0, b=1; return delegate with(a,b) { // it takes a and b with it ... } } Which would become exactly what you proposed. xs0
Aug 17 2006
next sibling parent reply kris <foo bar.com> writes:
xs0 wrote:
 Mikola Lysenko wrote:
 
 [snip]
 Any thoughts or comments?

Well, to me it seems that anything the compiler will try to do automatically will be wrong (or at least needlessly slow) in many cases. And a lot of the problem seems to be simply that one can't attach storage to a delegate without creating a whole class/struct, and doing that is too verbose to be used easily/often. So, why not simply have some syntax sugar for that? int delegate() fibs() { int a=0, b=1; return delegate with(a,b) { // it takes a and b with it ... } } Which would become exactly what you proposed. xs0

Nice, but the problem with that is as follows: When passing such a delegate as an argument, you don't know whether it'll be used in a synchronous or asynchronous manner. So, perhaps you choose the safe route and assume worst-case. That's cool, but if you choose best case instead (because you 'know' usage is synchronous) then you leave yourself open to nasty issues if that callee is ever changed. Think about passing a delegate to a third-party lib? The contract is weak, and therefore fragile. That's why we'd suggested an extension to the type system instead (which also has some problems). The other thing that Mik noted is that the entire frame should be on the heap; not just part of it (for performance reasons), and taking a snapshot copy of the scope (or part thereof) does not work at all, since there could be self-references, pointers, whatever, in there. It seems you have to flip the entire frame into the heap. Other than that, it is a pretty clean syntax :)
Aug 17 2006
parent xs0 <xs0 xs0.com> writes:
kris wrote:
 xs0 wrote:
 Well, to me it seems that anything the compiler will try to do 
 automatically will be wrong (or at least needlessly slow) in many 
 cases. And a lot of the problem seems to be simply that one can't 
 attach storage to a delegate without creating a whole class/struct, 
 and doing that is too verbose to be used easily/often.

 So, why not simply have some syntax sugar for that?

 int delegate() fibs()
 {
     int a=0, b=1;
     return delegate with(a,b) { // it takes a and b with it
         ...
     }
 }

Nice, but the problem with that is as follows: When passing such a delegate as an argument, you don't know whether it'll be used in a synchronous or asynchronous manner.

Are you sure you don't know? I can't think of a case where I'd be in doubt..
 So, perhaps you 
 choose the safe route and assume worst-case. That's cool, but if you 
 choose best case instead (because you 'know' usage is synchronous) then 
 you leave yourself open to nasty issues if that callee is ever changed. 
 Think about passing a delegate to a third-party lib? The contract is 
 weak, and therefore fragile. That's why we'd suggested an extension to 
 the type system instead (which also has some problems).

Well, I think it's not as big a problem realistically.. When you provide a delegate you need to know what its purpose is and I think that is something very unlikely to change. The two main types of delegates seem to be callbacks and specific operations for generic algorithms. I don't see how a library update would change the contract between those two.
 The other thing that Mik noted is that the entire frame should be on the 
 heap; not just part of it (for performance reasons)

What performance reasons? I read this entire thread and still have no idea how copying more/all of the frame could/would be faster..
 , and taking a 
 snapshot copy of the scope (or part thereof) does not work at all, since 
 there could be self-references, pointers, whatever, in there. It seems 
 you have to flip the entire frame into the heap.

The semantics are clear - the current values of the with() variables get copied at the point where the delegate literal becomes "instantiated"; whatever you put there is up to you.. xs0
Aug 18 2006
prev sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
xs0 wrote:
 Mikola Lysenko wrote:
 [snip]
 Any thoughts or comments?

Well, to me it seems that anything the compiler will try to do automatically will be wrong (or at least needlessly slow) in many cases. And a lot of the problem seems to be simply that one can't attach storage to a delegate without creating a whole class/struct, and doing that is too verbose to be used easily/often. So, why not simply have some syntax sugar for that? int delegate() fibs() { int a=0, b=1; return delegate with(a,b) { // it takes a and b with it ... } } Which would become exactly what you proposed. xs0

Would the instances of a & b of the fibs function be the same as the ones in the delegate? In other words, does the "with(a,b)" create a heap copy of a & b, for the delegate to use, or does it cause the original "int a=0, b=1;" to be heap allocated? -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 18 2006
parent xs0 <xs0 xs0.com> writes:
Bruno Medeiros wrote:
 xs0 wrote:
 Mikola Lysenko wrote:
 [snip]
 Any thoughts or comments?

Well, to me it seems that anything the compiler will try to do automatically will be wrong (or at least needlessly slow) in many cases. And a lot of the problem seems to be simply that one can't attach storage to a delegate without creating a whole class/struct, and doing that is too verbose to be used easily/often. So, why not simply have some syntax sugar for that? int delegate() fibs() { int a=0, b=1; return delegate with(a,b) { // it takes a and b with it ... } } Which would become exactly what you proposed. xs0

Would the instances of a & b of the fibs function be the same as the ones in the delegate? In other words, does the "with(a,b)" create a heap copy of a & b, for the delegate to use, or does it cause the original "int a=0, b=1;" to be heap allocated?

A heap copy is created at the point in code where the delegate is "evaluated". For example, the above case would function exactly the same as the following: int delegate() fibs() { int a=0, b=1; auto result = delegate with(a,b) { ... } a = 5000; b = -1; return result; } because it would become this behind the scenes: class _anonymousclass123 // more probably struct { int a, b; this(int a, int b) { this.a=a; this.b=b; } int _anonymousfunc() { ... } } int delegate() fibs() { int a=0, b=1; auto result = &((new _anonymousclass123(a, b))._anonymousfunc); a = 5000; b = -1; return result; } Of course, the compiler is free to allocate the fibs()'s a and b on the heap, if it determines the result is the same (it's potentially better because less stack is used), though I don't think it would actually matter in any realistic case.. xs0
Aug 18 2006