拡張性のある言語 FORTH

1981年12月、コンピュータサイエンスbit誌に「拡張性のある言語 FORTH」という記事が掲載されていました。

FORTHは、1Dayセミナーを受講し興味を持っていました。そして、いろいろ勉強して1981年1月にCSK社内講習会で「マイコン用最新言語 FORTH vs PASCAL」の講師を務めました。

小さいけどパワフルなFORTH言語について

「拡張性のある言語 FORTH」という記事は、FORTHシステムの裏の仕組みなどを解説しているので、大変興味深く読みました。この記事から、重要なポイントを加筆してメモします。

Shell(殻)構造とCore(核)構造

Shell(殻)構造

処理言語はあらかじめ備えた機能に限度があり、その言語によってこの限度を超える内容をもつプログラムを記述できません。処理言語は基本ソフト（ＯＳ）が許容する限度内の機能だけを処理言語のユーザーに提供します。

Core(核)構造

FORTHシステムは中心となる基本動作（基本ワード）があり、さらに基本ワードを組み合わせた応用動作があります。FORTHのプログラムはすべてワードだけで構成し、これらのワードはシステムが提供するワードも、ユーザーが定義したワードも基本的に変わりがありません。

FORTHには、「ワードを定義するためのワード」があり、これを利用することによりマクロ機能のような働きをもつ定義用ワードを作ることが可能です。

スタックと逆ポーランド基本演算

リターン・スタック

ワードの呼び出しにおける呼び出しのネスティング（入れ子構造）やDOループのパラメータの収納などに用います。

パラメータ・スタック

演算データの置き場所やワード間のパラメータの受け渡しに用います。

算術式「(9-2)*(5+3)」は、逆ポーランド記法では「9 2 – 5 3 + *」となります。

「9から2を引いた結果と、5に3を加えた結果とを、乗算する」

日本語の語順にマッチしています。

FORTHの構造

直接スレッディング方式(DCT)

もしプログラムを極端にモジュール化して、手続き呼び出しの連続で書いたならば下記のようにCALL命令が連なることになります。

手続き呼び出し(CALL命令)は共通なのでアドレスだけを連続して並べ、実行ルーチン（インタプリタ）により同じことを実現できます。このようにアドレスの羅列によるプログラムをDCT(Direct Threaded Code)方式と呼びます。

IPは仮想プログラムカウンタで、実行するアドレスを指しています。アドレス A(S_1) , A(S_2) ,･･･ には実行可能な機械語命令があり、その末尾はRET命令があり、制御がインタプリタに戻ります。

間接スレッディング方式(ICT)

呼び出し関係が以下のようなプログラムを考えます。

