www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - We need to have a way to say "convert this nested function into a

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Nested functions that allocate their environment dynamically can be 
quite useful. However, oftentimes the need is to convert the code plus 
the data needed into an anonymous struct that copies the state inside, 
similar to C++ lambdas that capture by value.

I wonder how to integrate that within the language nicely.


Andrei
Jun 05 2015
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
wrote:

 Nested functions that allocate their environment dynamically 
 can be quite useful. However, oftentimes the need is to convert 
 the code plus the data needed into an anonymous struct that 
 copies the state inside, similar to C++ lambdas that capture by 
 value.

 I wonder how to integrate that within the language nicely.


Some of us were discussing this at dconf. Essentially, we need a 
way to create a functor similar to how C++ lambdas do. The most 
straightforward way would involve string mixins, and you'd do 
something like

auto f = makeFunctor!"function code here"(arguments);
auto result = range.algorithm!f();

but that's not terribly pretty. Atila seemed to have figured out 
how we could do it with std.functional.partial, but I was too 
tired at the time to quite understand what his proposal was. So, 
we may have something better there. Ideally, we'd be able to just 
give a lambda, but that would put us right back in the problem of 
a delegate being allocated unnecessarily (though IIRC, Atila's 
suggestion somehow worked with lambdas and partial without 
allocating; I wish that I could remember what he proposed). But 
while it may or not be as pretty as we'd like, I think that it's 
at last _possible_ for us to have a shorthand for creating a 
functor by just providing the function's body and arguments that 
hold the values for its members. I'm certainly not against 
finding a language way to make it prettier though, since I'm not 
sure how clean we can really do it without language help.

That being said, we really should find a way to make it so that 
lambda's don't turn into delegates unless they really need to. In 
many, many cases, they should be plenty efficient without having 
to force the issue with functors, but they aren't, because we 
allocate for them unnecessarily. I don't know how easy it'll be 
though for the compiler devs to figure out how to optimize that, 
since sometimes you _do_ need to allocate a closure.

But having a shorthand way to create functors would definitely 
allow us to force the issue where necessary. And from what Liran 
was saying at dconf, that alone would make it possible for them 
to use a lot of Phobos that they can't right now. I suspect that 
unnecessary closures are actually the main reason that we have GC 
allocation problems with Phobos, since most algorithms just don't 
explicitly involve allocation unless they're doing array-specific 
stuff.

- Jonathan M Davis
Jun 05 2015
next sibling parent reply "Atila Neves" <atila.neves gmail.com> writes:
On Saturday, 6 June 2015 at 06:59:26 UTC, Jonathan M Davis wrote:

 On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
 wrote:

 Nested functions that allocate their environment dynamically 
 can be quite useful. However, oftentimes the need is to 
 convert the code plus the data needed into an anonymous struct 
 that copies the state inside, similar to C++ lambdas that 
 capture by value.

 I wonder how to integrate that within the language nicely.


 Some of us were discussing this at dconf. Essentially, we need 
 a way to create a functor similar to how C++ lambdas do. The 
 most straightforward way would involve string mixins, and you'd 
 do something like

 auto f = makeFunctor!"function code here"(arguments);
 auto result = range.algorithm!f();

 but that's not terribly pretty. Atila seemed to have figured 
 out how we could do it with std.functional.partial, but I was 
 too tired at the time to quite understand what his proposal 
 was. So, we may have something better there. Ideally, we'd be 
 able to just give a lambda, but that would put us right back in 
 the problem of a delegate being allocated unnecessarily (though 
 IIRC, Atila's suggestion somehow worked with lambdas and 
 partial without allocating; I wish that I could remember what 
 he proposed). But while it may or not be as pretty as we'd 
 like, I think that it's at last _possible_ for us to have a 
 shorthand for creating a functor by just providing the 
 function's body and arguments that hold the values for its 
 members. I'm certainly not against finding a language way to 
 make it prettier though, since I'm not sure how clean we can 
 really do it without language help.

 That being said, we really should find a way to make it so that 
 lambda's don't turn into delegates unless they really need to. 
 In many, many cases, they should be plenty efficient without 
 having to force the issue with functors, but they aren't, 
 because we allocate for them unnecessarily. I don't know how 
 easy it'll be though for the compiler devs to figure out how to 
 optimize that, since sometimes you _do_ need to allocate a 
 closure.

 But having a shorthand way to create functors would definitely 
 allow us to force the issue where necessary. And from what 
 Liran was saying at dconf, that alone would make it possible 
 for them to use a lot of Phobos that they can't right now. I 
 suspect that unnecessary closures are actually the main reason 
 that we have GC allocation problems with Phobos, since most 
 algorithms just don't explicitly involve allocation unless 
 they're doing array-specific stuff.

 - Jonathan M Davis


