スレッデッド・コードの内部インタプリタ

本棚を整理していたところ、原 通宏「Z80版 FIG-FORTHの解析」(1981年 CQ出版) が出てきました。懐かしくなってひととおり目を通した上で、懐古趣味にふけってみます。この文献は、8080 版 FIG-FORTH 1.1 (pdf) を原氏が Z80 に移植したソースコードに解説を加えたものです。

FORTH では手続きのことを語 (ワード) と呼びます。語は、仮想コードで記述された 2 次語と、ホスト・プロセッサの機械語で記述された 1 次語の 2 種類に加えて、様々なグローバル変数や配列も語になっています。実行定義を含む語は名前とコードの組で、名前は 7 ビット ASCII 文字列とビット・フラグ、次の語への単方向リンクからなります。FIG-FORTH 1.1 は、名前の長さフィールドは 5 ビット、つまり最大 31 文字で、1 ビットのフラグ 2 つからなります。名前フィールドは先頭バイトと末尾バイトの MSB を 1 として、間の MSB はゼロにします。コードはホスト・プロセッサの機械語で記述されたインタプリタへのポインタと、語の定義そのものの組になっています。例えば、スタックのトップとセカンドのうち小さな方を選択する 2 次語 MIN を次のように記述します。

/* : MIN 2DUP > IF SWAP ENDIF DROP ; */
        .byte       3+0x80,'M,'I,'N+0x80  /* name field */      
        .word       DABS-7          /* link field: 直前の語の name field */
MIN:    .word       DOCOL           /* code field: この語のインタプリタへのポインタを含む */
        .word       TDUP
        .word       GREAT
        .word       ZBRAN,MIN1-.    /* 制御構造は条件分岐命令にコンパイルされている */
        .word       SWAP
MIN1:   .word       DROP
        .word       SEMIS

MIN のインタプリタは DOCOL で、MIN の定義は TDUP から SEMIS までです。DOCOL から SEMIS まではすべてホスト・プロセッサの番地であり、アセンブリ上ではラベルです。つまり、他の語で、語 MIN を使つとき、ラベル MIN をデータにします。

FIG-FORTH 処理系では、すべての語がそれぞれ自分自身のインタプリタを知っていて、それが語のふるまいを決定します。MIN は 2 次語として実行されるインタプリタ DOCOL が指定してあります。他には、左辺値をスタックへプッシュする DOVAR インタプリタを持つグローバル変数としてふるまう語があります。スタックの整数値から配列要素の左辺値を計算してスタックへプッシュする配列用インタプリタや、定数値をスタックへプッシュする定数用インタプリタなど、複数のインタプリタが利用できるようになっています。インタプリタ自身は機械語で記述してありますが、2 次語で定義したインタプリタを実行するトランポリンをコンパイルする <BUILDS >DOES のような機構も利用できます。

では、機械語で定義してある 1 次語のインタプリタは何になるのかというと、自分自身をインタプリタに指定します。例えば、MIN が使っている SWAP は 1 次語で、スタックのトップとセカンドを交換する働きをします。アセンブリAT&T 形式で書いています。

        .byte       4+0x80,'S,'W,'A,'P+0x80
        .word       DROP-7
SWAP:   .word       .+2             /* code field: インタプリタは自分自身。*/
        loadw       2(%sp),%wa
        loadw       0(%sp),%ca
        storew      %ca,2(%sp)
        storew      %wa,0(%sp)
        jump        I2NEXT

いまさら Z80 はないので、FORTH の動作説明用の架空のプロセッサで書いています。バイト・アドレッシングのレジスタ・マシンで、16 ビット幅の汎用レジスタを持ち、奇数番地・偶数番地のどちらからでも 16 ビットのメモリの読み書きが可能とします。FORTH 用プロセッサは、機械語のプログラム・カウンタを除いて、他に 5 本のレジスタをもちます。

