Lambda-dropping: transforming recursive equations into programs with block structure Export

@inproceedings{citeulike:276781, abstract = {Lambda-lifting a functional program transforms it into a set of recursive equations. We present the symmetric transformation: lambda-dropping. Lambda-dropping a set of recursive equations restores block structure and lexical scope.For lack of scope, recursive equations must carry around all the parameters that any of their callees might possibly need. Both lambda-lifting and lambda-dropping thus require one to compute a transitive closure over the call graph:\• for lambda-lifting: to establish the Def/Use path of each free variable (these free variables are then added as parameters to each 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 their definition do not need to be passed along in the call path).Without free variables, a program is scope-insensitive. Its blocks are then 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 per se, both in principle and in practice, but our prime application is partial evaluation: except for Malmkj\ær and \Ørb\æk's case study presented at PEPM '95, most polyvariant specializers for procedural programs operate on 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 with dozens of parameters, which most compilers do not handle efficiently. Lambda-dropping in a post-processing phase restores their block structure and lexical scope thereby significantly reducing both the compile time and the run time of residual programs.}, address = {New York, NY, USA}, author = {Danvy, Olivier and Schultz, Ulrik P.}, booktitle = {PEPM '97: Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation}, citeulike-article-id = {276781}, citeulike-linkout-0 = {http://dx.doi.org/10.1145/258993.259007}, doi = {10.1145/258993.259007}, issn = {0362-1340}, keywords = {lambdadropping, partialevaluation, staticanalysis}, month = {December}, number = {12}, pages = {90--106}, posted-at = {2005-08-08 12:24:44}, priority = {2}, publisher = {ACM Press}, title = {Lambda-dropping: transforming recursive equations into programs with block structure}, url = {http://dx.doi.org/10.1145/258993.259007}, volume = {32}, year = {1997} }

TY - CONF ID - citeulike:276781 L3 - citeulike-article-id:276781 N2 - Lambda-lifting a functional program transforms it into a set of recursive equations. We present the symmetric transformation: lambda-dropping. Lambda-dropping a set of recursive equations restores block structure and lexical scope.For lack of scope, recursive equations must carry around all the parameters that any of their callees might possibly need. Both lambda-lifting and lambda-dropping thus require one to compute a transitive closure over the call graph:• for lambda-lifting: to establish the Def/Use path of each free variable (these free variables are then added as parameters to each 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 their definition do not need to be passed along in the call path).Without free variables, a program is scope-insensitive. Its blocks are then 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 per se, both in principle and in practice, but our prime application is partial evaluation: except for Malmkjær and Ørbæk's case study presented at PEPM '95, most polyvariant specializers for procedural programs operate on 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 with dozens of parameters, which most compilers do not handle efficiently. Lambda-dropping in a post-processing phase restores their block structure and lexical scope thereby significantly reducing both the compile time and the run time of residual programs. IS - 12 SN - 0362-1340 AD - New York, NY, USA EP - 106 TI - Lambda-dropping: transforming recursive equations into programs with block structure PB - ACM Press VL - 32 T2 - PEPM '97: Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation SP - 90 KW - lambdadropping KW - partialevaluation KW - staticanalysis AU - Danvy, Olivier AU - Schultz, Ulrik PY - 1997/12// UR - http://dx.doi.org/10.1145/258993.259007 ER -