## 如何使用 JavaScript 實現一門編程語言(6) —— Interpreter 到目前為止，我們寫了3個函數：InputStream，TokenStream 和 parse。為了從一段代碼中獲取AST，我們可以執行以下操作： ``` var ast = parse （TokenStream （InputStream （code ））） ; ``` 獲取AST后就可以編寫Interpreter（解釋器）了，這比寫parser容易。我們只需走AST，以正常順序執行表達式。 **執行環境** 正確執行表達式的關鍵是正確維護執行環境 - 一個擁有綁定變量的上下文。它將作為參數傳遞給我們的evaluate函數。每次我們進入”lambda”節點時，我們都必須用新變量（函數的參數）擴展環境，并用運行時傳遞的值對它們進行初始化。如果一個參數影響了外部作用域的變量，我們必須小心地在離開函數時恢復先前的值。 實現這個最簡單的方法是使用JavaScript的原型繼承。當我們輸入一個函數時，我們將創建一個新的環境。這種方式當我們退出時，我們不需要做任何事情——外部env已經包含在對象本身。 以下是Environment對象的定義： ``` function Environment(parent) { this.vars = Object.create(parent ? parent.vars : null); this.parent = parent; } Environment.prototype = { extend: function() { return new Environment(this); }, lookup: function(name) { var scope = this; while (scope) { if (Object.prototype.hasOwnProperty.call(scope.vars, name)) return scope; scope = scope.parent; } }, get: function(name) { if (name in this.vars) return this.vars[name]; throw new Error("Undefined variable " + name); }, set: function(name, value) { var scope = this.lookup(name); // let's not allow defining globals from a nested environment if (!scope && this.parent) throw new Error("Undefined variable " + name); return (scope || this).vars[name] = value; }, def: function(name, value) { return this.vars[name] = value; } }; ``` 一個Environment對象有一個parent屬性指向父作用域。在全局作用域下parent為null。它有一個vars屬性保存綁定的變量。 有以下方法： - extend() - 創建一個子作用域。 - lookup(name) - 查找具有給定名稱的變量的作用域。 - get(name) - 獲取變量的當前值。如果變量未定義，則會拋出錯誤。 - set(name, value) - 設置變量的值。這需要查找變量定義的實際作用域。如果找不到并且我們不在全局范圍內，則拋出錯誤。 - def(name, value) - 這會在當前范圍內創建（或覆蓋）一個變量。 **evaluate函數** 有了執行環境，我們就可以回到我們的主要問題（編寫Interpreter）中來，這個evaluate函數包含了一個大switch循環，按節點類型執行不同的邏輯，下面是每個節點的說明： ``` function evaluate(exp, env) { switch (exp.type) { ``` 常量節點，我們只返回它們的值： ``` case "num": case "str": case "bool": return exp.value; ``` 變量是從環境中提取的。請記住，”var” token，其value屬性包含變量名稱名稱： ``` case "var": return env.get(exp.value); ``` 對于賦值，我們需要檢查左側是否是一個 “var” token（如果不是，則拋出一個錯誤;現在我們不支持賦值給其他任何東西）。然后我們使用env.set設置值。 請注意，該值需要首先通過evaluate遞歸調用來計算。 ``` case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); return env.set(exp.left.value, evaluate(exp.right, env)); ``` 一個”binary”節點需要用到兩個操作數。我們稍后會寫這個apply_op函數，這很簡單。同樣，我們需要遞歸調用evaluator來計算left和right操作數 ``` case "binary": return apply_op(exp.operator, evaluate(exp.left, env), evaluate(exp.right, env)); ``` 一個”lambda”節點實際上會產生一個JavaScript閉包，所以它就像普通函數一樣可以從JavaScript中調用。我寫了一個make_lambda函數，將在后面定義它： ``` case "lambda": return make_lambda(env, exp); ``` 評估if節點很簡單：首先評估if條件。如果不成立，則評估then分支并返回其值。最后如果存在else分支，就評估，否則返回false. ``` case "if": var cond = evaluate(exp.cond, env); if (cond !== false) return evaluate(exp.then, env); return exp.else ? evaluate(exp.else, env) : false; ``` “prog”節點是一系列表達式。我們只是按順序評估它們并返回最后一個的值。對于一個空序列，返回值默認為false。 ``` case "prog": var val = false; exp.prog.forEach(function(exp){ val = evaluate(exp, env) }); return val; ``` 對于一個”call”節點，我們需要調用evaluate計算func函數。首先我們評估一下，它應該返回一個正常的JS函數，然后我們評估并應用該函數。 ``` case "call": var func = evaluate(exp.func, env); return func.apply(null, exp.args.map(function(arg){ return evaluate(arg, env); })); ``` 我們的程序不應該到下面這一步，但是為了防止在解析器中添加新的節點類型，并且忘記更新評估程序，讓我們拋出一個明確的錯誤。 ``` default: throw new Error("I don't know how to evaluate " + exp.type); } } ``` 這是evaluate函數的核心，你可以看到它非常簡單。最后，我們還需要編寫兩個函數，先從最簡單的apply_op函數開始： ``` function apply_op(op, a, b) { function num(x) { if (typeof x != "number") throw new Error("Expected number but got " + x); return x; } function div(x) { if (num(x) == 0) throw new Error("Divide by zero"); return x; } switch (op) { case "+" : return num(a) + num(b); case "-" : return num(a) - num(b); case "*" : return num(a) * num(b); case "/" : return num(a) / div(b); case "%" : return num(a) % div(b); case "&&" : return a !== false && b; case "||" : return a !== false ? a : b; case "<" : return num(a) < num(b); case ">" : return num(a) > num(b); case "<=" : return num(a) <= num(b); case ">=" : return num(a) >= num(b); case "==" : return a === b; case "!=" : return a !== b; } throw new Error("Can't apply operator " + op); } ``` 它接收運算符和其中需要運算的2個數，然后執行并返回而已。與JavaScript不同，我們只要求運算符的操作數為數字，并且使用num和div函數來檢查。對于字符串我們會定義其他的東西。 而make_lambda則有點微妙： ``` function make_lambda(env, exp) { function lambda() { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i < arguments.length ? arguments[i] : false); return evaluate(exp.body, scope); } return lambda; } ``` 正如你所看到的，它返回一個簡單的JavaScript函數，包含環境和表達式進行執行。 重點是，創建這個函數時什么都不會發生，但是當它被調用時，它會創建時的環境所使用的參數/值（如果傳遞的值少于函數的參數列表，缺少的部分默認為false）。 最后evaluate其函數體。 **原始功能** 如你所見，我們的語言沒有提供任何方式與外界進行交流。 在一些代碼示例中，我使用了一些print和println函數，但它們沒有在任何地方定義。 這些必須被定義為原始函數（也就是說，我們將用JavaScript編寫它們并將它們插入到全局環境中）。 現在把它放在一起，這里有一個測試程序： ``` // some test code here var code = "sum = lambda(x, y) x + y; print(sum(2, 3));"; // remember, parse takes a TokenStream which takes an InputStream var ast = parse(TokenStream(InputStream(code))); // create the global environment var globalEnv = new Environment(); // define the "print" primitive function globalEnv.def("print", function(txt){ console.log(txt); }); // run the evaluator evaluate(ast, globalEnv); // will print 5 ``` 您可以?[下載](http://annn.me/assets/download/lambda-eval1.js)?我們迄今為止編寫的代碼。它可以在NodeJS中運行——，例如： ``` echo 'sum = lambda(x, y) x + y; println(sum(2, 3));' | node lambda-eval1.js ```