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

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

我知道在大多数编程语言中明确编译的三个函数类构造：闭包，（顶级）函数和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的功能，这是因为第一是吊装后一个简单的函数的指针，和第二个是一个封闭。

我能想到的处理这个问题的四种方式：

的C++（98）的方法，这迫使被叫方要么选择一个调用点形状（通过形式参数类型：虚拟函子，函数指针或非虚拟函子），或者使用模板删除单独的编译，从而有效地指定下面的解决方案＃2。
重载：编译器可以用map和所有其他高阶函数，并使用适当的名称修改来执行多重实例化。实际上，每个调用站点形状都有一个单独的内部函数类型，重载决策选择正确的一个。
强制全球统一的呼叫站点形状。这意味着即使所有顶层函数都不需要它，也需要明确的env参数，并且必须引入“额外”闭包来包装非闭包参数。
保留顶层函数的“自然”签名，但要求通过闭包完成所有高阶函数参数的处理。已关闭函数的“额外”闭包调用封装trampoline函数来丢弃未使用的env参数。这似乎比选项3更优雅，但难以有效实施。或者编译器生成调用约定-上独立包装的多个，或它使用少量的调用约定敏感的thunk的...

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

不管怎么说，问题：

难道这一问题在文献中一个明确的名称？
除了上述四个之外，还有其他方法吗？
在方法之间是否有众所周知的折衷？

来源

2010-02-19 Ben Karel

这是一个相当深刻的问题，有很多后果，我不想在这里写一篇学术文章。我只会抓表面，并会指出其他地方的更多信息。我将我对个人经历的回应建立在Glorious Glasgow Haskell Compiler和Standard ML of New Jersey以及有关这些系统的学术论文上。

在一个雄心勃勃的编译器提出的主要区别是知电话和未知电话之间的区别。对于具有高级功能的语言，次要但仍然重要的区别是呼叫是否为完全饱和（我们只能在已知的呼叫站点上决定）。

一个称为呼叫意味着通话网站，编译器知道到底是被叫什么功能的多少参数，它预计。
an 未知呼叫表示编译器无法确定可能调用的函数。
已知的调用是完全饱和如果被调用的函数正在获取它期望的所有参数，并且它直接进入代码。如果函数是越来越少的参数比，预计，功能仅在闭合

例如分配部分应用和呼叫的结果，如果我写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呼叫都未知。

成熟编译器所做的主要事情是优化已知调用。在上面的分类中，这个策略主要落在＃2之下。

如果所有调用网站的功能是已知的，一个好的编译器会创建一个专用的调用约定只是该功能，例如，传递参数在恰到好处的寄存器来使事情成功很好。
如果只是部分而不是一个函数的所有调用位置是已知的，编译器可以决定是否值得以创建知调用，要么是内联的专用调用约定或将使用一个特殊的名字只有编译器才知道。在源代码中导出的函数将使用标准调用约定，其实现通常是对专用版本进行优化尾部调用的薄层。
如果一个已知的调用没有完全饱和，编译器会生成代码来在调用者中分配闭包。

封闭的表示（或是否一流功能由一些其它技术如λ提升或去官能化处理）在很大程度上是正交的已知的处理VS未知呼叫。（可能值得一提的是MLton使用的另一种方法：它是一个全程序编译器;它可以看到所有的源代码;它使用我已经忘记的一种技术将所有函数减少到第一顺序。有仍然未知来电，因为在高阶语言一般控制流分析是顽固性）

关于你的最后问题：

我觉得这ISS这只是“如何编译一流功能”这个混乱问题的一个方面。我从来没有听说过这个问题的特殊名称。
是的，还有其他方法。我画了一个，并提到另一个。
我不确定是否有任何关于权衡的伟大而广泛的研究，但我知道的最好的一个，我推荐得非常好，是Simon Marlow和Simon Peyton Jones的Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-Order Languages。本文的许多优点之一是，它解释了为什么函数的类型不是而是会告诉您对该函数的调用是否完全饱和。

要给你编号方案：数字1是于事无补。热门编译器使用与数字2和3相关的混合策略。我从来没有听说过任何类似于数字4的东西;已知和未知调用之间的区别似乎比将顶级函数与函数类型的参数区分开更有用。

来源

2010-02-20 00:56:42

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

回答

相关问题