Tiny Forthインタープリタ


はじめに

Forthは1960年代の終わりにCharles H. Mooreによって提案されたプログラミング言語で,アメリカの国立電波天文台における観測の自動化を目的として開発されました.Forthという名前は,第4世代を表す"fourth"からきていますが,当時開発に使用した計算機(IBM 1130)では5文字までのファイル名しか扱えないという制約があったためこの名前になったといわれています.

VTL(Very Tiny Language)の作成」にVTLという言語を知ったいきさつを書きましたが,Forthという言語処理系についても同じ経緯で知りました.ForthもVTLのようにコンパクトな処理系です.
データ構造の一つであるスタックを基本として処理を行う点が他の言語にはない独特な特徴であり,シンプルでエレガントな言語だと思います.
Forthは機械語に近いレベルの記述により向いた低級言語で,実際に使われているのはあまり見かけませんが,同じスタック型言語であるPostScriptはプリンタ等で使われるページ記述言語として見えないところでよく使われています.
ForthはVTLとは違ってある程度認知度があり,Web上でも使い方や様々な処理系を見つけることができます.また,Forthの標準規格も作られています.ACM SIGFORTHという研究会もあったようです.

VTLのインタープリタを作成した理由と同様に,AVRなどの組み込み用CPU上でこの言語処理系を動かしてみたいと思い,非常に基本的な機能だけを持ったForthインタープリタを実装してみました.C言語で書いたものとAVRのアセンブラで書いたものがあり,前者は移植性に優れており,後者はコードサイズが小さくフラッシュROMが2KバイトのAT90S2313でも動作します.C言語版の方も,ソースコードの行数は584行とコンパクトです.
なお,今回作成したForthの処理系は,あらかじめプログラムをコンパイルしてマシン語を生成するコンパイラではなく,対話的に処理を行うインタープリタです.そのため,例えばAVRの出力ポートに接続したLCDやステッピングモーター等の機器をコントロールするプログラムを書いて即座に実行するようなことができます.ただし,作成できるプログラムの大きさはRAMのサイズによって制約されます.

Forth入門

Forthの基本的な使い方について説明します.なおこの説明は今回作成した処理系Tiny Forth (C言語版)に合わせたものであり,世の中の他のForth処理系とは異なる場合があります.

スタックと逆ポーランド記法

Forthの一番の特徴は,スタックを用いて演算が行われることです.スタックとは,Last-In-First-Outとも呼ばれるデータ構造で,その名のとおり複数のデータを入力すると,最後に入れたものから順番に取り出されるような保管庫のようなものです.これはちょうど,机の上に本を積んで保管すると,最後に積まれた本から順番に取り出すことができるのと同じで,スタック(積み重ねたものの意味)という言葉はそこから来ています.

Forthでは,数字が入力されると,それらが入力された順番にForth内部のスタックに積まれていきます.
例えば,

1 2 3

と数字をスペースで区切って入力すると(行末ではリターンキーを押します),スタックは次のようになります(スタックは上方向に伸びていくものとします):

3
2
1

今回作成したTiny Forthで扱うことのできる数値は,符号無しの16bit整数(0~65535)だけです.

ここで,

+

として"+"という演算子を入力すると,スタックの上から1番目(スタックトップ)と2番目に積まれた数値を取り出して加算し,結果をスタックトップに追加します.結局スタックの要素は1減ることになり,スタックの中身は次のようになります:

5
1

スタックトップの値を取り出して画面に表示させるには,"."(ピリオド)という命令(ワード)を使います.例えば,スタックが上記の状態で,スタックトップを2回表示させると,初めに"5"が,次に"1"が表示されます(イタリックの文字はシステムの出力を表します):

.
5 OK
.
1 OK

スタックを用いて演算を行うことにより,括弧を使わないでも演算の順番を考慮して計算を行うことができます.例えば,"3+4*5"という計算ならば

3 4 5 * +

として,"(3+4)*5"という計算ならば

3 4 + 5 *

として計算できます."9*((8+7)*(6+5*4)-3)"ならば,

9 8 7 + 6 5 4 * + * 3 - *

となります.
このような式の表記方法は逆ポーランド記法と呼ばれており,慣れないと見にくいかもしれませんが,加減算よりも乗除算を優先するというような演算子の優先順位を考えなくてもすむため,計算機での処理は容易に行えます.

