7行代码,3分钟:从无到有实现一门编程语言

实现一门编程语言对任何程序员来说都是值得拥有的经验,因为它能加深你对计算原理的理解,并且还很有趣。

在这篇文章中,我已经让整个过程回归到它的本质:为一种函数式(图灵等价)编程语言设计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中仅有三种表达式:变量引用,匿名函数、函数调用

匿名函数:

匿名函数以”λ-.”标记开始,所以 (λ v . e)函数用来接收一个参数v并返回值e。

函数调用:

函数调用用两个临近的表达式表示:(f e)

Examples

我们可以将这个恒等函数应用到一个恒等函数上:

((λ x . x) (λ a . a))(仅返回这个恒等函数本身)

这儿有一个更有趣的程序:

你能弄清楚它是干嘛的?

等一下!见鬼,这怎么算一门编程语言?

乍一看,这门简单语言好像缺乏递归和迭代,更不用说数字、布尔值、条件语句、数据结构和剩余其他的。这样的语言怎么可能成为通用的呢?

λ演算实现图灵机-等价的方式是通过两种最酷的方式:

邱奇编码(Church encoding)和Y combinator(美国著名企业孵化器)

我已经写了两篇关于Y combinator和邱奇编码的文章。

但是,你如果不想读它们的话,我可以明确的告诉你比起你期望的仅一个((λ f . (f f)) (λ f . (f f)))程序来说 有更多的 lambda calculus知识。

表面上开始的程序叫做Ω,如果你尝试运行它的话,它不会终止(想一下你是否明白其中原因)

实现λ演算

下面是基于Scheme语言标准(R5RS)的7行、3分钟λ演算解释器。在术语中,它是一个依赖环境的指示解释器

代码将从文件中读入程序、分析、求值最后打印值(这是一段没有注释和空白行的7行代码)

Schema语言的read函数使得词法分析和语法分析简单化。只要你想处于语法“平衡圆括号”(符号式)世界里。

(如果不想的话,你必须钻研语法分析,你可以从我写的一篇语法分析文章开始)
在Scheme语言中,read函数从文件获取加括号的输入并把它分析然后生成树
函数eval 和 apply构成了解释器的内核。即使我们使用的是Scheme语言,我们仍给出了函数概念上的“签名”

eval函数将一个表达式和环境变量赋给一个值。表达式可以是一个变量、λ术语或者是一个应用。

一个环境值是从变量到值的映射,用来定义一个开项的自由变量(开项用来存放出现的没有绑定的变量)。想一下这个例子,表达式(λ x . z)是开项,因为我们不知道z是什么。

因为我们使用Scheme语言标准(R5RS),所以用联合列表来定义环境值

闭项是一个函数的编码,这个函数使用定义自由变量的环境值来匹配lambda 表达式来。换句话说来说,闭项关闭了一个开项

Racket中有一种更简洁的实现

Racket是Scheme的一种方言,功能齐备强大。它提供了一个整顿解释器的匹配构造机制。

这一种更加庞大,但是理解起来也更容易、更简单

一门更加庞大的语言

λ演算是一门极小的语言。尽管如此,解释器eval/apply的设计可以升级到更加庞大的语言。

例如,用大约100行的代码,我们可以为Scheme本身相当大的一个子集实现解释器

考虑一门含有不同表达式分类的语言:

  1. 变量引用:除x,foo,save_file
  2. 数值和布尔类型的常量:除300,3.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).

现在在语言中添加三种高级形式:

  1. 函数定义:(define (proc-name var …) expr).
  2. 全局定义:(define var expr)
  3. 高级表达式:expr

下面是完整的解释器,包含测试代码和测试用例:

你可以从这里下载源代码:minilang.rkt.

在这里

你应该尽可能快的通过修改最新的解释器为编程语言彻底检验新的想法

如果你想使用含有不同语法的语言,你可以建立一个解析器,将符号式转存出来。

使用这种方法,可以容易把句法设计与语义设计分离出来

更多资源:

1 收藏 1 评论

关于作者:Calarence

软件工程系大三生,喜欢看书,文学+技术,感兴趣的方向:web、模式识别,编程语言Java新浪微博@哆啦Aa有梦个人博客Calarencce\'s blog如需兼职或实习生,请Email我:749826557@qq.com 个人主页 · 我的文章 · 10

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部