static-analysis - 给定函数 f 的代码，如何静态确定 x 是否影响 f(x)？

Question

如果我有某个函数的代码f（为了简单起见，它接受一个输入），我需要确定输入是否x影响输出f(x)，即是否f是下面定义的常量函数。

如果wrt 的输出不变，则定义f为常量函数。这应该适用于所有输入。因此，例如，如果我们有，它可能会为除 x = 0 之外的所有输入输出 0，它可能会输出错误。所以不是一个常数函数。fxf(x) = 0 power xf

为了简单起见，我只能对代码进行静态分析并假设代码是 Java 源代码。这可能吗？

Answer 1

这几乎肯定是可能的。在大多数情况下。没有奇怪的事情发生的地方。

对于普通函数，是实际返回值而不是做自己的小事情的普通有用的类型，是的。

对于一个简单的函数，不是递归的，没有那种讨厌的，手动执行它，我可能会使静态分析等效于符号图，在那里我检查代码并确定可能是边界条件的 x 的每个值或类似的（例如，代码中有if (x < 0)某处，所以我检查函数的 x 值接近 0）。如果这种尝试注定要失败，请在我尝试将其用于某事之前告诉我。

除非您使用四倍精度 x 值或类似大小的东西，否则使用蛮力磨掉它可能会起作用，因为这样蛮力可能需要数年时间。尽管那时它不再是真正的静态分析。

静态分析通常实际上意味着让计算机通过查看代码来告诉您，而不是您自己查看（至少不是很多）。很多语言都有这样的算法，维基百科有这样的列表，包括一些免费甚至开源的。可以做某事的最终证明是它已经完成了。

Answer 2

这显然至少与解决停机问题（作为练习留下的证明）一样难，所以答案是“不”，这是不可能的。

Answer 3

由于您将非终止函数称为非常量，因此这是从您的问题到停止问题的简化：

void does_it_halt(...);

int f(int x) {
    if(x == 1) {
        does_it_halt();
    }
    return 0;
}

询问是否f为常数等同于询问是否does_it_halt停止。因此，您所要求的是不可能的，因为停止问题是无法确定的。