编译器能否在没有有关纯度的类型信息的情况下自动检测纯函数？

Question

所以我和我的 friend 争论，他声称像 GCC 这样的编译器可以在没有任何类型信息的情况下自动检测纯函数。我对此表示怀疑。

像 D 或 Haskell 这样的语言在它们的类型系统中具有纯粹性，程序员明确定义什么函数是纯粹的或不是。纯函数没有副作用，因此可以很容易地并行化。

所以问题是:这一切是否必要？编译器是否可以在没有任何元信息或类型信息的情况下，仅通过假设任何自动执行 IO 或自动访问全局变量的事物都不是纯粹的来检测纯度？

Answer 1

当然，在某些情况下您可以检测到纯函数。例如，

int f(int x)
{
    return x*2;
}

可以通过简单的静态分析检测为纯净。困难在于一般情况下这样做，检测使用“内部”状态但外部纯粹的接口(interface)基本上是不可能的。

GCC 确实有 warning options -Wsuggest-attribute=pure 和 -Wsuggest-attribute=const，建议可能是 pure 和 const 的候选函数 attributes .我不确定它是选择保守(即缺少许多纯函数，但从不建议使用非纯函数)还是让用户决定。

请注意 GCC 对 pure 的定义是“仅依赖于参数和全局变量”:

Many functions have no effects except the return value and their return value depends only on the parameters and/or global variables. Such a function can be subject to common subexpression elimination and loop optimization just as an arithmetic operator would be. These functions should be declared with the attribute pure.

— GCC manual

严格的纯度，即在所有情况下相同参数的相同结果，由 const 属性表示，但这样的函数甚至不能取消引用传递给它的指针。因此，pure 函数的并行化机会是有限的，但与您可以用 Haskell 等语言编写的纯函数相比，可以const 的函数要少得多。

顺便说一句，自动并行化纯函数并不像您想象的那么容易；困难的部分变成了决定要并行化的什么。太便宜的并行计算和开销使它毫无意义。并行化不够，您就得不到好处。由于这个原因，我不知道有任何实用的函数式语言实现会自动并行化，尽管像 repa 这样的库在用户代码中没有明确并行性的情况下在幕后并行执行许多操作。