HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Finite State Machines in Forth (1994) (forth.org)

74 pointsby ofalkaed2 コメント

要約

この記事は、Forthプログラミング言語で有限状態機械(FSM)を実装する方法について論じています。ネストされたIF文を用いた手続き型アプローチの複雑さと遅さを、状態テーブルを用いたFSMアプローチと比較しています。著者は、特に数値入力解析のようなタスクにおいて、従来の方式よりも構造化され効率的な解決策を目指し、ForthでのFSMの実装例をいくつか提示しています。

全文翻訳

Forthにおける有限状態機械

J.V. Noble

Institute for Nuclear and Particle Physics
University of Virginia
Charlottesville, VA 22901

要旨

このノートでは、Forthで決定性および非決定性有限状態オートマトンを構築する方法を提供します。「最良の」方法は、定義とオートマトンの状態テーブルとの間に一対一の関係を生み出します。この技術の重要な特徴は、(遅い)ネストされた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の用語で固定小数点数と呼ばれる、べき乗(power-of-10 exponents)のない符号付き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?  !  \ 数字ならOK、マイナス履歴をリセット
             ELSE  DUP    FIRST.MINUS?
                   IF     DROP   TRUE  DUP   PREVIOUS.MINUS?  !  \ 最初のマイナスならOK、マイナス履歴をセット
                   ELSE   FIRST.DP?
                        IF    TRUE  DUP   PREVIOUS.DP?  !  \ 最初の小数点ならOK、小数点履歴をセット
                        ELSE  FALSE
                        THEN
                   THEN
             THEN  ;

作業を行う単語は(アステリックスの作者であるウデルゾとゴシニーに謝罪して)次のようになります。

: 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!  \ 状態変数を定義し、0で初期化
  : WITHIN   ( n a b -- f) DDUP MIN  -ROT  MAX  ROT
                 UNDER MIN  -ROT MAX  = ;  \ nがaとbの間にあるかテスト
  : 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                            \ キー入力、キャリッジリターンでなければループ
             WHILE   mystate @   <Fixed.Pt#>     \ FSMを実行
             REPEAT  ;
より良いFSM

上記P3.1で概説されたアプローチ(基本的にBerrian[8]によって最近説明された方法)は機能し、バイナリ論理ツリーP2よりもはるかに明確なコードを生成しますが、それでも改善の余地があります。単語(0)、(1)、(2)は不十分にファクタリングされています(入力文字に対して実行されるテストが含まれています)。また、IF...ELSE...THENブランチが含まれています(速度と構造のために避けたい)。最後に、各FSMは多数の子定義から手作業で作成する必要があります。

図1の状態テーブルをプログラムに変換したいと考えています。前の試みは間接的すぎました。各状態は、多くのことを行う独自の単語で表されていました。おそらく、より直接的に変換することで、望ましい単純さを達成できるでしょう。Forthでは、このような変換は定義語を通じて最も自然に行われます。状態テーブルを行列として視覚化すると仮定します。そのセルにはアクション仕様(アドレスまたは実行トークン)が含まれ、列は入力カテゴリを表し、行は状態を表します。入力カテゴリを列番号に変換すると、カテゴリと状態変数の現在の値(行インデックス)が一意のセルアドレスを決定し、その内容は取得して実行できます。

入力を列番号に変換することで、テストは各文字あたり1回実行される単一の単語にファクタリングされます。この単語は、時間のかかる分岐命令を避けるべきです。これにより、すべての決定(どのテーブルセルを実行するか)が決定されるのではなく、計算されるようになります。テスト例の場合、事前定義は次のようになります。

VARIABLE mystate   0 mystate !  \ 状態変数を定義し、0で初期化

: WITHIN   ( n a b -- f) DDUP MIN  -ROT  MAX
             ROT TUCK MIN  -ROT MAX  = ;  \ nがaとbの間にあるかテスト

: DIGIT?  ( n -- f )   ASCII 0  ASCII 9 WITHIN  ;  \ 数字かテスト

