C++14 中的递归 lambda 函数

问题描述

在 C++11 中编写递归 lambda 函数有一个经常重复的技巧"，如下所示:

There is an oft-repeated 'trick' to write recursive lambda functions in C++11 that goes as follows:

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

assert( factorial(5) == 120 );

(例如 C++0x 中的递归 lambda 函数.)

尽管这种技术有两个直接的缺点:std::function 对象的目标被绑定(通过引用捕获)到一个非常特殊的 std::function<;Sig> 对象(这里是 factorial).这意味着生成的函子通常不能从函数返回，否则引用将悬空.

This technique has two immediate drawbacks though: the target of the std::function<Sig> object is tied (via the capture by reference) to a very particular std::function<Sig> object (here, factorial). This means that the resulting functor typically cannot be returned from a function, or else the reference would be left dangling.

另一个(虽然不那么直接)问题是使用 std::function 通常会阻止编译器优化，这是在其实现中需要类型擦除的副作用.这不是假设性的，可以很容易地进行测试.

Another (although less immediate) problem is that the use of std::function is typically going to prevent compiler optimizations, a side-effect of the need for type-erasure in its implementation. This is not hypothetical and can easily be tested.

在递归 lambda 表达式真的很方便的假设情况下，有没有办法解决这些问题?

In the hypothetical situation where recursive lambda expressions would really be convenient, is there a way to address those issues?

推荐答案

问题的症结在于，在 C++ lambda 表达式中，隐式 this 参数将始终引用到表达式的封闭上下文的对象(如果存在的话)，而不是由 lambda 表达式产生的函子对象.

The crux of the issue is that in a C++ lambda expression the implicit this parameter will always refer to the object of the enclosing context of the expression, if present at all, and not the functor object resulting from the lambda expression.

从匿名递归(有时也称为开放递归")中借用一片叶子，我们可以使用通用的 lambdaC++14 表达式重新引入一个显式参数来引用我们的递归函子:

Borrowing a leaf from anonymous recursion (sometimes also known as 'open recursion'), we can use the generic lambda expressions of C++14 to re-introduce an explicit parameter to refer to our would-be recursive functor:

auto f = [](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(/* hold on */); };

呼叫者现在有一个新的负担来拨打这种形式的电话，例如f(f, 5).由于我们的 lambda 表达式是自引用的，它实际上是自身的调用者，因此我们应该让 return n <;2 ?1 : n * self(self, n - 1);.

The caller now has a new burden of making calls of the form e.g. f(f, 5). Since our lambda expression is self-referential, it is in fact a caller of itself and thus we should have return n < 2 ? 1 : n * self(self, n - 1);.

由于在第一个位置显式传递函子对象本身的模式是可以预测的，我们可以重构这个丑陋的疣:

Since that pattern of explicitly passing the functor object itself in the first position is predictable, we can refactor this ugly wart away:

template<typename Functor>
struct fix_type {
    Functor functor;

    template<typename... Args>
    decltype(auto) operator()(Args&&... args) const&
    { return functor(functor, std::forward<Args>(args)...); }

    /* other cv- and ref-qualified overloads of operator() omitted for brevity */
};

template<typename Functor>
fix_type<typename std::decay<Functor>::type> fix(Functor&& functor)
{ return { std::forward<Functor>(functor) }; }

这允许一个人写:

auto factorial = fix([](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(self, n - 1); });

assert( factorial(5) == 120 );

我们成功了吗?由于 fix_type 对象包含它自己的函子，每次调用都会传递给它，因此永远不会有悬空引用的风险.所以我们的 factorial 对象可以真正地被无限地复制、移出、移入和移出函数.

Did we succeed? Since the fix_type<F> object contains its own functor which it passes to it for each call, there is never a risk of a dangling reference. So our factorial object can truly be endless copied, moved from, in and out of functions without hassle.

除了...虽然外部"调用者可以很容易地调用 factorial(5) 形式的调用，但事实证明在我们的 lambda 表达式内部，递归调用仍然看起来像 self(self,/* 实际有趣的参数 */).我们可以通过改变 fix_type 来改进这一点，而不是将 functor 传递给它自己，而是通过传递 *this 来代替.也就是说，我们传入 fix_type 对象，该对象负责在第一个位置传递正确的隐式为显式"参数:return functor(*this, std::forward<Args>(args)...);.然后递归变成n * self(n - 1)，它应该是.

Except... while the 'external' callers can readily make calls of the form factorial(5), as it turns out inside our lambda expression the recursive call still looks like self(self, /* actual interesting args */). We can improve on this by changing fix_type to not pass functor to itself, but by passing *this instead. That is, we pass in the fix_type object which is in charge of passing the correct 'implicit-as-explicit' argument in the first position: return functor(*this, std::forward<Args>(args)...);. Then the recursion becomes n * self(n - 1), as it should be.

最后，这是为 main 生成的代码，它使用 return factorial(5); 而不是断言(对于 fix_type):

00000000004005e0 <main>:
  4005e0:       b8 78 00 00 00          mov    eax,0x78
  4005e5:       c3                      ret    
  4005e6:       66 90                   xchg   ax,ax

[](auto&& self, int n)
{
    if(n < 2) return 1;               // return type is deduced here
    else return n * self(/* args */); // this has no impact
}