Since 2014
Lambda-Dropping: Transforming Recursive Equations into Programs with Block Structure
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Lambda-Dropping: Transforming Recursive Equations into Programs with Block Structure
|
|
| Creator |
Danvy, Olivier
Schultz, Ulrik P. |
|
| Description |
Lambda-lifting a functional program transforms it into a set of recursiveequations. We present the symmetric transformation: lambda-dropping.Lambda-dropping a set of recursive equations restores blockstructure and lexical scope.For lack of scope, recursive equations must carry around all theparameters that any of their callees might possibly need. Both lambda-liftingand lambda-dropping thus require one to compute a transitiveclosure over the call graph:- for lambda-lifting: to establish the Def/Use path of each freevariable (these free variables are then added as parameters toeach of the functions in the call path);- for lambda-dropping: to establish the Def/Use path of each parameter(parameters whose use occurs in the same scope as theirdefinition do not need to be passed along in the call path).Without free variables, a program is scope-insensitive. Its blocks arethen free to float (for lambda-lifting) or to sink (for lambda-dropping)along the vertices of the scope tree.We believe lambda-lifting and lambda-dropping are interesting perse, both in principle and in practice, but our prime application is partialevaluation: except for Malmkjær and Ørbæk's case study presented atPEPM'95, most polyvariant specializers for procedural programs operateon recursive equations. To this end, in a pre-processing phase,they lambda-lift source programs into recursive equations. As a result,residual programs are also expressed as recursive equations, often withdozens of parameters, which most compilers do not handle efficiently.Lambda-dropping in a post-processing phase restores their block structureand lexical scope thereby significantly reducing both the compiletime and the run time of residual programs.
|
|
| Publisher |
Aarhus University
|
|
| Date |
1997-01-06
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/18785
10.7146/brics.v4i6.18785 |
|
| Source |
BRICS Report Series; No 6 (1997): RS-06 Lambda-Dropping: Transforming Recursive Equations into Programs with Block Structure
BRICS Report Series; Nr. 6 (1997): RS-06 Lambda-Dropping: Transforming Recursive Equations into Programs with Block Structure 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/18785/16432
|
|