^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} Department of Computer Science, Science and Technology, Aarhus University^{3} Department of Computer Science, Science and Technology, Aarhus University

DOI:

10.1007/3-540-45788-7_8

Abstract:

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 cl osure 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(n 3 log n)toO(n2 log n), where n is the size of the program. Since a lambda-lifter can output programs of size O(n 2), we believe that our algorithm is close to optimal.

ISBN:

9783540442332

Type:

Conference paper

Language:

English

Published in:

Functional and Logic Programming: 6th International Symposium, Flops 2002 Aizu, Japan, September 15–17, 2002 Proceedings, 2002, p. 134-151