摘要：在開始解析之前，先通過詞法分析器運行源碼，這會將源碼打散成語法中全大寫的部分。我們基于每個規則的名稱的左側為其創建一個方法，再來看右側內容如果是全大寫的單詞，說明它是一個終止符即一個，詞法分析器會用到它。

本文轉載自：眾成翻譯
譯者：文藺
鏈接：http://www.zcfy.cc/article/661
原文：http://tadeuzagallo.com/blog/writing-a-lambda-calculus-interpreter-in-javascript/

最近，我發了一條推特，我喜歡上 lambda 演算了，它簡單、強大。

我當然聽說過 lambda 演算，但直到我讀了這本書 《類型和編程語言》（Types and Programming Languages） 我才體會到其中美妙。

已經有許多編譯器/解析器/解釋器（compiler / parser / interpreter）的教程，但大多數不會引導你完整實現一種語言，因為實現完全的語言語義，通常需要很多工作。不過在本文中， lambda 演算（譯者注：又寫作“λ 演算”，為統一行文，下文一律作 “lambda 演算”）是如此簡單，我們可以搞定一切！

首先，什么是 lambda 演算呢？維基百科是這樣描述的:

lambda 演算（又寫作 “λ 演算”）是表達基于功能抽象和使用變量綁定和替代的應用計算數學邏輯形式系統。這是一個通用的計算模型，可以用來模擬單帶圖靈機，在 20 世紀 30 年代，由數學家奧隆索·喬奇第一次引入，作為數學基礎的調查的一部分。

這是一個非常簡單的 lambda 演算程序的模樣：

(λx. λy. x) (λy. y) (λx. x)

lambda 演算中只有兩個結構，函數抽象（也就是函數聲明）和應用（即函數調用），然而可以拿它做任何計算。

編寫解析器之前，我們需要知道的第一件事是我們將要解析的語言的語法是什么，這是 BNF（譯者注：Backus–Naur Form，巴科斯范式， 上下文無關的語法的標記技術） 表達式：

Term ::= Application
        | LAMBDA LCID DOT Term

Application ::= Application Atom
               | Atom

Atom ::= LPAREN Term RPAREN
        | LCID

語法告訴我們如何在分析過程中尋找 token 。但是等一下，token 是什么鬼？

正如你可能已經知道的，解析器不會操作源代碼。在開始解析之前，先通過 詞法分析器（lexer） 運行源碼，這會將源碼打散成 token（語法中全大寫的部分）。我們可以從上面的語法中提取的如下的 token ：

LPAREN: "("
RPAREN: ")"
LAMBDA: "λ" // 為了方便也可以使用 “”
DOT: "."
LCID: /[a-z][a-zA-Z]*/ // LCID 表示小寫標識符
                       // 即任何一個小寫字母開頭的字符串

我們來建一個可以包含 type （以上的任意一種）的 Token 類，以及一個可選的 value (比如 LCID 的字符串)。

class Token {
  constructor(type, value) {
    this.type = type;
    this.value = value;
  }
};

現在我們可以拿上面定義的 token 來寫 詞法分析器（Lexer） 了， 為解析器解析程序提供一個很棒的 API 。

詞法分析器的 token 生成的部分不是很好玩：這是一個大的 switch 語句，用來檢查源代碼中的下一個字符：

_nextToken() {
  switch (c) {
    case "λ":
    case "":
      this._token = new Token(Token.LAMBDA);
      break;

    case ".":
      this._token = new Token(Token.DOT);
      break;

    case "(":
      this._token = new Token(Token.LPAREN);
      break;

    /* ... */
  }
}

下面這些方法是處理 token 的輔助方法：

next(Token): 返回下一個 token 是否匹配 Token

skip(Token): 和 next 一樣, 但如果匹配的話會跳過

match(Token): 斷言 next 方法返回 true 并 skip

token(Token): 斷言 next 方法返回 true 并返回 token

OK，現在來看 “解析器”！

