Programming Language Compilation
Suggest how you would represent Lambda-expressions in a form suitable for a simple
Lambda-evaluator in which the environment is represented as a linked list of name–
value pairs. [5 marks]
Outline the design of the evaluator, paying particular attention to the treatment of
bound variables, abstractions and applications. [5 marks]
Augment your evaluator to cope with sufficient expression operators, including a
built-in version of the Y operator so that when the evaluator is given the abstract
syntax tree for
Y (λf.λn. n=0 -> 1, n*f(n-1)) 5
it will yield 120. [10 marks]