読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

Forthの仕組み - 解釈実行

forth

前回

サンプルコードはgithubリポジトリに置いてある。

documentation-forth/002.interpret at master · phaendal/documentation-forth · GitHub

今回は、ユーザーの入力を解釈して、ワードを実行する仕組みを説明してみる。

といっても、他の言語とは違い、Forthは構文解析を必要としない。

Forthのコードのうち、空白又は改行によって区切られた単語を全てトークンと呼ぶことにする。 (例によって独自の言葉遣いなので読んだら忘れて欲しい)

例えば: inc 1 + ;というコードなら、文字列:inc1+;は全てトークン。

一応説明しておくと、トークンを読み込むのは

  1. 先頭の空白又は改行を全て読み飛ばす
  2. 空白又は改行が来るまで文字をトークンとして読み込み続ける

という処理を行う。

それで、今回の本題、解釈実行は

  1. トークンを読み込む
  2. そのトークンをワード名として持つワードを探す
  3. ワードがあればそのCoreを実行、無ければ数値として解釈等を行う

の繰り返しで行う。これだけしかない。

1はForth特有のテクニックではなく、3は前回の知識+αなので、2についてもう少し説明する。

ヘッダを辿ってワードを探す

前回、辞書の構造はこうなっていると説明した。

     101 [ ヘッダ       ]
CFA→ 102 [ Coreへの参照 ]
DFA→ 103 [ データ       ]
     104 [ データ       ]
     105 [ データ       ]

そのうち触れていなかった、ヘッダの構造を詳しく見てみる。

ヘッダに少なくとも必要なのは

  1. ワード名
  2. 前のワードへのリンク
  3. HIDDENフラグ
  4. IMMEDIATEフラグ

の4つ。そのうち、4はForthの自己拡張で使うので今回は触れない。

典型的なForthの辞書は、リンクリストになっている。ワードのヘッダに前のワードへのリンクが含まれていて、 単純にそのリンクリストを辿って比較していくことでワードを探す。

詳しく書くと、

  1. 一番最後に定義されたワードを「対象ワード」に指定する
  2. 対象ワードの名前が探しているものと一致しているか調べる
  3. 一致していれば対象ワードのアドレスを返して終わる
  4. そうでなければ、ヘッダの前のワードへのリンクを調べて、存在していれば対象ワードに設定して2へ戻る
  5. 前のワードが存在しなければ、ワードが存在しなかった事を返して終わる

となる。基本的なリンクリストの調べ方だと思う。

さらに、HIDDENフラグが立っているワードは名前を調べずに飛ばす。これも自己拡張の為に使う。

実装する

前回のコードを元に解釈実行を実装してみる。

トークンの切り出しは、後々Forth自身で拡張できるように、

  • 1文字だけ入力から読み込む
  • 1トークン読み込む

と2つの動作ができるようにしておく。

ヘッダは、JavaScript版ではオブジェクトを、C言語では構造体を使い、配列1番地のみを使うようにする。 (jonesforthなどアセンブリの場合はそのまま展開することが多いみたいだ)

それでは実際の実装を大まかに見てみる。JavaScriptとCで同じようなことを解説しているので、 必要が無ければどちらか片方を見て欲しい。

実装の概観(JavaScript)

ワードの定義は関数で自動的にした方が楽になるけど、今回までは読みやすさを優先して配列に直接書いた。

var dict = [0, // 終了用の番兵
            { next: null, name: "2"    }, pushTwo,             // pushTwo: 2
            { next: 1,    name: "*"    }, mul,                 // mul: 4
            { next: 3,    name: "."    }, printStack,          // printStack: 6
            { next: 5,    name: "ret"  }, ret,                 // ret: 8
            { next: 7,    name: "2*"   }, docolon, 2, 4, 8,    // 2倍: 10
            { next: 9,    name: "4*"   }, docolon, 10, 10, 8,  // 4倍: 15
            { next: 14,   name: "16*"  }, docolon, 15, 15, 8,  // 16倍: 20
            { next: 19,   name: "test" }, docolon, 2, 20, 6, 8 // main: 25
           ],
    latest = 24;

コメントの数字(ret:8 など)はその行のワードのCFA。ヘッダはそれの1つ前にある。retのヘッダアドレスは7。

また、今回からネイティブワード(pushTwo,mulなど)はData Fieldを持たない。 前回はわかりやすさのために書いておいたけど、Data Fieldはdocolonで実行していくためのアドレス置き場なので、 docolonを用いないネイティブワードには必要無い。

概観のために、実行に使う関数の名前だけ抜き出してみる。

makeReader 入力を文字列として受け取り、呼ばれる度に1文字返すリーダー(クロージャ)を返す
skipSpace  空白が続く限りリーダーに読み飛ばさせる
readToken  リーダーを受け取り、トークンを一つ切り出して返す

