Lambda-Lifting in Quadratic Time
Olivier Danvy
June 2004 |

## Abstract:
Lambda-lifting is a program transformation that is used in
compilers, partial evaluators, and program transformers. In this article, we
show how to reduce its complexity from cubic time 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
To reduce the
complexity of lambda-lifting, 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 , our algorithm is asympotically optimal.
Available as |

Last modified: 2004-07-02 by webmaster.