为什么这个使用代码的Y组合器无法编译？

Question

我已经读了三天关于组合子的文章了，我终于开始用代码编写它们(更像是从地方复制东西和理解事物)。

下面是我试图运行的一些代码：

#include <iostream>
#include <utility>

template <typename Lambda>
class y_combinator {
  private:
    Lambda lambda;
  public:
    template <typename T>
    constexpr explicit y_combinator (T&& lambda)
        : lambda (std::forward <T> (lambda))
    { }

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

template <typename Lambda>
decltype(auto) y_combine (Lambda&& lambda) {
    return y_combinator <std::decay_t <Lambda>> (std::forward <Lambda> (lambda));
}

int main () {
    auto factorial = y_combine([&] (auto self, int64_t n) {
        return n == 1 ? (int64_t)1 : n * self(n - 1);
    });
    
    int n;
    std::cin >> n;

    std::cout << factorial(n) << '\n';
}

如果我显式地将lambda的返回类型声明为-> int64_t，那么一切都运行良好。但是，当我删除它时，编译器会发出抱怨。错误：

main.cpp|16|error: use of 'main()::<lambda(auto:11, int64_t)> [with auto:11 = y_combinator<main()::<lambda(auto:11, int64_t)> >; int64_t = long long int]' before deduction of 'auto'

为什么编译器不能找出返回类型并推断自动？我首先认为，我可能需要将... ? 1 : n * self(n - 1)更改为... ? int64_t(1) : n * self(n - 1)，以便这两个返回值的类型最终成为int64_t，而不存在任何可能的歧义。但情况似乎并非如此。我遗漏了什么？

而且，在y_combinator类中，将lambda声明为Lambda&&类型的对象似乎会导致问题。为什么是这种情况？只有当我在operator ()重载中将强制转换写为(decltype(*this)&)而不是std::ref(*this)时，才会发生这种情况。他们在做不同的事情吗？

Answer 1

类型演绎

n == 1 ? (int64_t)1 : n * self(n - 1)的类型取决于self的返回类型，因此无法推断。您可能会认为int64_t是一个明显的候选，但是float和double也同样优秀。您不能期望编译器考虑每一种可能的返回类型，并选择最佳的候选。

若要修复此问题，而不是使用三元表达式，请使用if- fix块：

int main () {
    auto factorial = y_combine([&] (auto self, int64_t n) {
        if (n == 1) {
            return (int64_t)1;
        } else {
            return n * self(n - 1);
        }
    });
    // ...
}

对于这个返回语句，它不依赖于self的返回类型，因此可以进行类型推断。

在推导函数的返回类型时，编译器将依次查看函数正文中的所有返回语句，并试图推断它们的类型。如果失败，您将得到一个编译错误。

使用三元操作符，返回语句return n == 1 ? (int64_t)1 : n * self(n - 1);的类型取决于self的返回类型，该类型目前尚不清楚。因此，您将得到一个编译错误。

当使用if语句和多个返回语句时，编译器可以从遇到的第一个返回类型中推断返回类型，因为

如果有多个返回语句，它们都必须推断为相同的类型。

和

在函数中看到返回语句之后，从该语句导出的返回类型可以用于函数的其余部分，包括在其他返回语句中。

就像在优先选择上看到的。这就是为什么

        if (n == 1) {
            return (int64_t)1;
        } else {
            return n * self(n - 1);
        }

可以推导出返回int64_t。

作为旁注

        if (n == 1) {
            return 1; // no explicit cast to int64_t
        } else {
            return n * self(n - 1);
        }

无法编译，因为从第一个返回语句中，函数的返回类型将被推断为int，而第二个返回语句将被推断为int64_t。

        if (n != 1) {
            return n * self(n - 1);
        } else {
            return (int64_t)1;
        }

也会失败，因为它的第一个返回语句取决于函数的返回类型，因此无法推导。

第二个问题

发生此错误是因为在调用lambda时，由于lambda的auto self参数，您试图复制*this。这是因为有一个rvalue引用成员。(参见clang在哥德波特上的重大错误消息)

要解决这个问题，可以在原始问题中使用std::ref，或者使lambda具有一个auto &&self参数(并使用std::forward<decltype(self)>(self))。

还请注意，成员Lambda &&lambda是一个rvalue引用，因此只能使用临时的或移动的lambda构造y_combinator的实例。一般情况下，复制函子并不是什么大不了的事，标准库也是通过拷贝获取函子参数的。