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)