c++ - 为什么这个使用代码的 Y Combinator 编译失败？

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'

为什么编译器无法确定返回类型并推断出 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-else block :

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 语句和多个 return 语句时，编译器可以从它遇到的第一个推断返回类型，因为

If there are multiple return statements, they must all deduce to the same type.

和

Once a return statement has been seen in a function, the return type deduced from that statement can be used in the rest of the function, including in other return statements.

见 cppreference .这就是为什么

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

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

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

也会失败，因为它遇到的第一个 return 语句取决于函数的返回类型，因此无法推断。
第二个问题
发生错误是因为在调用 lambda 时您正在尝试复制 *this因为 lambda 的 auto self范围。这是由于有一个右值引用成员。 (参见 godbolt 上 clang 的重大错误消息)
要解决此问题，请使用 std::ref如原始问题中所述或使 lambda 具有 auto &&self参数(并使用 std::forward<decltype(self)>(self) )。
另请注意，成员 Lambda &&lambda是一个右值引用，所以你只能构造一个 y_combinator 的实例使用临时或移动的 lambda。通常复制仿函数没什么大不了的，标准库也通过复制获取仿函数参数。