Лямбда возвращается сама: это законно?

Редактировать: Кажется, есть некоторые разногласия по поводу того, является ли эта конструкция строго допустимой в соответствии со спецификацией C++. Преобладает мнение, что это неверно. См. Другие ответы для более подробного обсуждения. Остальная часть этого ответа применяет если, конструкция действительна; измененный код ниже работает с MSVC++ и gcc, а OP опубликовал дополнительный измененный код, который также работает с clang.

Это неопределенное поведение, потому что внутренняя лямбда захватывает параметр self по ссылке, но self выходит за пределы области действия после return в строке 7. Таким образом, когда возвращенная лямбда выполняется позже, она обращается к ссылке на переменную, которая вышла из строя. объема.

#include <iostream>
int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto self) {
      return [&](auto b) {
        std::cout << (a + b) << std::endl;
        return self(self); // <-- using reference to 'self'
      };
  };
  it(it)(4)(6)(42)(77)(999); // <-- 'self' is now out of scope
}

Запуск программы с valgrind иллюстрирует это:

==5485== Memcheck, a memory error detector
==5485== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5485== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5485== Command: ./test
==5485== 
9
==5485== Use of uninitialised value of size 8
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485== 
==5485== Invalid read of size 4
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485==  Address 0x4fefffdc4 is not stack'd, malloc'd or (recently) free'd
==5485== 
==5485== 
==5485== Process terminating with default action of signal 11 (SIGSEGV)
==5485==  Access not within mapped region at address 0x4FEFFFDC4
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485==  If you believe this happened as a result of a stack
==5485==  overflow in your program's main thread (unlikely but
==5485==  possible), you can try to increase the size of the
==5485==  main thread stack using the --main-stacksize= flag.
==5485==  The main thread stack size used in this run was 8388608.

Вместо этого вы можете изменить внешнюю лямбду так, чтобы она брала себя по ссылке, а не по значению, тем самым избегая кучи ненужных копий, а также решая проблему:

