The Compiler Construction Programming answers should be written in some notation approximating SML or OCaml. (a) Describe what is meant by tail recursion. [4 marks] (b) Eliminate tail recursion from foldl given below. Explain your answer. (* foldl : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a *) let rec foldl f accu l = match l with [] -> accu | a::l -> foldl f (f accu a) l [8 marks] (c) Eliminate tail recursion from the following mutually tail-recursive functions. Explain your answer. let rec is_even n = if n = 0 then true else is_odd (n - 1) and is_odd n = if n = 0 then false else is_even(n - 1) [8 marks] 4 CST.2016.3.5 4 Compiler Construction Consider writing a compiler for a simple language of expressions given by the following grammar, e ::= n (integer) | ? (read integer input from user) | e + e (addition) | e ' e (subtraction) | e e (multiplication) | (e, e) (pair) | fst e (first projection) | snd e (second projection) (a) Describe the tasks that should be carried in implementing a front end for this language and any difficulties that might be encountered. [5 marks] (b) 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. [5 marks] 5 (TURN OVER) CST.2016.3.6 5 Concepts in Programming Languages (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 v2; ArrayList w = new ArrayList<>(10); Explain any differences in behaviour between assignments v1 = w and v2 = w and also between method calls v1.set(4,n) and v2.set(4,n). [4 marks] 6 CST.2016.3.7 6 Further Java (a) Describe the operation of wait() and notifyAll(). Ensure that your answer explains when locks are acquired and released. [5 marks] (b) A future is a mechanism to store the eventual result of a computation done in another thread. The idea is that the computation is run asynchronously and the calling thread only blocks if it tries to use a result that hasn't been computed yet. An example program using a future is shown below. Future f = new Future() { @Override public String execute() { // ...long running computation... return data; }; // ... String result = f.get(); // blocks if execute() unfinished Use wait() and notifyAll() to provide an implementation of the Future class that would work with the example program above. [10 marks] (c) Give one potential advantage and one potential disadvantage of using notify() instead of notifyAll(). [2 marks] (d) Would it have been beneficial to use notify() instead of notifyAll() in your implementation? Justify your answer. [3 marks] 7 (TURN OVER) CST.2016.3.8 7 Prolog In this question you should ensure that your predicates behave appropriately with backtracking and avoid over-use of cut. You should provide an implementation of any library predicates used. You may not make use of extra-logical built-in predicates such as findAll. Minor syntactic errors will not be penalised. (a) Rewrite chooseAll without using not and cut (!). [10 marks] chooseAll(N,L,Res) :- chooseAll(N,L,[],Res). chooseAll(N,L,Seen,Res) :- choose(N,L,R), not(member(R,Seen)), !, chooseAll(N,L,[R|Seen],Res). chooseAll(,,Res,Res). (e) What is Last Call Optimisation and why is it beneficial? [3 marks] (f ) Rewrite pos to enable Last Call Optimisation. [2 marks] pos([],[]). pos([H|T],[H|R]) :- H >= 0, pos(T,R). pos([H|T],R) :- H < 0, pos(T,R). 8 CST.2016.3.9 8 Software Engineering Discuss the contribution and the relative value of the following aspects of the modern development environment. Illustrate with examples from your group project, or from experience you gained working for a commercial software developer, or both. In each case, would you discard this feature if your employer let you, or insist on retaining it (even covertly) should your employer not value it? Explain your reasons. (a) Dividing a project into short development episodes or sprints. (b) Project progress visualisation tools such as PERT and GANTT charts. (c) Automated regression testing tools. (d) Source code management tools. (e) Scrumming Example: Our current Trip of Goats (7): Jimi (4.7 years, female, coal) {alarm} Jaxx (5.6 years, female, bone) {armchair} Jono (6.5 years, female, gray) {attorney} Jden (0.4 years, male, snow) {accordion} Joey (4.7 years, female, coal) {alarm} Jedi (5.6 years, female, bone) {armchair} Judd (4.0 years, female, mint) {bacon} ***************************************** On Goat Date: 45944.9... Science News: Goat Cloned! Welcome, copy of Joey! New name: Jade Our current Trip of Goats (8): Jimi (4.8 years, female, coal) {alarm} Jaxx (5.7 years, female, bone) {armchair} Jono (6.6 years, female, gray) {attorney} Jden (0.5 years, male, snow) {accordion} Joey (4.8 years, female, coal) {alarm} Jedi (5.7 years, female, bone) {armchair} Judd (4.1 years, female, mint) {bacon} Jade (4.8 years, female, coal) {alarm} ***************************************** On Goat Date: 45945.0... The farmer must hold a funeral for Joey...RIP. Our current Trip of Goats (7): Jimi (4.9 years, female, coal) {alarm} Jaxx (5.8 years, female, bone) {armchair} Jono (6.7 years, female, gray) {attorney} Jden (0.6 years, male, snow) {accordion} Jedi (5.8 years, female, bone) {armchair} Judd (4.2 years, female, mint) {bacon} Jade (4.9 years, female, coal) {alarm} Here's how my code was laid out in my solution: Load name data into name vector Load color data into color vector Load food data into food vector Populate the initial trip with 3 goats Simulation engine running 10 times: Generate random choice 1-6 (but if the trip size is 0-2, only choose the option for the farmer to add to the trip) Switch statement to process the choices Update goat ages Update the goatdate time Sample OutputThe farmer added a goat to the trip! Welcome Jimi! The farmer added a goat to the trip! Welcome Jace! The farmer added a goat to the trip! Welcome Jael