Difficulty: ***
I’d contemplated setting this problem previously, but shied away from it, as it’s hard to understand why you need to do lambda lilfting in a compiler when you’ve not formally studied compilers and have not been exposed to the concepts of free and bound variables, lambda calculus etc. However, given how well students had coped with previous exercises in the language processing space I decided to try it out. I had originally planned to get the students to write an interepreter for the language, but that requires implementing partial application and that just got too messy.
The students were given a short refresher document on local functions, scope and partial application the day before the test, as these are key to understanding the transformation. I think that helped a lot, but students still found the test hard. Seven out of the 226 students scored full marks, which was amazing, but the average mark was around 66% (below the long-run average) and quite a few students didn’t get to Part III at all.
The specification here is exactly as set, with the exception of a couple of cosmetic changes to the wording.
Note: The problem of determining the optimal set of parameters to lifted functions is hard, so I opted for the dumb solution: if a function might need a free variable, then add it regardless before lifting it out. You can do better (see the references below).
Specification
Template File
Types module
Examples module
More Information
The original paper on lambda lifting [1] details the idea and provides an $O(n^3)$ equation-based algorithm for finding the optimal set of parameters in lifted functions (finding the optimal set is not an issue in this exercise, as we adopt the naive approach). An $O(n^2)$ algorithm was later developed exploiting dominator trees [2].
[1] T. Johnsson (1985) “Lambda lifting: Transforming programs to recursive equations”,
proc. Functional Programming Languages and Computer Architecture, Nancy, 1985, pp. 190–203.
[2] M.T. Morazan & U.P. Schultz, “Optimal Lambda Lifting in Quadratic Time”, proc. 19th International Workshop on the Impementation and Application of Functional Languages (IFL), 2007, Freiburg, Germany, (Revised Selected Papers) pp. 37–56.