7 行代码，3 分钟：实现一种编程语言 (2010)

7 行代码，3 分钟：从头开始实现一种编程语言 [ 文章索引 ] [ ] [ @mattmight ] [ rss ] 实现一种编程语言是任何程序员都不应缺少的经验；这个过程培养了对计算的深刻理解，而且很有趣！在本文中，我将整个过程归结为其本质：函数式（图灵等效）编程语言的 7 行解释器。实施大约需要3分钟。这个 7 行解释器展示了许多解释器中都存在的可扩展架构——《计算机程序结构与解释》的 eval/apply 设计模式：本文总共提供了三种语言实现：Scheme 中的 7 行 3 分钟解释器；在 Racket 中重新实现；以及一个 100 行的“1-afternoon”解释器，它实现了顶级绑定形式、显式递归、副作用、高阶函数等等！最后一个解释器是发展更丰富的语言的良好起点。一种小型（但图灵等效）语言最容易实现的编程语言是一种极简的高阶函数式编程语言，称为 lambda 演算。 lambda 演算实际上是所有主要函数式语言（Haskell、Scheme 和 ML）的核心，但它也存在于 JavaScript、Python 和 Ruby 中。如果您知道在哪里可以找到它，它甚至隐藏在 Java 内部。简史 Alonzo Church 于 1929 年开发了 lambda 演算。当时，它还没有被称为编程语言，因为还没有计算机；现在它被称为编程语言。没有任何东西可以“编程”。它实际上只是一种用于推理函数的数学符号。幸运的是，阿朗佐·丘奇拥有博士学位。学生名叫艾伦·图灵。艾伦·图灵定义了图灵机，成为第一个被接受的通用计算机定义。很快人们发现 lambda 演算和图灵机是等价的：任何可以用 lambda 演算描述的函数都可以在图灵机上实现，而任何可以在图灵机上实现的函数都可以在 lambda 演算中描述。值得注意的是，lambda 演算中只有三种表达式：变量引用、匿名函数和函数调用。匿名函数 匿名函数用“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)) 你能弄清楚它的作用吗？等待！这到底是一种“编程”语言吗？乍一看，这种简单的语言似乎缺乏递归和迭代，更不用说数字、布尔值、条件语句、数据结构等等。这种语言怎么可能是通用的？ lambda 演算实现图灵等价的方式是通过两种最酷的编程技巧：Church 编码和 Y 组合器。我写了一篇关于 Y 组合器的整篇文章和另一篇关于 Church 编码的文章。但是，如果您不想阅读这些内容，我可以让您相信 lambda 演算的内容超出了您对一个程序的预期： ((λ f . (f f)) (λ f . (f f))) 这个表面上良性的程序称为 Omega，如果您尝试执行它，它不会终止！ （看看您能否找出原因。） 实现 lambda 演算 下面是 R5RS 方案中 lambda 演算的 7 行、3 分钟解释器。用技术术语来说（如下所述），它是一个基于环境的指称解释器。 ; 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-expression ）语法世界中。 （如果没有，您必须阅读解析中的词法分析；您可以从我的一篇关于词法分析的文章开始。）在Scheme中，read从stdin和中获取正确的带括号的输入