圣诞树、标签系统和计算思维

陈凯

古老的圣诞树

早期的计算机系统的图像显示功能相当弱，为了显示一幅图画，就有可能占用掉计算机的大部分内存，于是人们想到了用ASCII字符来画画，这其实并不是一个新鲜的主意，打字机发明之后，很快有人想到可以将打字机打印出的符号进行组合来构成图画。计算机的出现，使得这种画图方式“发扬光大”了，因为计算机的文本编辑系统可以轻松地增加、删除、搬运符号，还可以利用程序来自动生成字符图画，图1所示的构图就是用程序生成的。

这些有趣的转换程序被称为“ASCII Art generator”。在日常教学中，也常常在讲程序设计的时候，用循环结构来生成简单的字符图画，比如打印一棵圣诞树，除了顶部和底部，其他部分是用双重循环生成的，如图2。然而用单纯的循环语句生成的圣诞树，看上去没有手工打印出来的显得自然，如图3。

计算机循环语句生成的圣诞树实在太规则了，而手工绘制的圣诞树，则是宏观规律（顶部小底部大）和局部随机的综合体，所以看上去更自然一些。

为了让圣诞树看上去更自然一些，常规的方法是用程序语言中的随机函数，每一行字符串都会有微小的动态变化。然而还有一种简单的方法，使得新生成的字符串虽然乍一看和先前的字符串有所不同，但仔细观察却又能发现与先前字符串之间的相似之处。比如图4所示的圣诞树，除了底部的树根和顶部的圆球，其主体部分既不是手工绘制，也不是用循环语句加随机函数制作出来的，而是用到了标签系统。

标签系统

标签系统（Tag system）是一种计算模型，它的运算语法很简单，比如说要生成圣诞树新一行的字符串，语法如图5所示。这段语法就是全部运行程序了。

“1-tag”的意思是，每生成一行新字符串，就扔掉该字符串的首部1个字符。上面例子里是“2-tag”，当然就是扔掉字符串首部2个字符，以此类推，“n-tag”就是扔掉n个字符。

“Alphabet： {/，＼，^，o，.}”的意思是，整个字符串可以用的符号只能是“{/”“＼”“^”“o”“.”这五种。当然，这是人为规定的，不同的任務所使用的字符集合可以不同。

“/ --> /＼”的意思是，如果先前的字符串首位是“/”，则将“/”符号和“＼”符号补充到新生成字符串末尾。其他补充规则也是类似的。

下面就拿画圣诞树来做例子。假设初始字符串是“../＼”，因为首位是“.”，根据预定规则新补充“../”，同时扔掉首位的“..”，于是新生成的字符串就是“/＼../”。然后继续，因为首位是“/”，则根据预定规则补充“/＼”，并扔掉首位的“/＼”，于是新生成的字符串就是“..//＼”。

实际运行起来会发现，因为字符串首部字符不停地被擦除，而末尾又不停地增添新的字符，所以看上去字符串仿佛是在以跑马灯的形式转圈，只是每次转圈后，新生成的字符串比以前更长，而且字符出现顺序和先前也有所不同。为便于观察，可以人为规定“.”符号为读取标志，当看到“.”符号到达字符串的开头，就表示一轮擦除—补充过程结束，可以读取信息了。

若谁有足够多的耐心，坚持将这个转圈工作进行10轮，那么就能新生成10行字符串，将它们叠加在一起，就是那棵圣诞树了。不过与其手工计算，不如利用计算机来简化工作，无论是用简单的程序代码，还是利用电子表格中的函数，都可以快速实现标签系统的功能。暂时先不要看文章后面的内容，想想应该如何实现这个需求。

用标签系统当然不是仅仅用来画画的，实际上，可以用2-tag的标签系统模拟任何计算模型，理论上说，只要设定特定的规则，就可以用标签系统的规则来模拟出任何程序设计语言。所以说，一方面，可以用程序设计语言编写代码来实现一个标签系统（这很容易）；另一方面，也可以用标签系统来实现一个程序设计语言（这很难）。之所以两者能够相互模拟，这个问题的证明非常长，网络上可以找到相关论文，这里就不展开讨论了。

如果大家看过上一期文章并真正弄明白了，那么就可以发现，实际上一个标签系统（Tag system），可以和一个L-System相互转换。换句话说，一棵真正生物学意义上的树，其生长过程与标签系统多少是有联系的。

计算思维挑战

计算思维究竟是什么？这不是一个依靠文字就能简单回答的问题。笔者比较认可的一种说法是，所谓计算思维，就是要用某个特定的机器（或者对应于数学上的某个特定的函数）来解决某个特定的问题，但关键是，那个机器（或函数）的功能是受到限制的。为了使得功能受限的系统实现人们的特定需求，人们在解决问题时就要用到机器（或函数）的思维方式，要学会怎样将问题抽象成数学及逻辑语言，要用递归或者迭代的办法将计算过程自动化，还要善于将一种形式转换为另一种形式。

比如在圣诞树的例子中，虽然可以用Python中的if和elif语句，提取字符串的首字符进行判断，并按规则将新字符补充到字符串末尾，但这样就更多是训练程序设计，重点就不在于培养计算思维了。不过只要稍微改一下问题要求：如何不用判断语句来实现标签系统的功能？这样就能将培养重点落在计算思维上。

考虑有一个小机器，它的功能十分有限，仅仅是把某个字符替换成另一个字符，那么就能用它来代替Python里的if和elif语句了。第15页图6所示的Python代码通过反复替换，来代替判断语句的使用，其中就用到了迭代的思想。当循环45次之后，就得到了全部10行新生成的圣诞树字符串。注意代码中因为要对特定符号转义，里面的“＼＼”其实代表的是一个斜杠。部分运行结果如第15页图7所示。因为只有“.”开头才表示读取，所以真正的结果正对应着圣诞树的每一行，如第15页图8。

这个例子其实说明，程序语言中的条件判断，本质上可以对应于某种替换规则，这也可以反过来理解，将不同的替换规则综合起来使用，就能组成条件判断的程序结构了。实际上，上面代码中的循环只是为了调试方便，并不是必须的，只要不停地把字符串替换程序所生成的结果当成初始数据，反复调用程序（递归）就能实现迭代过程。从这里也可以看出，用递归来实现重复运算，相对于用循环结构实现重复运算，处于更为基础的层次上。

观察认真的朋友大概会发现，本文例子中用替换过程实现标签系统的代码，并不是纯粹的字符串替换，比如“tmpstr=tmpstr[2：]+

tmpstr2”这行代码就不是替换操作。若要用纯粹的字符串替换来实现标签系统，当然是可以的，并且可以用不同的方法来实现。比如说，可以先用字符串替换的方法来模拟出一个图灵机系统，然后再用图灵机系统模拟出标签系统，这可不是件容易的事情，其实现过程中处处都是计算思维的训练。