Whitespaceのスタックマシン作成

Schemeの継続の実装について、いろいろマクロとかevalとかに悩んでで停滞してるので､
今度はWhitespaceに手を出してみました。
俺のニセSchemeもいづれはスタックマシンライクなバーチャルマシンで動かすつもりなので、その実験台として、Whitespaceのインタプリタ作成です。

Whitespaceは、スペース(' '), タブ('\t'), 改行('\n')だけで記述されるプログラミング言語で､印刷しても全く読めないため､スパイなどに向いているのだそうです。(Whitespace http://ja.wikipedia.org/wiki/Whitespace)

今回出来たのはスタックマシンのみです。まだWhitespaceのコードを解釈できるようにはなっていません。アセンブリ言語のような中間言語を実行できるだけです。

下記ソースをws.jsとして保存して、コマンドプロンプトから"cscript ws.js"と入力すれば実行できます。ずらーっとログが出たあと、フィボナッチ数列の10番目の値、55がスタックに残っているのが分かるんじゃないかと思います。

作って分かったこと

CPS変換ってのは、スタックマシン用のバイトコードにコンパイルできれば、十分なんじゃないかと思う。
あと、バイトコードに変換すると､末尾再帰の判定が簡単に出来そうな気がしてきた。つまり、関数内で自分と同じ関数が呼ばれた(再帰した)後、putLabel, jmpだけを通過してretに到達できていれば、末尾再帰なんだと思う。そしてその時は、再帰する場所で、実際に関数を呼び出すのではなく、今の関数の先頭にジャンプさせるっと・・・。

疑問点

store,retrieve,slide,readNumの各コマンドの実装が自信ない・・。

ソースは以下です。

// ws.js
// Whitespace用、スタックマシンのソース

//入出力関数
function p(x){
  WScript.StdOut.WriteLine(x);
}
function p_all(obj){
  for(var i in obj) p("["+i+"] = "+ obj[i]);
}
function printChar(ch){
  WScript.StdOut.Write(ch);
}
function readChar(){
  if(!WScript.StdIn.AtEndOfStream){
    return WScript.StdIn.Read(1);
  }
  return -1;
}

// 例外
function raise(str){
  throw new Exception(str);
}

// 文字列の置換
String.prototype.gsub = function (re, proc){
  if(this.match(re)){
    var result = "";
    var temp = this;
    while(temp.match(re)){
      result += RegExp.leftContext;
      result += proc(RegExp.lastMatch);
      temp = RegExp.rightContext;
    }
    return result + RegExp.rightContext;
  }else{
    return this;
  }
}

var pc=0;                        // プログラムカウンタ
var table = new Object();        // インストラクションテーブル
var alias = new Object();        // 上記の別名テーブル
var stack = new Array();        // スタック
var call_stack = new Array();    // コールスタック(returnする先)
var heap = new Array();          // ヒープ領域
var jump_table = new Array();    // ジャンプテーブル

// スタック操作
table["s"] = new Object();
table["s"]["s"]  = alias["putNum"]  = putNum;
table["s"]["ls"] = alias["dup"]     = dup;
table["s"]["ts"] = alias["copyAt"]  = copyAt;
table["s"]["lt"] = alias["swap"]    = swap;
table["s"]["ll"] = alias["discard"] = discard;
table["s"]["tl"] = alias["slide"]   = slide;

function putNum(n){
  stack.push(n);
}
function dup(){
  var x = stack.pop();
  stack.push(x);
  stack.push(x);
}
function copyAt(n){
  stack.push(stack[stack.length-1-n]);
}
function swap(n){
  var a = stack.pop();
  var b = stack.pop();
  stack.push(a);
  stack.push(b);
}
function discard(n){
  stack.pop();
}
function slide(n){
  // この処理自信ない
  var x = stack.pop();
  for(var i=0;i<stack.length;i++) stack.pop();
  stack.push(x);
}


// 数値演算
table["ts"] = new Object();
table["ts"]["ss"] = alias["add"] = add;
table["ts"]["st"] = alias["sub"] = sub;
table["ts"]["sl"] = alias["mul"] = mul;
table["ts"]["ts"] = alias["div"] = div;
table["ts"]["tt"] = alias["mod"] = mod;

function add(){
  var b = stack.pop();
  var a = stack.pop();
  stack.push(a+b);
}
function sub(){
  var b = stack.pop();
  var a = stack.pop();
  stack.push(a-b);
}
function mul(){
  var b = stack.pop();
  var a = stack.pop();
  stack.push(a*b);
}
function div(){
  var b = stack.pop();
  var a = stack.pop();
  stack.push(a/b);
}
function mod(){
  var b = stack.pop();
  var a = stack.pop();
  stack.push(a%b);
}


// ヒープアクセス
table["tt"] = new Object();  
table["tt"]["s"] = alias["store"]    = store;
table["tt"]["t"] = alias["retrieve"] = retrieve;

function store(){
  var val = stack.pop();
  var addr = stack.pop();
  heap[addr] = val;
  p(heap);
}
function retrieve(){
  var addr = stack.pop();
  if(!heap[addr]) heap[addr] = 0;
  stack.push(heap[addr]);
  p(heap);
}

// フロー制御
table["l"] = new Object();
table["l"]["ss"] = alias["putLabel"] = putLabel;
table["l"]["st"] = alias["call"] = call;
table["l"]["sl"] = alias["jmp"] = jmp;
table["l"]["ts"] = alias["jpz"] = jpz;
table["l"]["tt"] = alias["jpng"] = jpng;
table["l"]["tl"] = alias["ret"] = ret;
table["l"]["tt"] = alias["exit"] = exit;

function putLabel(label){
  // do nothing
}
function call(label){
  call_stack.push(pc);
  jmp(label);
}
function jmp(label){
  p("goto->"+label+"("+jump_table[label]+")");
  pc=jump_table[label];
}
function jpz(label){
  if( stack.pop() == 0){
    jmp(label);
  }
}
function jpng(label){
  if( stack.pop() < 0){
    jmp(label);
  }
}
function ret(){
  r = call_stack.pop();
  pc = r;
}
function exit(){
  throw new Error("exit");
}


// IO
table["tl"] = new Object();
table["tl"]["ss"] = alias["putc"] = putc;
table["tl"]["st"] = alias["puti"] = puti;
table["tl"]["ts"] = alias["readc"] = readc;
table["tl"]["tt"] = alias["readi"] = readi;

function putc(){
  var c = stack.pop();
  printChar(String.fromCharCode(c));
}
function puti(){
  var i = stack.pop();
  printNum(i);
}
function readc(){
  var c = readChar();
  stack.push(c.charCodeAt(0));
}
function readi(){
  // ここ、自信ない
  var c = readChar();
  stack.push(c-0);
}



// アセンブリ解析
function parse(src){
  // コメント削除
  var s = src.gsub(/\(.*\)/,
    function(x){return "";});
  
  var cmds = new Array();
  s.gsub(/[-_$\w:]+/, function(x){cmds.push(x);})
  
  return cmds;
}

// ジャンプテーブル初期化
function init_jump_table(cmds){
  var m;
  for(var i=0;i<cmds.length;i++){
    if(m = cmds[i].match(/putLabel:(\w+)/)){
      jump_table[m[1]] = i;
    }
  }
}

// アセンブリの命令の配列を評価
function eval(cmds){
  pc=0;
  while(pc<cmds.length){
    p("stack=["+stack.join(",")+"]"+" pc="+pc);
    p(cmds[pc]);
    var m = cmds[pc].match(/([a-z]+)(\:(\w+))?/i);
    if(m){
      var meth = alias[m[1]];
      var arg = m[3];
      if(arg){
        arg.match(/^\d+$/) ?
          meth(m[3]-0):
          meth(m[3]);
      }else{
        try{
          meth();
        }catch(e){
          if(e.message == "exit"){
            // exitコマンドで脱出してきた
            return ;
          }else{
            throw e;
          }
        }
      }
    }else{
      raise("eval");
    }
    pc++;
  }
}

prog=[
  "putNum:6",
  "call:fib",
  
//  "putNum:4",
//  "call:fact",

  "exit",

  "putLabel:fib",
  "dup",
  "putNum:2",
  "sub",
  "jpng:then_fib",
  "jmp:else_fib",
    "putLabel:then_fib",
    "jmp:endif_fib",
  "putLabel:else_fib",
    "dup",
    "putNum:1",
    "sub",
    "call:fib",
    "swap",
    "putNum:2",
    "sub",
    "call:fib",
    "add",
  "putLabel:endif_fib",
  "ret",

  "putLabel:fact",
    "dup",
    "jpz:then_fact",
    "jmp:else_fact",
    "putLabel:then_fact",
      "discard",
      "putNum:1",
      "jmp:end_fact",
    "putLabel:else_fact",
      "dup",
      "putNum:1",
      "sub",
      "call:fact",
      "mul",
    "putLabel:end_fact",
    "ret"

];

cmds = parse(prog.join("\n"));
init_jump_table(cmds);
//p_all(jump_table);
eval(cmds);
p(stack);