Ответ 1
Суть проблемы заключается в том, что в выражении лямбда С++ неявный параметр this всегда будет ссылаться на объект охватывающего контекста выражения, если он присутствует вообще, а не на объект-функтор, являющийся результатом выражения лямбда.
Заимствуя лист из анонимной рекурсии (иногда также называемой "открытой рекурсией" ), мы можем использовать общие лямбда-выражения С++ 14 для повторного введения явный параметр для ссылки на наш потенциальный рекурсивный функтор:
auto f = [](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(/* hold on */); };
У вызывающего абонента теперь есть новое бремя совершения вызовов формы, например. f(f, 5). Поскольку наше лямбда-выражение является самореференциальным, оно на самом деле является самозваным, поэтому мы должны иметь 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), как это получается внутри нашего лямбда-выражения, рекурсивный вызов по-прежнему выглядит как self(self, /* actual interesting args */). Мы можем улучшить это, изменив fix_type, чтобы не передать functor себе, а вместо этого перейдя *this. То есть мы передаем объект fix_type, который отвечает за передачу правильного аргумента "implicit-as-explicit" в первой позиции: 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
Компилятор смог оптимизировать все, как это было бы с помощью рекурсивной функции run-off-mill.
Каковы затраты?
Проницательный читатель, возможно, заметил одну любопытную деталь. При переходе от не-generic к общей лямбда я добавил явный тип возврата (т.е. -> int). Почему?
Это связано с тем, что возвращаемый тип, который нужно вывести, является типом условного выражения, тип которого зависит от вызова self, тип которого выведен. Быстрое чтение вывода типа возврата для нормальных функций предполагает, что переработка выражения лямбда следующим образом должна работать:
[](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 передается). Я оставляю это читателю, чтобы выбрать, какой компромисс сделать: менее вычитание типа или менее уродливые рекурсивные вызовы (также, конечно, вполне возможно иметь доступ к любому вкусу в любом случае).