解析器基本上是語法的一個副本。我們基于每個 production 規則的名稱（::= 的左側）為其創建一個方法，再來看右側內容 —— 如果是全大寫的單詞，說明它是一個 終止符 （即一個 token ），詞法分析器會用到它。如果是一個大寫字母開頭的單詞，這是另外一段，所以同樣為其調用 production 規則的方法。遇到 “/” （讀作 “或”）的時候，要決定使用那一側，這取決于基于哪一側匹配我們的 token。

這個語法有點棘手的地方是：手寫的解析器通常是遞歸下降（recursive descent）的（我們的就是），它們無法處理左側遞歸。你可能已經注意到了， Application 的右側開頭包含 Application 本身。所以如果我們只是遵循前面段落說到的流程，調用我們找到的所有 production，會導致無限遞歸。

幸運的是左遞歸可以用一個簡單的技巧移除掉：

Application ::= Atom Application"

Application" ::= Atom Application"
                | ε  # empty

進行分析時，需要以存儲分析出的信息，為此要建立 抽象語法樹 ( AST ) 。lambda 演算的 AST 非常簡單，因為我們只有 3 種節點： Abstraction （抽象）， Application （應用）以及 Identifier （標識符）（譯者注： 為方便理解，這三個單詞不譯）。

Abstraction 持有其參數（param） 和主體（body）； Application 則持有語句的左右側； Identifier 是一個葉節點，只有持有該標識符本身的字符串表示形式。

這是一個簡單的程序及其 AST:

(λx. x) (λy. y)

Application {
  abstraction: Abstraction {
    param: Identifier { name: "x" },
    body: Identifier { name: "x" }
  },
  value: Abstraction {
    param: Identifier { name: "y" },
    body: Identifier { name: "y" }
  }
}

現在有了我們的 AST 節點，可以拿它們來建構真正的樹了。下面是基于語法中的生成規則的分析方法：

term() {
  // Term ::= LAMBDA LCID DOT Term
  //        | Application
  if (this.lexer.skip(Token.LAMBDA)) {
    const id = new AST.Identifier(this.lexer.token(Token.LCID).value);
    this.lexer.match(Token.DOT);
    const term = this.term();
    return new AST.Abstraction(id, term);
  }  else {
    return this.application();
  }
}

application() {
  // Application ::= Atom Application"
  let lhs = this.atom();
  while (true) {
    // Application" ::= Atom Application"
    //                | ε
    const rhs = this.atom();
    if (!rhs) {
      return lhs;
    } else {
      lhs = new AST.Application(lhs, rhs);
    }
  }
}

atom() {
  // Atom ::= LPAREN Term RPAREN
  //        | LCID
  if (this.lexer.skip(Token.LPAREN)) {
    const term = this.term(Token.RPAREN);
    this.lexer.match(Token.RPAREN);
    return term;
  } else if (this.lexer.next(Token.LCID)) {
    const id = new AST.Identifier(this.lexer.token(Token.LCID).value);
    return id;
  } else {
    return undefined;
  }
}

現在，我們可以用 AST 來給程序求值了。不過想知道我們的解釋器長什么樣子，還得先看看 lambda 的求值規則。

首先，我們需要定義，什么是形式（terms）（從語法可以推斷），什么是值（values）。

我們的 term 是:

t1 t2   # Application

λx. t1  # Abstraction

x       # Identifier

是的，這些幾乎和我們的 AST 節點一模一樣！但這其中哪些是 value？

value 是最終的形式，也就是說，它們不能再被求值了。在這個例子中，唯一的既是 term 又是 value 的是 abstraction（不能對函數求值，除非它被調用）。

實際的求值規則如下：

1)       t1 -> t1"
     _________________

      t1 t2 -> t1" t2

2)       t2 -> t2"
     ________________

      v1 t2 -> v1 t2"

3)    (λx. t12) v2 -> [x -> v2]t12 

我們可以這樣解讀每一條規則：

如果 t1 是值為 t1" 的項， t1 t2 求值為 t1" t2。即一個 application 的左側先被求值。

如果 t2 是值為 t2" 的項， v1 t2 求值為 v1 t2"。注意這里左側的是 v1 而非 t1， 這意味著它是 value，不能再一步被求值，也就是說，只有左側的完成之后，才會對右側求值。

