調子に乗ってS式評価機を
もはやantlrと何の関係もない……！
namespace SExpr {
public abstract class SExpr {
public override string ToString() {
StringBuilder sb = new StringBuilder();
ToString(sb);
return sb.ToString();
}
public abstract void ToString(StringBuilder sb);
public IEnumerator<SExpr> GetEnumerator() {
SExpr cur;
for(cur = this; cur is Cons; cur = ((Cons)cur).Cdr)
yield return ((Cons)cur).Car;
if(cur is Null)
yield break;
else
throw new Exception("not proper list.");
}
public SExpr this[int idx] {
get {
int i = idx;
foreach(SExpr se in this)
if(i-- == 0)
return se;
throw new Exception("idx rangeerr.");
}
}
}
public class Cons : SExpr {
public Cons(SExpr car, SExpr cdr) {
Car = car;
Cdr = cdr;
}
public SExpr Car;
public SExpr Cdr;
public override void ToString(StringBuilder sb) {
sb.Append('(');
SExpr cur;
for(cur = this; cur is Cons; cur = ((Cons)cur).Cdr) {
((Cons)cur).Car.ToString(sb);
sb.Append(' ');
}
if(cur is Null) {
;
} else {
sb.Append(". ");
cur.ToString(sb);
}
sb.Append(')');
}
}
public class Symbol : SExpr {
public Symbol(string name) {
Name = name;
}
public string Name;
public override void ToString(StringBuilder sb) {
sb.Append(Name);
}
}
public class Integer : SExpr {
public Integer(int v) {
Value = v;
}
public int Value;
public override void ToString(StringBuilder sb) {
sb.Append(Value);
}
}
public class Null : SExpr {
protected Null() { }
public override void ToString(StringBuilder sb) {
sb.Append("()");
}
public static Null Instance = new Null();
}
}
namespace SExpr {
public delegate SExpr ProcedureDelegate(SExpr args);
public class Procedure : SExpr {
public ProcedureDelegate Proc;
public Procedure(ProcedureDelegate proc) { Proc = proc; }
public override void ToString(StringBuilder sb) { sb.Append("<procedure>"); }
}
public class Closure : SExpr {
public Closure(Environment env, SExpr param, SExpr body) { Env = env; Params = param; Body = body; }
public override void ToString(StringBuilder sb) { sb.Append("<closure>"); }
public Environment Env;
public SExpr Params;
public SExpr Body;
}
public class Special : SExpr {
public Special(string name) { Name = name; }
public override void ToString(StringBuilder sb) { sb.Append(string.Format("<special:{0}>", Name)); }
public string Name;
}
public class Environment {
public Environment() : this(null) { }
public Environment(Environment parent) { Parent = parent; }
public Environment Parent;
Dictionary<string, SExpr> m_env = new Dictionary<string, SExpr>();
public SExpr this[SExpr symbol] {
get { return this[((Symbol)symbol).Name]; }
set { this[((Symbol)symbol).Name] = value; }
}
public SExpr this[string name] {
get { if(m_env.ContainsKey(name)) return m_env[name]; else return Parent[name]; }
set { m_env[name] = value; }
}
public void AddProc(string name, ProcedureDelegate proc) {
this[name] = new Procedure(proc);
}
}
public class Evaluator {
public Evaluator() { }
public Environment GlobalEnv = new Environment();
public SExpr Eval(SExpr src) {
return Eval(src, GlobalEnv);
}
private SExpr Eval(SExpr src, Environment env) {
if(src is Cons) {
return EvalList((Cons)src, env);
} else if(src is Symbol) {
return env[src];
} else {
return src;
}
}
private SExpr EvalList(Cons l, Environment env) {
SExpr head = Eval(l.Car, env);
if(head is Procedure) {
return ((Procedure)head).Proc(Map(l.Cdr, env));
} else if(head is Closure) {
Closure c = head as Closure;
return EvalClosure(c, Map(l.Cdr, env), env);
} else if(head is Special) {
return EvalSpecial((head as Special).Name, l.Cdr, env);
} else
throw new Exception("err");
}
private SExpr EvalClosure(Closure c, SExpr args, Environment env) {
Environment new_env = CreateEnv(env, c.Params, args);
SExpr result = Null.Instance;
foreach(SExpr se in c.Body)
result = Eval(se, new_env);
return result;
}
private SExpr Map(SExpr arr, Environment env) {
Stack<SExpr> stk = new Stack<SExpr>();
foreach(SExpr s in arr)
stk.Push(Eval(s, env));
SExpr r = Null.Instance;
while(stk.Count > 0) {
SExpr s = stk.Pop();
r = new Cons(s, r);
}
return r;
}
private SExpr EvalSpecial(string p, SExpr args, Environment env) {
switch(p) {
case "if":
if(Eval(args[0], env) is Null)
return Eval(args[2], env);
else
return Eval(args[1], env);
case "lambda":
return new Closure(env, args[0], (args as Cons).Cdr);
case "quote":
return args;
}
throw new Exception("unknown special form");
}
private Environment CreateEnv(Environment parent, SExpr param, SExpr args) {
Environment env = new Environment(parent);
IEnumerator<SExpr> cur = param.GetEnumerator();
IEnumerator<SExpr> argcur = args.GetEnumerator();
while(cur.MoveNext() && argcur.MoveNext()) {
env[(Symbol)cur.Current] = argcur.Current;
}
return env;
}
}
}
namespace SExpr {
class Program {
static void Main(string[] args) {
Evaluator eval = new Evaluator();
Environment e = eval.GlobalEnv;
e["'"] = new Special("quote");
e.AddProc("+", delegate(SExpr s) {
int result = 0;
foreach(Integer i in s)
result += i.Value;
return new Integer(result);
});
e.AddProc("-", delegate(SExpr s) {
int result = 0;
foreach(Integer i in s)
result -= i.Value;
result += ((Integer)s[0]).Value*2;
return new Integer(result);
});
e["if"] = new Special("if");
e["lambda"] = new Special("lambda");
while(true) {
SExpr s=null;
try {
SExprParser p = new SExprParser(new SExprLexer(Console.OpenStandardInput()));
s = p.sexpr();
if(s == null) {
Console.WriteLine("syntax err.");
} else {
Console.WriteLine(s);
Console.WriteLine(" ==> " + eval.Eval(s).ToString());
}
} catch {
Console.WriteLine("err");
}
}
}
}
}ふー、びっくりした。rubyだったら四分の一くらいで収まりそうだな。
