Article
Improved Graph-Based Lambda Lifting
International Conference on Software Engineering Research and Practice & Conference on Programming Languages and Compilers, SERP 2006
(2006)
Abstract
Lambda lifting is a technique for transforming a program with local function definitions into a program consisting only of global function definitions. The best known lambda lifting algorithm computes the minimal set of extraneous parameters needed by each function in O(n 3 ) steps by solving a system of set equations which are recursive if the functions in the program are mutually recursive. Mutually recursive functions give rise to strongly connected components in the call graph of a program. Danvy and Schultz observed that all functions in a strongly connected component can be given the same set of free variables as extraneous parameters. Based on this observation, they developed an O(n 2 ) graph-based lambda lifting algorithm. This article illustrates how Danvy’s and Schultz’s algorithm is an approximation of Johnsson’s algorithm for a certain class of programs and describes an O(n 3 ) graph-based lambda lifting algorithm that yields the same results as Johnsson’s algorithm.
Disciplines
Publication Date
June, 2006
Citation Information
Marco Morazan and Barbara Mucha. "Improved Graph-Based Lambda Lifting" International Conference on Software Engineering Research and Practice & Conference on Programming Languages and Compilers, SERP 2006 (2006) Available at: http://works.bepress.com/marco-morazan/10/