本文由 简悦 SimpRead 转码， 原文地址 www.toutiao.com
实际上，λ演算是所有主要的函数式语言的核心——Haskell、Scheme 和 ML——但它也存在于 JavaScript、Python 和 R
本文最初发布于 Matt Might 的个人博客。
本文介绍了多种解释器实现。通过修改最后一个解释器，你应该可以快速测试关于编程语言的新想法。如果你希望有一种语法不一样的语言，就可以构建一个解析器，把 s - 表达式转储。这样，你就可以干净利落地将语法设计与语义设计分开。
实现一门编程语言是任何程序员都不应该错过的经验；这个过程可以培养你对计算的深刻理解，而且很有趣。
本文直击本质，把整个过程归结为：一个面向函数式（但图灵等价）编程语言的 7 行解释器，而其实现只需要大约 3 分钟。
这个 7 行的解释器展示了许多解释器中都存在的可扩展架构——《计算机程序的结构与解释》中的 eval/apply 设计模式：
本文中总共有三种语言的实现：
- 一个使用 Scheme 耗时 3 分钟实现的 7 行解释器；
- 使用 Racket 重新实现；
- 一个耗时 “一下午” 实现的 100 行解释器，实现了顶层绑定形式、显式递归、副作用、高阶函数等功能。如果想要实现一门功能更丰富的语言，那么最后一个解释器是一个不错的起点。
最容易实现的编程语言是一种极简的高阶函数式编程语言，名为λ演算（lambda calculus）。
实际上，λ演算是所有主要的函数式语言的核心——Haskell、Scheme 和 ML——但它也存在于 JavaScript、Python 和 Ruby 中。它甚至隐藏在 Java 中，不知道你是否知道在哪里可以找到它。
阿隆佐 · 丘奇在 1929 年开发了λ演算。
那时，它还不叫编程语言，因为当时没有计算机；没有什么东西可以 “编程”。
它实际上只是一个用于函数推理的数学符号。幸运的是，阿隆佐 · 丘奇有一个博士生叫艾伦 · 图灵。
艾伦 · 图灵定义了图灵机，这成为通用计算机第一个公认的定义。
人们很快发现，λ演算和图灵机是等价的：任何能用λ演算描述的函数都能在图灵机上实现，而任何能在图灵机上实现的函数都能用λ演算描述。
值得注意的是，λ演算中只有三种表达式：变量引用、匿名函数和函数调用。
匿名函数的编写采用 “lambda-dot” 标记法，如下所示：
复制代码
该函数接受参数 v ，返回值 e 。如果用 JavaScript 编写，上述代码等价于：
1
|
function (v) { return e ; }
|
复制代码
函数调用的写法是使两个表达式相邻：
复制代码
JavaScript（或其他任何语言）的写法如下：
复制代码
将参数原样返回的恒等函数写法如下：
复制代码
我们可以将恒等函数应用于恒等函数：
复制代码
（返回当然也是恒等函数。）下面这个程序更有意思一些：
1
|
(((λ f . (λ x . (f x))) (λ a . a)) (λ b . b))
|
复制代码
你能搞懂它做了什么吗？
乍一看，这门简单的语言似乎缺少递归和迭代，更不用说数值、布尔、条件、数据结构等其他东西。这种语言怎么可能是通用的呢？
λ演算达到图灵等价是通过两个最酷的编程黑科技实现的：Church 编码和 Y 组合子。
关于 Y 组合子，我已经写过一篇文章，关于 Church 编码，也写过一篇。不过，你不想读这些文章也没事，我只需一个程序就可以说服你，λ演算的功能远超你的预期：
1
|
((λ f . (f f)) (λ f . (f f)))
|
复制代码
这个看上去无害的程序名为 Omega，如果你试图执行它，就发现它不会终止！（看看你能不能找出原因）。
下面是用 R5RS Scheme 耗时 3 分钟实现的一个 7 行λ演算解释器。从技术上讲（下文有解释），它是一个基于环境的指示型解释器。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
; 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 - 表达式）的语法世界中。(如果不愿意，你就必须仔细研究解析中的词法分析；可以从我的一篇关于词法分析的文章入手）。在 Scheme 中，read 从 stdin 中获取括号括起来的输入，并将其解析为一棵树。
eval 和 apply 两个函数构成了解释器的核心。尽管是在 Scheme 中，但我们可以给予这些函数概念上的 “签名”：
1
2
3
4
5
6
7
|
eval : Expression * Environment -> Value
apply : Value * Value -> Value
Environment = Variable -> Value
Value = Closure
Closure = Lambda * Environment
|
复制代码
eval 函数接收一个表达式和一个环境然后转换为一个值。表达式可以是一个变量，一个 lambda 项或一个应用程序。环境是一个从变量到值的映射，用来定义一个开项的自由变量。（开项是一个变量的非绑定出现。）例如，考虑一下表达式（λ x . z）。这个项是开放的，因为我们不知道 z 是什么。
由于用的是 R5RS Scheme，我们可以使用关联列表来定义环境。
闭包是一个函数的编码，它将一个（可能是开放的）lambda 表达式与一个环境配对，以定义其自由变量。换句话说，一个闭包封闭了一个开项。
Racket 是 Scheme 的一种方言，它功能齐备，可以把事情做好。Racket 提供了一个可以清理解释器的匹配结构，如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#racket语言
; 引入匹配库：
(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用一个匹配来析构函数：
(define (apply f x) (match f
[`(closure (λ ,v . ,body) ,env)
(eval body (cons `(,v ,x) env))]))
; 读入、解析、求值：
(display (eval (read) '())) (newline)
|
复制代码
这个代码多点，但更简洁，更容易理解。
λ演算是一门很小的语言。即便如此，其解释器的 eval/apply 设计也可以扩展到更大的语言。例如，用大约 100 行代码，我们可以为一个相当大的 Scheme 子集实现一个解释器。
考虑一种具有各种表达形式的语言：
- 变量引用，如：x、foo、save-file。
- 数值和布尔常量，如：300、3.14、#f。
- 基本操作，如：+、-、<=。
- 条件：(if condition if-true if-false)。
- 变量绑定：(let ((var value) …) body-expr)。
- 递归绑定：(letrec ((var value) …) body-expr)。
- 变量可变：(set! var value)。
- 定序：(begin do-this then-this)。现在，为这门语言添加 3 个顶层形式：
- 函数定义：(define (proc-name var …) expr)。
- 全局定义：(define var expr)。
- 顶层表达式：expr。下面是完整的解释器，其中包括测试工具和测试用例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
#语言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))]))
; 一个方便的Currying eval的封装器：
(define (eval-with env)
(lambda (exp) (eval exp env)))
; eval for letrec:
(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*)))
; eval for let:
(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)
(* 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))
|
复制代码
下载源代码，请点击
https://matt.might.net/articles/implementing-a-programming-language/minilang.rkt?accessToken=
eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NTU0NTMzMzAsImZpbGVHVUlEIjoibG9xZVcyRXl2d0hkSkxBbiIsImlhdCI6MTY1NTQ1MzAzMCwidXNlcklkIjoyMDQxOTA5MH0.Nv5UyUdCUJNT7c0kIaPSE0g0f4k9Ed26rLl2Bu5RpG4
通过修改最后一个解释器，你应该可以快速测试关于编程语言的新想法。
如果你希望有一种语法不一样的语言，就可以构建一个解析器，把 s - 表达式转储。这样，你就可以干净利落地将语法设计与语义设计分开。
查看英文原文：
https://matt.might.net/articles/implementing-a-programming-language?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NTU0NTMzMzAsImZpbGVHVUlEIjoibG9xZVcyRXl2d0hkSkxBbiIsImlhdCI6MTY1NTQ1MzAzMCwidXNlcklkIjoyMDQxOTA5MH0.Nv5UyUdCUJNT7c0kIaPSE0g0f4k9Ed26rLl2Bu5RpG4