(This should take no longer than 15 minutes and is simply intended to probe whether you have understood the material in the prac questions. Answer on the questions sheet.)
1. You should get this right! What is your name?
2. A student solving the hailstone sequence problem comes up with the following Clang code for printing out a sequence
PROCEDURE ListSeries (Term);
(* Display the series starting from Term *)
BEGIN
Write(Term);
WHILE Term <> 1 DO BEGIN
IF Term / 2 * 2 <> Term THEN Term := 3 * Term + 1;
IF Term / 2 * 2 = Term THEN Term := Term / 2;
Write(Term);
END;
END;
To his horror this does not work properly. Why not?
It does not work because the first IF statement might alter the value of Term and this will then be used in the second IF statement in place of the original value of Term. We need to write code like this
IF Term / 2 * 2 <> Term
THEN Term := 3 * Term + 1
ELSE Term := Term / 2;
but we don't have an ELSE (wait for it, we'll add this essential feature in a
later version of the compiler). To fudge it, we can write code like this:
IF Term / 2 * 2 <> Term THEN Temp := 3 * Term + 1;
IF Term / 2 * 2 = Term THEN Temp := Term / 2;
Term := Temp;
Some "wrong" answers I received were:
(a) "It does not work because Term / 2 * 2 must always be the same as Term". Not so. Unless you have a totally unhelpful compiler that tries to optimize where it should not, the expression should be evaluated left to right; the division by 2 is done in INTEGER mode, and throws away any possible remainder; multiplying the quotient by 2 does not restore the original. For example
17 / 3 * 3
is evaluated as follows: 17 / 3 gives 5 remainder 2; throw away 2; multiply 5
by 3; gives 15 (not the 17 you started with).
(b) "You need parentheses"; for example
IF (Term / 2) * 2 <> Term THEN Term := 3 * Term + 1;
IF (Term / 2) * 2 = Term THEN Term := Term / 2;
Wrong again. Sure, if in doubt, put parentheses (brackets) into your
expressions. Indeed, given that C++ has an enormous 13 or so unmemorable
levels of "precedence" you would be foolish not to do so, for fear of getting
things wrong. But most languages will evaluate * and / "before" + and - (as
in arithmetic familiar from school), and will evaluate operators of equal
precedence from left to right. Clang, Pascal and even C++ do this.
3. Clang does not allow you to pass simple integer parameters "by reference". How do you suppose one can get the effect that was probably intended when a programmer tried writing
PROCEDURE Swap (x, y);
VAR temp;
BEGIN
temp := x; x := y; y := temp
END;
Incidentally, the famous Java does not allow you to pass integer parameters by reference either. This fills me with dread!
Well, this was designed to test your ingenuity. Any solution that one can come up with is a nasty hack - the absence of the "pass by reference" mechanism is a very nasty limitation on being able really to use Clang nicely.
Possible ways around the problem are:
(a) Don't use the procedure; just use the three assignments if ever you need them, as statements in what would have been the "calling" routine.
(b) Have a procedure, but don't pass it parameters, just use "global variables" (which is much the same as (a) in a sense).
(c) Since we can pass arrays by reference, pass the parameters in arrays of length 1:
PROCEDURE Swap (x[], y[]);
VAR temp;
BEGIN
temp := x[0]; x[0] := y[0]; y[0] := temp
END;
but this is pretty awful, as you would first have to copy the "real"
parameters into temporary arrays, and then copy them back out again:
x[0] := a; y[0] := b;
Swap(x, y);
a := x[0]; b := y[0];
(d) Some enterprising students suggested that you could write a FUNCTION which would return the swapped elements in an array:
FUNCTION Swap (x, y);
VAR temp[1];
BEGIN
temp[0] := y; temp[1] := x;
RETURN temp;
END;
Nice try (I mean that), but no, a Clang function (at this stage anyway) can only RETURN a single integer. This is a good example of non-orthogonality in design -- if a language supports functions, ideally its functions should be able to RETURN any of the possible entities that the data structures allow you to define (Several real languages suffer from this aspect of bad design).
4. What do you understand by the term "preprocessor"? C and C++ compilers make use of a preprocessor, although this is usually transparent to the user, and the system does its best to hide it from you. Draw a T diagram representation of how a C compiler would compile a simple program, distinguishing between the preprocessor and the rest of the compiler.
A preprocessor translates a superset of a language into the reduced form of that language. In C/C++ systems typically this involves processing #define and #include directives, among other things.
Here is one representation of the process:
+--------------------------+ +--------------------------+ +-------------------------+
| PROG.C | | PROG.C' | | PROG.EXE |
| Data -------> Results | | Data -------> Results | | Data -------> Results |
| | | | | |
+---------+ +------------------------+ +------------------------+ +----------
| | PREP.EXE | | COMP.EXE | |
| C | C --------> C' | C' | C' ------> M/C | M/C |
+------| |------| |------'
+--------+ +--------+ +--------+ +--------+
| | | |
| M/C | | M/C |
| | | |
'------' `------'
5. Niklaus Wirth may be a genius (he is), but sometimes his programs are hard to follow. His solution to the N Queens problem makes use of the arrays
VAR
A : ARRAY [1 .. Max] OF BOOLEAN;
B : ARRAY [2 .. 2*Max] OF BOOLEAN;
C : ARRAY [-Max+1 .. Max-1] OF BOOLEAN;
X : ARRAY [1 .. Max] OF INTEGER;
and there is cryptic code like
IF A[J] AND B[I+J] AND C[I-J] THEN BEGIN
X[I] := J;
A[J] := FALSE; B[I+J] := FALSE; C[I-J] := FALSE;
IF I < N
THEN Try(I+1, N)
ELSE DisplaySolution;
A[J] := TRUE; B[I+J] := TRUE; C[I-J] := TRUE;
END
What significance do the elements of A, B and C have, and why is B always subscripted "I+J" and C subscripted "I-J"?
The arrays are used to denote whether a queen in column I, row J of the board is threatened. If A[J] is TRUE it would be safe to place a queen in row J as there would be no other queen in row J. If B[I+J] is TRUE it would be safe to place the queen in Column I, Row J because there can be no queen threatening that square along a diagonal extending bottom left to top right - look at the diagram and you will see that the squares threatened on this line by the queen shown have the property that their Row + Column numbers all add to the same (in this case 5). If C[I-J] is TRUE it would be safe to place the queen in Column I, Row J because there can be no queen threatening that square along a diagonal extending top left left to bottom right - look at the diagram and you will see that the squares threatened on this line by the queen shown have the property that their (Column - Row) numbers all subtract to the same value (in this case -1).
Clever, isn't it? But it would have helped if the arrays had been given better names!
1 2 3 4 5
+-----+-----+-----+-----+-----+
| | | | | |
1 | | | | | |
+-----+-----+-----+-----+-----+
| | | | | |
2 | | | | | |
+-----+-----+-----+-----+-----+
| | | | | |
3 | | Q | | | |
+-----+-----+-----+-----+-----+
| | | | | |
4 | | | | | |
+-----+-----+-----+-----+-----+
| | | | | |
5 | | | | | |
+-----+-----+-----+-----+-----+
(This should take no longer than 15 minutes and is simply intended to probe whether you have understood the material in the prac questions. Answer on the questions sheet.)
1. You should get this right! What is your name?
2. Complete the following CLANG function
FUNCTION MOD (a, b);
(* Returns a MOD b - the remainder when a is divided by b *)
BEGIN
END;
One solution - the easiest and probably fastest is
FUNCTION MOD (a, b);
(* Returns a MOD b - the remainder when a is divided by b *)
BEGIN
RETURN a - (a/b) * b
END;
Some people suggested
FUNCTION MOD (a, b);
(* Returns a MOD b - the remainder when a is divided by b *)
BEGIN
WHILE a > b DO a := a - b;
RETURN a
END;
which works for positive and and b, but not otherwise. Clang does support
division - integer division that throws away the remainder and truncates the
quotient.
3. Clang does not allow you to pass simple integer parameters "by reference". How do you suppose one can get the effect that was probably intended when a programmer tried writing
PROCEDURE BiggestAndSmallest (List[], n, big, small);
(* Return big and small as the largest elements in List[0] ... List[n] *)
VAR i;
BEGIN
big := List[0]; small := big;
i := 1;
WHILE i <= n DO BEGIN
IF List[i] > big THEN big := List[i];
IF small < List[i] THEN small := List[i];
i := i + 1
END
END;
Incidentally, the famous Java does not allow you to pass integer parameters by reference either. This fills me with dread!
There are several possibilities, usually messy:
(a) Write separate functions for each result:
FUNCTION Biggest(List[], n);
(* Return biggest element in List[0] ... List[n] *)
VAR i, big;
BEGIN
big := List[0];
i := 1;
WHILE i <= n DO BEGIN
IF List[i] > big THEN big := List[i];
i := i + 1
END;
RETURN big
END;
FUNCTION Smallest(List[], n);
(* Return smallest element in List[0] ... List[n] *)
VAR i, small;
BEGIN
small := List[0];
i := 1;
WHILE i <= n DO BEGIN
IF List[i] < small THEN small := List[i];
i := i + 1
END;
RETURN small
END;
(b) Return the values as the two elements of another array:
PROCEDURE BiggestAndSmallest (List[], n, BigAndSmall[]);
(* Return BigAndSmall[0] and [1] as the extreme members of
List[0] ... List[n] *)
VAR i;
BEGIN
BigAndSmall[0] := List[0]; BigAndSmall[1] := BigAndSmall[0];
i := 1;
WHILE i <= n DO BEGIN
IF List[i] > BigAndSmall[0] THEN BigAndSmall[0] := List[i];
IF BigAndSmall[1] < List[i] THEN BigAndSmall[1] := List[i];
i := i + 1
END
END;
(c) Dispense with the parameters "big" and "small" and use "global variables".
4. Some C compilers achieve their goals by compiling first to assembly code and then using a complementary assembler to finish the job. (GCC can work in this way, I understand). Draw a T diagram representation of how such an arrangement would handle the compilation of a simple program.
Here is one representation of the process:
+--------------------------+ +--------------------------+ +-------------------------+
| PROG.C | | PROG.ASM | | PROG.EXE |
| Data ------> Results | | Data -------> Results | | Data ------> Results |
| | | | | |
+---------+ +------------------------+ +------------------------+ +---------+
| | GCC.EXE | | ASM.EXE | |
| C | C ------> ASM | | ASM -----> M/C | M/C |
+------| |------| |------+
+--------+ +--------+ +--------+ +--------+
| | | |
| M/C | | M/C |
| | | |
+------+ +------+
5. One Clang translation of the N-Queens program that I was shown this week had turned the code reading
IF A[J] AND B[I+J] AND C[I-J+N] THEN BEGIN
....
END
into
IF A[J] * B[I+J] * C[I-J+N] = 1 THEN BEGIN
....
END
which I thought was rather ingenious. Does this approach represent "short circuit" or "sequential conjunction" semantics, and how would you do the translation if you wanted to achieve the other semantics?
It represents "sequential conjunction". To get the other effect we would write code like:
IF A[J] THEN
IF B[I+J] THEN
IF C[I-J+N] = 1 THEN BEGIN
....
END