查表（Forth Dimensions XIX.3）
這是我 16 歲時與 Hans Bezemer 合著的一篇文章。文章刊載於 Forth Interest Group 所發行的 Forth 程式設計雜誌 Forth Dimensions 1997 年 9 月號。Hans 是名為「4tH」的 Forth 編譯器的作者，他幫我潤飾了文筆，也稍微收斂了我那股狂熱 Forth 信徒的語氣。我記得 案例二 和 陷阱 這兩節應該是我寫的。請參閱 原始 PDF。
若想進一步了解 Forth，請先閱讀 維基百科條目，再閱讀 Thinking Forth。
「就我個人而言，我認為 case 陳述式是一個優雅的解法，卻用錯了地方：它試圖用演算法來表達一個其實更適合用決策表來描述的問題。」
—Leo Brodie，Thinking Forth
前言
如果你以為這篇文章又要掀起一場關於老爭議的新論戰，那你就大錯特錯了。相反地，我們要透過一個簡單的概念——查表（lookup tables），為你介紹一種全新的解題方法。
隨便翻幾個 Forth 程式來看，你會發現除了偶爾出現的星期對照表之外，這種技巧幾乎沒人使用。這很可惜，因為使用查表的程式更容易設計、更容易除錯，也更容易維護。此外，它們通常更小、執行更快。接下來我們會舉幾個例子來說明。
查表之所以少見，一個可能的原因是在 Forth 中實作起來並不容易——尤其是處理字串時。在本文中，我們也會針對這個問題提供一些可行的解法。
有人可能會說，OOF 或其他非標準的擴充提供了更好的方式來處理這類問題。然而，ANS Forth 既非物件導向，也還沒有 Structure Extension（結構擴充），因此我們認為這類討論超出本文的範圍。
什麼是查表？
查表說穿了，就是一群具有共同特徵的物件的集合。使用查表，意味著你必須思考程式中所使用的物件，以及它們共享（與不共享）哪些特徵。
冒險遊戲就是一個很好的例子。每個房間都有自己的描述和出口，有些出口在特定條件達成前是隱藏的。房間裡有物件，所有物件都有描述，有些可以移動，有些不行，有些則會在特定條件未滿足時觸發動作。
這正是應該使用查表的典型應用。任何其他實作方式肯定都會顯得笨拙、難以除錯，也無法維護。一個使用查表的冒險遊戲範例可以在 http://www.IAEhv.nl/users/mhx/adventur.frt 找到 [還原版本，感謝 Wayback Machine]。這個冒險遊戲原本是為 4tH 設計的，並由 Marcel Hendrix 巧妙地移植到 ANS Forth。
為什麼要用查表？
查表的用途並不限於某一種語言或某一類問題。我們甚至曾在 Excel 試算表中成功實作查表，大幅減少了對大量資料進行人工操作與檢查的工作量。
一張工作表中的資料會與查表進行比對，遇到未知值時會自動產生「無此資料」的錯誤。透過在另一個查表中搜尋對應的分類，再對整張工作表進行排序，就能輕鬆產生小計。在此之前，所有的檢查與排序都是人工完成，很容易出錯。
但查表在其他情境中也同樣有用。Z80 處理器並非高速處理器，即使以 1980 年代中期的標準來看也是如此。因此，當 PSION 的 Steve Townsend 為 Sinclair Spectrum 上的 Checkered Flag 遊戲設計引擎時，他選擇用查表來連結檔位、速度與引擎轉速，而不是使用固定公式。操控方式的每次改變都會需要重新計算，而在沒有浮點運算硬體的 3.5 MHz 處理器上，這是非常昂貴的操作。
但如果你真的想體會查表有多強大，只要想想你正在使用的檔案系統——它本質上就是一組精密的查表。
查表非常靈活，可以用各種方式實作。如果需要，你甚至可以套用關聯式資料庫的任何設計方法。透過自行撰寫搜尋常式，你可以定義自己想要的查表存取方式，例如透過字串比對，或尋找最接近某個值的近似值。唯一的限制就是你的想像力。
案例一：錯誤處理器
本文的共同作者之一 Hans Bezemer 曾被一位朋友找上，遇到一個不尋常的問題。他的朋友受一家公司委託，要找出其最重要的一套應用程式中某些錯誤訊息的來源。
原本開發該應用程式的公司早已倒閉。系統管理員檢查了應用程式的主要原始碼，卻找不到這些訊息。不久後，他的朋友成功追蹤到這些訊息來自某個函式庫，事情似乎就此告一段落。
接著，他們請他進一步設計一套機制，以避免類似問題再次發生。但無論他提出什麼樣的說明文件方案，都無法通過規格要求。
最後，他們共同擬出了一套終獲採用的方案。與其讓每位程式設計師各自用自己的方式處理錯誤，不如設計一組集中管理的表格。所有錯誤訊息都必須透過一個錯誤處理器來傳遞，其定義如下：
error-handler ( c-addr u n1 n2 n3 -- )
\ c-addr u additional information
\ nl routine number
\ n2 error number
\ n3 severity常式編號是對應到一張集中管理的表格的索引，格式如下：
| 常式編號 | (CELL) |
| 常式名稱 | (STRING) |
錯誤編號則是對應到另一張集中管理的表格的索引，格式如下：
| 錯誤編號 | (CELL) |
| 訊息 | (STRING) |
嚴重程度表示錯誤的嚴重等級，共有五種不同的值：
| 致命 | (終止程式) |
| 錯誤 | (繼續執行，但輸出結果存疑) |
| 警告 | (注意，將嘗試復原) |
| 資訊 | (僅發布使用者資訊) |
| 除錯 | (除錯資訊) |
當然，數字本身沒什麼助記效果，因此加入了 CONSTANT 來盡量減少人為錯誤，例如：
0 CONSTANT S_DEBUG
1 CONSTANT S_INFO
2 CONSTANT S_WARN
3 CONSTANT S_ERROR
4 CONSTANT S_FATAL
0 CONSTANT E_SOUTOFRANGE
1 CONSTANT E_EOUTOFRANGE
2 CONSTANT E ROUTOFRANGE
3 CONSTANT E_NODATA
4 CONSTANT E_ENDOFILE
( etc.)
0 CONSTANT R_DATAENTRY
1 CONSTANT R_PROCESS
( etc.)使用錯誤處理器是強制性的，不過允許附帶一個包含額外資訊的字串。圖一展示了錯誤處理器的典型用法。
圖一 集中式錯誤處理器的典型用法
: process ( c-addr u -- n)
over over \ duplicate filename
file-status 0= \ check file status
if \ if ok; process the data
drop drop \ discard filename
S" None" R_PROCESS E_DATAOK S_INFO error-handler
( other code)
else \ if not ok; issue error
R_PROCESS E_NODATA S_FATAL error-handler
-1 \ return dummy value
then
;錯誤處理器做了幾件事。首先，它會檢查錯誤、常式與嚴重程度等值的有效性。其次，它會將嚴重等級與訊息等級進行比對，若嚴重等級等於或高於訊息等級，就會發出訊息。第三，它會將嚴重等級與中止等級進行比對，若嚴重等級等於或高於中止等級，程式就會終止。
從那天起，任何想與這家公司合作的軟體開發者都必須遵守這套機制。事實證明它非常簡單，大部分的品質保證工作甚至可以由他們自己的系統管理員來完成（我們得坦白說，在那個環境中，Forth 並不是首選語言）。
請注意，程式會回傳一個虛擬值。原因有二。首先，原本的 C 編譯器在省略回傳值時會發出警告。我們不喜歡警告，因為你永遠不知道它是否代表真正的錯誤。其次，如果某位聰明的程式設計師找到了修正錯誤的方法，並把嚴重程度從「致命」改為「錯誤」，就會產生模稜兩可的狀況。在 Forth 中，這可能會導致堆疊下溢，或更糟，引入一個難以尋找的臭蟲。
案例二：For32 反組譯器
另一位共同作者 Benjamin Hoyt 最近為他的 For32 系統實作了一個 Forth 反組譯器。他一開始想用一個大型的 CASE 陳述式來實作核心引擎，後來靈光一現，想到用查表來實作或許有其優勢，於是決定試試看。結果他設計出一個簡單的查表，出乎意料地一次就成功了！
他使用的表格基本上是一個二維陣列，第一個欄位放「特殊情況」的執行權杖（execution token）——例如 (LIT)、(S")、(TO) 等等，還有很多——第二個欄位則是對應的反組譯詞。為了讓你更清楚，圖二提供了其定義。
圖二 基於查表的反組譯器
-1 constant EOT \ end of table delimiter
( search table for x, if found return corresp. value and true flag)
: search-table ( x table -- value true | x false )
begin dup @ EOT = \ is it end of table?
if drop false exit \ no match found
then 2dup @ <> \ compare x with value in table
while [ 2 cells ] literal + \ move to next table entry
repeat nip cell+ @ true ; \ fetch corresponding value如你所見，真的非常簡單。當然，每個查表都需要自己的搜尋常式。如果你不想自己寫，我們稍後會提供一個通用的定義。別忘了，在許多（符合 ANS 標準的）系統上，甚至根本沒有提供 CASE。如果你必須自己實作 CASE，聽我們一句勸，自己寫個搜尋常式吧。那可比開發一整套 CASE 機制簡單多了。
除此之外，每一組 OF … ENDOF 就至少包含一個字面值、一次比較和兩次跳躍。在某些系統上，每組 OF … ENDOF 可能會佔到 40 個位元組。而查表中一個類似的項目只需要 8 個位元組。舉例來說，使用 CASE 的 For32 反組譯器與使用查表的版本之間就相差了 1.5 Kb。
另一個不該使用 CASE 的好理由是，它常常無法做到你想要的效果。CASE 只能比較整數。如果你還沒被說服，請記得查表通常更快。
有些 C 編譯器（如 R$/6000 上的 XL C）會用一長串跳躍與比較指令來實作 select() 陳述式。這相當耗時，尤其當項目清單有一定規模時。使用查表時，搜尋是在一個集中的執行範圍內完成，速度的提升會非常明顯。
陷阱
查表那種微妙的優雅或許你現在已經明白了，但陷阱在哪裡呢？為什麼這麼少 Forth 程式設計師使用它？問得好，因為實際上，你確實可能會遇到一兩個麻煩。
舉例來說，就拿前面提到的字串比對為例。假設你要寫一個巨集指令處理器，你決定用查表來實作。你已經寫好了字串比對的查表常式，然後用 ," 來建立表格。這個詞雖然不是 ANS Forth 標準的一部分，但在許多 Forth 系統中都有提供。
create command-table ( -- table )
," display" ' do-display ,
," end" ' do-end ,
," save" ' do-save ,
," load" ' do-load ,
EOT ,但你很快就發現自己太過草率。字串長度不一，你遇到了對齊問題，整個設計還得靠一個複雜又緩慢的搜尋常式來支撐。這個問題有幾種解法，其中最簡單的就是使用固定長度的字串，像這樣：
create command-table ( -- table )
," display" ' do-display ,
," end " ' do-end ,
," save " ' do-save ,
," load " ' do-load ,
EOT ,這樣做能簡化並加快速度，在某些情況下或許可行。但長短字串組合所浪費的空間怎麼辦？你可以先定義好字串，取得它們的位址，再編譯到表格中對應的欄位來解決這個問題。但那樣寫起來會相當難看：
: push-address
c" load"
c" save"
c" end"
c" display"
;
push-address
create command-table ( -- table )
, ' do-display ,
, ' do-end ,
, ' do-save ,
, ' do-load ,
EOT ,另一種解法是寫一個名叫 M" 的定義。它會解析一個字串並將其編譯到字典中，同時在堆疊上留下其位址。然後你就可以把這些位址逐一用「逗號」編進查表中。（見圖三。）
圖三 M" 作法
\ string compiling suite )
( c-addr u dest -- )
: place 2dup 2>r char+ swap chars move 2r> c! ;
( c-addr u -- )
: name, here over 1+ chars allot place ;
( "ccc<quote>" -- c-addr )
: m" align here [char] " parse name, ;
( table of macro commands )
m" display"
m" end"
m" save"
m" load"
( the addresses are all on the stack now, in reverse order)
create command-table ( -- table )
, ' do-load ,
, ' do-save ,
, ' do-end ,
, ' do-display ,
EOT ,
( search table for string c-addr u)
( give xt true if found else c-addr u false)
: string-search ( c-addr u table -- xt true | c-addr u false )
begin dup @ EOT = \ is it end of table?
if drop false exit \ no match found
then dup 2over rot @ count compare \ compare with c-addr u
while [ 2 cells] literal + \ move to next table entry
repeat nip nip cell+ @ true ; \ fetch xt from column 2如果只有少數幾個項目要編譯，這樣做或許可行，但當你有數十個項目時，維護起來就會變得很困難。問題在於，," 會當場編譯字串，S" 在直譯模式下只會暫時存放字串，而 C" 則完全缺乏直譯語意。你或許會再嘗試另一種寫法，得到像這樣的東西：
: display-s c" display" ;
: end-s c" end" ;
: save-s c" save" ;
: load-s c" load" ;
create command-table ( -- table )
display-s , ' do-display ,
end-s , ' do-end ,
save-s , ' do-save ,
load-s , ' do-load ,
EOT ,好吧，這樣也能運作，稍微費點事也能維護，但浪費了那麼多標頭，感覺實在不太好。讓我們看看能不能改善這一點。
解法與實作
4tH 編譯器是一個非常不同的 Forth 編譯器。有人甚至認為它根本不算 Forth 編譯器。在此脈絡下，我們認為這是個學術性的爭論。
重要的是，4tH 提供了一種簡易的方式來定義查表，它為字串和整數提供了不同的區段，而且不區分編譯與直譯語意。在 ANS Forth 中，也有幾種方式可以實作類似的功能。
你可以嘗試實作 LMI Forth 的解法。這個編譯器有一個名為 " 的詞，其行為大致類似具有直譯語意的 C"。在直譯時，它會使用環形緩衝區。麻煩的是，你永遠不知道系統何時會繞回起點。
另一種權宜之計是自行用 ALLOT 配置字串空間，並把字串編譯到那裡。陷阱在於，你的環境會受到所配置字串空間大小的限制。一旦字串空間用完，就必須重新啟動系統。這是 Wil Baden 提出的解法之一（圖四）。
圖四 Wil Baden 的解法
( Reserve STRING-SPACE in data-space. )
2000 CONSTANT /STRING-SPACE
CREATE STRING-SPACE /STRING-SPACE CHARS ALLOT
VARIABLE NEXT-STRING 0 NEXT-STRING !
( caddr n addr -- )
: PLACE 2DUP 2>R CHAR+ SWAP CHARS MOVE 2R> C! ;
( "ccc<quote>" -- caddr )
: STRING" [CHAR] " PARSE
DUP 1+ NEXT-STRING @ + /STRING-SPACE >
ABORT" String Space Exhausted. "
STRING-SPACE NEXT-STRING @ CHARS + >R
DUP 1+ NEXT-STRING +!
R@ PLACE
R>
;
CREATE months
STRING" January" , 31 ,
STRING" February" , 28 ,
STRING" March" , 31 ,
STRING" April" , 30 ,
STRING" May" , 31 ,
STRING" June" , 30 ,
STRING" July" , 31 ,
STRING" August" , 31 ,
STRING" September" , 30 ,
STRING" October" , 31 ,
STRING" November" , 30 ,
STRING" December" , 31 ,
: .Month 1- 2* CELLS months + @ COUNT TYPE SPACE ;要解決字串空間有限的問題有幾種方式。重新定義 /STRING-SPACE 是一種可能。一個顯而易見的方法是在動態記憶體中配置字串空間，並在需要時重新配置。但重新配置可能會使先前已編譯的所有位址失效，這絕對不是我們想要的。
另一種巧妙運用動態記憶體的方式來自 Marcel Hendrix。他將每個字串個別配置在動態記憶體中，如前述冒險遊戲中所展示的那樣。
解法有很多，請選擇最適合你的那一種。
不過，搜尋常式的問題依然存在。為了方便起見，我們提供一個幾乎可在任何 Forth 系統上實作的通用解法。至於字串部分，你得自行創造解法或使用我們提供的其中一種（圖五）。
圖五 通用解法
\ : th cells + ;
0 Constant NULL
create MonthTable
1 , " January " , 31 ,
2 , " February " , 28 ,
3 , " March " , 31 ,
4 , " April " , 30 ,
5 , " May " , 31 ,
6 , " June " , 30 ,
7 , " July " , 31 ,
8 , " August " , 31 ,
9 , " September" , 30 ,
10 , " October " , 31 ,
11 , " November " , 30 ,
12 , " December " , 31 ,
NULL ,
\ Generic table-search routine
\ Parameters: n1 = cell value to search
\ a1 = address of table
\ n2 = number of fields in table
\ n3 = number of field to return
\ Returns: n4 = value of field
f = true flag if found
: Search-Table ( n1 a1 n2 n3 -- n4 f )
swap >r ( n1 a1 n3 )
rot rot ( n3 n1 a1 )
over over ( n3 n1 a1 n1 a1 )
0 ( n3 n1 a1 n1 a1 n2 )
begin ( n3 n1 a1 n1 a1 n2)
swap over ( n3 n1 a1 n1 n2 a1 n2)
th ( n3 n1 a1 n1 n2 a2)
@ dup ( n3 n1 a1 n1 n2 n3 n3)
0> >r ( n3 n1 a1 n1 n2 n3)
rot <> ( n3 n1 a1 n2 f)
r@ and ( n3 n1 a1 n2 f)
while ( n3 n1 a1 n2)
r> drop ( n3 n1 a1 n2)
r@ + ( n3 n1 a1 n2+2)
>r over over ( n3 n1 a1 n1 a1)
r> ( n3 n1 a1 n1 a1 n2+2)
repeat ( n3 n1 a1 n2)
r@ if
>r rot r> ( nl a1 n3 n2)
+ th @ ( n1 n4)
swap drop ( n3)
else
drop drop drop ( n1)
then
r> ( n f)
r> drop ( n f)
;
: Search-Month ( n --)
MonthTable 3 2 Search-Table
if
.
else
drop ." Not Found"
then cr
;我們甚至可以更進一步，定義一個名為 TABLE 的詞，它會用 CREATE 建立一個查表，當該表被執行時，會自動搜尋自身並回傳所需的值：
( create search table called "name")
( when executed, searches its table for x)
( returning the table value and true if)
( found, else x and false )
: table ( "name" -- ) create
does> ( x -- value true | x false )
search-table ;你可以針對不同種類的查表，用不同的搜尋方式實作不同的版本。這讓你能夠非常快速地打造出強大的應用程式。別忘了，這正是使用 Forth 所享有的特權之一！
後記
你是否曾想過用查表來實作 Forth 字典，甚至是整個 Forth 系統？我們敢說這絕對做得到！事實上，整個 4tH 編譯器就是圍繞著四張不同的查表所建構的。
查表讓你能夠打造快速、精簡且易於維護的應用程式。在我們看來，這個方法在 Forth 中尚未被廣泛使用，部分原因是過去缺乏支援它的工具。我們希望本文提供的素材已足夠為你帶來一些新點子，並讓你能立刻動手嘗試。
Benjamin Hoyt 是一名高中生，熱愛以寫程式為嗜好。在接觸 Forth 之前，他曾用 80x86 組合語言嘗試繪圖與 AdLib 程式設計。一年多前，他打造了自己的第一個 Forth 編譯器，從此便忠於這個語言。目前他正在使用並開發一套名為 For32、執行於 MS-DOS 上的 ANS Forth。另一個他目前的主要專案是 For16，一套精簡且符合 ANS 標準、執行於 MS-DOS 上的 Forth 編譯器。
Hans「the Beez」Bezemer 自 1980 年代中期以來便開始使用 Forth 與 C。他是多套共享軟體及免費的 4tH 編譯器的作者。4tH 可於 ftp.taygeta.com 取得。
留言
登入後參與討論