#include <iostream>
int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto& self) { // <-- self is now a reference
      return [&](auto b) {
        std::cout << (a + b) << std::endl;
        return self(self);
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

Это работает:

==5492== Memcheck, a memory error detector
==5492== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5492== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5492== Command: ./test
==5492== 
9
11
47
82
1004

Кажется, лязг - это правильно. Рассмотрим упрощенный пример:

auto it = [](auto& self) {
    return [&self]() {
      return self(self);
    };
};
it(it);

Давайте пройдемся по нему как с компилятором (немного):

• Тип it - Lambda1 с оператором вызова шаблона.
• it(it); запускает создание оператора вызова
• Тип возврата оператора вызова шаблона - auto, поэтому мы должны его вывести.
• Мы возвращаем лямбда, захватывающую первый параметр типа Lambda1.
• Эта лямбда также имеет оператор вызова, который возвращает тип вызова self(self).
• Примечание: self(self) - это именно то, с чего мы начали!

Таким образом, тип не может быть выведен.

Программа плохо сформирована (clang правый) на [dcl.spec.auto] / 9:

If the name of an entity with an undeduced placeholder type appears in an expression, the program is ill-formed. Once a non-discarded return statement has been seen in a function, however, the return type deduced from that statement can be used in the rest of the function, including in other return statements.

По сути, вывод типа возвращаемого значения внутренней лямбды зависит от него самого (названная здесь сущность является оператором вызова), поэтому вы должны явно указать тип возвращаемого значения. В данном конкретном случае это невозможно, потому что вам нужен тип внутренней лямбды, но вы не можете назвать его. Но есть и другие случаи, когда попытка принудительно использовать такие рекурсивные лямбды может сработать.

Даже без этого у вас есть висячая ссылка.

Позвольте мне уточнить некоторые детали после обсуждения с кем-то более умным (например, T.C.). Существует важное различие между исходным кодом (слегка сокращенным) и предлагаемой новой версией (также сокращенным):

auto f1 = [&](auto& self) {
  return [&](auto) { return self(self); } /* #1 */ ; /* #2 */
};
f1(f1)(0);

auto f2 = [&](auto& self, auto) {
  return [&](auto p) { return self(self,p); };
};
f2(f2, 0);

И это то, что внутренняя экспрессия self(self) не зависит от f1, но self(self, p) зависит от f2. Когда выражения независимы, их можно использовать ... с готовностью ([temp.res] / 8, например, как static_assert(false) является серьезной ошибкой, независимо от того, создан ли шаблон, в котором он находится, или нет).

Для f1 компилятор (например, clang) может попытаться быстро создать экземпляр. Вы знаете выведенный тип внешней лямбды, как только вы дойдете до этого ; в точке #2 выше (это тип внутренней лямбды), но мы пытаемся использовать его раньше (подумайте об этом как в точке #1) - мы пытаемся использовать его, пока мы все еще анализируем внутреннюю лямбду, прежде чем мы узнаем, что это за тип на самом деле. Это противоречит dcl.spec.auto/9.

Однако для f2 мы не можем пытаться инстанцировать с нетерпением, потому что это зависит. Мы можем создать экземпляр только в момент использования, и к этому моменту мы все знаем.

Чтобы действительно сделать что-то подобное, вам понадобится y-комбинатор. Реализация из бумаги:

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

А вы хотите:

auto it = y_combinator([&](auto self, auto b){
    std::cout << (a + b) << std::endl;
    return self;
});

TL; DR;

лязг правильный.

Похоже, что раздел стандарта, который делает это некорректным, - это [dcl.spec.auto] стр. 9:

If the name of an entity with an undeduced placeholder type appears in an expression, the program is ill-formed. Once a non-discarded return statement has been seen in a function, however, the return type deduced from that statement can be used in the rest of the function, including in other return statements. [ Example:

auto n = n; // error, n’s initializer refers to n
auto f();
void g() { &f; } // error, f’s return type is unknown

auto sum(int i) {
  if (i == 1)
    return i; // sum’s return type is int
  else
    return sum(i-1)+i; // OK, sum’s return type has been deduced
}

—end example ]

Оригинальная работа через

Если мы посмотрим на предложение Предложение добавить Y Combinator в стандартную библиотеку, оно дает рабочее решение:

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

и он явно говорит, что ваш пример невозможен:

C++11/14 lambdas do not encourage recursion: there is no way to reference the lambda object from the body of the lambda function.

и он ссылается на Обсуждение, в котором Ричард Смит намекает на ошибку, которую дает вам лязг:

I think this would be better as a first-class language feature. I ran out of time for the pre-Kona meeting, but I was intending on writing a paper to allow giving a lambda a name (scoped to its own body):

auto x = []fib(int a) { return a > 1 ? fib(a - 1) + fib(a - 2) : a; };

Here, 'fib' is the equivalent of the lambda's *this (with some annoying special rules to allow this to work despite the lambda's closure type being incomplete).

Барри указал мне на последующее предложение Рекурсивные лямбды, в котором объясняется, почему это невозможно, и обходится ограничение dcl.spec.auto#9, а также показаны методы достижения этого сегодня без него:

Lambdas are a useful tool for local code refactoring. However, we sometimes want to use the lambda from within itself, either to permit direct recursion or to allow the closure to be registered as a continuation. This is surprisingly difficult to accomplish well in current C++.

Example:

  void read(Socket sock, OutputBuffer buff) {
  sock.readsome([&] (Data data) {
  buff.append(data);
  sock.readsome(/*current lambda*/);
}).get();

}

One natural attempt to reference a lambda from itself is to store it in a variable and capture that variable by reference:

 auto on_read = [&] (Data data) {
  buff.append(data);
  sock.readsome(on_read);
};

However, this is not possible due to a semantic circularity: the type of the auto variable is not deduced until after the lambda-expression is processed, which means the lambda-expression cannot reference the variable.

Another natural approach is to use a std::function:

 std::function on_read = [&] (Data data) {
  buff.append(data);
  sock.readsome(on_read);
};

This approach compiles, but typically introduces an abstraction penalty: the std::function may incur a memory allocation and the invocation of the lambda will typically require an indirect call.

For a zero-overhead solution, there is often no better approach than defining a local class type explicitly.

Достаточно легко переписать код в терминах классов, которые компилятор будет или, скорее, должен генерировать для лямбда-выражений.

Когда это будет сделано, станет ясно, что основная проблема - это просто висящая ссылка и что компилятор, который не принимает код, сталкивается с некоторыми проблемами в области лямбда.

Переписывание показывает, что циклических зависимостей нет.

#include <iostream>

struct Outer
{
    int& a;

    // Actually a templated argument, but always called with `Outer`.
    template< class Arg >
    auto operator()( Arg& self ) const
        //-> Inner
    {
        return Inner( a, self );    //! Original code has dangling ref here.
    }

    struct Inner
    {
        int& a;
        Outer& self;

        // Actually a templated argument, but always called with `int`.
        template< class Arg >
        auto operator()( Arg b ) const
            //-> Inner
        {
            std::cout << (a + b) << std::endl;
            return self( self );
        }

        Inner( int& an_a, Outer& a_self ): a( an_a ), self( a_self ) {}
    };

    Outer( int& ref ): a( ref ) {}
};

int main() {

  int a = 5;

  auto&& it = Outer( a );
  it(it)(4)(6)(42)(77)(999);
}

Полностью шаблонная версия, отражающая способ, которым внутренняя лямбда в исходном коде захватывает элемент шаблонного типа:

#include <iostream>

struct Outer
{
    int& a;

    template< class > class Inner;

    // Actually a templated argument, but always called with `Outer`.
    template< class Arg >
    auto operator()( Arg& self ) const
        //-> Inner
    {
        return Inner<Arg>( a, self );    //! Original code has dangling ref here.
    }

    template< class Self >
    struct Inner
    {
        int& a;
        Self& self;

        // Actually a templated argument, but always called with `int`.
        template< class Arg >
        auto operator()( Arg b ) const
            //-> Inner
        {
            std::cout << (a + b) << std::endl;
            return self( self );
        }

        Inner( int& an_a, Self& a_self ): a( an_a ), self( a_self ) {}
    };

    Outer( int& ref ): a( ref ) {}
};

int main() {

  int a = 5;

  auto&& it = Outer( a );
  it(it)(4)(6)(42)(77)(999);
}

Я полагаю, что именно этот шаблон во внутреннем механизме, что формальные правила призваны запретить. Если они все же запретят исходную конструкцию.

Что ж, ваш код не работает. Но это действительно так:

template<class F>
struct ycombinator {
  F f;
  template<class...Args>
  auto operator()(Args&&...args){
    return f(f, std::forward<Args>(args)...);
  }
};
template<class F>
ycombinator(F) -> ycombinator<F>;

Код теста:

ycombinator bob = {[x=0](auto&& self)mutable{
  std::cout << ++x << "\n";
  ycombinator ret = {self};
  return ret;
}};

bob()()(); // prints 1 2 3

Ваш код имеет форму UB и имеет неверный формат, диагностика не требуется. Что забавно; но оба могут быть исправлены независимо.

Во-первых, УБ:

auto it = [&](auto self) { // outer
  return [&](auto b) { // inner
    std::cout << (a + b) << std::endl;
    return self(self);
  };
};
it(it)(4)(5)(6);

это UB, потому что внешний принимает self по значению, затем внутренний захватывает self по ссылке, а затем возвращает его после завершения работы outer. Так что segfaulting определенно нормально.

Исправление:

[&](auto self) {
  return [self,&a](auto b) {
    std::cout << (a + b) << std::endl;
    return self(self);
  };
};

Код остается некорректным. Чтобы увидеть это, мы можем расширить лямбды:

struct __outer_lambda__ {
  template<class T>
  auto operator()(T self) const {
    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      T self;
    };
    return __inner_lambda__{a, self};
  }
  int& a;
};
__outer_lambda__ it{a};
it(it);

