QCon 演讲火热征集中,快来分享技术实践与洞见!222222 了解详情
写点什么

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:404406
用户头像
刘燕 InfoQ高级技术编辑

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

关注

评论

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

AI都会写脚本了,传统的运维工程师会失业吗? | 社区征文

wljslmz

AI 运维工程师 三周年征文

[杂谈]大型JSON数据切分(Java Jackson)

alexgaoyh

json elasticsearch Jackson 分割

Flink中的时间及窗口类型

阿泽🧸

flink 三周年连更

腾讯云和ScaleFlux联合推出可计算存储与大容量QLC NAND解决方案

ScaleFlux

腾讯云 数据中心 降本增效 企业级SSD SSD寿命

云原生应用交付流程安全规范

穿过生命散发芬芳

安全规范 三周年连更

通过自定义域名 + SSL 的方式访问 Amazon MQ for RabbitMQ

亚马逊云科技 (Amazon Web Services)

盘古云课堂加入 PolarDB 开源数据库社区

阿里云数据库开源

polarDB PolarDB-X PolarDB-PG PolarDB for PostgreSQL 阿里云瑶池数据库

类似Redmine,但更好的7款项目管理工具

爱吃小舅的鱼

项目管理 项目管理软件 Redmine

从IDC数据库安全报告,看OceanBase安全能力

OceanBase 数据库

数据库 oceanbase

来了!昇腾MindStudio全流程工具链分论坛精彩回顾,助力高效开发和迁移效率提升

Geek_2d6073

2023 开源之夏|和 Milvus & Towhee 一起玩转 AI、享开源、得奖金

Zilliz

Milvus Zilliz 向量数据库 Towhee 开源之下

中国网约车领域月度观察2023年04月

易观分析

网约车 出行服务

在SDN技术盛行的时代,网络工程师需要不断学习新技术跟上时代的步伐 | 社区征文

wljslmz

sdn 三周年征文

总有AI想害'朕' 失业,我们该何去何从| 社区征文

穿过生命散发芬芳

ChatGPT 三周年征文

C++模板和泛型编程详解

小万哥

c++ 程序员 面试 后端 开发

大数据如何助力营销(1)市场调研

MobTech袤博科技

2023-05-10:给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表 如果在二叉树中,存在一条一直向下的路径 且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,

福大大架构师每日一题

Go 算法 rust 福大大

用LeangooScrum敏捷工具做缺陷管理和迭代规划和迭代执行

顿顿顿

Scrum 敏捷开发 敏捷项目管理 敏捷工具 scrum敏捷工具

HTTPS 的加密过程及其工作原理

wljslmz

https 三周年连更

挑战与机遇,全面预算管理的执行计划

智达方通

Redis Operator在中原银行实践落地及能力创新

中原银行

redis 云原生 operator redis operator

软件测试丨Pytest-运行用例、常用参数、执行pytest、异常处理

测试人

软件测试 自动化测试 测试开发 pytest

可计算存储是否真的与众不同?

ScaleFlux

压缩数据 计算与存储 固态硬盘

理解并实现自动导入(Auto Import)功能的原理

Lee Chen

JavaScript

体验MMGPT本地部署(上)

IT蜗壳-Tango

三周年连更

麻了,一个操作把MySQL主从复制整崩了

JAVA旭阳

Java MySQL

澳鹏与 Reka AI 强强联合,构建高质量的多模态 LLM 应用

澳鹏Appen

人工智能 数据标注 生成式AI

AntDB数据库体验室上线啦!一站式培训+实操,带您感受“电信级”国产数据库的魅力

亚信AntDB数据库

AntDB AntDB数据库 企业号 5 月 PK 榜

浅谈如何做好知乎内容营销:需要注意哪些细节

石头IT视角

专访惠众科技|元宇宙应用如何借助3DCAT实时云渲染实现流畅大并发呈现?

3DCAT实时渲染

元宇宙 实时渲染云

Python自动化办公神器!1行代码实现文件转PDF,支持Word、Excel、PPT、TXT格式

程序员晚枫

Python PDF

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