簡単なインタプリタのテスト付きバージョン

ぜんぜん、簡単ではない、簡単なインタプリタにテストをつけて書き直しをしました。
１４回でここまで作るソースもあるのですけど、解説書く前にいろいろやることがあるとおもうので
まだまだ先になりそうです。

Go言語

C言語の後継としていい線いってそうな気がします。
Objective-Cの別構文なかんじで洗練されているのでしょうから。
並列処理が簡単にという機能もありがたい感じです。

構文については、式ベースにしてあるのかどうか調べてないので分かりませんが、おそらく違うのかなと。
Go言語を演算子で繋がるだけの構文にするとすると、
前置２項演算子というのがあって、そいつの優先順位をああだこうだ変えると
うまいこといろいろできるかもしれません。

func a b
var a b
と書けて、func, varがそれぞれaとbの項を持つとするのです。
イメージとしてはそんなかんじですが今までの蓄積がある文演算子のほうが（今は）扱いが楽です。
前置２項演算子の第一項は括弧が繋がらないことというルールを決めればいいのかもしれません。

以下ソースです。

import std.regexp;
import std.boxer;
import std.string;

class Tree {
  Tree opAdd(Tree b) {
    return new Op(this, Sym("+"), b);
  }
  Tree opSub(Tree b) {
    return new Op(this, Sym("-"), b);
  }
  Tree opMul(Tree b) {
    return new Op(this, Sym("*"), b);
  }
  Tree opDiv(Tree b) {
    return new Op(this, Sym("/"), b);
  }
  int opCmp(Tree b) {
    throw new Exception("undefined opCmp");
  }
}

class Sym : Tree {
  string str;
  static Sym[string] table;
  public this(string str) {
    this.str = str;
  }
  string toString() {
    return str;
  }
  static Sym opCall(string str) {
    if(str in table) return table[str];
    return table[str] = new Sym(str);
  }
}
static this() {
  nil = Sym("nil");
  vid = Sym("vid");
}
Tree nil;
Tree vid;

class Num : Tree {
  int n;
  this(int n) {
    this.n = n;
  }
  string toString() {
    return box(n).toString();
  }
  int opEquals(Tree t) {
    if(cast(Num)t) {
      Num s = cast(Num)t;
      return s.n == n;
    } else {
      return false;
    }
  }
  Tree opAdd(Tree b) {
    if (cast(Num)b) {
      Num bn = cast(Num)b;
      return new Num(this.n + bn.n);
    }
    return super.opAdd(b);
  }
  Tree opSub(Tree b) {
    if (cast(Num)b) {
      Num bn = cast(Num)b;
      return new Num(this.n - bn.n);
    }
    return super.opSub(b);
  }
  Tree opMul(Tree b) {
    if (cast(Num)b) {
      Num bn = cast(Num)b;
      return new Num(this.n * bn.n);
    }
    return super.opMul(b);
  }
  Tree opDiv(Tree b) {
    if (cast(Num)b) {
      Num bn = cast(Num)b;
      return new Num(this.n / bn.n);
    }
    return super.opDiv(b);
  }
  int opCmp(Tree b) {
    return (cast(Num)opSub(b)).n;
  }
}
Op push(ref Op[] t, Op a) {
  t.length = t.length + 1;
  t[$ - 1] = a;
  return a;
}
Tree push(ref Tree[] t, Tree a) {
  t.length = t.length + 1;
  t[$ - 1] = a;
  return a;
}
string join(Tree[] ts, string s) {
	string rc = "";
	foreach(Tree t; ts) {
		rc ~= t.toString() ~ s;
	}
	if(rc == "") return rc;
	return rc[0..$-1];
}
string toString(Tree[] t) {
	return "[" ~ t.join(",") ~ "]";
}

Tree shift(ref Tree[] t) {
  if(t.length == 0) return null;
  Tree t0 = t[0];
  t = t[1..$];
  return t0;
}

Tree first(ref Tree[] t) {
  if(t.length == 0) return null;
  return t[0];
}

