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

基本上，我们正在尝试制造一个自我返回的 λ。

  • 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 返回自身。

10390 次浏览
小开

编辑 : < em > 对于这个构造是否在 C + + 规范中严格有效，似乎存在一些争议。普遍的意见似乎认为它是无效的。请参阅其他答案，以便进行更详细的讨论。这个答案的其余部分应用了 如果，结构是有效的; 下面的修改过的代码适用于 MSVC + + 和 gcc，OP 发布了进一步修改过的代码，也适用于 clang。

这是有未定义行为的，因为内部 lambda 通过引用捕获参数 self，但是 self在第7行的 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，以自我参考而不是价值，从而避免了一堆不必要的副本，也解决了问题:

#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
小开

看起来“ clang”是正确的，考虑一个简单的例子:

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

让我们像编译器一样(稍微)浏览一下:

  • it的类型是带有模板调用操作符的 Lambda1。
  • it(it);触发调用操作员的实例化
  • 模板调用操作符的返回类型是 auto，因此我们必须推断它。
  • 我们返回一个捕获 Lambda1类型的第一个参数的 lambda。
  • 那个 lambda 也有一个调用操作符，它返回调用 self(self)的类型
  • 注意: self(self)正是我们开始时使用的！

因此，无法推断类型。

小开
最佳答案

每个 [ dcl.spec.auto ]/9程序格式不正确(当当声是正确的) :

如果表达式中出现具有未推导的占位符类型的实体的名称，则该程序格式不正确。然而，一旦在函数中看到非丢弃的返回语句，从该语句推导出的返回类型就可以用于函数的其余部分，包括其他返回语句。

基本上，对内部 lambda 的返回类型的推断取决于它本身(这里命名的实体是调用操作符)-因此您必须显式地提供返回类型。在这种特殊情况下，这是不可能的，因为您需要内部 lambda 的类型，但不能命名它。但在其他情况下，尝试像这样强制递归 lambdas，这是可行的。

即使没有这个，你也有 悬而未决的参考文献。

在与更聪明的人(例如 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。当表达式是非依赖的时候，它们可以被... ... 热切地使用(例如 [ tem.res ]/8，无论它发现自己所在的模板是否被实例化，static_assert(false)都是一个严重的错误)。

对于 f1，编译器(比如 clang)可以尝试急切地实例化它。一旦你到达上面 #2点的外 lambda (它是内 lambda 的类型) ，你就会知道外 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;
});
小开

;

“叮当”是正确的。

看起来标准中造成这种畸形的部分是 [ dcl.spec.auto ] p9:

如果表达式中出现具有未推导的占位符类型的实体的名称，则程序为 格式不正确。 一旦在函数中看到非丢弃的返回语句，那么返回类型 可以在函数的其余部分中使用，包括在其他 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
}

ー最后一个例子]

原创作品通过

如果我们看看 在标准库中添加 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));
}

它明确表示，你的例子是不可能的:

C + + 11/14 lambda 不鼓励递归: 没有办法从 lambda 函数体引用 lambda 对象。

它引用了 理查德 · 史密斯在其中暗示了当声给你带来的错误:

我认为这将更好地作为一流的语言功能。我没有时间参加科纳会议前的会议，但我打算写一篇论文，允许给一个 lambda 命名(以它自己的身体为范围) :

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

在这里，‘ fib’等价于 lambda 的 * this (尽管 lambda 的闭包类型不完整，但是有一些烦人的特殊规则允许它工作)。

Barry 向我指出了后续的建议 递归 lambdas，它解释了为什么这是不可能的，并围绕着 dcl.spec.auto#9的限制展开工作，同时也展示了今天在没有 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 表达式之后才能推断出来，这意味着 lambda 表达式不能引用该变量。

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

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

这种方法进行编译，但是通常会引入抽象代价: std: : 函数可能会引起内存分配，而 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);
}

我猜这就是内部机制的模板，正式的规则就是为了禁止这种模板。如果他们真的禁止了最初的构造。

小开

你的代码不管用，但这个可以:

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，因为 out 通过值获取 self，然后 inner 通过引用获取 self，然后在 outer完成运行后返回它。所以分隔绝对没问题。

解决办法:

[&](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);
}

现在代码是正确的，并编译。但是我觉得这有点黑客的味道，只要用一下 y 组合器就行了。


提交答案