关于 [1] 的第7章 Offline and Online Partial Evaluation 的笔记

Offline 和 Online 指的是什么?

Offline 和 Online 的区别在于 Binding Time Analysis 的时机: Offline 会提前把 Binding Time Analysis (BTA)做完, 并保证 binding time 的相合性, 再基于 BTA 的结果(可以由 Division 或 Annotated Program 表示)进行 specialize; Online 会直接基于输入的程序做 specialize, 在 specialize 的过程中保证 congruence.

Figure 1: Online 方法和 Offline 方法的结构

Figure 1: Online 方法和 Offline 方法的结构

Figure 2: Online 方法和 Offline 方法的定义

Figure 2: Online 方法和 Offline 方法的定义

Online 方法的分析

OnPE 方法的类型签名: \[ Expression \rightarrow On-Env \rightarrow On-Value \]

其中 \(On-Value\) 是 specialize 的结果, 是一个 Variant(tagged union): 如果表达式在\(On-Env\)中是 static 的, 则 specialize 到一个值(inVal); 如果表达式在\(On-Env\)中是 dynamic 的, 则 specialize 到一个表达式(inExp).

\(On-Env = Var \rightarrow On-Value\)包含了\(Expression\)中变量的绑定信息: 如果变量是 static 的, 则 specialize 到一个值(inVal); 如果是 dynamic 的, 则 specialize 到一个表达式(inExp).

为什么 OffPE 没有这样的区分呢? 因为 OffPE 在 BTA 中就分析了哪些表达式会 specialize 到 Value, 哪些会 specialize 到 Expression, 然后通过 division 或者 binding time annotation 表示这一信息.

OnPE 的含义是: 输入一个源程序的表达式(Expression), 和这个表达式中的自由变量在 residual program 中对应的 specialized expression(On-Env = Var -> On-Value), 如果是 static 则绑定到值, 如果是 dynamic 则直接绑定到一个变量表达式. 返回一个 specialized expression(On-Value).

Online 方法的输入是不区分 subject program 中的 static 和 dynamic exppression 的, 也就是说 Online 方法直接在输入源程序上进行变换. 因此可以在 specialize 的过程中"实时的"根据当前的 specialize 上下文判断输入的表达式是不是 static 的, 因此相比与 Offline 方法, Online 方法可以把更多的表达式视作为 static(发现更多的 specialize 机会).

Offline 方法的分析

而 OffPE 的类型签名: \[ 2Expression \rightarrow Off-Env \rightarrow Off-Value \]

其中 2Expression 代表了经过 Binding Time Analysis 后得到的 annotated program. OffPE 的含义是: 输入一个经过标注了 Binding Time 的 2Expression 表达式, 和一个 Off-Env 包含这个表达式中的自由变量的 Binding Time(Off-Value 是一个 untaged union: 可以是 static 的 Value, 也可以是一个代表需要动态求值的 1Expression). 返回一个 specialized expression(Off-Value).

BTA 保证了当一个变量出现在程序中需要 static value 的位置的时候, Off-Env 中的 lookup result 一定是一个 value, 所以在 OffPE 中无需再对 OffPE 的返回值的类型进行判断, 直接把返回值放在需要它的位置就好了.

为什么 online partial evaluation 对 self application 不友好?

OnPE 的类型签名: \[ Expression \rightarrow On-Env \rightarrow On-Value \]

光从类型上来看, OnPE 的类型和二村映射的类型是完全匹配的, 但是在通过 OnPE 实现第二二村映射生成 compiler 的表现却并不好, 书中给出了一个例子说明这一点:

(cons(car names)(car values)) 是解释器中的表达式, names 和 value 都是解释器中的变量. 在应用把 OnPE[OnPE, int] 的后, 会得到如下程序片段,

在 \(OnPE(int, prog)\) 的时候, \(lookup [names] rho\) 的返回值总是一个包含 prog 中的表达式的 Value, 但是在上面 \(OnPE(OnPE, int)\) 生成的程序中, 其对 \(lookup_{names} rho\) 的返回值也进行了判断.

从直觉上, 这样的"反常"现象可以由两方面来解释:

  1. 生成的 compiler 会从 OnPE 继承一些行为: OnPE 需要处理所有可能的 subject program 中的表达式, 并判断表达式在 On-Env 下是 static 还是 dynamic, 因此使用 OnPE 的返回值时需要根据返回值是 Value 还是 Expr 分别处理; 但是 \(OnPE(int, prog)\) 的时候, 有一些表达式一定是 Value, 比如说\(lookup [names] rho\), 但在 self application 的时候没有利用这一信息;
  2. OnPE 具有通用性(generality), 其能力对于实现二村映射来说"过剩"了: OnPE 对输入的类型没有任何限制, 对 任意 程序都可以specialize到其 任意 输入. OnPE 的输入 On-Env 中包含了 subject program 中的变量到 OnVal 的映射, 而 OnVal = Value | Expr 中的 Value 可以是任意类型的 program text 也可以是一般的数据, 但是在几个二村映射中 Env 中所绑定的都是 program text, (比如说 mix(int, prog), mix(mix, int) 的时候, On-Env 中的 Value 绑定到的就分别是源程序和解释器程序的 program text). 而 OnPE 中没有对这种"程序的输入本身是程序"情况做特殊的考虑:“不管 subject program 的获得哪种输入, 我都把它们嵌入到 subject program 中”. 也就是说, 我们甚至可以把 OnPE 应用到程序的输入, 生成一个没有什么实际意义的 crazy 程序, 这个 crazy 的语义是: 接受源程序然后得到源程序的运行结果. 而这样的一般性也被带到了由 OnPE [OnPE, int] 生成的 compiler 中: 在 OnPE [OnPE, int] 的输入 On-Env 中, 既可以绑定源程序片段, 从而得到编译器; 也可以绑定源程序的输入, 从而得到 crazy.
