Lambda回归:这是合法的吗？

Question

考虑这个相当无用的程序:

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

基本上我们正在尝试制作一个返回自己的lambda.

• MSVC编译程序,然后运行
• gcc编译程序,并且它是段错误的
• 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:问题不在于一般情况下lambda是否合法,而是关于这种特定方式的合法性.

相关问题:C++ lambda返回自身.

Answer 1

根据[dcl.spec.auto]/9,该程序格式错误(clang是对的):

如果表达式中出现具​​有未取消的占位符类型的实体的名称,则该程序格式错误.但是,一旦在函数中看到了非丢弃的return语句,从该语句推导出的返回类型可以在函数的其余部分中使用,包括在其他return语句中.

基本上,内部lambda的返回类型的推导取决于它自己(这里命名的实体是调用操作符) - 所以你必须显式提供一个返回类型.在这种特殊情况下,这是不可能的,因为你需要内部lambda的类型但不能命名它.但是还有其他情况试图强制这样的递归lambdas,这可以工作.

即使没有这个,你也有一个悬垂的参考.

让我解释多一些,与别人更聪明(即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)可以尝试急切地实例化它.你知道外部lambda的推导类型,一旦你达到上面的;点#2(它是内部lambda的类型),但我们试图比它更早使用它(想到它就像点#1) - 我们正在尝试在我们仍在解析内部lambda之前使用它,然后我们才知道它的类型实际上是什么.这与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;
});

Answer 2

编辑:根据C++规范,这种结构是否严格有效似乎存在争议.流行的观点似乎是无效的.请参阅其他答案以进行更全面的讨论.如果结构有效,则本答案的其余部分适用; 下面调整的代码适用于MSVC++和gcc,OP已经发布了与clang一起使用的进一步修改代码.

这是未定义的行为,因为内部lambda self通过引用捕获参数,但是在第7行self之后超出范围return.因此,当稍后执行返回的lambda时,它正在访问对超出范围的变量的引用.

#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.

相反,您可以通过引用而不是值来更改外部lambda以获取self,从而避免一堆不必要的副本并解决问题:

#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

Answer 3

TL; DR;

铿锵是对的.

看起来这个格式错误的部分是[dcl.spec.auto] p9:

如果表达式中出现具​​有未取消的占位符类型的实体的名称,则该程序格式错误.一旦未丢弃return语句已经在函数被视为,然而,从该语句推断返回类型,可以在功能上的其他地区,包括其他return语句.[例如:

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
}

- 末端的例子]

原创作品通过

如果我们查看提案A Proposal to Y 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不鼓励递归:没有办法从lambda函数的主体引用lambda对象.

并且它引用了一个讨论,其中理查德史密斯暗示铿锵声给你的错误:

我认为这将是一个更好的一流语言功能.我没有时间参加科纳会议前的会议,但是我打算写一篇论文,以便给一个lambda一个名字(作用于自己的身体):

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

在这里,'fib'相当于lambda的*this(尽管lambda的闭包类型不完整,但仍有一些令人讨厌的特殊规则允许它工作).

Barry向我提出了后续提议Recursive lambdas,它解释了为什么这是不可能的并且围绕dcl.spec.auto#9限制工作,并且还显示了在没有它的情况下实现这一目标的方法:

Lambdas是本地代码重构的有用工具.但是,我们有时希望在自身内部使用lambda,以允许直接递归或允许将闭包注册为延续.在当前的C++中,这很难很好地实现.

例:

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

}

从自身引用lambda的一种自然尝试是将其存储在变量中并通过引用捕获该变量:

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

但是,由于语义循环性,这是不可能的:直到处理lambda表达式之后才推导出auto变量的类型,这意味着lambda表达式不能引用变量.

另一种自然的方法是使用std :: function:

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

这种方法可以编译,但通常会引入抽象惩罚:std :: function可能会产生内存分配,而lambda的调用通常需要间接调用.

对于零开销解决方案,通常没有比明确定义本地类类型更好的方法.

Answer 4

看来clang是对的.考虑一个简化的例子:

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

让我们像编译器(一点点)一样经历它:

• 类型it是Lambda1模板调用运算符.
• it(it); 触发调用操作符的实例化
• 模板调用运算符的返回类型是auto,因此我们必须推导出它.
• 我们返回一个lambda捕获第一个类型的参数Lambda1.
• 该lambda也有一个调用操作符,它返回调用的类型 self(self)
• 注意:self(self)正是我们开始的!

因此,不能推断出类型.

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

代码仍然是不正确的.为了看到这个,我们可以扩展lambdas:

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.

Answer 6

根据编译器为lambda表达式生成或者更确切地说应该为lambda表达式生成的类来重写代码是很容易的.

当这样做时,很明显主要问题只是悬空引用,并且不接受代码的编译器在lambda部门中受到了一些挑战.

重写显示没有循环依赖.

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

一个完全模板化的版本,以反映原始代码中内部lambda的方式,捕获一个模板化类型的项:

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

我猜这是内部机制的模板,正式的规则被设计为禁止.如果他们确实禁止原始构造.