自产生程序

输出结果为程序自身源码的程序

自产生程序(英语:Quine),指的是输出结果为程序自身原始码的程序。其英文名称以美国哲学家奎恩Willard Van Orman Quine)命名,

能够直接读取自己原始码、读入用户输入或空白的程序一般都不视为自产生程序。

起源

编辑

这种编程思想在电脑刚刚兴起的时候就已出现。Paul Bratley发表的文章《Computer Recreations: Self-Reproducing Automata》也对此进行了讨论。[1]而已知最早的这类程序在1960年代于爱丁堡大学出现,由Hamish Dewar以Atlas Autocode英语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编写的无作弊的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)

参见

编辑

参考文献

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

外部链接

编辑