今天上‘高等数理逻辑’课程时听说了 Quine程序 ,一种很有意思的程序——自产生程序。 参考资料

Quine,是以哲学家奎恩命名,指的是输出结果为程序自身源码的程序。严格意义上的Quine有以下约定:

  1. 程序不能接受输入或者打开文件。
  2. 一个完全空白的程序不称为Quine。(虽然其自身输出就是空白)

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),重点在于设计一个符合输出要求的格式化字符串。但以上程序的不足:

  1. 忽略了依赖头的文件 #include
  2. 双引号的值是34,与ASCII中的码值一样

后来James Hu 发布的改进版

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

以上程序巧妙的运用了宏定义,宏展开的结果为:

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

原理

维基百科上有对Quine原理的描述:

我们先定义一个函数q,对于一个字串wa,q(wa)经过编程语言的解释会变成wb。

对于一个程式P而言,以下会使用<P> 来表示程式P的描述(即程式码)。

建立一个程式SELF,SELF由A、B所组成。换言之<SELF>=<A><B> 。且会先执行A再执行B。
 A=“储存<B>”
 B=“对于输入<M> ,而M为一段程式码。”
   1. 计算出q(<M>)
   2. 把计算结果和<M>结合起来
   3. 印出所出求出描述

而自生实际执行的过程为:
 1. 首先A先执行,会得到<B>。
 2. B开始执行,然后被输入<B>(即M=B)。
 3. B利用<B>,可以计算出q(<B>),并以此计算出<A>。将<A>与<B>组合成一个新的程式的描述<SELF>。
 4. 输出<SELF>。