why do lambda functions in c++11 not have function<> types?

Question

I am playing around with the c++11 functional features. One thing I find odd is that the type of a lambda function is actually NOT a function<> type. What's more, lambda's do not seem to play really well with the type-inferencing mechanism.

Attached is a small example in which I tested flipping the two arguments of a function for adding two integers. (The compiler I used was gcc 4.6.2 under MinGW.) In the example, the type for addInt_f has been explicitly defined using function<> while addInt_l is a lambda whose type is type-inferenced with auto.

When I compiled the code, the flip function can accept the explicitly type-defined version of addInt but not the lambda version, giving an error saying that, testCppBind.cpp:15:27: error: no matching function for call to 'flip(<lambda(int, int)>&)'

The next few lines show that the lambda version (as well as a 'raw' version) can be accepted if it's explicitly cast to the appropriate function<> type.

So my questions are:

1. Why is it that a lambda function does not have a function<> type in the first place? In the small example, why does not addInt_l have function<int (int,int)> as the type instead of having a different, lambda type? From the perspective of functional programming, what's the difference between a function/functional object and a lambda?

2. If there is a fundamental reason that these two have to be different. I heard that lambda's can be converted to function<> but they are different. Is this a design issue/defect of C++11, an implementation issue or is there a benefit in distinguishing the two as the way it is? It seems that the type-signature of addInt_l alone has provided enough information about the parameter and return types of the function.

3. Is there a way to write the lambda so that the above mentioned explicit type-casting can be avoided?

Thanks in advance.

    //-- testCppBind.cpp --
    #include <functional>
    using namespace std;
    using namespace std::placeholders;

    template <typename T1,typename T2, typename T3>
    function<T3 (T2, T1)> flip(function<T3 (T1, T2)> f) { return bind(f,_2,_1);}

    function<int (int,int)> addInt_f = [](int a,int b) -> int { return a + b;};
    auto addInt_l = [](int a,int b) -> int { return a + b;};

    int addInt0(int a, int b) { return a+b;}

    int main() {
      auto ff = flip(addInt_f);   //ok
      auto ff1 = flip(addInt_l);  //not ok
      auto ff2 = flip((function<int (int,int)>)addInt_l); //ok
      auto ff3 = flip((function<int (int,int)>)addInt0);  //ok

      return 0;
    }

Answer 1

std::function is a tool useful to store any kind of callable object regardless of its type. In order to do this it needs to employ some type erasure technique, and that involves some overhead.

Any callable can be implicitly converted to a std::function, and that's why it usually works seamlessly.

I'll repeat to make sure it becomes clear: std::function is not something just for lambdas or function pointers: it's for any kind of callable. That includes things like struct some_callable { void operator()() {} };, for example. That is a simple one, but it could be something like this instead:

struct some_polymorphic_callable {
    template <typename T>
    void operator()(T);
};

A lambda is just yet another callable object, similar to instances of the some_callable object above. It can be stored in a std::function because it's callable, but it doesn't have the type erasure overhead of std::function.

And the committee plans to make lambdas polymorphic in the future, i.e., lambdas that look like some_polymorphic_callable above. Which std::function type would such a lambda be?

---

Now... Template parameter deduction, or implicit conversions. Pick one. That's a rule of C++ templates.

To pass a lambda as a std::function argument, it needs to be implicitly converted. Taking a std::function argument means that you're choosing implicit conversions over type deduction. But your function template needs the signature to be deduced or provided explicitly.

The solution? Don't restrict your callers to std::function. Accept any kind of callable.

template <typename Fun>
auto flip(Fun&& f) -> decltype(std::bind(std::forward<Fun>(f),_2,_1))
{ return std::bind(std::forward<Fun>(f),_2,_1); }

---

You may now be thinking why do we need std::function then. std::function provides type erasure for callables with a known signature. That essentially makes it useful to store type-erased callables and to write virtual interfaces.

Answer 2

1. Because function<> employs type erasure. This allows several different function-like types to be stored in a function<>, but incurs a small runtime penalty. Type erasure hides the actual type (your specific lambda) behind a virtual function interface.
2. There is a benefit to this: one of the C++ design "axioms" is to never add overhead unless it is really needed. Using this setup, you do not have any overhead when using type inference (use auto or pass as a template parameter), but you still have all the flexibility to interface with non-template code through function<>. Also note that function<> is not a language construct, but a component of the standard library that can be implemented using simple language features.
3. No, but you can write the function to just take the type of the function (language construct) instead of the specifics of the function<> (library construct). Of course, that makes it a lot harder to actually write down the return type, since it does not directly give you the parameter types. However, using some meta-programming a la Boost.FunctionTypes you can deduce these from the function you pass in. There are some cases where this is not possible though, for example with functors that have a templated operator().