Quine:打印自己源代码的程序

一步步修改出一个可以打印出自己源代码的程序。


借《网络安全》课的机会,接触到了一个很有意思的话题:自打印程序。简单来说,自打印程序就是实现一个能够打印出自身源代码的程序。一般地,这项任务要求在默认的编译选项和运行环境下,不接收任何输入,向输出区打印自身的源代码(包括换行,除非整个代码只有一行),然后立即结束。源代码和输出都为空是不允许的。这个任务在英文中有一个专门的名词:Quine。

自打印程序与其实现的语言有很大的相关性。一些语言中的特性可以支持程序获得自己源代码(或其中的一部分),例如Lisp、Racket等中的反射特性,Python、Javascript等动态语言可以读取自身源文件等。

Example 1. Racket Quine

((λ (x) `(,x ',x)) '(λ (x) `(,x ',x)))

此处利用了Lisp中的Quote和Backquote(表示“把元素原样放在那里”)操作符。

Example 2. Javascript Quine

var a=function () {var b="var a="+a.toString()+"\;a()";alert(b)};a()

此处利用了toString() 方法返回了a函数的源代码。

但是这些代码都利用了语言的trick,而且不具有可扩展性(无法将一个现有的程序变成可自我打印的版本)。下面我尝试找到了一个可跨语言的、可扩展的自打印程序。

首先观察python中的打印语句:

print("abc")
# 输出abc

如果我们想让这个程序的输出和源代码尽量相近,可能可以这样写:

print("print()")
# 输出print()

开头是一样了,但显然通过这种方式输出,结果里永远会少一个print。如果在字符串后面加一个*2试试呢?

print("print("*2)
# 输出 print(print(

成功了!通过这种方式,我们输出了两个print。但代码中少了一些字符,如引号和右括号、以及*2。如果需要把左边的部分对齐,只需要加一个引号:

print("print(\""*2)
# 输出 print("print("

这样开头的若干个字符就完全相同了!不仅如此,利用这种方法,我们甚至可以在开头加入额外的字符,只要在引号内同样地重复一次就行了。比如

a=1;print("a=1;print(\""*2)
# 输出 a=1;print("a=1;print("

不过不知不觉间我们引入了一个新的问题:引号在字符串中需要解引用,这样就多引入了一个 \ 符号。可能的解决方案很多,对此我也进行了几种不同的尝试,篇幅关系就不在此赘述。最终成功的办法是使用ascii码来输出引号。引号的ascii码为39,python中将ascii码转换为对应字符串的函数是chr(),因此有:

a=chr(39);print( ("a=chr(39);print( ("+a)*2 )
# 输出 a=chr(39);print( ("a=chr(39);print( ("

代码和输出的前半部分终于完全相同了!接下来考虑代码的后半部分(不重复的部分,包括右引号、*2、右括号等,这些地方不能通过*2的方式来覆盖)。这个实现起来其实就容易了。容易想到,可以在*2后面加一个字符串,同时在print中也加上c的定义,如:

a=chr(39);c='+a)*2 )';print( ("a=chr(39); c='+a)*2 )';print( ("+a)*2+c )
# 输出a=chr(39); c='+a)*2 )';print( ("a=chr(39); c='+a)*2 )';print( ("+a)*2 ) 

这样,+a)*2 就成功地被在了后面。对比一下两边的代码,下面的结尾部分少了一个 +c 。再运用一次刚才一样的策略,在c和print中各添加一个 +c:

a=chr(39);c="+a)*2+c)";print(('a=chr(39);c="+a)*2+c)";print(('+a)*2+c)
# 输出a=chr(39);c="+a)*2+c)";print(('a=chr(39);c="+a)*2+c)";print(('+a)*2+c) 

源代码和输出终于完全相同,大功告成!正如上面说的,这段代码还具有可扩展性。比如假设我们将核心方法定义在__main__()函数中,那么只需要在c、print和代码的最后分别添加main函数的调用,如:

a=chr(39);c="+a)*2+c)__main__();";print(('a=chr(39);c="+a)*2+c)__main__();";print(('+a)*2+c);__main__();
# 输出 a=chr(39);c="+a)*2+c)__main__();";print(('a=chr(39);c="+a)*2+c)__main__();";print(('+a)*2+c);__main__();

这样,就完成了一个自打印的任意程序的改造。

上面的所有策略都没有依赖于python的任何语言特性。在别的语言中,只要支持将ascii码与字符/字符串互相转换,都可以完成这样的自打印程序。例如C/C++的版本(利用printf中的%c来转换ascii码):

#include <stdio.h>
int main(){char*c="#include <stdio.h>%cint main(){char*c=%c%s%c;printf(c,10,34,c,34,10);return 0;}%c";printf(c,10,34,c,34,10);return 0;} 

更多与Quine相关的信息可以在这个网站查看:http://rosettacode.org/wiki/Quine