initial commit of (extremely) bare bones D implementationHEADmaster

1 files changed, 806 insertions, 0 deletions

diff --git a/interpreter.d b/interpreter.d
new file mode 100644
index 0000000..e73551d
--- /dev/null
+++ b/interpreter.d
@@ -0,0 +1,806 @@
+import std.stdio;
+import std.string;
+import std.file;
+import std.algorithm : canFind, map;
+import std.conv;
+
+
+interface Function : Expr { Expr run(Expr[] args, Expr[string] std); }
+
+class UserFunction : Function {
+
+	string name;
+	string[] argNames;
+	Expr[] bodyExprs;
+	this(string name, Cons argNames, Expr[] bodyExprs) {
+		this.name = name;
+		foreach (Expr arg; argNames.inner) {
+			Symbol sym = cast(Symbol) arg;
+			this.argNames ~= sym.value;
+		}
+		this.bodyExprs = bodyExprs;
+	}
+
+	Expr run(Expr[] args, Expr[string] std) {
+		Interpreter intrp = new Interpreter();
+		if (args.length != this.argNames.length) {
+			throw new Exception("wrong number of arguments!");
+		}
+
+		// resolve variables
+		Expr[] evaluated;
+		Expr[string] env = std.dup;
+		for (int i = 0; i < args.length; i++) {
+			env[this.argNames[i]] = intrp.evaluate(args[i], std);
+		}
+
+		// call the body
+		return intrp.interpret(this.bodyExprs, env);
+	}
+}
+
+interface Builtin : Function { }
+
+class If : Builtin {
+
+	this() {}
+
+	Expr run(Expr[] args, Expr[string] std) {
+		if (args.length != 2 && args.length != 3) {
+			throw new Exception("expected 2 or three arguments");
+		}
+		Interpreter intrp = new Interpreter();
+		Expr e1 = intrp.evaluate(args[0], std);
+		if (!cast(Bool) e1) {
+			throw new Exception("expected a boolean condition");
+		}
+		Bool cond = cast(Bool) e1;
+
+		if (cond.value) {
+			return intrp.evaluate(args[1], std);
+		} else if (args.length == 3) {
+			return intrp.evaluate(args[2], std);
+		} else {
+			return null;
+		}
+
+	}
+}
+
+class Addition : Builtin {
+
+	this() {}
+
+	Expr run(Expr[] args, Expr[string] std) {
+		Interpreter intrp = new Interpreter();
+		Number[] evaluated;
+		foreach (Expr e; args) {
+			Expr ret = intrp.evaluate(e, std);
+			if (!cast(Number) ret) {
+				throw new Exception("expected a number, got " ~ to!string(ret));
+			}
+			evaluated ~= cast(Number) ret;
+		}
+
+		float fsum = 0;
+		int isum = 0;
+		foreach (Number num; evaluated) {
+			if (cast(Int) num) {
+				Int tmp = cast(Int) num;
+				isum += tmp.value;
+			} else {
+				Float tmp = cast(Float) num;
+				fsum += tmp.value;
+			}
+		}
+
+		if (fsum != 0) {
+			float total = fsum + to!float(isum);
+			return new Float(total);
+		} else {
+			return new Int(isum);
+		}
+	}
+}
+
+class Subtraction : Builtin {
+	
+	this() { }
+
+	Expr run(Expr[] args, Expr[string] std) {
+		Interpreter intrp = new Interpreter();
+		Number[] evaluated;
+		foreach (Expr e; args) {
+			Expr ret = intrp.evaluate(e, std);
+			if (!cast(Number) ret) {
+				throw new Exception("expected a number, got " ~ to!string(ret));
+			}
+			evaluated ~= cast(Number) ret;
+		}
+
+		float total = 0;
+		bool first = true;
+		bool swapped = false;
+		foreach (Number num; evaluated) {
+			if (cast(Int) num) {
+				Int i = cast(Int) num;
+				if (first) {
+					total -= i.value;
+					first = false;	
+				} else if (!swapped) {
+					total = (-1 * total) - i.value;
+					swapped = true;
+				} else {
+					total -= i.value;
+				}
+			} else {
+				Float f = cast(Float) num;
+				if (first) {
+					total -= f.value;
+					first = false;	
+				} else if (!swapped) {
+					total = (-1 * total) - f.value;
+					swapped = true;
+				} else {
+					total -= f.value;
+				}
+			}
+		}
+
+		if (to!int(total) == total) {
+			return new Int(to!int(total));
+		} else {
+			return new Float(total);
+		}
+	}
+}
+
+class LessThan : Builtin {
+
+	this() {}
+
+	Expr run(Expr[] args, Expr[string] std) {
+		if (args.length != 2) {
+			throw new Exception("requires 2 arguments");
+		}
+
+		Interpreter intrp = new Interpreter();
+		Number[] evaluated;
+		foreach (Expr e; args) {
+			Expr ret = intrp.evaluate(e, std);
+			if (!cast(Number) ret) {
+				throw new Exception("expected a number, got " ~ to!string(ret));
+			}
+			evaluated ~= cast(Number) ret;
+		}
+
+
+		float left, right;
+		Number first = evaluated[0];
+		if (cast(Int) first) {
+			Int i = cast(Int) first;
+			left = to!float(i.value);
+		} else {
+			Float f = cast(Float) first;
+			left = f.value;
+		}
+
+		Number second = evaluated[1];
+		if (cast(Int) second) {
+			Int i = cast(Int) second;
+			right = to!float(i.value);
+		} else {
+			Float f = cast(Float) second;
+			right = f.value;
+		}
+
+		return new Bool(left < right);
+	}
+}
+
+class Interpreter {
+
+	this() { }
+
+	Expr interpret(Expr[] exprs, Expr[string] std) {
+		Expr ret;
+		foreach (Expr expr; exprs) {
+			ret = evaluate(expr, std);
+		}
+		return ret;
+	}
+
+	Number evaluateNumber(Expr expr, Expr[string] std) {
+		Expr ret = evaluate(expr, std);
+		if (!cast(Number) ret) {
+			throw new Exception("expected a number, got " ~ to!string(ret));
+		}
+		return cast(Number) ret;
+	}
+
+	Expr evaluate(Expr expr, Expr[string] std) {
+
+		if (cast(Cons) expr) {
+
+			Cons cons = cast(Cons) expr;
+			// an empty cons should be returned as-is
+			if (cons.inner.length == 0) {
+				return cons;
+			}
+
+			// look up the symbol, which is the first element
+			if (!cast(Symbol) cons.inner[0]) {
+				throw new Exception("cons must begin with a symbol");
+			}
+
+			Symbol sym = cast(Symbol) cons.inner[0];
+
+			if (sym.value == "func") {
+				//std
+				Symbol nameSym = cast(Symbol) cons.inner[1];
+				Cons funcArgs = cast(Cons) cons.inner[2];
+				UserFunction func = new UserFunction(nameSym.value, funcArgs, cons.inner[3..$]);
+
+				std[nameSym.value] = func;
+				return func;
+			}
+
+			Expr* ex = (sym.value in std);
+			if (ex is null) {
+				writeln("unknown symbol ", sym);
+				return null;
+			}
+
+			if (!cast(Function) ex) {
+				return *ex;
+			}
+
+			Function* func = cast(Function*) ex;
+
+			/*
+			Expr[] args;
+			foreach (Expr e; cons.inner[1..$]) {
+				args ~= this.evaluateNumber(e, std);
+			}
+			*/
+			Expr[] args = cons.inner[1..$];
+
+			//return func.run(cons.inner[1..$]);
+			return func.run(args, std);
+
+		} else if (cast(Symbol) expr) {
+			Symbol sym = cast(Symbol) expr;
+
+			return std[sym.value];
+		} else if (cast(Type) expr) {
+			return expr;
+		} else if (cast(Value) expr) {
+			return cast(typeof(expr)) expr;
+		} else {
+			writeln("not sure what this is ", expr);
+			return null;
+		}
+	}
+}
+
+//Number addition(
+
+class Parser {
+
+	int idx;
+	Token[] tokens;
+
+	this(Token[] tokens) {
+		this.tokens = tokens;
+	}
+
+	Type parseType() {
+		assert(this.tokens[this.idx].type == TokenType.COLON);
+		this.idx++;
+
+		Token token = this.tokens[this.idx];
+		Type type;
+		switch (token.type) {
+			case TokenType.SYMBOL:
+				type = new Type(token, null);
+				break;
+			case TokenType.OPEN_BRACKET:
+				this.idx++;  // opening bracket
+				Type inner = parseType();
+				this.idx++;  // closing bracket
+
+				if (this.tokens[this.idx].type != TokenType.CLOSE_BRACKET) {
+					throw new Exception("inner type not properly closed");
+				}
+				type = new Type(new Symbol(":[]"), inner);
+				break;
+			default:
+				throw new Exception("types must be a valid symbol");
+		}
+		return type;
+	}
+
+	Expr parseExpr() {
+		this.idx++; // open paren
+		
+		Token token;
+		Expr[] inner;
+		while(this.idx < this.tokens.length) {
+			token = this.tokens[this.idx];
+			if (token.type == TokenType.CLOSE_PAREN) {
+				break;
+			}
+
+			switch (token.type) {
+				case TokenType.OPEN_PAREN:
+					Expr expr = parseExpr();
+					inner ~= expr;
+					//this.idx--;  // to account for the extra closing?
+					break;
+				case TokenType.COLON:
+					Type type = this.parseType();
+					inner ~= type;
+					break;
+				default:
+					inner ~= token.value;
+					break;
+			}
+
+			this.idx++;
+		}
+
+		if (token.type == TokenType.EOF) {
+			throw new Exception("not enough closing parens!");
+		}
+		assert(token.type == TokenType.CLOSE_PAREN);
+		return new Cons(inner);
+	}
+
+	Expr[] parse() {
+		this.idx = 0;
+		Expr[] exprs;
+		Token token;
+		while (this.idx < this.tokens.length) {
+			token = this.tokens[this.idx];
+
+			if (token.type == TokenType.EOF) {
+				break;
+			}
+			
+			switch (token.type) {
+				case TokenType.OPEN_PAREN:
+					Expr expr = this.parseExpr();
+					exprs ~= expr;
+					break;
+				case TokenType.COLON:
+					Type type = this.parseType();
+					exprs ~= type;
+					break;
+				default:
+					exprs ~= token.value;
+					break;
+			}
+
+			this.idx++;
+		}
+
+		return exprs;
+	}
+
+}
+
+class Lexer {
+
+	int line, idx;
+	char[] data;
+
+	char[3] whitespace = [' ', '\t', '\n'];
+
+	this(char[] data) {
+		this.line = 1;
+		this.idx = 0;
+		this.data = data;
+	}
+
+	char peek() {
+		return data[this.idx + 1];
+	}
+
+	Token lexSymbol() {
+		int startLine = this.line;
+		char[] acc;
+
+		while (this.idx < this.data.length && 
+				!canFind([' ', '\t', '\n', ')', ']', '&', ','], this.data[idx])) {
+			acc ~= this.data[idx];
+			this.idx++;
+		}
+		this.idx--;
+
+		Value val = new Symbol(to!string(acc));
+		return Token(startLine, TokenType.SYMBOL, val);
+	}
+
+	Token lexString() {
+		assert(this.data[this.idx] == '"');
+		this.idx++;
+
+		int startLine = this.line;  // strings can be multi-lined
+		char[] acc;
+		bool esc = false;
+		while (this.idx < this.data.length) {
+			char ch = this.data[idx];
+
+			// end of the string
+			if (!esc && ch == '"') {
+				break;
+			}
+			// in an escape, always add the next character
+			else if (esc) {
+				acc ~= ch;
+				esc = false;
+			}
+			// escape character doesn't get added
+			else if (ch == '\\') {
+				esc = true;
+			}
+			// everything else is valid
+			else {
+				acc ~= ch;
+				if (ch == '\n') {
+					this.line++;
+				}
+			}
+
+			this.idx++;
+		}
+
+		if (this.idx == this.data.length) {
+			throw new Exception("EOF reached -- unterminated string!");
+		}
+
+		Value val = new String(to!string(acc));
+		return Token(startLine, TokenType.STRING, val);
+	}
+
+	Token lexNumber() {
+		int startLine = this.line;
+		char[] acc;
+		while (this.idx < this.data.length && 
+				!canFind([' ', '\t', '\n', ')', ']'], this.data[idx])) {
+			acc ~= this.data[idx];
+			this.idx++;
+		}
+
+		// if we got a newline, register it
+		if (this.data[idx] == '\n') {
+			this.line++;
+		}
+
+		Token tok;
+		Value val;
+		if (canFind(acc, '.')) {
+			float f;
+			try {
+				f = to!float(acc);
+			} catch (ConvException e) {
+				throw new Exception("invalid float!");
+			}
+			val = new Float(f);
+			tok = Token(startLine, TokenType.FLOAT, val);
+		} else {
+			int i;
+			try {
+				i = to!int(acc);
+			} catch (ConvException e) {
+				throw new Exception("invalid int!");
+			}
+			val = new Int(i);
+			tok = Token(startLine, TokenType.INT, val);
+		}
+
+		this.idx--;
+		return tok;
+
+	}
+
+	Token lexBool() {
+		assert(this.data[this.idx] == '#');
+
+		char[] acc = ['#'];
+		while (this.idx < this.data.length && !canFind([' ', '\t', '\n', ')', ']'], this.peek())) {
+			acc ~= this.peek();
+			this.idx++;
+		}
+
+		Value val;
+		switch (acc) {
+			case "#true":
+				val = new Bool(true);
+				break;
+			case "#false":
+				val = new Bool(false);
+				break;
+			default:
+				throw new Exception("bad bool");
+				break;
+		}
+
+		return Token(this.line, TokenType.BOOL, val);
+
+	}
+
+	Token[] lex() {
+		Token[] tokens;
+		while (idx < this.data.length) {
+			char ch = this.data[idx];
+
+			switch (ch) {
+				case ' ':
+					break;
+				case '\n':
+					this.line++;
+					break;
+				case '(':
+					tokens ~= Token(this.line, TokenType.OPEN_PAREN, null);
+					break;
+				case ')':
+					tokens ~= Token(this.line, TokenType.CLOSE_PAREN, null);
+					break;
+				case ':':
+					tokens ~= Token(this.line, TokenType.COLON, null);
+					break;
+				case '[':
+					tokens ~= Token(this.line, TokenType.OPEN_BRACKET, null);
+					break;
+				case ']':
+					tokens ~= Token(this.line, TokenType.CLOSE_BRACKET, null);
+					break;
+				// comments
+				case ';':
+					while (idx < this.data.length && this.peek() != '\n') {
+						idx++;
+					}
+					break;
+				// bool
+				case '#':
+					Token token = this.lexBool();
+					tokens ~= token;
+					break;
+				// int and float
+				case '0':.. case '9':
+					Token token = this.lexNumber();
+					tokens ~= token;
+					break;
+				// string
+				case '"':
+					Token token = this.lexString();
+					tokens ~= token;
+					break;
+				default:
+					Token token = this.lexSymbol();
+					tokens ~= token;
+					break;
+			}
+
+			this.idx++;
+		}
+		tokens ~= Token(this.line, TokenType.EOF);
+		return tokens;
+	}
+
+}
+
+
+char[] readFile(string fname) {
+
+	File f = File(fname, "r");
+
+	char[] ret = [];
+	while (!f.eof()) {
+		ret = ret ~ f.readln();
+	}
+	f.close();
+	return ret;
+}
+
+interface Expr { }
+
+class Cons : Expr {
+	string name;
+	Expr[] inner;
+	this(Expr[] inner) {
+		this.name = "cons";
+		this.inner = inner;
+	}
+
+	this(Expr wrap) {
+		this.inner ~= wrap;
+	}
+
+	override string toString() {
+		string ret = "(";
+		foreach (Expr e; this.inner) {
+			ret ~= to!string(e) ~ " ";
+		}
+		ret ~= ")";
+		return ret;
+	}
+}
+
+class Type : Expr {
+	string name;
+	Symbol sym;
+	int line;
+	Type inner;
+
+	this(Token tok) {
+		this.name = "type";
+		this.sym = to!Symbol(tok.value);
+		this.line = tok.line;
+		this.inner = null;
+	}
+
+	this(Token tok, Type inner) {
+		this.name = "type";
+		this.sym = to!Symbol(tok.value);
+		this.line = tok.line;
+		this.inner = inner;
+	}
+
+	this(Symbol sym) {
+		this.name = "type";
+		this.sym = sym;
+		this.inner = null;
+	}
+
+	this(Symbol sym, Type inner) {
+		this.name = "type";
+		this.sym = sym;
+		this.inner = inner;
+	}
+
+	override string toString() {
+		if (this.sym.value == ":[]") {
+			return ":[" ~ to!string(this.inner) ~ "]";
+		} else {
+			return ":" ~ to!string(this.sym.value);
+		}
+	}
+}
+
+class Value : Expr {
+	string name;
+	this(string name) {
+		this.name = name;
+	}
+}
+
+class Number : Value {
+	float value;
+	this(string name) {
+		super(name);
+	}
+}
+
+class Int : Number { 
+	int value;
+	this(int value) {
+		super("int");
+		this.value = value;
+	}
+
+	override string toString() {
+		return to!string(this.value);
+	}
+}
+
+class Float : Number { 
+	float value;
+	this(float value) {
+		super("float");
+		this.value = value;
+	}
+
+	override string toString() {
+		return to!string(this.value);
+	}
+}
+
+class Bool : Value {
+	bool value;
+	this(bool value) {
+		super("bool");
+		this.value = value;
+	}
+
+	override string toString() {
+		return '#' ~ to!string(this.value);
+	}
+}
+
+class String : Value {
+	string value;
+	this(string value) {
+		super("string");
+		this.value = value;
+	}
+
+	override string toString() {
+		return this.value;
+	}
+}
+
+class Symbol : Value {
+	string value;
+	this(string value) {
+		super("symbol");
+		this.value = value;
+	}
+
+	override string toString() {
+		return '\'' ~ this.value;
+	}
+}
+
+struct NebInt { int value; string name = "int"; }
+struct NebFloat { float value; string name = "float"; }
+struct NebBool { bool value; string name = "bool"; }
+
+//alias NebValue = SumType!(NebInt, NebFloat, NebBool);
+	
+
+struct Token {
+	int line;
+	TokenType type;
+	Value value;
+}
+
+enum TokenType { 
+	OPEN_PAREN,
+	CLOSE_PAREN,
+	OPEN_BRACKET,
+	CLOSE_BRACKET,
+	COLON,
+	EOF,
+	BOOL,
+	INT,
+	FLOAT,
+	STRING,
+	SYMBOL
+};
+
+int main(string[] args) {
+
+	if (args.length <= 1) {
+		writeln("no input file!");
+		return 1;
+	}
+
+	string fname = args[1];
+
+	if (!exists(fname)) {
+		writeln("file doesn't exist: ", fname);
+		return 1;
+	}
+
+	char[] data = readFile(fname);
+
+	Lexer lexer = new Lexer(data);
+	Token[] tokens = lexer.lex();
+
+	Parser parser = new Parser(tokens);
+	Expr[] exprs = parser.parse();
+
+	Expr[string] stdi;
+	stdi["+"] = new Addition();
+	stdi["-"] = new Subtraction();
+	stdi["<"] = new LessThan();
+	stdi["if"] = new If();
+
+	Interpreter interpreter = new Interpreter();
+	Expr result = interpreter.interpret(exprs, stdi);
+	writeln("=> ", result);
+
+	return 0;
+}