问题的关键是在 C++ lambda 表达式中implicit this
参数将始终引用表达式的封闭上下文的对象(如果存在),而不是由 lambda 表达式生成的函子对象。
借一片叶子匿名递归 http://en.wikipedia.org/wiki/Anonymous_recursion(有时也称为“开放递归”),我们可以使用 C++14 的通用 lambda 表达式重新引入explicit参数来引用我们的递归函子:
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);
.
由于在第一个位置显式传递函子对象本身的模式是可以预测的,因此我们可以重构这个丑陋的疣:
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<F>
对象包含自己的函子,每次调用时都会将其传递给它,因此永远不存在悬空引用的风险。所以我们的factorial
对象确实可以毫无麻烦地无限制地从函数中复制、移入和移出。
除了...虽然“外部”呼叫者可以轻松拨打以下形式的电话factorial(5)
,事实证明,在我们的 lambda 表达式中,递归调用仍然是这样的self(self, /* actual interesting args */)
。我们可以通过改变来改进这一点fix_type
不通过functor
到它自己,但是通过传递*this
反而。也就是说,我们传入fix_type
负责在第一个位置传递正确的“隐式作为显式”参数的对象:return functor(*this, std::forward<Args>(args)...);
。那么递归就变成了n * self(n - 1)
,应该如此。
最后,这是生成的代码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
编译器能够优化所有内容,就像使用普通的递归函数一样。
费用是多少?
精明的读者可能已经注意到一个奇怪的细节。在从非泛型 lambda 到泛型 lambda 的过程中,我添加了显式返回类型(即-> int
)。怎么会?
这与要推导的返回类型是条件表达式的类型有关,具体类型取决于对self
,正在推导哪种类型。快速阅读普通函数的返回类型推导 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3638.html建议按如下方式重写 lambda 表达式应该可行:
[](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 4.9 示例
- 完整代码,初尝味道 http://coliru.stacked-crooked.com/a/845e539a805f2658
- 完整代码,第二种味道 http://coliru.stacked-crooked.com/a/596268717ab16c94
- 完整代码,第一风格,C++11 http://coliru.stacked-crooked.com/a/87812c680208564b
- 可变参数的示例fix对于一组相互递归的 lambda 表达式 http://coliru.stacked-crooked.com/a/dff32e33a322427f