自產生程式

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

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

起源

這種編程思想在電腦剛剛興起的時候就已經出現了。Paul Bratley發表的文章"Computer Recreations: Self-Reproducing Automata"也對此進行了討論。而已知最早的這類程式在1960年代於愛丁堡大學出現，由Hamish Dewar以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

原理

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

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

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

A=“儲存$\langle B\rangle$”

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

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

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

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

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

四、輸出$\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

參見

• 塔珀自指公式

外部連結

• The Quine Page （頁面存檔備份，存於網際網路檔案館）
• wikisource:Quines
• JavaWorld@TW - 自產生程式 （頁面存檔備份，存於網際網路檔案館）