CuBeatSystems: NT-Basic on KOZOSのために・・・ (NT-Basicの改良)

NT-Basic on KOZOS(NT-Basicの改良)

SWEST14での刺激を受けた結果、インタプリタの実装に興味が出てきてNT-Basicなるものを出力しました。

それではという事でKOZOSと組み合わせて使おうと思ったのですが、実際にあまり使い勝手が良くなかったのでNT-Basicの改良から行うことにしました。

エディタが必要だ

KOZOS上で実際に動作させる場合、単にファイルシステムからコードを読み込んで動作させるだけでは面白くありません。ターミナルエミュレータから実際にコードを入力して実行するようなインタラクティブな動作を実現したいのです。

この時に必要になるのが実用的なエディタです。入力を間違えても再編集できて、昔ながらのBasicシステムに似たような動作を提供できるのが理想です。viのように本格的なエディタを設計する気分にはなれなかったので、以下のような戦略をとることにしました。

行編集機能はNT-Shellを用いて機能提供する。
プログラムは新たに作るtexteditモジュールが保持する。
ターミナルにrunコマンドを与えた時点でイタンプリタを動作させる。

こうする事でtexteditモジュールのみを設計実装すれば済みます。
texteditモジュールのインターフェースは以下のようにしました。

int textedit_init(textedit_t *p);
int textedit_clear(textedit_t *p);
int textedit_insert(textedit_t *p, const int line_number, const char *text);
int textedit_delete(textedit_t *p, const int line_number);
int textedit_fetch(textedit_t *p, const int line_number, char *text, const int maxsize);

NT-Basicはプログラムを文字列として受け取ります。
エディタを設計するならば、内部データは双方向リンクリストで構成する行データの集合として表現したいのですが、NT-Basic側の都合に合わせて単純な一つの文字列で複数の行編集が可能なtexteditモジュールとして設計しました。

これでプログラムの編集は実現できます。

プログラムエラー発生時の挙動修正

初版のNT-Basicでは、プログラムエラーが発生した時に最終的にハードウェア抽象化層のhal_halt関数を呼び出していました。この関数は無限に処理を返さない関数として実装する事を想定しており、「プログラムエラー＝処理を永遠に返さない」というあんまりな挙動を提供する結果を生んでいました。

「それはないだろう」という事で、エラーを検出した時点で、そこから最終的にntbasic_executeまでエラーを伝搬させるようにしました。HAL層にhaltがあると意味がわからないので、hal_haltは削除しました。ちなみに、c89で上位にエラーを伝搬させるのは丁寧に実装するしかない、みたいな感じの実装になっています。

上位でエラー発生時の行番号の取得も可能です。

NT-Basicの実行方法

初版の実装でもう一つ致命的に使いにくいのが、実行方法でした。ntbasic_executeは、実行したらプログラム終了まで処理を返さないという仕様だったのです。が、これではベアメタルシステムで使いにくくて仕方ありません。NT-Basicでチョコチョコ処理をしながら、別の作業をさせたい事もあるわけです。

実際に使ってみると、先ほどのエラー時の挙動と合わせて組み込みシステムで実質使えないような挙動になっていました。

そこで、改良したNT-Basicでは、ntbasic_executeを呼ぶ度に1ステートメントのみ処理するように仕様を変更しました。こうする事でベアメタルシステムでもNT-Basicを導入しやすくなります。

  ntbasic_t ntbasic;
  ntbasic_error_t error;

  /*
   * Setup and execute.
   */
  error = ntbasic_setup(&ntbasic, program);
  while (error == NoError) {
    error = ntbasic_execute(&ntbasic);
  }

  /*
   * Check the termination code.
   */
  if (error != EndOfTheProgram) {
    core_error_message(&ntbasic, error);
  }

上記のような簡単なコードを上位に加えれば従来のような使い方もできます。

辛かった変数名の制限

最初の実装では変数名はAからZまでの26文字という小さなBasicではありがちの制限を持っていました。

実際にプログラムを組んでみるとわかるのですが、これがかなり辛い制限です。
「あれ？この変数は何を入れてるんだっけ？」みたいにすぐに迷子になれます。
「えーと、Rはアレの略にしたから・・・、で、Aは・・・何だっけ？」みたいに脳内記号表を使う羽目になるわけです。本来、これは機械にやらせるべき作業内容です。

