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

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

私に教えられることなら

Forthの仕組み5 - ループ

前回

今回は、前回に続きワードbranch0branchを使い、Forth自身でループ用ワードを作っていく。

サンプルコード

比較ワードの追加

ループを作る前に、その終了条件の判定などに数値の比較を行うワードを実装する。

0が偽として、真をどの数値で返すかを考える。0以外なら真だけど、何を返すか統一しておいたほうがわかりやすそうだ。

ここはちょっと好みが別れるところらしい。次の段落は、余談だし間違いもあるかもしれないので飛ばしていい。

FORTH79では1を返していたけど、FORTH83からは-1を返すようになった。これはNOTをTRUE/FALSEフラグの切り替え(0 =)として使うか、全てのビットを反転させるINVERT(-1 XOR)として使うかを標準化できなかったため、どちらの場合でも使えるように考慮された結果らしい。しかしC言語など他の言語とのインターフェイスを考えると、負の数でエラーを表す言語も多いので分かりづらくなる。それが理由でTRUEに1を使うFORTH実装も多いみたいだ。この文書の参考にしたjonesforthも、その理由で1を使うことにしているので、それに従うことにする。

というわけで、真の場合は1を返す。

今回は比較ワードとして= <> > < >= <=を実装する。<>はnot equal。

同じようなコードを書くことになるので、Cはマクロ、JavaScriptクロージャを使って比較部分だけを書けるようにする。

begin ... until

begin ... untilは、...部分のコードを実行し、untilの時点でスタックトップが偽ならばbeginに戻る。簡単に言うと、真になるまでループする。

どういうコードにコンパイルしたいか考えてみる。スタックトップが0の場合に戻るので、0branchを使えば良さそうだ。辞書の番地が小さい方に0branchするので、負のオフセットを使う。オフセットの幅は、そのままbeginuntilの間になる。

つまり... 0branch begin時点への負のオフセットというコードにコンパイルできればいい。beginuntil、どちらもimmediateワードで、コンパイル時に実行する。

まずbeginで、戻り先であるその時点の辞書ポインタをスタックに置く。

untilでは、戻るコードをコンパイルする。具体的に言うと、

  1. 0branchをコンパイルする
  2. beginで置いたアドレスを使って、負のオフセットを計算する
  3. オフセットを辞書に追加する

という動作を行う。

Forthコードでの定義は以下になる。

: begin  dict-here ; immediate!
: until  compile> 0branch  dict-here -  push-dict ; immediate!

例として、begin 1 - dup 0 <= untilというコードのコンパイルを見てみる。スタックトップの数値を、0より大きい間引いていく。以下、アドレスは適当で、コンパイルモード中とする。

今、辞書ポインタが101とする。beginを実行すると、スタックにそれが追加される。

スタック: 101

1 - dup 0 <=までコンパイルした時点で、辞書とスタックはこのようになっている。

スタック: 101
101 [ lit ]
102 [ 1   ]
103 [ -   ]
104 [ dup ]
105 [ lit ]
106 [ 0   ]
107 [ <=  ]

untilの実行に移る。まず、0branchコンパイルする。

スタック: 101
101 [ lit     ]
102 [ 1       ]
103 [ -       ]
104 [ dup     ]
105 [ lit     ]
106 [ 0       ]
107 [ <=      ]
108 [ 0branch ]

次にdict-here -を実行する。この時点での辞書ポインタ109を、スタックトップに置いておいたbegin時の辞書ポインタ101から引く。101 109 -で、負のオフセット-8になる。

スタック: -8
101 [ lit     ]
102 [ 1       ]
103 [ -       ]
104 [ dup     ]
105 [ lit     ]
106 [ 0       ]
107 [ <=      ]
108 [ 0branch ]

最後にそれを辞書に追加する。

スタック:
101 [ lit     ]
102 [ 1       ]
103 [ -       ]
104 [ dup     ]
105 [ lit     ]
106 [ 0       ]
107 [ <=      ]
108 [ 0branch ]
109 [ -8      ]

0branchによって、スタックトップが0の場合、109 -8 +で101の位置にジャンプする。つまり、偽の場合ループする。

begin ... again

begin ... againは無条件ループで、until0branchbranchに変えただけのものだ。そのまま実行すれば無限ループになるので、retでワードごと抜けたりして使う。

定義もそのままbranchに変更すればいいんだけど、後で全く同じコードを使うので、againの内容を'back-branchとしてワードにしておく。

: 'back-branch  compile> branch dict-here - push-dict ;
: again  'back-branch ; immediate!

begin ... while ... repeat

begin ... while ... repeatは、上二つとは違い、先に条件判定を行える制御構造だ。while時点でスタックトップが真ならば、while ... repeatの部分を実行し、beginまで戻る。while時点で偽ならば、repeatの次までジャンプしてループを抜ける。

偽の場合はジャンプ、ということでwhileでは0branchコンパイルする。repeat時点までジャンプするので、オフセットをrepeatで書き換える。ifの時に定義したsave-offsetが使える。