ワードと辞書

"+"や"."などのForthの命令は,ワードと呼ばれます.多くのワードは,スタック上のデータを消費したり供給したりします.例えば,"+"は2つのデータを消費して1つのデータを供給し,"."は1つのデータを消費します.

Forthで使われるワードは,Forthの辞書に登録されています.ワードが入力されると,Forthはその辞書を探索して,辞書に書かれた処理内容を実行する,という仕組みになっています.この辞書はユーザーが自由に拡張できます.つまり,"+"などのあらかじめ登録されたワードだけではなく,ユーザーは新しいワードを定義して使うことができます.

新しいワードは": <新しいワード名> <新しいワードを構成するワード列> ;"として定義します.例えば,

: ABC DUP 1 + * 2 / ;

として,"ABC"という新しいワードを定義できます.このワードは,スタックトップの値をxとすると,スタックのデータを1つ消費して,x*(x+1)/2の値をスタックに追加することになります(DUPはスタックトップの値を複製するワードです).なお,":"を入力して";"を入力するまでのワードを定義するモードをコンパイルモードと呼び,それ以外のインタラクティブにワードを実行するモードを実行モードと呼びます. 新しく追加したワードはあらかじめ登録されているワードと同様に使うことができます:

5 ABC .
15 OK

既に登録されているのと同じ名前のワードを登録することもできます.その場合,辞書中に2つの同名のワードが存在することになりますが,最後に登録したワードが実際には使われます.これは,Forthでは辞書を探索する場合に,最後に登録されたワードから探索して,途中でワードが見つかれば探索を終了するからです."+"などのあらかじめ定義されているワードも再定義できます.

登録したワードを辞書から削除するには,"FGT"というワードを使います.

FGT ABC

FGTでワードを削除すると,指定したワードとそれ以降に定義されたワードが全て辞書から削除されます. なお,このTiny Forthではワードの名前は最大3文字という制限があります.それ以上の長さの文字は無視されるので,"ABC"というワードも"ABCD"というワードも同じものとして扱われます.

変数

変数を使用する場合は,"VAR"というワードで変数を定義します.例えば,

VAR AB

とすると,ABという変数が使えるようになります.変数に値を代入したり,変数から値を取り出すには,それぞれ"!"と"@"というワードを使います:

123 AB !
AB @ .
123 OK

定義された変数は,実際はその変数が格納されたメモリ領域のアドレスを返すようなワードとして働きます."!"というワードはスタックの上から1番目の値をメモリのアドレスとみなして,2番目の値をその領域に書き込む動作をして,"@"というワードはスタックトップの値をメモリのアドレスとみなしてその領域の値をスタックに積む動作をします.

制御文

Forthでは,いくつかの条件分岐や繰り返し等の制御構造を扱うことができます.ただしこれらの制御文は,ワードの定義中(コンパイルモード)でのみ使用することができます.またTiny Forthで真偽値の判定を行う際には,0以外の値を真,0を偽として扱います.

IF <words> THN
スタックトップの値が真ならばワード列<words>を実行します.
IF <words1> ELS <words2> THN
スタックトップの値が真ならばワード列<words1>を,偽ならばワード列<words2>を実行します.
BGN <words> END
ワード列<words>を実行して,スタックトップの値が偽ならば再び繰り返します.
BGN <words1> WHL <words2> RPT
ワード列<words1>を実行して,スタックトップの値が偽ならば終了し,真ならばワード列<words2>を実行した後に再びワード列<words1>を繰り返し実行します.
DO <words> LOP
スタックの上から1番目の値をループカウンタの初期値,2番目の値を終了値として,ワード列<words>を実行し,ループカウンタの値を1増やし,ループカウンタの値が終了値より小さければワード列<words>の実行を繰り返します.ループカウンタの値は"I"というワードで参照できます.ループカウンタの初期値や終了値は,ループの実行中はリターンスタックと呼ばれる通常の演算に使われるスタック(パラメータスタック)とは別のスタック上に保管されます.

例.1から10の値を出力する

: A 11 1 DO I . LOP ;
A
1 2 3 4 5 6 7 8 9 10 OK

例.階乗の計算(再帰)

: FCT DUP 0 = IF DRP 1 ELS DUP 1 - FCT * THN ;
0 FCT .
1 OK
1 FCT .
1 OK
2 FCT .
2 OK
3 FCT .
6 OK
4 FCT .
24 OK
5 FCT .
120 OK

