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

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

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

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

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

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

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

這是一個(gè)非常簡單的 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)知道的，解析器不會操作源代碼。在開始解析之前，先通過 詞法分析器（lexer） 運(yùn)行源碼，這會將源碼打散成 token（語法中全大寫的部分）。我們可以從上面的語法中提取的如下的 token ：

LPAREN: "("
RPAREN: ")"
LAMBDA: "λ" // 為了方便也可以使用 “”
DOT: "."
LCID: /[a-z][a-zA-Z]*/ // LCID 表示小寫標(biāo)識符
                       // 即任何一個(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 一樣, 但如果匹配的話會跳過

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 ），詞法分析器會用到它。如果是一個(gè)大寫字母開頭的單詞，這是另外一段，所以同樣為其調(diào)用 production 規(guī)則的方法。遇到 “/” （讀作 “或”）的時(shí)候，要決定使用那一側(cè)，這取決于基于哪一側(cè)匹配我們的 token。

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

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

Application ::= Atom Application"

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

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

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

這是一個(gè)簡單的程序及其 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 來給程序求值了。不過想知道我們的解釋器長什么樣子，還得先看看 lambda 的求值規(guī)則。

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

我們的 term 是:

t1 t2   # Application

λx. t1  # Abstraction

x       # Identifier

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

value 是最終的形式，也就是說，它們不能再被求值了。在這個(gè)例子中，唯一的既是 term 又是 value 的是 abstraction（不能對函數(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è)的完成之后，才會對右側(cè)求值。

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

解釋器遵循求值規(guī)則，將一個(gè)程序歸化為 value。現(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ī)則：

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

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

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

如果上面都不行，只對左側(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ù)需要的變量上，然后再對函數(shù)體求值。

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

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

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

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

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

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

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

一個(gè)簡單的 辦法是為每個(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 方法，它會遞歸打印所有子節(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

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