answer the question clearly

Describe and compare the call-by-value, call-by-name, and call-by-need evaluation strategies for functional programming languages. The ML function butlast removes the last element from a non-empty list: exception Butlast; fun butlast [] = raise Butlast | butlast [ ] = [] | butlast (x::xs) = x::(butlast xs); Show how the evaluation of butlast [[1,2],[],[3],[4,5]] proceeds in ML. Write an iterative version of butlast (i.e. one in which the recursive function calls are tail recursive). You may assume the existence of the append (@) function. State with justification the time complexity of your function. An ML data type of lazy lists can be defined by: datatype 'a lazy list = Nil | Cons of unit -> 'a * 'a lazy list; An 'infinite' list of increasing integers can be generated by the function infinite below: fun infinite n = Cons (fn () => (n, infinite(n+1))); Write a version of butlast for lazy lists which terminates when applied to an infinite lazy list such as infinite(0). Can an iterative version of this function be written that still terminates on infinite lazy lists? Explain your reasoning. [20 marks] ) What does the ML function map do? Give an example, first coded without map and then with it, to illustrate how it can lead to more compact or comprehensible code. [3 marks] (b) Functions foldl and foldr might be defined as fun foldl f (e, []) = e | foldl f (e, x::xs) = foldl f (f(e,x), xs); fun foldr f ([], e) = e | foldr f (x::xs , e) = f(x, foldr f (xs,e)); Explain what these two functions do and why they may be useful. [4 marks] (c) Here is a typical use of map: fun mangle n = (n-2)*(n+7); fun manglelist x = map mangle x; Show how to express manglelist using one of the "fold" functions rather than map.

(a) List two differences between the programming languages FORTRAN and Pascal. [4 marks] (b) List two differences between the programming languages SIMULA and Smalltalk. [4 marks] (c) Explain what is understood by type checking and by type inference in the context of programming languages. Compare the two approaches, presenting their advantages and disadvantages. [4 marks] (d) Give an example in the SML Modules language of a signature and of a structure. State whether or not the structure matches the signature, explaining your answer. [4 marks] (e) The programming language Scala introduced case classes. Explain why they are useful in programming, giving code samples.

(a) Various languages provide a built-in 'eval' operator which evaluates an expression passed as an argument. Discuss the extent to which this: (i) fits with existing language features, naming languages or classes of languages for which it is easy or hard to implement; (ii) easily deals with variable scoping; (iii) is a security risk. [4 marks] (b) (i) Explain and justify what goes wrong when the following code is given to a Standard ML system: fun id x = x; val fnlist = ref [id]; fnlist := (fn x=>x+1) :: !fnlist; fnlist := Math.sqrt :: !fnlist; print (hd(!fnlist)(1)) (ii) Explain, giving an example, a related problem involving polymorphic exceptions. [5 marks] (c) (i) Explain the concept of a "value type" in an object-oriented language, including which, if any, primitive and non-primitive types in Java can be seen as value types. (ii) Discuss to what extent a programmer can use final to create value types in Java, and whether this implementation gives the expected space and time usage. [Hint: You may find it useful to discuss arrays of complex numbers.] [5 marks] (d) An implementation of finite sets of natural numbers in Standard ML uses int list as its representation. However, certain client code has been found to be buggy, because it misuses :: to add elements (creating duplicates) and length to obtain the number of elements (miscounting duplicates). (i) Explain how ML modules might be helpful for addressing such bugs. (ii) Use the ML modules language to create a type natset which uses int list internally but only exposes operations (a) to create an empty set, (b) to (functionally) insert one (non-negative) element into a set, (c) to sum the elements in a set, (d) to count the number of elements in a set. No other operation may create or manipulate an natset value(a) Give an overview of the FORTRAN execution model (or abstract machine) and comment on its merits and drawbacks from the viewpoints of programming, compilation, execution, etc. [5 marks] (b) What is garbage collection in the context of programming languages? Comment on its merits/drawbacks and explain the contexts in which it arises, giving examples. [5 marks] (c) Recall that Algol has a primitive static type system. In particular, in Algol 60, the type of a procedure parameter does not include the types of its parameters. Thus, for instance, in the Algol 60 code procedure P( procedure F ) begin F(true) end ; the types of the parameters of the procedure parameter F are not specified. Explain why this piece of code is statically type correct. Explain also why a call P(Q) may produce a run-time type error, and exemplify your answer by exhibiting a declaration for Q with this effect. Why does this problem not arise in SML? [5 marks] (d) Give an implementation of the abstract data type of stacks using the SML module system.(a) Write a LISP program for detecting whether a LISP interpreter treats the language as being dynamically scoped (as was the case in historical LISP) or as being statically scoped (as is the case in modern LISP). You may use pseudo-code and should explain your answer in detail. [4 marks] (b) You manage two junior programmers and overhear the following conversation: A: "I don't know why anyone needs a language other than Java, it provides clean thread-based parallel programming." B: "Maybe, but I write my parallel programs in a functional programming language because they are then embarrassingly parallel." Discuss the correctness of these statements and the extent to which they cover the range of languages for parallel programming. [6 marks] (c) Explain why the SML interpreter accepts the declarations datatype 'a FBtree = node of 'a * 'a FBtree list; fun dfs P (t: 'a FBtree) = let exception Ok of 'a; fun auxdfs( node(n,F) ) = if P n then raise Ok n else foldl (fn(t,_) => auxdfs t) NONE F; in auxdfs t handle Ok n => SOME n end; while it does not accept the declaration exception Ok of 'a; [4 marks] (d) Consider the declarations structure Z = struct type t = int; val z = 0 end; structure A = Z : sig type t ; val z: t end; structure B = Z :> sig type t = int ; val z: t end; structure C = Z :> sig type t ; val z: t end; in the SML Modules language. Explain the behaviour of the SML interpreter on inputting each of the expressions Z.z = A.z; Z.z = B.z; Z.z = C.z;(a) Write a procedure and a call to it in block-structured pseudocode such that the execution of the procedure under pass-by-reference and under pass-by-value/result yields different outcomes. Justify your answer. [7 marks] (b) Explain the meaning of static (i.e. compile-time) and dynamic (i.e. run-time) type checking. Compare the advantages and disadvantages of these two approaches to type checking from the point of view of the language designer, the language implementer, and the programmer. [6 marks] (c) Explain how objects can be simulated in SML, giving an example. Does it follow that SML, together with its module system, is an object-oriented programming language? Why?define a function mkarr(m,n) of type (int*int)->A that will return a value representing a rectangular array of n + 1 rows each of which are of length m + 1 in which each cell is initialised to zero [5 marks] Paths originating from the bottom leftmost cell (which will be referred to by the variable root) are represented by values of the type dir list where dir is declared as follows: datatype dir = Right | Up; Finally define a function inc path cells of type A->A list->unit that will increment the integers in all the cells that lie on a specified path within a given collection of cells. For instance after root had been set up as above, the two calls 4 CST.94.1.5 inc path cells root [Right, Up, Right]; inc path cells root [Right, Right, Right]; would leave root representing the following arrangement 1 1 You may assume that the path does not try to reach cells outside the given arrangement.

