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