ランダムアクセス機械のサンプルコード

社内勉強会用にランダムアクセス機械のサンプルコードを自宅で書いていたのですが、さっきできました。なぜに自宅で書いていたかというと、多分サンプルを作るほどのことは無いくせに、どうしても趣味で作りたかったから気が引けたのです。

ちなみにランダムアクセス機械というのはチューリング機械みたく抽象的なモデルらしくて、でもでも、逐次アクセスできないチューリングマシンと異なり任意の記憶領域に直接アクセスできるらしくて、チューリングマシンよりも出回っているコンピュータに近いらしくて、一つのアキュムレータ（レジスタ）とたくさんの記憶領域を持つらしいです。

で、テキストには以下の10個くらいの命令を持つランダムアクセス言語が例として載っていました。

命令記号	引数	意味
LDA	X	X番地の内容をACに取得する
LDI	X	X番地の内容を間接方式でACに取得する
STA	X	ACの内容をX番地に記憶する
STI	X	ACの内容を間接方式でX番地に記憶する
ADD	X	X番地の内容をACに加える
SUB	X	ACからX番地の内容をを引く
JMP	X	ラベルXの命令にジャンプする
JMZ	X	ACが0のとき、ラベルXの命令にジャンプする
HLT	-	停止する

今回は、このランダムアクセス言語をJavaScriptで書いてみました。なぜJavaScriptかというと最近全然書いていないし、書いていたときもjQueryでばっかり書いていたので一から書いてみたかったからです。

つかいかたはこんなかんじになります（イメージです）。

    var codeStr = "\
1 LDI 3  # 検索対象配列Aのi番目の要素を取得
2 ADD 4  # 作業用配列Bの指標jを得るため配列Aの終端位置を加える
3 STA 5  # 配列Bの指標jを記憶する";

    var memory = [1, 0, 6, 9];

    try {
        var ral = new Ral();
        ral.parse(codeStr, function(code) { alert(code); });
        ral.run(memory, function(ac, code, memory) { alert('lineno => ' + code.lineno });
    }
    catch(e) { alert(e.message); }

parse()で受け取るコードの文字列は左から、命令番号、オペレータ、オペランドです。parse(), run()の第二引数はデバッグ用です。

で、本体はこんなのです（肝は function run() だけかも。evalしてますが…）

var Ral = function() {};
Ral.prototype = {
    parse : function(codeStr, callback) {
        var lines = codeStr.split("\n");
        var code = [];
        for (var i = 0; i < lines.length; i++) {
            var l = lines[i];
            if (l.length == 0) { continue; }
            if (! l.match(/(\d+)\s+(\w+)\s*(\d*)\s*(#\s*(.*))?/)) {
                throw new Error('Invalid code[' + l + ']');
            }
            code.push({
                lineno: parseInt(RegExp.$1),
                operator: RegExp.$2,
                operand: parseInt(RegExp.$3),
                comment: RegExp.$4
            });
        }
        this.code = code;
        callback(this.code);
    },
    run : function(memory, iter) {
        var pc = 1; // program counter == line number
        var ac = 0; // accumlator

        var LDA = function(operand) { ac = memory[operand]; pc++ }
        var LDI = function(operand) { ac = memory[memory[operand]]; pc++ }
        var STA = function(operand) { memory[operand] = ac; pc++ }
        var STI = function(operand) { memory[memory[operand]] = ac; pc++ }
        var ADD = function(operand) { ac += memory[operand]; pc++ }
        var SUB = function(operand) { ac -= memory[operand]; pc++ }
        var JMP = function(operand) { pc = operand; }
        var JMZ = function(operand) { if (ac == 0) pc = operand; else pc++ }
        var HLT = function(operand) { throw new Error('finish'); }

        var nextCode = function(codelist, pc) {
            for (var ln = pc; ln < 1024; ln++) {
                for (var key in codelist) {
                    if (codelist[key].lineno == ln) return codelist[key];
                }
            }
        };

        while (true) {
            code = nextCode(this.code, pc);
            if (!code) { throw new Error('Next code is not found.'); }
            if (iter) { iter(ac, code, memory); }
            var src = code.operator + '(' + code.operand + ')';
            eval(src);
        };
    }
};

ちなみにテキストには例として、「数値配列から重複した値を検索する処理」をランダムアクセス言語で表していました。Rubyだとこんなかんじかしら。

A = [3, 4, 2, 2]
B = Array.new(16, 0);

(0...A.size).each do |i|
  if B[A[i]] != 0
    puts A[i]
    exit 0
  else
    B[A[i]] = 1
  end
end

なので、今回のサンプルでもそのネタを使ってます。

実のところ、本体はざざっとすぐにできたのですが、そのままだと全然処理がわからないのでかなり困りました。Firebugでちまちまやるのもつまらない。ということで、処理が見えるようにやったのが以下（見える化が大変だった…）。

Random access machine

runボタンを押すと、textareaのコードが読み込まれて評価されていきます。記憶領域は右側です。それぞれrunを押下する前に弄くれるようになっています。
あと、1ステップ毎にダイアログが上がってくるので、じっくり見れる（一方、途中から鬱陶しくなってくる）ようになっています。途中で止めたかったらマウスでタブかウィンドウの閉じるを連打しつつ、スペースかエンターキーを連打すると、閉じられます（酷い仕様だなぁ）。
重複した値が見つかるとfinish的なダイアログが出て、答え用の記憶領域に「重複した値を指す指標i」が格納されるようになっています。

あと、おそらくFirefoxでしか動かないような気がします。

以下、自分にとってのプチ発見。

JavaScriptはFC2とかの無料ホームページに置いておくと何かと楽。
はてなは相変わらずJavaScriptさせてくれない。
JavaScriptで例外を投げるようにしておくとうれしい。