自產生程式
自產生程式(英語:Quine),指的是輸出結果為程式自身源碼的程式。其英文名稱以美國哲學家奎恩(Willard Van Orman Quine)命名,
能夠直接讀取自己源碼、讀入使用者輸入或空白的程式一般都不視為自產生程式。
起源
這種編程思想在計算機剛剛興起的時候就已出現。Paul Bratley發表的文章《Computer Recreations: Self-Reproducing Automata》也對此進行了討論。[1]而已知最早的這類程式在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
原理
我們先定義一個函數,對於一個字串,經過程式語言的解釋會變成。
對於一個程式而言,以下會使用來表示程式P的描述(即程式碼)。
建立一個程式SELF,SELF由A、B所組成。換言之。且會先執行A再執行B。
A=“儲存”
B=“對於輸入<M> ,而M為一段程式碼。一、計算出q(<M>) 二、把計算結果和<M>結合起來 三、印出所出求出描述。”
而自生實際執行的過程為:
- 一、首先A先執行,會得到。
- 二、B開始執行,然後被輸入(即)。
- 三、B利用 ,可以計算出,並以此計算出。將與組合成一個新的程式的描述。
- 四、輸出。
示例
在Quine的定義里,程序不能有任何形式的輸入,否則將被視為「作弊」。例如,一個程序讀取該程序自身的源代碼然後打印出來,利用這種方法的程序屬於作弊的Quine。
Perl
一個用Perl編寫的無作弊的Quine:
$_=q{print"\$_=q{$_};eval"};eval
Python
Python本身提供repr()
運算,其作用大致等同於上述之q()
。如:
# repr() function
>>> w='Hello World\nHwllo World'
>>> print (w)
Hello World
Hwllo World
>>> repr(w)
"'Hello World\\nHwllo World'"
# Quine (line 11, 13, 14)
A:
>>> x='y="x="+repr(x)+"\\n"\nprint (y+x)'
B:
>>> y="x="+repr(x)+"\n"
>>> print (y+x)
x='y="x="+repr(x)+"\\n"\nprint (y+x)'
y="x="+repr(x)+"\n"
print (y+x)
參見
參考文獻
- ^ Bratley, Paul; Millo, Jean. Computer Recreations: Self-Reproducing Automata. Software Practice and Experience. 1972, 2: 397–400. doi:10.1002/spe.4380020411.