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

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

私に教えられることなら

Forthの仕組み - ワード実行

forth

(7/19 いくつかミスが見つかったので修正)

いろいろForth処理系を作ってきて、 大分動作が頭に染みこんできたので、ここらへんで一度復習も兼ねて動作を解説してみる。

ForthやConcatenativeLanguageには本当にいろいろな作り方があるんだけど、 今回はjonesforthで学んだ、おそらく一番伝統的なやり方を選ぶ。

前提として、ポインタとリンクリスト、関数ポインタ(参照)を理解していれば大丈夫だと思う。

それから、JavaScriptでサンプルコードを書くけど、コードに合わせた詳細な説明はせず、動作や仕組み、考え方を大まかに説明する。 というよりjonesforthの更に入門みたいになるだろうから、興味がある人はjonesforthを続けて読んで欲しい。

Forth言語自体の説明はしない。1 1 +2がスタックに置かれること、: inc 1 + ;でincというワードを定義し、 3 inc4がスタックに置かれること、がわかってればok。

なお、正式な教育を受けたわけじゃないので、オリジナルの言葉を定義して使う。読んで動作がわかったら、それは忘れて欲しい。

今回はワードの構造と実行の仕組み。

ワードの構造

ワード1つ分の構造は、アセンブリならメモリ、高級言語なら配列で、こんなカンジになる。(番地は適当。)

101 [ ヘッダ             ]
102 [ ワードの核への参照 ]
103 [ データ             ]
104 [ データ             ]
105 [ データ             ]

(実際にはヘッダが何番地か占めていたりするけど、それは実装による。)

大きく分けると、ヘッダ、ワードの核、データの並び、の3つ。

ワードの核ってのは正式な用語じゃない。実際はワードのコードとか呼ぶみたいだけど、 コードと言われて(僕が)連想する: inc 1 + ;1 +の部分、ではないのでちょっとややこしい。 なのでワードの核、Coreと呼ぶけど、独自の言葉なので注意してほしい。本当は「コード」です。本当は『コード』です。

で、Coreへの参照が入ってる場所(上なら101の内容)をCore Field略してCFと呼び、そこのアドレス(上なら101自体)を Core Field Address略してCFAと呼ぶ。

そして、データの並びをData Field、それが始まる番地(上なら102)をData Field Address略してDFAと呼ぶ。

それを元に書き直すと

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

となる。

Forthは、このワードが並んだ、「辞書」と呼ばれるメモリ・配列を使ってプログラムを組んでいく。 他の言語のハッシュテーブルを意味する辞書とは違うので注意。

ワードの核と実行

ワードの核は、実装する言語でのコード、機械語や関数でできている。

ここは実際に見てもらった方が早い。「helloworld!と表示するワード」を作ってみよう。

ワードのヘッダはとりあえず空白(0)で、Data Fieldも0のみ、dictという配列に突っ込む。

function hello () {
    console.log("helloworld!");
}

var dict = [0, hello, 0];

ここらへんからがForthのミソなんだけど、まず「今から実行するCFA」を指すip(Instruction Pointer)を使う。このときCFAが入ってることに注意する。サンプルコードだとip = helloじゃなくてip = 1を入れる。

で、dict[ip]を実行する(呼び出す)。今後この動作を「ipをexecuteする」と呼ぶ。

function hello () {
    console.log("helloworld!");
}

var dict = [0, hello, 0],
    ip   = 1;

function execute () {
    dict[ip]();
}

execute();

しかしこれだと一つの核しか実行できない。そこで、「次の命令」を指すNext Pointer、npを導入する。

NEXT

辞書がこうなってるとする

0 [ ワードyoのヘッダ  ]
1 [ CF                ] -> yo!と出力する関数
2 [ 0                 ]
3 [ ワードheyのヘッダ ]
4 [ CF                ] -> hey!と出力する関数
5 [ 0                 ]

ワードyoとheyを交互に2回ずつ実行したい。そのために、まずyoとheyのCFAを辞書に置く。

