24

我阅读了 Ken Thompson 的经典论文Reflections on Trusting Trust，他在其中提示用户写一个Quine作为他的论点的介绍（强烈推荐阅读）。

quine 是一种计算机程序，它不接受任何输入并生成其自己的源代码的副本作为其唯一输出。

天真的做法只是想说：

print "[insert this program's source here]"

但是很快就会发现这是不可能的。我最终使用 Python自己编写了一个，但仍然无法解释“诀窍”。我正在寻找一个很好的解释为什么 Quines 是可能的。

4

2 回答 2

14

正常的技巧是使用printf格式字符串表示程序的结构，并为字符串本身使用占位符以获得所需的递归：

来自http://www.nyx.net/~gthompso/quine.htm的标准 C 示例很好地说明了这一点：

char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);}

编辑：写完这篇文章后，我做了一些搜索： http: //www.madore.org/~david/computers/quine.html给出了一个非常好的、更理论的描述 quines 到底是什么以及它们为什么起作用。

于 2012-01-15T20:56:43.643 回答
3

这是我写的一个使用putchar而不是printf; 因此它必须处理所有自己的转义码。但它在所有 C 执行字符集上都是 %100 可移植的。

您应该能够看到文本表示中有一个接缝，它反映了程序文本本身中的一个接缝，它从开始工作变为结束工作。编写 Quine 的诀窍是克服这个“驼峰”，在那里你转而挖掘自己的出路！您的选项受到文本表示和语言输出设施的限制。

#include <stdio.h>

void with(char *s) {
    for (; *s; s++) switch (*s) {
    case '\n': putchar('\\'); putchar('n'); break;
    case '\\': putchar('\\'); putchar('\\'); break;
    case '\"': putchar('\\'); putchar('\"'); break;
    default: putchar(*s);
    }
}
void out(char *s) { for (; *s; s++) putchar(*s); }
int main() {
    char *a[] = {
"#include <stdio.h>\n\n",
"void with(char *s) {\n",
"    for (; *s; s++) switch (*s) {\n",
"   case '\\",
"n': putchar('\\\\'); putchar('n'); break;\n",
"   case '\\\\': putchar('\\\\'); putchar('\\\\'); break;\n",
"   case '\\\"': putchar('\\\\'); putchar('\\\"'); break;\n",
"   default: putchar(*s);\n",
"    }\n}\n",
"void out(char *s) { for (; *s; s++) putchar(*s); }\n",
"int main() {\n",
"    char *a[] = {\n",
NULL }, *b[] = {
"NULL }, **p;\n",
"    for (p = a; *p; p++) out(*p);\n",
"    for (p = a; *p; p++) {\n",
"   putchar('\\\"');\n",
"   with(*p);\n",
"   putchar('\\\"'); putchar(','); putchar('\\",
"n');\n",
"    }\n",
"    out(\"NULL }, *b[] = {\\",
"n\");\n",
"    for (p = b; *p; p++) {\n",
"   putchar('\\\"');\n",
"   with(*p);\n",
"   putchar('\\\"'); putchar(','); putchar('\\",
"n');\n",
"    }\n",
"    for (p = b; *p; p++) out(*p);\n",
"    return 0;\n",
"}\n",
NULL }, **p;
    for (p = a; *p; p++) out(*p);
    for (p = a; *p; p++) {
    putchar('\"');
    with(*p);
    putchar('\"'); putchar(','); putchar('\n');
    }
    out("NULL }, *b[] = {\n");
    for (p = b; *p; p++) {
    putchar('\"');
    with(*p);
    putchar('\"'); putchar(','); putchar('\n');
    }
    for (p = b; *p; p++) out(*p);
    return 0;
}

一个常见的技巧是通过编写一个程序来读取文本文件并输出一个数字数组来启动quine。然后修改它以使用静态数组，并针对新的（静态数组）程序运行第一个程序，生成一个代表该程序的数字数组。将它插入到静态数组中，再次运行它直到它稳定下来，你就会得到一个 quine。但是，它与特定的字符集相关联（== 不是 100% 可移植的）。像上面这样的程序（而不是经典的printf hack）在 ASCII 或 EBCDIC 上的工作方式相同（经典的printf hack 在 EBCDIC 中失败，因为它包含硬编码的 ASCII）。

编辑：

仔细（最终）再次阅读这个问题，看来您实际上是在寻找更多的哲学而不是技术。让你摆脱无限倒退的诀窍是two-fer。您必须从相同的数据中获取编码程序和扩展程序：使用相同的数据两种方式。因此，该数据仅描述了围绕其未来表现形式的程序部分，即框架。此框架内的图像是原件的直接副本。

这就是你自然会手工制作递归绘图的方式：tv of a tv of tv。在某些时候你累了，只是在屏幕上勾勒出一些眩光，因为递归已经充分建立。

编辑：

我正在寻找一个很好的解释为什么 Quines 是可能的。

奎因的“可能性”深入到 19 世纪和 20 世纪的数学革命的深处。WVO Quine 的“经典”quine 是单词序列 (IIRC)

附加到自身时产生 false

这是一个悖论，类似于大卫要求“让我在悲伤时快乐，在快乐时让我悲伤”的要求，两边刻着的奖章回答说：“这也会过去”。

现代数理逻辑的先驱，如弗雷格、罗素和怀特黑德、Łukasiewicz，当然还有我们的孩子图灵、丘奇和图伊，也研究了同样的结。将Quine从文字游戏领域转换为程序演示（解开悖论部分）的技巧是哥德尔将算术运算本身编码为数字的方法，因此可以将整个数学表达式编码为一个（巨大的）整数。特别地，执行该表示的解码的数学函数可以以相同的（数字）形式表示。这个数字（哥德尔编码的函数）既是代码又是数据。

这个权力三重奏（代码、表示、数据）可以转换为不同的表示。通过选择不同的表示形式（或类似的链：字节-> ASCII-> 十六进制-> 整数），改变了代码的行为，从而改变了数据的外观。

于 2012-10-18T16:36:47.383 回答