● [转载]“打印自身的程序”杂谈 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: acmer (飘飘), 信区: Program
标  题: [转载]“打印自身的程序”杂谈
发信站: 荔园晨风BBS站 (2005年07月11日18:07:04 星期一), 站内信件

这篇文章发表于2004年第《CSDN开发高手》第5期。本来是投稿给《程序员》杂志的，但
是给“调剂”到《CSDN开发高手》上去了，是一大遗憾。《CSDN开发高手》目前已经停
刊。

    另外，“打印自身的程序”有一个很简洁的C语言解答，虽然核心思想是类似的，但
是实现技巧很玄妙，不象文章中的程序可以很自然地一步一步推导出来，因此没有写进
去。这个程序是：

#include <stdio.h>
int main() { char *s = "#include <stdio.h>%cint main() { char *s = %c%s%c;
printf( s, 10, 34, s, 34 ); return 0; }"; printf( s, 10, 34, s, 34 );
return 0; }

    “打印自身的程序”杂谈

    “写一个程序，其执行结果是把程序自身打印出来。”
    这个论题我在网上看到过若干次，不过真正意义上的回答却从来没看见过。学过计
算理论的高手们应该都知道答案，但是大多数程序员们可能没有精力去啃理论书籍，就
让我对这个有趣的命题来做个介绍吧。
    首先要澄清，什么是“打印”，什么是“自身”，以及程序执行环境的限制。“打
印”可以有各种理解，比如向屏幕输出，向磁盘输出，向打印机输出，向内存输出，等
等，但是本质上都是一样的，因此不做限制。
    “自身”的一种理解是源程序，另一理解是机器码。提到“机器码”这个名词，你
可能立刻就想到了“病毒”了吧，对，病毒就是最典型的自我打印程序，病毒的起源“
磁心大战”就是各个程序在存储器中复制自己抢地盘，发展到现在更是丰富多彩，从传
统的文件到时髦的Email，无所不用其极。
    但是各种病毒型的自打印程序都有一个限制，即需要宿主系统提供的服务才能完成
关键的“得到自己”的动作。如果自身代码在内存中，如何才能知道其起始地址呢？问
操作系统吧。或者读取指令指针的值再做调整，这其实也是利用了执行环境之一的“指
令指针”。又如邮件病毒，甚至不需要知道自己在哪里，只要调用软件的“转发”接口
就行了。作为病毒当然是不错的构思，但是要作为“打印自身”的题解，显然就是耍赖
皮了。推向极端，操作系统提供一个“把我自己打出来”的API，程序调用一下不就完了
？
    因此，限定程序的执行环境是讨论问题的必要前提。现代计算机和操作系统的“外
部环境”实在太复杂了，搬出图灵机理论在这里也不太适合，干脆就这么定义命题：使
用某种高级语言（比如说C语言），除了屏幕输出(如printf函数)以外不得使用其他系统
相关函数和IO函数，打印出程序自身的源代码。虽说这种定义细究下去也有许多含糊的
地方（比如，C语言规定全局变量的初值会自动赋为零值，这个特性就不应该被允许），
我们还是把它抛到一边，赶紧进入正题吧。
    为了简化讨论，我们假设有一种智能的PRINT语句，所谓智能就是说，看到语句PRIN
T X时，程序会自动根据X的类型按照常规把X的内容打出来，还有就是可以随着我们讨论
的进行它可以自然获得我们希望它有的特性，这样我就不用一上来就很突兀地给它定义
很多特性。
    好，不管怎样，程序里一定是会有一句打印语句的：
    PRINT X [1]
    执行后屏幕上就出现了X的内容。
    为了满足“打印自身”的要求，必定还有一句把上面那句中的“PRINT”给打出来：

    PRINT Y [2]
    最简单的当然是写成这样：
    PRINT PRINT X
    这里，第一个PRINT自动认出了后面的是一个字符串常量，将之打印出来。
    我想，你一定意识到了，这样做是行不通的，因为每次都会多出一个PRINT，这样下
去就陷入了无限。
    [花絮]，如果允许无限长的程序话，倒真是可以这么写程序：
    PRINT
    PRINT PRINT
    PRINT PRINT PRINT
    ......
    第一个PRINT因为没有参数，所以什么也不打。还有一种特殊的程序是“空”，就是
一句话也没有的程序。呵呵，这篇文章以趣味性为主，千万不要找我抬杠哟。
    [/花絮]
    因此，[2]中的Y必然不能是常量，而是间接引用的变量。或者说就是一段存储，里
边放着一个串“PRINT”，后面跟着X的内容。给这段存储起个名字叫做S，类型是字符串
，这样，[2]就成为：
    PRINT S [3]
    现在[1]已经由[3]打印出来了，[3]又由谁来打印呢？只有[1]了。于是，我们的程
序变成：
    PRINT PRINT S [4]
    PRINT S [5]
    虽然看上去有循环依赖的嫌疑，但是关键点在于，[5]是个间接打印，只是把某个固
定起始地址的串发送到屏幕上，是个完全固定的操作，并不依赖于其他语句！更进一步
，[5]也不一定非要是PRINT语句不可，可以换成任何固定的对S的操作序列，而[4]只需
要把[5]的语句原汁原味打印出来就可以了：
    PRINT A(S) B(S) C(S) [6]
    A(S) B(S) C(S) [7]
    [6][7]就是解决“自我打印”的基本方案。也许并不是非常明显，让我对它做一个
特殊的解释就清楚了。
    假定S不是普通内存，而是字符模式下的“显存”，也就是里边有什么字符屏幕上就