MAIN
 |---- S_1
 |   |
 |   |---- S_11
 |   |   |---- S_111
 |   |   `---- S_112
 |   |
 |   `---- S_12
 |
 |---- S_2
 |   |
 |   |---- S_21
 |   |
 |   `---- S_22
 |
 |---- S_3
 |

手続き呼び出しによるプログラムは以下のようになります。

FORTHは、ICT(Indirect Threaded Code)方式で実現しています。

サブルーチンの入口は、DEF_SUBのアドレスを格納します。その次から、サブルーチンを構成するワードのアドレス（CFA:コード フィールド アドレス）を順番に格納します。サブルーチンの出口は、ENDのアドレスを格納します。アドレスENDにはRETURNのアドレスを格納しています。

IPは、仮想プログラム・カウンタです。インタプリタは、次の処理を繰り返します。

1. IPの示す参照先、すなわち呼び出すワードのCFAからアドレス(AP)を取得します。
2. IPをインクリメントして進めます。
3. 先に取ったCFAの参照先からコードアドレス(BP)を取得します。
4. コードアドレス(BP)にジャンプします。

サブルーチンの入口では、アドレスDEF_SUBにジャンプしてIPをリターン・スタックにPUSHして保存し、IPをDEF_SUBの次のワードを示してインタプリタにジャンプして戻ります。
サブルーチンの出口では、アドレスRETURNにジャンプしてリターン・スタックからIPにPOPし、インタプリタにジャンプして戻ります。

FORTHシステムは、このような小さなアドレスインタプリタで実装していますのでオーバーヘッドはほとんどありません。

ワードとディクショナリ

FORTHは、ひとつの手続きをワード(Word)と呼びます。そして、ワードはディクショナリ(Dictionary)に登録します。

ワードは、次のいずれかで定義します。

• FORTH言語によるコロン定義 ( : ワード名 操作ワード･･･ ; )
• 機械語によるCODE定義 ( CODE ワード名 命令･･･ NEXT )

いったんディクショナリに登録したワードは、同等に扱われます。

• 機械語により書いたモジュール
• FORTH言語で書いたモジュール
• システム提供のモジュール
• ユーザーが定義したモジュール

FORTHインタプリタ

ワード定義の内部構造は、ヘッダー部、名前部、リンク部、そしてワード内容の定義から構成します。

二乗を計算するSQUARワード（: SQUAR DUP * ;）を定義した場合、下記のような構成になります。

ワードは、ディクショナリからリンク部で接続しています。ワード内容の定義は、ワードのアドレス羅列になっています。

FORTHインタプリタは、アウター・インタプリタとインナー・インタプリタがあります。

アウター・インタプリタ

アウター・インタプリタは、テキスト・インタプリタです。入力したテキスト・ストリングを解釈して、ディクショナリに定義済みのワードアドレスに変換してコンパイルするか、インナー・インタプリタにより実行します。
コロン定義(FORTH言語によるワード定義)とCODE定義(アセンブラによるワード定義)の場合は、コンパイルして新しいワードをディクショナリに登録します。

インナー・インタプリタ

インナー・インタプリタは、間接スレッディング方式のアドレス・インタプリタです。アドレスが指している定義を実行してゆくことで、アドレス列をインタプリトします。ディクショナリ定義のワードは、定義済みワードのアドレスで構成します。これらのワードは、すでにコンパイル済みなので、ディクショナリ・サーチを必要としません。

インナー・インタプリタは、重要な特徴が有ります。

1. 実行が早い
2. オブジェクトの定義が非常にコンパクト
3. FORT定義はマシン独立

FORTHシステムの多くのワードはコロン定義し、インナー・インタプリタによりインタプリトします。テキスト・インタプリタも、この方式で定義しています。

FORTHのメモリ操作

大域変数と定数

大域変数を定義するとき、VARIABLE ワードを使用して変数名を指定します。

VARIABLE 変数名

• コンパイル時は、メモリに変数領域を割り当てて、変数名を新しいワードとして辞書に登録します。
• 変数名ワードの実行時は、変数領域のアドレスをスタックにPUSHします。

---

定数を定義するとき、CONSTANT ワードを使用して値と定数名を指定します。

値 CONSTANT 定数名

• コンパイル時は、メモリに定数領域を割り当てて、定数名を新しいワードとして辞書に登録します。
• 定数名ワードの実行時は、定数領域のアドレスをスタックにPUSHして、定数値をロードします。

---

メモリ ロードとストア

メモリから値をロードするとき、スタックにアドレスをPUSHして、@ワードを使用します。
メモリに値をストアするとき、スタックに値とアドレスをPUSHして、!ワードを使用します。

ワード名	機能	スタック状態	説明
@	ロード	adr → val	val＝*(adr)
!	ストア	val adr →	*(adr)＝val

定数Cと変数Aを加算して変数Zにストアする Z=C+A のコードは、以下のようになります。

    360 CONSTANT C
    VARIABLE A
    VARIABLE Z

    C @ A @ + Z !

FORTHレベル

FORTHは、複数レベルでの操作があります。

• LEVEL0 : ディクショナリからのワードを実行します
• LEVEL1 : 定義ワードを使用して新しいディクショナリ項目を作成します
• LEVEL2 : 新しい定義語を生成します

LEVEL2のFORTH定義語は、特定の型の構造を辞書にコンパイルするためのミニコンパイラと考えることができます。

「<BUILDS DOES>」機構により、コンパイル時の動作と実行時の動作を定義できます。

---

大域変数を定義する VARIABLE ワードは次のように動作します。

  : VARIABLE <BUILDS 2 ALLOT DOES> ;

VARIABLE DAT 【大域変数の定義】
0 DAT ! 【大域変数の設定 DAT＝0】

<BUILDSは、コンパイル時の動作の始まりを表します。入力ソースから次の単語を取り出し、辞書にワードエントリーを登録します。”2 ALLOT”はパラメータ領域に2バイトを予約します。
この例では、DATというワードのヘッダー部、名前部、リンク部を登録します。DOES>の直前でコンパイル時の動作は終了します。

DOES>以降は実行時の動作で、新たに登録したワードのコード部に登録します。この例では、いきなりセミコロン(;)でVARIABLEの定義を終了しているので何もしません。

新しいワード DAT を実行すると、先に予約したパラメータ領域のポインタをスタックに積みます。

「0 DAT !」の実行により、値0を大域変数DATにストアします。

---

定数を定義する CONSTANT ワードは次のように動作します。

  : CONSTANT <BUILDS , DOES> @ ;

314 CONSTANT PI 【定数の定義】
PI 【定数の参照】

<BUILDSは、コンパイル時の動作の始まりを表します。入力ソースから次の単語を取り出し、辞書にワードエントリーを登録します。”,”はスタックTOPの値(この例では、314)をパラメータ領域にコピーしたものにコンパイルします。DOES>の直前でコンパイル時の動作は終了します。
DOES>以降は実行時の動作で、新たに登録したワードのコード部に登録します。この例では、’@’ワードを登録します。

新しいワード PI を実行すると、先に値をコピーしたパラメータ領域のポインタをスタックに積みます。次に’@’ワードを実行しますので、値314をスタックTOPにロードします。

---

コンパイル時と実行時の動作切り替え、IMMEDIATE属性、定義用ワードの生成技法により、FORTHシステムは極めて拡張性に富んだ言語となり、meta FORTHにより新たなシステムの記述が可能になります。

FORTHワード概要

FORTHワードの多くはスタックに積んだデータを入力として、出力をスタックに戻します。
主なFORTHワードとその機能、ワード操作の前後のスタック状態を示します。

数値演算基本ワードの例

ワード名	機能	スタック状態	説明
+	加算	n1 n2 → n	n＝n1+n2
–	減算	n1 n2 → n	n＝n1-n2
*	乗算	n1 n2 → n	n＝n1*n2
/	除算	n1 n2 → n	n＝n1/n2
MOD	剰余	n1 n2 → n	n＝n1%n2
1+	インクリメント	n1 → n	n＝n1+1
1-	デクリメント	n1 → n	n＝n1-1
MIN	最小値	n1 n2 → n	n＝min(n1,n2)
MAX	最大値	n1 n2 → n	n＝max(n1,n2)
ABS	絶対値	n1→ n	n＝abs(n1)

論理演算基本ワードの例

論理値は、真(true)を1、偽(false)を0とします。

ワード名	機能	スタック状態	説明
AND	論理積	n1 n2 → n	n＝and(n1,n2)
OR	論理和	n1 n2 → n	n＝or(n1,n2)
XOR	排他的論理和	n1 n2 → n	n＝xor(n1,n2)
NOT	否定	n1 → n	n＝not(n1)

比較演算基本ワードの例

比較結果は、真(true)を1、偽(false)を0とします。

ワード名	機能	スタック状態	説明
<	小なり	n1 n2 → b	b＝(n1<n2)?1:0
>	大なり	n1 n2 → b	b＝(n1>n2)?1:0
=	等しい	n1 n2 → b	b＝(n1==n2)?1:0
0=	ゼロ判定	n → b	b＝(n==0)?1:0
0>	正判定	n → b	b＝(n>0)?1:0
0<	負判定	n → b	b＝(n<0)?1:0

スタック操作基本ワードの例

ワード名	機能	スタック状態	説明
DROP	TOP破棄	n →	スタックTopを破棄
DUP	TOP複写	n → n n	スタックTopを複写
OVER	2nd複写	a b → a b a	スタック2ndを複写
SWAP	2nd⇔1st交換	a b → b a	スタック1stと2ndを交換
ROT	3 Data回転	a b c → b c a	スタック1st-2nd-3rdを回転

アドレス操作基本ワードの例

ワード名	機能	スタック状態	説明
@	ロード	adr → val	val＝*(adr)
!	ストア	val adr →	*(adr)＝val
+!	メモリ加算	val adr →	*(adr)＝*(adr)+val

まとめ

「拡張性のある言語 FORTH」という記事を読んで、間接スレッディング方式のアドレス・インタプリタで少ないオーバーへッドでFORTHを実現していることが理解できました。

FORTH定義語によるミニコンパイラ拡張性はとても面白いと思います。この記事だけでは、詳細な仕掛けが理解できませんでした。

実際の処理系のソースコードを解析すれば、より深く理解できると思います。