Yukang's Page

另一本魔法书: EOPL

2014-03-29

eopl

概述

很多学习计算机的同学都知道有一本号称魔法书的经典教材叫作《SICP》《计算机程序的构造和解释》,MIT的计算机入门课程用的教程。这本书内容广泛而深邃,从出版几十年来影响了很多程序员。今天介绍另外一本我认为也是魔法书的教材,叫做《Essential of Programming Language》,简称EOPL,当然能获得简称的书都是不简单的。这本书虽然也年代久远,但是知名度不如SICP高。其作者是Dan Friedman,就是那位王垠同学的导师。这位程序语言领域的大牛写过很多Scheme相关的书籍,比如《The Little Scheme》系列,这个系列广受好评,可能很多人都读过。

我读的是EOPL3,据说这个版本稍微有点冗长,不过我还没读过前面的版本,所以对此不好评价。
EOPL主要关注程序语言的方方面面,一共分为9章。这本书的讲解方式是先稍微概述主题,然后会有相关语法的定义,然后是关键代码的实现。这里同样采用了Scheme来讲解。用Scheme的好处的我们可以站在一个更抽象的角度来编写程序(Scheme如此强大,可以定义自己的语法,比如这里面的define-datatype和sllgen)。你可以看到这本书在反复折腾各种解释器,里面都是在往一个简单的解释器添加各种特性。

预备基础

阅读这本需要一些简单的Scheme基础,不过对于有一些编程经验的人来说不难。我推荐这本Teach Yourself Scheme in Fixnum Days。Scheme的基本元素很少、内核简单(用Scheme写一个能自身的元解释器非常容易),这和象棋有些像:规则简单,组合变化多。至少需要了解以下Scheme的基本内容

递归思想

递归不只是理解程序的一种方式,同样也是写程序的一种方式。在EOPL中到处都是递归,解释器执行的过程是递归,里面的Checker也是递归。递归无处不在。

高阶函数

在函数式编程语言中,函数和变量一样也是一等公民。在Scheme里函数可以接收函数作为参数,可以把函数作为返回值。在EOPL中的envrioment可以用函数来表示。

代码即数据 数据即代码

抛开效率不说,用List可以表示很多数据结构。
用Scheme的一个好处,就是代码和数据几乎没有界限,比如Parser部分,因为书里自带的sllgen如此强大,要修改语法的定义是如此的简单。而Parser出来的结果就是语法树,这语法树同样是个层层嵌套的表,解释器把这个作为输入就行了。

各章内容

Abstraction

前两章都是基础准备,介绍了如何用递归来做抽象,包括定义和相关数据结构的实现。比如Enviroment,这不过是在一个小的envrioment上添加一个新的绑定。仔细思考那种用高阶函数的表示方法,这在以前的语言中不常见。

Expression

基本的解释器,但这个解释器是后面章节的基础。到这里这个简单的语言已经可以支持递归了。

State

实现了一个简单的store,用来映射variable到value。接着讲述call-by-value, call-by-reference。到这里你可以看到程序语言中指针到底是个什么东西,以及这到底是如何实现的。

CPS

CPS内容比较难理解,但是CPS也是一个很有用的概念。可以看到使用CPS使得程序的空间固定,如何使用CPS来实现多线程。后面一章也是关于CPS的,实现了一个通用算法来进行CPS转换。

Type System

为语言添加类型的好处,类型推倒如何实现,用替换法来做的一个简单的Type Checker。

Module

如何从语言层面支持Module,以及面向接口编程。

OO

面向对象和接口是如何实现的,在这里OO的实现看起来是有点繁杂,通过实现OO来看清楚本质。

习题

这本书有很多习题,每一个题目都有相应的星号标示难度,三颗星的习题大部分还是需要很多思考。
这里大部分习题都是需要coding,在解释器里添加一些新的特性,往往需要一些简单的代码修改即可。

我做了大部分习题,https://github.com/chenyukang/eopl,不敢保证全是正确的代码,可供参考。

使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章