3. (a) Given the following lambda expressions:
TRUE = Lx.Ly.x
FALSE = Lx.Ly.y
IF = Lc.Le1.Le2.((c e1) e2)
NOT = Lx.(((IF x) FALSE) TRUE)
OR = Lx.Ly.(((IF x) TRUE) y)
and using normal order beta-reduction ( => ), show that
(i) (NOT TRUE) reduces to FALSE
(ii) ((OR FALSE) FALSE) reduces to FALSE
(6 marks)
(b) Equivalence (eq) is defined by the following truth table
X Y X eq Y
----- ----- --------
false false true
false true false
true false false
true true true
Define the body of the lambda function
EQ = Lx.Ly.
such that it realises the equivalence relation above.
(12 marks)
(c) There are two forms of beta-reduction, namely applicative
order (->), and normal order (=>). Describe both of these,
making clear their relatve advantages and disadvantages.
(4 marks)
(d) Generally, ML uses applicative order. However, there are a
number of notable exceptions, such as the lazy evaluation of the
functions orelse and andalso. Explain why this is so.
(3 marks)