用 Javascript 编写λ演算解释器

本文讲的是用 Javascript 编写λ演算解释器，


最近，我在推特上对λ演算非常着迷，它是如此简单和强大。

当然我之前听说过λ演算，但是直到我读了这本书 Types and Programming Languages 我才真正了解了它的美丽之处。

有许多其他的编译器、剖析器、解释器的教程，但是它们大多不会指导你遍览语言的全部实现，因为编程语言的实现需要进行大量的工作，然而λ演算是如此简单以至于我们可以完全讲解。

首先，什么是λ演算？这里是一个 Wikipedia 的描述：

λ演算（英语：lambda calculus，λ-calculus）是一套在数学逻辑上针对表达式计算的形式系统，主要使用变量绑定和替换来研究函数定义、函数应用。它是一种计算的统一模型，可以被用来模拟任何单步图灵机。数学家 Alonzo Church 在20世纪30年代首次提出了这个概念作为基础数学的一个研究。

一个简单的λ演算程序如下：

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

在λ演算仅仅有两种构造：函数定义（例如：一个函数声明）和函数应用（例如：函数调用）。有了这两种构造之后你就可以做任何计算了。

1. 语法

在介绍 Parser 之前，我们要做的第一件事情是了解一下所要 Parser 的语言的语法，这里是 BNF ：

Term ::= Application
        | LAMBDA LCID DOT Term

Application ::= Application Atom
               | Atom

Atom ::= LPAREN Term RPAREN
        | LCID

语法告诉了我们如何在 Parser 阶段查找 Token ，但是 Token 又是什么呢？

2. Token

你可能早已了解，Parser 并不在源码上操作。在 Parser 之前，源码会通过 Lexer 分词成 Token （就是在语法中全部大写的那些），这里是我们从上面语法中提取出的 Token ：

LPAREN: '('
RPAREN: ')'
LAMBDA: 'λ' // 为了方便我们也可以使用 '\'
DOT: '.'
LCID: /[a-z][a-zA-Z]*/ // LCID 代表了小写字母的标识符
                     // 例如：任何以小写字母开头的字符串

我们会有一个 Token 类，包含一个 type 属性（上面中的一个），和一个可选的 value 属性（例如，LCID 中的字符串）：.

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

3. Lexer（词法分析器）

现在我们可以使用上面定义的 Token 来写一个 Lexer ，以此为 Parser 处理程序提供一个良好的 API 。

Lexer 中 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, 并且将其返回。

好了，让我们继续聊聊 Parser ！

4. Parser

Parser 基本上是语法的拷贝。我们基于产生式规则的名字（ ::= 左边的部分）给每个产生式规则创建了一个方法， ::= 右边则遵循以下规则：如果字母都是大写的，那么就是一个_终结符_（例如：一个 Token ），并且我们可以使用 Lexer 处理它；如果右边是一个（首字母）大写的单词，那么则是另一个产生式，因此我们可以给它调用方法。当我们看到一个 | （读作or）时，我们需要决定去使用哪边，具体取决于哪边匹配 Token 。

语法中只有一个棘手的部分，手写的 Parser 通常是递归下降（我们遇到过很多这样的情况），并且它们无法处理左递归。你可能注意到 Application 产生式的右边，在第一个位置包含了 Application 本身，所以我们只是遵循上一段提到的产生规则的话，当我们调用看到的所有产生式时将会导致无限递归。

幸运的是左递归可以用以下技巧去掉：

Application ::= Atom Application'

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

4.1. AST

在 Parser 之后，我们需要以某种方式存储信息，因此我们将创造一个 抽象语法树(AST)。λ演算的语法树非常简单，只需要三种节点：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' }
  }
}

4.2. Parser 实现

现在我们有了 AST 节点，我们可以用它们去构建实际的树。这里是语法中基于产品规则的 Parser 方法。

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

5. 求值

现在我们可以使用 AST 来求值了，但是为了知道解释器的具体细节，我们首先许需要关注一下λ演算的求值规则。

5.1. 求值规则

首先我们需要定义什么是 Term （这可以从语法中猜测出来）以及什么是值。

Term 就是:

t1 t2   # Application

