陳凱

古老的圣誕樹

早期的計(jì)算機(jī)系統(tǒng)的圖像顯示功能相當(dāng)弱，為了顯示一幅圖畫，就有可能占用掉計(jì)算機(jī)的大部分內(nèi)存，于是人們想到了用ASCII字符來(lái)畫畫，這其實(shí)并不是一個(gè)新鮮的主意，打字機(jī)發(fā)明之后，很快有人想到可以將打字機(jī)打印出的符號(hào)進(jìn)行組合來(lái)構(gòu)成圖畫。計(jì)算機(jī)的出現(xiàn)，使得這種畫圖方式“發(fā)揚(yáng)光大”了，因?yàn)橛?jì)算機(jī)的文本編輯系統(tǒng)可以輕松地增加、刪除、搬運(yùn)符號(hào)，還可以利用程序來(lái)自動(dòng)生成字符圖畫，圖1所示的構(gòu)圖就是用程序生成的。

這些有趣的轉(zhuǎn)換程序被稱為“ASCII Art generator”。在日常教學(xué)中，也常常在講程序設(shè)計(jì)的時(shí)候，用循環(huán)結(jié)構(gòu)來(lái)生成簡(jiǎn)單的字符圖畫，比如打印一棵圣誕樹，除了頂部和底部，其他部分是用雙重循環(huán)生成的，如圖2。然而用單純的循環(huán)語(yǔ)句生成的圣誕樹，看上去沒有手工打印出來(lái)的顯得自然，如圖3。

計(jì)算機(jī)循環(huán)語(yǔ)句生成的圣誕樹實(shí)在太規(guī)則了，而手工繪制的圣誕樹，則是宏觀規(guī)律（頂部小底部大）和局部隨機(jī)的綜合體，所以看上去更自然一些。

為了讓圣誕樹看上去更自然一些，常規(guī)的方法是用程序語(yǔ)言中的隨機(jī)函數(shù)，每一行字符串都會(huì)有微小的動(dòng)態(tài)變化。然而還有一種簡(jiǎn)單的方法，使得新生成的字符串雖然乍一看和先前的字符串有所不同，但仔細(xì)觀察卻又能發(fā)現(xiàn)與先前字符串之間的相似之處。比如圖4所示的圣誕樹，除了底部的樹根和頂部的圓球，其主體部分既不是手工繪制，也不是用循環(huán)語(yǔ)句加隨機(jī)函數(shù)制作出來(lái)的，而是用到了標(biāo)簽系統(tǒng)。

標(biāo)簽系統(tǒng)

標(biāo)簽系統(tǒng)（Tag system）是一種計(jì)算模型，它的運(yùn)算語(yǔ)法很簡(jiǎn)單，比如說(shuō)要生成圣誕樹新一行的字符串，語(yǔ)法如圖5所示。這段語(yǔ)法就是全部運(yùn)行程序了。

“1-tag”的意思是，每生成一行新字符串，就扔掉該字符串的首部1個(gè)字符。上面例子里是“2-tag”，當(dāng)然就是扔掉字符串首部2個(gè)字符，以此類推，“n-tag”就是扔掉n個(gè)字符。

“Alphabet： {/，＼，^，o，.}”的意思是，整個(gè)字符串可以用的符號(hào)只能是“{/”“＼”“^”“o”“.”這五種。當(dāng)然，這是人為規(guī)定的，不同的任務(wù)所使用的字符集合可以不同。

“/ --> /＼”的意思是，如果先前的字符串首位是“/”，則將“/”符號(hào)和“＼”符號(hào)補(bǔ)充到新生成字符串末尾。其他補(bǔ)充規(guī)則也是類似的。

下面就拿畫圣誕樹來(lái)做例子。假設(shè)初始字符串是“../＼”，因?yàn)槭孜皇恰?”，根據(jù)預(yù)定規(guī)則新補(bǔ)充“../”，同時(shí)扔掉首位的“..”，于是新生成的字符串就是“/＼../”。然后繼續(xù)，因?yàn)槭孜皇恰?”，則根據(jù)預(yù)定規(guī)則補(bǔ)充“/＼”，并扔掉首位的“/＼”，于是新生成的字符串就是“..//＼”。

實(shí)際運(yùn)行起來(lái)會(huì)發(fā)現(xiàn)，因?yàn)樽址撞孔址煌５乇徊脸?，而末尾又不停地增添新的字符，所以看上去字符串仿佛是在以跑馬燈的形式轉(zhuǎn)圈，只是每次轉(zhuǎn)圈后，新生成的字符串比以前更長(zhǎng)，而且字符出現(xiàn)順序和先前也有所不同。為便于觀察，可以人為規(guī)定“.”符號(hào)為讀取標(biāo)志，當(dāng)看到“.”符號(hào)到達(dá)字符串的開頭，就表示一輪擦除—補(bǔ)充過程結(jié)束，可以讀取信息了。

若誰(shuí)有足夠多的耐心，堅(jiān)持將這個(gè)轉(zhuǎn)圈工作進(jìn)行10輪，那么就能新生成10行字符串，將它們疊加在一起，就是那棵圣誕樹了。不過與其手工計(jì)算，不如利用計(jì)算機(jī)來(lái)簡(jiǎn)化工作，無(wú)論是用簡(jiǎn)單的程序代碼，還是利用電子表格中的函數(shù)，都可以快速實(shí)現(xiàn)標(biāo)簽系統(tǒng)的功能。暫時(shí)先不要看文章后面的內(nèi)容，想想應(yīng)該如何實(shí)現(xiàn)這個(gè)需求。

