高阶函数调用的闭包转换和分离编译

Question

在编译高阶函数调用时，是否有一种标准的处理分离编译和不同类型闭包转换之间交互的方式？

我知道大多数编程语言中存在三种不同编译的类似函数的结构：闭包、（顶层）函数和C++样式的函数对象。它们在语法上被称为相同的方式，但编译器最好生成不同形状的调用站点：

Syntax:  | clo(args)                 |   func(args)     |   obj(args)
--------------------------------------------------------------------------------
Codegen: | clo.fnc(&clo.env, args)   |   func(args)     |   cls_call(&obj, args)
              ^      ^                      ^                   ^     ^
            fn ptr   |                      +--"top level" fn --+     |
                     +--- "extra" param, compared to source type -----+

在C++中，cls_call将是T::operator()，对于obj的类T。C++还允许虚函数对象，但这本质上是带有额外间接性质的闭包情况。

此时，对map (x => x > 3) lst和map (x => x > y) lst的调用应该会调用不同的map函数，因为第一个是简单的函数指针，在提升后，而第二个是一个闭包。

我可以想到四种处理这个问题的方法：

1. C++（98）方法，强制被调用者选择调用站点形状（通过形式参数类型：虚函数对象、函数指针或非虚函数对象）或使用模板放弃分离编译，有效地指定下面的解决方案#2。 2. 重载：编译器可以使用适当的名称修饰，多次实例化map和所有其他高阶函数。实际上，每个调用站点形状都有一个单独的内部函数类型，并且重载解析选择正确的函数。 3. 强制全局统一的调用站点形状。这意味着所有顶层函数都需要显式的env参数，即使它们不需要它，还必须引入“额外”的闭包来包装非闭包参数。 4. 保留顶层函数的“自然”签名，但强制所有处理高阶函数参数的操作都通过闭包完成。已经关闭的函数的“额外”闭包调用一个包装器跳板函数来丢弃未使用的env参数。这似乎比选项3更优雅，但实现起来更困难。编译器要么生成大量的调用约定无关的包装器，要么使用少量的调用约定敏感的thunks...

拥有一个优化的闭包转换/lambda lifting混合方案，每个函数可以选择将给定的闭包参数放在env或参数列表中，似乎会使问题更加严重。

问题：

1. 这个问题在文献中有明确的名称吗？ 2. 除了上述四种方法之外，还有其他方法吗？ 3. 有哪些众所周知的方法之间的权衡？

- Ben Karel

Answer 1

这是一个非常深奥的问题，具有很多影响，我不想在这里写一篇学术文章。我只会浅尝辄止，并指向其他地方获取更多信息。我的回答基于个人使用Glorious Glasgow Haskell Compiler和Standard ML of New Jersey的经验以及关于这些系统撰写的学术论文。

在雄心勃勃的编译器中所做的关键区分是已知调用和未知调用之间的区别。对于具有高阶函数的语言，次要但仍然重要的区别是调用是否完全饱和（我们只能在已知的调用站点上决定）。

- 已知调用意味着编译器确切地知道被调用的函数以及它期望的参数数量。 - 未知调用意味着编译器无法确定可能被调用的函数。 - 如果被调用的函数正在接收其期望的所有参数，并且直接进入代码，则已知调用是完全饱和的。如果该函数接收的参数少于期望的参数，则该函数是部分应用的，并且该调用仅导致闭包的分配。

例如，如果我编写Haskell函数：

mapints :: (Integer -> a) -> [a]
mapints f = map f [1..]

那么对 map 的调用就是已知的并且完全饱和的。
如果我写

inclist :: [Integer] -> [Integer]
inclist = map (1+)

然后调用 map，它是已知的并且部分应用的。
最后，如果我写

compose :: (b -> c) -> (a -> c) -> (a -> c)
compose f g x = f (g x)

那么对于函数f和g的调用都是未知的。

成熟的编译器主要做的事情是优化已知调用。根据您上面的分类，这个策略主要属于第二类。

• 如果对一个函数的所有调用点都已知，好的编译器会为该函数创建一种特殊的调用约定，例如在恰当的寄存器中传递参数以使事情顺利进行。

• 如果某些但不是所有函数的调用点都已知，则编译器可能决定为已知调用创建一种特殊的调用约定，这些调用将被内联或将使用仅对编译器已知的特殊名称。在源代码中导出的函数将使用标准调用约定，其实现通常是生成优化尾调用到专门版本的薄层。

• 如果已知调用没有完全饱和，则编译器只会生成代码来在调用者中分配闭包。

闭包的表示（或者是否使用其他技术如lambda提升或defunctionalization处理一级函数）与已知与未知调用的处理大致无关。

（值得一提的是，MLton使用的是另一种方法：它是一个整个程序编译器；它可以看到所有的源代码；它使用了我忘记的一种技术将所有函数降为一级。在高阶语言中，由于通用控制流分析是不可行的，仍然存在未知的调用。）

---

关于你的最后问题：

• 我认为这个问题只是一个混乱问题的一面，这个问题被称为“如何编译一流函数”。我从来没有听说过仅仅针对这个问题的特殊名称。

• 是的，还有其他方法。我草拟了一个并提到了另一个。

• 我不确定是否有任何关于权衡的广泛研究，但我所知道的最好的一篇文章，我强烈推荐，是由Simon Marlow和Simon Peyton Jones撰写的Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-Order Languages。这篇论文的许多伟大之处之一在于它解释了函数类型不能告诉您该函数调用是否完全饱和。

---

为了总结你的编号选择：第一项是不可行的。 流行的编译器使用与第2和第3项相关的混合策略。 我从未听说过类似于第4项的任何东西；区分已知调用和未知调用似乎比区分顶级函数和函数类型参数更有用。

- Norman Ramsey