自产生程序(Quine)

自产生程式（Quine），它以哲学家奎恩命名，指的是输出结果为程式自身源码的程式。

Quine 的想法最初出现在 Bratley, Paul and Jean Millo. “Computer Recreations; Self-Reproducing Automata”, Software — Practice & Experience, Vol. 2 (1972). pp. 397-400 中。Bratley 在看到已知的第一个这样的程序以后对 Quine 产生了兴趣。这个程序于二十世纪六十年代由爱丁堡大学的 Hamish Dewar 以 Atlas Autocode 语言写成。

作为真正的 Quine ，有一些约定：程序不能接受输入或者是打开文件，因为那样就可以直接输入源代码或者是把源代码文件直接打开再重新打印出来，就没有什么意思了；同时，一个完全空白的程序(产生完全空白的输出，即没有输出)也并不能称作 Quine。

C语言示例

例如上面这一段C语言程序，编译、运行后将会输出程序自身。

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

简要分析一下上面这段代码。代码之所以能达到这样的效果，核心在于printf(s,34,s,34)。我们知道，printf需要将一个常量字符串作为自己的格式化字符串，此处使用的正是s。而34是"的ASCII码值。因此，printf("%c", 34)表示输出一个引号。于是，这段代码运行的结果是程序自身。

下面是另一个更加简短的例子：

main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);}

这段运用了这一原理：函数调用时参数压栈的顺序为从右至左。因此，在printf中先对a进行赋值操作，然后再将a作为格式化字符串。

另一个使用宏来实现的例子：

#define q(k)main(){return!puts(#k"\nq("#k")");}
q(#define q(k)main(){return!puts(#k"\nq("#k")");})

实现原理

A=”储存<B>”
B=”对于输入<M>,而M作为一段程序码。
   一、计算出q(<M>)
   二、把计算结果和<M>结合起来
   三、打印出所求出的结果”

自产生程序的实际执行过程：

首先A先执行，会得到 。
B开始执行，然后被输入（即M=B）。
B利用 ,可以计算出 q()，并以此计算出 < A >。将 < A > 与 组合成一个新的程式的描述 < SELF > 。
输出< SELF >。

输出注释

有了上面的普适性的原理，不难构造一个能够输出注释的自产生程序。

//Copyright (c) He Tao
#include<stdio.h>
void main() {
    char *s="//Copyright (c) He Tao%c#include<stdio.h>%cvoid main() { %c%cchar *s=%c%s%c;%c%cprintf(s,10,10,10,9,34,s,34,10,9,10);%c}";
    printf(s,10,10,10,9,34,s,34,10,9,10);
}

输出到文件

接下来，再构造一个能够产生自身源文件的C程序。

//Copyright (c) He Tao
#include<stdio.h>
main(){
	FILE *fp=fopen("file.c","w");
	char *s="//Copyright (c) He Tao%c#include<stdio.h>%cmain(){ %c%cFILE *fp=fopen(%cfile.c%c,%cw%c);%c%cchar *s=%c%s%c;%c%cfprintf(fp,s,10,10,10,9,34,34,34,34,10,9,34,s,34,10,9,10,9,10,9,10);%c%cfclose(fp);%c%creturn 0;%c}";
	fprintf(fp,s,10,10,10,9,34,34,34,34,10,9,34,s,34,10,9,10,9,10,9,10);
	fclose(fp);
	return 0;
}

自产生程序的利用

由于自产生程序的独特性质，可以将其用来做一些很Hacker的事情。在Ken Thompson的大作Reflections on trusting trust中，他详细讲述了如何利用这个原理，在编译器中插入后门，使得所有的使用这个编译器编译的Unix系统都带着一个后门，并且从源码中看不出任何问题。

中科大的李博杰根据这一原理对LCC做了这样的Hack，并在LUG的活动中做了一次相关的演讲。

Python实现

x='y="x="+`x`+"\\n"\nprint(y+x)'
y="x="+'x'+"\n"
print(y+x)

s = 's = %r\nprint(s%%s)'
print(s%s)

Haskell实现

某种意义上讲，Quine程序的功能与Combinatory Logic中的$S$ Combinator有异曲同工之妙！上文提到了构造一个Quine程序的基本原理，起始就相当于程序加上程序对应的字符串，而程序的功能是将字符串输出两遍。而$S$ Combinator表达的含义是：$S \ f \ g \ x = ((x \ z) \ (y \ z))$。Haskell 中，$S$ Combinator相当于Monad的ap或者Applicative的<*>（类型((->) r)是Monad和Applicative的实例类型）。基于这一原理，不难构造出 Quine程序：

((++)<*>show)"((++)<*>show)"
(ap (++) show) "(ap (++) show) "

-- expand `ap` / <*>
(\x -> x ++ show x) "(\\x -> x ++ show x) "

参考

注: 所有代码均在gcc 4.8.1上通过测试。