用標(biāo)簽系統(tǒng)當(dāng)然不是僅僅用來(lái)畫畫的，實(shí)際上，可以用2-tag的標(biāo)簽系統(tǒng)模擬任何計(jì)算模型，理論上說(shuō)，只要設(shè)定特定的規(guī)則，就可以用標(biāo)簽系統(tǒng)的規(guī)則來(lái)模擬出任何程序設(shè)計(jì)語(yǔ)言。所以說(shuō)，一方面，可以用程序設(shè)計(jì)語(yǔ)言編寫代碼來(lái)實(shí)現(xiàn)一個(gè)標(biāo)簽系統(tǒng)（這很容易）；另一方面，也可以用標(biāo)簽系統(tǒng)來(lái)實(shí)現(xiàn)一個(gè)程序設(shè)計(jì)語(yǔ)言（這很難）。之所以兩者能夠相互模擬，這個(gè)問題的證明非常長(zhǎng)，網(wǎng)絡(luò)上可以找到相關(guān)論文，這里就不展開討論了。

如果大家看過上一期文章并真正弄明白了，那么就可以發(fā)現(xiàn)，實(shí)際上一個(gè)標(biāo)簽系統(tǒng)（Tag system），可以和一個(gè)L-System相互轉(zhuǎn)換。換句話說(shuō)，一棵真正生物學(xué)意義上的樹，其生長(zhǎng)過程與標(biāo)簽系統(tǒng)多少是有聯(lián)系的。

計(jì)算思維挑戰(zhàn)

計(jì)算思維究竟是什么？這不是一個(gè)依靠文字就能簡(jiǎn)單回答的問題。筆者比較認(rèn)可的一種說(shuō)法是，所謂計(jì)算思維，就是要用某個(gè)特定的機(jī)器（或者對(duì)應(yīng)于數(shù)學(xué)上的某個(gè)特定的函數(shù)）來(lái)解決某個(gè)特定的問題，但關(guān)鍵是，那個(gè)機(jī)器（或函數(shù)）的功能是受到限制的。為了使得功能受限的系統(tǒng)實(shí)現(xiàn)人們的特定需求，人們?cè)诮鉀Q問題時(shí)就要用到機(jī)器（或函數(shù)）的思維方式，要學(xué)會(huì)怎樣將問題抽象成數(shù)學(xué)及邏輯語(yǔ)言，要用遞歸或者迭代的辦法將計(jì)算過程自動(dòng)化，還要善于將一種形式轉(zhuǎn)換為另一種形式。

比如在圣誕樹的例子中，雖然可以用Python中的if和elif語(yǔ)句，提取字符串的首字符進(jìn)行判斷，并按規(guī)則將新字符補(bǔ)充到字符串末尾，但這樣就更多是訓(xùn)練程序設(shè)計(jì)，重點(diǎn)就不在于培養(yǎng)計(jì)算思維了。不過只要稍微改一下問題要求：如何不用判斷語(yǔ)句來(lái)實(shí)現(xiàn)標(biāo)簽系統(tǒng)的功能？這樣就能將培養(yǎng)重點(diǎn)落在計(jì)算思維上。

考慮有一個(gè)小機(jī)器，它的功能十分有限，僅僅是把某個(gè)字符替換成另一個(gè)字符，那么就能用它來(lái)代替Python里的if和elif語(yǔ)句了。第15頁(yè)圖6所示的Python代碼通過反復(fù)替換，來(lái)代替判斷語(yǔ)句的使用，其中就用到了迭代的思想。當(dāng)循環(huán)45次之后，就得到了全部10行新生成的圣誕樹字符串。注意代碼中因?yàn)橐獙?duì)特定符號(hào)轉(zhuǎn)義，里面的“＼＼”其實(shí)代表的是一個(gè)斜杠。部分運(yùn)行結(jié)果如第15頁(yè)圖7所示。因?yàn)橹挥小?”開頭才表示讀取，所以真正的結(jié)果正對(duì)應(yīng)著圣誕樹的每一行，如第15頁(yè)圖8。

這個(gè)例子其實(shí)說(shuō)明，程序語(yǔ)言中的條件判斷，本質(zhì)上可以對(duì)應(yīng)于某種替換規(guī)則，這也可以反過來(lái)理解，將不同的替換規(guī)則綜合起來(lái)使用，就能組成條件判斷的程序結(jié)構(gòu)了。實(shí)際上，上面代碼中的循環(huán)只是為了調(diào)試方便，并不是必須的，只要不停地把字符串替換程序所生成的結(jié)果當(dāng)成初始數(shù)據(jù)，反復(fù)調(diào)用程序（遞歸）就能實(shí)現(xiàn)迭代過程。從這里也可以看出，用遞歸來(lái)實(shí)現(xiàn)重復(fù)運(yùn)算，相對(duì)于用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)重復(fù)運(yùn)算，處于更為基礎(chǔ)的層次上。

觀察認(rèn)真的朋友大概會(huì)發(fā)現(xiàn)，本文例子中用替換過程實(shí)現(xiàn)標(biāo)簽系統(tǒng)的代碼，并不是純粹的字符串替換，比如“tmpstr=tmpstr[2：]+

tmpstr2”這行代碼就不是替換操作。若要用純粹的字符串替換來(lái)實(shí)現(xiàn)標(biāo)簽系統(tǒng)，當(dāng)然是可以的，并且可以用不同的方法來(lái)實(shí)現(xiàn)。比如說(shuō)，可以先用字符串替換的方法來(lái)模擬出一個(gè)圖靈機(jī)系統(tǒng)，然后再用圖靈機(jī)系統(tǒng)模擬出標(biāo)簽系統(tǒng)，這可不是件容易的事情，其實(shí)現(xiàn)過程中處處都是計(jì)算思維的訓(xùn)練。