class Lexer {
  Tree[] tokens(string src) {
    Tree[] ts;
    while (true) {
      bool t = true;
      foreach(m; RegExp("^[\\t ]*[\\r\\n][\\r\\n\\t ]*([(){}\\[\\]])").search(src)) {
        src = src[m.match(0).length..$];
        ts.push(Sym("n" ~ m.match(1)));
        t = false;
        break;
      }
      foreach(m; RegExp("^[\\r\\n\\t ]*([+*\\-\\/<>=]+|[(){}\\[\\],;]|[a-zA-Z_][a-zA-Z_0-9]*)").search(src)) {
        src = src[m.match(0).length..$];
        ts.push(Sym(m.match(1)));
        t = false;
        break;
      }
      foreach(m; RegExp("^[\\r\\n\\t ]*([0-9]+)").search(src)) {
        src = src[m.match(0).length..$];
        ts.push(new Num(std.string.atoi(m.match(1))));
        t = false;
        break;
      }
      if (t) return ts;
    }
  }
}

class IntHash {
  int[string] hash;
  IntHash opCall(string s, int n) {
    hash[s] = n;
    return this;
  }
  bool opIn_r(Tree t) {
    if(!cast(Sym)t) return false;
    Sym s = cast(Sym)t;
    return (s.str in hash) != null;
  }
  int opIndex(Tree t) {
    if(!cast(Sym)t) return -1;
    Sym s = cast(Sym)t;
    if (s.str in hash) {
      return hash[s.str];
    } else {
      return -1;
    }
  }
}

class StringHash {
  string[string] hash;
  StringHash opCall(string s, string n) {
    hash[s] = n;
    return this;
  }
  bool value(Tree s) {
    string str = s.toString();
    foreach(key,value; hash) {
      if(str == value) return true;
    }
    return false;
  }
  string opIndex(Tree s) {
    return hash[s.toString()];
  }
  bool opIn_r(Tree t) {
    if(!cast(Sym)t) return false;
    Sym s = cast(Sym)t;
    return (s.str in hash) != null;
  }
}

class Op : Tree {
  Tree l;
  Sym op;
  Tree r;
  this(Tree l, Sym op, Tree r) {
    this.l = l;
    this.op = op;
    this.r = r;
  }
  string toString() {
    return "Op(" ~ l.toString() ~ "," ~ op.toString() ~ "," ~ r.toString() ~ ")";
  }
}

class Parser {
  Tree[] tokens;
  IntHash opLs;
  IntHash opRs;
  IntHash opMs;
  IntHash opBs;
  StringHash opPs;
  StringHash opSs;

  Tree parse(string src) {
    opLs = (new IntHash)(">",190)("<",190)("+",10)("-",10)("*",20)("/",20)(",",2)("else",1);
    opRs = (new IntHash)("=",5);
    opBs = (new IntHash())("++",30)(";",1);
    opMs = (new IntHash)("(",200)("[",200)("{",200);
    opPs = (new StringHash)("(",")")("[","]")("{","}")("n(",")")("n[","]")("n{","}");
    opSs = (new StringHash)("fun","(")("if","(")("mac","(");
    tokens = (new Lexer).tokens(src);
    return exp();
  }
  Tree exp() {
    Tree t = expn(0);
    while(tokens.length > 0 && !opPs.value(tokens.first())) {
      t = new Op(t, Sym("@"), expn(0));
    }
    return t;
  }
  Tree expn(int p) {
    if (opPs.value(tokens.first())) {
      return vid;
    }
    Tree t = tokens.shift();
    if (t in opSs && opSs[t] == tokens.first().toString()) {
      Tree op = tokens.shift();
      Tree e = exp();
      Tree op2;
      if ((op2 = tokens.shift()).toString() != opPs[op]) {
        throw new Exception( "parser error 1 " ~ op2.toString());
      }
      t = new Op(e, Sym("S" ~ t.toString() ~ op.toString() ~ op2.toString()), expn(0));
    } else if (t in opPs) {
      Tree t2 = exp();
      string t3;
      if((t3 = tokens.shift().toString()) != opPs[t]) {
        throw new Exception("error");
      }
      string t4 = t.toString();
      if(t4[0]=='n') t4 = t4[1..$];
      t = new Op(t2, Sym("P" ~ t4 ~ t3), nil);
    }

    int tagp;
    while (true) {
      if (tokens.first() in opBs && (tagp = opBs[tokens.first()]) >= p) {
        Tree op = tokens.shift();
        t = new Op(t, Sym("B" ~ op.toString()), nil);
        p = tagp;
      } else if (tokens.first() in opMs && (tagp = opMs[tokens.first()]) >= p) {
        Tree op = tokens.shift();
        Tree e = expn(0);
        Tree op2;
        if((op2 = tokens.shift()).toString() != opPs[op]) throw new Exception("error");
        t = new Op(t, Sym("M" ~ op.toString() ~ op2.toString()), e);
      } else if (tokens.length > 0 && tokens.first() in opLs && (tagp = opLs[tokens.first()]) > p) {
        Tree op = tokens.shift();
        t = new Op(t, cast(Sym)op, expn(tagp));
      } else if(tokens.length > 0 && tokens.first() in opRs && (tagp = opRs[tokens.first()]) >= p) {
        Tree op = tokens.shift();
        t = new Op(t, cast(Sym)op, expn(tagp));
      } else {
        break;
      }
    }
    return t;
  }

}

