Лямбда возвращается: это законно? - программирование
Подтвердить что ты не робот

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

Рассмотрите эту довольно бесполезную программу:

#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);
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

В основном мы пытаемся сделать лямбду, которая возвращается сама.

  • MSVC компилирует программу, и она запускается
  • gcc компилирует программу, и она segfaults
  • clang отклоняет программу сообщением:

    error: function 'operator()<(lambda at lam.cpp:6:13)>' with deduced return type cannot be used before it is defined

Какой компилятор прав? Существует ли ограничение статического ограничения, UB или нет?

Обновление этой незначительной модификации принято clang:

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

Обновление 2: я понимаю, как написать функтор, который возвращает себя или как использовать комбинатор Y, для достижения этого. Это вопрос языка-юриста.

Обновление 3: вопрос заключается не в том, является ли законным для лямбда возвращение вообще, а в отношении законности этого конкретного способа сделать это.

Связанный с этим вопрос: C++ lambda возвращается сам.

4b9b3361

ОТВЕТЫ

Ответ 1

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

Если в выражении появляется имя объекта с неопределенным типом-заполнителем, программа плохо сформирована. Однако, если в функции не был отброшен оператор возврата без возврата, возвращаемый тип, выведенный из этого оператора, может использоваться в остальной части функции, в том числе в других операторах return.

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

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

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

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;
});

Ответ 2

Редактирование: Кажется, есть некоторые разногласия относительно того, является ли эта конструкция строго достоверной по спецификации C++. Преобладающее мнение кажется, что оно неверно. См. Другие ответы для более подробного обсуждения. Остальная часть этого ответа применяется, если конструкция действительна; приведенный ниже код работает с MSV C++ и 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 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

Ответ 3

TL; DR;

clang является правильным.

Похоже, что раздел стандарта, который делает это плохо сформированным, [dcl.spec.auto] p9:

Если в выражении появляется имя объекта с неопределенным типом-заполнителем, программа плохо сформирована. Однако, если в функции не был отброшен оператор возврата без возврата, возвращаемый тип, выведенный из этого оператора, может использоваться в остальной части функции, в том числе в других операторах return. [ Пример:

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

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

-End пример]

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

Если мы рассмотрим предложение A "Добавить 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 не поощряют рекурсию: нет способа ссылаться на лямбда-объект из тела лямбда-функции.

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

Я думаю, что это будет лучше, как первоклассная языковая функция. У меня не хватило времени на встречу в пре-Коне, но я намеревался написать бумагу, чтобы дать имя лямбда (ограниченное собственным телом):

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

Здесь "fib" является эквивалентом лямбда * этого (с некоторыми раздражающими специальными правилами, позволяющими этому работать, несмотря на то, что тип закрытия лямбда является неполным).

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

Lambdas - полезный инструмент для рефакторинга локального кода. Однако мы иногда хотим использовать лямбду внутри себя, либо для прямой рекурсии, либо для того, чтобы позволить закрытию регистрироваться как продолжение. В настоящее время C++ на удивление трудно добиться успеха.

Пример:

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

}

Одна естественная попытка ссылаться на лямбду от себя - это хранить ее в переменной и захватывать эту переменную по ссылке:

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

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

Другим естественным подходом является использование функции std:

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

Этот подход компилируется, но обычно вводит штраф абстракции: функция std :: может нести распределение памяти, а вызов лямбды обычно требует косвенного вызова.

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

Ответ 4

Похоже, что кланг прав. Рассмотрим упрощенный пример:

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

Пропустите через него как компилятор (немного):

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

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

Ответ 5

Ну, ваш код не работает. Но это делает:

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 и плохо сформирован. Диагностика не требуется. Что смешно; но оба могут быть установлены независимо.

Во-первых, 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) используется до того, как мы его вывели. Ill сформировал программу.

Мы можем исправить это, спрятав 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.

Ответ 6

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

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

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

#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);
}

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