JavaScriptで仮想機械の勉強をしましょう (その2) - 檜山正幸のキマイラ飼育記 (はてなBlog)

随分と昔（2009年11月末）に「JavaScriptで仮想機械の勉強をしましょう」という記事を書きました。今頃になって続きです。

以前の記事で、算術計算をするオモチャの仮想機械を、JavaScriptで作りました。それを RAC0（Rudimentary Arithmetic Calculator Leval-0）と名付けて、「RAC1, RAC2 などがあるかも」と言いながらずっと放置。んで、ちょっとした気の迷いから今日続き（RAC1の話）を書くことにします。

とはいえ、変数の機能と命令セットを決めただけなんで、とりあえずそれを説明します。仮想機械の実行部分は明日以降に。[追記]サンプルを作りました。[/追記]

内容：

RAC1の特徴
変数のメカニズム
命令セット
1. 算術演算の命令
2. 定数の命令
3. 述語／関係の命令
4. 論理演算の命令
5. 流れ制御の命令
6. ブロックスコープと変数の命令
7. スタック操作の命令
8. ネイティブ関数呼び出しの命令

RAC1の特徴

RAC0は、単に算術式の評価ができるだけでしたが、RAC1には次の機能を持たせます（その予定）。

変数を使える。
制御構造を持つ。
整数以外に真偽値（boolean）もデータとする。
JavaScriptにより機能を拡張できる。

変数に関しては、ネスト可能なブロックスコープを仮想機械のレベルでサポートします。JavaScriptにはブロックスコープがないので、この点では（この点だけ）RAC1のほうがJavaScriptよりチャントしてます。

制御構造を持つとは、高級言語のif文やwhile文に相当する命令列をRAC1アセンブリ言語で書けるということです。

制御構造では条件式を使うので、真偽値が必要になります。整数値で真偽値の代用もできますが、0や1ではないtrue/falseを導入します。（でも型チェックはしません。）

「JavaScriptにより機能を拡張できる」とは、JavaScriptの関数を仮想機械の組み込み命令のように使えるようにすることです。

変数のメカニズム

変数とはメモリストレージのことです。通常のメモリは、アドレスが付いたメモリセルの単純な並びです。単純なメモリを使ってハッシュテーブルやリストを実現するにはソフトウェアが必要です。ここでは、メモリ側に機能を持たせて、RAC1のプログラムが何もしなくてもネスト可能なブロックスコープを利用できるようにします。

RAC1で使うメモリは次のようなものです。

var rac1 = {/* モジュール名前空間 */};

// ブロックスコープの機能を持つメモリ
rac1.BlockScopes = function (scope) {
    this.scopes = [scope];	
};

rac1.BlockScopes.prototype = {
    // 新しいブロックを作る
    openBlock:
    function () {
	this.scopes.push({});
    },
    
    // 現在のブロックを捨てる
    closeBlock:
    function () {
	this.scopes.pop();
    },

    // 指定された変数を持つスコープオブジェクトを探す
    findScope:
    function (name) {
	var j = this.scopes.length - 1;
	for (; 0 <= j; j-- ) {
	    var scope = this.scopes[j];
	    if (name in scope) {
		return scope;
	    }
	}
	return null;
    },

    // 変数名に対応する値を返す
    getVal:
    function (name) {
	var scope = this.findScope(name);
	if (scope) {
	    return scope[name];	    
	} else {
	    throw "UnboundVariable";	    
	}
    },

    // 変数名に値を束縛する
    setVal:
    function (name, val) {
	var scope = this.findScope(name);
	if (!scope) {
	    scope = this.scopes.top();
	}
	scope[name] = val;
    },

    // 現在（一番内側）のスコープ内に変数を作る
    // 値の初期化はしない
    allocVar:
    function (name) {
	var scope = this.scopes.top();
	if (name in scope) {
	    throw "BoundVariable";
	} else {
	    scope[name] = undefined;
	}
    }
};

命令セット

RAC0の命令（インストラクション）は、定数のCと算術演算のOPだけでした。算術演算の種類はOPのパラメータ（オペランド）部に入れていたのです。今回のRAC1では、四則演算（と割り算の余り）をそれぞれ独立の命令にします。算術演算の対象データは、スタックにあるとします。したがって、命令のパラメータはありません。

算術演算の命令

命令	説明
ADD	足し算
SUB	引き算
MUL	掛け算
DIV	割り算（整除）
REM	割り算の余り

これらの命令は、スタックトップとスタックの二番目のデータを消費して、代わりに演算結果をスタックに積みます。

その他の命令も以下にザーッと並べます。命令のパラメータに使われている記号の意味は以下のとおりです。

n 整数
a ラベル名（文字列）
v 変数名（文字列）
f ネイティブ関数名（文字列）

パラメータ以外に必要なデータは常にスタックから取ることにします。first はスタックトップ、secondはスタックの二番目のデータを示します。特の断りがなければ、スタック上の引数データは消費され計算結果で置き換えられます。

[追記]firebugコンソールでは、$$という関数が前もって定義されているようなので、$$を$$$に変更しました。それと、実際にRAC1アセンブリ言語で書いてみると、もう少し命令を足したほうが便利みたいですね。[/追記]

定数の命令

命令	説明
CONST n	定数nをスタックに積む

述語／関係の命令

命令	説明
EQ	firstとsecondが等しいかどうか
LT	first ＜ second かどうか

結果はtrueかfalseになります。

論理演算の命令

命令	説明
AND	論理アンド
OR	論理オア
NOT	論理ノット

流れ制御の命令

命令	説明
$$$ a	ラベルを付ける
JMP a	ラベルの場所にジャンプ
IFT a	firstが真だったらラベルの場所にジャンプ

ブロックスコープと変数の命令

命令	説明
BOPEN	新しいブロックを作成
BCLOSE	現在のブロックを破棄
REF v	変数値をスタックに積む
ASSIGN v	変数にfirstを代入、firstはそのまま
ALLOC v	変数を確保（値は未定義）

スタック操作の命令

命令	説明
DISCARD	スタックトップを捨てる
DUP	スタックトップをコピー
XCHG	スタックトップと二番目を入れ換える

ネイティブ関数呼び出しの命令

ネイティブ関数とは、仮想機械の実装言語（＝JavaScript）で書かれた関数です。

命令	説明
NFCALL f	名前fで示される関数を呼ぶ

各命令の実装は次回。