это создает экземпляр __outer_lambda__::operator()<__outer_lambda__>:

  template<>
  auto __outer_lambda__::operator()(__outer_lambda__ self) const {
    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      __outer_lambda__ self;
    };
    return __inner_lambda__{a, self};
  }
  int& a;
};

Итак, теперь нам нужно определить тип возвращаемого значения __outer_lambda__::operator().

Мы проходим его строка за строкой. Сначала мы создаем тип __inner_lambda__:

    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      __outer_lambda__ self;
    };

Теперь посмотрите туда - его тип возврата - self(self) или __outer_lambda__(__outer_lambda__ const&). Но мы пытаемся определить возвращаемый тип __outer_lambda__::operator()(__outer_lambda__).

Тебе нельзя этого делать.

Хотя на самом деле тип возвращаемого значения __outer_lambda__::operator()(__outer_lambda__) на самом деле не зависит от типа возвращаемого значения __inner_lambda__::operator()(int), C++ не заботится о выводе типов возврата; он просто проверяет код построчно.

И self(self) используется до того, как мы его вывели. Плохо сформированная программа.

Мы можем исправить это, скрыв self(self) на потом:

template<class A, class B>
struct second_type_helper { using result=B; };

template<class A, class B>
using second_type = typename second_type_helper<A,B>::result;

int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto self) {
      return [self,&a](auto b) {
        std::cout << (a + b) << std::endl;
        return self(second_type<decltype(b), decltype(self)&>(self) );
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

и теперь код правильный и компилируется. Но я думаю, что это небольшая хитрость; просто используйте ycombinator.