: DP?  ASCII .  = ;  \ 小数点かテスト

: MINUS?  ASCII -  = ;  \ マイナスかテスト

そして、入力変換は次のように実行されます。

: cat->col#   ( n -- n')
         DUP   DIGIT?     1 AND                     \ 数字 -> 1
         OVER  MINUS?     2 AND  +                  \ - -> 2
         SWAP  DP?        3 AND  +                  \ . -> 3
   ;                                                \ その他 -> 0

次に、状態テーブルコンパイラを計画する必要があります。一般に、テーブルの各セルに対して、必要なアクションと状態変更を実行するアクション単語を定義します。コンパイル時に、定義語はこれらのアクション単語の実行アドレス(ANS-Forthでは実行トークン[9])の配列をコンパイルします。実行時に、子単語はユーザー指定の列番号とmystateの現在の値から適切な行列セルのアドレスを計算し、その行列セルから実行アドレスを取得して、適切なアクションを実行します。テーブルは任意の数の列を持つことができるため、列の数はコンパイル時に指定する必要があります。これらの要件は、次の定義につながります。

: TUCK       COMPILE UNDER  ;                    \ ANS互換性
: WIDE ;                                        \ 明確さのためのNOOP
: CELLS      COMPILE  2*  ;                      \ ANS互換性
: CELL+      COMPILE  2+  ;                      \ ANS互換性
: PERFORM    COMPILE @   COMPILE EXECUTE  ;       \ エイリアス

: FSM:       ( width -- )  CREATE  ,   ] 
        DOES>  ( n adr -- ) 
               TUCK  @  mystate @  *   +   CELLS   CELL+  + 
               ( adr')  PERFORM  ; 

ここで、CREATEは辞書に新しいヘッダーを作成し、,はスタックの最上位の数値をパラメータフィールドの最初のセルに格納し、]はコンパイルモードに切り替えます。実行時コードは、目的のアクションへのベクトルを含むセルのアドレスを計算し、そのベクトルを取得してアクションを実行します。[注:このシンプルでエレガントな実装は、間接スレッドForthでのみ機能します。ANS標準の代替案が別紙に提供されています。]

次に、この強力な新しい単語を例の問題に適用します。図1から、遷移(状態の変化)はセル(0,0)、(0,1)、(0,2)、(1,0)、および(1,2)でのみ発生することがわかります。これらは常にEMIT(図中のE)に関連付けられています。間違った入力に伴う状態変化はありません。したがって、定義する必要があるのは2つの異なる状態変更アクションのみです。

: (00)   EMIT  1 mystate ! ;  \ エコーして状態1へ遷移

: (02) EMIT 2 mystate ! ;  \ エコーして状態2へ遷移

入力文字に対して4つの条件をテストする必要があるため、状態テーブルは4列幅になります。

4 WIDE FSM: <Fixed.Pt#>   ( action# -- )   
\           other   num    -     .            \ state
             DROP    (00)  (00)  (02)     \ 0
             DROP    (00)  DROP  (02)    \ 1
             DROP    (02)  DROP  DROP  ; \ 2
 

作業を行う単語は次のとおりです。

: Getafix   0 mystate !   BEGIN   KEY   DUP   13 <>   \ キャリッジリターンでない間ループ
         WHILE   DUP   cat->col#   <Fixed.Pt#>     \ 入力カテゴリを計算し、FSMを実行
         REPEAT  ;

次のように、FSMをすぐにテストできます。

FLOAD F:X.1  Loading F:X.1  ok
ASCII 3 cat->col# . 1  ok
ASCII 0 cat->col# . 1  ok
ASCII - cat->col# . 2  ok
ASCII . cat->col# . 3  ok
ASCII A cat->col# . 0  ok

: Getafix   0 mystate !   BEGIN  KEY  DUP  13 <>  WHILE
    DUP   cat->col#   <Fixed.Pt#>   REPEAT  ;  ok