そこで、自由に変数名を付けられるような仕様変更を行いました。

内部設計と実装は至ってシンプルです。
小さな記号表モジュールを作って対応しました。

記号表の考え方は非常に面白いものです。
ここでハッシュ法を使った動作を簡単なモデルで紹介しましょう。

ハッシュ法を用いた記号表の実現

記号表は、変数名や型、長さやその他属性を管理するテーブルです。
NT-Basicの場合、変数は内部的にintしか持たないので型や長さは存在しません。
記号表における一番シンプルな例という事になります。

で、与えられた変数名から実際の値を取りだす場合、テーブルを探索する事になります。
線形探索した場合、最悪の場合テーブルのサイズ分の文字列比較作業が必要になります。

上記の図でGHIという変数を探索した場合、先頭から3番目で探索完了になりますが、実際にテーブルの最後に存在した場合、テーブルサイズ分の探索作業を行なう事になります。

これでは変数にアクセスする度に膨大な時間が必要になるので効率的とは言えません。
そこで考えられたのがハッシュ法です。

基本的な考えは非常にシンプルです。

まず、与えられた文字列から導出可能なハッシュ値を得ます。
このハッシュ値は文字列から得られる値で、同じ文字列からは毎回同じ値が得られます。

次に、この得られたハッシュ値を元にテーブルの参照先インデックスを決定します。
例えば、参照先インデックスとして28という数値が得られたら、記号表のインデックス28を参照するという仕組みです。

有限長のテーブルの場合、「参照先インデックス % テーブルサイズ」などとして参照先インデックスを決定します。

整理すると「文字列からハッシュ値」、「ハッシュ値からテーブル参照先インデックス」という過程で、変数名を与えるだけで一意に決まる(ように見える)インデックス番号が求まりました。

さて、ここで疑問が沸いてきます。
仮にテーブルのサイズが16だったとして、ハッシュ値0と16の結果はどうなるでしょうか？

先ほどの例では「参照先インデックス % テーブルサイズ」なのでテーブルの参照先がどちらも0になってしまいます。

変数名として与えられた文字列が異なるものなので、理想的には得られたハッシュ値は異なる結果となります。それにも関わらずテーブルの参照先が同じになってしまいました。

安直な実装の場合、参照先インデックスに格納されている変数名と照合して、合致すれば期待する変数が格納されているものとして処理します。

そして、期待する変数名でなければ近い位置のテーブルを探します。
これにより、線形探索よりも遥に少ない処理で期待する変数値を得ることができます。

実際には、ハッシュ値自身の衝突も考える必要があります。
ハッシュ値自身の衝突の場合も、上記のように期待する変数でなければ近い位置のテーブルを探索するという方法を取ります。

ちなみに、流石に上限なしで対応させるとメモリが幾らあっても足りないので、デフォルトの定義では変数名8文字、変数32個までにしてあります。これはヘッダファイルを書き換えるだけで大きくする事ができます。組み込むシステムに合わせて定義を修正すれば良いでしょう。

この改良によって、以下のようなプログラムが見違えるように判りやすく書けるようになります。
以下はアリスとボブとキャロルの年齢を総計として出力する例です。（ちょっと無理矢理な例）

改良前

INPUT "A=",A
INPUT "B=",B
INPUT "C=",C
T = A + B + C
PRINT "T=",T

改良後

INPUT "Alice=",Alice
INPUT "Bob=",Bob
INPUT "Carol=",Carol
Total = Alice + Bob + Carol
PRINT "Total=",Total

まとめ

今回は小規模組み込みシステムで楽しむためのNT-Basicの改良として、実行方法、エラー時の挙動、変数名の制限について改良した内容について示しました。

ちなみに、NT-Basicは総行数が約2000行とコンパクト。
１人で簡単に読み切れるサイズです。

--------------------
Lines File
--------------------
438 core.c
281 expression.c
109 hal.c
106 main.c
157 ntbasic.c
269 ntlibc.c
443 statement.c
111 tinyrand.c
135 variable.c
--------------------
2049 Total

最新のリリースは以下からダウンロードできます。
http://shinta.main.jp/firmware/ntbasic/ntbasic_ja.html

CuBeatSystems

2012年9月22日土曜日

NT-Basic on KOZOSのために・・・ (NT-Basicの改良)