关于 Partial Evaluation 的第一章 Introduction 的笔记.
从抽象上来看, 程序都可以看作是一个输入到输出的函数. 比如说某个程序输入可以拆分为 in1 和 in2,
如果该程序的输入 in1 是可以在运行之前确定的,
那么我们就可以生成一个针对 in1 优化的程序, 这个过程就叫做 specialization(特化).
针对 in1 优化的"优化器"可以叫做 specializer.
所以 Partial Evaluation 可以看作做了两件事情:
- 计算可以预先知道的输入
- 为提前知道的输入进行特化, 生成一个针对预先输入优化的程序
二村映射
我们通过一个解释器程序来举例子, 一个解释器可以通过下图描述:
+--------+
P --> | interp | --> out
input --> | |
+--------+
对于这个 interpreter, 如果有一个可以针对解释器的源程序输入 P 的 specializer,
那么我们可以通过在解释器上 specialize 得到一个可执行程序. 用图画出来就是这样,
下图中的 PE 就是我们的 specializer, interpP 就是一个可执行程序.
图 1:
+----+
interp --> | PE | --> interpP
P --> | |
+----+
这个时候我们可以看到, 这个 specialzer 本身也是多参数的函数,
如果我们已经有了一个 specialzer,
如果再把这个 specializer 对 interp 参数进行 specialization,
我们就可以得到一个编译器(下图中的 PEinterp).
图 2:
+----+
PE --> | PE | --> PEinterp
interp --> | |
+----+
这里的 PE 又是一个多参数的函数, 我们又可以对其进行 Specialization.
如果有一个 specialzer, 可以让 PE 对 PE 进行进行 Specialization,
那么就可以得到一个编译器的生成器(图中的 PE_PE).
+----+
PE --> | PE | --> PE_PE
PE --> | |
+----+
这里的每个 PE 的输入都是两个程序,
其中一个程序 in1 是另外一个程序 in2 的输入;
PE 的功能都是为 in2 生成一个特化在 in1 的版本,
这个特化的版本往往会比 in1 |> in2 更加高效.
二村映射就是指的以上的几个程序特化的过程,
上面的 specialize 的过程有时候也叫 stage: 通过 specialize 把原来的程序分成了好几步.
Partial Evaluation 和 Partial Application(柯里化)
Partial Evaluation 和编程语言中的 Partial Application(柯里化)还是很不一样的 在 Partial Application 中, 得到的是相同语言中的函数; 而 partial evaluation 中, 得到的是一个 新的程序. 这里就体现了一个 program text 和 running program 的区别: program text 是一个 syntactic world 里的东西, 比如说符号, 表达式, 只是程序的 表示; function 是数学意义(语义)上的东西, 需要把 program text 传给语义函数后(通俗的说就是要把程序运行起来)才能把 program text 和 function 关联起来. 所以 partial evaluation 和 柯里化 时的 partial application 并不是一回事.
感谢 kokic 为本文找到的 typo!