Getafix -3.1415975 ok
Getafix 55.3259 ok

過剰な小数点、不正なマイナス記号、または数値以外の文字の不正な入力は、意図したとおりに画面にエコーされずにドロップされたため、表示されません。

3.3 エレガントなFSM

P3.2の定義語FSM:は有用ですが、改善の余地があります。このバージョンは、子単語のセルにコンパイルされたアクション単語内に状態遷移を隠します。より完全にファクタリングされたアプローチは、各FSMの定義内で、遷移をそれらが続くアクションの隣に明示的に指定します。定義は、各定義が状態テーブルとまったく同じように見えるため、より読みやすくなります。つまり、理想的なFSM定義は次のようになります。

4 WIDE FSM: <Fixed.Pt#>
\ 入力:  |  other?  |  num?   |  minus?  |   dp?     |
\ 状態:  ---------------------------------------------
   ( 0 )     DROP  0    EMIT  1   EMIT  1      EMIT  2
   ( 1 )     DROP  1    EMIT  1   DROP  1     EMIT  2
   ( 2 )     DROP  2    EMIT  2   DROP  2     DROP  2 ;

そのため、(00)および(02)という単語を必要とすることはありません。幸いなことに、遷移を明示的に含めるようにFSM:を再定義することは難しくありません。状態遷移を実行するためにCONSTANTを使用できます。

    0 CONSTANT >0
    1 CONSTANT >1
    2 CONSTANT >2
    .............

そして、FSM:の実行時部分をそれに応じて変更します。

