First-class polymorphic lamdas?

[ZombineDev via Digitalmars-d]

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