(このように再帰関数を定義する方法は,一般的なForthとは異なっています)

リファレンスガイド

このTiny Forthでサポートされている全てのワードについては,こちらのリファレンスガイドをご参照ください. 
このガイドの中で,"( v3 v2 v1 -- w3 w2 w1 )"というような表記がありますが,これはワードが消費・供給するスタックの要素を表しています.この例では,スタックトップから順にv1,v2,v3という3つの値を消費して,スタックトップから順にw1,w2,w3という値を供給することを表しています.

Forthインタープリタの実装

Forthの実装については,文献[1]を参考にしました.これは雑誌の連載ですが,PC-8001用にZ-80のアセンブラで書かれたForth処理系について詳細に解説しています.また,Forthという言語のリファレンスとしても大変分かりやすく書かれています.ただし今回はサイズの小さな処理系を作りたかったため,このForth/Σとの互換性などは考えておらず,プログラムの構造も大きく異なっています.
はじめは移植性を重視してC言語で書きましたが,サイズ的にAT90S2313で動かすのが難しかったため,AVRのアセンブラで書き換えたものを作りました.

以前作成したVTLと同様に,いくつかのOSやCPUで動作させました.H8版,UNIX版,MinGW版があります.それぞれの版は,ソースファイルに含まれている"h8/","unix/","mingw/"というディレクトリで"make"を実行するとコンパイルできます.以下,各機種ごとの説明です:

H8版(C言語版)
H8用です. トランジスタ技術2004年4月号に付属のH8/3694Fで動作確認をしました.
入出力は,RS-232C(SCI)で接続した端末を通じて行います.
UNIX版(C言語版)
UNIX系用です.Linux,FreeBSD,およびWindows上のCygwinで動作確認をしました.
MinGW版(C言語版)
Windows上のMinGW用です.コンパイル済みの実行形式も用意しておきました.
AVR版(AVRアセンブラ版)
AVR用です.AT90S2313で動作確認をしています.コードサイズは1,964バイトなので,ハードウェアスタックの設定などを書き換えれば多くのAVRで動作可能だと思います.
入出力は,RS-232C(UART)で接続した端末を通じて行います.
クロックが7.3728MHz,通信速度が19200baudの場合のバイナリ形式も用意しておきました.

C言語版の方は上記のCPUやOS以外でも,system.c中のinitl(),getchr(),putchr()の3つの関数を用意すれば 動作させることができます.initl()は(必要であれば)機種に依存した初期化処理,getchr()は(バッファリングを行わない,エコー出力を行 う)1文字入力,putchr()は(バッファリングを行わない)1文字出力です.詳しい内容は,H8版,UNIX版,MinGW版のsystem.cをご参考にしてください.

インタープリタ本体のプログラム

C言語版

AVRアセンブラ版

使ってみて

このインタープリタは,正直言って実用性を目指して作ったものではなく,Forthのインタープリタを書いてみたいという動機で作ったものです.
しかしながら完全にお遊びというわけではなく,Forthはメモリアクセス等を直接行うことができて無駄が少ない言語なので,AVRのポートに接続した機器をインタラクティブに操作して実験するのに向いているのではないかと考えていました.実際に,冒頭で述べたようにこのForthという言語は,もともと天文台での観測の自動化を目的として開発されたという経緯があります.

そこでステッピングモーターの制御にこのTiny Forthを使ってみました.AT90S2313のポートにMOS-FET(MP4401)を取り付けて,ステッピングモーター(TS3103N124)を二相励磁で動かしてみました.この程度の制御なら可能ですが,AT90S2313にはRAMが128バイトしかないので,もう少し複雑なことを行う場合はもっとRAMを持ったマイコンの方がよいです.

Tiny Forthによるステッピングモーターの制御 Tiny Forthによるステッピングモーターの制御

参考資料

  1. 一ノ瀬敏彰,山口晶嗣: Forth/Σ 連載第一回~連載第六回, ASCII, 1982年4月号~9月号.
  2. 金田悠紀夫,和田耕一: Forthとは何か, インターフェース, 1981年8月号, pp. 118-126.

[戻る]
2010-01-30 ページ更新
2009-01-17 ページ作成
(2004-08 製作)
T. Nakagawa