编译器能否自动检测纯函数，而不需要关于纯度的类型信息？

问题描述

所以我和我的朋友争辩说，像GCC这样的编译器可以在没有任何类型信息的情况下自动检测纯函数。我怀疑这一点。

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

所以问题是：这是否必要？编译器是否可以检测纯度，没有任何元数据或类型信息，只要假设任何执行IO或自动访问全局变量的东西都不是纯粹的？ 解决方案当然，你可以在某些情况下检测纯函数。例如，

  int f（int x）
 {
 return x * 2; 
} 
  

可以通过简单的静态分析检测为纯粹的。难度一般在这样做，检测使用内部状态但外部纯的接口基本上是不可能的。

GCC确实有 -Wsuggest-attribute = pure 和 -Wsuggest-attribute = const ，它提供了可能成为纯和 const 。我不确定它是否选择保守（即缺少许多纯函数，但从不建议用于非纯函数）或让用户决定。

请注意，GCC对 pure 的定义是仅取决于参数和全局变量：

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

顺便说一下，自动并行纯函数并不像想象的那么容易。最难的部分就是决定要并行运行什么。并行计算太便宜了，而开销却使得它毫无意义。不够平行，并且你没有收获好处。由于这个原因，我不知道有什么实际的功能语言实现可以自动并行化，但是像这样的库并行化在用户代码中没有显式并行性的背后幕后的许多操作。

So I'm arguing with my friend who claims that a compiler like GCC can detect a pure function automatically without any type information. I doubt that.

Languages like D or Haskell have purity in their type systems and a programmer explicitly defines what function is pure or not. A pure function has no side effects and can therefore very easily be parallelized.

So the question is: Is this all necessary or not? Could a compiler detect purity, without any meta or type information, just by assuming that anything that does IO or accesses global variables automatically is not pure?

解决方案

Sure, you can detect pure functions in some cases. For instance,

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

can be detected as pure with simple static analysis. The difficulty is doing this in general, and detecting interfaces which use "internal" state but are externally pure is basically impossible.

GCC does have the warning options -Wsuggest-attribute=pure and -Wsuggest-attribute=const, which suggest functions that might be candidates for the pure and const attributes. I'm not sure whether it opts to be conservative (i.e. missing many pure functions, but never suggesting it for a non-pure function) or lets the user decide.

Note that GCC's definition of pure is "depending only on arguments and global variables":

Strict purity, i.e. the same results for the same arguments in all circumstances, is represented by the const attribute, but such a function cannot even dereference a pointer passed to it. So the parallelisation opportunities for pure functions are limited, but much fewer functions can be const compared to the pure functions you can write in a language like Haskell.

By the way, automatically parallelising pure functions is not as easy as you might think; the hard part becomes deciding what to parallelise. Parallelise computations that are too cheap, and overhead makes it pointless. Don't parallelise enough, and you don't reap the benefits. I don't know of any practical functional language implementation that does automatic parallelisation for this reason, although libraries like repa parallelise many operations behind the scenes without explicit parallelism in the user code.

这篇关于编译器能否自动检测纯函数，而不需要关于纯度的类型信息？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！