I remember the conversation but not really what I said. However, 
I just wrote this:


import std.stdio;
import std.algorithm;
import std.range;
import std.conv;
import std.traits;
import std.exception;


auto functorPartial(alias F, T)(T arg) {
     struct Functor {

         T arg;

         this(T args) { //because of opCall
             this.arg = arg;
         }

         auto opCall(U...)(U rest) {
             return F(arg, rest);
         }
     }

     return Functor(arg);
}

int adder(int i, int j) {
     return i + j;
}

void main(string[] args) {

     enforce(args.length > 1, "An argument must be passed in");

     auto arg = args[1].to!int; //to prove it's at runtime
     auto adderPartial = functorPartial!adder(arg); //runtime value
     writeln("adder result: ", adderPartial(4));

     //"subtracter"? "subtractor"? who cares
     auto subtracterPartial = functorPartial!((a, b) => a - 
b)(arg);
     writeln("subtracter partial: ", subtracterPartial(4));

}
Jun 06 2015
parent reply John Colvin <john.loughran.colvin gmail.com> writes:
On Saturday, 6 June 2015 at 12:49:37 UTC, Atila Neves wrote:

 On Saturday, 6 June 2015 at 06:59:26 UTC, Jonathan M Davis 
 wrote:

 On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
 wrote:

 Nested functions that allocate their environment dynamically 
 can be quite useful. However, oftentimes the need is to 
 convert the code plus the data needed into an anonymous 
 struct that copies the state inside, similar to C++ lambdas 
 that capture by value.

 I wonder how to integrate that within the language nicely.


 Some of us were discussing this at dconf. Essentially, we need 
 a way to create a functor similar to how C++ lambdas do. The 
 most straightforward way would involve string mixins, and 
 you'd do something like

 auto f = makeFunctor!"function code here"(arguments);
 auto result = range.algorithm!f();

 but that's not terribly pretty. Atila seemed to have figured 
 out how we could do it with std.functional.partial, but I was 
 too tired at the time to quite understand what his proposal 
 was. So, we may have something better there. Ideally, we'd be 
 able to just give a lambda, but that would put us right back 
 in the problem of a delegate being allocated unnecessarily 
 (though IIRC, Atila's suggestion somehow worked with lambdas 
 and partial without allocating; I wish that I could remember 
 what he proposed). But while it may or not be as pretty as 
 we'd like, I think that it's at last _possible_ for us to have 
 a shorthand for creating a functor by just providing the 
 function's body and arguments that hold the values for its 
 members. I'm certainly not against finding a language way to 
 make it prettier though, since I'm not sure how clean we can 
 really do it without language help.

 That being said, we really should find a way to make it so 
 that lambda's don't turn into delegates unless they really 
 need to. In many, many cases, they should be plenty efficient 
 without having to force the issue with functors, but they 
 aren't, because we allocate for them unnecessarily. I don't 
 know how easy it'll be though for the compiler devs to figure 
 out how to optimize that, since sometimes you _do_ need to 
 allocate a closure.

 But having a shorthand way to create functors would definitely 
 allow us to force the issue where necessary. And from what 
 Liran was saying at dconf, that alone would make it possible 
 for them to use a lot of Phobos that they can't right now. I 
 suspect that unnecessary closures are actually the main reason 
 that we have GC allocation problems with Phobos, since most 
 algorithms just don't explicitly involve allocation unless 
 they're doing array-specific stuff.

 - Jonathan M Davis


 I remember the conversation but not really what I said. 
 However, I just wrote this:


 import std.stdio;
 import std.algorithm;
 import std.range;
 import std.conv;
 import std.traits;
 import std.exception;


 auto functorPartial(alias F, T)(T arg) {
     struct Functor {

         T arg;

         this(T args) { //because of opCall
             this.arg = arg;
         }

         auto opCall(U...)(U rest) {
             return F(arg, rest);
         }
     }

     return Functor(arg);
 }

 int adder(int i, int j) {
     return i + j;
 }

 void main(string[] args) {

     enforce(args.length > 1, "An argument must be passed in");

     auto arg = args[1].to!int; //to prove it's at runtime
     auto adderPartial = functorPartial!adder(arg); //runtime 
 value
     writeln("adder result: ", adderPartial(4));

     //"subtracter"? "subtractor"? who cares
     auto subtracterPartial = functorPartial!((a, b) => a - 
 b)(arg);
     writeln("subtracter partial: ", subtracterPartial(4));

 }