In this question you should ensure that your predicates behave appropriately with backtracking. You may not make use of extra-logical built-in predicates such as findAll. Use of the cut operator is permitted unless specified otherwise. You may ignore the possibility of overflow or division by zero. (a) A term can either be an atom, variable or a compound term. Define each of these. [3 marks] (b) Euclid's algorithm for computing the greatest common divisor of two integers can be implemented in ML as: fun gcd(a,0) = a | gcd(a,b) = gcd(b, a mod b); Provide an implementation in Prolog without using the cut operator. [4 marks] (c) We can represent fractions using the compound term div/2. For example div(1,3) represents 1 3 . Implement a predicate simplify which transforms a fraction into its smallest exact representation. For example, simplify(div(8,4),B) should unify B with 2, and simplify(div(4,8),A) should unify A with div(1,2). Your predicate should avoid unnecessary computation. [5 marks] (d) We can also represent arithmetic expressions involving addition, subtraction, multiplication and division. For example, the expression 3 5 21 + 4 is represented as add(mul(3,div(5,sub(2,1))),4). Implement a predicate reduce which reduces an arithmetic expression to its smallest exact representation e.g. reduce(add(div(1,2),div(1,4)),A) should unify A with div(3,4)

Consider the following claim: "The cross-product trick can be used as a plug-in substitution for the comparison operation between two arguments that gives a three-way result (namely <, > or =). Therefore, given an arbitrary set of 2D vectors all starting from the origin, I can sort them in order of increasing polar angle, from 0 to 2, without computing any angles, merely by applying a standard sort algorithm with the comparison operation replaced by the crossproduct trick". (i) Explain the "cross-product trick". [3 marks] (ii) Prove the correctness of the above claim or refute it with a clearly explained graphical or numerical counterexample. [7 marks] (c) Traditionally, Jarvis's march handles the left side and the right side of the hull separately. Clearly explain why a single pass would not work as desired and then describe a variant implementation to handle the problem in one pass, highlighting its advantages and disadvantages. [Hint: see part (b)(ii).] Describe how a data model is represented in a relational database, and explain how one might specify a relational database schema. [5 marks] What is meant by a referential integrity constraint in a relational database? [3 marks] Each year the number of tourists coming to Cambridge increases by 10%. Most of the pressure falls on a limited number of identified sites in the city centre. The Tourist Board has restricted the size of any group visiting such a site to 20, and requires a group of ten people or more to get a permit in advance. Most bookings are made either by tour operators or directly by independent guides: the Tourist Board will arrange guides for groups if asked to do so. A database is being installed to coordinate bookings and to provide information about the opening times of sites. Each site has separate opening times for summer and winter (owing to college autonomy, changes of season differ from site to site). Permits are issued to start on the hour or on the half-hour: they are valid either for 1 hour or for 2 hours, the duration being fixed for each site. The final permits of each day are timed to expire at the site's closing time. Each site has a fixed(a) Explain the terms amortized analysis and aggregate analysis, highlighting the difference between them. [3 marks] (b) Assume that the following two classes, which implement the standard stack (last-in first-out) and queue (first-in first-out) data structures, are available. class Stack class Queue void push(Item x) void enqueue(Item x) Item pop() Item dequeue() Boolean isEmpty() Boolean isEmpty() (i) A Multistack class is derived from Stack with the addition of two methods: a void multipush(Itemlist l) that takes a list l of items and pushes each of the items onto the stack (each action of extracting an item from the list and pushing it onto the stack has constant cost), and a void multipop(int m) that takes an integer m and pops that many items off the stack (raising an exception if there were fewer, but don't worry about that). Is it true or false that, given an arbitrary sequence of n Multistack operations starting from an empty Multistack, each operation in the sequence has amortized constant cost? Justify your answer in detail. [5 marks] (ii) Provide an implementation of class Queue using no other data structures than Item, Boolean, int and Stack. The amortized running time of each Queue method must be constant. (Note that you may only use the Stack as a black box: you are not allowed to access its internal implementation.) [7 marks] (iii) Using the potential method, prove that the amortized running time of all your Queue methods from part (b)(ii) is indeed constant. [5 marks]