Character Output

Lambda: Overloading and Recursive

Lambda expression is very handy, but there’re some restrictions – it can’t be overloaded and it can’t call itself. Well, only at language level. Remember we’re talking about c++? It’s fairly easy to overload lambdas and make it recursive-enabled in a library fashion.

Recursive Lambda in C++11

Of course, you can already use lambda recursively in c++11, with the help of std::function.

std::function<int(int)> factorial = [&factorial](int i)
{
    return i == 0? 1 : i * factorial(i - 1);
};

But then you suffer the runtime penalty of std::function.

Recursive Lambda in C++1y

With the introduction of generic lambda in c++1y, we can avoid the overhead:

auto factorial = [](auto self, int i)->int
{
    return i == 0? 1 : i * self(self, i - 1);
};

Note that how the recursive call is written: self(self, i - 1). In the user code, you have to call it in the same way:

factorial(factorial, n);

It’s a bit ugly because the functor itself has to appear twice in one call. To make it more appealing, with the same signature as a normal one, we can make a wrapper:

template<class F>
struct recursive
{
    template<class... Ts>
    decltype(auto) operator()(Ts&&... ts) const
    {
        return f(*this, std::forward<Ts>(ts)...);
    }
    
    F f;
};

auto const make_recursive = [](auto f)
{
    return recursive<decltype(f)>{std::move(f)};
};

Now we can use make_recursive to define the lambda:

auto factorial = make_recursive([](auto& self, int i)->int
{
    return i == 0? 1 : i * self(i - 1);
});

Voila! In the lambda body, we can spell self(i - 1) instead of self(self, i - 1) as in the above example. In the user code, we can call factorial(n) as usual. Perfect, isn’t it?

Let’s move on to the next topic – overloading.

Overload Lambdas

C++ allows us to overload functions, but what a lambda expression gives us is a closure, that is, a function object. You can’t overload the variables:

auto f = [](){...};
auto f = [](int){...};

Yet, we can make a wrapper. The simplest way that comes to mind is:

template<class... Fs>
struct overload : Fs...
{
    overload(Fs&&... fs)
      : Fs(std::move(fs))...
    {}
};

auto const make_overload = [](auto... fs)
{
    return overload<decltype(fs)...>{std::move(fs)...};
};

Make an overloaded functor and call it:

auto f = make_overload
(
    []{ std::cout << "1\n"; }
  , [](int){ std::cout << "2\n"; }
);
 
f();
f(2);

It works fine with clang 3.5, but g++ 4.9.1 doesn’t buy it. Actually, g++ seems to be correct here, see this stackoverflow question.

So, we have to use operator() from the bases explicitly, but it’s illegal to write:

using Fs::operator()...;

Instead, we have to do:

template<class F, class... Fs>
struct overload : F, overload<Fs...>
{
    using F::operator();
    using overload<Fs...>::operator();

    overload(F&& f, Fs&&... fs)
      : F(std::move(f))
      , overload<Fs...>(std::move(fs)...)
    {}
};

template<class F>
struct overload<F> : F
{
    using F::operator();

    overload(F&& f)
      : F(std::move(f))
    {}
};

That’s it.

So far I’ve shown you how to make a recursive lambda and how to overload them, what next? Well, let’s combine the two :)

Recursive and Overloaded Lambda

Recursive template function calls are often not really recursive, actually different functions are called, they just happened to have the same name, at least to the programmer. And usually, we need to deal with the special cases by overloading the function. Combing both tricks makes generic lambda more powerful.

Let’s write a helper function that ties them up:

auto const make_recursive_overload = [](auto&&... fs)
{
    return make_recursive(make_overload(static_cast<decltype(fs)>(fs)...));
};

Now we can play with it. For instance, to implement a recursive for_each for variadic param-pack:

auto const for_each = make_recursive_overload
(
    [](auto& self, auto&& f, auto&& t, auto&&... ts)
    {
        f(static_cast<decltype(t)>(t));
        self(f, static_cast<decltype(ts)>(ts)...);
    }
  , [](auto& self, auto&& f) {}
);

The first overload does the recursive call, and the second one is the termination condition. This is how it is used:

for_each([](auto&& val)
{
    std::cout << val << ',';
}, 1, 2, 3, 4);

If you remember my last post about param-pack, you could have more fun:

auto const each = [](auto&& f)
{
    return [&](auto&&... ts)
    {
        for_each(f, static_cast<decltype(ts)>(ts)...);
    };
};

auto p = pack(1, 2, 3, 4);
p(each([](auto&& val)
{
    std::cout << val << ',';
}));

Pack/Unpack without Using Tuple

Args packing/unpacking is particularly useful when the args aren’t handled immediately, but stored for later invocation. In this post, I’ll show you a practical way to do it without resorting to tuple.

Before the journey start, let’s see how we used to do args packing/unpacking using std::tuple and std::index_sequence.

The Offical Way

Packing the args is quite easy:

auto args = std::make_tuple(1, "hey");

Unpacking needs more code, we first write a helper function invoke that can be reused:

template<class F, std::size_t... Ns, class... Ts>
decltype(auto) invoke_impl(F& f, std::index_sequence<Ns...>, std::tuple<Ts...> const& params)
{
    return f(std::get<Ns>(params)...);
}

