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，不敢保证全是正确的代码，可供参考。