圣誕樹、標簽系統和計算思維

陳凱

古老的圣誕樹

早期的計算機系統的圖像顯示功能相當弱，為了顯示一幅圖畫，就有可能占用掉計算機的大部分內存，于是人們想到了用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”這行代碼就不是替換操作。若要用純粹的字符串替換來實現標簽系統，當然是可以的，并且可以用不同的方法來實現。比如說，可以先用字符串替換的方法來模擬出一個圖靈機系統，然后再用圖靈機系統模擬出標簽系統，這可不是件容易的事情，其實現過程中處處都是計算思維的訓練。