%ip     実行中の 2 次語の次の 2 次語のアドレスを指す。
%wa     実行中の 2 次語を含む語のコード・フィールドを示す。作業レジスタに使って良い。
%ca     実行中の 2 次語を含む語のコード定義の先頭を示す。作業レジスタに使って良い。
%rs     2次語のリターン・スタック・ポインタ。スタックはアドレスが減る方向へ伸びる。
%sp     演算スタック・ポインタ。スタックはアドレスが減る方向へ伸びる。

さて、1 次語の定義の終わりがリターン命令ではなくジャンプ命令になるのが FORTH 仮想マシンの仕組みです。リターン・スタックへ戻り番地をプッシュ・ポップするのは 2 次語だけで、1 次語はリターン・スタックを使いません。

1 次語が最後にジャンプする先の I2NEXT は内部インタプリタと呼ばれ、語ごとに指定されているインタプリタへ間接ジャンプをおこないます。I2NEXT と語ごとのインタプリタと 1 次語がセットになって、いわばループ文の中の巨大な switch 文になっていて、I2NEXT からは二重間接ジャンプで目的の機械語片へ飛んでいきます。この一連の仕掛けをスレッデッド・コードと呼びます。スレッデッド・コードは、FORTH の生みの親であるチャールズ・ムーアが発明した FORTH を FORTH たらしめている中核技術です。

I2NEXT: loadw       (%ip),%wa
        addw        $2,%ip
        loadw       (%wa),%ca
        jump        *%ca            /* pc = memory[memory[ip++]] */

スレッデッド・コードは機械語で説明するのがわかりやすい概念ですが、 C 言語で扱うこともできるそうで、次のウェブ・ページがいくつかものテクニックを紹介しています。

http://www.complang.tuwien.ac.at/forth/threaded-code.html

リターン・スタックの操作をおこなうのは 2 次語のインタープリタ DOCOL と、2 次語の最後の語である SEMIS です。DOCOL は語コロンと組になって定義されています。SEMIS は 1 次語で、語セミコロンがコンパイル時にコンパイル中の語に書き加えます。DOCOL はリターン・スタックへレジスタ ip を退避して 2 次語の定義部分の実行に移します。SEMIS は通常のリターンにあたりレジスタ ip を元に戻します。

/* : : ?EXEC !CSP CURRENT @ CONTEXT ! CREATE ] ;CODE IMMEDIATE */
        .byte       1+0xC0,':+0x80
        .word       TSTOR-5
COLON:  .word       DOCOL
        .word       QEXEC,SCSP,CURR,AT,CONT,STORE,CREAT,RBRAC,PSCOD
DOCOL:  subw        $2,%rs
        storew      %ip,(%rs)       /* memory[--rs] = ip */
        leaw        2(%wa),%ip      /* ip = wa + 2 */
        jump        I2NEXT

/* ;S */
        .byte       2+0x80,';,'S+0x80
        .word       RPSTO-6
SEMIS:  .word       .+2
        loadw       (%rs),%ip       /* ip = memory[rs++] */
        addw        $2,%rs
        jump        I2NEXT

このように、FORTH の語は他のプログラミング言語の手続きとは異なり、自力でリターン・スタックを成長させるという変な性質をもっています。FORTH の起動処理では、この性質を使って、簡素なコードでいきなり 2 次語の初期化手続きの実行を始めます。

CLD:    loadw       inits0,%sp
        loadw       initr0,%rs
        leaw        COLD,%ip
        jp          I2NEXT

/* : COLD EMPTY-BUFFERS 0 DENSITY ! FIRST USE ! FIRST PREV ! ... */
        .byte       4+0x80,'C,'O,'L,'D+0x80
        .word       WARM-7
COLD:   .word       DOCOL
        .word       MTBUF,ZERO,DENSTY,STORE,LIT,BUF1,USE,STORE,LIT,BUF1,PREV,STORE,...

便利と言えば便利ですけど、この方式の欠点は末尾呼び出しをジャンプにしにくい弱点があり、スタック処理言語なのに深い再帰に弱く、制御構造のループ形式を多用する結果につながります。