: FSM:   ( width -- )   CREATE  ,  ]   DOES>   ( col# -- ) 
     
    TUCK   @                            ( -- adr col# width )
         mystate @  *  +  2*  CELLS  CELL+  +  ( -- offset )
         DUP   CELL+  PERFORM   mystate !   PERFORM   ; 

ここで、実行時コードは状態変数の変更が実行時アクションの前に行われるように定義されています。場合によっては、望ましいアクションはABORTとエラーメッセージです。状態変数を先に変更すると、各FSMセルに対して個別のエラーハンドラを記述する必要がなくなりますが、ABORTがどこで行われたかを伝えることができます。ABORTが最初の場合、状態は更新されていません。

FSMは次のように定義されます。

4 WIDE FSM: 
\ 入力:  |    other?  |   num?     |    minus?   |    dp?     |
\ 状態:  ------------------------------------------------------
   ( 0 )     DROP >0    EMIT >1   EMIT >1     EMIT >2
   ( 1 )     DROP >1    EMIT >1   DROP >1     EMIT >2
   ( 2 )     DROP >2    EMIT >2   DROP >2     DROP >2 ;

これは明確で読みやすいです。もちろん、FSM:の実行時(DOES>)部分を、追加のCONSTANT >0、>1などを必要としないように定義することもできます。実際には、数値はテーブルに次のように格納できます。

4 WIDE FSM: <Fixed.Pt#>
\ 入力:  |   other?    |   num?    |   minus?   |    dp?     |
\ 状態:  -----------------------------------------------------
   ( 0 )   DROP [ 0 , ]  EMIT [ 1 , ] EMIT [ 1 , ] EMIT [ 2 , ]
   ( 1 )   DROP [ 1 , ]  EMIT [ 1 , ] DROP [ 1 , ] EMIT [ 2 , ]
   ( 2 )   DROP [ 2 , ]  EMIT [ 2 , ] DROP [ 2 , ] DROP [ 2 , ] ;

しかし、§4で述べた理由から、数値リテラルを組み込むよりもCONSTANTを使用して状態遷移を実装する方が良いです。

3.4 これまでの最高のFSM

プログラム作成におけるFSMアプローチの使用経験から、さらに2つの改善が動機付けられました。まず、FSMをネストする必要がある場合、つまり、1つを別のものにコンパイルする場合、あるいは再帰する場合を考えてみましょう。グローバル変数mystateは、そのような洗練を不可能にします。したがって、各FSMの状態変数を、WIDTHと同様に、そのデータ構造に含めることが理にかなっています。この変更は、コストがFSMあたり1つの追加メモリセルであるため、状態が名前を持たない場合、呼び出すことができないため、FSMの状態を偶発的な相互作用から保護します。第二に、アクション単語のいずれか一方がスタックに何かを残すことになっており、何らかの理由で、アクションの後ではなく前(実際には、物事を行うためのより自然な順序)に状態を変更することが望ましいとします。スタック効果がどうなるかを事前に知る方法がないため、衝突を避けるためにリターンスタックを一時ストレージに使用します。したがって、修正は次のようになります。

: 2@     COMPILE  D@  ;           \ エイリアス; D@はANSでOK
: WIDE   0 ; 

: FSM:   ( width 0 -- ) 
      CREATE   ,  ,   ] 
      DOES>               ( col# adr -- ) 
         DUP >R  2@  *  + ( -- col#+width*state ) 
         2*  2+  CELLS    ( -- offset-to-action)
         DUP >R           ( -- offset-to-action)
         PERFORM          ( ? ) 
         R> CELL+         ( -- offset-to-update)
         PERFORM          ( -- state') 
         R> !   ;         \ 状態を更新

例の修正されたキーボード入力単語は次のとおりです。

: Getafix   0  ' <Fixed.Pt#> ! 
            BEGIN   KEY   DUP   13 <>      WHILE 
            DUP   cat->col#  <fixed.pt#>   REPEAT ; 

状態変数はゼロに初期化されます。これは、FSMのパラメータフィールドの最初のセルに格納されており、' <Fixed.Pt#>(または使用中のForth方言の同等物 - 別紙参照)というフレーズでアクセスできることを知っているためです。

4. 非決定性有限状態機械

これで、状態遷移を管理するためにCONSTANTを定義することが、次の状態の数値を単に組み込むよりも優れている理由を説明する準備ができました。まず、状態に番号ではなく名前を付けることに明白な理由はありません。Forthのアウターインタープリタ自体は、COMPILEとINTERPRETの2つの状態を持つ状態機械です。つまり、名前は数値よりも明確であることがよくあります。

数値ではなく単語を使用して遷移を実行すると、より広範な変更が可能になります。私たちのコードは、テーブルの各セルが確定的な次の状態への遷移を含む決定性FSMのコンパイラを定義します。指定されたアクションに従って、複数の次の状態のいずれかに分岐することを許可した場合はどうなりますか?これを行うことができるFSMは非決定性と呼ばれます。命名法にもかかわらず、そして文献[10]で時折見られるそのようなFSMの誤解を招く説明にもかかわらず、次の遷移に関してランダムまたは「推測」のようなものは何も必要ありません。複数の可能性を許可するのは、現在の状態と現在の入力以外の追加情報です。

私のFORmula TRANslator[11]で使用されている簡単な非決定性FSMを次に示します。問題は、FORTRANの規則に従って、テキストの一部が適切な識別子(つまり、変数、サブルーチン、または関数の名前)であるかどうかを判断することです。IDは文字で始まる必要があり、最大7文字までで、文字は文字または数字である必要があります。ASCII文字コードが文字、数字、または「その他」を表すかどうかを判断するプロセスを高速化するために、デコーダー(高速テーブルトランスレータ)を定義します。

: TAB:   ( #bytes -- ) 
           CREATE   HERE  OVER  ALLOT   SWAP  0 FILL  DOES>  +  C@  ; 

そして、それを迅速に埋める方法を定義します。

: install      ( col# adr char.n char.1 -- )   \ 高速フィル
               SWAP 1+ SWAP   DO  DDUP I +  C!  LOOP  DDROP ; 

IDを検出するために必要な変換テーブルは次のとおりです。

128 TAB: [id]
1 ' [id]  ASCII Z  ASCII A  install
1 ' [id]  ASCII z  ASCII a  install
2 ' [id]  ASCII 9  ASCII 0  install

\ F79の規約に従い、' はpfaを返します。F83またはANSに変換するには、' を ' >BODY に置き換えます。

したがって、例えば
    ASCII R  [id] .  1 ok
    ASCII s  [id] .  1 ok
    ASCII 3  [id] .  2 ok
    ASCII +  [id] .  0 ok
    \ ANSIに変換するにはASCIIをCHARに置き換えます

ID規則をFSMにどのように具体化しますか?最初の試みは次のようになります。

3 WIDE FSM: (id)
\ 入力:     |  other  |  letter   |    digit    |
\ 状態      -------------------------------------
   ( 0 )       NOOP >8     1+ >1       NOOP >2
   ( 1 )       NOOP >8     1+ >2       1+   >2
   ( 2 )       NOOP >8     1+ >3       1+   >3
   ( 3 )       NOOP >8     1+ >4       1+   >4
   ( 4 )       NOOP >8     1+ >5       1+   >5
   ( 5 )       NOOP >8     1+ >6       1+   >6
   ( 6 )       NOOP >8     1+ >7       1+   >7
   ( 7 )       NOOP >8   NOOP >8       NOOP >8  ;

: state<     [COMPILE]  '   LITERAL  ; IMMEDIATE
\ FSMの "state" セルへのアドレスをコンパイル
\ F83 または ANS では、' を ' \>BODY に置き換えます

:    ( $end $beg -- f)                  \ f = IDならT、そうでなければF
         0  state< (id) !                   \ 状態を0に初期化
         BEGIN   DUP C@  [id]  (id)         \ FSMを実行
                 DDUP  >                    \ $end > $beg ?
                 state<  (id) @  2 <        \ 終了していないか?
                 AND                        \ フラグを結合
         WHILE   1+                         \ $beg = $beg+1
         REPEAT   DDROP                     \ ループを終了、クリーンアップ
         state< (id)  @  
 8 <  ;            \ フラグを残す

IDが最大7文字であることを確認するために、8つの状態を提供する必要がありました。テーブルは非常に繰り返しが多いです。より簡単な代替案は、変数を使用して、文字が到着するたびにカウントすることです。修正は次のとおりです。

VARIABLE id.len   0 id.len !   \ IDの長さをカウントする変数
: +id.len   id.len  @  1+   id.len  !  ;    \ カウンターをインクリメント

: >1?    id.len @  7 <  DUP  1 AND  SWAP  NOT  2 AND +  ; 
( -- 7文字未満なら1、そうでなければ2)

3 WIDE FSM: (id)
\ 入力:     |  other  |  letter     |    digit    |
\ 状態      ---------------------------------------
   ( 0 )       NOOP >2   +id.len >1    NOOP >2
   ( 1 )       NOOP >2   +id.len >1?   +id.len >1?  ;

:    ( $end $beg -- f)                  \ f = IDなら-1、そうでなければ0
         0 id.len !   0 state< (id) !       \ 初期化
         BEGIN   DUP C@  [id]  (id)         \ FSMを実行
                 DDUP  >                    \ $end > $beg ?
                 state< (id) @  2 <         \ 終了していないか?
                 AND                        \ フラグを結合
         WHILE   1+  REPEAT   DDROP         \ $beg = $beg+1
         state< (id) @   1 =  ;             \ フラグを残す

結果のFSMは非決定性です。なぜなら、単語>1?が状態1または(終端の)状態2への遷移を誘発するからです。状態数が少なく、メモリ消費量も少なくなります。状態遷移を仲介するためにサブルーチンに固執したため、確定的な遷移(>0または>1などのCONSTANT経由)から不確定な遷移への移行は、再定義を必要としません。

次のFSMは、正しく形成された浮動小数点数を検出します。

128 TAB: [fp#]                         \ fp#のデコーダー
1 ' [fp#]  ASCII E  ASCII D  install
1 ' [fp#]  ASCII e  ASCII d  install
2 ' [fp#]  ASCII 9  ASCII 0  install
3 ' [fp#]  ASCII +  +  C!
3 ' [fp#]  ASCII -  +  C!
4 ' [fp#]  ASCII .  +  C!

: #err   CRT       \ 通常の出力を復元
       ." Not a correctly formed fp#" ABORT   ;  \ fp#エラーハンドラ

5 WIDE FSM: (fp#)
\ 入力:     |  other  |   dDeE    
|   digit  | + or -  |    dp    |
\ 状態:     -------------------------------------------------------
   ( 0 )       NOOP >6    NOOP >6     1+  >0    NOOP >6   1+     >1
   ( 1 )       NOOP >6    1+   >2     1+  >1    #err >6   #err   >6
   ( 2 )       NOOP >6    #err >6    NOOP >4    1+   >3   #err   >6
   ( 3 )       NOOP >6    #err >6     1+  >4    #err >6   #err   >6
   ( 4 )       NOOP >6    #err >6     1+  >5    #err >6   #err   >6
   ( 5 )       NOOP >6    #err >6    #err >6    #err >6   #err
   >6 ; 

: skip-  DUP C@  ASCII - =  -  ;            \ 先頭の-をスキップ
\ 環境依存: "true" が -1 であると仮定

: <fp#>   ( $end $beg -- f)
         0 state< (fp#) !                   \ 状態を初期化
         skip-                              \ 先頭の-記号を無視
     1-  BEGIN   1+  DUP C@  [fp#]  (fp#)   \ FSMを実行
                 DDUP  <                    \ $end < $beg ?
                 state< (fp#) @   6 =  OR   \ エラーで終了したか?
         UNTIL   DDROP                
      \ クリーンアップ
         state< (fp#) @   6 <   ;           \ フラグを残す

FSM (fp#) は仮数部の桁数を数えませんが、指数部の桁数を2桁以下に制限します。非決定性バージョンの(fp#)は状態数を減らし、仮数部と指数部の両方の桁数を数えながら、メモリ消費量を削減します。

5 WIDE FSM: (fp#)
\ 入力:     |  other  |   dDeE    |   digit  | + or -  |    dp    |
\ 状態:     -------------------------------------------------------
   ( 0 )       NOOP >4    NOOP >4   +mant >0?   NOOP >4   1+     >1
   ( 1 )       NOOP >4    ?1+  >2   +mant >1?   #err >4   #err   >4
   ( 2 )       NOOP >4    #err >4   +exp  >3    1+   >3   #err   >4
   ( 3 )       NOOP >4    #err >4   +exp  >3?   #err >4   #err   >4  ;

+mant、+exp、?+1、>0?、>1?、>3?という単語の詳細を埋めることは、読者への演習として残されています。

謝辞

ガスパイプライン制御や教育用コンピューターゲームなど、多様な分野でのFSMコンパイラの応用に関する肯定的なフィードバックをRick Van Norman氏とLloyd Prentice氏に感謝します。

別紙

ここでは、HS/FORTHのCASE: ... ;CASE(HS/FORTHのバージョンよりも多くのオーバーヘッドを課しますが)の高レベル定義を示します。これは間接スレッドシステムで機能します。

: CASE:   CREATE  ]   DOES>  ( n -- )  OVER  + +  @  EXECUTE ; 
: ;CASE   [COMPILE] ;   ;  IMMEDIATE   ( または単に ; を使用 )

しかし、これは直接スレッドForth(F-PCなど)では機能しません。これは、直接スレッドシステムで]を使用してコンパイラをオンにしたときに通常コンパイルされるものが実行トークンのリストではないため失敗します。最も簡単な代替案(間接スレッドシステムでも機能します)は、コンパイル機能をCASE:からファクタリングすることです。

: CASE:      CREATE   ;
: |     '  ,  ;                                  \ F83およびANSバージョン
: ;CASE      DOES>  OVER + +  PERFORM  ;         \ エラーチェックなし

使用例を次に示します。

CASE: TEST   | *  | /  | +  | -  ;CASE
3 4 0 TEST .  12 ok
1
2 4 1 TEST .  3 ok
5 7 2 TEST . 12 ok
5 7 3 TEST . -2 ok

CASEステートメントは複数行に拡張できますが、可読性と適切なファクタリングから、そのような定義は短く保つことが推奨されます。

同じ手法を使用して、F-PCおよびその他のF83ベースまたはANS準拠システムで機能するFSM:のバージョンを提供できます。これは、FSM:を試したいが§3.4のバージョンを試すためのHS/FORTHを持っていない人向けです。定義は次のとおりです。

: |     '  ,  ;              \ F83およびAN
Sバージョン
: WIDE   0 ; : FSM:   ( width 0 -- )      CREATE   ,  ,   ;
: ;FSM   DOES>               ( col# adr -- )          DUP >R  2@  *  +
( -- col#+width*state )          2*  2+  CELLS       ( -- offset-to-
action)          DUP >R              ( -- offset-to-action)
         PERFORM             ( ? ) 
         R> CELL+            ( -- ? offset-to-update)
         PERFORM             ( -- ? state')          R> !   ; ( ? ) 
\ 状態を更新

§3.3のFSMは次の形式になります。

4 WIDE FSM: <Fixed.Pt#>
\ 入力:  |    other?  |   num?     |    minus?   |    dp?     |
\ 状態:  ------------------------------------------------------
   ( 0 )  | DROP | >0  | EMIT | >1  | EMIT  | >1  |  EMIT  | >2
   ( 1 )  | DROP | >1  | EMIT | >1  | DROP  | >1  |  EMIT  | >2
   ( 2 )  | DROP | >2  | EMIT | >2  | DROP  | >2  |  DROP  | >2  ;FSM

: state<           '  >BODY   LITERAL  ; IMMEDIATE
: Getafix   0   state< <Fixed.Pt#>  ! 
            BEGIN   KEY   DUP   13 <>      WHILE
            DUP   cat->col#  <fixed.pt#>   REPEAT ; 

参考文献

  1. 例えば、A.V. Aho, R. Sethi and J.D. Ullman, Compilers: Principles, Tools and Techniques (Addison Wesley Publishing Company, Reading, MA, 1986); R. Sedgewick, Algorithms (Addison Wesley Publishing Company, Reading, MA, 1983)を参照。

  2. J.V. Noble, "Avoid Decisions", Computers in Physics 5, 4 (1991) p 386。

  3. J. Basile, J. Forth Appl. and Res. 1,2 (1982) pp 76-78。

  4. E. Rawson, J. Forth Appl. and Res. 3,4 (1986) pp 45-64。

  5. C. E. Eaker, Forth Dimensions Vol II No. 3 September/October 1980, pp 37-40。

  6. HS/FORTH Harvard Softworks, P. O. Box 69, Springboro, OH 45066。

  7. ANSI X3.215-1994 American National Standard for Infomation Systems -- Programming Languages -- Forth, American National Standards Institute New York, NY 1994

  8. D.W. Berrian, Proc. 1989 Rochester Forth Conf. (Inst. for Applied Forth Res., Inc., Rochester, NY 1989) pp. 1-5。

  9. J. Woehr, Forth: The New Model (M&T Books, San Mateo, CA, 1992) p. 43 ff。

  10. A.K. Dewdney, The Turing Omnibus: 61 Excursions in Computer Science (Computer Science Press, Rockville, MD, 1989), p. 154ff。

  11. J.V. Noble, Scientific FORTH: a modern language for scientific computing (Mechum Banks Publishing, Ivy, VA 1992)。特に第11章と付属プログラムディスクを参照。

HTMLに変換 2003/12/23
フォーマット 1995年4月17日
フォーマット 1994年6月11日

元の場所: ftp://ftp.taygeta.com/pub/Forth/Literature/NOBLE004.HTM.txt