aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--interpreter.d806
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;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-10-29 05:46:37 +0000