プログラミング言語の作り方の書き方

今日もプログラミング言語を作っていました。
否、プログラミング言語の作り方の効率的な書き方を考えていました。
だいたいのプログラミング言語の完成系はイメージがついているのですが、その過程をどれだけシンプルに書くか？
これは非常に難しい問題です。ですが、難しければそれに対応する手法ってのが存在するはずと。
で、今日やってみてたのは、test と diff と patch による工程の管理です。

testを作っておいてそれをこなせば何段階目まで出来ているということが明示できます。
適当に作り方を書くために作ったプログラムがバグっていたら意味がないので。テストは重要です。
ないテストがあったら、必要なバージョン以降のソースにすべて加えればよいわけです。
テストをしないでつくってあとでバグを直すと前のバージョンも遡らないといけないのです。

彫刻的アプローチ

これが大変なので、削る作業をしてみてたのですが、今度は作りすぎ問題が浮上してきました。
徐々に削っていって、最後にはじめのプログラムを作り出す。
という彫刻的アプローチです。

それで、PHPで作ったプログラムから順番につけた機能を削ってみたり、D言語で作ってみたりしてました。
まだまだ、ブレている部分があるので用語が統一できてないなとか、どうあるべきなのかナァ？ってことを永遠と考えてます。

自分が作ったとなるのか、はたまた、ほかの人が作ったとなるのかはわかりませんけど、未来には必ず自分が考えていることが
常識となると信じて作っています。

構文木処理系の名前

今はC式からなる言語というのを作っています。
Cは炭素の記号ですので、炭素から出来ている炭をつくり次にDiamondを作ろうとしているわけです。
それで今は、 Sumi 言語と呼んでいます。

しかし自分が考えている言語の方向性がどうも LISP に近いことが分かってきました。
構造がシンプルで方言が沢山ある言語です。
そうなると Sumi 言語というのは如何せん名前がよろしくないなと思うようになって来ました。

LISP は CONS セルを基本としたリストのプロセッサーです。
自分が考えているものは演算子を基本とした構文木の処理系なわけです。

Operator Syntax Tree Processorなので OSTP とでも名づけたら良いのかなぁ？
Syntax Tree Languageで stl だと、標準テンプレートライブラリだし。
いや、式プロセッサなんだから eXpression Processor 略して XP とかがいいんじゃ？でもそれじゃ検索が。。。
exppはヨーロッパうんたらかんたららしいとか。
等と考えているのでした。要するに未定だけど、別な名前を探しています。

[D言語]Dで書いた簡単なLISP級マクロ付き言語

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

class Tree {
  bool opEquals(Tree t) {
    return false;
  }
  Tree opAdd(Tree b) {
    throw new Exception("undefined opAdd");
  }
  Tree opSub(Tree b) {
    throw new Exception("undefined opSub");
  }
  Tree opMul(Tree b) {
    throw new Exception("undefined opMul");
  }
  Tree opDiv(Tree b) {
    throw new Exception("undefined opDiv");
  }
  int opCmp(Tree b) {
    throw new Exception("undefined opCmp");
  }
}
class Nil : Tree {
  public string toString() { return "nil"; }
}
class Vid : Tree {
  public string toString() { return "vid"; }
}
Nil nil;
Vid vid;
static this() {
  nil = new Nil();
  vid = new Vid();
}
class Str : Tree {
  string str;
  this(string str) {
    this.str = str;
  }
  string toString() {
    return str;
  }
  bool opEquals(Tree t) {
    if(cast(Str)t) {
      Str s = cast(Str)t;
      return s.str == str;
    } else {
      return false;
    }
  }
}
class Symbol : Tree {
  string str;
  private this(string str) {
    this.str = str;
  }
  static Symbol intern(string str) {
    static Symbol[string] arr;
    if(str in arr) return arr[str];
    return arr[str] = new Symbol(str);
  }
  bool opEquals(Tree t) {
    if(cast(Symbol)t) {
      Symbol s = cast(Symbol)t;
      return s == this;
    } else {
      return false;
    }
  }
  public string toString() {
    return "'" ~ str;
  }
}

class Num : Tree {
  int n;
  this(int n) {
    this.n = n;
  }
  string toString() {
    return box(n).toString();
  }
  bool 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;
  }
}

class Op : Tree {
  Tree l;
  Str op;
  Tree r;
  this(Tree l, Str op, Tree r) {
    this.l = l;
    this.op = op;
    this.r = r;
  }
  bool opEquals(Tree t) {
    if(cast(Op)t) {
      Op s = cast(Op)t;
      return l==s.l && s.op == this.op && r==s.r;
    } else {
      return false;
    }
  }