Unfortunately this doesn't solve the problem in general with 
 nogc. When passing one of these functors to e.g. 
std.algorithm.map, there is no way to avoid the reference to the 
current scope. The challenge is to implement a (correct, see 
https://issues.dlang.org/show_bug.cgi?id=14982)  nogc version of 
this function without rewriting map:

auto foo(int a)
{
     return iota(10).map!(x => x + a);
}

I don't think it can be done without language changes.

I wonder what could be done if we could get inspect and 
manipulate context pointers in code...
Oct 28 2015
parent Atila Neves <atila.neves gmail.com> writes:
On Wednesday, 28 October 2015 at 11:42:08 UTC, John Colvin wrote:

 On Saturday, 6 June 2015 at 12:49:37 UTC, Atila Neves wrote:

 On Saturday, 6 June 2015 at 06:59:26 UTC, Jonathan M Davis 
 wrote:

 On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
 wrote:

 [...]


 Some of us were discussing this at dconf. Essentially, we 
 need a way to create a functor similar to how C++ lambdas do. 
 The most straightforward way would involve string mixins, and 
 you'd do something like

 auto f = makeFunctor!"function code here"(arguments);
 auto result = range.algorithm!f();

 but that's not terribly pretty. Atila seemed to have figured 
 out how we could do it with std.functional.partial, but I was 
 too tired at the time to quite understand what his proposal 
 was. So, we may have something better there. Ideally, we'd be 
 able to just give a lambda, but that would put us right back 
 in the problem of a delegate being allocated unnecessarily 
 (though IIRC, Atila's suggestion somehow worked with lambdas 
 and partial without allocating; I wish that I could remember 
 what he proposed). But while it may or not be as pretty as 
 we'd like, I think that it's at last _possible_ for us to 
 have a shorthand for creating a functor by just providing the 
 function's body and arguments that hold the values for its 
 members. I'm certainly not against finding a language way to 
 make it prettier though, since I'm not sure how clean we can 
 really do it without language help.

 That being said, we really should find a way to make it so 
 that lambda's don't turn into delegates unless they really 
 need to. In many, many cases, they should be plenty efficient 
 without having to force the issue with functors, but they 
 aren't, because we allocate for them unnecessarily. I don't 
 know how easy it'll be though for the compiler devs to figure 
 out how to optimize that, since sometimes you _do_ need to 
 allocate a closure.

 But having a shorthand way to create functors would 
 definitely allow us to force the issue where necessary. And 
 from what Liran was saying at dconf, that alone would make it 
 possible for them to use a lot of Phobos that they can't 
 right now. I suspect that unnecessary closures are actually 
 the main reason that we have GC allocation problems with 
 Phobos, since most algorithms just don't explicitly involve 
 allocation unless they're doing array-specific stuff.

 - Jonathan M Davis


 I remember the conversation but not really what I said. 
 However, I just wrote this:


 import std.stdio;
 import std.algorithm;
 import std.range;
 import std.conv;
 import std.traits;
 import std.exception;


 auto functorPartial(alias F, T)(T arg) {
     struct Functor {

         T arg;

         this(T args) { //because of opCall
             this.arg = arg;
         }

         auto opCall(U...)(U rest) {
             return F(arg, rest);
         }
     }

     return Functor(arg);
 }

 int adder(int i, int j) {
     return i + j;
 }

 void main(string[] args) {

     enforce(args.length > 1, "An argument must be passed in");

     auto arg = args[1].to!int; //to prove it's at runtime
     auto adderPartial = functorPartial!adder(arg); //runtime 
 value
     writeln("adder result: ", adderPartial(4));

     //"subtracter"? "subtractor"? who cares
     auto subtracterPartial = functorPartial!((a, b) => a - 
 b)(arg);
     writeln("subtracter partial: ", subtracterPartial(4));

 }


 Unfortunately this doesn't solve the problem in general with 
  nogc. When passing one of these functors to e.g. 
 std.algorithm.map, there is no way to avoid the reference to 
 the current scope. The challenge is to implement a (correct, 
 see https://issues.dlang.org/show_bug.cgi?id=14982)  nogc 
 version of this function without rewriting map:

 auto foo(int a)
 {
     return iota(10).map!(x => x + a);
 }

 I don't think it can be done without language changes.

 I wonder what could be done if we could get inspect and 
 manipulate context pointers in code...


And why is rewriting map off the table? The code below works. The 
only difference with respect to C++ is no syntax for variable 
capture.

import std.stdio: writeln;
import std.conv: to;
import std.range: isInputRange, iota;


void main(string[] args) {
     int a = args[1].to!int;
     writeln(foo(a));
}

auto foo(int i)  nogc  safe pure nothrow {
     return iota(i).map(functionPartial!((a, b) => a + b)(i));
}

auto map(R, F)(R range, F func) if(isInputRange!R) {
     static struct Result {
         R range;
         F func;

         auto front() {
             return func(range.front);
         }

         void popFront() {
             range.popFront;
         }

         bool empty() const {
             return range.empty;
         }
     }

     return Result(range, func);
}

auto functionPartial(alias F, T)(T arg) {

     static struct Function {

         T arg;

         this(T arg) { //because of opCall
             this.arg = arg;
         }

         auto opCall(U...)(U rest) const {
             return F(arg, rest);
         }
     }

     return Function(arg);
}

Atila
Oct 29 2015
prev sibling next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2015-06-06 08:59, Jonathan M Davis wrote:

 On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu wrote:

 Nested functions that allocate their environment dynamically can be
 quite useful. However, oftentimes the need is to convert the code plus
 the data needed into an anonymous struct that copies the state inside,
 similar to C++ lambdas that capture by value.

 I wonder how to integrate that within the language nicely.


 Some of us were discussing this at dconf. Essentially, we need a way to
 create a functor similar to how C++ lambdas do. The most straightforward
 way would involve string mixins, and you'd do something like

 auto f = makeFunctor!"function code here"(arguments);


Which could look like this with AST macros ;)

auto f = makeFunctor(args) {
    function code goes here, no strings are needed
}

-- 
/Jacob Carlborg
Jun 06 2015
next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 6 June 2015 at 13:44:51 UTC, Jacob Carlborg wrote:

 On 2015-06-06 08:59, Jonathan M Davis wrote:

 On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
 wrote:

 Nested functions that allocate their environment dynamically 
 can be
 quite useful. However, oftentimes the need is to convert the 
 code plus
 the data needed into an anonymous struct that copies the 
 state inside,
 similar to C++ lambdas that capture by value.

 I wonder how to integrate that within the language nicely.


 Some of us were discussing this at dconf. Essentially, we need 
 a way to
 create a functor similar to how C++ lambdas do. The most 
 straightforward
 way would involve string mixins, and you'd do something like

 auto f = makeFunctor!"function code here"(arguments);


 Which could look like this with AST macros ;)

 auto f = makeFunctor(args) {
    function code goes here, no strings are needed
 }


