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 

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

 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 

 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 


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



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



 
 
 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 

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



 
 
 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

 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

lambda expression syntax was conceived. 

What in D is: 
(int a, int b) { return a + b; }


(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:
'+


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.




 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




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

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

 lambda expression syntax was conceived. 
 
 What in D is: 
 (int a, int b) { return a + b; }
 

 (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:
 '+
 

 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.
 

 
 

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 

 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 

 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 

 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 


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 

 
 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:











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


















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:



... 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:







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:








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:


 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:
 


 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:


 frame for delegates.


 



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 

 


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:


  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


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 

 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
     };


<snip>

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
}
}


 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


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