0 [ ワードyoのヘッダ  ]
1 [ CF                ] -> yo!と出力する関数
2 [ 0                 ]
3 [ ワードheyのヘッダ ]
4 [ CF                ] -> hey!と出力する関数
5 [ 0                 ]
6 [ 1                 ] yo のCFA
7 [ 4                 ] heyのCFA
8 [ 1                 ] yo のCFA
9 [ 4                 ] heyのCFA

そしてどうすればいいんだろう?まずipがyoのCFAになってほしいので、それが入っているdict[6]の内容を入れる。

6 [ 1 ] yoのCFA
7 [ 4 ] heyのCFA
8 [ 1 ] yoのCFA
9 [ 4 ] heyのCFA

なので、ip = dict[6]ip = 1と同じだ。

そしてここで、「次に実行すべきCFAが入ってる場所」を指すnp(Next Pointer)を導入する。

np = 7 で、こういう状況になる。

      6 [ 1 ] ip = 1
np → 7 [ 4 ] 
      8 [ 1 ] 
      9 [ 4 ] 

yoの核の実行が終わった時点で、まず npが指している辞書の中身をipに入れる

      6 [ 1 ]
np → 7 [ 4 ] ip = 4
      8 [ 1 ] 
      9 [ 4 ] 

npに次の番地を指させる(np++)

      6 [ 1 ] 
      7 [ 4 ] ip = 4
np → 8 [ 1 ] 
      9 [ 4 ]

そしてipを再度executeすることで、次の命令を実行できる。 この一連の動作をNEXTルーチンと呼び、組み込みのワードの最後に加えることで、 次々と辞書に並んだCFAを実行していくことができる。

最終的に停止させるために、ipが0だったらループを終了させる。

function next () {
    ip = dict[np];
    np++;
}

function yo () {
    console.log("yo!");
    next();
}

function hey () {
    console.log("hey!");
    next();
}

var dict = [0, yo,  0,
            0, hey, 0,
            1, 4, 1, 4, 0],
    ip = dict[6],
    np = 7;

function execute () {
    while (ip !== 0) {
        dict[ip]();
    }
}

execute();

これで組み込みのワードと、その列を実行することができるようになった。残るは、ユーザー定義ワードの実行だ。

リターンスタック

ユーザー定義ワードは、Data FieldにCFAを並べて、ipとnpをセットアップする核を実行してやればいい。

ワードの定義は: ワード名 ワード ワード ;という形なので、Colon Definitionと呼ぶ。Colon Definitionされた ワードを実行するので、核の関数名はdocolonとする。

docolonでは、ipが自分が置いてあるCFAを指しているので、npをip+1に設定する。

ワードyoとワードheyを実行するワードyoheyを定義すると、こういう構造になる。

 0 [ ワードyoのヘッダ    ]
 1 [ CF                  ] -> yo!と出力する関数
 2 [ 0                   ]
 3 [ ワードheyのヘッダ   ]
 4 [ CF                  ] -> hey!と出力する関数
 5 [ 0                   ]
 6 [ ワードyoheyのヘッダ ]
 7 [ CF                  ] -> docolon
 8 [ 1                   ] yo のCFA
 9 [ 4                   ] heyのCFA
10 [ 0                   ]

この場合docolonを実行するときは、ipはyoheyのCFA、7なので、npをip + 1の8にしてやればいい。 後はexecuteすれば万事上手く……いかない。

ユーザー定義ワードが入れ子になるとおかしくなってしまう。 例で実行を追ってみよう。yoheyを二回実行する、2yoheyというワードを定義する。

 6 [ ワードyoheyのヘッダ  ]
 7 [ CF                   ] -> docolon
 8 [ 1                    ] yo のCFA
 9 [ 4                    ] heyのCFA
10 [ 0                    ]
11 [ ワード2yoheyのヘッダ ]
12 [ CF                   ] -> docolon
13 [ 7                    ] yoheyのCFA
14 [ 7                    ] yoheyのCFA
15 [ 0                    ]

今、ipを2yoheyのCFA(12)にセットしてexecuteを始めた。

