Alias parameter predicates considered harmful?
Vladimir Panteleev
thecybershadow.lists at gmail.com
Sat Mar 20 00:29:54 UTC 2021
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- at 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.
More information about the Digitalmars-d
mailing list