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):
Finally, this is the generated code for a main that uses return factorial(5); instead of the assertion (for either flavour of fix_type):
00000000004005e0 <main>:
4005e0: b8 78 00 00 00 mov eax,0x78
4005e5: c3 ret
4005e6: 66 90 xchg ax,ax
编译器能够优化所有内容，就像使用普通的递归函数一样.
The compiler was able to optimize everything away, as it would have done with a run-off-the-mill recursive function.
精明的读者可能已经注意到一个奇怪的细节.在从非泛型到泛型 lambda 的转变过程中，我添加了一个显式返回类型(即 -> int).怎么来的?
The astute reader may have noticed one curious detail. In the move from a non-generic to a generic lambda, I added an explicit return type (i.e. -> int). How come?
这与要推导的返回类型是条件表达式的类型这一事实有关，哪种类型取决于对self的调用，推导的是哪种类型.快速阅读正常函数的返回类型推导如下重写 lambda 表达式应该可行:
This has to do with the fact that the return type to be deduced is the type of the conditional expression, which type depends on the call to self, which type is being deduced. A quick reading of Return type deduction for normal functions would suggest that rewriting the lambda expression as follows should work:
[](auto&& self, int n)
{
if(n < 2) return 1; // return type is deduced here
else return n * self(/* args */); // this has no impact
}
GCC 实际上只会接受带有 fix_type 的第一种形式的代码(通过 functor 的那个).我无法确定抱怨其他形式(*this 被传递的地方)是否正确.我让读者选择权衡取舍:减少类型推导，或者减少丑陋的递归调用(当然，无论如何也完全有可能获得任何一种风格).
GCC will in fact accept this code with the first form of fix_type only (the one that passes functor). I'm not able to determine if it is right to complain about the other form (where *this is passed). I leave it to the reader to choose what trade-off to make: less type deduction, or less ugly recursive calls (it's also of course completely possible to have access to either flavour anyway).
- 完整代码，初尝
- 完整代码，二次元
- 完整代码，第一版，C++11
- 一组相互递归的 lambda 表达式的可变参数
fix示例
相关文章