template<class F, class... Ts>
decltype(auto) invoke(F&& f, std::tuple<Ts...> const& params)
{
    return invoke_impl(f, std::make_index_sequence<sizeof...(Ts)>(), params);
}

Now you can use it to unpack the args:

invoke(do_something, args);

Not hard at all. But do we really need std::tuple for that kind of thing? Well, no. In c++1y, the language itself provides us a powerful tool – generic lambda.

The Alternative

The idea is simple:

template<class... T>
auto pack(T... t)
{
    return [=](auto&& f)->decltype(auto)
    {
        return f(t...);
    };
};

And the usage is very simple as well:

auto args = pack(1, "hey");
args(do_something);

However, it doesn’t support move-only types. Before we step further, there’s another noticeable c++1y feature – init-capture, which lets you do something like:

template<class T>
auto pack(T t)
{
    return [t=std::move(t)](auto&& f)->decltype(auto)
    {
        return f(t);
    };
};

As a imaginative C++ programmer, you probably already come up with this:

template<class... T>
auto pack(T... t)
{
    return [t=std::move(t)...](auto&& f)->decltype(auto)
    {
        return f(t...);
    };
};

Looks great, but it won’t compile! There’s a thread in the ISO C++ group discussing this issue if you’re interested.

Anyway, we have to find a workaround. We know that people can already do this in c++11 without init-capture, so the situation is same here. The basic idea is: make a move-proxy the does move when copying.

template<class T>
struct mover
{
    mover(T const& val) : val(val) {}

    mover(T&& val) : val(std::move(val)) {}

    mover(mover const& other) = default;

    mover(mover&& other) = default; 

    mover(mover& other) : val(std::move(other.val)) {}

    operator T const&() const
    {
        return val; 
    }

    T val;
};

And to decide when is needed or beneficial to apply the mover, we write a helper trait wrap_t:

template<class T>
using wrap_t = typename std::conditional
    <
        std::is_move_constructible<T>::value
    && !std::is_trivially_copy_constructible<T>::value
      , mover<T>
      , T
    >::type;

In case that your standard library doesn’t support std::is_trivially_copy_constructible, use instead:

template<class T>
using wrap_t = typename std::conditional
    <
        std::is_move_constructible<T>::value
    && !(std::is_copy_constructible<T>::value && boost::has_trivial_copy_constructor<T>::value)
      , mover<T>
      , T
    >::type;

But boost::has_trivial_copy_constructor seems to report false positive, so we also use std::is_copy_constructible here.

We can implement pack as below:

template<class... Ts>
auto pack_impl(wrap_t<Ts>... ts)
{
    return [=](auto&& f)->decltype(auto)
    {
        return f(static_cast<Ts const&>(ts)...);
    };
}

auto const pack = [](auto&&... ts)
{
    return pack_impl<std::decay_t<decltype(ts)>...>(static_cast<decltype(ts)>(ts)...);
};

If you’re confused about static_cast<decltype(ts)>, it’s just perfect forwarding, exactly the same as std::forward, written in another form.

You can use normal function template instead of generic lambda here, but I’d like to use lambda when possible since it may provide some benefit over function template, for example, the symbol names of lambda are in general shorter than those of template functions with many types encoded, and it can be an effective factor of compile/link time.

We’re almost done here. Let’s write a special class A to test the behavior:

struct A
{
    A() = default;

    A(A&&)
    {
        std::cout << "move\n";
    }

    A(A const&)
    {
        std::cout << "copy\n";
    }
};

Now test it:

A a;
std::cout <<"p1------------\n";
auto p1 = pack(std::move(a));
std::cout <<"p2------------\n";
auto p2 = std::move(p1);
std::cout <<"p3------------\n";
auto p3 = p2;

code above will print:

p1------------
move
move
p2------------
move
p3------------
copy

Note that when constructing p1, A is moved twice, if the language supports init-capture on parameter pack, there’d be only one move. Still, there’s some workaround if you really care about it, but let me stop here :p

Startup

I didn’t write blogs, so this is my first time to build a blog (or something alike).

Building this blog is itself an interesting thing and was somewhat frustrating but now encouraging.

The very first thing is to decide where to host the blog, since I hosted my own code at Github, and it provides Github Page for docs hosting as well, which is Jekyll powered, it seems a reasonable choice, and most importantly, I love its domain: github.io ;-)

Using Jekyll, you can blog with Github Page, which is very cool but, I don’t want to install Jekyll, what I prefer is a clean Github-page repo with Jekyll enabled. First I found JekyllBootstrap, but it also requires installing, then I found gh-pages-blog, which is what you see now.

Still one thing – comments section – is missing, which I think is good for a technical blog. Github Page deosn’t provide such service, it’s completely static-content. Yet, there’s Disqus, a comment system, which is widely used on the Github-page hosted blogs, but I don’t want to use it :p

Remember the issues page we have in Github? I think it’s something we can exploit, but I’m not a web guru, it may not be easy for me to do this. Fortunately, someone has exaclty the same idea, and he realized the idea, that’s it! See Ivan’s blog post on how to do this if you’re interested.

So, that’s the story how this blog was built, probably the only blog entry about web technology. From now on, I’d like to share some C++ ideas with you.

Stay tuned!