Intel 4004 (その19) VTLインタプリタを機能拡張する

4004で動くVTLインタプリタでStarTrekを走らせる話です。

去年作ったVTLインタプリタですが、このときの目標はとりあえずマンデルブロ集合を表示するプログラムASCIIART.BASを走らせることだったので、未実装の機能がいくつかありました。

Intel 4004 (その12) VTLインタプリタを作ってみる - ブログの練習

しかし、メモリ空間をほぼギリギリまで使っていたため機能追加は難しい状況。4004で動く8080のエミュレータがあれば8080用の言語処理系が動かせるのではないかと思って作ったのがこちら↓です。これでPalo Alto Tiny BASICやGAME80を動かすことはできたのですが、ちょっと実用にならないレベルの遅さでした。

Intel 4004 (その13) 8080エミュレータを作ってみる - ブログの練習

というわけで、VTLインタプリタの方をもう少しちゃんとしたものにすることにしました。メモリ空間はモニタプログラムの機能を削って確保しました。

今回実装した機能は下記の通り。

• 乱数(疑似乱数)
• 配列
• サブルーチンコールのネスト
• 高速GOTO(通常のGOTOとは別の独自仕様)
• 二項演算子(剰余, 排他的論理和)

古典的なコンピュータゲームであるStarTrekが走るレベルの機能を目標にしました。

まずは乱数。

疑似乱数の生成アルゴリズムというのは結構奥が深い世界なのですが、そんなに真面目に実装する気は無いし、そもそも4004には計算パワーも論理演算命令も無いので、とりあえず線形合同法でいいやと思って実装してみました。下記のような単純なものです。

uint16_t rand(){
static uint16_t x=1;
x=x*16877; /* 16877=7^5 */
return(x>>4);}

x_nをそのまま使うと出てこない数があったので>>4して0～4095までの乱数にしました。試しにx_nをプロットしてみるとこんな感じ。

周期性がありますが、まあわりと乱数っぽいです。ゲームぐらいには使えるかなと思ったのですが、後述するStarTrekで星がいつでも斜めに並ぶという現象が発生。

(x_{2n}, x_{2n+1})をプロットしてみると・・・

これはダメです。ちょっと使い物になりません。

というわけで、もうちょっと真面目に実装することにしました。疑似乱数生成アルゴリズムをググっていたところ、１６ビットマイコンボードの製作 というページにxorshiftというアルゴリズムが紹介されているのを見つけました。

16 bit xorshift rng (now with more period)

聞いたこと無いなあと思って見てみたところ、どうやら2003年に提案されたアルゴリズムのようです。とてもシンプルなアルゴリズムです。

uint16_t rnd_xorshift_32() {
static uint16_t x=1,y=1;
uint16_t t=(x^(x>>5));
x=y;
return y=(y^(y>>1))^(t^(t>>3));
}

これが21世紀になるまで発見されていなかったというのは逆に驚きでした。

y_nをプロットしてみると、

この範囲では周期性っぽい模様は見えません。(y_{2n}, y_{2n+1})を見ても、

ちゃんと乱数っぽくなっています。良さそうなのでこれを実装することにしました。

しかしここで問題が。4004にはxorを計算する命令がありません。8080エミュレータのときに書いたコードをベースにして作ってみました。長いですが他に方法も無いのでこれを使うことにしました。

4004で16bitのxorを計算するプログラムです。

乱数生成部のルーチンはこんな感じになりました。

データRAMを16bitのレジスタとして使うためのサブルーチン群が既にあるのでこの程度に収まってます。ビットシフトは乗除算に使っているサブルーチンを流用しています。

これにより、システム変数 ' で0～32767までの乱数が得られるようになりました。0～99の乱数が欲しいときは、最初、

R=' / 100 R=%

のようにして求めていたのですが、見た目が悪いので剰余を求める二項演算子 % を実装して、

R='%100

と書けるようにしました。'(100)という記法にするより実装しやすいのでこうなりました。あと、せっかく排他的論理和のルーチンも作ったので二項演算子 ^ も実装しました。

乱数が作れたことにより、最古の経営シミュレーションと思われる「イスカンダルのトーフ屋ゲーム」を走らせることができました。動画はこちら。

