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

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

私に教えられることなら

Forthの仕組み - コンパイル

前回

今回は、ユーザがワードを定義できるように、コンパイル処理を作っていく。

サンプルコード

Forthのコンパイルとは

前回までに見た通り、ForthのワードはCoreのみ、又はCore(docolon)+呼び出すワードのCFAの列、となっている。前者をネイティブワード、後者をコロンワードと呼ぶ。通常、ユーザが定義するのはコロンワードだ。

: double dup + ;というコロンワードの定義を見てみる。3 double6が置かれる。このコロンワードを定義するには、ヘッダとdocolonの後にdup+retのCFAを辞書に置いてやればいい。

Forthのコンパイルは、基本的には、

  1. ワード名を読み
  2. そのワードのCFAを辞書に追加する

だけでいい。

実行モードとコンパイルモード

じゃあそのコンパイルをどこで行うかというと、今までワード名を読み込んで実行していたインタープリタを使う。サンプルコードならinterpret関数とそれが呼び出す関数に、新しく「コンパイルモード」を付け加える。以降、このモードの事を「VMモード」と呼ぶ。

トークンを1つ読みこみ、同じ名前のワードを探して、そのCFAを

  • 実行モード(execute mode)なら実行する
  • コンパイルモードなら辞書に追加する

の2通りで扱う。

それから、主に自己拡張ワードのために、コンパイルモード中にワードを実行したい場合が出てくる。そのために、ワードのヘッダでimmediateフラグが立っていれば、コンパイルモードでもコンパイルせず、実行するようにしておく。

lit

数字の場合はコンパイルを工夫する必要がある。そのまま辞書に数字を追加すると、それがCFAとして解釈されてしまうからだ。

そのためにlitというワードを追加する。litは自分の次にある辞書の値をスタックに置く。

例えば現在、こうなっているとする

スタック: 空

ip -> 201 [ litのCFA ]
np -> 202 [ 3 ]
      203 [ +のCFA ]

litが呼ばれたとき、ipには自分のCFAが置かれてるアドレス(201)が、npには辞書の次のアドレス(202)が入っている。litの目的の値は辞書のnp番地にある。この場合は3をnp番地から取り出して、スタックに置く。

スタック: 3

ip -> 201 [ litのCFA ]
np -> 202 [ 3 ]
      203 [ +のCFA ]

このままだとnextルーチンで3がCFAと解釈されてしまうので、npを一つ進めておく。

スタック: 3

ip -> 201 [ litのCFA ]
      202 [ 3 ]
np -> 203 [ +のCFA ]

これでlit内のnextルーチンによって、203以降へと進んでいく。

コンパイル時に数字nを読み込んだときは、litを先に追加してlit nと辞書に置くことで数字を置く動作にコンパイルできる。

実装

もう少し詳しく実装について見てみる。

dict_hereとpushDict

CFAを辞書に追加していくために、

  1. 辞書の次の空き位置dict_here変数
  2. 1の場所に何か値を入れ、1を進めるpushDict関数

の2つを使う。

また、自己拡張の為にどちらもForthから使えるようにしておく。今回はコンパイル時に使うので、まずpushDictをpush-dictワードによってForthから使えるようにする。

ワード定義関数

前回まで、わかりやすさの為にワードの定義は直接辞書に置き、latestを手動で更新していた。

今回はそれを簡単にするためにワード定義の為の関数を作る。

まずワードのヘッダを作る必要がある。ヘッダを作る関数をcreateHeaderとする。ワードのヘッダには

  • 前のワード
  • ワードの名前
  • フラグ

が必要で、更にlatestをそのヘッダのアドレスに更新する。

次に、ワードの定義のために

  1. ネイティブワードを作るdefnative
  2. コロンワードを作るdefword

の2つを作る。defnativeはCoreを、defwordはCFAの列を受け取る。

defnative/defword共通してまずcreateHeaderでヘッダを作る。次に、defnativeは受け取ったCoreを辞書に置く。defwordは、まずdocolonを辞書に置いてから、受け取ったCFAの列を辞書に並べていく。

Coreをどう置くかは実装による。今回は、C版なら関数ポインタを、JavaScript版は関数を直接置く。

defnative用のCoreは、だいたいnext()を最後に呼び出す必要があるけど、defnativeで自動的に付加はしない。一部のワードはnextを呼ばないためだ。

ただ、nextを置くことを忘れやすいので、デフォルトでnextを置く動作にして、nextを置かずにネイティブワードを定義する方法を加えたほうがいいかもしれない。

defwordでも、ワードの最後にだいたいretを置く必要がある。これも一応自動的に付加はしない。

