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

Chr*_*ler 38 c compiler-construction gcc haskell d

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

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

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

ehi*_*ird 34

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

int f(int x)
{
    return x*2;
}
Run Code Online (Sandbox Code Playgroud)

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

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

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

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

- GCC手册

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

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

  • @NiklasBaumstark:C具有"as-if"规则,只要合规程序无法区分结果,它就允许实现执行任何想要的操作.并行化纯函数的执行将属于这个范畴. (11认同)
  • 一个明智的编译器,当猜测函数的"纯度"(为了优化)时,将允许错误否定(可能错过优化的机会),但不会误报(否则将执行错误的优化). (5认同)

Ing*_*ngo 12

还有另一个问题.考虑

int isthispure(int i) {
   if (false) return getchar();
   return i + 42;
}
Run Code Online (Sandbox Code Playgroud)

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

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

  • +1,但实际上编译器只需要检查从"INT_MIN"到"INT_MAX"的整数不是Lycrel数,这比证明不存在更容易.一个好的静态分析器当然可以对参数空间小于某些绑定的"M"(例如,"M = 1 << 32"左右)的函数应用强制方法. (3认同)
  • @R.我打赌你不能在合理的时间里只做10个整数(比如从190到200).有Lycrel候选人(当时是192或196,dunno),你的个人电脑可能会忙一年左右,但仍然不会证明它不是. (3认同)