2. (a) ------ P = ((pair a) b) => ((Lx.Ly.Lf.((f x) y) a) b) => (Ly.Lf.((f a) y) b) => Lf.((f a) b) (P first) = (Lf.((f a) b) Lx.Ly.x) => ((Lx.Ly.x a) b) => (Ly.a b) => a (P second) = (Lf.((f a) b) Lx.Ly.y) => ((Lx.Ly.y a) b) => (Ly.y b) => b 2. (b) ------ Applicative order is the same as "call by value". To evaluate a function application, we first evaluate the argument expression, and then substitute into the function expression. That is, we replace all occurances of the bound variable in the body of the function expression with the evaluated argument expression. Normal order is the same as "call by name". We substitute into the function expression the unevaluated argument expression. That is, we replace all occurances of the bound variable in the body of the function expression with the unevaluated argument expression. This looks very similar to "macro expansion". Applicative order will tend to be more efficient. If there are multiple occurances of the bound variable in the function expressions body then normal order may ultimately have to evaluate that expression many times, whereas applicative order need do it only once. However, if the expression to be evaluated has a normal form, then normal order will find it, and will terminate. That is, normal form may be reached by normal order. This is not true for applicative order. Therefore, if normal order fails to terminate then so will applicative order. If normal order terminates, this cannot be taken as a guarntee that applicative order will terminate. 2. (c) ------ The above definition of factorial will never terminate. fact 2 = cond (2 = 0) 1 (2 * (fact (2 - 1))) => cond false 1 (2 * (fact 1)) => cond false 1 (2 * (cond (1 = 0) 1 (1 * (fact (1 - 1))))) => cond false 1 (2 * (cond false 1 (1 * (fact 0)))) => cond false 1 (2 * (cond false 1 (1 * (cond (0 = 0) 1 (0 * (fact (0 - 1))))) => cond false 1 (2 * (cond false 1 (1 * (cond true 1 (0 * (fact -1))))) As can be seen we end up generating a call to fact -1 which will not terminate. More generally, what is happening is that in a call to cond we are evaluating the arguments c, e1, and e2 prior to entering the function. That is, cond is evaluated using "applicative order" (call by value). Even more generally, all functions that we define in ml are evaluated using applicative order. But we can write a terminating recursive definition of factorial using the "if then else" construct. That is, given "if C the E1 else E2" expression E1 is evaluated if (and only if) C is true, and E2 is evaluated if (and only if) C is false. Therefore, we have a mix, between applicative and normal order evaluation. The if-then-else, orelse, andalso constructs must be using normal order, or somethin similar. That "something similar" may be delayed evaluation via "abstraction" (as in the lambda expression for pair above), sometimes called "thunk".