defnative、defwordともにヘッダのアドレスを返す。今回のC版・JavaScript版の実装ではヘッダアドレスからCFAもその逆も計算しやすいけど、ヘッダの構造によってはCFAからヘッダアドレスを計算するのが面倒になるためだ。

まとめると、以下の3つの関数を作る。

  • createHeader ( ワード名、フラグ -- addr )
  • defnative ( -- )
  • defword ( -- )

VMモードとimmediate

VMモード(実行/コンパイル)の取得と切り替えを行う関数を作っておく。

ANS Forthでは、VMモードを実行モードに変更するのは[というワード、コンパイルモードは]というワードで、ワード定義中に: foo [ ここにコンパイル中に実行するコード ] bar ;といった使い方をする。

しかし、今回の実装ではRetroを参考にしたQuotationまで作り、その表記に[ foo ]を使いたいので、それぞれexecute-mode>>compile-mode>>と長めの名前にする。

実行モード中にコンパイルモードに切り替えたい場合は、単にcompile-mode>>を解釈実行させるだけでいいけど、コンパイルモード中にexecute-mode>>を入力して実行モードに切り替えようとしても、execute-mode>>のCFAがコンパイルされるだけでモードは切り替えられない。

そのため、execute-mode>>のヘッダでimmediateフラグを立てておき、切り替えられるようにする。

execute-mode>>自体をコンパイルする方法(postpone)もある。次回以降で説明する。

コロンでのワードのコンパイル

Forthでのコロンワード定義、: inc 1 + ;でのワード:;について解説する。

Forthでは:;は単なるコロン定義ワードで、ユーザが定義できるワードと違いは無い。

:の動作は

  • ワード名を読み込み、ヘッダを作る
  • docolonをCore Fieldに置く
  • hiddenフラグを立てる
  • コンパイルモードに切り替える

;はimmediateワードで、

  • リターンワード(ret)をコンパイルする
  • hiddenフラグを外す
  • 実行モードに切り替える

となる。

hiddenフラグと拡張

何故hiddenフラグを立てるのかというと、(おそらく伝統的なForthらしく)同名ワード定義で拡張するためだ。

定義の最初にhiddenフラグを立てることで、現在定義中のワードは参照できなくなる。: foo foo ;という定義のワードだと、無限に再帰するのではなく、今定義中のfooより一つ前で定義されたfooを呼び出すことになる。

例えばmがnの2倍以上ならGREAT!と表示するワードgreat?を定義する(処理系はgforth)

: great? ( m n -- )
  / 2 >= if ." GREAT!" exit then ." no..." ;

4 3 great? no... ok
6 3 great? GREAT! ok

このとき、nが0だとゼロ除算エラーであることを表示したいとする。普通の言語だと関数にガードなどを書き足すことになるけど、Forthの場合は同名ワードでカバーするような拡張ができる。

: great? ( m n -- )
  dup 0 <= if ." zero division error!" exit then great? ;

3 0 great? zero division error! ok

さらにワード実行の前後に何か処理を付け加えることもできる。

: great? ( m n -- )
  ." [START] " great? space ." [END]" ;

10 3 great? [START] GREAT! [END] ok

他の言語を使っている人は、この動作・拡張の仕方を気に入らない人も多いだろうと思う。

自分は

  • ワードを細かく分解するとき、命名に悩まなくていい
  • それぞれの動作を書いた時点でテストできる
  • スタックを使うと末尾再帰的なコードが書きやすいので、あまり素の再帰を使わない

の三点からこの動作を好んで使っている。例えば自作の処理系jf64の組み込み辞書でも、同名ワードでの拡張とtail-recurによるジャンプでの再帰を多用している。

Factorみたいに関数型言語としての側面を強くするなら普通に再帰した方がいいかもしれない。その場合はhiddenフラグ関係の処理を外すだけで再帰できる。相互再帰のための宣言などはまた別の話になる。

文字列の扱いとトークンの読み込み

伝統的なForthでは、文字列は長さとアドレスの組を使う。また、トークンを読み込んでワード名としてヘッダに置くときは、インプットバッファから辞書に直接コピーする。

今回のJavaScriptとCでは、どちらもその方法は取らない。

JavaScriptではGCがあるのでJavaScriptの文字列を直接使う。Cでは、Cのヌル終端文字列を、一度バッファに格納してからstrdupでコピーして使う。そのため、ワードのヘッダをfreeするときは、ワード名の文字列もfreeする必要がある。

サンプルコード

