処理系

JSでscheme処理系もどきを書こうと思ったけどdefine出来るネスト可な四則演算しか書けなかったorz.. 今週末気が向いたらフィボナッチが動くくらいはがんばるかな。
今回のだと下記くらいしかできない

(define a 3)
(define b 2)
(+ a (+ b 1) (/ 4 2) (+ 3 (- b a (+ 3 5))))

追記

このくらいは出来るようになった。

(define (f n m k)
  (+ n m (* m k) (- k n)))
(f 1 2 3)

下のをやろうとするとtoo much recursionで落ちる。
evalが無限ループしてるぽ。

(define (fib n)
  (if (< n 3)
    1
    (+ (fib (- n 1)) (fib (- n 2)))))
(fib 3)

var specialSymbols = ["define", "if"];
var globalSymbols = [];
var basicSymbols = {
  "define" : function(tree) {
    var sib = tree.getSibling();
    var sib2 = sib.getSibling();
    if (sib.type == Type.SYMBOL) {
      var symbolName = sib.value;
      var symbol = new Symbol(symbolName, sib2);
      sib.symbol = symbol;
      if (tree.parent && tree.parent.parent && 
          tree.parent.parent.value == "root") {
        globalSymbols[symbolName] = symbol;
      }
    } else if (sib.type == Type.LIST) {
      var children = sib.getChildren();
      var symbolName = children[0].value;
      var args = [];
      for (var i = 1; i < children.length; i++) {
        var child = children[i];
        args.push(child);
      }
      var symbol = new Symbol(symbolName, sib2, args);
      children[0].symbol = symbol;
      if (tree.parent && tree.parent.parent && 
          tree.parent.parent.value == "root") {
        globalSymbols[symbolName] = symbol;
      }
    }
  },

  "if" : function(tree) {
    var condition = tree.getSibling();
    var trueSentence = condition.getSibling();
    var falseSentence = trueSentence.getSibling();
    var parse = new Parse();
    var result = parse.eval(condition);
    if (result) {
      return parse.eval(trueSentence);
    } else {
      return parse.eval(falseSentence);
    }
  },

  "+" : function(ary) {
    var ret = 0;
    for (var i = 0; i < ary.length; i++) {
      try {
      ret += parseInt(ary[i]);
      } catch (e) {
        throw "plus: args must be num.";
      }
    }
    return ret;
  },

  "-" : function(ary) {
    var ret = 0;
    try {
      ret = parseInt(ary[0]);
    } catch (e) {
      throw "plus: args must be num.";
    }
    for (var i = 1; i < ary.length; i++) {
      try {
      ret -= parseInt(ary[i]);
      } catch (e) {
        throw "plus: args must be num.";
      }
    }
    return ret;
  },

  "*" : function(ary) {
    var ret = 0;
    if (ary.length != 2)
      throw "multi: args length must be 2.";
    try {
      var arg1 = parseInt(ary[0]);
      var arg2 = parseInt(ary[1]);
      ret = arg1 * arg2;
    } catch (e) {
      throw "multi: args mult be num.";
    }
    return ret;
  },

  "/" : function(ary) {
    var ret = 0;
    if (ary.length != 2)
      throw "div: args length must be 2.";
    try {
      var arg1 = parseInt(ary[0]);
      var arg2 = parseInt(ary[1]);
      ret = arg1 / arg2;
    } catch (e) {
      throw "div: args must be num.";
    }
    return ret;
  },

  ">" : function(ary) {
    var ret = false;
    if (ary.length != 2)
      throw ">: args length must be 2.";
    try {
      var arg1 = parseInt(ary[0]);
      var arg2 = parseInt(ary[1]);
      return arg1 > arg2;
    } catch (e) {
      throw ">: args must be num.";
    }
  },

  "<" : function(ary) {
    var ret = false;
    if (ary.length != 2)
      throw "<: args length must be 2.";
    try {
      var arg1 = parseInt(ary[0]);
      var arg2 = parseInt(ary[1]);
      return arg1 < arg2;
    } catch (e) {
      throw "<: args must be num.";
    }
  },

  "=" : function(ary) {
    var ret = false;
    if (ary.length != 2)
      throw "=: args length must be 2.";
    try {
      var arg1 = parseInt(ary[0]);
      var arg2 = parseInt(ary[1]);
      return arg1 == arg2;
    } catch (e) {
      throw "=: args must be num.";
    }
  },

};

var Type = new Object();
Object.extend(Type, {
  SYMBOL: "symbol",
  LIST: "list",
  NUM: "num"
});

var Symbol = Class.create({
  initialize: function(name, body, args) {
    this.name = name;
    this.body = body;
    this.args = args;
  }
});

var Tree = Class.create({
  initialize: function(parent, type, value) {
    this.parent = parent;
    this.children = [];
    this.sibling = null;
    this.type = type;
    this.value = value;
    this.symbol = null;
  },

  pushChild: function(child) {
    this.children.push(child);
  },

  setSibling: function(sib) {
    this.sibling = sib;
  },

  getChildren: function() {
    return this.children;
  },

  getSibling: function() {
    return this.sibling;
  },

  getSymbol: function() {
    return this.symbol;
  },
});

