2. (a) You are given the following lambda expressions:
pair = Lx.Ly.Lf.((f x) y)
first = Lx.Ly.x
second = Lx.Ly.y
Evaluate the following function applications, showing
each reduction step (=>) in your evaluations.
(i) P = ((pair a ) b)
(ii) (P first)
(iii) (P second)
(10 marks)
(b) There are two approaches to evaluating function applications,
namely "applicative order" (->) and "normal order" (=>). Explain
what these approaches mean and discuss the advantages and
disadvantages of each approach.
(8 marks)
(c) In ML we might define a replacement for the "if then else"
construct as follows:
fun cond c e1 e2 = if c then e1 else e2;
We might now attempt to define the factorial function in terms
of the function cond as follows:
fun fact n = cond (n = 0) 1 (n * fact(n-1));
Show that the above function does not work, and explain what
this tells us about ML in general, and about the "if then else"
construct in particular.
(7 marks)