编译器是否可以自动检测纯函数而无需关于纯度的类型信息？

Question

所以我和我的朋友争论说,像GCC这样的编译器可以在没有任何类型信息的情况下自动检测纯函数.我不信.

像D或Haskell这样的语言在其类型系统中具有纯度,程序员明确定义了哪些函数是纯粹的还是纯粹的.纯函数没有副作用,因此可以非常容易地并行化.

所以问题是:这一切都是必要的吗？编译器可以检测纯度,而不需要任何元或类型信息,只需假设任何执行IO或自动访问全局变量的东西都不纯粹吗？

Answer 1

当然,在某些情况下,您可以检测纯函数.例如,

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

通过简单的静态分析可以检测到纯度.困难在于一般地这样做,并且检测使用"内部"状态但外部纯粹的接口基本上是不可能的.

GCC确实有警告选项 -Wsuggest-attribute=pure和-Wsuggest-attribute=const,这表明,可能是考生的功能pure和const 属性.我不确定它是否选择保守(即缺少许多纯函数,但从不建议它用于非纯函数)或让用户决定.

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

除返回值外,许多函数都没有效果,它们的返回值仅取决于参数和/或全局变量.这样的函数可以像算术运算符那样经受公共子表达式消除和循环优化.应使用属性声明这些函数pure.

- GCC手册

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

顺便说一句,自动并行化纯函数并不像你想象的那么容易; 困难的部分变得决定什么是并行.并行化计算太便宜,而且开销使它毫无意义.不要足够平行,你没有收获的好处.我不知道任何实际的函数式语言实现是出于这个原因进行自动并行化的,尽管像rep这样的库在后台并行化许多操作而没有用户代码中的显式并行性.

Answer 2

还有另一个问题.考虑

int isthispure(int i) {
   if (false) return getchar();
   return i + 42;
}

该函数实际上是纯粹的,虽然它包含不纯的代码,但是无法访问此代码.现在假设false被替换为g(i)但我们非常确定g(i)是假的(例如,g可能检查其参数是否是Lychrel数).为了证明这是纯粹的,编译器必须证明不存在Lychrel数.

(我承认这是一个非常理论上的考虑.人们还可以决定,如果一个函数包含任何不纯的代码,它本身就是不纯的.但是这种情况并不适用于C类型系统,恕我直言.)