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

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. 保留顶级函数的"自然"签名,但要求通过闭包完成所有高阶函数参数的处理.已关闭函数的"额外"闭包调用包装器trampoline函数来丢弃未使用的env参数.这似乎比选项3更优雅,但更难以有效实施.编译器生成大量的calling-convention-indepedent包装器,或者使用少量的call-convention-sensitive thunks ...

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

无论如何,问题:

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

Answer 1

这是一个非常深刻的问题,有很多分歧,我不想在这里写一篇学术文章.我将抓住表面,并指出您在其他地方的更多信息.我的回应基于Glorious Glasgow Haskell编译器和新泽西标准ML的个人经验,以及关于这些系统的学术论文.

雄心勃勃的编译器的主要区别在于已知调用和未知调用之间的区别.对于具有高阶函数的语言,次要但仍然重要的区别在于呼叫是否完全饱和(我们只能在已知的呼叫站点处决定).

• 一个众所周知的呼叫是指在通话网站,编译器知道到底是什么功能被称为有多少参数的期望.

• 一个未知的呼叫意味着编译器无法找出可以被称为什么功能.

• 如果被调用的函数正在获得它期望的所有参数,则已知调用完全饱和,并且它将直接进入代码.如果函数获得的参数少于预期,则部分应用该函数,并且仅在分配闭包时产生调用

例如,如果我编写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.

• 如果函数的所有调用站点都是已知的,那么一个好的编译器将为该函数创建一个专用的调用约定,例如,在正确的寄存器中传递参数以使事情很好地运行.

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

• 如果已知调用未完全饱和,则编译器只会生成代码以在调用者中分配闭包.

闭包的表示(或者是否通过一些其他技术(例如lambda提升或去泛化)处理第一类函数)与已知与未知调用的处理大致正交.

(这可能是值得一提的另一种方法,通过使用MLton:它是一个整体,程序编译器,它会看到所有的源代码;它使用我忘了一个技术减少到一阶的所有功能,还有仍然未知调用是因为高阶语言中的一般控制流分析是难以处理的.)

关于你的最后问题:

• 我认为这个问题只是凌乱问题的一个方面,称为"如何编译一流函数".我从未听过这个问题的特殊名称.

• 是的,还有其他方法.我勾画了一个并提到了另一个.

• 我不知道是否有权衡上任何伟大的,广泛的研究,但最好的一个,我知道的,我建议非常高,是制作咖喱快:推/输入与评估和演示/申请高阶语言通过Simon Marlow和Simon Peyton Jones.本文的许多好处之一是它解释了为什么函数的类型不能告诉你对该函数的调用是否完全饱和.

要包装您编号的替代方案:编号1是不可启动的.流行的编译器使用与数字2和3相关的混合策略.我从来没有听说过类似4号的东西; 已知和未知调用之间的区别似乎比将顶级函数与函数类型的参数区分开来更有用.