自產生程式

自產生程式（英語：Quine），它以美國哲學家奎恩（Willard Van Orman Quine）命名，指的是輸出結果為程式自身源碼的程式。

能夠直接讀取自己源碼、讀入使用者輸入或空白的程式一般都不視為自產生程式。

起源

这种编程思想在计算机刚刚兴起的时候就已经出现了。Paul Bratley发表的文章"Computer Recreations: Self-Reproducing Automata"也对此进行了讨论。^[1]而已知最早的這類程式在1960年代於愛丁堡大學出現，由Hamish Dewar以Atlas Autocode（英语：Atlas Autocode）編寫：

%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 

原理

我們先定義一個函數${\displaystyle q}$ ，對於一個字串${\displaystyle w_{a}}$ ，${\displaystyle q(w_{a})}$ 經過程式語言的解釋會變成${\displaystyle w_{b}}$ 。

對於一個程式${\displaystyle P}$ 而言，以下會使用${\displaystyle \langle P\rangle }$ 來表示程式P的描述（即程式碼）。

建立一個程式SELF，SELF由A、B所組成。換言之${\displaystyle \langle SELF\rangle =\langle A\rangle \langle B\rangle }$ 。且會先執行A再執行B。

A=“儲存${\displaystyle \langle B\rangle }$ ” 

B=“對於輸入<M> ,而M為一段程式碼。一、計算出q(<M>) 二、把計算結果和<M>結合起來 三、印出所出求出描述。” 

而自生實際執行的過程為：

一、首先A先執行，會得到${\displaystyle \langle B\rangle }$ 。

二、B開始執行，然後被輸入${\displaystyle \langle B\rangle }$ （即${\displaystyle M=B}$ ）。

三、B利用${\displaystyle \langle B\rangle }$  ,可以計算出${\displaystyle q(\langle B\rangle )}$ ，並以此計算出${\displaystyle \langle A\rangle }$ 。將${\displaystyle \langle A\rangle }$ 與${\displaystyle \langle B\rangle }$ 組合成一個新的程式的描述${\displaystyle \langle SELF\rangle }$ 。

四、輸出${\displaystyle \langle SELF\rangle }$ 。

例子

在Quine的定义里，程序不能有任何形式的输入，否则将被视为“作弊”。例如，一个程序读取该程序自身的源代码然后打印出来，利用这种方法的程序属于作弊的Quine。

Perl

一个用Perl编写的无作弊的Quine：

$_=q{print"\$_=q{$_};eval"};eval 

Python

Python本身提供repr()或運算``，其作用大致等同於上述之q()。如：

 >>> w='Hello World\nHwllo World' >>> print w Hello World Hwllo World >>> `w` "'Hello World\\nHwllo World'" >>> print w Hello World Hwllo World A: >>> x='y="x="+`x`+"\\n"\nprint y+x' B: >>> y="x="+`x`+"\n" >>> print y+x 

參見

• 塔珀自指公式

參考文獻

1. Bratley, Paul; Millo, Jean. Computer Recreations: Self-Reproducing Automata. Software Practice and Experience. 1972, 2: 397–400. doi:10.1002/spe.4380020411. 

外部連結

• The Quine Page （页面存档备份，存于互联网档案馆）
• wikisource:Quines^{[永久失效連結]}
• JavaWorld@TW - 自產生程式 （页面存档备份，存于互联网档案馆）