repeatではそれに加えて、beginの位置まで戻るコードをコンパイルする。負のオフセットで無条件ジャンプなので、begin ... againで定義した'back-branchが使える。

手順を整理する。まずwhileでは次の2つを行う。

  1. 0branchコンパイルする
  2. オフセット記録用のアドレスをスタックに積み、仮の値を辞書に置く

気づいた人も居るかもしれないけど、実はワードifと同じ手順だ。

repeatの時点で、スタックはbeginの位置 whileのオフセット記録位置(右が上)となっている。よって次の2つを行う。

  1. swapして対象をbeginの位置にし、'back-branchでループするコードをコンパイル
  2. save-offsetwhileの飛び先をrepeat時点に書き換える

以上から、定義は以下になる。

: while   compile> 0branch  dict-here 0 push-dict ; immediate!
: repeat  swap 'back-branch  save-offset ; immediate!

詳しく動作を追ってみる。例として、スタックトップの数値を出力しながらカウントダウンするワードwhile-testコンパイルを見る。0より大きい間動作を行う。以下、アドレスは適当で、コンパイルモード中とする。

: while-test  begin  dup 0 >  while  dup .  1 -  repeat ;

まずワードbeginが実行され、スタックトップに現在の辞書ポインタが積まれる。

スタック: 101

whileの手前、>までコンパイルが終わった時点で辞書とスタックは次のようになっている。

スタック: 101
101 [ dup ]
102 [ lit ]
103 [ 0   ]
104 [ >   ]

ここでimmediateワードのwhileを実行する。まず手順1、0branchコンパイルする。

スタック: 101
101 [ dup     ]
102 [ lit     ]
103 [ 0       ]
104 [ >       ]
105 [ 0branch ]

次に手順2、オフセット記録用の辞書ポインタをスタックに積み、仮の値0を置いて辞書ポインタを進めておく。

スタック: 101 106
101 [ dup     ]
102 [ lit     ]
103 [ 0       ]
104 [ >       ]
105 [ 0branch ]
106 [ 0       ]

再びコンパイルを進める。

: while-test  begin  dup 0 >  while  dup .  1 -  repeat ;

whileのあと、dup . 1 -コンパイルした時点で辞書とスタックは次のようになっている。

スタック: 101 106
101 [ dup     ]
102 [ lit     ]
103 [ 0       ]
104 [ >       ]
105 [ 0branch ]
106 [ 0       ]
107 [ dup     ]
108 [ .       ]
109 [ lit     ]
110 [ 1       ]
111 [ -       ]

ここで今度はimmediteワードrepeatの実行に移る。まず手順1、swapして対象をbeginの位置にし、'back-branchでループするコードをコンパイルする。

スタック: 106
101 [ dup     ]
102 [ lit     ]
103 [ 0       ]
104 [ >       ]
105 [ 0branch ]
106 [ 0       ]
107 [ dup     ]
108 [ .       ]
109 [ lit     ]
110 [ 1       ]
111 [ -       ]
112 [ branch  ]
113 [ -12     ]  (begin時の101) - 113 = -12

スタックトップに残っているのは、while実行時のオフセット記録用アドレスだ。そこに手順2で、現在の辞書ポインタ114へのオフセットを記録する。

スタック:
101 [ dup     ]
102 [ lit     ]
103 [ 0       ]
104 [ >       ]
105 [ 0branch ]
106 [ 8       ]  (手順2時点の辞書ポインタ114) - 106 = 8
107 [ dup     ]
108 [ .       ]
109 [ lit     ]
110 [ 1       ]
111 [ -       ]
112 [ branch  ]
113 [ -12     ]  (begin時の101) - 113 = -12

105の0branchからの順方向ブランチなので、このオフセットは正になる。

最後に、存在を忘れがちだけど、ワード;がワードretコンパイルして終了となる。

スタック:
101 [ dup     ]
102 [ lit     ]
103 [ 0       ]
104 [ >       ]
105 [ 0branch ]
106 [ 8       ]  (手順2時点の辞書ポインタ114) - 106 = 8
107 [ dup     ]
108 [ .       ]
109 [ lit     ]
110 [ 1       ]
111 [ -       ]
112 [ branch  ]
113 [ -12     ]  (begin時の101) - 113 = -12
114 [ ret     ]

while時点(105の0branch)で条件が偽なら、114まで飛び、そこからはretのみなのでワード自体が終了となる。

実装の概観

C版とJavaScript版の違いは二値ワードの定義方法のみ。

サンプルコードはC版をマクロで、JavaScript版をクロージャで短く書けるようにした。

どちらも共通して、スタックアイテムの順番に気をつける。例えばa b >というForthコードなら、bがスタックトップ、aが2番目で、中置記法だとa > bになる。

おわりに

次回はインタラクティブにコードを入力できるようにして、再帰と、リターンスタックの操作を追加する。

そろそろwikiとかに移した方が見やすいかな……と思案中。

広告を非表示にする