会出现什么字符；而A(S) B(S) C(S)是作用在字符串S上的一连串操作代码，对S操作完
成后S的新值成为 PRINT S [换行] S。在这种解释下，[6][7]就是一个“自我打印”程
序。
    紧接着我们用一个简单的技巧把“显存”给干掉：
    S=A(S) B(S) C(S) [8]
    A(S) B(S) C(S) [9]
    [8]不直接打印到屏幕，而是打印到字符串S。[9]中，A(S) B(S) C(S)把S变换为
'S'={S} [换行] {S}(其中'S'指单个字符S，{S}指S的内容)，然后在屏幕上打印出S。
    这就是“打印自身”的一个解的模式，可以适用于任何高级语言。如果把A(S)
B(S) C(S)具体写出来的话，就是这样的伪码：
    S= S="S="+{S}+"\n"+{S} PRINT S [10]
    S="S="+{S}+"\n"+{S} PRINT S [11]
    当然这个写法中的语法是需要“灵活理解”的，如果真的要用现实的编程语言来写
的话，还有许多细节要处理。文章最后附有一个我用C语言写的程序，有兴趣的话可以自
行分析。核心思想就是[10][11],只是用了很多技巧来处理字符。

    主题内容讲完了，接下来就是杂谈了。
    其实，如果用自然语言来描述程序的思想，其实可以写成这样：
    把下面这个字符串抄两遍，并且在第二句上加上引号。
    “把下面这个字符串抄两遍，并且在第二句上加上引号。”
    之所以要用两句话，是因为程序语言中没有“把我自己抄一遍”的对应物。抽象的
“自我指称”可是很危险的东西哟，“罗素悖论”就是这么来的。
    一个很迷惑人的观点是，机床比螺丝复杂，汽车厂比汽车复杂，创造者要比被创造
者复杂。而生命是可以自我复制的（繁殖），因此生命无法用机械原理来理解。假如是
在1950年(DNA是1953年发现的)，你该如何反驳呢？我们的“自我打印”程序证明了，“
创造者要比被创造者复杂”是错误的。我们的程序加以扩展，可以携带任意的信息，执
行任意额外的动作，而仍可以完全复制自身，这就是计算理论中的“递归定理”。20世
纪三四十年代，在现代电子计算机还没有诞生的时候，计算理论的先行者图灵、丘奇、
哥德尔等就已经解决了“什么是计算”、“什么是可计算的”等深刻的问题。我们这些
现代的程序员，在解决了“编程技巧”、“项目管理”等吃饭相关的问题之余，如果不
花点时间去领略一下计算理论的美丽与神奇，不是太可惜了吗？

    附：“打印自身”的C语言程序，其中的注释和#if 0 / #endif 中的文字是帮助阅
读的，并不是代码的一部分，也不会被打印出来。

#include <stdio.h>

char buf[100][1000]; int cur=-1;

void P1(char *p) {sprintf(buf[++cur],p);} //record p to buf
void P2(char *p) { printf(p); putchar(10);} //print p and change line
void P3() {int i;for(i=0;i<=cur;i++){
putchar(80);putchar(49);putchar(40);putchar(34);printf(buf[i]);putchar(34);pu
tchar(41);putchar(59);putchar(10);} for(i=0;i<cur;i++){
putchar(80);putchar(50);putchar(40);putchar(34);printf(buf[i]);putchar(34);pu
tchar(41);putchar(59);putchar(10);}
printf(buf[cur]);putchar(10);putchar(125);putchar(10);}

void main() {

P1("#include <stdio.h>");
P1("char buf[100][1000]; int cur=-1;");
P1("void P1(char *p) {sprintf(buf[++cur],p);}");
P1("void P2(char *p) { printf(p); putchar(10);}");
P1("void P3() {int i;for(i=0;i<=cur;i++){
putchar(80);putchar(49);putchar(40);putchar(34);printf(buf[i]);putchar(34);pu
tchar(41);putchar(59);putchar(10);} for(i=0;i<cur;i++){
putchar(80);putchar(50);putchar(40);putchar(34);printf(buf[i]);putchar(34);pu
tchar(41);putchar(59);putchar(10);}
printf(buf[cur]);putchar(10);putchar(125);putchar(10);}");
P1("void main() {");
P1("P3();");

P2("#include <stdio.h>");
P2("char buf[100][1000]; int cur=-1;");
P2("void P1(char *p) {sprintf(buf[++cur],p);}");
P2("void P2(char *p) { printf(p); putchar(10);}");
P2("void P3() {int i;for(i=0;i<=cur;i++){
putchar(80);putchar(49);putchar(40);putchar(34);printf(buf[i]);putchar(34);pu
tchar(41);putchar(59);putchar(10);} for(i=0;i<cur;i++){
putchar(80);putchar(50);putchar(40);putchar(34);printf(buf[i]);putchar(34);pu
tchar(41);putchar(59);putchar(10);}
printf(buf[cur]);putchar(10);putchar(125);putchar(10);}");
P2("void main() {");

P3();
}

#if 0 //read P3() convinently
void P3() {
int i;
for(i=0;i<=cur;i++){
putchar(80); //'P'
putchar(49); //'1'
putchar(40); //'('
putchar(34); //'"'
printf(buf[i]);
putchar(34); //'"'
putchar(41); //')'
putchar(59); //';'
putchar(10); //'\n'
}
for(i=0;i<cur;i++){
putchar(80); //'P'
putchar(50); //'2'
putchar(40); //'('
putchar(34); //'"'
printf(buf[i]);
putchar(34); //'"'
putchar(41); //')'
putchar(59); //';'
putchar(10); //'\n'
}
printf(buf[cur]); //for P3();
putchar(10);

putchar(125); //'}'
putchar(10);
}
#endif
--
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.149]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店