COMPUTER SCIENCE TRIPOS Part IB – 2015 – Paper 3
Compiler Construction (TGG)
(a) Consider a programming language with nested function declarations that allows
only first-order functions. That is, functions are not treated as values and can
neither be passed as arguments nor returned by functions.
Lambda lifting and static links are two common methods of implementing such
a language using a run-time stack. Describe these methods and discuss their
advantages and disadvantages. [6 marks]
(b) Now suppose we are dealing with a programming language that supports
higher-order functions that can be passed as arguments and returned as results.
Give an example, in ML-like pseudo-code, where the techniques that you have
described in (a) can no longer be used. Justify your answer. [6 marks]
(c) Carefully explain the techniques you might use to compile the example that you
presented in (b). [8 marks]