This test is intended to probe whether you have understood the material in the prac questions and the early part of the course. Answer on the question sheet (4 sides).
1. You should get this right! Mine is Pat Terry, 63T0844. What is yours? [1]
Pat Terry, 63T0184
2. You were asked to study a paper entitled "Seven Deadly Sins of Programming Langauge Design" by McIver and Conway.
(a) In which country did the authors live when they wrote this paper, and when did they write it? [1 + 1]
Australia (Monash University); 1996
(b) Their seven deadly sins are described under the brief headings (1) Less is more (2) More is more (3) Grammatical traps (4) Hardware dependence (5) Backwards compatibility (6) Excessive cleverness and (7) Violation of expectations.
Give an example of where a programming language known to you commits one of these sins and why it does so - please identify which sin you have chosen! [3]
Plenty to choose from - read the paper again or perhaps for the first time?
(c) Which sin do McIver and Conway regard as the worst? [1]
Violation of expectations - read the paper carefully again, or perhaps for the first time?
3. When experimenting with the Sieve program last week you should have discovered that the Pascal compiler allowed you to declare a sieve array of about 65000 elements, but attempts to look for prime numbers larger than about 16411 did not succeed. Give a brief but reasonable explanation of why this should be. [2]
This was very badly done (only one or two people came close). Several suggested that it was because a 16 bit compiler could represent numbers in the range 0 ... 216 (which is why we can set up a sieve of very nearly this size; not quite 216, because we need some space for the other simple variables). Their argument then went that 16 bit integers can represent numbers in the range -215 ... 215 - 1 and that this explained it all. Unfortunately this range is -32768 ... 32767, so one is left with an unconvincing argument.
To understand the problem we have to look at the algorithm. The part of it that reads
int k = i;
do {
Uncrossed[k] = false;
k += i;
} while (k <= n);
deserves careful analysis. When we find a large enough prime (16411) in the range 0 .. 32767 (which itself causes no problem) we shall start the loop with a number that when added to itself produces a number greater than 32767, and which then appears to be negative. Of course, this negative number is less than n, so the loop executes again and promptly crashes with an attempt to use a negative subscript in an indexing operation.
Bizarre as it may seem, better performance is achieved by coding the loop on the lines of
int k = i;
do {
Uncrossed[k] = false;
k = k + i;
} while (k <= n && k > 0); // +++ handle overflow in k
4. A reminder of the methods in the IntSet class appears below.
public class IntSet {
public IntSet()
public IntSet(BitSet s)
public IntSet(int ... members)
public void incl(int i)
public void excl(int i)
public boolean contains(int i)
public boolean isEmpty()
public int members()
public IntSet union(IntSet otherSet)
public IntSet intersection(IntSet otherSet)
public IntSet difference(IntSet otherSet)
public void write()
public String toString()
} // IntSet
The code below shows a Java version of a Sieve program for counting the number of primes below a limit read in as data. Show how it could be modified to make use of the IntSet class, in place of the Boolean array it currently uses. It will suffice to mark the changes on the code; there is no need to write out all the code again. [5]
import library.*;
class Sieve {
public static void main (String [] args) {
final int Max = 4000;
boolean [] Uncrossed = new boolean [Max];
IO.write("Supply largest number to be tested ");
int n = IO.readInt();
int primes = 0;
for (int i = 2; i <= n; i++) {
Uncrossed[i] = true;
}
for (int i = 2; i <= n; i++) {
if (Uncrossed[i]) {
primes++;
int k = i;
do {
Uncrossed[k] = false;
k += i;
} while (k <= n);
}
}
IO.write(primes + " primes between 1 and " + n);
}
}
Those of you who had really understood the question in the prac had, as expected, no trouble with this whatsoever. A "set" is really very like an "array of Boolean". A correct solution follows (note that you had only to count the primes, not display the list of them):
import library.*;
class Sieve {
public static void main (String [] args) {
Symset Uncrossed = new IntSet(); // +++++++++
IO.write("Supply largest number to be tested ");
int n = IO.readInt();
int primes = 0;
for (int i = 2; i <= n; i++) {
Uncrossed.incl(i); // +++++++++
}
for (int i = 2; i <= n; i++) {
if (Uncrossed.contains(i)) { // +++++++++
primes++;
int k = i;
do {
Uncrossed.excl(k); // +++++++++
k += i;
} while (k <= n);
}
}
IO.write(primes + " primes between 1 and " + n);
}
}
5. 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? [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;
}
6. The program below gives (most of) the code for a simple interpreter that can react to a sequence of commands given to a "turtle" - for example the sequence
MOVE 10 TURNLEFT MOVE 10 TURNLEFT MOVE 10 TURNLEFT MOVE 10 TURNLEFT WHERE QUIT
will have the effect of tracing out a square of side 10, reporting that the turtle was back at (0, 0) and then stopping.
(a) Which lines of code can be said to perform "lexical analysis". Simply give the line number(s) (for example 17 - 18) but then briefly explain your choice. [3]
Lexical analysis is the phase where characters are assembled into tokens. In this program this happens in lines 21 and 24, where the IO method calls effectively do exactly that.
(b) Which lines of code can be said to perform "syntax analysis". Give the line number(s) (for example 17 - 18) but then briefly explain your choice. [3]
Syntax analysis is where tokens are combined to form recognizable sentences. In this program that effectively happens in lines 22 - 24 where the potential tokens read by the IO methods are compared with the key words to see whether they syntactically form the commands for the turtle (and for interpretation).
(c) Fill in suitable code for the LEFT, RIGHT and MOVE operations. [3+3+6]
See below - lines 33 - 51. Notice that this code uses the names assocoated with the code wherever possible, and not some "magic numbers" directly. Note also that we are assuming a normal coordinate system with x and y measured positive to the right and up, respectively.
1 import library.*;
2
3 public class Turtle {
4 // Simple turtle interpreter
5
6 public static void main(String[] args) {
7 final int
8 East = 0, North = 1, West = 2, South = 3, // directions
9
10 Bad = 0,
11 Left = 1, Right = 2, Move = 3, Home = 4, Where = 5, Quit = 6; // operations
12
13 boolean running = true;
14
15 String[] code = { "", "turnleft", "turnright", "move", "home", "where", "quit" };
16
17 int direction = East;
18 double x = 0.0, y = 0.0, step = 0.0;
19
20 while (running) {
21 code[0] = IO.readWord().toLowerCase().trim();
22 int operation = Quit;
23 while (!code[0].equals(code[operation])) operation--;
24 if (operation == Move) step = IO.readDouble();
25 switch (operation) {
26 case Quit :
27 running = false; break;
28 case Where:
29 IO.write("Now at (x, y) = ("); IO.writeFixed(x, 1, 2);
30 IO.write(" , "); IO.writeFixed(y, 1, 2);
31 IO.writeLine(")");
32 break;
33 case Left :
34 if (direction == South) direction = East; else direction++;
35 // or, more neatly direction = (direction + 1) % 4;
36 break;
37 case Right :
38 if (direction == East) direction = South; else direction--;
39 // or, more neatly: direction = (direction + 3) % 4;
40 break;
41 case Move :
42 // we must now choose which coordinate to alter
43
44 switch (direction) {
45 case East : x += step; break;
46 case North: y += step; break;
47 case West : x -= step; break;
48 case South: y -= step; break;
49 }
50
51 break;
52 case Home:
53 x = 0.0; y = 0.0; direction = East; break;
54 } // switch (operation)
55 } // while (running)
56 } // main
57
58 } // Turtle
(d) Look for simplicity, look for elegance - can you suggest a better way of recording the state of the turtle, and what impact would this have on the interpreter? (Full details are not required - nor is a whole OOP approach!) Hint: Consider how you might extend the possibilities for turning. [4]
The insight I was looking for is that, rather than have an enumeration of possible directions (which does not generalize without fairly major surgery to the code every time you have a New Idea), it is simpler to record the direction as an angle measured in the usual way anticlockwise from the +x axis. School trigonometry then does the rest very easily. The code below shows this idea, as well as a few more enumerated special cases. Remember that you have to convert from the familiar "degrees" into "radians" before you can use the sine and cosine functions.
import library.*;
public class Turtle3 {
// Simple turtle interpreter
// P.D. Terry, Rhodes University, 2010
public static void main(String[] args) {
final double
East = 0.0, // directions
deg90 = Math.PI / 2.0,
deg45 = Math.PI / 4.0;
final int
Bad = 0, // turtle operations
HalfLeft = 1, Left = 2, HalfRight = 3, Right = 4,
Turn = 5, Move = 6, Home = 7, Where = 8, Quit = 9;
boolean running = true;
String[] code = { "", "halfleft", "turnleft", "halfright", "turnright", "turn",
"move", "home", "where", "quit" } ;
double direction = East;
double x = 0.0, y = 0.0, step = 0.0;
while (running) {
code[0] = IO.readWord().toLowerCase().trim();
int operation = Quit;
while (!code[0].equals(code[operation])) operation--;
if (operation == Move) step = IO.readDouble();
if (operation == Turn) step = IO.readDouble() * Math.PI / 180.0;
switch (operation) {
case Quit :
running = false; break;
case Where:
IO.write("Now at (x, y) = ("); IO.writeFixed(x, 1, 2);
IO.write(" , "); IO.writeFixed(y, 1, 2);
IO.write(") Direction = ");
IO.writeFixed(direction * 180.0 / Math.PI, 1, 2); IO.writeLine();
break;
case HalfLeft :
direction += deg45; break;
case HalfRight :
direction -= deg45; break;
case Left :
direction += deg90; break;
case Right :
direction -= deg90; break;
case Turn :
direction += step; break;
case Move :
x += step * Math.cos(direction);
y += step * Math.sin(direction);
break;
case Home:
x = 0.0; y = 0.0; direction = East; break;
} // switch (operation)
} // while (running)
} // main
} // Turtle3