陳凱

古老的圣誕樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

計算思維挑戰(zhàn)

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

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

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

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

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

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