自產生程式

维基百科,自由的百科全书
跳转至: 导航搜索

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

原理[编辑]

我們先定義一個函數q,對於一個字串w_aq(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

參見[编辑]

參考文獻[编辑]

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

外部連結[编辑]