class Env : Tree {
  Tree[string] env;
  this(Env parent = null) {
    if (parent !is null) env["parent"] = parent;
  }
  bool opIn_r(string name) {
    if (name in env) {
      return true;
    } else if("parent" in env && cast(Env)env["parent"]) {
      if(name in (cast(Env)env["parent"])) {
        return true;
      } else {
        return false;
      }
    } else {
      return false;
    }
  }
  Tree opIndex(string name) {
    if(name in env) return env[name];
    if("parent" in env) {
      if(cast(Env)env["parent"]) {
        return (cast(Env)env["parent"])[name];
      }
    }
    return nil;
  }
  Tree opIndexAssign( Tree value, string name) {
    if (put(name, value) == false) {
      env[name] = value;
    }
    return value;
  }
  bool put(string name, Tree value) {
    if (name in env) {
      env[name] = value;
      return true;
    } else if ("parent" in env && cast(Env)env["parent"]) {
      return (cast(Env)env["parent"]).put( name, value);
    } else {
      return false;
    }
  }
}

class Calc {
  Env env;
  Op[] macros;
  Tree evalute(string src) {
    Tree exp = (new Parser).parse(src);
    env = new Env();
    exp = macroExpand(exp);
    return this.execute(exp);
  }
  Tree macroExpand(Tree a) {
    foreach(Op mac; macros) {
      env = new Env(env);
      bool rc = macroMatch(mac.l, a);
      if (rc) {
        Tree r = execute(mac.r);
        env = cast(Env)env["parent"];
        return r;
      }
      env = cast(Env)env["parent"];
    }
    if (cast(Op)a) {
      Op op = cast(Op)a;
      if (op.op.str == "Smac()") {
        macros.push(op);
        return nil;
      } else
      if (op.op.str == "M()" && op.l.toString() == "add" && cast(Op)op.r && (cast(Op)op.r).op.toString() == ",") {
        return new Op(
          macroExpand((cast(Op)(op.r)).l),
          Sym("+"),
          macroExpand((cast(Op)(op.r)).r));
      } else {
        return new Op(macroExpand(op.l), op.op, macroExpand(op.r));
      }
    } else {
      return a;
    }
  }
  bool macroMatch (Tree a, Tree b) {
    if(cast(Op)a) {
      Op oa = cast(Op)a;
      if(oa.l == Sym("q") && oa.op.str == "M{}") {
        env[oa.r.toString()] = b;
        return true;
      } else if(cast(Op)b) {
        Op ob = cast(Op)b;
        return oa.op==ob.op && macroMatch(oa.l,ob.l) && macroMatch(oa.r, ob.r);
      } else {
        return false;
      }
    } else {
      return cast(bool)(a == b);
    }
  }
  Tree execute(Tree exp) {
    if (cast(Op)exp) {
      Op op = cast(Op)exp;
      switch (op.op.str) {
      case ",": return new Op(execute(op.l), op.op, execute(op.r));
      case "+": return this.execute(op.l) + this.execute(op.r);
      case "-": return this.execute(op.l) - this.execute(op.r);
      case "*": return this.execute(op.l) * this.execute(op.r);
      case "/": return this.execute(op.l) / this.execute(op.r);
      case "<": return new Num(this.execute(op.l) < this.execute(op.r));
      case ">": return new Num(this.execute(op.l) > this.execute(op.r));
      case "@": execute(op.l); return execute(op.r);
      case "=": Tree rc = execute(op.r); env[op.l.toString()] = rc; return rc;
      case "B;": return execute(op.l);
      case "B++": string name = op.l.toString(); Tree dt = env[name]; env[name] = dt + new Num(1); return dt;
      case "P()": return execute(op.l);
      case "P{}": return execute(op.l);
      case "M()":
        if(op.l==Sym("p")){
          exp = execute(op.r); printf("%.*s\n", exp.toString()); return exp;
        } else {
          Tree t = execute(op.l);
          if (!cast(Op)t && (cast(Op)t).op != Sym("Sfun()")) throw new Exception("undefined function " ~ op.l.toString());
          Tree r = execute(op.r);
          Op fun = cast(Op)t;
          Env back = env;
          env = new Env(cast(Env)fun.r);
          bind(env, (cast(Op)fun.l).l, r);
          Tree a = execute((cast(Op)fun.l).r);
          env = back;
          return a;
        }
      case "Sfun()": return new Op(exp, Sym("fun"), env);
      case "fun": return exp;
      case "Sif()":
        Tree l1 = this.execute(op.l);
        printf("%.*s\n", l1.toString());
        if (cast(Op)(op.r)!is null && (cast(Op)op.r).op.str == "else") {
          if (cast(Num)l1 !is null && (cast(Num)l1).n != 0) {
            return this.execute((cast(Op)op.r).l);
          } else {
            return this.execute((cast(Op)op.r).r);
          }
        } else {
          if (cast(Num)l1 !is null && (cast(Num)l1).n != 0) {
            return this.execute(op.r);
          } else {
            return nil;
          }
        }
      }
    } else if(exp==nil) {
      return nil;
    } else if(cast(Sym)exp) {
      string e = (cast(Sym)exp).str;
      if (e in env) return env[e];
      return new Num(0);
    } else {
      return exp;
    }
  }
  void bind(Env env, Tree p, Tree l) {
    if (cast(Sym)p) {
      env[p.toString()] = l;
    } else if(cast(Op)p) {
      Op op = cast(Op)p;
      Op ol = cast(Op)l;
      if(op.op != Sym(",")) throw new Exception("runtime error 3");
      if(ol.op != Sym(",")) throw new Exception("runtime error 4");
      bind(env, op.l, ol.l);
      bind(env, op.r, ol.r);
    } else {
      throw new Exception("runtime error 5");
    }
  }
}

