打印自身的程序

Quine 简介

Quine 以哲学家 Willard van Orman Quine (1908-2000) 而命名,表示一个可以 生成他自己的完全的源代码的程序。编写出某个语言中最简短的 quine 通常作为 黑客们的消遣。

作为真正的 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

这个就是前面提及的以 Atlas Autocode 写成的 quine :

%BEGIN
!THIS IS A SELF-REPRODUCING PROGRAM
%ROUTINESPEC R
R
PRINT SYMBOL(39)
R
PRINT SYMBOL(39)
NEWLINE
%CAPTION %END~
%CAPTION %ENDOFPROGRAM~
%ROUTINE R
%PRINTTEXT '
%BEGIN
!THIS IS A SELF-REPRODUCING PROGRAM
%ROUTINESPEC R
R
PRINT SYMBOL(39)
R
PRINT SYMBOL(39)
NEWLINE
%CAPTION %END~
%CAPTION %ENDOFPROGRAM~
%ROUTINE R
%PRINTTEXT '
%END
%ENDOFPROGRAM

C 语言

这个据说是用 C 语言写成的 quine 中最简短的一个是由 Vlad Taeerov 和 Rashit Fakhreyev 所写成的仅包含 64 个字符的程序:

我在《高效程序的奥秘》(Henry S. Warren, Jr. Hacker's Delight) 一书的前 言中找到了这个程序。类似的还有这个例子:

以及:

作为另外一个比较长的例子的是我在 WikiPedia 上看到的例子:

Lisp 语言

关于 Common Lisp 里面的 quine ,有一篇专门的文章: Peter Norvig, Self-Reproducing Programs in Common Lisp 。事实上,在 Lisp 里面,任何 的数字都可以算是一个 quine ,但这多少显得有点无聊,所以通常限定必须是 non-atomic 的表达式。作为一个经典的例子,在任何 Lisp 方言里面都成立的 一个 quine 是:

在有反引号的语法的“现代 Lisp ”里面,可以有更紧凑的写法:

Common Lisp 里面还可以这么写:

再从理论上来讨论的话,对于 Y-operator 来说,如果应用正则序求值的话,我 们可以得到

(Y identity) = (identity (Y identity)) = (Y identity)

不过在像 Lisp 这种应用序求值的语言中,这只会造成无限循环而已。

另外还有一些比较新的 Common Lisp 里面的 quine :

以及:

对于 Scheme ,有 Tanaka Tomoyuki 写的

以及 Douglass Auclair 用 Elisp 写的

Shell 脚本

对于 Shell 脚本也有很多 quine ,比如 Brian A.E. Meekings 写的适用于 sh 和 ksh 的脚本:

以及 Mark Wooding 的作品

等,另外,作为魔数字 #! 的经典把戏,下面的脚本也轻易地把自己打印了出来:

在线资料

Wikipedia

Wikipedia 上有对 quine 做了详尽解释的页面,并举了一些例子。

The Quine Page

Gary P. Thompson 的这个页面里面搜集了大量的 quine 程序,按照语言进行分 类,非常不错!

Wiki Wiki Web 上的 Quine 页面

这里以一个失败的试图构造 quine 的例子讲述了 quine 的困难,并且列举了许 多 quine 程序。

David Madore 对于 Quine 的讨论

这里对 Quine 做了非常详尽的讨论,如果你对 Quine 很感兴趣的话,这是非常 不错的资料。

The Search For Self-Documenting Code

Craig S. Kaplan 的这篇文章讲述了编写 quine 的方法。