JavaScriptとC共通で、次のコードで試す。

  interpret(": 32* 32 * ;");
  interpret(": inc 1 + ;");
  interpret(": 64. 1 inc 32* . ;");
  interpret("64."); // => 64

コロン定義ワード32*inc、さらにそれらを使った64.が動くことを確認する。

実装の概観(JavaScript)

後方参照をできるだけしないように、toCFAなど必要に応じて前に出すことにする。

辞書構造の変更

前回まで、このように配列に直接辞書を作っていた。

var return_stack = [],
    data_stack   = [],
    ip, np;

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;

今回から、ワード定義用の関数を使うので、辞書の初期値にはfind用の番兵0のみを置く。これはJavaScript版では使わない。他の実装と合わせるために使う。

また、辞書に動的に値を追加するため、辞書の次の空き位置を指すdict_here変数を用意し、find用にlatestをnullにセットしておく。

更に、VMモードを表すvm_modeグローバル変数も用意しておく。

var return_stack = [],
    data_stack   = [],
    ip, np,
    vm_mode = 0, // 0: execute, 1: compile
    
    dict_here = 1,
    dict = [0], // 終了用の番兵
    latest = null;

ワード定義関数

上で説明した通り、ワード定義を簡単にするために以下の3つの関数を定義する

  • createHeader
  • defword
  • defnative

defwordはヘッダのアドレスを配列として渡して使う。

// 使用例(アドレスは適当)
defword("foo", [10, 15]);

defword、defNative共にヘッダのアドレスを返す。これを変数に入れておいて、defwordで直接アドレスを指定する代わりに使う。

// 使用例(不足)
vaw word_2x = defword("2*", [word_two, word_mul]),
var word_4x = defword("4*", [word_2x, word_2x]);

retは自動的に足さないので、上の例では動かない。自分で置くのを忘れないようにする。

// 使用例
vaw word_2x = defword("2*", [word_two, word_mul, word_ret]),
var word_4x = defword("4*", [word_2x, word_2x, word_ret]);

JavaScript版ではCoreはJavaScriptの関数なので、defNativeではワード名と関数を渡して使う。

// 使用例
var word_dot = defNative(".", function () {
    console.log(dpop());
    next();
});

モード別処理

前回までは、1つのトークンを処理するdoToken内で、直接ワード/数値の処理関数を呼び出していた。今回からはモード別の処理が必要なので、procWordとprocValueに任せるようにする。

procValueでは、数値のコンパイル時に、数値の前にワードlitのCFAを置く。

コロン定義

ワード:で使うread-token>は、readToken関数をそのまま使いトークンを読み込む。そのため、今使用しているトークンリーダーを登録するグローバル関数global_readerを導入し、interpret毎に更新する。

また、同じくワード:で使うcreate-headerのコードでは、ヘッダの後に忘れずにdocolonを辞書に置く。

ただ、docolonを辞書に置くワードと、ヘッダのみを作るワードをそれぞれ別に作ると自己拡張の際に少し便利になる。例えば前者はワード内ワードを定義する場合に、後者はネイティブコードコンパイルを行う場合にそれぞれ楽になる。次回以降に定義するjump!を使えば同じ事はできるので、必須ではない。

ワード;のimmediateフラグを忘れずに立てておく。

実装の概観(C)

後方参照をできるだけしないように、toCFAなど必要に応じて前に出すことにする。

辞書構造の変更

前回まで、このように配列に直接辞書を作っていた。

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;

今回から、ワード定義用の関数を使うので、辞書の初期値にはfind用の番兵0のみを置く。

また、辞書に動的に値を追加するため、辞書の次の空き位置を指すdict_here変数を用意し、find用にlatestを0にセットしておく。

#define DICT_MAX 65536
DictValue dict[DICT_MAX] = { 0 }; // 終了用の番兵

int latest = 0;
int dict_here = 1;

データ構造の変更

辞書にString(char*)を置けるように、DictValue共用体を変更する。(また、ファイルの最初に構造体などの宣言を移動した。)

typedef long int Number;
typedef char* String;

// Core
typedef void (*Core)(void);

// ワードのフラグ
typedef struct  {
  unsigned int immediate:1;
  unsigned int hidden:1;
} wflag;

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

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

VMモードアクセサ

VMのモードを表すvm_modeグローバル変数を用意しておく。

また、それぞれのモードに切り替える関数と、併せてnext();を呼ぶCore用の関数も定義しておく。

ワード定義関数

上で説明した通り、ワード定義を簡単にするために以下の3つの関数を作る。

  • createHeader
  • defword
  • defnative

createHeaderでは、Headerwflag、さらに名前のString(char*)の3つをmallocすることになる。念の為、それらを解放するfreeHeader関数も定義しておく。