まずdocolonの実行でnpは13になる。そして、docolonがNEXTルーチンを呼び、ipは7、npは14になる。

       6 [ ワードyoheyのヘッダ  ]
       7 [ CF                   ] -> docolon
       8 [ 1                    ] yo のCFA
       9 [ 4                    ] heyのCFA
      10 [ 0                    ]
      11 [ ワード2yoheyのヘッダ ]
      12 [ CF                   ] -> docolon
      13 [ 7                    ] yoheyのCFA  ip = 7
np -> 14 [ 7                    ] yoheyのCFA
      15 [ 0                    ]

そして、ワードyoheyのCFAを実行すると、docolonによってipとnpはこうなる

       6 [ ワードyoheyのヘッダ  ]
       7 [ CF                   ] -> docolon
       8 [ 1                    ] yo のCFA  ip = 1
np ->  9 [ 4                    ] heyのCFA
      10 [ 0                    ] 
      11 [ ワード2yoheyのヘッダ ]
      12 [ CF                   ] -> docolon
      13 [ 7                    ] yoheyのCFA
      14 [ 7                    ] yoheyのCFA
      15 [ 0                    ]

その後NEXTルーチンで順調に進んで……0で終わってしまう。2回目のyoheyは実行されない。

そこで、yoheyの最後の0の代わりに、元居た場所にnpを戻すreturnワードを置く。元居た場所 を覚えておくために、docolon実行時にnpを保存するリターンスタックを導入する。

       6 [ ワードyoheyのヘッダ  ]
       7 [ CF                   ] -> docolon
       8 [ 1                    ] yo のCFA
       9 [ 4                    ] heyのCFA
      10 [ n                    ] returnのCFA
      11 [ ワード2yoheyのヘッダ ]
      12 [ CF                   ] -> docolon
      13 [ 7                    ] yoheyのCFA  ip = 7
np -> 14 [ 7                    ] yoheyのCFA
      15 [ n                    ] returnのCFA

2yoheyのdocolonを実行した時点で、こうなっている。(2yoheyのdocolon前の準備は後述)

dict[7]のdocolonで、最初にnpの内容(14)をリターンスタックに置かせる。

       6 [ ワードyoheyのヘッダ  ]
       7 [ CF                   ] -> docolon
       8 [ 1                    ] yo のCFA ip = 1
np ->  9 [ 4                    ] heyのCFA
      10 [ n                    ] returnのCFA
      11 [ ワード2yoheyのヘッダ ]
      12 [ CF                   ] -> docolon
      13 [ 7                    ] yoheyのCFA
      14 [ 7                    ] yoheyのCFA
      15 [ n                    ] returnのCFA
リターンスタック: 14

そして、dict[10]のreturnの時に、リターンスタックからpopしてnpに入れてやると

       6 [ ワードyoheyのヘッダ  ]
       7 [ CF                   ] -> docolon
       8 [ 1                    ] yo のCFA
       9 [ 4                    ] heyのCFA
      10 [ n                    ] returnのCFA ip = n
      11 [ ワード2yoheyのヘッダ ]
      12 [ CF                   ] -> docolon
      13 [ 7                    ] yoheyのCFA
np -> 14 [ 7                    ] yoheyのCFA
      15 [ n                    ] returnのCFA
リターンスタック:

無事npが2回目のyoheyを指すので、後はreturn内のNEXTルーチンで進めてやればよい。

一番最初、ワード2yoheyのdocolonを実行する前に、npに0を入れておけば、最終的にそれがipにpopされて停止できる。(なので、本当は0番地にヘッダじゃなくて0を入れておく)

var return_stack = [],
    ip, np;

var dict = [0, yo,  0,
            0, hey, 0,
            0, ret, 0,
            0, docolon, 1, 4, 7,
            0, docolon, 10, 10, 7];

function rpush (x) {
    return_stack.push(x);
}

function rpop () {
    return return_stack.pop();
}


function next () {
    ip = dict[np];
    np++;
}

function yo () {
    console.log("yo!");
    next();
}

function hey () {
    console.log("hey!");
    next();
}

function ret () {
    np = rpop();
    next();
}

