(This should take no longer than 20 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 (surname)? [1]
Pat (Terry)
2. 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"? [5]
The arrays are used to denote whether a queen placed in row I, column J of the board would threaten other queens in that column, or on the diagonals passing through that [I,J] position. If A[J] is TRUE it would be safe to place a queen in column J as there would be no other queen in column J. If B[I+J] is TRUE it would be safe to place the queen in Row I, Column 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 Row I, Column J because there can be no queen threatening that square along a diagonal extending top 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 (Row - Column) 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 (Columns 1 - 5)
.-----------------------------.
| | | | | |
Row 1 | | | | | |
|-----+-----+-----+-----+-----|
| | | | | |
Row 2 | | | | | |
|-----+-----+-----+-----+-----|
| | | | | |
3 | | Q | | | |
|-----+-----+-----+-----+-----|
| | | | | |
4 | | | | | |
|-----+-----+-----+-----+-----|
| | | | | |
5 | | | | | |
`-----------------------------'
Looked at in another way, once a Queen has been placed any of the squares shown, the value of the array element shown will be set to "false".
1 2 3 4 5 (Columns 1 - 5)
.-----------------------------.
|A[1] |A[2] |A[3] |A[4] |A[5] |
|B[2] |B[3] |B[4] |B[5] |B[6] |
Row 1 |C[0] |C[-1]|C[-2]|C[-3]|C[-4]|
|-----+-----+-----+-----+-----|
|A[1] |A[2] |A[3] |A[4] |A[5] |
|B[3] |B[4] |B[5] |B[6] |B[7] |
Row 2 |C[1] |C[0] |C[-1]|C[-2]|C[-3]|
|-----+-----+-----+-----+-----|
|A[1] |A[2] |A[3] |A[4] |A[5] |
|B[4] |B[5] |B[6] |B[7] |B[8] |
3 |C[2] |C[1] |C[0] |C[-1]|C[-2]|
|-----+-----+-----+-----+-----|
|A[1] |A[2] |A[3] |A[4] |A[5] |
|B[5] |B[6] |B[7] |B[8] |B[9] |
4 |C[3] |C[2] |C[1] |C[0] |C[-1]|
|-----+-----+-----+-----+-----|
|A[1] |A[2] |A[3] |A[4] |A[5] |
|B[6] |B[7] |B[8] |B[9] |B[10]|
5 |C[4] |C[3] |C[2] |C[1] |C[0] |
`-----------------------------'
3. 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? [3]
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
4. Parva does not allow you to pass simple integer parameters "by reference", or to use "global variables". How do you suppose one can get the effect that was probably intended when a programmer tried writing the code below? [3]
void BiggestAndSmallest (int [] list, int n, int big, int small) {
// Return big and small as the largest/smallest elements in list[0] ... list[n]
big = list[0]; small = big;
for (int i = 1; i <= n; i++) {
if (list[i] > big) { big = list[i]; }
if (small < list[i]) { small = list[i]; }
}
}
There are several possibilities, all a bit messy:
(a) Write separate functions for each result:
int biggest (int [] list, int n) {
// Return the largest element in list[0] ... list[n]
int big = list[0];
for (int i = 1; i <= n; i++) {
if (list[i] > big) { big = list[i]; }
}
return big;
}
int smallest (int [] list, int n) {
// Return the smallest element in list[0] ... list[n]
int small = list[0];
for (int i = 1; i <= n; i++) {
if (small < list[i]) { small = list[i]; }
}
return small;
}
(b) Return the values as the two elements of another array:
void BiggestAndSmallest (int [] list, int n, int [] bigsmall) {
// Return bigsmall[0] and bigsmall[1] as the largest/smallest elements in list[0] ... list[n]
bigsmall[0] = list[0]; bigsmall[1] = bigsmall[0];
for (int i = 1; i <= n; i++) {
if (list[i] > bigsmall[0]) { bigsmall[0] = list[i]; }
if (bigsmall[1] < list[i]) { bigsmall[1] = list[i]; }
}
}
(c) Set up arrays of length 1 for big and small (arrays are always passed by reference).
void BiggestAndSmallest (int [] list, int n, int [] big, int [] small) {
// Return big[0] and small[0] as the largest/smallest elements in list[0] ... list[n]
big[0] = list[0]; small[0] = big[0];
for (int i = 1; i <= n; i++) {
if (list[i] > big[0]) { big[0] = list[i]; }
if (small[0] < list[i]) { small[0] = list[i]; }
}
}
(d) In Parva you cannot dispense with the parameters "big" and "small" and use "global variables" , or try to "return" two integers with two "return" statements. An int function can only return one value!
5. 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). Complete the T diagram representation of how such an arrangement would handle the compilation of a simple program. [4]
.--------------------------. .--------------------------. .--------------------------.
| Simple.C | | Simple.ASM | | Simple.EXE |
| | | | | |
| Input --------> Output | | Input --------> Output | | Input --------> Output |
`-------. .--------------------------. .--------------------------. .-------'
| | CtoASM.EXE | | ASMto8086.EXE | |
| | | | | |
| C | C ---------> ASM | ASM | ASM ---------> 8086 | 8086 |
`------------------. .--------------------------. .------------------'
| | | |
| 8086 | | 8086 |
| | | |
`----------' `----------'
.----------. .----------.
| 8086 | | 8086 |
`----------' `----------'
6. Consider the silly Modula program below along with its translation into C performed using the translator X2C. (Even if you are not expert in Modula the intent of this piece of code should be pretty obvious.)
Why do you suppose the X2C translation makes so much of the assignment statement List[I] := I + 10 ? [2]
There are two points - firstly it is doing "range checking" to ensure that the value assigned to List[I-5] is correctly within the range 5 to 15. Those of you who have grown up in the unprotected world of C++ have never learnt how useful this sort of check can be when debugging programs, unfortunately. Secondly, it has had to map the subscripts 5 ... 15 to 0 ... 10.
Why do you suppose the X2C translation has introduced such long-winded variable names and the p2c one has not deemed it necessary to do so? [ 2 ]
X2C has done this so as to try to ensure that "name clashes" do not arise in the C++ code that is produced. Each name has been synthesized from the "simple" name and the "module name" - this may make for long identifiers but helps programmers and compilers identify whence they have come (quickly - if I gave you a piece of C++ code with a function call to a function called offsetof, which library does it come from?).
MODULE Silly;
TYPE
SUBSCRIPTS = INTEGER [5 .. 15];
VAR
I, J : SUBSCRIPTS;
List : ARRAY SUBSCRIPTS OF SUBSCRIPTS;
BEGIN
FOR I := 5 TO J DO List[I] := I + 10 END
END Silly.
#include "X2C.h"
typedef X2C_INT16 Silly_SUBSCRIPTS;
static Silly_SUBSCRIPTS Silly_I;
static Silly_SUBSCRIPTS Silly_J;
typedef Silly_SUBSCRIPTS Silly_ANONYM1[11];
static Silly_ANONYM1 Silly_List;
int main(int argc, char **argv) /* translation by X2C */
{ X2C_BEGIN(argc, argv);
static Silly_SUBSCRIPTS Silly_V1;
Silly_I = 5;
Silly_V1 = Silly_J;
if (Silly_I <= Silly_V1) {
for (;;) {
Silly_List[(X2C_INT16) Silly_I - 5] = (X2C_INT16) X2C_CHK((Silly_I + 10), 5, 15);
if (Silly_I == Silly_V1) break;
++Silly_I;
}
}
return 0;
}