defwordは可変長引数を使ってヘッダアドレスの列を渡す。そのため、最後に0を付け加える必要がある。

// 使用例(アドレスは適当)
defword("foo", 10, 15, 0);

defword、defnative共にヘッダのアドレスを返す。これを変数に入れておいて、defwordで直接アドレスを指定する代わりに使う。

// 使用例(不足)
int word_2x   = defword("2*", word_2, word_mul, 0);
int word_4x = defword("4*", word_2x, word_2x, 0);

retは自動的に足さないので、上の例では動かない。自分で置くのを忘れないようにする。

// 使用例
int word_2x   = defword("2*", word_2, word_mul, word_ret, 0);
int word_4x = defword("4*", word_2x, word_2x, word_ret, 0);

C版では、defnativeにはvoid(Core*)(void)を渡して使う。

// Core
void printStr () {
  printf("%s\n", dpop().str);
  next();
}

void prepareBuiltins () {
  // ... 他の定義 ...
  int word_dot = defnative(".", printStack);
  // ...
}

上のように、最初にprepareBuiltinsで組み込みワードを準備する。

文字列の読み込み

C版では、ワード名などの文字列はchar*をそのまま辞書やスタックに置いて使う。

read-token>では、まずreadToken()を使って、インプットバッファからtoken[]バッファにトークンを読み込む。

次に、read-token>用のバッファtoken_bufferに読み込んだバッファをコピーして、そのアドレスを返す。token_bufferはリングバッファで、最大16トークンまで保持するようにしている。

何故read-token>用のバッファを用意するかというと、token[]バッファをそのまま使った場合、実行モードだとread-token>で読み込んだワードが使う前に上書きされてしまうためだ。

例えばスタックトップのchar*をとり文字列を表示するprintワードを定義し、read-token>で読み込んだトークンを表示しようとする場合

read-token> foo print

printを読み込んだ時点でtoken[]バッファにはprintという文字列が入ってしまう。よってtoken[]をそのまま使う場合、表示されるのはread-token>で読み込んだトークンfooではなく、printになる。

それを避けるためにread-token>用のリングバッファに移し、移した位置を返す。

ちなみにtoken[]をそのまま使う場合でも、: print-token read-token> print ;とワードに定義して、print-token fooインタプリタに入力した場合はfooが表示される。問題になるのはインタプリタ上でトークンを読み込んでそれを使いまわしたりする場合だ。

この問題はC言語のヌル終端文字列を使うために起きる。最初にインプットバッファに読み込んだとき、トークンの直後に0を置いたりするとまずいことになる場合があるからだ。

上で説明したように、アセンブリなどで組む伝統的なForthでは、普通はヌル終端文字列ではなく長さとアドレスの組を使う。パスカル文字列みたいに最初に長さを置くのではなく、スタックを使って2つの値で使う。

その設計の場合は、上記のような問題は起こらず、そもそもreadToken()token[]バッファにコピーする必要もない。インプットバッファでの開始アドレスと、トークンの長さでそのまま使える。インプットバッファを十分長くとる必要があるけど、設計自体は簡単になる。実際に組み込みなどで使う処理系を書くときは、その設計の方がいいかもしれない。

モード別処理

前回までは、1つのトークンを処理するdoToken内で、直接ワード/数値の処理関数を呼び出していた。今回からはモード別の処理が必要なので、procWordとprocValueに任せるようにする。

procValueでは、数値のコンパイル時に、数値の前にワードlitのCFAを置く。

コロン定義

ワード:で使うcreate-headerのコードでは、ヘッダの後に忘れずにdocolonを辞書に置く。

ただ、docolonを辞書に置くワードと、ヘッダのみを作るワードをそれぞれ別に作ると自己拡張の際に少し便利になる。例えば前者はワード内ワードを定義する場合に、後者はネイティブコードコンパイルを行う場合にそれぞれ楽になる。次回以降に定義するjump!を使えば同じ事はできるので、必須ではない。

また、フラグ変更用のsetImmediate関数を作っておき、ワード;を忘れずにimmediateワードにしておく。

おわりに

次回はbranchと0branchによるジャンプを作り、immediateワードによってif文を実装してみる予定。

文章の読みにくさが気になってきたので、印刷して推敲してみた。構成ももう少し練れば良かったなと思うけど、一度フルに動くものを書き上げてから改めてもう一度解説書いたほうが良さそうだ。もし読んでくれてる人がいて、わかりづらいと思ったら、今回のバージョンは流し読みして次のバージョンに期待しててください。。

広告を非表示にする