Relationship between Lambda Hoisting and Fully Lazy Lambda Lifting

Two algorithms have been proposed for transforming functional programs into ones suitable for fully lazy evaluation-Lambda hoisting (Takeichi [7]) and fully lazy lambda lifting (Peyton Jones [4]). These algorithms share similar operations such as floating out local definitions and extracting maximal free occurrences of subexpressions to achieve full laziness, while they look different at first sight. This paper investigates these algorithms in a same framework and shows that the differences lie in the evaluation schemes for the resultant programs. We conclude that the main part of these algorithms may be considered identical by transforming the lambda hoisting rules into those for fully lazy lambda lifting.