自產生程式

自產生程式（Quine），它以哲學家奎恩命名，指的是輸出結果為程式自身源碼的程式

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

起源

這個玩意最早見於Bratley, Paul and Jean Millo: "Computer Recreations; Self-Reproducing Automata", Software -- Practice & Experience, Vol. 2 (1972). pp. 397-400.。而已知最早的這類程式在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$ 。

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 - 自產生程式