来源：伯乐头条 作者：Calarence 翻译，黄利民 校稿
实现一门编程语言对任何程序员来说都是值得拥有的经验，因为它能加深你对计算原理的理解，并且还很有趣。
在这篇文章中，我已经让整个过程回归到它的本质：为一种函数式（图灵等价）编程语言设计7行代码的解释器。大概只需要3分钟就能实现
这个7行代码的解释器展示了在众多解释器中同时存在的一个可升级的体系结构–eval/apply设计模式。《Structure and Interpretation of Computer Programs》这本书提到过该模式。
在这篇文章中总计有三门语言的实现：
-
一个是scheme语言的7行，3分钟实现的解释器
-
一个是Racket语言的重实现
-
最后一个是100行、“1-afternoon”解释器，它实现了高级绑定形式、显示递归、额外作用、高阶函数式等等
对于掌握一门更丰富的语言来说，最后一个解释器是一个好起点
一个小型(图灵机等价)语言
最容易实现的一门编程语言是一个叫做λ运算的极简单、高阶函数式编程语言
λ运算实际上存在于所有主要的功能性语言的内核中：Haskell, Scheme、 ML，但是它也存在于JavaScript、Python、Ruby中。它甚至隐藏在Java中，如果你知道到哪里去找它。
历史简介
1929年Alonzo Church开发出λ演算
在那时，lambda calculus不被叫做编程语言因为没有计算机，所以没有编程的概念。
它仅仅是一个推演函数的数学标记。
幸运的是，Alonzo Church有一个叫作艾伦·图灵的哲学博士。
艾伦·图灵定义了图灵机，图灵机成了第一个被接受的通用计算机定义
不久后发现lambda calculus和图灵机是等价的：任何用λ演算描述的功能可以在图灵机上实现；并且在图灵机上实现的任何功能可以用λ演算描述
值得注意的是在lambda calculus中仅有三种表达式：变量引用，匿名函数、函数调用
匿名函数：
|
1
|
(λv.e) |
匿名函数以”λ-.”标记开始，所以 (λ v . e)函数用来接收一个参数v并返回值e。
|
1
|
如果你用JavaScript编程，格式function (v) { return e ; }是相同的。 |
函数调用：
|
1
|
(fe) |
函数调用用两个临近的表达式表示：(f e)
|
1
2
3
|
f(e)在JavaScript中（或者其他任何语言），写为f(e) |
Examples
|
1
2
3
4
|
(λ x . x)例如： 恒等函数（identity function），仅仅返回它的参数值，简单地写为(λ x . x) |
|
1
|
((λ x . x) (λ a . a)) |
我们可以将这个恒等函数应用到一个恒等函数上：
((λ x . x) (λ a . a))（仅返回这个恒等函数本身）
|
1
|
(((λ f . (λ x . (f x))) (λ a . a)) (λ b . b)) |
这儿有一个更有趣的程序：
|
1
|
(((λ f . (λ x . (f x))) (λ a . a)) (λ b . b)) |
你能弄清楚它是干嘛的？
等一下！见鬼，这怎么算一门编程语言？
乍一看，这门简单语言好像缺乏递归和迭代，更不用说数字、布尔值、条件语句、数据结构和剩余其他的。这样的语言怎么可能成为通用的呢？
λ演算实现图灵机-等价的方式是通过两种最酷的方式：
邱奇编码（Church encoding）和Y combinator（美国著名企业孵化器）
|
1
|
((λ f . (f f)) (λ f . (f f))) |
我已经写了两篇关于Y combinator和邱奇编码的文章。
但是，你如果不想读它们的话，我可以明确的告诉你比起你期望的仅一个((λ f . (f f)) (λ f . (f f)))程序来说 有更多的 lambda calculus知识。
表面上开始的程序叫做Ω，如果你尝试运行它的话，它不会终止（想一下你是否明白其中原因）
实现λ演算
下面是基于Scheme语言标准(R5RS)的7行、3分钟λ演算解释器。在术语中，它是一个依赖环境的指示解释器
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
; eval takes an expression and an environment to a value(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 takes a function and an argument to a value(define (apply f x) (eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f)))); read and parse stdin, then evaluate:(display (eval (read) '())) (newline)This code will read a program from stdin, parse it, evaluate it and print the result. (It's 7 lines without the comments and blank lines.) |
代码将从文件中读入程序、分析、求值最后打印值(这是一段没有注释和空白行的7行代码)
Schema语言的read函数使得词法分析和语法分析简单化。只要你想处于语法“平衡圆括号”(符号式)世界里。
(如果不想的话，你必须钻研语法分析，你可以从我写的一篇语法分析文章开始)在Scheme语言中，read函数从文件获取加括号的输入并把它分析然后生成树函数eval 和 apply构成了解释器的内核。即使我们使用的是Scheme语言，我们仍给出了函数概念上的“签名”
|
1
2
3
4
5
6
|
eval : Expression * Environment -> Value apply : Value * Value -> Value Environment = Variable -> Value Value = Closure Closure = Lambda * Environment |
eval函数将一个表达式和环境变量赋给一个值。表达式可以是一个变量、λ术语或者是一个应用。
一个环境值是从变量到值的映射，用来定义一个开项的自由变量(开项用来存放出现的没有绑定的变量)。想一下这个例子，表达式(λ x . z)是开项，因为我们不知道z是什么。
因为我们使用Scheme语言标准(R5RS)，所以用联合列表来定义环境值
闭项是一个函数的编码，这个函数使用定义自由变量的环境值来匹配lambda 表达式来。换句话说来说，闭项关闭了一个开项
Racket中有一种更简洁的实现
Racket是Scheme的一种方言，功能齐备强大。它提供了一个整顿解释器的匹配构造机制。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#lang racket; bring in the match library:(require racket/match); eval matches on the type of expression:(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 destructures the function with a match too:(define (apply f x) (match f [`(closure (λ ,v . ,body) ,env) (eval body (cons `(,v ,x) env))])); read in, parse and evaluate:(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).
现在在语言中添加三种高级形式：
-
函数定义：(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
|
#lang racket(require racket/match);; Evaluation toggles between eval and apply.; eval dispatches on the type of expression:(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))])); a handy wrapper for 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*))); applies a procedure to arguments:(define (apply-proc f values) (match f [`(closure (lambda ,vs ,body) ,env) ; => (eval body (env-extend* env vs values))] [`(primitive ,p) ; => (apply p values)]));; Environments map variables to mutable cells;; containing values.(define-struct cell ([value #:mutable])); empty environment:(define (env-empty) (hash)); initial environment, with bindings for primitives:(define (env-initial) (env-extend* (env-empty) '(+ - / * <= void display newline) (map (lambda (s) (list 'primitive s)) `(,+ ,- ,/ ,* ,<= ,void ,display ,newline)))); looks up a value:(define (env-lookup env var) (cell-value (hash-ref env var))); sets a value in an environment:(define (env-set! env var value) (set-cell-value! (hash-ref env var) value)); extends an environment with several bindings:(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])); mutates an environment with several assignments:(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)]));; Evaluation tests.; define new syntax to make tests look prettier:(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);; Programs are translated into a single letrec expression.(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))))); read in a program, and evaluate:(eval-program (read-all)) |
你可以从这里下载源代码：minilang.rkt.
在这里
你应该尽可能快的通过修改最新的解释器为编程语言彻底检验新的想法
如果你想使用含有不同语法的语言，你可以建立一个解析器，将符号式转存出来。
使用这种方法，可以容易把句法设计与语义设计分离出来。
PPV课其他精彩文章：
1、回复“干货”查看干货 数据分析师完整知识结构
2、回复“答案”查看大数据Hadoop面试笔试题及答案
3、回复“设计”查看这是我见过最逆天的设计，令人惊叹叫绝
4、回复“可视化”查看数据可视化专题-数据可视化案例与工具
5、回复“禅师”查看当禅师遇到一位理科生，后来禅师疯了！！知识无极限
6、回复“啤酒”查看数据挖掘关联注明案例-啤酒喝尿布
7、回复“栋察”查看大数据栋察——大数据时代的历史机遇连载
8、回复“数据咖”查看数据咖——PPV课数据爱好者俱乐部省分会会长招募
9、回复“每日一课”查看【每日一课】手机在线视频集锦
原文始发于微信公众号（PPV课数据科学社区）：【学习】7行代码，3分钟：从无到有实现一门编程语言
原创文章，作者：ppvke，如若转载，请注明出处：http://www.ppvke.com/archives/24261
