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

事情があって、コンピュータのハードウェアメカニズムをごく簡単に説明したいのです。本物のCPUは難しくて簡単な説明にはならないし、そもそも僕は本物がどうなっているかよく知りません。

そこで、オモチャの仮想機械を作ることにしました。加減乗除だけができるスタックマシンです。仮想機械の実装はJavaScript、ユーザーインターフェースはHTMLです。こういうとき、JavaScript + HTML はお手軽でほんとに便利です。

Web上で試せるURL

http://www.chimaira.org/tools/rac0.html

初等算術計算仮想機械の実装

仮想機械を実装するソースコードは次のようです。インストラクション（機械語命令）の説明はすぐ後でします。

/* rac0vm.js */
/*
 * Rudimentary Arithmetic Calculator Level-0
 */

var C  = 0; // 定数値 (Constant)
var OP = 1; // 演算 (Operation)

var code;   // 現在実行中のコード
var pc;     // プログラムカウンタ
var stack;  // 計算用スタック

var result; // 最終結果

var debug = true; // デバッグフラグ

function setup(c) {
  code = c;
  pc = 0;
  stack = [];
}

function exec() {
  while (true) {
    if (pc >= code.length) break;
    var inst = code[pc];
    if (debug) {
      var mess = instToString(inst) + "\n" + stackToString();
      alert(mess);
    }
    if (inst[0] === C) {
      stack.push(inst[1]);
    } else if (inst[0] == OP){
      doOperation(inst[1]);
    } else {
      throw "illegal instruction";
    }
    pc++;
  }
  result = stack.pop();
}

function doOperation(opcode) {
  // スタックから引数を取り出すときは逆順
  var arg2 = stack.pop();
  var arg1 = stack.pop();
  // opcode により分岐実行
  switch (opcode) {
  case "+":
    stack.push(arg1 + arg2);
    break;
  case "-":
    stack.push(arg1 - arg2);
    break;
  case "*":
    stack.push(arg1 * arg2);
    break;
  case "/":
    stack.push(Math.floor(arg1 / arg2));
    break;
  case "%":
    stack.push(arg1 % arg2);
    break;
  default:
    throw "illegal opcode";
  }
}

// 以下、デバッグメッセージ用

function instToString(inst) {
  var s;
  switch (inst[0]) {
  case C:
    s = "Const:";
    break;
  case OP:
    s = "Opera:";
    break;
  default:
    return "Illegal instruction!";
  }
  s += inst[1];
  return s;
}

function stackToString() {
  var s = "Stack|";
  for (var i = 0; i < stack.length; i++) {
    s += stack[i];
    s += "|";
  }
  return s;
}

stackToString() でforループ回しているところは、stack.join("|") ってやりゃ良かった、と今思ったがまーいいや。

インストラクション（機械語命令）

1つのインストラクションは、種別を表す接頭辞とデータの組です。種別は定数（constant）C、または演算(operation）OPのどちらかです。定数は整数に限ります（実際は、JavaScriptの浮動小数点も使えてしまいますが）。演算は算数の四則演算、+, -, *, /, % です。% は割り算の余りを求める演算。

インストラクションの記述形式は [種別, データ] の形：

定数 1 ： [C, 1]
定数 2 ： [C, 2]
演算 + ： [OP, "+"]

インストラクションをカンマで区切って並べたものがプログラムです。[C, 1], [C, 2], [OP, "+"] はプログラムですね。カンマを忘れがちですから注意してください。

定数はスタックにそのまま置かれ、演算はスタック上の値を引数として実行されます。したがって、[C, 1], [C, 2], [OP, "+"] は 1 + 2 を計算します。http://www.chimaira.org/tools/rac0.html のテキストエリアに機械語コードを入れて実行してみてください。デバッグ用アラートには、これから実行するインストラクションと、その時（インストラクション実行直前）のスタック状態が表示されます。最終結果はHTMLページ内に書き込まれます。

逆ポーランド記法

スタック計算機の機械語コードは、だいたい逆ポーランド記法になります。逆ポーランド記法とは、演算の引数（被演算数）を先に書き、演算子を後に置く書き方です。例えば、
2 + 3 は 2 3 + となります。以下では、引数／演算子の区切りにカンマを入れることにします。2, 3, + のようになります。このほうが、今話題にしている仮想機械RAC0の機械語コードに近いですから。

逆ポーランド記法では、括弧を使う必要がなく、並べたまんまに計算が進行します。スタックマシンとたいへん相性がいいのです。いくつかの例を見れば、逆ポーランド記法をすぐに理解できると思いますよ。以下に、普通の算術式、逆ポーランド記法、RAC0の機械語コードを並べた例を示します。