欢迎大家来到IT世界,在知识的湖畔探索吧!
本文最初发布于 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)
欢迎大家来到IT世界,在知识的湖畔探索吧!
复制代码
该函数接受参数v ,返回值e 。如果用 JavaScript 编写,上述代码等价于:
欢迎大家来到IT世界,在知识的湖畔探索吧!
function (v) { return e ; }
复制代码
函数调用
函数调用的写法是使两个表达式相邻:
(f e)
复制代码
JavaScript(或其他任何语言)的写法如下:
欢迎大家来到IT世界,在知识的湖畔探索吧!
f(e)
复制代码
示例
将参数原样返回的恒等函数写法如下:
(λ x . x)
复制代码
我们可以将恒等函数应用于恒等函数:
((λ x . x) (λ a . a))
复制代码
(返回当然也是恒等函数。)下面这个程序更有意思一些:
(((λ f . (λ x . (f x))) (λ a . a)) (λ b . b))
复制代码
你能搞懂它做了什么吗?
这到底是怎样的一种“编程”语言?
乍一看,这门简单的语言似乎缺少递归和迭代,更不用说数值、布尔、条件、数据结构等其他东西。这种语言怎么可能是通用的呢?
λ演算达到图灵等价是通过两个最酷的编程黑科技实现的:Church 编码和 Y 组合子。
关于 Y 组合子,我已经写过一篇文章,关于Church编码,也写过一篇。不过,你不想读这些文章也没事,我只需一个程序就可以说服你,λ演算的功能远超你的预期:
((λ f . (f f)) (λ f . (f f)))
复制代码
这个看上去无害的程序名为 Omega,如果你试图执行它,就发现它不会终止!(看看你能不能找出原因)。
实现λ演算
下面是用 R5RS Scheme 耗时 3 分钟实现的一个 7 行λ演算解释器。从技术上讲(下文有解释),它是一个基于环境的指示型解释器。
; 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 中,但我们可以给予这些函数概念上的“签名”:
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 的实现更简洁
Racket是 Scheme 的一种方言,它功能齐备,可以把事情做好。Racket 提供了一个可以清理解释器的匹配结构,如下所示:
#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。下面是完整的解释器,其中包括测试工具和测试用例:
#语言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)
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
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/32919.html