高阶函数调用的闭包转换和单独编译

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 也允许虚拟函子，但这本质上是带有额外间接寻址的闭包情况。）

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

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

1. C++ (98) 方法，它强制被调用者选择调用站点形状（通过形式参数类型：虚拟函子、函数指针或非虚拟函数）函子）或通过使用模板放弃单独的编译，有效地指定下面的解决方案 #2。

2. 重载：编译器可以通过适当的名称重整来多次实例化map以及所有其他高阶函数。实际上，每个调用站点形状都有一个单独的内部函数类型，并且重载解析会选择正确的类型。

3. 强制采用全球统一的调用站点形状。这意味着所有顶级函数都采用显式的 env 参数，即使它们不需要它，并且必须引入“额外”闭包来包装非闭包参数。

4. 保留顶级函数的“自然”签名，但要求所有高阶函数参数的处理都通过闭包完成。已关闭函数的“额外”闭包调用包装器 Trampoline 函数来丢弃未使用的 env 参数。这看起来比选项 3 更优雅，但更难有效实施。编译器要么生成大量与调用约定无关的包装器，要么使用少量对调用约定敏感的 thunk...

拥有优化的闭包转换/lambda 提升混合方案，每个函数可以选择是否将给定的闭包参数粘贴在环境或参数列表中，似乎会使问题更加尖锐。

无论如何，问题是：

• 这个问题在文献中有明确的名称吗？
• 除了以上四种方法之外，还有其他方法吗？
• 方法之间是否存在众所周知的权衡？

Answer 1

这是一个非常深刻的问题，有很多影响，我不想在这里写一篇学术文章。我将只触及表面，并会向您指出其他地方的更多信息。我的回答基于使用 Glorious Glasgow Haskell Compiler 和 新泽西州标准机器学习，以及有关这些系统的学术论文。

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

• 已知调用表示编译器确切知道正在调用哪个函数以及需要多少个参数的调用站点。

• 未知调用意味着编译器无法确定可能调用的函数。

  未知调用

• 如果被调用的函数正在获取它期望的所有参数，并且直接进入代码，则已知调用是完全饱和。如果函数获取的参数少于预期，则该函数部分应用并且调用仅导致分配闭包

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

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

则调用 地图已知并且完全饱和。
如果我

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

这样写，那么对 map 的调用就是已知并且部分应用。
最后，如果我

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

这样写，那么对 f 和 g 的调用都是未知。

成熟编译器所做的主要事情是优化已知调用。在您上面的分类中，该策略主要属于#2。

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

• 如果函数的部分但不是全部调用点已知，编译器可能会认为值得为已知调用创建一个特殊用途的调用约定，该约定将被内联或使用只有编译器知道的特殊名称。源代码中以该名称导出的函数将使用标准调用约定，其实现通常是薄层，它对专用版本进行优化的尾部调用。

• 如果已知调用未完全饱和，编译器仅生成代码以在调用者中分配闭包权利。

  如果已知调用未完全饱和，编译

闭包的表示（或者一等函数是否由其他技术（例如 lambda 提升或去功能化）处理）在很大程度上与已知调用和未知调用的处理正交。

（可能值得一提的是 MLton 使用的另一种方法：它是一个整体程序编译器；它可以看到 代码；它使用我已经忘记的技术将所有函数简化为一阶，因为高阶语言中的一般控制流分析很棘手。）

---

所有源 问题：

• 我认为这个问题只是“如何编译一等函数”这个混乱问题的一个方面。我从未听说过这个问题的特殊名称。

• 是的，还有其他方法。我已经概述了一种方法并提到了另一种方法。

• 我不确定是否有关于权衡的伟大、广泛的研究，但我所知道的最好的、我强烈推荐的研究是制作快速柯里化：Push/Enter 与 Eval/Apply 用于高阶语言 作者：Simon Marlow 和 Simon Peyton琼斯.本文的众多优点之一是它解释了为什么函数的类型不告诉您对该函数的调用是否完全饱和。

---

总结一下你的编号选项：编号 1 是不可能的。
流行的编译器使用与数字 2 和 3 相关的混合策略。
我从来没有听说过类似数字 4 的东西；已知和未知调用之间的区别似乎比区分顶级函数和函数类型的参数更有用。