ルックアップテーブル（Forth Dimensions XIX.3）
原文は Ben Hoyt により に公開されました。 このブログを購読する
これは私が16歳のときにハンス・ベーゼマー（Hans Bezemer）と共著した記事です。この記事は、Forth Interest Groupが発行するForthプログラミング雑誌『Forth Dimensions』の1997年9月号に掲載されました。「4tH」というForthコンパイラの作者であるハンスは、私の文章を磨き、熱心すぎるForth信者的な語り口を少し和らげるのを手伝ってくれました。ケーススタディIIと落とし穴の章は私が書いたと思います。オリジナルのPDFをご覧ください。
Forthについてもっと知りたい方は、Wikipediaの記事を読んでからThinking Forthを読んでみてください。
「個人的には、case文は見当違いの問題に対するエレガントな解決策だと考えている。つまり、本来は決定表（ディシジョンテーブル）で記述するのがより適切なものを、無理にアルゴリズムで表現しようとしているのだ。」
—レオ・ブロディ（Leo Brodie）、Thinking Forth
はじめに
この記事が古くからの論争について新たな議論を始めると思ったなら、大間違いだ。そうではなく、私たちはルックアップテーブルというシンプルな概念を使って、問題を解決する新しい方法を提示する。
手当たり次第にいくつかのForthプログラムを調べてみると、たまに見かける曜日テーブルなどを除けば、このテクニックはほとんど使われていないことがわかる。残念なことだ。ルックアップテーブルを使ったプログラムは、設計もデバッグも保守も容易になるからだ。さらに、通常はサイズが小さく、実行も速くなる。いくつかの例を挙げて、この点を説明しよう。
あまり使われていない理由の一つとして、Forthではルックアップテーブルの実装が難しいこと、特に文字列を扱う場合に難しいことが考えられる。この記事では、その問題に対するいくつかの解決策も提示する。
OOFやその他の非標準の拡張機能の方が、こうした問題を扱うのにより優れた方法を提供すると主張する人もいるかもしれない。しかし、ANS Forthはオブジェクト指向ではないし、（今のところ）Structure拡張も存在しない。その議論は本記事の範囲外と考える。
ルックアップテーブルとは何か
ルックアップテーブルとは、共通の特徴を持つオブジェクトの集まりに過ぎない。これを使うということは、プログラム内で使われるオブジェクトと、それらが共有する（あるいは共有しない）特徴について考える必要があるということだ。
アドベンチャーゲームは良い例だ。各部屋にはそれぞれ説明と出口がある。一部の出口は、ある条件が満たされるまで隠されている場合がある。部屋の中にはオブジェクトがある。すべてのオブジェクトには説明がある。動かせるものもあれば、そうでないものもある。特定の条件が満たされないときに何らかのアクションを実行するものもある。
これはまさにルックアップテーブルを使うべきアプリケーションの好例だ。他の方法で実装すれば、間違いなく不器用で、デバッグが困難で、保守も不可能になるだろう。ルックアップテーブルを使ったアドベンチャーゲームの例は、http://www.IAEhv.nl/users/mhx/adventur.frt［復元版はWayback Machineのおかげ］で見ることができる。このアドベンチャーゲームは元々4tH向けに設計され、マルセル・ヘンドリックス（Marcel Hendrix）によって巧みにANS Forthへ移植された。
なぜルックアップテーブルなのか
ルックアップテーブルの利用は、特定の言語や特定の問題に限られるものではない。私たちはExcelのスプレッドシートでさえ、ルックアップテーブルをうまく活用したことがある。これにより、大量のデータに対する手作業での操作やチェックの回数を大幅に減らすことができた。
あるシートのデータはルックアップテーブルと照合され、未知の値が見つかると自動的に「利用不可」エラーが生成される。別のルックアップテーブルで適切なカテゴリを検索し、その後シート全体をソートすることで、小計を簡単に作成できる。それ以前は、すべてのチェックとソートが手作業で行われ、ミスが起こりやすかった。
しかし、ルックアップテーブルは他の場面でも役立つ。Z80プロセッサは高速なプロセッサではない。1980年代半ばの基準でさえそうだ。そのため、PSIONのスティーブ・タウンゼンド（Steve Townsend）がCheckered Flagゲーム（Sinclair Spectrum版）のエンジンを設計した際、彼は決まった計算式ではなく、ギア、速度、エンジン回転数を結びつけるためにルックアップテーブルを使った。操作を変えるたびに再計算が必要になるが、それは浮動小数点ハードウェアを持たない3.5MHzのプロセッサでは非常にコストの高い処理だからだ。
ルックアップテーブルがどれほど強力かを本当に理解したいなら、自分が使っているファイルシステムが、洗練されたルックアップテーブルの集合に過ぎないことを思い出してほしい。
ルックアップテーブルは非常に柔軟で、さまざまな方法で実装できる。必要であれば、リレーショナルデータベースの設計手法をそのまま適用することさえできる。独自の検索ルーチンを作れば、文字列を比較したり、ある値に最も近い近似値を見つけたりといった、自分好みのアクセス方法を定義できる。限界はあなた自身の想像力だけだ。
ケーススタディI：エラーハンドラ
本記事の共著者の一人であるハンス・ベーゼマーは、ある友人から風変わりな問題について相談を受けた。その友人は、ある企業で最も重要視されているアプリケーションの一つから出るエラーメッセージの発生源を探すために雇われていた。
そのアプリケーションを元々開発した会社はとっくに倒産していた。システム管理者はアプリケーションのメインのソースを調べたが、これらのメッセージを見つけることができなかった。しばらくして、友人はそのメッセージがライブラリに由来することを突き止め、それで一件落着かと思われた。
その後、彼には後続の作業として、この種の問題を防ぐための何らかの仕組みを設計するよう依頼があった。しかし、彼がどんな文書化の仕組みを考えても、仕様を満たすことができなかった。
二人は協力して、最終的に受け入れられる仕組みを作り上げた。各プログラマにエラーを自分のやり方で処理する自由を与えるのではなく、集中的に管理される一連のテーブルを設計したのだ。すべてのエラーメッセージは、次のような定義を持つエラーハンドラを経由しなければならなかった。
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) |
重大度（severity）は、エラーがどれほど深刻かを示すものだった。次の5つの値のいずれかを取る。
| Fatal | (プログラムを中断) |
| Error | (続行するが、出力は疑わしい) |
| Warning | (注意、リカバリを試みる) |
| Info | (単なるユーザー向け情報の発行) |
| Debug | (デバッグ情報) |
もちろん、数字だけでは覚えにくいので、ヒューマンエラーの可能性を最小限に抑えるために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.)エラーハンドラの使用は必須だったが、追加情報を含む文字列を添えることは許されていた。図1に、エラーハンドラの典型的な使用例を示す。
図1. 集中管理されたエラーハンドラの典型的な使用例
: 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
;エラーハンドラはいくつかのことを行った。第一に、エラー、ルーチン、重大度の値の妥当性をチェックする。第二に、重大度レベルをメッセージレベルと照合する。重大度レベルがメッセージレベル以上であれば、メッセージが出力される。第三に、重大度レベルを中断（abort）レベルと照合する。重大度レベルが中断レベル以上であれば、プログラムは終了される。
その日から、この会社と取引したいすべてのソフトウェア開発者は、この仕組みに従わなければならなくなった。この仕組みは非常にシンプルであることが証明され、品質保証のほとんどを同社のシステム管理者自身が行えるほどだった（白状すると、Forthはその環境で選ばれた言語ではなかったのだが）。
プログラムがダミーの値を返していることに注意してほしい。理由は二つある。第一に、元のCコンパイラはそれを省略すると警告を出したからだ。私たちは警告が好きではない。本当のエラーを示しているのかどうかわからないからだ。第二に、もし頭の切れるプログラマがエラーを修正する方法を見つけ、重大度を「fatal」から「error」に変更した場合、曖昧な状態が生じるからだ。Forthでは、それがスタックアンダーフローや、さらに悪いことに見つけにくいバグを引き起こす可能性がある。
ケーススタディII：For32デコンパイラ
もう一人の共著者であるベンジャミン・ホイト（Benjamin Hoyt）は、最近自身のFor32システムのためにForthデコンパイラを実装した。彼は当初、メインエンジンを一つの大きなCASE文で実装しようと考えていた。しかし、ルックアップテーブルによる実装には利点があるかもしれないとひらめき、試してみることにした。彼はシンプルなルックアップテーブルを考案したが、驚いたことに一発で動いたのだ。
彼が使ったテーブルは基本的に二次元配列で、最初のフィールドには「特殊ケース」の実行トークン、例えば(LIT)や(S")、(TO)など数多くのものが入り、2番目のフィールドにはデコンパイル用のワードが入る。参考までに、図2にその定義を示す。
図2. ルックアップテーブルを使ったデコンパイラ
-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.5Kbに及ぶ。
CASEを使わない方がよいもう一つの理由は、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"という定義を書くことだ。これは文字列をパースして辞書にコンパイルしつつ、そのアドレスをスタックに残す。そして、これらのアドレスをすべてカンマでテーブルにコンパイルして、ルックアップテーブルを作成する（図3を参照）。
図3. 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）が提案した解決策の一つだ（図4）。
図4. ウィル・ベイデンによる解決策
( 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を再定義するのも一つの方法だ。わかりやすい方法は、文字列領域を動的メモリに確保し、必要に応じて再確保することだ。しかし、再確保すると以前にコンパイルされたすべてのアドレスが無効になる可能性があり、それは決して望むことではない。
動的メモリを使う別の巧妙な方法は、マルセル・ヘンドリックスによるものだ。彼は、先ほど触れたアドベンチャーゲームで示されているように、各文字列を個別に動的メモリに確保する。
解決策は数多くある。自分に最も合ったものを使ってほしい。
それでも、検索ルーチンの問題は残る。便宜のために、事実上すべてのForthシステムで実装できる汎用的な解決策を紹介する。文字列については、自分で解決策を作るか、私たちのもののいずれかを使う必要がある（図5）。
図5. 汎用的な解決策
\ : 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コンパイラ全体は4つの異なるルックアップテーブルを中心に構成されている。
ルックアップテーブルを使えば、高速で、小さく、保守しやすいアプリケーションを構築できる。私たちの見解では、この手法はForthではあまり広く使われてこなかった。その理由の一つは、それをサポートする手段が少なかったことだ。本稿が、あなたに新鮮なアイデアを与え、すぐにでも始められるだけの十分な材料を提供できたことを願っている。
ベンジャミン・ホイトは、プログラミングを趣味とするシックスフォーム（大学進学準備課程）の学生である。Forthに出会う前は、80x86アセンブラでグラフィックスやAdLibのプログラミングを試していた。1年以上前に初めてのForthコンパイラを自作して以来、この言語に忠実であり続けている。現在は、MS-DOS上で動作する自作のANS ForthであるFor32を使い、開発にも取り組んでいる。現在取り組んでいるもう一つの主要なプロジェクトは、MS-DOS上で動作する小型のANS準拠ForthコンパイラであるFor16だ。
ハンス・“ザ・ビーズ”・ベーゼマーは、1980年代半ばからForthとCを使ってきた。いくつかのシェアウェアプログラムと、フリーウェアの4tHコンパイラの作者である。4tHはftp.taygeta.comで入手できる。
コメント
ログインしてコメントする