Forthにおける有限状態機械 (1994年)

Forthにおける有限状態機械 J.V. Noble Institute for Nuclear and Particle Physics University of Virginia Charlottesville, VA 22901 要旨 このノートでは、Forthで決定性および非決定性有限オートマトンを構築する方法を提供します。「最良の」方法は、オートマトンの定義と状態テーブルの間に1対1の関係を生み出します。この技術の重要な特徴は、（遅い）ネストされたIF句が存在しないことです。 はじめに 特定のプログラミング問題は、構造化されたコードを使用しても手続き的に解決するのが困難ですが、抽象的な有限状態機械（FSM）[1]を使用すると簡単に解決できます。たとえば、コンパイラは、浮動小数点数を表すテキスト文字列と、同様の文字が同様の順序で含まれる可能性のある代数式を区別する必要があります。あるいは、機械コントローラーは、ランダムな順序で発生する事前に決定された入力に対する応答を選択する必要があります。このような問題は、無限の入力に応答するプログラムは、単なる逐次プログラムよりも「思考する機械」に近いという点で興味深いものです。したがって、浮動小数点数を表す文字列は一連の規則によって定義されます。その長さは決まっておらず、シンボルが現れる順序も決まっていません。さらに悪いことに、同じ数値に対して複数の形式が許可される場合があります。ユーザーフレンドリーさは、ある程度のフォーマットの柔軟性を要求します。一般的なパターン認識は論理式（つまり、十分な数のIF、ELSE、THENを連結すること）を通じて実装できますが、結果として得られるコードは一般に読みにくく、デバッグや変更が困難です。さらに悪いことに、このアプローチは、コードがどれほど「きれいに」レイアウトされていても、構造化されていません。インデントはそれほど効果がありません。そして、主に論理式で構成されるプログラムは、多くのプロセッサが分岐時にパイプラインをダンプするため、遅くなる可能性があります[2]。ネストされたIFアプローチのこれらの欠点は、それを克服するための市販ツールの豊富さによって証明されています。Stirling CastleのLogic Gem（論理式を変換および単純化する）、Matrix SoftwareのMatrix Layout（FSMの表形式表現をBASIC、Modula-2、Pascal、またはCなどの複数の言語のいずれかに変換する）、またはAYECO, Inc.のCOMPEDITOR（同様の変換を実行する）です。[これらのCASEツールは、少なくとも1993年まではThe Programmer's Shopやその他の開発者向けソフトウェアディスカウンターから入手可能でした。] Forthは、FSMを生成するための自然で読みやすい方法を奨励する、特に構造化された言語です。このノートでは、いくつかの高レベルなForth実装について説明します。有限状態機械は、以前にもこのジャーナルで議論されています[3]、[4]。現在の方法は、以前の方法を改善するものです。 簡単な例 キーボードから数値入力を受け付けるタスクを考えてみましょう。非友好的なプログラムは、ユーザーが数値をすべて入力してから、最初の桁の後に小数点 (.) が2つあることを通知します。対照的に、友好的なプログラムは、不正な文字を認識または表示することを拒否します。代わりに、有効な文字またはキャリッジリターン（入力の終了を示す）を待ちます。バックトラッキングを許可し、不正な入力を消去できるようにします。例を小さく保つために、私たちの数値入力ルーチンは、べき乗（FORTRANの用語では固定小数点）なしで符号付き10進数を許可します。小数点、数字、および先頭のマイナス記号は有効ですが、それ以外のASCII文字（スペースを含む）は認識されません。有効な数値の例を次に示します。0.123、.123、1.23、-1.23、123など。これらの例から、次の規則を導き出します。0-9、-、および.以外の文字は無効です。数字0-9は有効です。最初の文字は-、0-9、または小数点にすることができます。最初の文字の後、-は無効です。最初の小数点の後、小数点が無効です。従来のプロシージャルアプローチは次のようになります。 VARIABLE PREVIOUS.MINUS? VARIABLE PREVIOUS.DP? : DIGIT? ( c -- f ) ASCII 0 ASCII 9 WITHIN ; : DP? ( c -- f ) ASCII . = ; : MINUS? ( c -- f ) ASCII - = ; : FIRST.MINUS? MINUS? PREVIOUS.MINUS? @ NOT AND ; : FIRST.DP? DP? PREVIOUS.DP? @ NOT AND ; : LEGAL? ( c -- f ) DUP DIGIT? IF DROP TRUE DUP PREVIOUS.MINUS? ! ELSE DUP FIRST.MINUS? IF DROP TRUE DUP PREVIOUS.MINUS? ! ELSE FIRST.DP? IF TRUE DUP PREVIOUS.DP? ! ELSE FALSE THEN THEN THEN ; 作業を行う単語は（アステリックスの作者であるUderzoとGoscinnyに敬意を表して）次のようになります。 : Getafix FALSE PREVIOUS.MINUS? ! FALSE PREVIOUS.DP? ! BEGIN KEY DUP CR WHILE LEGAL? IF DUP ECHO APPEND THEN REPEAT ; この例（ほぼすべての言語で公開されているコードに頻繁に登場する類似例）がなぜひどいのでしょうか？各文字の合法性は時間依存性があり、履歴セマフォが必要です。したがって、単語LEGAL?のロジックが、部分的なファクタリングと論理演算による単純化にもかかわらず、実際には間違っていることを検査で判断するのは困難です。 FORTH有限状態機械 FSMアプローチは、真偽値の履歴セマフォを1つの状態変数に置き換えます。規則は状態テーブルに具体化でき、各可能な入力に対する応答を、具体的なアクションと状態遷移として表現します。これは、以下の図1に示されています。 入力: OTHER? DIGIT? MINUS? DP? 状態 遷移 アクション 遷移 アクション 遷移 アクション 遷移 アクション 0 X -> 0 E -> 1 E -> 1 E -> 2 1 X -> 1 E -> 1 X -> 1 E -> 2 2 X -> 2 E -> 2 X -> 2 X -> 2 図1 固定小数点数の規則を要約した状態テーブル。Eは「エコー」（CRTへの出力）を意味し、Xは「何もしない」を意味します。 状態テーブルでは、 「その他の」文字の無効性は、均一なアクションXと状態遷移の欠如によって表現されます。最初の文字の特別なステータスは、受け入れ可能なすべての文字が初期状態（0）からの遷移を引き起こすという事実によって表現されます。初期の-記号または数字は状態1に移行し、そこでは-記号は受け入れられません。小数点はいずれもシステムを状態2に移行させ、そこでは小数点を受け入れません。一部のFSMはBEGIN...WHILE...REPEATまたはBEGIN...UNTILループで合成できますが、キーボード入力はこのアプローチには容易に適合しません。ここでは、図1の状態テーブルをForth FSMとして3つの実装を検討します。 総当たりFSM 「総当たり」FSMは、Eaker CASEステートメントを使用します。元の形式[5]またはHS/FORTH[6]の単純化された構造を使用します。HS/FORTHは、定義語CASE: ;CASEを提供し、その子語は定義内で複数の語のいずれか1つを実行します。たとえば、CASE: CHOICE WORD0 WORD1 WORD2 WORD3 ... WORDn ;CASE 3 CHOICE （WORD3を実行する）ok HS/FORTHのCASE: ... ;CASEは、語自体を実行する相対的な実行時速度ペナルティはほとんどありません。さて、CASE: ... ;CASEを使用してFSMを実装するにはどうすればよいでしょうか？まず、0、1、2の値を取ることができる状態変数（0に初期化される）が必要です。入力文字が数字、マイナス記号、小数点、または「その他」であるかどうかをテストするために、次のように定義します。 [注：ANSI標準[7]はASCIIをCHARに、UNDERをTUCKに改名しています。また、DDUPはHS/FORTH固有であり、ANSI準拠のために2DUPに置き換える必要があります。ここで使用されているWITHINは、a <= n <= bの場合にTRUEを返しますが、これはANS仕様とは異なります。これらの注意点は、特に断りがない限り、ここおよび以下に適用されます。] VARIABLE mystate mystate 0! : WITHIN ( n a b -- f) DDUP MIN -ROT MAX ROT UNDER MIN -ROT MAX = ; : DIGIT? ( c -- f ) ASCII 0 ASCII 9 WITHIN ; : DP? ( c -- f ) ASCII . = ; : MINUS? ( c -- f ) ASCII - = ; 次に、CASE: ;CASEを使用するために、各状態でのテストを処理する3つの単語を定義します。 : (0) ( char -- ) DUP DIGIT? OVER MINUS? OR IF EMIT 1 mystate ! ELSE DUP DP? IF EMIT 2 mystate ! ELSE DROP THEN THEN ; : (1) ( char -- ) DUP DIGIT? IF EMIT 1 mystate ! ELSE DUP MINUS? IF 1 mystate ! ELSE DUP DP? IF EMIT 2 mystate ! ELSE DROP THEN THEN THEN ; : (2) ( char -- ) DUP DIGIT? IF EMIT ELSE DROP THEN ; 最後に、上記を使用する単語を定義します。 CASE: <Fixed.Pt#> (0) (1) (2) ;CASE : Getafix 0 mystate ! BEGIN KEY DUP 13 not CR ? WHILE mystate @ <Fixed.Pt#> REPEAT ; より良いFSM While the a