编译器专家再谈C程序与费马大定理终止性问题
来源标题:Compilers and Termination Revisited
编译器研究者重新解释此前引发争议的C程序案例:该程序穷举搜索费马大定理反例,理论上应永不终止。作者承认前文解释不足导致误解,本文给出更完整分析,说明常见C编译器对该程序的优化行为及其语义含义。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
我之前那篇《C 编译器证伪费马大定理》的文章在博客和 Reddit 上都引发了不少讨论。遗憾的是,讨论中充斥着误解。部分原因是这个话题本身就比较微妙,但另一部分责任在我:那篇文章本意是写得轻松些,但我完全没把底层问题解释清楚。本文给出一个更完整的图景。
我们的目标是确定下面这个 C 程序的语义:
#include <stdio.h>
int fermat (void) {
const int MAX = 1000;
int a=1,b=1,c=1;
while (1) {
if (((a*a*a) == ((b*b*b)+(c*c*c)))) return 1;
a++;
if (a>MAX) {
a=1;
b++;
if (b>MAX) {
b=1;
c++;
if (c>MAX) {
c=1;
return 0;
}
}
}
}
return 0;
}
int main (void) {
if (fermat()) {
printf ("Fermat's Last Theorem has been disproved.\n");
} else {
printf ("Fermat's Last Theorem has not been disproved.\n");
}
return 0;
}
这个程序就是一个简单的反例搜索;如果它能证伪费马大定理的某个特例,程序就会终止。由于人们普遍相信该定理成立,我们预期这个反例搜索会永远运行下去。然而,市面上常见的 C 编译器却会生成会终止的代码:
regehr@john-home:~$ icc fermat2.c -o fermat2
regehr@john-home:~$ ./fermat2
Fermat's Last Theorem has been disproved.
regehr@john-home:~$ suncc -O fermat2.c -o fermat2
"fermat2.c", line 20: warning: statement not reached
regehr@john-home:~$ ./fermat2
Fermat's Last Theorem has been disproved.
在继续之前,先澄清几点。第一,我要问的并不是这个问题:
我怎样才能修改这段代码,让编译器尊重它的终止特性?
这很容易,有几种可靠的办法,比如使用 volatile 变量或内联汇编。
第二,我对下面这种“答案”不感兴趣:
这里发生的事情显而易见:编译器看到函数中有一条路径是死路,于是推断唯一剩下的路径必然是活的。
这个观察并非不对,但它有点像在解释“二战之所以发生,是因为人们没法好好相处”。它完全没有触及问题的核心。
第三,只要代码是为 int 至少 32 位的平台编译的,这里就不存在整数溢出的把戏。看一眼程序就能明白这一点。这些终止问题与整数溢出毫无关系。
程序的意义由它所书写的语言的语义决定。语义告诉我们如何解释语言中的构造(整数有多宽?if 运算符如何工作?),以及如何把各运算的结果组合成一个整体结果。有些计算机语言有形式化的数学语义,有些有标准文档,还有些只有参考实现。
我们来看几个例子。继续使用 C,并且会讲得相当不正式(关于 C 程序语义的形式化论述,参见 Michael Norrish 的博士论文)。为简单起见,我们只看不接受任何输入的“自包含”程序。考虑这个程序:
int main (void) {
return 3;
}
它的含义是 {{3,""}}。这个记号稍显杂乱,但可以读作“该程序有唯一的解释:返回 3,且不产生副作用”。为简单起见,我把副作用表示为打印到 stdout 的字符串。当然,一般情况下还存在其他类型的副作用。
int main (void) {
int a = 1;
return 2 + a;
}
它同样意味着 {{3,""}},因为不存在整数溢出的可能。
并非所有程序都有唯一的含义。考虑:
int main (void) {
unsigned short a = 65535;
return a + 1;
}
这个程序的含义是 {{65536,""}, {0,""}}。换句话说,它有两种含义:它可能返回 65536,也可能返回 0(两种情况都不产生副作用操作),取决于所用的具体 C 实现是把 unsigned short 的大小定义为 16 位,还是大于 16 位。
C 程序获得多重含义的另一种方式,是执行具有未指定行为的操作。与实现定义行为不同——后者要求实现必须记录其行为选择并一致地使用——未指定行为甚至可能在单个程序的执行过程中发生变化。例如:
int a;
int assign_a (int val) {
a = val;
return val;
}
int main (void) {
assign_a (0) + assign_a (1);
return a;
}
由于 C 中子表达式的求值顺序是未指定的,这个程序意味着 {{0,""}, {1,""}}。也就是说,它可能返回 0,也可能返回 1。
#include <stdio.h>
int main (void) {
return printf ("hi\n");
}
它的含义是 {{0,""}, {1,"h"}, {2,"hi"}, {3,"hi\n"}, {-1,""}, {-2,""}, {-3,""}, …}。这个集合中的第 4 个元素,返回值为 3,是我们预期看到的结果。第 1 到第 3 个元素对应 I/O 子系统截断了字符串的情况。第 5 个及其后的元素对应 printf() 调用失败的情况;标准规定此时返回一个负值,但没说具体是哪一个。到这里,我们就开始明白为什么对真实的 C 程序进行推理并不容易了。在后续例子中,我们会忽略 printf() 产生非预期结果的那些程序行为。
有些程序,比如下面这个,没有任何含义:
#include <limits.h>
int main (void) {
return INT_MAX+1;
}
在 C 中,对有符号整数溢出属于未定义行为,而执行这种操作的程序完全没有任何含义。它是病态的。我们把该程序的含义记为 {{UNDEF}}。
重要的是要认识到,执行未定义操作对程序语义有着无界的后果。例如,这个程序:
#include <limits.h>
int main (void) {
INT_MAX+1;
return 0;
}
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。