## 十二、項目：編程語言 > 原文：[Project: A Programming Language](https://eloquentjavascript.net/12_language.html) > > 譯者：[飛龍](https://github.com/wizardforcel) > > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > > 自豪地采用[谷歌翻譯](https://translate.google.cn/) > > 部分參考了[《JavaScript 編程精解（第 2 版）》](https://book.douban.com/subject/26707144/) > 確定編程語言中的表達式含義的求值器只是另一個程序。 > > Hal Abelson 和 Gerald Sussman，《計算機程序的構造和解釋》  構建你自己的編程語言不僅簡單（只要你的要求不要太高就好），而且對人富有啟發。 希望通過本章的介紹，你能發現構建自己的編程語言其實并不是什么難事。我經常感到某些人的想法聰明無比，而且十分復雜，以至于我都不能完全理解。不過經過一段時間的閱讀和實驗，我就發現它們其實也并沒有想象中那么復雜。 我們將創造一門名為 Egg 的編程語言。這是一門小巧而簡單的語言，但是足夠強大到能描述你所能想到的任何計算。它允許基于函數的簡單抽象。 ## 解析 程序設計語言中最直觀的部分就是語法（syntax）或符號。解析器是一種程序，負責讀入文本片段（包含程序的文本），并產生一系列與程序結構對應的數據結構。若文本不是一個合法程序，解析器應該指出錯誤。 我們的語言語法簡單，而且具有一致性。Egg 中一切都是表達式。表達式可以是綁定名稱、數字，或應用（application）。不僅函數調用屬于應用，而且`if`和`while`之類的語言構造也屬于應用。 為了確保解析器的簡單性，Egg 中的字符串不支持反斜杠轉義符之類的元素。字符串只是簡單的字符序列（不包括雙引號），并使用雙引號包圍起來。數值是數字序列。綁定名由任何非空白字符組成，并且在語法中不具有特殊含義。 應用的書寫方式與 JavaScript 中一樣，也是在一個表達式后添加一對括號，括號中可以包含任意數量的參數，參數之間使用逗號分隔。 ``` do(define(x, 10), if(>(x, 5), print("large"), print("small"))) ``` Egg 語言的一致性體現在：JavaScript 中的所有運算符（比如`>`）在 Egg 中都是綁定，但是可以像其他函數一樣調用。由于語法中沒有語句塊的概念，因此我們需要使用`do`結構來表示多個表達式的序列。 解析器的數據結構用于描述由表達式對象組成的程序，每個對象都包含一個表示表達式類型的`type`屬性，除此以外還有其他描述對象內容的屬性。 類型為`"value"`的表達式表示字符串和數字。它們的`value`屬性包含對應的字符串和數字值。類型為`"word"`的表達式用于標識符（名稱）。這類對象以字符串形式將標識符名稱保存在`name`屬性中。最后，類型為`"apply"`的表達式表示應用。該類型的對象有一個`operator`屬性，指向其操作的表達式，還有一個`args`屬性，持有參數表達式的數組。 上面代碼中`> (x, 5)`這部分可以表達成如下形式： ```js { type: "apply", operator: {type: "word", name: ">"}, args: [ {type: "word", name: "x"}, {type: "value", value: 5} ] } ``` 我們將這樣一個數據結構稱為表達式樹。如果你將對象想象成點，將對象之間的連接想象成點之間的線，這個數據結構將會變成樹形。表達式中還會包含其他表達式，被包含的表達式接著又會包含更多表達式，這類似于樹的分支重復分裂的方式。  我們將這個解析器與我們第 9 章中編寫的配置文件格式解析器進行對比，第 9 章中的解析器結構很簡單：將輸入文件劃分成行，并逐行處理。而且每一行只有幾種簡單的語法形式。 我們必須使用不同方法來解決這里的問題。Egg 中并沒有表達式按行分隔，而且表達式之間還有遞歸結構。應用表達式包含其他表達式。 所幸我們可以使用遞歸的方式編寫一個解析器函數，并優雅地解決該問題，這反映了語言自身就是遞歸的。 我們定義了一個函數`parseExpression`，該函數接受一個字符串，并返回一個對象，包含了字符串起始位置處的表達式與解析表達式后剩余的字符串。當解析子表達式時（比如應用的參數），可以再次調用該函數，返回參數表達式和剩余字符串。剩余的字符串可以包含更多參數，也有可以是一個表示參數列表結束的右括號。 這里給出部分解析器代碼。 ```js function parseExpression(program) { program = skipSpace(program); let match, expr; if (match = /^"([^"]*)"/.exec(program)) { expr = {type: "value", value: match[1]}; } else if (match = /^\d+\b/.exec(program)) { expr = {type: "value", value: Number(match[0])}; } else if (match = /^[^\s(),"]+/.exec(program)) { expr = {type: "word", name: match[0]}; } else { throw new SyntaxError("Unexpected syntax: " + program); } return parseApply(expr, program.slice(match[0].length)); } function skipSpace(string) { let first = string.search(/\S/); if (first == -1) return ""; return string.slice(first); } ``` 由于 Egg 和 JavaScript 一樣，允許其元素之間有任意數量的空白，所以我們必須在程序字符串的開始處重復刪除空白。 這就是`skipSpace`函數能提供的幫助。 跳過開頭的所有空格后，`parseExpression`使用三個正則表達式來檢測 Egg 支持的三種原子的元素：字符串、數值和單詞。解析器根據不同的匹配結果構造不同的數據類型。如果這三種形式都無法與輸入匹配，那么輸入就是一個非法表達式，解析器就會拋出異常。我們使用`SyntaxError`而不是`Error`作為異常構造器，這是另一種標準錯誤類型，因為它更具體 - 它也是在嘗試運行無效的 JavaScript 程序時，拋出的錯誤類型。 接下來，我們從程序字符串中刪去匹配的部分，將剩余的字符串和表達式對象一起傳遞給`parseApply`函數。該函數檢查表達式是否是一個應用，如果是應用則解析帶括號的參數列表。 ```js function parseApply(expr, program) { program = skipSpace(program); if (program[0] != "(") { return {expr: expr, rest: program}; } program = skipSpace(program.slice(1)); expr = {type: "apply", operator: expr, args: []}; while (program[0] != ")") { let arg = parseExpression(program); expr.args.push(arg.expr); program = skipSpace(arg.rest); if (program[0] == ",") { program = skipSpace(program.slice(1)); } else if (program[0] != ")") { throw new SyntaxError("Expected ',' or ')'"); } } return parseApply(expr, program.slice(1)); } ``` 如果程序中的下一個字符不是左圓括號，說明當前表達式不是一個應用，parseApply會返回該表達式。 否則，該函數跳過左圓括號，為應用表達式創建語法樹。接著遞歸調用`parseExpression`解析每個參數，直到遇到右圓括號為止。此處通過`parseApply`和`parseExpression`互相調用，實現函數間接遞歸調用。 因為我們可以使用一個應用來操作另一個應用表達式（比如`multiplier(2)(1)`），所以`parseApply`解析完一個應用后必須再次調用自身檢查是否還有另一對圓括號。 這就是我們解析 Egg 所需的全部代碼。我們使用`parse`函數來包裝`parseExpression`，在解析完表達式之后驗證輸入是否到達結尾（一個 Egg 程序是一個表達式），遇到輸入結尾后會返回整個程序對應的數據結構。 ```js function parse(program) { let {expr, rest} = parseExpression(program); if (skipSpace(result.rest).length > 0) { throw new SyntaxError("Unexpected text after program"); } return expr; } console.log(parse("+(a, 10)")); // → {type: "apply", // operator: {type: "word", name: "+"}, // args: [{type: "word", name: "a"}, // {type: "value", value: 10}]} ``` 程序可以正常工作了！當表達式解析失敗時，解析函數不會輸出任何有用的信息，也不會存儲出錯的行號與列號，而這些信息都有助于之后的錯誤報告。但考慮到我們的目的，這門語言目前已經足夠優秀了。 ## 求值器（evaluator） 在有了一個程序的語法樹之后，我們該做什么呢？當然是執行程序了！而這就是求值器的功能。我們將語法樹和作用域對象傳遞給求值器，執行器就會求解語法樹中的表達式，然后返回整個過程的結果。 ```js const specialForms = Object.create(null); function evaluate(expr, scope) { if (expr.type == "value") { return expr.value; } else if (expr.type == "word") { if (expr.name in scope) { return scope[expr.name]; } else { throw new ReferenceError( `Undefined binding: ${expr.name}`); } } else if (expr.type == "apply") { let {operator, args} = expr; if (operator.type == "word" && operator.name in specialForms) { return specialForms[operator.name](expr.args, scope); } else { let op = evaluate(operator, scope); if (typeof op == "function") { return op(...args.map(arg => evaluate(arg, scope))); } else { throw new TypeError("Applying a non-function."); } } } } ``` 求值器為每一種表達式類型都提供了相應的處理邏輯。字面值表達式產生自身的值（例如，表達式`100`的求值為數值`100`）。對于綁定而言，我們必須檢查程序中是否實際定義了該綁定，如果已經定義，則獲取綁定的值。 應用則更為復雜。若應用有特殊形式（比如`if`），我們不會求解任何表達式，而是將表達式參數和環境傳遞給處理這種形式的函數。如果是普通調用，我們求解運算符，驗證其是否是函數，并使用求值后的參數調用函數。 我們使用一般的 JavaScript 函數來表示 Egg 的函數。在定義特殊格式`fun`時，我們再回過頭來看這個問題。 `evaluate`的遞歸結構類似于解析器的結構。兩者都反映了語言自身的結構。我們也可以將解析器和求值器集成到一起，在解析的同時求解表達式，但將其分離為兩個階段使得程序更易于理解。 這就是解釋 Egg 所需的全部代碼。這段代碼非常簡單，但如果不定義一些特殊的格式，或向環境中添加一些有用的值，你無法使用該語言完成很多工作。 ## 特殊形式 `specialForms`對象用于定義 Egg 中的特殊語法。該對象將單詞和求解這種形式的函數關聯起來。目前該對象為空，現在讓我們添加`if`。 ```js specialForms.if = (args, scope) => { if (args.length != 3) { throw new SyntaxError("Wrong number of args to if"); } else if (evaluate(args[0], scope) !== false) { return evaluate(args[1], scope); } else { return evaluate(args[2], scope); } }; ``` Egg 的`if`語句需要三個參數。Egg 會求解第一個參數，若結果不是`false`，則求解第二個參數，否則求解第三個參數。相較于 JavaScript 中的`if`語句，Egg 的`if`形式更類似于 JavaScript 中的`?:`運算符。這是一條表達式，而非語句，它會產生一個值，即第二個或第三個參數的結果。 Egg 和 JavaScript 在處理條件值時也有些差異。Egg 不會將 0 或空字符串作為假，只有當值確實為`false`時，測試結果才為假。 我們之所以需要將`if`表達為特殊形式，而非普通函數，是因為函數的所有參數需要在函數調用前求值完畢，而`if`則只應該根據第一個參數的值，確定求解第二個還是第三個參數。`while`的形式也是類似的。 ```js specialForms.while = (args, scope) => { if (args.length != 2) { throw new SyntaxError("Wrong number of args to while"); } while (evaluate(args[0], scope) !== false) { evaluate(args[1], scope); } // Since undefined does not exist in Egg, we return false, // for lack of a meaningful result. return false; }; ``` 另一個基本的積木是`do`，會自頂向下執行其所有參數。整個`do`表達式的值是最后一個參數的值。 ```js specialForms.do = (args, scope) => { let value = false; for (let arg of args) { value = evaluate(arg, scope); } }; ``` 我們還需要創建名為`define`的形式，來創建綁定對綁定賦值。`define`的第一個參數是一個單詞，第二個參數是一個會產生值的表達式，并將第二個參數的計算結果賦值給第一個參數。由于`define`也是個表達式，因此必須返回一個值。我們則規定`define`應該將我們賦予綁定的值返回（就像 JavaScript 中的`=`運算符一樣）。 ```js specialForms.define = (args, scope) => { if (args.length != 2 || args[0].type != "word") { throw new SyntaxError("Incorrect use of define"); } let value = evaluate(args[1], scope); scope[args[0].name] = value; return value; }; ``` ## 環境 `evaluate`所接受的作用域是一個對象，它的名稱對應綁定名稱，它的值對應這些綁定所綁定的值。 我們定義一個對象來表示全局作用域。 我們需要先定義布爾綁定才能使用之前定義的`if`語句。由于只有兩個布爾值，因此我們不需要為其定義特殊語法。我們簡單地將`true`、`false`兩個名稱與其值綁定即可。 ```js const topEnv = Object.create(null); topScope.true = true; topScope.false = false; ``` 我們現在可以求解一個簡單的表達式來對布爾值求反。 ```js let prog = parse(`if(true, false, true)`); console.log(evaluate(prog, topScope)); // → false ``` 為了提供基本的算術和比較運算符，我們也添加一些函數值到作用域中。為了確保代碼短小，我們在循環中使用` Function`來合成一批運算符，而不是分別定義所有運算符。 ```js for (let op of ["+", "-", "*", "/", "==", "<", ">"]) { topScope[op] = Function("a, b", `return a ${op} b;`); } ``` 輸出也是一個實用的功能，因此我們將`console.log`包裝在一個函數中，并稱之為`print`。 ```js topScope.print = value => { console.log(value); return value; }; ``` 這樣一來我們就有足夠的基本工具來編寫簡單的程序了。下面的函數提供了一個便利的方式來編寫并運行程序。它創建一個新的環境對象，并解析執行我們賦予它的單個程序。 ```js function run(program) { return evaluate(parse(program), Object.create(topScope)); } ``` 我們將使用對象原型鏈來表示嵌套的作用域，以便程序可以在不改變頂級作用域的情況下，向其局部作用域添加綁定。 ```js run(` do(define(total, 0), define(count, 1), while(<(count, 11), do(define(total, +(total, count)), define(count, +(count, 1)))), print(total)) `); // → 55 ``` 我們之前已經多次看到過這個程序，該程序計算數字 1 到 10 的和，只不過這里使用 Egg 語言表達。很明顯，相較于實現同樣功能的 JavaScript 代碼，這個程序并不優雅，但對于一個不足 150 行代碼的程序來說已經很不錯了。 ## 函數 每個功能強大的編程語言都應該具有函數這個特性。 幸運的是我們可以很容易地添加一個`fun`語言構造，`fun`將最后一個參數當作函數體，將之前的所有名稱用作函數參數。 ```js specialForms.fun = (args, scope) => { if (!args.length) { throw new SyntaxError("Functions need a body"); let body = args[args.length - 1]; let params = args.slice(0, args.length - 1).map(expr => { if (expr.type != "word") { throw new SyntaxError("Parameter names must be words"); } return expr.name; }); return function() { if (arguments.length != argNames.length) { throw new TypeError("Wrong number of arguments"); } let localScope = Object.create(scope); for (let i = 0; i < arguments.length; i++) { localScope[params[i]] = arguments[i]; } return evaluate(body, localScope); }; }; ``` Egg 中的函數可以獲得它們自己的局部作用域。 `fun`形式產生的函數創建這個局部作用域，并將參數綁定添加到它。 然后求解此范圍內的函數體并返回結果。 ```js run(` do(define(plusOne, fun(a, +(a, 1))), print(plusOne(10))) `); // → 11 run(` do(define(pow, fun(base, exp, if(==(exp, 0), 1, *(base, pow(base, -(exp, 1)))))), print(pow(2, 10))) `); // → 1024 ``` ## 編譯 我們構建的是一個解釋器。在求值期間，解釋器直接作用域由解析器產生的程序的表示。 編譯是在解析和運行程序之間添加的另一個步驟：通過事先完成盡可能多的工作，將程序轉換成一些可以高效求值的東西。例如，在設計良好的編程語言中，使用每個綁定時綁定引用的內存地址都是明確的，而不需要在程序運行時進行動態計算。這樣可以省去每次訪問綁定時搜索綁定的時間，只需要直接去預先定義好的內存位置獲取綁定即可。 一般情況下，編譯會將程序轉換成機器碼（計算機處理可以執行的原始格式）。但一些將程序轉換成不同表現形式的過程也被認為是編譯。 我們可以為 Egg 編寫一個可供選擇的求值策略，首先使用`Function`，調用 JavaScript 編譯器編譯代碼，將 Egg 程序轉換成 JavaScript 程序，接著執行編譯結果。若能正確實現該功能，可以使得 Egg 運行的非常快，而且實現這種編譯器確實非常簡單。 如果讀者對該話題感興趣，愿意花費一些時間在這上面，建議你嘗試實現一個編譯器作為練習。 ## 站在別人的肩膀上 我們定義`if`和`while`的時候，你可能注意到他們封裝得或多或少和 JavaScript 自身的`if`、`while`有點像。同樣的，Egg 中的值也就是 JavaScript 中的值。 如果讀者比較一下兩種 Egg 的實現方式，一種是基于 JavaScrip t之上，另一種是直接使用機器提供的功能構建程序設計語言，會發現第二種方案需要大量工作才能完成，而且非常復雜。不管怎么說，本章的內容就是想讓讀者對編程語言的運行方式有一個基本的了解。 當需要完成一些任務時，相比于自己完成所有工作，借助于別人提供的功能是一種更高效的方式。雖然在本章中我們編寫的語言就像玩具一樣，十分簡單，而且無論在什么情況下這門語言都無法與 JavaScript 相提并論。但在某些應用場景中，編寫一門微型語言可以幫助我們更好地完成工作。 這些語言不需要像傳統的程序設計語言。例如，若 JavaScript 沒有正則表達式，你可以為正則表達式編寫自己的解析器和求值器。 或者想象一下你在構建一個巨大的機械恐龍，需要編程實現恐龍的行為。JavaScript 可能不是實現該功能的最高效方式，你可以選擇一種語言作為替代，如下所示： ``` behavior walk perform when destination ahead actions move left-foot move right-foot behavior attack perform when Godzilla in-view actions fire laser-eyes launch arm-rockets ``` 這通常被稱為領域特定語言（Domain-specific Language），一種為表達極為有限的知識領域而量身定制的語言。它可以準確描述其領域中需要表達的事物，而沒有多余元素。這種語言比通用語言更具表現力。 ## 習題 ### 數組 在 Egg 中支持數組需要將以下三個函數添加到頂級作用域：`array(...values)`用于構造一個包含參數值的數組，`length(array)`用于獲取數組長度，`element(array, n)`用于獲取數組中的第`n`個元素。 ```js // Modify these definitions... topEnv.array = "..."; topEnv.length = "..."; topEnv.element = "..."; run(` do(define(sum, fun(array, do(define(i, 0), define(sum, 0), while(<(i, length(array)), do(define(sum, +(sum, element(array, i))), define(i, +(i, 1)))), sum))), print(sum(array(1, 2, 3)))) `); // → 6 ``` ### 閉包 我們定義`fun`的方式允許函數引用其周圍環境，就像 JavaScript 函數一樣，函數體可以使用在定義該函數時可以訪問的所有局部綁定。 下面的程序展示了該特性：函數f返回一個函數，該函數將其參數和f的參數相加，這意味著為了使用綁定a，該函數需要能夠訪問f中的局部作用域。 ```js run(` do(define(f, fun(a, fun(b, +(a, b)))), print(f(4)(5))) `); // → 9 ``` 回顧一下fun形式的定義，解釋一下該機制的工作原理。 ### 注釋 如果我們可以在 Egg 中編寫注釋就太好了。例如，無論何時，只要出現了井號（`#`），我們都將該行剩余部分當成注釋，并忽略之，就類似于 JavaScript 中的`//`。 解析器并不需要為支持該特性進行大幅修改。我們只需要修改`skipSpace`來像跳過空白符號一樣跳過注釋即可，此時調用`skipSpace`時不僅會跳過空白符號，還會跳過注釋。修改代碼，實現這樣的功能。 ```js // This is the old skipSpace. Modify it... function skipSpace(string) { let first = string.search(/\S/); if (first == -1) return ""; return string.slice(first); } console.log(parse("# hello\nx")); // → {type: "word", name: "x"} console.log(parse("a # one\n # two\n()")); // → {type: "apply", // operator: {type: "word", name: "a"}, // args: []} ``` ### 修復作用域 目前綁定賦值的唯一方法是`define`。該語言構造可以同時實現定義綁定和將一個新的值賦予已存在的綁定。 這種歧義性引發了一個問題。當你嘗試為一個非局部綁定賦予新值時，你最后會定義一個局部綁定并替換掉原來的同名綁定。一些語言的工作方式正和這種設計一樣，但是我總是認為這是一種笨拙的作用域處理方式。 添加一個類似于`define`的特殊形式`set`，該語句會賦予一個綁定新值，若綁定不存在于內部作用域，則更新其外部作用域相應綁定的值。若綁定沒有定義，則拋出`ReferenceError`（另一個標準錯誤類型）。 我們目前采取的技術是使用簡單的對象來表示作用域對象，處理目前的任務非常方便，此時我們需要更進一步。你可以使用`Object.getPrototypeOf`函數來獲取對象原型。同時也要記住，我們的作用域對象并未繼承`Object.prototype`，因此若想調用`hasOwnProperty`，需要使用下面這個略顯復雜的表達式。 ```js Object.prototype.hasOwnProperty.call(scope, name); ``` ```js specialForms.set = function(args, env) { // Your code here. }; run(` do(define(x, 4), define(setx, fun(val, set(x, val))), setx(50), print(x)) `); // → 50 run(`set(quux, true)`); // → Some kind of ReferenceError ```