  string toString() {
    return "Op(" ~ l.toString() ~ "," ~ op.toString() ~ "," ~ r.toString() ~ ")";
  }
}
string to_s(ref Tree[] ts) {
  string r;
  foreach(Tree t; ts) {
    if (r != "") r ~= ",";
    r ~= t.toString();
  }
  return "[" ~ r ~ "]";
}

class Lexer {
  char[] src;
  this(char[] src) {
    this.src = src;
  }

  Tree lex() {
    
    foreach(m; RegExp("^[\\t ]*[\\r\\n][\\r\\n\\t ]*([(){}\\[\\]])").search(src)) {
      src = src[m.match(0).length..$];
      return new Str("n" ~ m.match(1));
    }
    foreach(m; RegExp("^[\\r\\n\\t ]*'([a-zA-Z_][a-zA-Z_0-9]*)").search(src)) {
      src = src[m.match(0).length..$];
      return Symbol.intern(m.match(1));
    }
    foreach(m; RegExp("^[\\r\\n\\t ]*([(){}\\[\\],]|[+*\\-\\/=<>]+|[a-zA-Z_][a-zA-Z_0-9]*)").search(src)) {
      src = src[m.match(0).length..$];
      return new Str(m.match(1));
    }
    foreach(m; RegExp("^[\\r\\n\\t ]*([0-9]+)").search(src)) {
      src = src[m.match(0).length..$];
      return new Num(std.string.atoi(m.match(1)));
    }
    return new Str("");
  }

  Tree[] tokens() {
    Tree[] ts;
    Tree token;
    while ((token = this.lex()) != new Str("")) {
      ts ~= token;
    }
    printf("%.*s\n", ts.to_s());
    return ts;
  }

}
Op push(ref Op[] t, Op a) {
  t.length = t.length + 1;
  t[$-1] = a;
  return a;
}
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 vid;
  return t[0];
}

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

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(Str)t) return false;
    Str s = cast(Str)t;
    return (s.str in hash) != null;
  }
}

class Parser {
  IntHash opLs;
  IntHash opRs;
  StringHash opPs;
  IntHash opMs;
  StringHash opSs;
  IntHash opBs;

  Tree[] tokens;
  this() {
    opLs = (new IntHash())(">",190)("<",190)("+",10)("-",10)("*",20)("/",20)(",",2)("else",1);
    opRs = (new IntHash())("=",5);
    opPs = (new StringHash())("(",")")("[","]")("{","}")("n(",")")("n[","]")("n{","}");
    opMs = (new IntHash())("(",200)("[",200)("{",200);
    opSs = (new StringHash())("fun","(")("if","(")("mac","(");
    opBs = (new IntHash())("++",30)(";",1);
  }

