自产生程序

自产生程序（英语：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()。如：

# 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)

参见

• 塔珀自指公式

外部链接

• The Quine Page （页面存档备份，存于互联网档案馆）
• wikisource:Quines
• JavaWorld@TW - 自产生程序 （页面存档备份，存于互联网档案馆）