为什么这个使用代码的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 的 return 类型明确声明为 -> 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'

为什么编译器无法找出 return 类型并推导出 auto？我首先想到，也许我需要将 ... ? 1 : n * self(n - 1) 更改为 ... ? int64_t(1) : n * self(n - 1)，以便两个 return 值的类型最终都为 int64_t，并且不会留下任何可能的歧义。但这似乎并非如此。我错过了什么？

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

Answer 1

类型推导

n == 1 ? (int64_t)1 : n * self(n - 1)的类型取决于self的return类型，因此无法推导出。你会认为 int64_t 是一个明显的候选者，但 float 和 double 也同样好。您不能期望编译器考虑所有可能的 return 类型并选择最佳候选者。

要解决此问题而不是使用三元表达式，请使用 if-else 块：

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

其中一个 return 语句不依赖于 self 的 return 类型，因此可以进行类型推导。

当推导函数的 return 类型时，编译器会依次和函数体中的所有 return 语句试图推断出它们的类型。如果失败，则会出现编译错误。

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

当使用一个 if 语句和多个 return 语句时，编译器可以从它遇到的第一个语句中推断出 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);
        }

可以推导出return一个int64_t。

作为旁注

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

将无法编译，因为从第一个 return 语句中，函数的 return 类型将被推导出为 int，而从第二个 return 语句中推导出为int64_t.

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

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

第二个问题

错误的发生是因为在调用 lambda 时，由于 lambda 的 auto self 参数，您正试图复制 *this。这是因为有一个右值引用成员。（请参阅 godbolt 上 clang 的重要错误消息）

要解决此问题，请使用原始问题中提到的 std::ref 或使 lambda 具有 auto &&self 参数（并使用 std::forward<decltype(self)>(self)）。

另请注意，成员 Lambda &&lambda 是右值引用，因此您只能使用临时或移动的 lambda 构造 y_combinator 的实例。一般来说，复制仿函数没什么大不了的，标准库也通过复制来获取仿函数参数。

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

Why does this Y Combinator using code fail to compile?

c++

lambda

y-combinator

类型推导

第二个问题