First-class polymorphic lamdas?
ZombineDev via Digitalmars-d
digitalmars-d at puremagic.com
Fri Feb 5 12:36:20 PST 2016
Background: I'm working on a transducers proposal for Phobos,
which
generalizes ranges to support push data-flow model (in addition
to the current pull-only) enabling composable algorithmic
transformations that can be applied to other sources of data such
as RX observables[0], signal & slots, channels, etc, as well as
the traditional data sources like containers, generator ranges
like `iota` and so on.
For example, this would allow one to use a single transformation
object e.g. { filter -> map -> uniq } for both synchronous and
asynchronous sequences of data.
The existing implementations that I'm studying are the one
introduced originally by Rich Hickey in Clojure[1] and Ableton's
Atria C++ library presented at CppCon 2015 [2].
My main obstacle is that they both rely on returning polymorphic
lambdas. E.g. polymorphic lambdas are need to be first-class
value types.
AFAIU, as per proposal N3649[3] which was accepted for C++14, if
one of the parameters of a lambda expression has type-specifier
`auto`, the compiler should generate a **non-templated**
placeholder struct with a **templated** call operator. This
allows the following code to work:
```
// Compile with -std=c++14
#include <iostream>
#include <vector>
using namespace std;
int main()
{
double local_var = 1.0;
auto add = [&](auto number) { local_var += number; };
add(3); cout << local_var << endl; // Prints 4
add(3.14); cout << local_var << endl; // Prints 7.14
add(20LL); cout << local_var << endl; // Prints 27.14
auto vec = vector<decltype(add)> { add, add, add, add };
for (auto&& fun : vec)
{
fun(1);
fun(0.5);
fun(2LL);
}
cout << local_var << endl; // Prints 41.14
}
```
In D, on the other hand, the compiler stores a reference to the
lambda function as a function-pointer (or a delagate-pointer, if
any local variables are captured), however this precludes support
for polymorhpic lambdas. AFAIU, delegates are implemented the way
they are because this enables much easier ABI interoperability.
Kenji worked on supporting polymorphic lambdas for DMD 2.070
[4][5] and his design
(if I understand it correctly) works like so:
```
alias add = (a,b) => a + b;
// is syntactically lowered to
alias add = add__compile_generated;
template add__compile_generated(T, U)
{
auto add__compile_generated(T a, U b) { return a + b; }
}
```
This by itself was a good enhancement, however it is incapable of
handling some very useful cases which C++14 supports, showcased
in the below example, which is adopted from the Transducers
CppCon 2015 lecture:
```
// 0) accumulate
// (nothing special here)
template <typename In, typename S, typename Rf>
S accumulate(In first, In last, S state, Rf step) {
for (; first != last; ++first) {
state = step(state, *first);
}
return state;
}
// 1) output_rf
// !!! Proper value-type with templated operator() !
auto output_rf = [] (auto out, auto input) {
*out++ = input;
return out;
};
// 2) map & filter a value-types with templated operator()
// that return value-types with tempalted operator()
// !!!
auto map = [] (auto fn) {
return [=] (auto step) {
return [=] (auto s, auto ...ins) {
return step(s, fn(ins...));
};
};
};
// !!!
auto filter = [] (auto pred) {
return [=] (auto step) {
return [=] (auto s, auto ...ins) {
return pred(ins...)?
step(s, ins) :
s;
};
};
};
auto f = filter([](int x) { return x > 0; });
auto xf = comp(
filter([](int x) { return x > 0; }),
map([](int x) { return x * 2; })
);
accumulate(first, last, out, xf);
// which turns into:
accumulate(first, last, out, comp(filter(pred), map(fn))
(output_rf));
// which turns into:
accumulate(first, last, out, filter(pred) (map(fn) (output_rf)));
// In order to replicate this in D I need to use ugly workarounds
like:
// * wrap the lambda expression in a dummy struct
// * put the body of the lambda expression in a templated opCall
// * return DummyStruct.init, in order to prevent the compiler
from trying to call
// the opCall function
// * @property just in case some future version decides to
enforce if for
// calling functions without parentheses
```
```
// 1) translated to D
// current syntax
@property auto outputRf()
{
struct OutputReducer
{
Out opCall(OutRange, E)(ref OutRange output, E elem)
if (isOutputRange!(OutRange, E))
{
output.put(elem);
return output;
}
}
return OutputReducer.init;
}
// desired syntax:
auto outputRf(O, E) = (ref O output, E elem) {
output.put(elem);
return output;
};
// 2) translated to D
// current syntax:
auto map(alias fn, Rf)(Rf step)
{
struct MapResult
{
Rf step;
auto opCall(S, Input...)
(auto ref S state, auto ref Input inputs)
{
return step(state, fn(inputs));
}
}
MapResult result = { step : step };
return result;
}
// New problems:
// * Need to use alias template parameter to capture the mapping
function.
// It would be better if I could take it as a value parameter
like in C++.
// * Need to manually put all of the captured variables as
members of the struct
// * Can't return MapResult(step), because the compiler confuses
it with a call to
// opCall, even though opCall is not a static function. Instead
I need to use
// the C struct initializer syntax.
//
// Desired syntax:
// 1. Omitting the type-specifier let's the compiler know
// that there should be a corresponding template parameter.
// 2. Allow for optional template parameters before the
// run-time parameters.
auto filter = (pred) {
return (step) {
return (S, Inputs...)(S s, Inputs ins) {
return pred(ins)?
step(s, ins) :
s;
};
};
};
```
To sum up, I want the compiler to do all those things for me,
like the C++14 compilers do. Presently it feels like I'm doing
the compiler's job.
[0]: http://reactivex.io/intro.html
[1]: https://www.youtube.com/watch?v=6mTbuzafcII
[2]: https://www.youtube.com/watch?v=vohGJjGxtJQ
[3]:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3649.html
[4]: http://dlang.org/changelog/2.070.0.html#alias-funclit
[5]: https://github.com/D-Programming-Language/dmd/pull/3638
More information about the Digitalmars-d
mailing list