红帽白皮书新鲜出炉!点击获取,让你的云战略更胜一筹! 了解详情
写点什么

7 行代码 3 分钟:从零开始实现一门编程语言

  • 2022-06-17
  • 本文字数:4971 字

    阅读完需:约 16 分钟

7行代码3分钟:从零开始实现一门编程语言

本文最初发布于 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)
复制代码


该函数接受参数v ,返回值e 。如果用 JavaScript 编写,上述代码等价于:



function (v) { return e ; }
复制代码

函数调用

函数调用的写法是使两个表达式相邻:



(f e)
复制代码


JavaScript(或其他任何语言)的写法如下:



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 子集实现一个解释器。


考虑一种具有各种表达形式的语言:


  1. 变量引用,如:xfoosave-file

  2. 数值和布尔常量,如:3003.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)。现在,为这门语言添加 3 个顶层形式:

  9. 函数定义:(define (proc-name var ...) expr)

  10. 全局定义:(define var expr)

  11. 顶层表达式: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))
复制代码


下载源代码,请点击minilang.rkt

结语

通过修改最后一个解释器,你应该可以快速测试关于编程语言的新想法。


如果你希望有一种语法不一样的语言,就可以构建一个解析器,把 s-表达式转储。这样,你就可以干净利落地将语法设计与语义设计分开。


查看英文原文:


https://matt.might.net/articles/implementing-a-programming-language?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NTU0NTMzMzAsImZpbGVHVUlEIjoibG9xZVcyRXl2d0hkSkxBbiIsImlhdCI6MTY1NTQ1MzAzMCwidXNlcklkIjoyMDQxOTA5MH0.Nv5UyUdCUJNT7c0kIaPSE0g0f4k9Ed26rLl2Bu5RpG4

2022-06-17 16:402509
用户头像
刘燕 InfoQ高级技术编辑

发布了 1112 篇内容, 共 489.1 次阅读, 收获喜欢 1965 次。

关注

评论

发布
暂无评论
发现更多内容

Android系统有哪些优缺点

InfoQ IT百科

终于有人讲明白了!原来这才是全球低时延一张网技术

华为云开发者联盟

音视频 华为云 实时音视频 低时延

移动平台WorkPlus集成化办公,打造企业全场景业务生态

WorkPlus

目前5G SoC 芯片技术成熟吗?

InfoQ IT百科

iOS开发面试攻略(KVO、KVC、多线程、锁、runloop、计时器)

iOSer

ios iOS面试 ios开发 iOS面试题

手机处理器未来的发展趋势如何

InfoQ IT百科

为什么手机操作系统开始向多端融合方向发展

InfoQ IT百科

LAXCUS分布式操作系统冗余容错之节点篇

LAXCUS分布式操作系统

分布式系统 冗余 集群容灾

手机里的NPU可以起到什么作用

InfoQ IT百科

未来的手机操作系统在智能化上会有哪些突破

InfoQ IT百科

Oceanbase 和 TiDB 粗浅对比之 - 执行计划

TiDB 社区干货传送门

4.25解锁OpenHarmony技术日!年度盛会,即将揭幕!

Anna

未来手机操作系统有哪些发展趋势

InfoQ IT百科

手机拍照算法和硬件哪个更重要

InfoQ IT百科

如何在面试中机智的展现架构能力?

非凸科技

rust 编程语言 量化 构架师 互联网大厂

不同研发协作模式在云效中的应用

阿里云云效

云计算 阿里云 云原生 研发 研发协作

你必须懂也可以懂的微服务系列三:服务调用

爱好编程进阶

Java 面试 后端开发

手机硬件性能的发展主要受哪几方面制约

InfoQ IT百科

netty系列之:netty中常用的字符串编码解码器

程序那些事

Java Netty 程序那些事 4月月更

18张图,详解SpringBoot解析yml全流程

码农参上

springboot 配置文件 4月月更

如何优化前端页面的LCP?

BUG侦探

前端 性能 网页指标

为什么switch里的case没有break不行

爱好编程进阶

Java 面试 后端开发

手机软硬件协同很重要吗?

InfoQ IT百科

为拿几家大厂Offer,“闭关修炼

爱好编程进阶

Java 面试 后端开发

苹果A13处理器在技术上有哪些创新?

InfoQ IT百科

诚邀报名丨首期OpenHarmony开发者成长计划分享日

OpenHarmony开发者

OpenHarmony

洞见科技首批通过央行国家金融科技测评中心「联邦学习」产品评测,实现「MPC+FL」金融应用双认证

洞见科技

联邦学习 隐私计算 多方安全计算

外包学生管理系统详细架构设计文档

danny_xian

开发手机操作系统的难度有多大

InfoQ IT百科

手机硬件都有哪些

InfoQ IT百科

【高并发】为何在32位多核CPU上执行long型变量的写操作会出现诡异的Bug问题?看完这篇我懂了!

冰河

并发编程 多线程 协程 异步编程 精通高并发系列

7行代码3分钟:从零开始实现一门编程语言_语言 & 开发_Matt Might_InfoQ精选文章