Three alternative representations for non-negative integers, n, are:
• Peano: values have the form S(... S(Z) ...), applying S n times to Z where
S and Z are constructors or constants of some data type.
• Binary: values are of type bool list with 0 being represented as the empty
list, and the least-significant bit being stored in the head of the list.
• Church: values have the form fn f => fn x => f(... f(x) ...), applying
f n times to x
(a) Write ML functions for each of these data types which take the representation
of an integer n as argument and return n as an ML int. [6 marks]
(b) Write ML functions for each of these data types which take representations of
integers m and n and return the representation of m + n. Your answers must
not use any value or operation on type int or real. [Hint: you might it useful
to write a function majority: bool*bool*bool -> bool (which returns true
when two or more of its arguments are true) and to note that the ML inequality
operator '<>' acts as exclusive-or on bool.] [10 marks]
(c) Letting two and three respectively be the Church representations of integers 2
and 3, indicate whether each of the following ML expressions give a Church
representation of some integer and, if so what integer is represented, and if not
giving a one-line reason.
(i) two three
(ii) three two
(iii) two ◦ three
(iv) three ◦ two
 

 

Suppose that the target virtual machine is stack-oriented and that the stack
elements are integer values, and addresses can be stored as integers. Explain
which other features are required in such a virtual machine. Invent a simple
language of instructions for such a machine and show how it would be used to
implement each of the expressions. [10 marks]
(c) Suppose that the following rules are proposed as possible optimizations to be
implemented in your compiler.
expression simplifies to expression
(fst e, snd e) → e
fst (e1, e2) → e1
snd (e1, e2) → e2
Describe how you could implement these rules so that the simplifications are
made only when the program's semantics is correctly preserved. [

(a) Explain what is meant by a monad in a programming language, giving the two
fundamental operations of a monad along with their types. [3 marks]
(b) Consider the use of a monad for input-output. For the purposes of this question,
take the IO monad as including two operations readint and writeint which
respectively read integers from stdin and write integers to stdout. Give the types
of these operators. [2 marks]
(c) Assume MLreadint and MLwriteint are primitives with side effects for inputoutput and consider the ML expression add1 of type int:
let val x = MLreadint() in MLwriteint(x+1); x end
(i) Give an equivalent expression which uses the IO monad instead of
side-effects, and state its type. [3 marks]
(ii) Give a function run2diff which can be applied to your answer to
part (c)(i). When so applied it should give a value in the IO monad which
corresponds to ML code that runs add1 twice and returns the difference
between the values read. [4 marks]
(d) State what happens when attempting to compile and execute the following Java
fragment (explaining the origin of any error messages or exceptions which might
arise).
Object n = new Integer(42), o = new String("Whoops");
Object [] v;
Integer [] w = new Integer[10];
v = w;
v[4] = n;
v[5] = o; [4 marks]
(e) Consider the Java code:
Object n = new Integer(42);
ArrayList v1;
ArrayList