Foundations of Computer Science

The ML data type BOOL, defined below, is to be used to represent boolean expressions.

   datatype BOOL = VAR of string
                   | NOT of BOOL
                   | AND of BOOL*BOOL
                   | OR    of BOOL*BOOL;

The constructor VAR is used to represent named boolean variables, and NOT, AND and OR are used to represent the corresponding boolean operators.

Define a function that will return a list of the distinct names used in a given boolean expression. [4 marks]

A context is represented by a list of strings corresponding to the boolean variables that are set to true. All other variables are deemed to be set to false. Define a function that will evaluate a given boolean expression in a given context. [3 marks]

incorporate your two functions into a program that will determine whether a given boolean expression is true for all possible settings of its variables. [3 marks]

Programming in Modula-3

Show how Modula-3 exceptions can be used in conjunction with a FOR loop

to simulate the effect of the EXIT statement; [5 marks]
to skip to the next iteration of the loop. [5 marks]

System Design

What are the advantages of using a high-level language for writing programs? [7 marks]
Why must some parts of the code which makes up an executable binary program typically have to be written in assembly language ? Who typically writes these parts and where are they normally stored in the system? [3 marks]

Foundations of Computer Science

Define an ML function rotations that will compute the list of all rotations of a given list. For example

rotations [1,2,3] = [[1,2,3],[2,3,1],[3,1,2]]

The order in which the rotations occur is unimportant. [10 marks]

Carefully explain how your function works and estimate the time complexity of your solution. [10 marks]

Foundations of Computer Science

Give the declaration of an ML datatype that could be used in the representation of a lazy list of integers, and illustrate its use by defining a function ints that when given an argument n and yields a lazy list of integers from n to infinity. [5 marks]

The decimal representation of a real number in the range 0 to 1 is to be represented as an infinite sequence of the decimal digits following the decimal point (O.d₁d₂ ... ). Define a function mknumb which which when applied to the digit function dig will construct a lazy list of these digits where the i^th digit (d_i) is given by dig i. [5 marks]

Suppose we have an infinite sequence of such numbers [r₁,r₂,...], in which the digits of the decimal expansion of r_i are given by the digit function f_i, and that the collection of digit functions is represented by the lazy list [f₁,f₂ .... ]. Define suitable datatypes for the list of numbers and the list of digit functions. [5 marks]

Define a function newnumb which when given the lazy list of digit functions will yield a lazy list of digits that have the property that its i^th digit differs from the i^th digit of r_i. [5 marks]

Programming in Modula-3

A student unfamiliar with Modula-3 wrote the following procedure:

         PROCEDURE Stats () =
         VAR m, v := 0.0;
         BEGIN
           WITH n = IO.GetInt (),
                a = ARRAY [1. .n]  OF REAL DO
             FOR i := 1 TO n DO a[i] := IO.GetReal () END;
             FOR i := 1 TO n DO INC (m, a[i]) END;
             m := m / n;
             FOR i := 1 TO n DO INC (v, (a[i]-m)*(a[i]-m)) END;
             v := v / n;
             RETURN RECORD {m, v};
           END;
         END Stats;

Explain, to the extent that you can reconstruct them, the programmer's intentions. [5 marks]

Comment on the legality of the code and indicate what the Modula-3 compiler's response would be to it. [5 marks]

How would you correct the procedure -

following the external data format and internal data structure and algorithm intended by the programmer; [5 marks]
re-writing it completely from scratch, possibly even having a different external data format (which should be specified). [5 marks]

Programming in Modula-3

A priority queue maintains a list of pairs, each consisting of a priority (a natural number) and a name (a text string), sorted into increasing order of priority. Consider the implementation of such a queue as an object in Modula-3. This should have two methods insert taking a pair as its arguments to be placed at the appropriate point in the list, and next taking no arguments but removing the first pair from the list and returning its text string component.

Give type definitions and default method implementations for this queue object. [20 marks]

System Design

How does a loaded program in a general purpose timesharing computer gain access to input and output streams provided by the operating system? [5 marks]
What happens when the program is ready to receive the next data from a keyboard input stream and no key press is ready? [5 marks]
A CPU intensive program will tend to run for long periods of time without making requests of the operating system. What happens to other users programs when someone runs a CPU intensive program? [5 marks]
What can be done for a shared output device such as a printer or plotter to ensure civilised results when two or more users try to use it at once? [5 marks]

System Design

With modern technology, many pieces of equipment which we would describe as a `computer' actually contain multiple hardware components, each performing fetch- execute cycles. However not all of these are always intended to be `seen' by the programmer as part of the programming model. Define or explain the following:

The term microprocessor. [3 marks]
The term programming model. [3 marks]
The effects (or lack of them) on the programming model of having microprocessors imbedded in peripheral devices of a computer. [6 marks]
A programming model of an overt multiprocessor machine. [6 marks]
What type of system in production today is likely to have exactly one microprocessor inside? [2 marks]