function docolon () {
    rpush(np);
    np = ip + 1;
    next();
}

function execute () {
    while (ip !== 0) {
        dict[ip]();
    }
}

ip = 15;
np = 0;
execute();

まとめ

結局、この設計のForthは

  • CFA列
  • 今から実行するCFA
  • 次に実行するCFAが入ってる場所のポインタ
  • リターンスタック

の4つだけでワードを実行させることができる。アセンブリのjumpやCでgotoを使えばexecuteはループが消えてもっと簡単な設計になる。

もちろん値を渡すためにデータスタックを使ったり、ワードをコンパイルするために 辞書を操作したりなどもするんだけど、それもかなり簡単にできる。

次はワードの実行とコンパイルを書く予定。

サンプル

JavaScriptとCでのサンプル。データスタックを実装して、

  • スタックに2を積むワード
  • スタックの1番目と2番目を掛けるワード
  • スタックトップの数値をpopして表示するワード

を組み合わせて、32を表示する動作を加えた。

JavaScript

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

var dict = [0, pushTwo,  0,          // pushTwo: 1
            0, mul, 0,               // mul: 4
            0, printStack, 0,        // printStack: 7
            0, ret, 0,               // ret: 10
            0, docolon, 1, 4, 10,    // 2倍: 13
            0, docolon, 13, 13, 10,  // 4倍: 18
            0, docolon, 18, 18, 10,  // 16倍: 23
            0, docolon, 1, 23, 7, 10 // main: 28
           ];

function rpush (x) {
    return_stack.push(x);
}

function rpop () {
    return return_stack.pop();
}

function dpush (x) {
    data_stack.push(x);
}

function dpop () {
    return data_stack.pop();
}

function next () {
    ip = dict[np];
    np++;
}

function pushTwo () {
    dpush(2);
    next();
}

function mul () {
    var a = dpop(),
        b = dpop();
    dpush(a * b);
    next();
}

function printStack () {
    console.log(dpop());
    next();
}

function ret () {
    np = rpop();
    next();
}

function docolon () {
    rpush(np);
    np = ip + 1;
    next();
}

function execute () {
    while (ip !== 0) {
        dict[ip]();
    }
}

ip = 28;
np = 0;
execute();

C

#include <stdio.h>

// スタック
// ===================================================================
int dstack[128];
int dsp = 0;

int rstack[128];
int rsp = 0;

void rpush (int x) {
  rstack[rsp] = x;
  rsp++;
}

int rpop () {
  rsp--;
  return rstack[rsp];
}

void dpush (int x) {
  dstack[dsp] = x;
  dsp++;
}

int dpop () {
  dsp--;
  return dstack[dsp];
}


// 辞書
// ===================================================================
typedef void (*Core)(void);

typedef union {
  int  number;
  Core core;
} DictValue;

DictValue ip;
int np;

void next ();

void pushTwo () { dpush(2); next(); }

void mul () {
  int a = dpop();
  int b = dpop();
  dpush(a * b);
  next();
}

void printStack () {
  printf("%d\n", dpop());
  next();
}

void ret () {
  np = rpop();
  next();
}

void docolon () {
  rpush(np);
  np = ip.number + 1;
  next();
}

DictValue dict[] = {
  0, {.core = pushTwo},  0,          // pushTwo: 1
  0, {.core = mul}, 0,               // mul: 4
  0, {.core = printStack}, 0,        // printStack: 7
  0, {.core = ret}, 0,               // ret: 10
  0, {.core = docolon}, 1, 4, 10,    // 2倍: 13
  0, {.core = docolon}, 13, 13, 10,  // 4倍: 18
  0, {.core = docolon}, 18, 18, 10,  // 16倍: 23
  0, {.core = docolon}, 1, 23, 7, 10 // main: 28
};

void next () {
  ip = dict[np];
  np++;
}

void execute () {
  while (ip.number != 0) {
    dict[ip.number].core();
  }
}

int main (int argc, char* argv[]) {
  ip.number = 28;
  np = 0;
  execute();

  return 0;
}
広告を非表示にする