findWord   ワードのヘッダアドレスを返す
toCFA      ヘッダアドレスから、CFAを返す
executeCFA CFAを受け取り実行する
asValue    トークンを数値として解釈できればその数値をスタックに置く
doToken    トークンと同名のワードがあれば実行、でなければ数値として解釈、できなければエラー

interpret  受け取ったコード文字列からトークンを一つ切り出しdoToken、をトークンが無くなるまでループ

実装の概観(C)

新たにヘッダの為の構造体を追加した。また、数値の解釈でstrtolを使って楽をするために、 スタックに積まれる数値はlong intに変更。

ワードのフラグwflagはビットフィールドを使い、以下のような構造体で管理する。

// Header
typedef struct {
  int    next;
  char  *name;
  wflag *flag;
} Header ;

typedef union {
  Number number;
  Core   core;
  Header *header;
} DictValue;

ヘッダと辞書も含めて、ワードの定義は自動化した方が楽になるけど、 今回まではわかりやすさを優先して全て手で書いた。

// ヘッダと辞書の構造体
// Numberはlong int、wflagはフラグ用のビットフィールド
typedef struct {
  int    next; // 前のワードのヘッダアドレス
  char  *name;
  wflag *flag;
} Header ;

typedef union {
  Number number;
  Core   core;
  Header *header;
} DictValue;


// 手で書くヘッダの例
// f_noneは何も立ってないフラグのビットフィールド
Header h_dot = { 3, ".", &f_none };
void printStack () {
  printf("%ld\n", dpop());
  next();
}


// 辞書
DictValue dict[] = {
  0,
  {.header = &h_two},   {.core = pushTwo},             // pushTwo: 2
  {.header = &h_mul},   {.core = mul},                 // mul: 4
  {.header = &h_dot},   {.core = printStack},          // printStack: 6
  {.header = &h_ret},   {.core = ret},                 // ret: 8
  {.header = &h_mul2},  {.core = docolon}, 2, 4, 8,    // 2倍: 10
  {.header = &h_mul4},  {.core = docolon}, 10, 10, 8,  // 4倍: 15
  {.header = &h_mul16}, {.core = docolon}, 15, 15, 8,  // 16倍: 20
  {.header = &h_main},  {.core = docolon}, 2, 20, 6, 8 // main: 25
};

int latest = 24;

辞書のコメントの数字(ret:8 など)はその行のワードのCFA。ヘッダはそれの1つ前にある。retのヘッダアドレスは7。

また、今回からネイティブワード(pushTwo,mulなど)はData Fieldを持たない。 前回はわかりやすさのために書いておいたけど、Data Fieldはdocolonで実行していくためのアドレス置き場なので、 docolonを用いないネイティブワードには必要無い。

読み取りについては、rbufferとtokenというグローバル変数を作り、 コードをrbufferにコピー、tokenに1トークンずつ切り出して使う設計にした。

概観のために、実行に使う関数の名前だけ抜き出してみる。

setup_reader コード全体を受け取り、バッファを0でクリアして、読み取り位置を先頭に
             戻してからコードをバッファにコピーする

reader     バッファから1文字読み取り返す。読み取り位置は次の文字へ移動する
skipSpace  空白が続く限りreaderで読み飛ばす
readToken  グローバル変数tokenに、バッファから1トークン切り出してコピーする。

findWord   ワードのヘッダアドレスを返す
toCFA      ヘッダアドレスから、CFAを返す
executeCFA CFAを受け取り実行する
asValue    トークンを数値として解釈できればその数値をスタックに置く
doToken    トークンと同名のワードがあれば実行、でなければ数値として解釈、できなければエラー

interpret  受け取ったコード文字列からトークンを一つ切り出しdoToken、をトークンが無くなるまでループ

テストコード

JavaScriptとCどちらも、以下のようにForthコードを実行できる。

  interpret(" 2 16* . ");     // => 32
  interpret("2 2* 4* 2* . "); // => 32 前に空白無し
  interpret(" 2 4* 4* .");    // => 32 後ろに空白無し
  interpret("main");          // => 32 前後に空白無し
  interpret("-8 4 * -1 * ."); // => 32 リテラル使用
  interpret("this-is-wrong-word-name"); // エラー

おわりに

かなりシンプルな仕組みで動くことがわかってもらえたら嬉しい。

この後は、組み込みワードの追加とコンパイルで一応処理系として完成させた後、Forth自身で分岐・ループ・変数の構文を作る方法までは書きたい。余裕があれば、RetroForthを参考にしたQuotationとPrivate、自分で考えたちょっと(だいぶん)ナイーヴな実装のローカル変数、あと細々したデバッグツールの作り方ぐらいまで書けたらな、と考えてる。それ以上は知らないので勉強・練習しなきゃだ。

それから、C言語に慣れてない(練習中)のも多分にあるんだろうけど、今のところ、やっぱりForthはアセンブリで書いたほうが単純で楽だな……という感想。いやポインタと構造体に慣れてないだけかなやっぱり。メモリ配置が直感で把握できるようになったら便利に思えるのかもしれない。

広告を非表示にする