自产生程序
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
自产生程序(英语: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.
外部链接
|