[科普中國]-自產(chǎn)生程序

自產(chǎn)生程序（Quine），它以哲學(xué)家奎恩命名，指的是輸出結(jié)果為程序自身源碼的程序。

能夠直接讀取自己源碼、讀入用戶輸入或空白的程序一般都不視為自產(chǎn)生程序。

起源這種編程思想在計算機剛剛興起的時候就已經(jīng)出現(xiàn)了。Paul Bratley發(fā)表的文章"Computer Recreations: Self-Reproducing Automata"也對此進行了討論。而已知最早的這類程序在1960年代于愛丁堡大學(xué)出現(xiàn)，由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

原理我們先定義一個函數(shù) q {\displaystyle q} ，對于一個字符串 w a {\displaystyle w_{a}} ， q ( w a ) {\displaystyle q(w_{a})} 經(jīng)過編程語言的解釋會變成 w b {\displaystyle w_} 。

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

創(chuàng)建一個程序SELF，SELF由A、B所組成。換言之 ? S E L F ? = ? A ? ? B ? {\displaystyle \langle SELF\rangle =\langle A\rangle \langle B\rangle } 。且會先運行A再運行B。

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

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

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

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

二、B開始運行，然后被輸入 ? B ? {\displaystyle \langle B\rangle } （即 M = B {\displaystyle M=B} ）。

三、B利用 ? B ? {\displaystyle \langle B\rangle } ,可以計算出 q ( ? B ? ) {\displaystyle q(\langle B\rangle )} ，并以此計算出 ? A ? {\displaystyle \langle A\rangle } 。將 ? A ? {\displaystyle \langle A\rangle } 與 ? B ? {\displaystyle \langle B\rangle } 組合成一個新的程序的描述 ? S E L F ? {\displaystyle \langle SELF\rangle } 。

四、輸出 ? S E L F ? {\displaystyle \langle SELF\rangle } 。

例子在Quine的定義里，程序不能有任何形式的輸入，否則將被視為“作弊”。例如，一個程序讀取該程序自身的源代碼然后打印出來，利用這種方法的程序?qū)儆谧鞅椎腝uine。

Perl一個用Perl編寫的無作弊的Quine：

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

PythonPython本身提供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+x1

本詞條內(nèi)容貢獻者為:

任毅如 - 副教授 - 湖南大學(xué)