  Tree parse(string src) {
    Lexer lexer = new Lexer(src);
    tokens = lexer.tokens();
//    printf("%.*s", tokens.toString())
    Tree t = expn(0);
    while (tokens.length > 0) {
      t = new Op(t,new Str("@"), 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 = expn(0);
      Tree op2;
      if ((op2 = tokens.shift()).toString() != opPs[op]) {
        throw new Exception( "parser error 1 " ~ op2.toString());
      }
      t = new Op(e, new Str("S" ~ t.toString() ~ op.toString() ~ op2.toString()), expn(0));
    } else if (t in opPs) {
      Tree t2 = expn(0);
      string t3;
      if((t3 = tokens.shift().toString()) != opPs[t]) {
        throw new Exception("parser error 2");
      }
      string t4 = t.toString();
      if(t4[0]=='n') t4 = t4[1..$];
      t = new Op(t2, new Str("P" ~ t4 ~ t3), nil);
    }

    int tagp = 0;
    while (true) {
      if (tokens.first() in opBs && (tagp = opBs[tokens.first()]) >= p) {
        Tree op = tokens.shift();
        t = new Op(t, new Str("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("parser error 3");
        t = new Op(t, new Str("M" ~ op.toString() ~ op2.toString()), e);
      } else if (tokens.first() in opLs && (tagp = opLs[tokens.first()]) > p) {
        Tree op = tokens.shift();
        Str sop = cast(Str)op;
        sop.str = "L" ~ sop.str;
        t = new Op(t, sop, expn(tagp));
      } else if(tokens.first() in opRs && (tagp = opRs[tokens.first()]) >= p) {
        Tree op = tokens.shift();
        Str sop = cast(Str)op;
        sop.str = "R" ~ sop.str;
        t = new Op(t, sop, 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 {
  Parser parser;
  Env env;
  Op[] macros;
  this() {
    this.parser = new Parser();
  }

  Tree evalute(string src) {
    Tree exp = this.parser.parse(src);
    printf("%.*s\n", exp.toString());
    env = new Env();
    exp = macroExpand(exp);
    return this.execute(exp);
  }

  Tree macroExpand(Tree a) {
    foreach(Op obj; macros) {
      env = new Env(env);
      bool rc = macroMatch(obj.l, a);
      if (rc) {
        Tree r = execute(obj.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() == "L,") {
        return new Op(
          macroExpand((cast(Op)(op.r)).l),
          new Str("L+"),
          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 && cast(Op)b) {
        Op oa = cast(Op)a;
        Op ob = cast(Op)b;
        return oa.op==ob.op && macroMatch(oa.l,ob.l) && macroMatch(oa.r, ob.r);
    } else if (cast(Symbol)a) {
      string name = (cast(Symbol)a).str;
      env[name] = b;
      return true;
    } else {
      return a == b;
    }
  }
  
  Tree execute(Tree exp) {
    if (cast(Op)exp) {
      Op op = cast(Op)exp;
      switch (op.op.str) {
      case "L+": return this.execute(op.l) + this.execute(op.r);
      case "L-": return this.execute(op.l) - this.execute(op.r);
      case "L*": return this.execute(op.l) * this.execute(op.r);
      case "L/": return this.execute(op.l) / this.execute(op.r);
      case "L<": return new Num(this.execute(op.l) < this.execute(op.r));
      case "L>": return new Num(this.execute(op.l) > this.execute(op.r));
      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 "R=": return this.env[op.l.toString()] = this.execute(op.r);
      case "P()": return this.execute(op.l);
      case "P{}": return this.execute(op.l);
      case "P[]": return this.execute(op.l);
      case "M()":
        if(cast(Str)op.l && op.l.toString() == "p") {
          exp = execute(op.r); printf("%.*s\n", exp.toString());return exp;
        } else {
          Op fun = cast(Op)execute(op.l);
          Env back = env;
          env = new Env(cast(Env)fun.r);
          bind(env, (cast(Op)fun.l).l, op.r);
          Tree a = execute((cast(Op)fun.l).r);
          env = back;
          return a;
        }
      case "@": this.execute(op.l); return this.execute(op.r);
      case "Sfun()": return new Op(exp, new Str("fun"), env);
      case "fun": return exp;
      case "Sif()":
        Tree l1 = this.execute(op.l);
        if (cast(Op)(op.r)!is null && (cast(Op)op.r).op.str == "Lelse") {
          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;
          }
        }
      default: throw new Exception("runtime error 2 " ~ op.op.str);
      }
    } else if (cast(Str)exp) {
      if (exp.toString() in this.env) {
        return this.env[exp.toString()];
      } else {
        return new Num(0);
      }
    } else {
      return exp;
    }
  }

  void bind(Env env, Tree p, Tree l) {
    if (cast(Str)p) {
      env[p.toString()] = l;
    } else if(cast(Op)p) {
      Op op = cast(Op)p;
      Op ol = cast(Op)l;
      if(op.op.str != "L,") throw new Exception("runtime bind error 3");
      if(ol.op.str != "L,") throw new Exception("runtime bind error 4");
      bind(env, op.l, ol.l);
      bind(env, op.r, ol.r);
    } else {
      throw new Exception("runtime error 5");
    }
  }
}

void main() {

  auto parent = new Env();
  parent["hoge"] = new Num(10);
  auto env = new Env(parent);
  printf("%.*s\n", env["hoge"].toString());
  env["hoge"] = new Num(5);
  printf("%.*s\n", env["hoge"].toString());
  printf("%.*s\n", parent["hoge"].toString());
  
  auto calc = new Calc();

  printf("%.*s\n", calc.evalute("add=fun(a,b)if(a>b)1 else 2 add(1,2)").toString());
  printf("%.*s\n", calc.evalute("b=2 p(b ++) b").toString());
  printf("%.*s\n", calc.evalute("b=2 p(b ++)\n(b)").toString());
  printf("%.*s\n", calc.evalute("co=fun(b)b+1 co(3)").toString());
  printf("%.*s\n", calc.evalute("co=fun(a){fun(b){a=a+b}} c=co(1)p(c(1))p(c(1))c(1)").toString());
  printf("%.*s\n", calc.evalute("add(1,2)").toString());
  printf("%.*s\n", calc.evalute("mac(mul('a,'b))a*b mul(2,3)").toString());

}