8080エミュレータでは激遅でとても遊べない速度でしたが、今回はちゃんとした速度で動きました。

次に配列です。とりあえず1次元配列を1つだけ実装。記法は、@(x)にしました。TK-80BSのLevel 1 BASICをリスペクトしています。最初これをPEEK、POKEの機能にしようかとも思ったのですが、4004の機械語を書いてもそこにジャンプして実行できるわけではなく、データ格納以外に使い道が無いので、変数と同じ16bitの整数として読み書きします。

これでStarTrek走るかな？と思ってエンサイクロペディアASCIIのStarTrek特集を眺めてみると、多段のGOSUBが使われています。サブルーチンが1段だけのVTL用に移植されたもの(マイクロTREK)もあったのですが、配列に返り番地を積むとか、あまり美しくない移植だったので、多段のサブルーチンを真面目に実装することにしました。

GOSUBは現在実行中のコンテクストを退避してGOTOでジャンプするだけ、RETURNはコンテクストを復帰させるだけなので、それほど難しくはありません。退避するコンテクストは、

• 実行中の行の先頭アドレス
• 実行中のプログラム位置(GOSUB文!=xxxの直後)を示すアドレス
• 実行中の次の行の先頭アドレス

としました。本質的なのは実行中のプログラム位置だけですが、今回の実装ではその前後もある方が作りやすかったのでコンテクストに含めています。

実行中の行の先頭アドレスは、後述の高速GOTO用のシステム変数 # のため、次の行の先頭アドレスはIF文不成立時に文末まで舐めずに次の行に飛ぶためのものです。

これでどうにかStarTrekを動かせるレベルの言語処理系が準備できました。

StarTrekのプログラムは結構長いので、どこかに転がってないかとググってみたところ、こちらのサイト(Bequest333のページ)で電大版StarTrekが入ったパッケージを入手。どうやら電大版Tiny BASICにはFOR文が無いようで、GOTOを#=に、PRを?=に、IFを;=にのように機械的に置き換えるだけでほぼそのままVTL-4004に移植できました。

さっそく実行してみましたが何かがおかしく、いろいろ調べてみたところどうやらエネルギーが0で何も出来無いという状態。安田寿明著「マイ・コンピュータをつかう」に載っているソースと比べてみたところ、なぜか330行目のGOSUB 1600が存在せず、エネルギーや光子魚雷の数が設定されなくなっていたのが原因でした。

そこを修正したところ無事ゲームで遊べるようになったのですが、速度がかなり遅いです。Short Range Sensorの表示に1分ぐらいかかっていました。

考えられる原因はGOTO文(#=)の処理です。今の実装では#=は飛び先の場所をプログラムの先頭から行番号を探してジャンプします。一応行番号の隣に次の行へのポインタを格納しているので、プログラムの文字列を全部舐めているわけではないのですが、それでもプログラムの後ろの方に

5000 I=I+1 ;=I<10 #=5000

みたいな行があると、#=5000でプログラムの先頭から順番に見ていって5000の行まで探すので大規模なプログラムだとかなりのオーバーヘッドになります。

ジャンプ先を行番号ではなくプログラムの場所のポインタで指定できれば即座にジャンプできます。というわけで、システム変数 # を、現在実行している行の行番号ではなく、現在実行中の行の先頭アドレスに変更することにしました。

さらに、実行するプログラムの位置を変更するための記法として、>= を実装しました。さきほどの例は、

5000 I=I+1 ;=I<10 @(I)=0 >=#

のように書き直します。16bitの値で普通に変数に格納できるので、ループを多重にしたい場合は A=#のように保存しておいて、>=Aでジャンプすることもできます。

ループで何度も実行されるGOTOをこれに書き直すことによってかなり高速化され、Short Range Sensorも30秒ほどで表示できるようになりました。

ゲームの様子です。まだ遅いと言えば遅いですが、ギリギリ耐えられる遅さにすることができたかなと思います。

インタプリタのソースコード等一式はGitHubに置きました。

GitHub - ryomuk/VTL4004: VTL Interpreter for 4004 Evaluation Board