application (λx. t12) v2 的結果，和 t12 中出現的所有 x 被有效替換之后是一樣的。注意在對 application 求值之前，兩側必須都是 value。

解釋器遵循求值規則，將一個程序歸化為 value?，F在我們將上面的規則用 JavaScript 寫出來：

首先定義一個工具，當某個節點是 value 的時候告訴我們：

const isValue = node => node instanceof AST.Abstraction;

好了，如果 node 是 abstraction，它就是 value；否則就不是。

接下來是解釋器起作用的地方：

const eval = (ast, context={}) => {
  while (true) {
    if (ast instanceof AST.Application) {
      if (isValue(ast.lhs) && isValue(ast.rhs)) {
        context[ast.lhs.param.name] = ast.rhs;
        ast = eval(ast.lhs.body, context);
      } else if (isValue(ast.lhs)) {
        ast.rhs = eval(ast.rhs, Object.assign({}, context));
      } else {
        ast.lhs = eval(ast.lhs, context);
      }
    } else if (ast instanceof AST.Identifier) {
       ast = context[ast.name];
    } else {
      return ast;
    }
  }
};

代碼有點密，但睜大眼睛好好看下，可以看到編碼后的規則：

首先檢測其是否為 application，如果是，則對其求值：

若 abstraction 的兩側都是值，只要將所有出現的 x 用給出的值替換掉； (3)

否則，若左側為值，給右側求值；(2)

如果上面都不行，只對左側求值；(1)

現在，如果下一個節點是 identifier，我們只需將它替換為它所表示的變量綁定的值。

最后，如果沒有規則適用于AST，這意味著它已經是一個 value，我們將它返回。

另外一個值得提出的是上下文（context）。上下文持有從名字到值（AST節點）的綁定，舉例來說，調用一個函數時，就說你說傳的參數綁定到函數需要的變量上，然后再對函數體求值。

克隆上下文能保證一旦我們完成對右側的求值，綁定的變量會從作用域出來，因為我們還持有原來的上下文。

如果不克隆上下文， application 右側引入的綁定可能泄露并可以在左側獲取到 —— 這是不應當的。考慮下面的代碼：

(λx. y) ((λy. y) (λx. x))

這顯然是無效程序： 最左側 abstraction 中的標識符 y沒有被綁定。來看下如果不克隆上下文，求值最后變成什么樣。

左側已經是一個 value，所以對右側求值。這是個 application，所以會將 (λx .x) 與 y 綁定，然后對 (λy. y) 求值，而這就是 y 本身。所以最后的求值就成了 (λx. x)。

到目前，我們完成了右側，它是 value，而 y 超出了作用域，因為我們退出了 (λy. y)， 如果求值的時候不克隆上下文，我們會得到一個變化過的的上下文，綁定就會泄漏，y 的值就是 (λx. x)，最后得到錯誤的結果。

OK， 現在差不多完成了：已經可以將一個程序歸化為 value，我們要做的就是想辦法將這個 value 表示出來。

一個簡單的 辦法是為每個AST節點添加 toString方法：

/* Abstraction */ toString() {
  return `(λ${this.param.toString()}. ${this.body.toString()})`;
}

/* Application */ toString() {
  return `${this.lhs.toString()} ${this.rhs.toString()}`;
}

/* Identifier */ toString() {
  return this.name;
}

現在我們可以在結果的根節點上調用 toString 方法，它會遞歸打印所有子節點， 以生成字符串表示形式。

我們需要一個腳本，將所有這些部分連接在一起，代碼看起來是這樣的：

// assuming you have some source
const source = "(λx. λy. x) (λx. x) (λy. y)";

// wire all the pieces together
const lexer = new Lexer(source);
const parser = new Parser(lexer);
const ast = parser.parse();
const result = Interpreter.eval(ast);

// stringify the resulting node and print it
console.log(result.toString());

完整實現可以在 Github 上找到： github.com/tadeuzagallo/lc-js

感謝閱讀，一如既往地歡迎你的反饋！