7行代码，3分钟：实现一种编程语言（2010）

# 7 行代码，3 分钟：实现一种编程语言 来源：https://matt.might.net/articles/implementing-a-programming-language/ 实现一种编程语言是每位程序员都不应错过的体验；这一过程能培养对计算的深刻理解，而且非常有趣！ 在本文中，我将整个过程提炼到了其本质：一个仅 7 行的函数式（图灵等价）编程语言解释器。实现它大约只需要 3 分钟。 这 7 行代码的解释器展示了在许多解释器中发现的可扩展架构——即《计算机程序的构造和解释》（Structure and Interpretation of Computer Programs, http://www.amazon.com/gp/product/0262510871/ref=as_li_ss_tl?ie=UTF8&tag=mmamzn06-20&linkCode=as2&camp=217145&creative=399369&creativeASIN=0262510871）中的 eval/apply 设计模式： [](http://www.amazon.com/gp/product/0262510871/ref=as_li_ss_il?ie=UTF8&tag=mmamzn06-20&linkCode=as2&camp=217145&creative=399369&creativeASIN=0262510871) 总共，本文包含三种语言实现： - 一个 7 行代码、3 分钟完成的 Scheme 解释器； - 一个用 Racket (http://racket-lang.org/) 重写的版本； - 一个 100 行代码、“一个下午”完成 的解释器，实现了顶层绑定形式、显式递归、副作用、高阶函数等更多功能！ 最后一个解释器是构建更丰富语言的良好起点。 ## 一种小型（但图灵等价）的语言 最容易实现的编程语言是一种极简主义的高阶函数式编程语言，称为 lambda 演算（lambda calculus）。 Lambda 演算实际上位于所有主要函数式语言的核心——Haskell、Scheme 和 ML——但它也存在于 JavaScript、Python 和 Ruby 内部。如果你知道去哪里找，甚至 Java 内部也藏着它。 ### 简要历史 Alonzo Church 于 1929 年开发了 lambda 演算。 当时，它并不被称为编程语言，因为那时还没有计算机；没有什么东西可以“编程”。 它其实只是一种用于推理函数的数学符号。 幸运的是，Alonzo Church 有一位名叫 Alan Turing 的博士生。 Alan Turing 定义了图灵机，这成为了通用计算机的第一个被接受的定义。 人们很快发现 lambda 演算和图灵机是等价的：任何你可以用 lambda 演算描述的功能都可以在图灵机上实现，任何你可以在图灵机上实现的功能都可以用 lambda 演算描述。 令人称奇的是，lambda 演算中只有三种表达式的类型：变量引用、匿名函数和函数调用。 ### 匿名函数 匿名函数使用“lambda-点”表示法书写，例如： `` (λ v . e) `` 这是一个接受参数 `v` 并返回 `e` 的值的函数。 如果你写过 JavaScript，这种形式等价于： `` function (v) { return e ; } `` ### 函数调用 函数调用通过将两个表达式相邻来书写： `` (f e) `` 在 JavaScript（或几乎任何其他语言）中，你会写成： `` f(e) `` ### 示例 恒等函数（identity function），它只是返回其参数，很容易写： `` (λ x . x) `` 我们可以将恒等函数应用到另一个恒等函数上： `` ((λ x . x) (λ a . a)) `` （当然，这只会返回恒等函数。） 下面是一个稍微更有趣的程序： `` (((λ f . (λ x . (f x))) (λ a . a)) (λ b . b)) `` 你能弄清楚它做了什么吗？ ### 等等！这怎么算是一种“编程”语言？ 乍一看，这种简单的语言似乎既缺乏递归和迭代，更不用说数字、布尔值、条件语句、数据结构以及所有其他东西了。这种语言怎么可能具备通用性呢？ Lambda 演算实现图灵等价的方式是通过两个最酷的编程技巧：Church 编码和 Y 组合子。 我写过一篇关于 Y 组合子的完整文章 (https://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/)，另一篇关于 Church 编码的文章 (https://matt.might.net/articles/church-encodings-demo-in-scheme/)。但是，如果你不想读那些，我可以只用一个程序来说服你，lambda 演算比你预期的要强大得多： `` ((λ f . (f f)) (λ f . (f f))) `` 这个表面看似无害的程序被称为 Omega，如果你尝试执行它，它将永远不会终止！（试着想想为什么。） ## 实现 lambda 演算 以下是 lambda 演算的 7 行代码、3 分钟解释器，使用 R5RS Scheme 编写。用技术术语来说（下文有解释），它是一个基于环境的指称解释器。 `` ; eval 接收一个表达式和一个环境，返回一个值 (define (eval e env) (cond ((symbol? e) (cadr (assq e env))) ((eq? (car e) 'λ) (cons e env)) (else (apply (eval (car e) env) (eval (cadr e) env))))) ; apply 接收一个函数和一个参数，返回一个值 (define (apply f x) (eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f)))) ; 从 stdin 读取并解析，然后求值： (display (eval (read) '())) (newline) `` 这段代码将从 stdin 读取程序，解析它，求值并打印结果。（不包括注释和空行，正好是 7 行。） Scheme 的 `read` 函数让词法分析和解析变得简单——只要你愿意生活在“平衡括号”（即 s-表达式 (http://en.wikipedia.org/wiki/S-expression)）的语法世界中。（如果不愿意，你就需要阅读关于词法分析和解析的资料；可以从 我关于词法分析的一篇文章 (https://matt.might.net/articles/nonblocking-lexing-toolkit-based-on-regex-derivatives/) 开始。）在 Scheme 中，`read` 从 stdin 获取正确括号的输入并将其解析为树。 两个函数构成了解释器的核心：`eval` 和 `apply`。尽管我们使用的是 Scheme，但我们可以给这些函数赋予概念上的“签名”： `` eval : Expression * Environment -> Value apply : Value * Value -> Value Environment = Variable -> Value Value = Closure Closure = Lambda * Environment `` `eval` 函数接收一个表达式和一个环境，返回一个值。表达式可以是变量、lambda 项或应用（application）。 环境是一个从变量到值的映射，用于定义开放项（open term）的自由变量。（开放项是指包含未绑定变量出现的项。）例如，考虑表达式 `(λ x . z)`。这个项是开放的，因为我们不知道 `z` 是什么。 由于我们使用的是 R5RS Scheme，我们可以使用关联列表来定义环境。 闭包（closure）是对函数的编码，它将一个（可能开放的）lambda 表达式与环境配对，以定义其自由变量。换句话说，闭包封闭了一个开放项。 ## Racket 中更整洁的实现 Racket (http://racket-lang.org/) 是一种功能齐全、注重实效的 Scheme 方言。Racket 提供了 `match` 构造，使解释器更加整洁。看看这个： `` #lang racket ; 引入 match 库： (require racket/match) ; eval 根据表达式类型进行模式匹配： (define (eval exp env) (match exp [`(,f ,e) (apply (eval f env) (eval e env))] [`(λ ,v . ,e) `(closure ,exp ,env)] [(? symbol?) (cadr (assq exp env))])) ; apply 也使用 match 解构函数： (define (apply f x) (match f [`(closure (λ ,v . ,body) ,env) (eval body (cons `(,v ,x) env))])) ; 读取、解析并求值： (display (eval (read) '())) (newline) `` 这个版本代码稍长，但更整洁且易于理解。 ## 一种更大的语言 Lambda 演算是一种非常小的语言。即便如此，其解释器的 eval/apply 设计模式也能扩展到更大的语言。例如，用大约 100 行代码，我们可以实现一个涵盖 Scheme 本身相当大子集的解释器。 考虑一种包含以下多种表达式形式的语言： 1. 变量引用；例如：`x`、`foo`、`save-file`。 2. 数值和布尔常量；例如：`300`、`3.14`、`#f`。 3. 基本操作；例如：`+`、`-`、`<=`。 4. 条件语句：`(if condition if-true if-false)`。 5. 变量绑定：`(let ((var value) ...) body-expr)`。 6. 递归绑定：`(letrec ((var value) ...) body-expr)`。 7. 变量变异：`(set! var value)`。 8. 顺序执行：`(begin do-this then-this)`。 现在为该语言添加三种顶层形式： 1. 函数定义：`(define (proc-name var ...) expr)`。 2. 全局定义：`(define var expr)`。 3. 顶层表达式：`expr`。 以下是整个解释器，包括测试支架和测试用例： `` #lang racket (require racket/match) ;; 求值在 eval 和 apply 之间切换。 ; eval 根据表达式类型进行分发： (define (eval exp env) (match exp [(? symbol?) (env-lookup env exp)] [(? number?) exp] [(? boolean?) exp] [`(if ,ec ,et ,ef) (if (eval ec env) (eval et env) (eval ef env))] [`(letrec ,binds ,eb) (eval-letrec binds eb env)] [`(let ,binds ,eb) (eval-let binds eb env)] [`(lambda ,vs ,e) `(closure ,exp ,env)] [`(set! ,v ,e) (env-set! env v e)] [`(begin ,e1 ,e2) (begin (eval e1 env) (eval e2 env))] [`(,f . ,args) (apply-proc (eval f env) (map (eval-with env) args))])) ; 用于柯里化 eval 的便捷包装器： (define (eval-with env) (lambda (exp) (eval exp env))) ; letrec 的 eval： (define (eval-letrec bindings body env) (let* ((vars (map car bindings)) (exps (map cadr bindings)) (fs (map (lambda _ #f) bindings)) (env* (env-extend* env vars fs)) (vals (map (eval-with env*) exps))) (env-set!* env* vars vals) (eval body env*))) ; let 的 eval： (define (eval-let bindings body env) (let* ((vars (map car bindings)) (exps (map cadr bindings)) (vals (map (eval-with env) exps)) (env* (env-extend* env vars vals))) (eval body env*))) ; 将过程应用于参数： (define (apply-proc f values) (match f [`(closure (lambda ,vs ,body) ,env) ; => (eval body (env-extend* env vs values))] [`(primitive ,p) ; => (apply p values)])) ;; 环境将变量映射到包含值的可变单元格。 (define-struct cell ([value #:mutable])) ; 空环境： (define (env-empty) (hash)) ; 初始环境，包含基本操作的绑定： (define (env-initial) (env-extend* (env-empty) '(+ - / * <= void display newline) (map (lambda (s) (list 'primitive s)) `(,+ ,- ,/ ,* ,<= ,void ,display ,newline)))) ; 查找一个值： (define (env-lookup env var) (cell-value (hash-ref env var))) ; 在环境中设置一个值： (define (env-set! env var value) (set-cell-value! (hash-ref env var) value)) ; 用多个绑定扩展环境： (define (env-extend* env vars values) (match `(,vars ,values) [`((,v . ,vars) (,val . ,values)) ; => (env-extend* (hash-set env v (make-cell val)) vars values)] [`(() ()) ; => env])) ; 用多个赋值变异环境： (define (env-set!* env vars values) (match `(,vars ,values) [`((,v . ,vars) (,val . ,values)) ; => (begin (env-set! env v val) (env-set!* env vars values))] [`(() ()) ; => (void)])) ;; 求值测试。 ; 定义新语法以使测试看起来更美观： (define-syntax test-eval (syntax-rules (====) [(_ program ==== value) (let ((result (eval (quote program) (env-initial)))) (when (not (equal? program value)) (error "test failed!")))])) (test-eval ((lambda (x) (+ 3 4)) 20) ==== 7) (test-eval (letrec ((f (lambda (n) (if (<= n 1) 1 (* n (f (- n 1))))))) (f 5)) ==== 120) (test-eval (let ((x 100)) (begin (set! x 20) x)) ==== 20) (test-eval (let ((x 1000)) (begin (let ((x 10)) 20) x)) ==== 1000) ;; 程序被转换为单个 letrec 表达式。 (define (define->binding define) (match define [`(define (,f . ,formals) ,body) ; => `(,f (lambda ,formals ,body))] [`(define ,v ,value) ; => `(,v ,value)] [else ; => `(,(gensym) ,define)])) (define (transform-top-level defines) `(letrec ,(map define->binding defines) (void))) (define (eval-program program) (eval (transform-top-level program) (env-initial))) (define (read-all) (let ((next (read))) (if (eof-object? next) '() (cons next (read-all))))) ; 读取程序并求值： (eval-program (read-all)) `` 你可以下载源代码：minilang.rkt (https://matt.might.net/articles/implementing-a-programming-language/minilang.rkt)。 ## 下一步 你应该能够通过修改最后一个解释器快速测试关于编程语言的新想法。 如果你想要一种具有不同语法的语言，你可以构建一个解析器来输出 s-表达式。采用这种方法可以清晰地分离语法设计和语义设计。 ## 更多资源 ## 相关文章 ---