Lambda-Lifting in Quadratic Time
Olivier Danvy
August 2003 |

## 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, and we present a
flow-sensitive lambda-lifter that also works in 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
Instead, we partition the call
graph of the source program into strongly connected components, based on the
simple observation that Since a lambda-lifter can output programs of size , we believe that our algorithm is close to optimal.
Available as |

Last modified: 2003-07-19 by webmaster.