var Parse = Class.create({
  initialize: function() {
    this.root = new Tree(null, null, "root");
    this.input = $("inputtext");
    this.result = $("result");
    this.symbols = basicSymbols;
  },

  submit: function() {
    var source = this.input.value;
    this.run(source, this.root);
  },

  run: function(source, tree) {
    var tokens = this.getTokens(source);
    this.parse(tokens, this.root);
    var ret = this.eval(this.root);
    this.result.value = ret;
  },

  parse: function(tokens, tree) {
    var leftTree = null;
    var inFlag = false;
    for (var i = 0; i < tokens.length; i++) {
      var token = tokens[i];
      if (token == '(') {
        var newTree = new Tree(tree, Type.LIST, "list");
        if (leftTree == null) {
          leftTree = newTree;
        } else {
          leftTree.setSibling(newTree);
          leftTree = newTree;
        }
        tree.pushChild(newTree);
        i += this.parse(tokens.slice(i + 1, tokens.length), newTree);
      } else if (token == ')') {
        return i + 1;
      } else if (token.match(/[+-]?\d+/)) {
        var newTree = new Tree(tree, Type.NUM, token);
        if (leftTree == null) {
          leftTree = newTree;
        } else {
          leftTree.setSibling(newTree);
          leftTree = newTree;
        }
        tree.pushChild(newTree);
      } else {
        var newTree = new Tree(tree, Type.SYMBOL, token);
        if (leftTree == null) {
          leftTree = newTree;
        } else {
          leftTree.setSibling(newTree);
          leftTree = newTree;
        }
        tree.pushChild(newTree);
      }
    }
  },

  getTokens: function(source) {
    var list = [];
    var token = "";
    var i = 0;
    var c = source[0];
    while(c) {
      if (c.match(/\s/)) {
        if (token != "") {
          list.push(token);
          token = "";
        }
      } else if (c.match(/\(|\)|\'|\"/)) {
        if (token != "") {
          list.push(token);
          token = "";
        }
        list.push(c);
      } else if (c == "/") {
        if (token != "") {
          list.push(token);
          token = "";
        }
        list.push(c);
      } else {
        token = token.concat(c);
      }
      c = source[++i];
    }
    return list;
  },

  eval: function(tree) {
    var ret = null;
    var children = tree.getChildren();
    if (children.length == 0)
      return tree.value;
    for (var i = 0; i < children.length; i++) {
      var child = children[i];
      if (child.type == Type.SYMBOL) {
        if (specialSymbols.any(function(symbol) { return child.value == symbol;})) {
          return this.symbols[child.value].call(this, child);
        } else if (this.symbols[child.value]) {
          var sibling = child.sibling;
          var ary = [];
          while (sibling) {
            if (sibling.type == Type.SYMBOL) {
              var symbol = this.symbolSearch(sibling, sibling.value);
              if (symbol.body.type == Type.LIST) {
                ary.push(this.eval(symbol.body));
              } else if (symbol.body.type == Type.NUM) {
                ary.push(symbol.body.value);
              }
            } else if (sibling.type == Type.LIST) {
              ary.push(this.eval(sibling));
            } else if (sibling.type == Type.NUM) {
              ary.push(sibling.value);
            }
            sibling = sibling.sibling;
          }
          return this.symbols[child.value].call(this, ary);
        } else {
          var symbol = this.symbolSearch(child, child.value);
          var func = symbol.body;
          var args = symbol.args;
          var sibling = child.sibling;
          var ary = [];
          var i = 0;
          while (sibling) {
            var arg = args[i++];
            if (sibling.type == Type.SYMBOL) {
              var symbol = this.symbolSearch(sibling, sibling.value);
              if (symbol.body.type == Type.LIST) {
                var symbol = new Symbol(this.eval(symbol.body), sibling);
                sibling.symbol = symbol;
              } else if (symbol.body.type == Type.NUM) {
                var symbol = new Symbol(symbol.body, sibling);
                sibling.symbol = symbol;
              }
            } else if (sibling.type == Type.LIST) {
              var symbol = new Symbol(this.eval(sibling), sibling);
              sibling.symbol = symbol;
              globalSymbols[arg.value] = symbol; //bad
            } else if (sibling.type == Type.NUM) {
              var symbol = new Symbol(arg.value, sibling);
              tree.symbol = symbol;
              globalSymbols[arg.value] = symbol; //bad
            }
            sibling = sibling.sibling;
          }
          return this.eval(func);
        }
      } else if (child.type == Type.NUM) {
        return child.value;
      } else if (child.type == Type.LIST) {
        ret = this.eval(child);
        if (i == children.length - 1) 
          return ret;
      }      
    }
    return ret;
  },

  symbolSearch: function(tree, name) {
    var ret;
    this.symbolSearchItr(tree, name, ret);

    // search global scope
    if (ret == null) {
      ret = globalSymbols[name];
    }
    return ret;
  },

  symbolSearchItr: function(tree, name, ret) {
    var parent = tree.parent;
    if (parent == null)
      return;
    var children = parent.getChildren();
    for (var i = 0; i < children.length; i++) {
      var child = children[i];
      if (child == tree) {
        break;
      }
      if (child.symbol) {
        if (child.symbol.name == name) {
          ret = child.symbol;
        }
      }
    }
    this.symbolSearchItr(parent, name, ret);
  },

  debugPrint: function(tree) {
    var i = 0;
    tree.getChildren().each(function(child) {
      console.log(child.value);
      console.log(" ");
      if (child.getChildren()) {
        this.debugPrint(child);
      }
      console.log("\n");
    }.bind(this));
  }
});

ほとんどCのような書き方してるから、Cで書き直してsodexのshellに四則演算機能として組み込めるかな？