void test(string result, string expected) {
  if(expected != result) {
    printf("error expected %.*s but result %.*s\n", expected, result);
  }
}

void main() {
  int v = 14;
  switch(v) {
  case 14:
    test((new Parser).parse("mac(mul(q{a},q{b}))a*b mul(3,4)").toString(),
      "Op(Op(Op(mul,M(),Op(Op(q,M{},a),,,Op(q,M{},b))),Smac(),Op(a,*,b)),@,Op(mul,M(),Op(3,,,4)))");
    test((new Calc).evalute("mac(mul(q{a},q{b}))a*b").toString(),"nil");
    test((new Calc).evalute("mac(mul(q{a},q{b}))a*b mul(2,3)").toString(),"6");
  case 13:
    test((new Parser).parse("add(1,2)").toString(),"Op(add,M(),Op(1,,,2))");
    test((new Calc).evalute("add(1,2)").toString(), "3");
  case 12:
    test((new Parser).parse("co=fun(b)b+1 co(3)").toString(), "Op(Op(co,=,Op(b,Sfun(),Op(b,+,1))),@,Op(co,M(),3))");
    test((new Calc).evalute("co=fun(b)b+1 co(3)").toString(), "4");
    test((new Parser).parse("co=fun(a){fun(b){a=a+b}} c=co(1)p(c(1))p(c(1))c(1)").toString(), "Op(Op(Op(Op(Op(co,=,Op(a,Sfun(),Op(Op(b,Sfun(),Op(Op(a,=,Op(a,+,b)),P{},nil)),P{},nil))),@,Op(c,=,Op(co,M(),1))),@,Op(p,M(),Op(c,M(),1))),@,Op(p,M(),Op(c,M(),1))),@,Op(c,M(),1))");
    test((new Calc).evalute("co=fun(a){fun(b){a=a+b}} c=co(1)p(c(1))p(c(1))c(1)").toString(), "4");
  case 11:
    test((new Parser).parse("b=2 p(b ++)\n(b)").toString(),
      "Op(Op(Op(b,=,2),@,Op(p,M(),Op(b,B++,nil))),@,Op(b,P(),nil))");
    test((new Calc).evalute("b=2 p(b ++)\n(b)").toString(), "3");
  case 10:
    test((new Parser).parse("b=2 p(b ++) b").toString(),
      "Op(Op(Op(b,=,2),@,Op(p,M(),Op(b,B++,nil))),@,b)");
    test((new Calc).evalute("b=2 p(b ++) b").toString(), "3");
  case 9:
    test((new Calc).evalute("a=1 b=2 a>b").toString(),"0");
    test((new Calc).evalute("a=2 b=1 a>b").toString(),"1");
    test((new Calc).evalute("a=1 b=2 if(a>b) 1 else 0").toString(),"0");
    test((new Calc).evalute("a=2 b=1 if(a>b) 1 else 0").toString(),"1");
    test((new Parser).parse("a=fun(a,b)if(a>b)1 else 2 a(1,2)").toString(),
      "Op(Op(a,=,Op(Op(a,,,b),Sfun(),Op(Op(a,>,b),Sif(),Op(1,else,2)))),@,Op(a,M(),Op(1,,,2)))");
    test((new Calc).evalute("a=fun(a,b)if(a>b)1 else 2 a(1,2)").toString(),"2");
    test((new Calc).evalute("add=fun(a,b)a+b add(1,2)").toString(), "3");
    test((new Calc).evalute("add=fun(a,b)a+b add(1+2,3)").toString(), "6");
  case 8:
    test((new Parser).parse("add=fun(a,b)a+b add(1,2)").toString(), "Op(Op(add,=,Op(Op(a,,,b),Sfun(),Op(a,+,b))),@,Op(add,M(),Op(1,,,2)))");
    test((new Calc).evalute("add=fun(a,b)a+b add(1,2)").toString(), "3");
  case 7:
    test((new Parser).parse("a=(1+2)*3 p(a) a+1").toString(), "Op(Op(Op(a,=,Op(Op(Op(1,+,2),P(),nil),*,3)),@,Op(p,M(),a)),@,Op(a,+,1))");
    test((new Calc).evalute("a=(1+2)*3 p(a) a+1").toString(), "10");
  case 6:
    test((new Calc).evalute("a={1+1 3}*3 a+1").toString(), "10");
    test((new Parser).parse("a=(1+2)*3 a+1").toString(), "Op(Op(a,=,Op(Op(Op(1,+,2),P(),nil),*,3)),@,Op(a,+,1))");
    test((new Calc).evalute("a=(1+2)*3 a+1").toString(), "10");
    test((new Parser).parse("a=(1+2)*3").toString(), "Op(a,=,Op(Op(Op(1,+,2),P(),nil),*,3))");
    test((new Calc).evalute("a=(1+2)*3").toString(), "9");
  case 5:
    test((new Parser).parse("a=1+2*3 a+4").toString(), "Op(Op(a,=,Op(1,+,Op(2,*,3))),@,Op(a,+,4))");
    test((new Calc).evalute("a=1+2*3 a+4").toString(), "11");
  case 4:
    test((new Parser).parse("1+2 * 3").toString(), "Op(1,+,Op(2,*,3))");
    test((new Calc).evalute("1+2 * 3").toString(), "7");
  case 3:
    test((new Calc).evalute("2").toString(), "2");
    test((new Calc).evalute("1+2").toString(), "3");
    test((new Calc).evalute("  1-2").toString(), "-1");
    test((new Calc).evalute("4/ 2").toString(), "2");
    if(v < 4) {
      test((new Calc).evalute("1+2 * 3").toString(), "9");
    }
    test((new Calc).evalute("2 *  3 +  4").toString(), "10");
  case 2:
    test((new Parser).parse("2").toString(), "2");
    test((new Parser).parse("1+2").toString(), "Op(1,+,2)");
    test((new Parser).parse("  1-2").toString(), "Op(1,-,2)");
    test((new Parser).parse("4/ 2").toString(), "Op(4,/,2)");
    if(v < 4) {
      test((new Parser).parse("1+2 * 3").toString(), "Op(Op(1,+,2),*,3)");
    }
    test((new Parser).parse("2 *  3 +  4").toString(), "Op(Op(2,*,3),+,4)");
  case 1:
    test((new Lexer).tokens("2").toString(), "[2]");
    test((new Lexer).tokens("1+2  ").toString(), "[1,+,2]");
    test((new Lexer).tokens("  1-2").toString(), "[1,-,2]");
    test((new Lexer).tokens("4/ 2").toString(), "[4,/,2]");
    test((new Lexer).tokens("1+2 * 3").toString(), "[1,+,2,*,3]");
    test((new Lexer).tokens("2 *  3 +  4").toString(), "[2,*,3,+,4]");
  }
}