这篇文章是我 16 岁时与 Hans Bezemer 合著的，发表于《Forth Dimensions》1997 年 9 月号——由 Forth Interest Group 主办的 Forth 编程杂志。Hans 是名为“4tH”的 Forth 编译器的作者，他帮我润色了文字，也稍稍收敛了我那股狂热 Forth 信徒的语气。我记得案例研究二和陷阱这两节是我写的。参见原版 PDF。

想进一步了解 Forth，请先阅读维基百科条目，然后阅读《Thinking Forth》。

“就我个人而言，我认为 case 语句是对一个方向错误的问题给出的优雅解法：试图用算法去表达本该用决策表来描述的东西。”

——Leo Brodie，《Thinking Forth》

引言

如果你以为本文又要挑起一场关于老争议的新讨论，那就大错特错了。相反，我们将介绍一种利用简单概念——查找表——来解决问题的全新思路。

随便翻看几个 Forth 程序，你会发现除了偶尔出现的星期表之外，这种技巧几乎无人使用。这实在可惜，因为使用查找表的程序更易于设计、调试和维护，而且通常更小、运行更快。我们会举几个例子来说明这一点。

查找表之所以少见，一个可能的原因是在 Forth 中实现起来并不容易——尤其涉及字符串时。本文也会就此提供几种可行的解决方案。

有人可能会说，OOF 或其他非标准扩展提供了处理这类问题的更好方法。然而，ANS Forth 既非面向对象，也（目前）没有结构体扩展，我们认为这一讨论超出了本文的范围。

什么是查找表？

查找表无非是一组具有共同特征的对象集合。使用查找表，意味着要审视程序中所用到的对象，思考它们共享哪些特征、又有哪些不同。

文字冒险游戏就是一个很好的例子。每个房间都有各自的描述和出口，有些出口在满足特定条件前是隐藏的。房间里还有物品，所有物品都有描述，有些可以移动，有些则不行，有些在特定条件未满足时会触发动作。

这正是应该使用查找表的典型应用。任何其他实现方式都必然笨拙、难以调试、无法维护。一个使用查找表的冒险游戏示例可在 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

例程编号是集中维护的表格的索引，格式如下：

错误编号是另一张集中维护表格的索引，格式如下：

严重级别用于表示错误的严重程度，共有五档：

当然，数字本身没什么助记性，因此加入了若干 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 语句来实现核心引擎，随后灵光一现，意识到用查找表或许更有优势，于是决定一试。他设计了一张简单的查找表，出乎意料地一次就成功了！

他所用的表本质上是一个二维数组，第一列存放“特殊情况”的执行令牌——例如 (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 至少包含一个字面量、一次比较和两次跳转。在某些系统上，每对要占用多达 40 字节，而查找表中类似的一项只需 8 字节。例如，For32 反编译器使用 CASE 与使用查找表的版本相差 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 的 ANS Forth，运行于 MS-DOS 之上。当前他的另一项主要工程是 For16——一个小巧、符合 ANS 标准的 Forth 编译器，同样运行于 MS-DOS。

Hans “the Beez” Bezemer 自 1980 年代中期起便使用 Forth 和 C。他是多款共享软件以及免费软件 4tH 编译器的作者。4tH 可在 ftp.taygeta.com 获取。