1.(a)
Theoretical reasons. Functional languages such as ml have sound
mathematical basis, ie the lambda calculus. 

Practical reasons. Generally, when being used in their strict sense 
(ie without assignment statements) we have referential transparency.
This means that we can evaluate arguments in any order. This gives us
the opportunity to exploit parallel or distributed hardware. 

Also, when used strictly, we can prove programs to be correct via
induction.


1.(b)
The first function mult takes as arguments a pair (x,y). More
generally, we might think of a function that takes n arguments
(x1,x2,...,xn) as taking a single argument that is an n-tuple. The
function prod again can be considered as taking a single argument.
When prod is given that single argument a new function is delivered
as a result, which can then be applied to the second argument. That
is, we apply the function to an argument and this delivers as a
result another function, and so on. This has been referred to as
"Curried" or "partially applicable" functions, and is a powerful
feature of ml.

1.(c)

      fun convert 0 = [0]
         |convert 1 = [1]
         |convert n = if (n mod 2) = 0
                      then 0::(convert (n div 2))
                      else 1::(convert (n div 2));


1.(d) 

    fun add_digits (0,0,0) = (0,0)
       |add_digits (1,0,0) = (1,0)
       |add_digits (0,1,0) = (1,0)
       |add_digits (1,1,0) = (0,1)
       |add_digits (0,0,1) = (1,0)
       |add_digits (1,0,1) = (0,1)
       |add_digits (0,1,1) = (0,1)
       |add_digits (1,1,1) = (1,1)

    I can now apply this to a list of arguments


     fun add_bin 0 [] y = y
        |add_bin 0 x [] = x
        |add_bin 1 [] y = add 0 [1] y
        |add_bin 1 x [] = add 0 x [1]
        |add_bin carry (x::xs) (y::ys) = let val (r,c) = add_bin (carry,x,y)
                                         in r::(add c xs ys) end;
2.(a)

     fun add_new e S = if not (member e S)
                       then e::S
                       else S;

    fun delete e [] = []
       |delete e (h::t) = if e=h
                          then t
                          else h::(delete e t);

    fun intersection [] S2 = []
       |intersection S1 [] = []
       |intersection (h::t) S2 = if member h S2
                                 then h::(union t S2)
                                 else (union t S2);

    fun subset [] S2 = true
       |subset (h::t) S2 = (member h S2) andalso (subset t S2);

    fun card [] = 0
       |card (h::t) = 1 + (card t);


2.(b)
  I can write a function called (for example) pair, that given two
arguments produces a pair. 

    fun pair x y = (x,y);

I can then partially apply it, giving it one argument, such that it always 
produces a pair with the same first element. For example I can
produce a function pair_with.

   val pair_with = pair e;

I can then map this over the set T, giving me all pairs from T that
have e as their first element:

   map pair_with T;

I need to do this for all elements in S. Therefore ...

   fun cartprod [] T = []
      |cartprod (x::xs) T = 
       (map (pair x) T) @ (cartprod xs T);


2.(c)
By polymorphic we mean that the function is defined for as yet
unspecified argument types. For example the functions above (in (a))
could be used over sets of integers, reals, colours, animals, etc. 
However, the functions in (a) must have arguments that support tests
for equality "=" otherwise they will not work. Therefore we could not
compute the union of two sets of functions. The function cartprod
could be used in such a scenario, allowing us to compute Cartesian
product of sets of functions, since it does not depend on tests of
equality.
3.(a)
   (NOT TRUE)
   == (Lx.(((IF x) FALSE) TRUE) TRUE)
   => (((IF TRUE) FALSE) TRUE)
   => (((Lc.Le1.Le2.((c e1) e2) TRUE) FALSE) TRUE)
   => ((Le1.Le2.((TRUE e1) e2) FALSE) TRUE)
   => (Le2.((TRUE FALSE e2) TRUE)
   => ((TRUE FALSE) TRUE)
   == ((Lx.Ly.x FALSE TRUE)
   => (Ly.FALSE TRUE)
   => FALSE


   ((OR FALSE) FALSE)
   == ((Lx.Ly.(((IF x) TRUE) y) FALSE) FALSE)
   => (((IF FALSE) TRUE) FALSE)
   == (((Lc.Lx.Ly.((c x) y) FALSE) TRUE) FALSE)
   => ((Lx.Ly.((FALSE x) y) FALSE) TRUE)
   => (Ly.((FALSE TRUE) y) FALSE)
   => ((FALSE TRUE) FALSE)
   == ((Lx.Ly.y TRUE) FALSE)
   => (Ly.y FALSE)
   => FALSE

3.(b)
  X eq Y is true when X and Y are both true, or when X and Y are both false.
  Therefore we have:

     ((OR A) B)

  where A is ((AND x) y)
        B is ((AND (NOT x)) (NOT y))

  We must then define AND, as follows:
   
        AND = Lx.Ly.(((IF x) y) FALSE)

  Altogether we get

        EQ = Lx.Ly.((OR ((AND x) y) ((AND (NOT x)) (NOT y))

3.(c)
Applicative order: all occurrences of the function expression's bound
variables in the function's body is replaced by the VALUE of the
argument expression.

Normal order: all occurrences of the function expression's bound
variable are replaced with the UNEVALUATED argument expression.

In applicative order we may gain an efficiency in that we may only
need to evaluate an argument once, and then substitute it in many
times, whereas in normal order we may then evaluate an argument
expression many times. However, it can be shown that if a function
application does reduce to some minimal form it is guaranteed to do so under
normal order reduction, but applicative order might never reach this
minimal form. The minimal form is called normal form.

3.(d)
If orelse and andalso used applicative order both operands would be
evaluated before the operator was applied. For example X andalso Y
would require that X be evaluated, then Y evaluated, then andalso
applied. Clearly, if X evaluated to FALSE then we need not evaluate
Y. In the orelse case, X orelse Y, we need only evaluate Y when X
evaluates to FALSE. Therefore lazy evaluation gives us a possible efficiency.
However ... it is not only an efficiency, it is also an necessity.
We can consider IF x THEN y as being equivalent to (not x) andalso y
If we used applicative order (call by value) we would always evaluate
y, and we do not want to do this.