Lambda lifting is a method to transform functional programs into a form of function without free variables in lazy functional languages. The idea of lambda lifting is to pass free variables via new additional parameters. But the addition of parameters results in the increase of stack access and heap consumption, particularly, in case of recursive function calls. Despite of not applying lambda lifting, the similar overhead can happen in functions which always pass same-valued parameters during recursive calls.
In this thesis, we propose a reverse lambda lifting : lambda lowering. Lambda lowering transforms some parameters into free variables by introducing new let blocks, so that the parameters can be shared during arbitrary recursive calls.
We experiment the effect of lambda lowering with Glasgow Haskell compiler and well-known Hartel's benchmarks. The experiments show the decrease of stack access and heap consumption in many benchmark cases. By examination of benchmarks results, we find the number of subsequent recursive calls somewhat small. The smaller the number of subsequent recursive calls is, the bigger the overhead of let block is. Therefore, the initial overhead can possibly overwhelm the gains of applying lambda lowering.
So, we suggest for programmers to select functions to apply lambda lowering rather than for compilers to do automatically, since the overall effect of transformation might increase the execution cost in some cases.
