www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Alias parameter predicates considered harmful?

reply Vladimir Panteleev <thecybershadow.lists gmail.com> writes:
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.
Mar 19 2021
parent reply Paul Backus <snarwin gmail.com> writes:
On Saturday, 20 March 2021 at 00:29:54 UTC, Vladimir Panteleev 
wrote:

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


Here's an idiom I've found useful in situations like this:

/// Pass struct members as arguments to a function
alias apply(alias fun) = args => fun(args.tupleof);

auto fun()  nogc
{
     int toAdd = 1;
     return iota(10)
         .zip(repeat(toAdd))
         .map!(apply!((n, toAdd) => n + toAdd));
}
Mar 19 2021
parent Vladimir Panteleev <thecybershadow.lists gmail.com> writes:
On Saturday, 20 March 2021 at 01:03:39 UTC, Paul Backus wrote:

 Here's an idiom I've found useful in situations like this:

 /// Pass struct members as arguments to a function
 alias apply(alias fun) = args => fun(args.tupleof);


Thank you. This is indeed a good trick.


 auto fun()  nogc
 {
     int toAdd = 1;
     return iota(10)
         .zip(repeat(toAdd))
         .map!(apply!((n, toAdd) => n + toAdd));
 }


Using `repeat` to pass data to range predicates feels dirty and 
wrong, though. :)
Mar 21 2021