| |
 | Posted by Vladimir Panteleev |  Permalink Reply |
|
Vladimir Panteleev 
| Sorry if this is well-trodden ground - it's something I maybe should have realized a long time ago.
Currently we use alias parameters to specify predicates for map, filter, sort etc. This generally works well, but has some limitations.
One big limitation is the necessity to create a closure to access variables that are not part of the range. This is a reoccurring problem:
https://forum.dlang.org/post/lwcciwwvwdizlrwoxyiu@forum.dlang.org
https://forum.dlang.org/thread/mgcflvidsuentxvwbmih@forum.dlang.org
https://forum.dlang.org/post/rkfezigmrvuzkztxqqxy@forum.dlang.org
Example illustrating the problem:
auto fun() @nogc
{
int toAdd = 1;
return iota(10).map!(n => n + toAdd);
}
In order to make toAdd accessible to the predicate, it must create a closure to host it (and nest the map instantiation inside the closure).
Another example is the age-old issue with taskPool.parallel. Because it is already a method, you can't give it a predicate with a context pointer, making it useless for most potential applications. (Someone even contributed a DMD pull request to attempt to address this, by introducing a second context pointer, but it is getting reverted because GDC/LDC can't implement this. Oops!)
However, there is apparently a simple solution. Instead of using alias parameters for predicates, pass predicates as functors via regular parameters:
struct Map(R, Pred)
{
@nogc:
R r;
Pred pred;
@property bool empty() { return r.empty; }
@property auto front() { return pred(r.front); }
void popFront() { return r.popFront(); }
}
auto map(R, Pred)(R r, Pred pred) @nogc { return Map!(R, Pred)(r, pred); }
auto fun() @nogc
{
struct Pred
{
@nogc:
int toAdd;
int opCall(int i) { return i + toAdd; }
}
Pred pred;
pred.toAdd = 1;
return iota(10).map(pred);
}
The call site is a bit noisy in this case. When self-contained state isn't required, it's easy enough to wrap arbitrary lambdas in a functor:
struct Pred(alias fun)
{
auto opCall(Args)(auto ref Args args) { return fun(args); }
}
auto pred(alias fun)()
{
return Pred!fun.init;
}
assert(5.iota.map(pred!(n => n*2)).equal([0, 2, 4, 6, 8]));
(Or you could just use a simple delegate.)
Now that I think of it, this is starting to look really familiar... wasn't there a language that nobody uses that has syntax to transform lambda-like inline functions into essentially functor-like class types that can grab copies or references of locals? :)
Putting the two head-to-head:
- The syntax for alias parameters is nicer right now. (Though maybe D can steal some syntax from the above-mentioned language later.)
- Alias parameters may or may not include an implicit context pointer. Functor parameters ALSO can include a context pointer - either explicit or implicit (structs themselves can have a context pointer, and you can even control it by using alias parameters on the struct!)
- Functor parameters can have additional self-contained state! This enables the map-with-state-in-@nogc use case mentioned at the top.
- You can have as many functor parameters with different contexts as you like. Even the DMD pull request added only a second context pointer.
- Unlike delegates, there is no opaqueness (everything is inlinable), and you can still use template (type-inferred) arguments in your predicate.
- If you don't need a context pointer, or any self-contained state (i.e your predicate is a pure function), your functor type will still have the size of 1 byte because of a stupid rule D inherited from C. This might be optimized out as a parameter, but if you want to store it somewhere (like, your range type), it may matter. Seriously, we should probably just kill this and make extern(D) structs with no explicit alignment zero-sized - we already have zero-sized types (albeit useless), and - if you're using non-extern(C) empty structs with no align() directives or explicit padding for alignment, you were aiming that gun at your foot already.
- All delegates are already functors! As far as I can see, currently there is actually no way to pass a standard delegate to map. map!dg won't do what one would think does - it will pass a reference to the "dg" variable wherever that is (probably your function's stack), creating a closure. https://run.dlang.io/is/PcFCZ9
Considering that you can easily wrap an alias parameter predicate into a functor predicate (but not the other way around), functor predicates seem to be essentially strictly superior to alias predicates. Is there even any reason to continue using alias predicates? Should we start overhauling Phobos range functions to accept functor predicates? We could keep the alias versions as simple forwarders to the functor ones.
BTW, another approach specifically to the map problem would be to allow nesting map in a struct. Currently I don't see a way to do this, i.e.:
struct S
{
int toAdd;
int pred(int x) { return x + toAdd; }
void test()
{
iota(5).map!pred;
}
}
doesn't work. (Though a very long time ago I proposed a pull request which enabled this: https://github.com/dlang/dmd/pull/3361)
Granted, this is a bit iffy because you will probably want to return map's range from the method, in which case the context pointer that the map range has to S may or may not continue being valid.
|
