サブルーチンコール
自分でコンパイラやインタープリタを作ろうとしている人がみるかも知れないということで、思いっきり基本から書いてみる。
マシンインストラクション
ネイティブコード方式でサブルーチンを呼び出す場合に用いるのは、基本はCALL（コール）インストラクションである。
インストラクションとは「教示」というような意味だが、「マシン インストラクション」で「機械命令」と訳されるようである。
計算しろとかデータを移動しろとか、コンピュータの基本的動作を命令する符号で、機械の種類毎に違う決まった数値で表されている。
コンピュータの動作に結びつく実行コードはメモリーに配置されているのであるから、要は、実行したいコードのあるメモリーアドレスを取って、そこに実行を飛ばせばよいのである。現在実行している場所のメモリーアドレス値は、IPとかPCと呼ばれる特別なレジスターで管理していることが多い（次の機械命令の頭を指している）。そのレジスターの値は、普段は各インストラクションのサイズ毎にジワジワ先に進んでいく（大きくなっていく）のだが、CALLとかJUMP（ジャンプ）のインストラクションは、その値を飛躍的に変化させる機械命令なわけである。
実行位置を飛ばすには、絶対アドレスによるものと、相対アドレスによるものがある。ちなみに、アドレスというのは住所のことだが、メモリー内の場所を表す数値である。地番ともいう。
絶対アドレスというのは要するに飛びたい先のメモリ地番の数値をそのまま使う方法、相対アドレスというのは現在実行中のコードの地番から飛ぶ先の地番までの数値差を使う方法である。実行個所を指しているIPレジスタの操作としていえば、絶対アドレスでは、その数値を直接ロード（代入）すればいいし、相対アドレスでは、数値差を足し算すればよいのである。実際、CALL、JUMPインストラクションはそういう動作をする。
CALLとJUMPの違いは、CALLは戻ってくることを前提に飛ぶのに対して、JUMPは行ったっきり、ということである。そのため、CALLでは、戻ってくるべき場所の地番をまず保存しておかないといけない。これに使われるのがリターンスタックである。つまり、CALLは、現在実行中のインストラクションの次のインストラクションの場所（これがIPに入っている）を、まずリターンスタックに保存して、スタックのトップの場所を合わせた後で、それからIPの値を変えて飛ぶという手順になる。CALLの機械命令一つで、これらを自動的に行うわけである。JUMPは行ったっきりなので、リターンスタックの操作が必要ない。したがって、その分操作は軽いということになる。CALLはサブルーチン呼び出しに使われるのに対して、JUMPは条件分岐とかループに使われるのである。
各ワードのデータは、それぞれサイズは違うが、基本パッケージとして、メモリーのまとまった領域を占めている。そこには、ワード名文字列などのデータとともに、実行コードが格納されている。ネイティブコード方式なら機械命令の塊である。そのような各辞書領域はリストとしてつながっている。辞書検索では、そのリストを手繰って必要なワードのパートを捜し出し、そこにある機械命令のアドレスを獲得するのである。
辞書中のワードリンク
この辞書のリスト構造の仕組みは、基本は、一方向リンクである。新しく定義したものから古いものに向けてつながっている。もちろん、効率化のためにツリー状にするとかも考えられる。けれども、forthでは、辞書検索をするのはコンパイル時であるし、何万もワードを定義するのは滅多にないことなので、機構を複雑にすることはあまり実益がない。
リンクを手繰る
大抵、各ワードの辞書フィールドの冒頭に、リンク用フィールドがある。ここに、隣のワードとの間の距離を格納するのである。普通は２バイトもあれば十分なのだが、余裕をとって４バイト数にしてある。格納場所のアドレス間の相対アドレスになるので、格納場所はVARIABLEのようなものと考えられる。リンクを手繰っていくには、
VARIABLE LINK-FIELD
LINK-FIELD dup @ +
でよいのである。もっとも、"dup @ +"はDISPLACEというワードで定義されているので、
LINK-FIELD displace
で終わりである。（さらに細かくいうと、Mopsでは辞書が前に飛ぶことも考えるので、64ビット環境のiMopsでは、4バイト数を符号付きにするために、@の代わりに@Xというワードを使う。）
リンクを張る
では、リンクを張るときにはどうするかというと、
addr LINK-FIELD tuck - swap !
とやるのである。ここで、addrはリンク先のアドレスで、上のdisplaceで取り出せる数値である。
何をやっているかというと、(addr - LINK-FIELD)の引き算結果をLINK-FIELDに格納しているのである。スタックを追えば、
addr LINK-FIELD
tuck \ LINK-FIELD addr LINK-FIELD
- \ LINK-FIELD (addr - LINK-FIELD)
swap \ (addr - LINK-FIELD) LINK-FIELD
!
である。
このtuck以下の部分も１つのワードになっており、Mopsでは伝統的にDISPL!というワード名になっている。つまり、
addr LINK-FIELD displ!
とすれば、LINK-FIELDに差分が格納されるのである。
と、このようにワードリストは極めて単純な一方向リンクであり、ワード検索はDISPLACEを繰り返しながらリンクを遡っていくのである。大抵のforthのワードリストも、このような仕組みであると思われる。
このリンクフィールドから、そのワードのコード辞書パートが始まる。そこには以後変動しないデータが何種類か書き込まれる。ネイティブコード実装のforthなら、内容に当たる機械命令コードも書き込まれている。マシン語で呼び出すことができるためには、リンクフィールドから、その機械命令コードの先頭アドレスに到達できるようにしておく必要がある。Mopsの場合、ワード名文字列が機械命令前のデータ域に含まれ、その長さは不定になるので、いくつか計算をしないと到達できない。その計算は、まず絶対XTまで到達し、そこからもう一度計算して機械命令に到達する。XTに到達する計算は、WBASE>XTというワードに固めてある。機械命令コードのアドレスが分れば、呼び出し部分のアドレスを取って、前から後を引き算をすれば、相対アドレスによるCALLのコードがコンパイルできる。辞書フィールドの内容をどうするかは、実装する人が判断すればよい。IMMEDIATE指定されたワードは、大抵、辞書フィールドのどこかにフラグを立てることによって、一般のワードと識別するので、最低限、フラグのためのスペースは必要だろう。
入り口と出口
リストは糸というか鎖のようにつながっているわけで、両端がある。最後の端は0を格納することによって識別するのが簡単である。確か、番兵とかいうやつである。Mopsのワードリストは、最初のワードのリンクフィールドは0とすることで、終わりを告げている。そこまで行ってみつからなければ、そのワードは定義されていない、というエラーメッセージをだしてabortすることになっている。
以上が出口の話だが、入り口は、何かのワードパートのリンクフィールドではなく、決まった場所に出発点を配置している。Mopsでは、そのアドレスはCONTEXTという名前でポイントされている。
ワード検索は、このCONTEXTを解くことから始まる。
CONTEXTのあるメモリーフィールドには、そこのアドレスから、いちばん最近に定義されたワードのリンクフィールドまでの、アドレス差の値が格納されている。したがって、CONTEXTもまたそのアドレスを残すVARIABLE型変数として、
CONTEXT displace
とすれば、最初のワードのリンクフィールドのアドレスが獲得できる。探しているワードの名前の文字列は何処かに格納しておいて、辞書内のワードパートのワード名データと比較して、該当ワードであるかチェックする。ダメなら、今獲得したリンクフィールドアドレスにまた、displaceを作用させれば、次のワードに移ることができる。ワードのリンクフィールドには、その前に定義されたワードのリンクフィールドまでの距離が格納されているからである。
リストへの追加
というわけで、すでに述べたように、ワードのリストは、新しく定義したものから、前に定義されたものへとつなぐのである。今新しくワードを定義してリストに追加しようとするとき、直前に定義されたワードはどこで分るかというと、CONTEXTでわかるのである。つまり、CONTEXTから、直前に定義されたワードのリンクフィールドアドレスまでの差が、CONTEXTの場所に格納されているのである。これはもちろん、上の、検索開始のときのアドレス獲得と同じ方法で取れる。そこで、新しいワードのリンクフィールドアドレスをLINK-FIELDと書いて、
CONTEXT displace LINK-FIELD displ!
とすれば、新しいワードのリンクフィールドには、直前のワードのリンクフィールドまでの差の値が格納される。
それに加えて、CONTEXTの中身を、最新のワードに更新しておくには、
LINK-FIELD CONTEXT displ!
とする。
これで、新ワードが１つ、リストに追加されたことになる。次からの検索は、今定義したワードから始まって順々に遡っていくことになるのである。
ただし、ワードリストの最後の端は０にしておかないといけない。上のコードをそのままだと、CONTEXTが空っぽ状態の最初のワードのリンクフィールドに、CONTEXTのアドレスにリンクが張られてしまう。これでは終わりのない循環リンクである。そんなわけで、CONTEXTの中身が０であるときには、最初の行は実行しないことにしなければならない。これをまとめると、
CONTEXT @
IF CONTEXT displace LINK-FIELD displ! THEN
LINK-FIELD CONTEXT displ!
となる。THENはforthではIF構造の終結部分の印であることに注意。
CONTEXTが何回も出てくるのでスタック操作して書くとすると
CONTEXT dup @
IF dup displace LINK-FIELD displ! THEN
LINK-FIELD swap displ!
となる。LINK-FIELDも一回で済ませられないこともない、
CONTEXT LINK-FIELD over @
IF over displace over displ! THEN
swap displ!
最初のコードが多分いちばん読みやすい。最後のはスタック効果の注がないと何してるのかよく見ないとわからない。
ワード検索
ワード検索は、通常、ワード名の比較で行う。検索は、FINDというワードを用いることになっているが、ソースコードの字句解析からワード名が獲得されてパラメターとして渡される。仮にワード名をW-NAMEとしておこう。辞書内のリンクフィールドのアドレスから、比較用ワード名に至るワードをLFD>NMF（Link-Field to Name Fieldである）とし、リンクフィールドアドレスからワードのXT（後で説明する）を取るワードをLFD>XTとする。すると、検索の内容は大体次のような形になる。
: FIND { W-NAME \ ^lfd -- xt true | w-name false }
CONTEXT displace -> ^lfd
BEGIN ^lfd @
WHILE ^lfd LFD>NMF W-NAME S= IF ^lfd LFD>XT true EXIT THEN ^lfd displace -> ^lfd
REPEAT
^lfd LFD>NMF W-NAME S= IF ^lfd LFD>XT true ELSE W-NAME false THEN
;
WHILEは0のときにループを抜けるワードなので、リストの先頭のワードは調べられないことになってしまう。そこで、最後の行が、もう一回だけチェックするのである。見つかったときはXTとtrueを返し、見つからないときは渡されたワード名とfalseを返す。
ここでは、W-NAMEは名前付きパラメターに、リンクフィールドは局所変数に格納し、いわゆるlocalsを利用した。Mopsでは何度も参照される値はこの方がコードの実行が速い。つまり、これはMops風のコードである。
上のコードに^lfdやW-NAMEが頻出するのを見て、局所変数無しだとキツいのではないかと思うかも知れないが、実はそうでもない。書いてみると、
: FIND ( w-name -- xt true | w-name false )
>R CONTEXT displace
BEGIN dup @
WHILE dup LFD>NMF R@ S= IF R> drop LFD>XT true EXIT THEN displace
REPEAT
dup LFD>NMF R@ S= IF R> drop LFD>XT true ELSE drop R> false THEN
;
まあ、どちらにしても、サッとみて理解できるにはかなり慣れが必要である。
２つ目のコードは、主なデータの１つをデータスタックに、１つをリターンスタックに置くことで、かなり楽になっている。むしろコードはこちらの方が短い。
方針としては、変化していく値はデータスタックに、ずっと同じ値で保たれるものはリターンスタックに置くのがよいと思われる。というのは、リターンスタックの値上への演算には制約が多いからである。
局所変数を使い慣れると、上のようなスタックの特性を考えて分けるという発想が薄れてくる気もする。
CALLのコンパイル
ワードのXTが取れたら、そこから、機械命令実体のある場所を解く。
XTというのは、execution token（エグセキューション トークン）の略であり、無理に訳せば実行標である。ワードを特定する数値であり、辞書内に定義されている、少なくともサブルーチンに当たるワードには、全て付帯している。それをEXECUTEというワードに喰わせて、ワード実行できたりするが、大抵、その値からちょっとした計算で、該当ワードの辞書内のいろいろなデータにアクセスできるようになっている。このXTからマシンインストラクションの先頭のメモリーアドレスを取るのである。
そうした上で、現在コンパイル中のコードのアドレス、これはMopsではCDPというValue変数で管理されているが、それとのアドレス差を用いて、相対コールをコンパイルすれば良いわけである。ただし、この場合、CALLの直前までのコードは全て機械命令にコンパイルされてしまっていなければ、現在のアドレスを確定できない。iMopsでは、CALLがあったら、まずそこまではコンパイルするようになっている。理屈の上ではCALLがあってもとりあえず必要なデータだけ保存しておいて、実際の機械命令を書き出すのはできるだけ先延ばしして、仮想状態のうちにできる限り効率化するという方法も考えられる。けれども、X86-64だと、レジスタの数もそれほど多くもなく、あまり意味がなさそうなので、iMopsでも、CALLでブロックを切ることにした。
スタックアイテムのレジスタ渡しとか、局所変数の処理は、別のページでの説明に回すことにする。
一般化可能性
と、現実のforth系言語、特にiMopsでの関数呼び出し実装を説明してみたが、この方法は静的リンカーの実装と考えてもよいのである。
例えば、既定義関数について、内容となる機械命令の塊は別の場所にあるとしても、そこへの参照を含んだ関数情報リストを作っておいて、他の関数定義内で関数名に出会ったなら、そのリストを手繰って検索し、情報を得て、適切な準備コードとCALLをコンパイルすればよい。
特に難しいことは、forthで書く限りは何もない。全てが直接的だからである。他言語ではそうもいかないらしい。
基本的に機械命令のコンパイルは、必要なコード断片を準備して、情報をフラグ追加しつつ、ヒープに配置したバイトアレイに詰めていくという
手順になるのは、どの言語でも同じであろうと思われる。Forth系では、それがプログラム上予定された動作であるという違いがあるだけである。
最終更新：2019年03月08日 23:54
