Рекурсивные лямбда-функции в С++ 14

Существует много повторяющийся "трюк" для записи рекурсивных лямбда-функций в С++ 11, который выглядит следующим образом:

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

assert( factorial(5) == 120 );

(например, Рекурсивные лямбда-функции в С++ 0x.)

Этот метод имеет два непосредственных недостатка: цель объекта std::function<Sig> привязана (через захват по ссылке) к особому объекту std::function<Sig> (здесь factorial). Это означает, что полученный функтор обычно не может быть возвращен из функции, иначе ссылка будет оставлена висевшей.

Другая (хотя и менее непосредственная) проблема заключается в том, что использование std::function обычно предотвращает оптимизацию компилятора, побочный эффект необходимости стирания стилей в его реализации. Это не гипотетично и может быть легко протестировано.

В гипотетической ситуации, когда рекурсивные лямбда-выражения действительно будут удобны, есть ли способ решить эти проблемы?

Ответ 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 передается). Я оставляю это читателю, чтобы выбрать, какой компромисс сделать: менее вычитание типа или менее уродливые рекурсивные вызовы (также, конечно, вполне возможно иметь доступ к любому вкусу в любом случае).

Примеры GCC 4.9

Ответ 2

Это не лямбда-выражение, но чуть больше кода, работает с С++ 98 и может рекурсивно:

struct {
    int operator()(int n) const {
        return n < 2 ? 1 : n * (*this)(n-1);
    }
} fact;
return fact(5);

В соответствии с [class.local]/1 он имеет доступ ко всем именам, к которым имеет доступ закрывающая функция, что важно для частных имен в функции-члене.

Конечно, не являясь лямбда, вам нужно написать конструктор, если вы хотите захватить состояние вне объекта функции.