Figure 3: crazy 程序的语义

Figure 3: crazy 程序的语义

通过消除一般性以更好的 self-Applicatoin

刚刚提到, OnPE 是具有通用性(generality)的: 想在 On-Env 中绑定什么都行, 只要它能作为 subject program 的输入. 但是在二村映射中, 这样的一般性是不必要的, 因为静态输入的参数已经确定了–待编译的源程序.

\(OnPE_2[int, source]\) 的时候, \(int\) 是subejct program, \(int\) 中被绑定到 \(source\) 程序片段的名字, 在环境中映射到 InVal, 绑定到 \(input\) 的名字在 On-Env 中映射到 InExp 中. 所以 \(OnPE_2\) 的行为通俗来讲是这样的:

  1. 拿到一个待 PE 的 subject program \(int\);
  2. 拿到一个subject program的Environment, 在这个Enviroment中, 告诉了 \(OnPE_2\) subject program \(int\) 中哪些变量绑定到 InVal (source 关联的变量), 哪些变量绑定到 InExp (input 关联的变量).
  3. 开始递归遍历 subject program \(int\), 返回residual program, 在这个过程中: 如果看到 \(int\) 中的name, 需要去 Environment 中查看这个 name 是 InVal 还是 InExp.

在 \(OnPE_1[OnPE_2, int]\) 的时候, \(OnPE_1\) 的"眼中":

  1. \(OnPE_2\) 是一个一般的程序, \(int\) 是这个程序已知的输入;
  2. \(OnPE_2\) 的另一个输入 Environment 是未知的, 所以对于 \(OnPE_2\) 中依赖于 Environment 的计算在specialize的过程中都会保留, 比如说 lookup [name] 这一操作, 即使 \(OnPE_2[int, source]\) 的时候 lookup[name] 一定返回一个 InVal, \(OnPE_1\) 也不知道这一点, 它只知道 \(OnPE_2\) 往一个既有 InVal 又有 InExp 的Environment中lookup了, 所以lookup的返回值有可能是 InVal 或 InExp 两种, 所以对这个返回值的分支判断当然要保留.

Offline Partial Evaluator 在 self-application 上的优势正是通过消除 Online Partial Evaluator 的一般性获得的: Offline PE 会首先通过 Binding Time Analysis 得到一个 annotated interpreter: \(int^{ann}\).

首先分析一下 \(OffPE_2[int^{ann}, source]\) 的计算过程: \(OffPE_2\) 在判断 \(int^{ann}\) 中的表达式应该是 static 还是 dynamic 不需要管另一个输入 \(source\), 因为一切都在 \(int^{ann}\) 中标定好了.

然后就可以在已知 \(int^{ann}\) 的输入下, 对 \(OffPE_2\) 进行标定了: \(OffPE_2\) 中的表达式, 如果在只依赖于 \(int^{ann}\) 那么就可以标定为 static , 标定后的 \(OffPE_2\) 可以称之为 \(OffPE^{ann}\).

再来分析 \(OffPE_1 [OffPE^{ann}, int^{ann}]\) : \(OffPE^{ann}\) 中保留了 \(OffPE_2[int^{ann}, source]\) 时候的信息: 如果已知 \(int^{ann}\) 输入, \(OffPE_2\) 中"哪些表达式是 static". 从而 \(OffPE_1\) 可以利用这些信息决定 \(OffPE^{ann}\) 要 specialize 成什么样.

由于 \(int^{ann}\) 已经标注了"等source来了要如何使用"了, \(OffPE^{ann}\) 也会利用这些annotation做specialize (标注了static的就代表environment中能找到Value或者能由environemnt中的Value计算出来, 标注了dynamic的就代表environemnt中有Expression或者保持原样), 也就是说 \(OffPE^{ann}\) 不需要知道source是什么也能做specialize. 这个行为继承到生成的compiler中表现为生成的compiler不需要再对Enrionment中取得的值做分支判断, 这个判断已经被 \(int^{ann}\) 标注好了.

为什么说失去了通用性呢? 因 为相比于 OnPE, OffPE 还限制了 self-application 所生成的 compiler 的输入: 哪些东西是 static, 哪些东西是 dynamic 需要与 \(int^{ann}\) 中的 annotation 保持一致.

具体来说, 在 OffPE(int, source) 的 Off-Env 中: 待编译的源程序片段是 static 的输入, 只能作为 Value 绑定到静态变量; 而源程序输入是 dynamic 的, 只能作为 Expression 绑定到动态变量.

Partial Evaluation

References

[1]
N. D. Jones, C. K. Gomard, and P. Sestoft, Partial Evaluation and Automatic Program Generation. USA: Prentice-Hall, Inc., 1993.