λx. t1  # Abstraction

x       # Identifier

是的，这些跟 AST 中的节点很像，但是这些中的哪些是值？

值就是有着最终形态的 Term ，例如：它们不能再被求值了。这种情况下，唯一的 Term 同时也是值的是 Abstraction （除非它被调用，否则不会求值）。

实际的求值规则如下：

1)       t1 -> t1'
     _________________

      t1 t2 -> t1' t2

2)       t2 -> t2'
     ________________

      v1 t2 -> v1 t2'

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

这里是每条规则的介绍：

  1. 如果 t1 是一个求 t1' 值的 Term ，t1 t2 就是求 t1' t2 的值，例如：Application 的左边会先求值。
  2. 如果 t2 是一个求 t2' 值的 Term ，v1 t2 就是求 v1 t2' 的值，注意这里左边是 v1 而不是 t1 意味着它是一个值，不能再被求值了，例如：只有左边求值完之后才能给右边求值。
  3. Application (λx. t12) v2 的结果，和把 t12 中所有出现 x 的地方替换为 v2 的结果是等效的。注意在 Application 求值前两边都变成了值。

5.2. 解释器

解释器是遵循求值规则把程序分解成值的部分。现在我们需要做的是把上面的规则翻译成 JavaScript ：

首先，我们将定义简单的助手方法来告诉我们什么时候节点是一个值：

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

规则就是：如果是一个 Abstraction ，它就是一个值，否则就不是。

这里是解释器的一个片段 ：

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)
    • 另外，如果左边是值， 我们给 Application 的右边求值；(2)
    • 如果以上都没用到，那么我们给 Application 的左边求值；(1)
  • 现在，如果下一个节点是 Identifier ，我们可以简单地用值来替代。
  • 最后，如果没有规则适用 AST ，意味着它已经是一个值了，仅仅返回就行。

另一件值得注意的是 Context ， Context 包含了名称和值之间的绑定关系（ AST 节点），例如，当你调用一个方法时，你传入了方法所期望的变量，并且用方法的主体进行了求值。

克隆 Context 来确保一旦我们完成了右边的求值，限定的变量就会超出范围，因为我们仍然持有原始的 Context 。

如果我们不克隆 Context 的话，Application 的右边绑定就会泄漏，并且可以被左边获取，这本来是不应该的。考虑下面场景：

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

这很明显是一个非法的程序：在 Abstraction 最左边使用的 Identifier y 没有限制。但是让我们来看看如果我们不克隆 Context 的话求得的值是什么样的：

左边已经是值了，所以我们给右边求值。它是一个 Application ，所以会绑定 (λx .x) 到 y ，并且给 (λy. y) 求值，其实就是 y 本身，所以也等价于 (λx. x) 。

这样就完成了右边，把它变成了值，并且 y 现在超出了范围，因为我们退出了 (λy. y) ，但是我们在求值的时候没有克隆 Context，并且绑定泄漏了，同时 y 将有值 (λx. x) ，这最终导致了错误的程序结果。

6. 输出

现在我们基本做完了：我们已经可以把程序拆解为值，现在我们需要做的是用一种方式来表现值。

一种简单的方式是在每个 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 方法，这将以字符串形式递归输出所有孩子节点。

7. 整合

我们需要一个运行脚本把所有部分整合起来，代码应该像下面这样：

// 假设你有一些代码
const source = '(λx. λy. x) (λx. x) (λy. y)';

// 把所有片段放在一起
const lexer = new Lexer(source);
const parser = new Parser(lexer);
const ast = parser.parse();
const result = Interpreter.eval(ast);

// 字符串化结果节点并输出
console.log(result.toString());

源码

所有的实现都能在 Github 找到：github.com/tadeuzagallo/lc-js

结束语

非常感谢阅读，并且期待反馈:D





原文发布时间为：2016年07月12日


本文来自合作伙伴掘金，了解相关信息可以关注掘金网站。

时间： 2025-01-29 16:21:51

用 Javascript 编写λ演算解释器的相关文章

用JavaScript编写程序实现文本滚动

