Lambda-Lifting in Quadratic Time
Lambda-Lifting in Quadratic Time
复制标题
二次时间内的 Lambda 提升
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
U. Schultz
中科院分区：
文献类型：
--
作者：
O. Danvy;U. Schultz
Lambda提升是一种在编译器和部分求值器中使用的程序转换，并且在立方时间内操作。在本文中，我们将展示如何将这种复杂性降低到二次时间。Lambda提升将块结构的程序转换为一组递归方程，源程序中的每个局部函数都对应一个递归方程。每个方程都带有额外的参数，以说明相应的局部函数及其所有被调用者的自由变量。这是搜索这些额外的参数，产生了三次因子在传统的公式化的提升，这是由于约翰松。这种搜索是通过一个传递闭包来进行的，相反，我们将源程序的调用图划分为强连接的组件，基于一个简单的观察，即每个组件中的所有函数都需要相同的额外参数，因此不需要传递闭包。因此，我们通过将每个强连接分量而不是每个函数作为一个单元来简化对额外参数的搜索，从而将Adjuda-lifting的时间复杂度从O（n3 log n）降低到O（n2 log n），其中n是程序的大小。由于Adjuda-lifting可以输出O（n2）大小的程序，我们相信我们的算法接近最优。
Lambda-lifting is a program transformation used in compilers and in partial evaluators and that operates in cubic time. In this article, we show how to reduce this complexity to quadratic time.Lambda-lifting transforms a block-structured program into a set of recursive equations, one for each local function in the source program. Each equation carries extra parameters to account for the free variables of the corresponding local function and of all its callees. It is the search for these extra parameters that yields the cubic factor in the traditional formulation of lambda-lifting, which is due to Johnsson. This search is carried out by a transitive closure.Instead, we partition the call graph of the source program into strongly connected components, based on the simple observation that all functions in each component need the same extra parameters and thus a transitive closure is not needed. We therefore simplify the search for extra parameters by treating each strongly connected component instead of each function as a unit, thereby reducing the time complexity of lambda-lifting from O(n3 log n) to O(n2 log n), where n is the size of the program.Since a lambda-lifter can output programs of size O(n2), we believe that our algorithm is close to optimal.