Microkernel operating systems aim to address perceived modularity and reliability issues in traditional "monolithic" operating systems. (i) Describe the typical architecture of a microkernel operating system such as Mach 3.0, including its use of address spaces, processor privilege levels and communication channels compared with a traditional operating system structure. [6 marks] (ii) How does this structure affect the system performance? [4 marks] (b) Virtual machine monitors existed before microkernels and have experienced a recent resurgence of interest; using examples, describe some of the motivations for a virtual machine monitor approach. [4 marks] (c) Compare and contrast the means used to support pre-existing applications in the microkernel and virtual machine worlds. ; (iv) ambiguity in rhetorical relations (discourse relations). [12 marks total] (b) Explain what is meant by "packing" in parsing and discuss its relevance to the treatment of ambiguity. [8 marks] d) Consider the design of a one-bit full-adder in asynchronous dual-rail logic. There will be three input pairs: (P0, P1), (Q0, Q1) and (R0, R1), and two output pairs: (S0, S1) for the high-order bit of the sum and (T0, T1) for the low-order bit. All inputs should become valid before any outputs become valid, and then all the outputs should remain valid until all the inputs are clear again. Sketch a circuit diagram for the adder using inverters, NAND gates, NOR gates and C elements. [10 marks] 4 Digital Communication II (a) Many distributed algorithms for sharing resources on the time scale of a roundtrip time exist. (i) Describe the p-persistent CSMA/CD algorithm used on Ethernets to manage capacity and contention for a shared resource. [5 marks] (ii) Describe a difference from (i) arising from the hidden- and exposedterminal problems in shared-media wireless media networks, and how this leads to CSMA/CA. [5 marks] (b) Discuss how the use of TCP's congestion avoidance and control algorithm can be seen as similar to the contention schemes used in Ethernets (wired or wireless). [5 marks] (c) What is the key parameter distinguishing between CSMA/CD and TCP, and why does this make a difference in the different schemes for avoiding congestion and contention on shared media? [5 marks] 3 (TURN OVER) CST.2007.9.4 5 Distributed Systems (a) When distributed systems are designed and engineered, certain fundamental properties have to be taken into account, including: 1. concurrent execution of components 2. independent failure modes 3. communication delay 4. no global time Give three examples of the implications of these properties (separately or in combination) on the engineering of large-scale, widely distributed systems. [9 marks] (b) (i) Define role-based access control (RBAC). (ii) Outline how RBAC could be used for a national healthcare system comprising many administration domains such as primary care practices, hospitals, specialist clinics, etc. Principals may, from time to time, work in domains other than their home domain, and must be authorised to do so. (iii) A national Electronic Health Record (EHR) service must be accessible from all domains. It is required by law that access control policy should be able to capture exclusion of principals and relationships between them. How could this requirement be met in an RBAC design? [11 marks] 4 CST.2007.9.5 6 Computer Vision (a) Briefly define each of the following concepts as it relates to vision: (i) active contour; [2 marks] (ii) Hadamard's criteria for well-posed problems; [2 marks] (iii) functional streaming; [2 marks] (iv) reflectance map; [2 marks] (v) Bayesian prior. [2 marks] (b) What is accomplished by the lateral signal flows within both plexiform layers of the mammalian retina, in terms of spatial and temporal image processing and coding? [3 marks] (c) Give finite difference operators that could be applied to 1-dimensional discrete data (such as a row of pixels) in order to approximate the 1st and 2nd derivatives, d dx and d 2 dx2 . How would your finite difference operators actually be applied to the row of pixels? What is the benefit of using a 2nd finite difference (or derivative) instead of a 1st finite difference (or derivative) for edge detection? [3 marks] (d) Explain the formal mathematical similarity between the "eigenface" representation for face recognition, and an ordinary Fourier transform, in the following respects: (i) Why are they both called linear transforms, and what is the "inner product" operation in each case? [1 mark] (ii) What is a projection coefficient and an expansion coefficient in each case? [1 mark] (iii) What is the orthogonal basis in each case, and what is meant by orthogonality? [1 mark] (iv) Finally, contrast the two in terms of the use of a data-dependent or a data-independent (universal) expansion basis. [1 mark] 5 (TURN OVER) CST.2007.9.6 7 Advanced Graphics (a) Outline a method that could be used for modelling water and other fluids. [6 marks] (b) (i) Show how to find the first intersection between a ray and a finite-length, open-ended cone, of unit slope, centred at the origin, aligned along the y-axis, for which both ends of the finite-length are on the positive y-axis (i.e. 0 < ymin < ymax). [6 marks] (ii) Extend this to cope with a closed cone (i.e. the same cone, but with end caps). Take care to consider any special cases. [4 marks] (iii) Extend this further to give the normal vector at the intersection point. Take care to consider all cases. [4 marks] 8 Specification and Verification II (a) Given a predicate B specifying a set of initial states and a transition relation R, define the set of reachable states. [4 marks] (b) Explain the difference between Linear Temporal Logic and Interval Temporal Logic. [4 marks] (c) (i) What is model checking? [2 marks] (ii) Explain the key idea of symbolic model checking. [2 marks] (d) (i) What is a SERE in PSL? [2 marks] (ii) Give an example of a PSL formula involving a SERE and explain its meaning. [2 marks] (e) (i) What is the difference between dynamic verification and static verification? [2 marks] (ii) What kind of tools are used with each sort of verification? [2 marks] 6 CST.2007.9.7 9 Artificial Intelligence II An agent exists within an environment in which it can perform actions to move between states. On executing any action it moves to a new state and receives a reward. The agent aims to explore its environment in such a way as to learn which action to perform in any given state so as in some sense to maximise the accumulated reward it receives over time. (a) Give a detailed definition of a deterministic Markov decision process within the stated framework. [4 marks] (b) Give a general definition of a policy, of the discounted cumulative reward, and of the optimum policy within this framework. [4 marks] (c) Give a detailed derivation of the Q-learning algorithm for learning the optimum policy. [8 marks] (d) Explain why it is necessary to trade-off exploration against exploitation when applying Q-learning, and explain one way in which this can be achieved in practice. [4 marks] 10 Digital Signal Processing (a) Write an efficient microcontroller program (pseudocode) that outputs a continuous sine wave of frequency f = 440 Hz with values yn in the range 1 to 1 at a sampling frequency fs = 32 kHz. The programming language you have available lacks complex-number arithmetic, the runtime environment offers only basic floating-point arithmetic (i.e., no trigonometric functions), addition is much faster than multiplication, and there is insufficient memory to store a precomputed waveform. [10 marks] (b) The discrete sequence yn = cos(2nf1/fs) + A cos(2nf2/fs) is fed into a (hypothetical) digital-to-analogue converter that outputs a constant voltage y(t) = yn during the time interval n/fs t < (n + 1)/fs for all integers n. (i) Explain how this behaviour of the digital-to-analogue converter affects the amplitude spectrum of the resulting signal. [5 marks] (ii) What amplitude A has to be chosen for the second term such that the resulting amplitude spectrum shows equally high peaks at both f1 = 1 kHz and f2 = 2 kHz if the sampling frequency is fs = 6 kHz? [5 marks] 7 (TURN OVER) CST.2007.9.8 11 Computer Systems Modelling (a) Consider a general birth-death process with birth rate i and death rate i in state i (i = 0, 1, 2, . . .). What are the detailed balance equations for this process? [2 marks] (b) Derive the steady-state distribution for the general birth-death process considered in part (a). What are the conditions for the steady-state distribution to exist? [4 marks] (c) Describe the M/M/1 queue and give a stochastic model for the number of customers present. Find the steady-state distribution for the number of customers present and state the condition for it to exist. [4 marks] (d) Derive the mean number of customers present in steady state in the M/M/1 queue. [4 marks] (e) State Little's law and use it to derive the mean time spent in the M/M/1 queue in the steady state. [2 marks] (f ) Discuss what is meant by the traffic intensity for an M/M/1 and explain what happens to the mean number of customers present as the traffic intensity increases towards one. [4 marks] 8 CST.2007.9.9 12 Quantum Computing (a) Consider a quantum finite automaton with two basis states, |0i being the start state and |1i the only accepting state. The automaton operates on a two-letter alphabet, with matrices Ma = " 1 2 1 2 1 2 1 2 # and Mb = 1 0 0 1 . What are the probabilities that the automaton accepts each of the following input strings? (i) a [3 marks] (ii) aba [3 marks] (iii) abb [3 marks] (b) Give a complete description of the probabilities of acceptance associated with various possible input strings. [5 marks] (c) Prove that there is no two-state probabilistic automaton with the same behaviour as the automaton described in part (a). [6 marks] 13 Bioinformatics (a) Describe a bioinformatics application of hidden Markov models. [6 marks] (b) Discuss the properties of the Markov clustering algorithm and the differences with respect to the k-means and hierarchical clustering algorithms. [8 marks] (c) Describe the Gillespie algorithm and discuss its relationship with genetic or biochemical networks (give one example). [6 marks] 9 (TURN OVER) CST.2007.9.10 14 Types (a) Give the rules inductively defining the type system of the polymorphic lambda calculus (PLC). [5 marks] (b) What does it mean for a PLC expression M to be in beta-normal form? [2 marks] (c) The long normal forms, L, and the neutral forms, N, are special kinds of PLC expression given by the following grammar: L ::= x : (L) | (L) | N, N ::= x | N L | N . (i) Arguing by induction on the structure of L and N, or otherwise, show that all such expressions are in beta-normal form. [4 marks] (ii) Show that if N is a neutral form, then {} ` N : is not provable in the PLC type system for any type , where {} is the empty typing environment. (You may assume without proof that if ` M : is provable in the PLC type system, then the free variables of the expression M are contained in the domain of definition of the typing environment .) [3 marks] (iii) Hence prove that for any long normal form L, {} ` L : () is not provable in the PLC type system. [6 marks] 10 CST.2007.9.11 15 Denotational Semantics Assume a denotational semantics is given for PCF: a mapping of PCF types to domains [[ ]] together with a mapping of closed PCF terms of type , M : Explain in detail what happens when class GPS below is instantiated noting, in particular, any assignments that are made. [17 marks] class GPS { public int[][] a = new int[4][4]; private int[] i = new int[1]; private int[] j = new int[1]; public GPS() { this.j[0] = this.gps(this.j, 4, new Pi(), new Fg()); } private int gps(int[] i, final int N, Pass z, Feval v) { i[0] = 0; while (i[0]c[2] &(*pps)[1] ++p->i [8 marks] (b) Explain why the code shown below, when executed, will print the value 420. #include #define init_employee(X,Y) {(X),(Y),wage_emp} typedef struct Employee Em; struct Employee {int hours,salary;int (*wage)(Em*);}; int wage_emp(Em *ths) {return ths->hours*ths->salary;} #define init_manager(X,Y,Z) {(X),(Y),wage_man,(Z)} typedef struct Manager Mn; struct Manager {int hours,salary;int (*wage)(Mn*);int bonus;}; int wage_man(Mn *ths) {return ths->hours*ths->salary+ths->bonus;} int main(void) { Mn m = init_manager(40,10,20); Em *e= (Em *) &m; printf("%d ",e->wage(e)); return 0; } [4 marks] (c) Rewrite the C code shown in part (b) using C++ primitives and give four reasons why your C++ solution is better than the C one. [8 marks] 5 (TURN OVER) CST.2007.10.6 5 Computer Graphics and Image Processing (a) In image compression we use three different mechanisms to compress pixel data: (i) mapping the pixel values to some other set of values; (ii) quantising those values; (iii) symbol encoding the resulting values. Explain each mechanism, describe the way in which it helps us to compress the image, and describe how the mechanism is implemented in the baseline JPEG compression method. [10 marks] (b) Describe the limitations of human vision in terms of: (i) spatial resolution, (ii) luminance, (iii) colour, and explain the implications that each of these has on the design of display devices, including numerical estimates of the limits beyond which a human cannot discriminate. [10 marks] 6 CST.2007.10.7 6 Mathematics for Computation Theory State the requirements for (S, 6) to be: (a) a partially ordered set; (b) a totally ordered set; (c) a well ordered set. [5 marks] Let N be the natural numbers. Give, without proof, three examples of relations 6i , where i = 1, 2, 3, such that (N, 6i) satisfies exactly i of the conditions (a), (b), (c). [3 marks] Let S = {a, b} be an alphabet, with total order a < b. Let = S be the set of all strings over S; for w = s1s2 . . . sn we write `(w) = n, and for 1 6 r 6 n = `(w) we write wr = s1s2 . . . sr. Denote by the unique word of such that `() = 0, the null string. Conventionally w0 = for all words w . Define relation on as follows: Let v, w , and n = min{`(v), `(w)}. Let r = max{i | vi = wi} 6 n. Then v w if: either (i) `(v) = r; or (ii) vr+1 = vra, wr+1 = wrb, where vr = wr. Which of conditions (a), (b), (c) above are satisfied by (, )? [12 marks] 7 (TURN OVER) CST.2007.10.8 7 Computation Theory (a) (i) Define the notion of a register machine and the computations that it carries out. [5 marks] (ii) Explain, in general terms, what is meant by a universal register machine. (You should make clear what scheme for coding programs as numbers you are using, but you are not required to describe a universal register machine program in detail.) [5 marks] (b) (i) Explain what it means for a partial function f from N to N to be computable by a register machine. [2 marks] (ii) Let n > 1 be a fixed natural number. Show that the partial function from N to N fn(x) = n nx if x > 0 undefined if x = 0 is computable. [3 marks] (iii) Explain why there are only countably many computable functions from N to N. Deduce that there exists a partial function from N to N that is not computable. (Any standard results you use about countable and uncountable sets should be clearly stated, but need not be proved.) [3 marks] (iv) If a partial function f from N to N is computable, how many different register machine programs are there that compute f? [2 marks] 8 Artificial Intelligence I We have a basic search problem, consisting of a set S of states, a start state s0, a goal test G(s) that returns True if s S is a goal and False otherwise, and a function exp(s) that returns the set of states obtained by expanding state s. (a) Describe in detail the Graph Search algorithm for solving a problem of this type. How does it differ from the related Tree Search algorithm? [8 marks] (b) Give a detailed description of the Recursive Best First search algorithm, and explain why it might be used in preference to the A? algorithm. [12 marks] 8 CST.2007.10.9 9 Introduction to Security (a) You have received a shipment of hardware random-number generators, each of which can output one 128-bit random number every 10 milliseconds. You suspect that one of these modules has been tampered with and that it actually produces only 30-bit random numbers internally, which are then converted via a pseudo-random function into the 128-bit values that it outputs. (i) How does this form of tampering reduce the security of a system that uses a generated 128-bit random number as the secret key of a block cipher used to generate message authentication codes? [2 marks] (ii) Suggest a test that has a more than 0.5 success probability of identifying within half an hour that a module has been tampered with in this way. [6 marks] (b) Explain briefly (i) the encryption and decryption steps of Cipher Feedback Mode; [3 marks] (ii) why some operating systems ask the user to press a special key combination (e.g., Alt-Ctrl-Del) before each password login; [3 marks] (iii) how a secure hash function can be used to implement a one-time signature scheme; [3 marks] (iv) what happens if the same private key of the scheme from (iii) is used multiple times, to sign different messages. [3 marks] 9 (TURN OVER) CST.2007.10.10 10 Data Structures and Algorithms (a) Give a clear description of an efficient algorithm for finding the i th smallest element of an n-element vector. Write some pseudocode for the algorithm and discuss its time complexity. Compare it with other plausible ways of achieving the same result. [Notes: Use zero-based indexing. You may assume for simplicity that all the elements of the vector are different.] [4 marks] (b) Give a clear description of an efficient algorithm for finding the k smallest elements of a very large n-element vector. Compare its running time with that of other plausible ways of achieving the same result, including that of applying k times your solution for part (a). [Note that in part (a) the result of the function consists of one element, whereas here it consists of k elements. As above, you may assume for simplicity that all the elements of the vector are different.] [6 marks] (c) Give an optimal algorithm for solving part (b) for k = 1. Give the worst-case number of comparisons performed by your algorithm as a function of n. [Note: exact number of comparisons, not just asymptotic complexity.] [4 marks] (d) Same as part (c), but for k = 2. [6 marks] 10 CST.2007.10.11 11 Introduction to Functional Programming (a) Specify the types of the following SML functions: (i) fn f => map f [2 marks] (ii) fn f => map map f [2 marks]An inertial navigation system is a device that uses gyros and accelerometers to measure changes in its position and orientation. It is typically used in aircraft to provide a backup navigation mechanism for GPS and other radio-based systems, and to provide an altitude reference when flying on autopilot. You have been hired to adapt such a device to be the main navigation system for an unmanned submersible. Describe the methodology you would use, with particular reference to how you would assure your customer of the device's dependability, and what sort of problems you would watch out for. [20 marks] 2 Computer Design (a) What is the difference between the latency and the bandwidth of a communication link? [2 marks] (b) Why are control-flow processors sensitive to memory latency even if the memory bandwidth exceeds what the processor could ever require? [4 marks] (c) How is average memory latency typically reduced? [5 marks] (d) What is the difference between serial and parallel communication and what is the receiver required to do to recover the data in each case? [5 marks] (e) The PCI communication standard for add-on cards for PCs has moved to PCI express (PCIe). PCI uses a parallel bus to communicate to several cards whereas PCIe uses sets of point-to-point serial links for communication. Why are multiple serial links rather than parallel buses preferred for high bandwidth communication? [4 marks] 2 CST.2007.5.3 3 Digital Communication I Using four examples, explain how multiple higher-layer channels can be multiplexed onto a lower-layer channel. In each example consider (i) how the individual higher-layer channels can be recognised; (ii) what the mechanism is for allocation of lower-layer channel resources to the higher-layer channels; and (iii) the characteristics of the higher-layer channels. [4 5 marks] 4 Concurrent Systems and Applications (a) A software engineer is developing computer-aided design software for an architect who works with designs for three different types of building: Contemporary, Victorian, and Roman. When laying out buildings, the architect places windows, doorways, walls and roofs in the appropriate style for the building on which she is working. Explain, including all the Java interfaces and code fragments, how the software can use the Abstract Factory design pattern to construct and maintain its internal data structures representing a building. [6 marks] (b) In terms of software testing, what is equivalence partitioning, how can it be done, and how can the partitioned sets be used to select test patterns? [6 marks] (c) What are decision coverage and condition coverage? [2 marks] (d) Describe Java's Remote Method Invocation (RMI) system, including the means by which objects and servers are named, how clients perform binding, and the purpose of the RMI CodeBase. [6 marks] 3 (TURN OVER) CST.2007.5.4 SECTION B 5 Computer Graphics and Image Processing (a) Describe, in detail, an algorithm that will draw a one-pixel wide outline of a circle of integer radius centred on the origin. [10 marks] (b) Describe the modifications required to your algorithm in part (a) to make it draw a filled circle. [3 marks] (c) Describe the modifications required to your algorithm in part (a) to make it draw the outline of a circle centred at arbitrary integer coordinates. [2 marks] (d) Describe the modifications required to your algorithm in part (c) to make it draw the outline of a circle centred at arbitrary non-integer coordinates and of non-integer radius. [5 marks] 6 Compiler Construction (a) Describe how a stack is used to implement procedures and functions. [6 marks] (b) Suppose a language allows the creation of pointers. How does this complicate the use of stacks as described in part (a)? [2 marks] (c) How does the Java language deal with the problem described in part (b)? [2 marks] (d) Consider the following ML-like program containing the function g that returns a function as a result. let a = 17 in let g b = (let h c = a + b + c in h) in let f1 = g 21 in let f2 = g 33 in let v = f1(3) + f2(57) in ... ... Explain carefully how such a program can be compiled. In particular, pay special attention to how the code for the body of the function h can access the values of a, b, and c. [10 marks] 4 CST.2007.5.5 7 Concepts in Programming Languages (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. [5 marks] 5 (TURN OVER) CST.2007.5.6 8 Databases (a) The Entity/Relationship model is based around the concepts of entity, attribute, and relationship. Describe how these can be represented in the relational model. [6 marks] (b) Data normalisation is often an important component in database design. Discuss why this is so, and give examples of situations where normalisation is not important. [6 marks] (c) Let A and B be disjoint non-empty sets of attributes. Let R be a relation over attributes A B and let S be a relation over attributes B. Suppose that we want to introduce a new relational operation called division, denoted R S, that will return a relation over attributes A. The relation R S is made up of all tuples t such that for all s S we have ts R (ts is the concatenation of t and s). Note that in the special case that R = T S for some relation T, then (R S) = T and (R T) = S. In other words, can be treated as an inverse to the Cartesian product. Can we define R S in the relational algebra? Prove that your answer is correct. [8 marks] 6 CST.2007.5.7 SECTION C 9 Logic and Proof (a) You have to write a program that accepts a propositional formula and returns an interpretation that falsifies . Describe the algorithm you would employ in each of the following circumstances: (i) can be expected to contain many occurrences of the connective. [4 marks] (ii) will be delivered in disjunctive normal form. [4 marks] (b) Let S be a set of propositional clauses, each of which contains a negative literal. (i) Show that applying the resolution procedure to S will never generate the empty clause. [3 marks] (ii) Describe a model that satisfies S. [3 marks] (c) Prove or disprove the sequent (P Q) (P) (Q) of S4 modal logic. [6 marks] 7 (TURN OVER) (iii) fn f => (map o map) f [2 marks] [Recall that the composition operator o has type ( ) * ( ) .] (b) Let datatype tree = empty | node of * tree * tree be the data type of binary trees. (i) A bijective correspondence between types and is given by a pair of functions f : and g : such that g o f = fn a : => a and f o g = fn b : => b. Exhibit recursive SML functions f: unit tree (unit tree) list and g: (unit tree) list unit tree that establish a bijective correspondence between the types unit tree and (unit tree) list. [3 marks] (ii) Give an alternative definition of the function g in terms of either foldl or foldr. [3 marks] (iii) Define a treefold function of type ( * tree * ) ( tree) and give an alternative definition of the function f in terms of it. [3 marks] (c) Rigorously argue for the correctness of the following identities: g o f = fn t:unit tree => t f o g = fn l:(unit tree) list => l [5 marks] 11 (TURN OVER) CST.2007.10.12 12 Operating System Foundations Operating systems are integrated closely with the hardware on which they run. (a) Distinguish the hardware and software involved in interrupt-driven I/O. [4 marks] (b) Describe three uses of the interrupt mechanism in addition to device I/O. [3 marks] (c) Give examples of how the privilege state bit in a CPU's status register is used. [2 marks] (d) (i) What could go wrong in a system that does not make use of a timing device in process scheduling? [1 mark] (ii) What class of scheduling algorithms would be impossible to implement without a timing device? [2 marks] (e) What is the main advantage of using half the virtual address space of a process for the operating system and half for applications? [1 mark] (f ) Explain memory-mapped I/O. [2 marks] (g) In a paging system, would you expect every page of the operating system address space to be: (i) mappable in the Translation Lookaside Buffer (TLB)? [2 marks] (ii) capable of being cached? [1 mark] Explain your answers. (h) How do DMA (Direct Memory Access) devices operate? [2 marks] , to elements of the corresponding domain [[M]] [[ ]]. In the following you may refer to the notion of a PCF context without an explicit definition. (a) State clearly what properties the semantics must fulfil in order to be compositional. Give the fundamental property that a compositional semantics enjoys with respect to arbitrary contexts. [2 marks] (b) Assume the standard typed evaluation operational semantics for PCF. Without referring to explicit evaluation rules or to the syntax of PCF, state clearly what properties the denotational semantics must fulfil in order to be: (i) sound; [1 mark] (ii) adequate. [2 marks] (c) Define: (i) the contextual preorder ctx for closed PCF terms; [2 marks] (ii) contextual equivalence =ctx for closed PCF terms. [1 mark] (d) Prove that if a denotational semantics is compositional, sound and adequate then denotational equality implies contextual equivalence. [4 marks] (e) State the extensionality properties of the contextual preorder for both base types (bool and nat) and function types. [4 marks] (f ) Using extensionality, prove that the following terms are contextually equivalent: (i) (fn x : bool bool . 0)(fn x : bool . true) and 0; [2 marks] (ii) fn x : nat . (fn y : nat nat . y(yx))(fn z : nat . succ(z)) and fn x : nat . succ(succ(x)). [2 marks] 11 (TURN OVER) CST.2007.9.12 16 Optimising Compilers (a) Summarise very briefly (one short paragraph each) the overall idea behind program analysis using (i) abstract interpretation; (ii) set-constraint-based (CFA-like) analysis; (iii) rule-based analysis. [6 marks] (b) Consider the following language of integer expressions e and (integer) list expressions E where n represents integer constants, x and X respectively range over integer and list variables, represents integer operations (e.g. +, etc.), and if and IF test their first argument for zero/non-zero as in C: e ::= x | n | e1 e2 | hd E | if(e0, e1, e2) E ::= X | [ ] | e :: E | tl E | IF(e, E1, E2) In escape analysis and optimisation, given a call to f such as g(x, y) = f(x :: x :: [ ], y :: [ ]) we want to know whether or not the result of f can include any of the cons-cells reachable from its arguments. A formal parameter of f that might be incorporated into its result is known as escaping. This is useful because if (say) formal parameter 1 to f cannot escape then cons-cells allocated for actual parameter 1 can be allocated (more cheaply) on the stack instead of in the heap. This problem may be formulated as an analysis that takes an expression, e or E, constituting the body of f. The parameters of f are the free variables, xi and Xi , of its body. Express this analysis using two of the techniques from part (a). In both cases state how to use the analysis result for e or E to test "parameter Xi definitely does not escape from E or e". [Hint: in some analyses it is easier to treat the variables xi and Xi just as strings, and in others as variables ranging over {0, 1}.] [5 marks each] (c) Indicate what changes would be necessary for one of your analyses were the syntax also to allow a recursive call to f. [4 marks]