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.d1d2 ... ).
Define a function mknumb which which when applied to the digit function dig will
construct a lazy list of these digits
where the ith digit (di) is given by dig i.
[5 marks]
Suppose we have an infinite sequence of such numbers [r1,r2,...], in which the
digits of the decimal expansion of ri are given by
the digit function fi, and that
the collection of digit functions is represented by the lazy list
[f1,f2 .... ]. 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 ith digit
differs from the ith digit of ri. [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]