Well, this kind of syntax can be implemented without AST macros. 
But there are syntactic ambiguities if the delegate has 
parameters:

auto f = makeFunctor(args) (a, b) { }

Is the second pair of parens the delegate's parameter list, or a 
call a callable object returned by makeFunctor?

Besides, do we require a semicolon after the closing brace? If 
yes, that would be at odds with the rest of the language, but if 
not, we cannot easily chain such calls...
Jun 06 2015
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Saturday, 6 June 2015 at 13:44:51 UTC, Jacob Carlborg wrote:

 On 2015-06-06 08:59, Jonathan M Davis wrote:

 On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
 wrote:

 Nested functions that allocate their environment dynamically 
 can be
 quite useful. However, oftentimes the need is to convert the 
 code plus
 the data needed into an anonymous struct that copies the 
 state inside,
 similar to C++ lambdas that capture by value.

 I wonder how to integrate that within the language nicely.


 Some of us were discussing this at dconf. Essentially, we need 
 a way to
 create a functor similar to how C++ lambdas do. The most 
 straightforward
 way would involve string mixins, and you'd do something like

 auto f = makeFunctor!"function code here"(arguments);


 Which could look like this with AST macros ;)

 auto f = makeFunctor(args) {
    function code goes here, no strings are needed
 }


That may be, but Walter and Andrei have definitively said that 
we're never getting AST macros, so there isn't really in point in 
worrying about what could be done with them.

- Jonathan M Davis
Jun 06 2015
prev sibling parent reply "Meta" <jared771 gmail.com> writes:
On Saturday, 6 June 2015 at 06:59:26 UTC, Jonathan M Davis wrote:

 That being said, we really should find a way to make it so that 
 lambda's don't turn into delegates unless they really need to. 
 In many, many cases, they should be plenty efficient without 
 having to force the issue with functors, but they aren't, 
 because we allocate for them unnecessarily. I don't know how 
 easy it'll be though for the compiler devs to figure out how to 
 optimize that, since sometimes you _do_ need to allocate a 
 closure.


int n = 2;

auto r1 = [1, 2, 3].map!(x => x + n); //Ok
auto r2 = [1, 2, 3].map!(function(x) => x + n); //Error
auto r3 = [1, 2, 3].map!(curry!(function(x, n) => x + n, n)); //Ok

