想了想，最后还是觉得应该用这篇paper开头。

什么是Defunctionalization?

简单的来说，Defunctionalization是一个程序变换。更具体的说，Defunctionalization接受一个高阶编程语言的程序，输出一个一阶编程语言的程序。这通过一下变换完成。

  • 创建一个代数数据类型，lam，跟创建一个函数apply: (lam * Any) -> Any（是的，naive的Defunctionalization并不类型安全）
  • 对于所有a -> b类型作为一等公民（不是直接调用）出现的地方，把类型a -> b变换成lam。
  • 对于所有构建闭包的地方，创建一个新的lam构造子。这个构造子的成员就是这个闭包捕获的变量。
  • 同时，在apply函数内，给出该lam构造子的实现 - 而这实现照抄原closure的body。
  • 对所有调用闭包f x的地方，改为apply (f, x)。

举个例子，假如我们有以下代码，

(* aux : int * (int -> int) -> int *)
fun aux (i, f) 
    = f i

(* main = fn : int * int list -> int list *)
fun main (i, js)
    = let fun walk nil
          = nil
        | walk (j :: js)
          = (aux (i, fn i => i + j)) :: (walk js)
    in walk js
end

Defunctionalize后，会成为

datatype lam = LAM of int

(* apply : lam * int -> int *)
fun apply (LAM j, i)
    = i + j

(* aux_def : int * lam -> int *)
fun aux_def (i, f)
    = apply (f, i)

(* main_def : int * int list -> int list *)
fun main_def (i, js)
    = let fun walk nil
          = nil
        | walk (j :: js)
          = (aux_def (i, LAM j)) :: (walk js)
    in walk js
end

这时候，我们可以看到

  • aux的一个f类型从(int -> int)成为lam
  • fn i => i + j成为了Lam j，而apply(Lam j, i)会返回i + j
  • aux函数原先f i的地方，改为调用apply (f, i)

Defunctionalization的用处是什么？

一般来说，Defunctionalization可以把闭包编译上代数数据类型，于是可以通过实现代数数据类型来实现闭包。但是，我们一般不这样整，是因为闭包实现本来也不难，而defunctionalization以后诞生的巨大的pattern matching会带来性能问题。

尽管如此，Defunctionalization依然很有意思。这篇paper，就是在探究Defunctionalization跟各种常见PL概念之间的联系。

更具体的说，

  • church encoding的defunctionalization是原数据结构
  • 用DList数据结构实现reverse的程序，在defunctionalize下，就是最经典的reverse as foldl of cons
  • 如果我们有一个CPS的程序，我们把continuation defunctionalize后可以玩一些有趣的东东。CPS变换+Defunctonalization是一个很经典的连招。
  • 对于一个small step operational semantic interpreter, CPS + Defunctionalization = Contextual Semantic
  • 对于一个Definitional Interpreter，这样整可以给出对应的Abstract Machine，比如Call By Name/Value对应着Krivine’s Machine跟CEK Machine
  • 对于一个0^n1^n识别器（试图识别一个字符串，前面是一串0，后面是同等长度的一串1），CPS + Defunc = PushDown Automaton，而这时候continuation/stack刚好代表了peano natural，就是在数多吃了多少个0
  • 对于一个regular expression matcher，CPS + Defunctionalization = stack based regular expression matcher

就这样。额外阅读：

  • Defunctionalization of Typed Programs - 还记得上面说Defunctionalization不是type-safe的吗？这篇paper把这修复了。
  • Cutting out continuations - 上面举出的很多工作，都是CPS变换后上Defunctionalization。这篇paper说这两个步骤可以合二为一。
  • Defunctionalized interpreters for programming languages - 这篇paper把各种各样的operational semantic/denotational semantic联系在一起，属于‘semantic的大一统’paper。（不过吐槽一下，忘了axiomatic semantic了。不过dijkstra monad is nothing but state monad continuzed，按这个角度口胡几下？）