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

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

最近，我發(fā)了一條推特，我喜歡上 lambda 演算了，它簡(jiǎn)單、強(qiáng)大。

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

已經(jīng)有許多編譯器/解析器/解釋器（compiler / parser / interpreter）的教程，但大多數(shù)不會(huì)引導(dǎo)你完整實(shí)現(xiàn)一種語言，因?yàn)閷?shí)現(xiàn)完全的語言語義，通常需要很多工作。不過在本文中， lambda 演算（譯者注：又寫作“λ 演算”，為統(tǒng)一行文，下文一律作 “l(fā)ambda 演算”）是如此簡(jiǎn)單，我們可以搞定一切！

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

lambda 演算（又寫作 “λ 演算”）是表達(dá)基于功能抽象和使用變量綁定和替代的應(yīng)用計(jì)算數(shù)學(xué)邏輯形式系統(tǒng)。這是一個(gè)通用的計(jì)算模型，可以用來模擬單帶圖靈機(jī)，在 20 世紀(jì) 30 年代，由數(shù)學(xué)家奧隆索·喬奇第一次引入，作為數(shù)學(xué)基礎(chǔ)的調(diào)查的一部分。

這是一個(gè)非常簡(jiǎn)單的 lambda 演算程序的模樣：

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

lambda 演算中只有兩個(gè)結(jié)構(gòu)，函數(shù)抽象（也就是函數(shù)聲明）和應(yīng)用（即函數(shù)調(diào)用），然而可以拿它做任何計(jì)算。

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

Term ::= Application
        | LAMBDA LCID DOT Term

Application ::= Application Atom
               | Atom

Atom ::= LPAREN Term RPAREN
        | LCID

語法告訴我們?nèi)绾卧诜治鲞^程中尋找 token 。但是等一下，token 是什么鬼？

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

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

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

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

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

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

_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): 返回下一個(gè) token 是否匹配 Token

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

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

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

OK，現(xiàn)在來看 “解析器”！

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

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

幸運(yùn)的是左遞歸可以用一個(gè)簡(jiǎn)單的技巧移除掉：

Application ::= Atom Application"

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

進(jìn)行分析時(shí)，需要以存儲(chǔ)分析出的信息，為此要建立 抽象語法樹 ( AST ) 。lambda 演算的 AST 非常簡(jiǎn)單，因?yàn)槲覀冎挥?3 種節(jié)點(diǎn)： Abstraction （抽象）， Application （應(yīng)用）以及 Identifier （標(biāo)識(shí)符）（譯者注： 為方便理解，這三個(gè)單詞不譯）。

Abstraction 持有其參數(shù)（param） 和主體（body）； Application 則持有語句的左右側(cè)； Identifier 是一個(gè)葉節(jié)點(diǎn)，只有持有該標(biāo)識(shí)符本身的字符串表示形式。

這是一個(gè)簡(jiǎn)單的程序及其 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" }
  }
}

現(xiàn)在有了我們的 AST 節(jié)點(diǎn)，可以拿它們來建構(gòu)真正的樹了。下面是基于語法中的生成規(guī)則的分析方法：

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;
  }
}

現(xiàn)在，我們可以用 AST 來給程序求值了。不過想知道我們的解釋器長(zhǎng)什么樣子，還得先看看 lambda 的求值規(guī)則。

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

我們的 term 是:

t1 t2   # Application

λx. t1  # Abstraction

x       # Identifier

是的，這些幾乎和我們的 AST 節(jié)點(diǎn)一模一樣！但這其中哪些是 value？

value 是最終的形式，也就是說，它們不能再被求值了。在這個(gè)例子中，唯一的既是 term 又是 value 的是 abstraction（不能對(duì)函數(shù)求值，除非它被調(diào)用）。

實(shí)際的求值規(guī)則如下：

1)       t1 -> t1"
     _________________

      t1 t2 -> t1" t2

2)       t2 -> t2"
     ________________

      v1 t2 -> v1 t2"

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

我們可以這樣解讀每一條規(guī)則：

如果 t1 是值為 t1" 的項(xiàng)， t1 t2 求值為 t1" t2。即一個(gè) application 的左側(cè)先被求值。

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

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

解釋器遵循求值規(guī)則，將一個(gè)程序歸化為 value?，F(xiàn)在我們將上面的規(guī)則用 JavaScript 寫出來：

首先定義一個(gè)工具，當(dāng)某個(gè)節(jié)點(diǎn)是 value 的時(shí)候告訴我們：

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;
    }
  }
};

代碼有點(diǎn)密，但睜大眼睛好好看下，可以看到編碼后的規(guī)則：

首先檢測(cè)其是否為 application，如果是，則對(duì)其求值：

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

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

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

現(xiàn)在，如果下一個(gè)節(jié)點(diǎn)是 identifier，我們只需將它替換為它所表示的變量綁定的值。

最后，如果沒有規(guī)則適用于AST，這意味著它已經(jīng)是一個(gè) value，我們將它返回。

另外一個(gè)值得提出的是上下文（context）。上下文持有從名字到值（AST節(jié)點(diǎn)）的綁定，舉例來說，調(diào)用一個(gè)函數(shù)時(shí)，就說你說傳的參數(shù)綁定到函數(shù)需要的變量上，然后再對(duì)函數(shù)體求值。

克隆上下文能保證一旦我們完成對(duì)右側(cè)的求值，綁定的變量會(huì)從作用域出來，因?yàn)槲覀冞€持有原來的上下文。

如果不克隆上下文， application 右側(cè)引入的綁定可能泄露并可以在左側(cè)獲取到 —— 這是不應(yīng)當(dāng)?shù)??？紤]下面的代碼：

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

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

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

到目前，我們完成了右側(cè)，它是 value，而 y 超出了作用域，因?yàn)槲覀兺顺隽?(λy. y)， 如果求值的時(shí)候不克隆上下文，我們會(huì)得到一個(gè)變化過的的上下文，綁定就會(huì)泄漏，y 的值就是 (λx. x)，最后得到錯(cuò)誤的結(jié)果。

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

一個(gè)簡(jiǎn)單的 辦法是為每個(gè)AST節(jié)點(diǎn)添加 toString方法：

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

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

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

現(xiàn)在我們可以在結(jié)果的根節(jié)點(diǎn)上調(diào)用 toString 方法，它會(huì)遞歸打印所有子節(jié)點(diǎn)， 以生成字符串表示形式。

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

// 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());

完整實(shí)現(xiàn)可以在 Github 上找到： github.com/tadeuzagallo/lc-js

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