IMO this is pretty much the same thing as copying the variables 
you want to close over into a struct, with the advantage that we 
can do it today. The only thing is that you have to specify which 
variables you want to copy, which isn't necessarily a bad thing.
Jun 06 2015
parent "Meta" <jared771 gmail.com> writes:
On Saturday, 6 June 2015 at 18:32:14 UTC, Meta wrote:

 On Saturday, 6 June 2015 at 06:59:26 UTC, Jonathan M Davis 
 wrote:

 That being said, we really should find a way to make it so 
 that lambda's don't turn into delegates unless they really 
 need to. In many, many cases, they should be plenty efficient 
 without having to force the issue with functors, but they 
 aren't, because we allocate for them unnecessarily. I don't 
 know how easy it'll be though for the compiler devs to figure 
 out how to optimize that, since sometimes you _do_ need to 
 allocate a closure.


 int n = 2;

 auto r1 = [1, 2, 3].map!(x => x + n); //Ok
 auto r2 = [1, 2, 3].map!(function(x) => x + n); //Error
 auto r3 = [1, 2, 3].map!(curry!(function(x, n) => x + n, n)); 
 //Ok

 IMO this is pretty much the same thing as copying the variables 
 you want to close over into a struct, with the advantage that 
 we can do it today. The only thing is that you have to specify 
 which variables you want to copy, which isn't necessarily a bad 
 thing.


And apparently curry actually allocates a closure. Nevermind 
that, then.
Jun 06 2015
prev sibling next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
wrote:

 Nested functions that allocate their environment dynamically 
 can be quite useful. However, oftentimes the need is to convert 
 the code plus the data needed into an anonymous struct that 
 copies the state inside, similar to C++ lambdas that capture by 
 value.

 I wonder how to integrate that within the language nicely.


 Andrei


Related: deadalnix's DIP30 contains a section about fully-typed 
delegates:
http://wiki.dlang.org/DIP30
Jun 06 2015
parent deadalnix <deadalnix gmail.com> writes:
On Saturday, 6 June 2015 at 12:42:38 UTC, Marc Schütz wrote:

 On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
 wrote:

 Nested functions that allocate their environment dynamically 
 can be quite useful. However, oftentimes the need is to 
 convert the code plus the data needed into an anonymous struct 
 that copies the state inside, similar to C++ lambdas that 
 capture by value.

 I wonder how to integrate that within the language nicely.


 Andrei


 Related: deadalnix's DIP30 contains a section about fully-typed 
 delegates:
 http://wiki.dlang.org/DIP30


Damn it, I should have read the full thread :)
Oct 28 2015
prev sibling next sibling parent reply "Idan Arye" <GenericNPC gmail.com> writes:
On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
wrote:

 Nested functions that allocate their environment dynamically 
 can be quite useful. However, oftentimes the need is to convert 
 the code plus the data needed into an anonymous struct that 
 copies the state inside, similar to C++ lambdas that capture by 
 value.

 I wonder how to integrate that within the language nicely.


 Andrei


My solution: http://dpaste.dzfl.pl/aa013ff51f60

Can't make it  nogc though, because it thinks I'm trying to 
capture `a` and `b`...
Jun 06 2015
parent "Atila Neves" <atila.neves gmail.com> writes:
On Saturday, 6 June 2015 at 22:15:42 UTC, Idan Arye wrote:

 On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
 wrote:

 Nested functions that allocate their environment dynamically 
 can be quite useful. However, oftentimes the need is to 
 convert the code plus the data needed into an anonymous struct 
 that copies the state inside, similar to C++ lambdas that 
 capture by value.

 I wonder how to integrate that within the language nicely.


 Andrei


 My solution: http://dpaste.dzfl.pl/aa013ff51f60

 Can't make it  nogc though, because it thinks I'm trying to 
 capture `a` and `b`...


I forgot to do that. In my solution, functorPartial is  nogc. 
Just slapped it on and it still compiled.

Atila
Jun 06 2015
prev sibling parent deadalnix <deadalnix gmail.com> writes:
On Saturday, 6 June 2015 at 06:16:17 UTC, Andrei Alexandrescu 
wrote:

 Nested functions that allocate their environment dynamically 
 can be quite useful. However, oftentimes the need is to convert 
 the code plus the data needed into an anonymous struct that 
 copies the state inside, similar to C++ lambdas that capture by 
 value.

 I wonder how to integrate that within the language nicely.


 Andrei


http://wiki.dlang.org/DIP30 ?
Oct 28 2015