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

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

私に教えられることなら

Forthの仕組み - 制御構造if

前回

今回は、ワードbranch0branchを使い、Forth自身で制御構造ifを作っていく。

サンプルコード

追加ネイティブワード

まずいくつかのネイティブワードを追加する。また、今回からスタックエフェクトを説明に使う。

スタックエフェクトとは、ワードの実行前後のスタックの状態を表すコメントで、例えばワード+なら( a b -- c )のように表す。

aとb、二つの値をとり、加算した新しいcという値をスタックに残す、と読む。--がワード実行の前後を区切る。といっても単なるコメントなので、自由にいろいろ書いてもいい。

このとき、スタックの上にあるのはbの方だ。1 2 +というコードで+を実行するとき、スタックは上から順に2 1となる。

つまり、( a b --というスタックエフェクトのa bの順番はコードで書く順番と同じになる。

メモリ操作

アドレスによるメモリ内容の取得と書き換えをできるようにする。

ワード@ ( addr -- value )は、メモリaddr番地の内容を取ってきて、スタックに置く。

ワード! ( value addr -- )は、メモリaddr番地の内容をvalueに書き換える。

例えば次のようなコードが書ける。

1 12 !    ( アドレス12番地の内容を1に書き換える   )
12 @      ( スタックトップに12番地の内容1を置く   )
1 + 12 !  ( それに1を足して、12番地に再び書き込む )
12 @ . cr ( 12番地の内容を表示して改行 -> 2 )

: x 12 ;  ( アドレス12を置くxというワードを作る   )
1 x !     ( ここからやってることは上と同じだが、  )
x @       ( xは他の言語の変数みたいにみえる。     )
1 + x !
x @ . cr

スタック操作ワード

スタックの値を、入れ替えたり複製したりと操作する次の3つのワードを定義する。

  • dup ( x -- x x ) スタックトップの複製
  • swap ( a b -- b a ) スタックトップの交換
  • drop ( x -- ) スタックトップを捨てる

スタックを操作するためには、push/popを使う素直な方法と、スタックポインタを直に使う効率よい方法がある。

後者について、例えばswapの場合、次のようにスタックポインタを使えば交換できる。

// dstackは配列によるデータスタック、dspはスタックトップアドレス(空の場所)
// dspが+方向にスタックは伸びていくとする
var tmp = dstack[dsp - 1];
    dstack[dsp - 1] = dstack[dsp - 2]; // 2番目を1番目に
    dstack[dsp - 2] = tmp;

push/popを素直に使うと、次のようなコードになる。

var a = dpop(),
    b = dpop();
dpush(a);
dpush(b);

3命令が4命令になったが、dpopとdpushの中でスタックポインタも操作しているため、実際は8命令以上になる。

今回のサンプルはスタック操作ワードの動きを掴んでもらうためにpush/pop方式で書いた。理解したら、試しにスタックポインタを直接操作するように書き換えてみてほしい。

immediate!

最後に定義したワードのimmediateフラグを立てるimmediate! ( -- )を定義する。

対象は最後に定義したワード(latest)、フラグも立てるのみと限定された動作のワードになる。immediateフラグを外したり、latest以外のimmediateフラグを立てようとする場面は少ないためだと思う。

もしかしたら、フラグとアドレスを受け取り、immediateフラグにセットするset-immediate ( flag addr -- )みたいなものを定義したほうが、便利になる場面もあるかもしれない。

set-immediateを作っておいて、例えばフラグを0/1で管理するなら

: ON 1 ;
: OFF 0 ;
: immediate! ON latest @ set-immediate! ;

のようにimmediate!は定義できる。

ここからは余談だけど、伝統的なForthではIMMEDIATEというワード名みたいだ。自分の好みで、何かを破壊するワードは最後に!をつけて注意を引いている。

減算

基本的なことだけど、Forthの減算/除算の順番は( a b -- a-b )となる。ネイティブコードで減算/除算を書く時に、どちらが先か気を付ける。

一応例も挙げる。1行目は1、2行目は-1が出力される。

2 1 - .
5 6 - .

また、これもpush/popではなく、直接スタックポインタを使って演算した方が速い。

find, >cfa

find ( str -- addr )は、read-token>などで読み込んだ文字列を使って、ワードのヘッダアドレスを探してスタックに置く。

例えばread-token> + findでワード+のヘッダアドレスを取得する。

後方参照を避けるため、JavaScript版・C版ともにfind関数を前に出す。

>cfa ( addr -- cfa )は、ヘッダアドレスをCFAに変換する。JavaScript版・C版ともにtoCFA関数を使う。

ちなみに、Forth文字列の場合は文字列のアドレスと長さがそれぞれ別なので、find ( str-addr str-len -- addr )となる。

dict-here

辞書ポインタを取得するdict-here ( -- addr )と、設定するdict-here! ( addr -- )も定義しておく。

スタックエフェクトからその動作を想像して欲しい。

branch

今回のメインテーマ、ワードbranch0branchを作る。

無条件ジャンプ branch

ワードbranchは、まずlitのように辞書の次の値を読み取る。そして、それを使ってジャンプして実行の流れを変える。

以降、その読み取った数値のことをオフセットと呼ぶ。

branchの動作は、オフセットをnpに足してNEXTルーチンを実行するだけだ。

詳しく見てみる。branch実行時、ipとnpが次のような状況になっているとする。

      101 [ branch ] ip -> branchのCFA
np -> 102 [ 3      ]
      103 [ lit    ]
      104 [ 5      ]
      105 [ +      ]
      106 [ ret    ]

このとき、branchはまずnpが指すアドレスの内容3を取り出し、npに足す。

すると、npは102 + 3で105を指す

      101 [ branch ] ip -> branchのCFA
      102 [ 3      ]
      103 [ lit    ]
      104 [ 5      ]
np -> 105 [ +      ]
      106 [ ret    ]

あとはbranch内のNEXTルーチンで次の状況になり、ワード+が実行される。

      101 [ branch ]
      102 [ 3      ]
      103 [ lit    ]
      104 [ 5      ]
      105 [ +      ] ip -> +のCFA
np -> 106 [ ret    ]

lit 5が飛ばされたことになる。

無条件ジャンプは、後で説明するif ... else ... thenでのelse部分の迂回に使う。

条件つきジャンプ 0branch

ワード0branchは、スタックトップが0の場合のみbranchと同じ動作を行う。

例としてコンパイルされたlit 0 0branch 3 lit 5 + retというコードの動作を見てみる。

始めのlit 0が実行済みで、スタックには0が乗っているとする。

スタック: 0
      099 [ lit     ]
      100 [ 0       ]
      101 [ 0branch ] ip -> 0branchのCFA
np -> 102 [ 3       ]
      103 [ lit     ]
      104 [ 5       ]
      105 [ +       ]
      106 [ ret     ]

0branchはスタックトップを取り出し、0なので、branchのときと同様にnp(102)にオフセット(3)を足し、105の+にジャンプする。

一方、lit 1から始まる次の場合はジャンプを行わない。

スタック: 1
      099 [ lit     ]
      100 [ 1       ]
      101 [ 0branch ] ip -> 0branchのCFA
np -> 102 [ 3       ]
      103 [ lit     ]
      104 [ 5       ]
      105 [ +       ]
      106 [ ret     ]

この場合、そのまま0branch内のNEXTルーチンを動作させると、102の3がCFAと見なされてしまう。

それを避けるため、スタックトップが0以外の場合は、npをインクリメントしてから0branch内のNEXTルーチンに移る。

      099 [ lit     ]
      100 [ 1       ]
      101 [ 0branch ] ip -> 0branchのCFA
      102 [ 3       ]
np -> 103 [ lit     ]
      104 [ 5       ]
      105 [ +       ]
      106 [ ret     ]

これで、lit 5 +と実行されることになる。

サンプルコード

まずはbranchを使った例。

interpret(": skip-test 1 branch execute-mode>> 3 push-dict compile-mode>>  9 . ;");
interpret("skip-test");

この定義で、ワードskip-testの中身はlit 1 branch 3 lit 9 . retという形にコンパイルされる。オフセット(3)によってlit 9の部分が飛ばされ、全体でlit 1 . retという流れになって1が表示される。

次に0branchを使った例。

// 2は数字ではなく、前に定義したワード名なので、lit 2 の形にはコンパイルされない。
interpret(": cond-jump-test 0branch execute-mode>> 4 push-dict compile-mode>> 2 . ret 3 . ;");
interpret("1 cond-jump-test"); // 2
interpret("0 cond-jump-test"); // 3

ワードcond-jump-test0branch 4 2 . ret lit 3 . retという形にコンパイルされる。2を置くワード2を前に定義したので、lit 2という形にはならないことに注意する。

オフセット(4)によって、

  • スタックトップが0の場合は2 . retの部分を飛ばす
  • スタックトップが0以外の場合は2 . retを実行し、retによってワードを抜ける

という動作になる。

制御構造 if

0branchの実装によって、条件分岐できるようになった。しかしこのままだと毎回手でオフセットアドレスを計算する必要がある。

そこで、自動的にオフセットを計算してコンパイルするifワードとthenを実装する。

if ... thenは、0branch thenの次までのオフセット ...という形にコンパイルされる。スタックトップが0の場合はif ... thenの間が飛ばされるので、この実装では0ならば偽、それ以外なら真となる。

immediateワードの動作

実装の前に、一度immediateワードの動作を確認しておく。

コンパイルモード中、immediateワードを読み込んだ場合、Forth処理系はコンパイルせずにすぐ実行する。

gforthでの例を書く。呼び出されるとyo!と表示するだけのimmediateワード、yoを定義する。

: yo ." yo!" ; immediate  ok

普通に呼び出すと、ただ実行される。

yo yo! ok

しかし、yoを他のワード定義中に書くと、コンパイルされずに即実行される。

: yo-yo yo yo ; yo!yo! ok

何もコンパイルされてないので、yo-yoを実行しても何も起こらない。

yo-yo ok

ちなみにimmediateワードyoコンパイルしたい場合は、ワードpostponeに続けてワード名を書けばコンパイルできる。

: yo-yo postpone yo postpone yo ; redefined yo-yo   ok
yo-yo yo!yo! ok

コンパイルワード

ワードifthenはimmediateワードにする。それ自身が辞書にコンパイルされるわけではない。

どういう構造を作りたいかもう一度確認する。if ... then0branch オフセット ...となるので、まずifを実行するときに、0branchを辞書にコンパイルする必要がある。

例えば: compile-0branch lit 0branch push-dict ;というワードを実行すると、0branchをコンイパルすることができる。litのせいで少し混乱するかもしれないけど、この定義は次のように素直にコンパイルされる。

[ litのCFA       ]
[ 0branchのCFA   ]
[ push-dictのCFA ]

数値をコンパイルするときはlitが自動でコンパイルされるけど、litコンパイルするときに何か特別なことが起きるわけではない。

このlitが実行されると、0branchのCFAがスタックトップに積まれて、次はpush-dictが実行される。push-dictによって0branchのCFAが実行時点の辞書位置(dict-here)に積まれる、つまりコンパイルされる。

Forthのコンパイルとは単にCFAを辞書に追加することなので、こういうことができる。

compile> ( -- )

何かワードをコンパイルするワードを作りたいとき、毎回lit word-name push-dictみたいな形にするのも面倒だ。パッと見てわかりやすくもない。

そこで、compile> word-nameというコードを書くと、そのコードの実行時点でword-nameコンパイルできるようにする。

compile>の動作に必要なのは、

  1. litを辞書に追加する
  2. トークンを読み込み、CFAを探して辞書に追加する
  3. push-dictを辞書に追加する

の3つだ。

また、compile>が実行されるのはコンパイル時でないといけない。

と、コンパイル動作が二重になっている。

compile>の手順2は、read-token> find >cfa push-dictでできる。1と3は0branchコンパイルするコードのときと同じなので、compile>は次のような定義になる。

: compile>
  lit lit push-dict
  read-token> find >cfa push-dict
  lit push-dict push-dict ; immediate!

これとは別にlitpush-dictコンパイルしたいときも結構あるので、ワードを追加しておいた。

: 'lit lit lit push-dict ;
: 'push-dict lit push-dict push-dict ;

これでcompile>の定義は以下のようになる。

: compile> 'lit read-token> find >cfa push-dict 'push-dict ; immediate!

if ... then

if ... thenの定義に取り掛かる。

実例が欲しいので、0以外のときだけインクリメントして、条件に関係無く数字を出力するコードif 1 + then .コンパイルを考えてみる。

以降は、ワードのコロン定義中など、コンパイルモード中の話になる。

コンパイル後、辞書は次の形になっていてほしい。アドレスは適当で、ワード名はそれのCFA。

101 [ 0branch      ]
102 [ (オフセット) ]
103 [ lit          ]
104 [ 1            ]
105 [ +            ]
106 [ .            ]

if ... thenで実現する手順を書く。まずifの実行時に

  1. 0branchコンパイルする
  2. dict-hereでオフセットを置きたいアドレス(102)を置く。
  3. 仮の値0push-dictしておいて、辞書ポインタを次(103)に進めておく

次にthen実行時

  1. dict-hereで辞書ポインタ(106)を取り出す
  2. 2で置いておいたアドレス(102)からオフセット(106 - 102 = 4)を計算
  3. さらにそのアドレス(102)にオフセット(4)を書き込む。

となる。コードは以下のようになる。thenの手順はワードelseでもう一度使うので、save-offsetというワードにまとめておく。

: if compile> 0branch dict-here 0 push-dict ; immediate!
: save-offset dup dict-here swap - swap ! ;
: then save-offset ; immediate!

ややこしいところなので、もう一度順を追って辞書とスタックの内容を見てみる。

コンパイル中にifが実行されたとき、まず手順1で0branchコンパイルされる

スタック:

101 [ 0branch      ]

次に手順2で、辞書ポインタがスタックに積まれる。今0branchを置いた次の辞書アドレスだ。

スタック: 102

101 [ 0branch      ]

手順3、アドレス102はオフセットを保存するために空けておきたい。とりあえず0でも置いて、辞書ポインタを進めておく。(辞書ポインタを直接操作してもいい)

スタック: 102

101 [ 0branch      ]
102 [ 0            ] 

さて、コンパイルモード中のimmediateワードifの実行が終わったので、それ以降は再びコンパイルに戻る。if 1 + then .ifあと、1 +コンパイルが終わった時点でこうなる。

スタック: 102

101 [ 0branch      ]
102 [ 0            ]
103 [ lit          ]
104 [ 1            ]
105 [ +            ]

ここでimmediateワードthenの実行に移る。まずスタックトップのアドレスを複製(dup)しておく。そして手順1、辞書ポインタをdict-hereで取り出し、スタックに置く。スタックは右が上とする。

: save-offset dup dict-here swap - swap ! ;dup dict-hereの動作になる。

スタック: 102 102 106

101 [ 0branch      ]
102 [ 0            ]
103 [ lit          ]
104 [ 1            ]
105 [ +            ]

手順2、オフセットを計算する。スタックだけ見てみる。現在の辞書ポインタ(106)から、オフセットを入れる場所(102)を引けばいい。Forthの減算は( a b -- a-b)なので、交換してから引く必要がある。

102 102 106に対しswap102 106 102になる。

102 106 102に対し-102 4になる。

これが: save-offset dup dict-here swap - swap ! ;swap -の動作で、この時点で辞書とスタックは次のようになっている。

スタック: 102 4

101 [ 0branch      ]
102 [ 0            ]
103 [ lit          ]
104 [ 1            ]
105 [ +            ]

最後に手順3、ワード!を使って102番地にオフセット4を書き込む。!のスタックエフェクトは( value addr -- )だけど、今スタックは102(addr) 4(value)となっているので、swapしてから!を実行する。実行後の状況は以下のようになる。

スタック:

101 [ 0branch      ]
102 [ 4            ]
103 [ lit          ]
104 [ 1            ]
105 [ +            ]

thenの実行が終わり、コンパイルに戻る。if 1 + then .の最後、.コンパイルして終了。

101 [ 0branch      ]
102 [ 4            ]
103 [ lit          ]
104 [ 1            ]
105 [ +            ]
106 [ .            ]

if ... thenは以上の定義・動作で実現できる。

if 条件が真のとき thenなので条件が偽の場合にも分岐したい。そのためelseワードを作ることにする。

else

if 真の場合 thenに、条件が偽の場合も加えたif 真の場合 else 偽の場合 thenという構造を追加する。

if ... thenでもif ... else ... thenでも、どちらでも書けるようにしたい。

辞書がどんな形になればいいだろうか?条件が真なら1、偽なら-1を足すif 1 else -1 then +というコードをコンパイルする場合で考えてみる。

以降もワードのコロン定義中など、コンパイルモードでの話になる。

まずifで置く0branchがどこに飛べばいいのか考える。0branchでジャンプするのはスタックトップが0、つまり条件が偽の場合なので、else実行時の辞書位置まで飛べばいい。

if 真の場合 else 偽の場合 thenの真の場合を実行した後はどうすればいいだろうか?else ... thenの間を実行したくない。無条件ジャンプで偽の場合を飛ばせば良さそうだ。

以上から、if 1 else -1 then +なら、次の形にコンパイルしたい。アドレスは適当で、ワード名はそれぞれのCFA。

201 [ 0branch ]
202 [ 5       ]  207へのオフセット
203 [ lit     ]  ifの次
204 [ 1       ]
205 [ branch  ]
206 [ 3       ]  209へのオフセット
207 [ lit     ]  elseの次
208 [ -1      ]
209 [ +       ]  thenの次

ではワードelseは何をすればいいだろうか?else実行時には、スタックにはifで置いたアドレス202がある。また、アドレスを一つ残しておけば、thenがそこへのオフセットを書き込んでくれる。else実行時の辞書ポインタは205を指している。

elseでやりたいことは、次の2つだ

  1. アドレス206をthenのために残しておく
  2. アドレス202に、202から207へのオフセットを書き込む

具体的な手順を書き起こしてみる。

  1. ワードbranchコンパイルする
  2. 辞書ポインタ(206)をスタックに積み、0などの適当な値をpush-dictして辞書ポインタを207に進める
  3. スタックが202 206(右が上)となっているので、swapして202を操作対象にする
  4. save-offsetを実行する

コードは以下のようになる。

: else
  ( 1 ) compile> branch
  ( 2 ) dict-here 0 push-dict
  ( 3 ) swap
  ( 4 ) save-offset
  ; immediate!

else内の番号コメントは上の手順に対応している。

サンプルコードでは以下のように分けている。

: save-else-offset swap save-offset ;
: else compile> branch dict-here 0 push-dict save-else-offset ; immediate!

これもまた詳しく動作を見てみる。

コンパイルモード中、if 1 else -1 then +if 1まで処理した時点で、スタックと辞書はこうなっている。

スタック: 202

201 [ 0branch ]
202 [ 0       ]
203 [ lit     ]
204 [ 1       ]

elseの実行に移る。

まず、手順1のワードbranchコンパイルを行う。

スタック: 202

201 [ 0branch ]
202 [ 0       ]
203 [ lit     ]
204 [ 1       ]
205 [ branch  ]

手順2に従って、まず現在の辞書ポインタ(206)をワードdict-hereでスタックに積み、適当な値(0)をpush-dictで辞書に追加する。スタックは右が上になる。

スタック: 202 206

201 [ 0branch ]
202 [ 0       ]
203 [ lit     ]
204 [ 1       ]
205 [ branch  ]
206 [ 0       ]

手順3、swapして202を操作対象にする。

スタック: 206 202

201 [ 0branch ]
202 [ 0       ]
203 [ lit     ]
204 [ 1       ]
205 [ branch  ]
206 [ 0       ]

そして手順4、 save-offsetを実行する。このときsave-offset内でdict-hereが使われるから、202からのオフセットが計算されるのは206ではなく207ということに注意。

スタック: 206

201 [ 0branch ]
202 [ 5       ]  207へのオフセット
203 [ lit     ]  ifの次
204 [ 1       ]
205 [ branch  ]
206 [ 0       ]

あとはコンパイルしていき、thenがスタックに残っている206からのオフセットを計算・記録して、完成となる。

201 [ 0branch ]
202 [ 5       ]  207へのオフセット
203 [ lit     ]  ifの次
204 [ 1       ]
205 [ branch  ]
206 [ 3       ]  209へのオフセット
207 [ lit     ]  elseの次
208 [ -1      ]
209 [ +       ]  thenの次

コントロールフロースタックを使う場合

オフセット計算元・記録先のアドレスをデータスタックに積んで使っていると、コンパイルモード中、他のimmediateワードでスタックを使うときに気をつける必要がある。

そこで、データスタックとリターンスタックに加えて、オフセット計算用のデータを保存しておく「コントロールフロースタック」を使う実装もある。これは処理系に組み込んでもいいし、Forth自身でも作れる。(スタックを作ること自体にコントロールフローを使いたいので、処理系に組み込んだ方が楽かもしれない)

サンプルコード

C言語版・JavaScript版共通で、以下のコードで試している。

どちらも、スタックトップが偽(0)か真(0以外)かで出力する数字を変えている。

if-testでは、if ... then内でretによってワード実行を終了させて、真の場合にthenより後を実行しないようにしている。

interpret(": if-test if 4 . ret then 5 . ;");
interpret("1 if-test"); // 4
interpret("0 if-test"); // 5

interpret(": if-else-test if 6 else 7 then . ;");
interpret("1 if-else-test"); // 6
interpret("0 if-else-test"); // 7

実装の概観

今回は処理系内部に新しい機能を追加しないので、C版もJavaScript版もあまり変わらない。

ネイティブワード

もう一度実装するネイティブワードをリストアップしておく。

  • メモリ操作 @, !
  • スタック操作 swap, dup, drop
  • immediate!
  • 減算 -
  • 辞書ポインタ操作 dict-here, dict-here!
  • find, >cfa
  • ジャンプ branch, 0branch

if, then, else

コントロールフローはForthのみで定義するので、どちらもinterpret関数に同じコードを渡す。

// if
interpret(": 'lit lit lit push-dict ;");
interpret(": 'push-dict lit push-dict push-dict ;");
interpret(": compile> 'lit read-token> find >cfa push-dict 'push-dict ; immediate!");

interpret(": if compile> 0branch dict-here 0 push-dict ; immediate!");
interpret(": save-offset dup dict-here swap - swap ! ;");
interpret(": then save-offset ; immediate!");
interpret(": save-else-offset swap save-offset ;");
interpret(": else compile> branch dict-here 0 push-dict save-else-offset ; immediate!");

おわりに

図が必要。。

次はループの予定。

広告を非表示にする