@article{Danvy_Schultz_1997, title={Lambda-Dropping: Transforming Recursive Equations into Programs with Block Structure}, volume={4}, url={https://tidsskrift.dk/brics/article/view/18785}, DOI={10.7146/brics.v4i6.18785}, abstractNote={<p>Lambda-lifting a functional program transforms it into a set of recursive<br />equations. We present the symmetric transformation: lambda-dropping.<br />Lambda-dropping a set of recursive equations restores block<br />structure and lexical scope.<br />For lack of scope, recursive equations must carry around all the<br />parameters that any of their callees might possibly need. Both lambda-lifting<br />and lambda-dropping thus require one to compute a transitive<br />closure over the call graph:</p><p>- for lambda-lifting: to establish the Def/Use path of each free<br />variable (these free variables are then added as parameters to<br />each of the functions in the call path);</p><p>- for lambda-dropping: to establish the Def/Use path of each parameter<br />(parameters whose use occurs in the same scope as their<br />definition do not need to be passed along in the call path).<br />Without free variables, a program is scope-insensitive. Its blocks are<br />then free to float (for lambda-lifting) or to sink (for lambda-dropping)<br />along the vertices of the scope tree.</p><p><br />We believe lambda-lifting and lambda-dropping are interesting per<br />se, both in principle and in practice, but our prime application is partial<br />evaluation: except for Malmkjær and Ørbæk’s case study presented at<br />PEPM’95, most polyvariant specializers for procedural programs operate<br />on recursive equations. To this end, in a pre-processing phase,<br />they lambda-lift source programs into recursive equations. As a result,<br />residual programs are also expressed as recursive equations, often with<br />dozens of parameters, which most compilers do not handle efficiently.<br />Lambda-dropping in a post-processing phase restores their block structure<br />and lexical scope thereby significantly reducing both the compile<br />time and the run time of residual programs.<br /><br /></p><p> </p>}, number={6}, journal={BRICS Report Series}, author={Danvy, Olivier and Schultz, Ulrik P.}, year={1997}, month={Jan.} }