javascript|程序 在一些网页上,们经常看到一些滚动文本,很酷的,如何做呢? 下面我们就以徐志摩的一首<再别康桥>为例,用JavaScript编写一段程序,来实现文本的滚动. 1.运行Dreamweaver应用程序,单击工具栏中的"显示代码视图和设计视图"按钮, 在打开的代码窗口中,把下面这一段代码,插入到< head>区域中. < SCRIPT LANGUAGE="JavaScript"> < !-- Begin

javascript编写实用的省市选择器

 这篇文章主要介绍了javascript编写实用的省市选择器的方法及示例分享,非常不错,推荐给有相同需求的小伙伴们.     省市选择器是大家经常用到的, 但网上找的省市选择器都不是很实用,于是自己写了移动端的省市选择器. 界面: 源码结构:   演示地址:http://component.cform.cn/city/ 演示二维码: 源码地址:http://component.cform.cn/city/city.zip

在用JavaScript编写富文本，问一些细节问题。求思路。

问题描述 在用JavaScript编写富文本,问一些细节问题.求思路. 现在的富文本编辑器是怎么做到所见即所得的.我看了几个案例(比如CSDN这个文本编辑)都是直接写入到一个DIV中.那怎么以表单的方式提交呢? 我在前面的一个问题里解决了获取选中内容的问题.当换行时我希望在当前结点后追加一个P标签,但新输入的内容怎么能让它进入到新的p标签里? Like this: <div id="t" contenteditable="true"> <p>

javascript引擎-用javascript编写一个登陆的页面，求代码 ，急求！！

问题描述 用javascript编写一个登陆的页面,求代码 ,急求!! 像是这样的:function request(paras){//获取url参数 var url=location.href; var paraString=url.substring(url.indexOf("?")+1,url.length).split("&"); var paraObj={}; for (i=0; j=paraString[i]; i++)paraObj[j.sub

一个Javascript 编写的代码编辑器_网页编辑器

EditArea : http://sourceforge.net/projects/editarea 特点:1. 一个 Javascript 编写的代码编辑器, 支持代码加亮, 缩进, 行号等特征; 2. A free javascript editor for source code. It allow to write well formated source code with line numerotation, tab support, search & replace (with

原生JavaScript编写canvas版的连连看游戏_javascript技巧

本文实例为大家分享了JavaScript编写canvas版的连连看游戏的具体实现代码,供大家参考,具体内容如下 效果图: 实现代码: <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title></title> <style> #box{ /*border: 1px solid #D1D1D1; */ overflow: hidden; pos

基于javascript编写简单日历_javascript技巧

一.表格行数问题      既然要显示日期表格的话,首先得知道这个表格有多少行多少列,列数是已经确定的,从星期天(日历上第1列是星期天)到星期六一共7列.要解决行数问题之前,还得先知道这个月的第1天是星期几,因为每个月的1号并不都是从日历上的星期天开始排的,可能1号是星期五,星期六也说不定,所以1号的左边部分,就得用空表格代替了.那么用多少个空表格代替呢,这里就得用到getDay()方法了,该方法返回数组[0-6]中的一个数字,0代表星期天,1代表星期一,2代表星期二,以此类推.所以如果一个月的

Javascript编写Asp时需要注意的一些地方

  Javascript编写Asp时需要注意的一些地方 论坛里面有不少人在使用Javascript编写Asp,经常有人在论坛提问,为什么Asp对象在对比指定值时返回结果不对?现在在这里给大家写点关于使用Javascript编写Asp一些需要注意的地方. 最常见的问题:   Code: Response.Write(Request.Form("Key") == "")  返回的结果怎么都是"False".在这里,我们使用typeof就可以发现:Re

安全研究人员发现一种完全由JavaScript编写的勒索软件

安全研究人员发现了一种完全由JavaScript编写的新型勒索软件,使用CryptoJS库去加密受害者电脑上的文件.被称为RAA的勒索软件主要通过电子邮件附件的形式传播,打开附件后受害者只看到一个受损的文件,但其实勒索软件在背后做了很多活,其中包括删除Windows Volume Shadow Copy防止加密后恢复,以及开机启动,下载额外的恶意程序. 目前还没有办法解密文件,安全研究人员建议不要打开附件. 本文转自d1net(转载)