Language and Interpreters

partial evaluation 的第三章 Programming Languages and Interpreters 的笔记.

这一章主要是形式化的介绍了一下 Partial Evaluation 中的基本概念: 程序, 解释和编译.

程序只是一种表示, 程序的语义决定了程序的含义, 在这里程序的语义指的是程序执行语义的描述, 比如说 Operational Semantic, 就提供了一套指导程序应该如何进行规约(reduction)的规则.

定义语言 = 定义抽象机

所有编程语言的语义都隐式定义了一个用于执行程序的抽象机, 可以把抽象机看作是程序的"解释器"(有的资料也称之为"元解释器", 但我还没想明白"元"在哪里), 这也是大家经常说 所有语言本质上都是解释执行 的原因.

解释器和解释器开销

与直接在这个编程语言的抽象机来执行不同, 用另外一个程序来实现程序的语义可以称之为 解释执行, 也就是我们常说的解释器 (注意: 解释器本身也是在解释器对应语言的抽象机上执行的).

对于某个目标程序 P, 解释器 int 在对应抽象机上的解释程序 P 所需要的执行步数, 一般要比 P 在 P 对应的抽象机上的执行步数要多, 而且往往是成倍数的多.

比如说, 对于一个变量的求值, 在代表程序语义的抽象机上一共只需要一步 \(x \rightarrow Env[ [ x ] ]\) ; 而在解释器中, 这个求值会对应到 5 步:

解释函数 (如 eval) 的调用
模式匹配判断当前表达式是一个变量
读取环境
读取变量名
读取环境中对应变量名的值

所以我们可以通过 case by case 的分析各种语义的对应解释器步数得到一个大致的倍数, 从而估算解释的开销(overhead), 这个开销被称为 解释器开销(Interpretation Overhand).

刚刚提到了开销, 这个开销实际上是不可以忽略的, 首先, 在真实世界的编程语言中, 这个开销的倍数可能非常大; 另一方面, 当语言的实现涉及到多层中间表示的时候, 解释也会有多层, 那么这个开销的倍数也会相乘, 最终开销也会呈指数增长. 将源程序直接编译为可执行的程序(比如说机器指令)就是减少开销上的一种思路(减少解释的开销). 这个过程也叫 lowering, 把更高层的表示 lowering 到底层的表示.

自举(bootstrapping)

自举指的是一个 compiler h 可以通过被其 compiled version t 编译, 并且得到 compiled version t.

现在发现其实很多介绍没有把这一点讲透, 很多人都说: “自举就是编译器可以编译自己.” 让人感觉不到这其中的微妙之处: “自己编译自己有什么神奇的吗?” 实际上更完整的描述应该是: 一个编译器(compiled version)可以通过编译自己(source)*得到自己*(compiled version)

书上通过举了个例子说明如何通过扩展 S 语言实现的 S 语言的编译器并完成自举的过程:

首先我们已有 S 语言编译器的源码 h 和编译后的代码 t