Solutions
This should take no longer than 45 minutes and is simply 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).
"The purpose of computing is insight, not numbers" (Richard Hamming)
1. You should get this right! Mine is Pat Terry, 63T0844. What is yours? [1]
Pat Terry, 63T0844. Student name and student number! And it is genuine. Note that your student number normally just has two digits (63) for the year of first registration, the initial letter of the surname, and a four digit number for the number of applications that had been received when yours was processed. the number is often quoted with a further leading 6 (as in 663T0844), but this is a hangover from the days when we had campus 6 (Grahamstown) and campus 8 (East London). No, I don't know, so don't ask!
2. What is the significance of each of the numbers 16384, 32767, 16411, and why? (Be careful!) [4]
16384 is 214. It is the number of unique values that one could represent directly using a 14 bit bitstring..
32767 is 215 - 1. It is the largest positive integer one could represent in twos complement with a 16 bit machine/bitstring.
16411 is the largest prime one can identify easily using the Sieve method on a 16 bit machine. 16411 * 2 = 32822 which is the first number one would try to "cross out" after detecting 16411, and this is larger than 32767. You should have discovered this in the prac!
3. Here is a simple Parva program (assume it is stored in the file Silly.pav):
void main() {
// A rather simple Parva program - but what does it calculate?
int a, b;
read("Supply a and b (0 stops) ", a, b); /* first pair of data */
while (a != 0) {
int c = a - a / b * b;
write(a, b, c);
read(a, b); // read the next data pair
}
} // main
(a) What does it attempt to calculate and print? [2]
The remainder when a is divided by b (integer arithmetic), that is a % b . It was alarming how many students seem not to understand (or know about) "integer" arithmetic and how it differs from "double" arithmetic.
(b) It would not execute sensibly if it were given the data pair { 8 , 0 } for fairly obvious reasons. Would you classify such a fault as an example of an syntactic error, a static semantic error. or a dynamic semantic error - and why? [2]
A dynamic semantic error. It could not be detected at compile time - although a more friendly program would have built in a runtime check of its own, perhaps, rather than letting a user crash and burn:
void main() {
// A rather simple Parva program - but what does it calculate?
int a, b;
read("Supply a and b (0 stops) ", a, b); /* first pair of data */
while (a != 0) {
if (b != 0) {
int c = a - a / b * b;
write("When ", a, "/", b, " the remainder is ", c);
}
if (b == 0)
write("When ", a, "/", b, " the remainder is undefined");
read(a, b); // read the next data pair
}
} // main
If you were to translate this program to Java using the Parva2ToJava program, it would produce the following code (Silly.java):
import library.*;
class Silly {
static public void main(String[] args) {
int a, b;
{ IO.write("Supply a and b (0 stops) "); a = IO.readInt(); b = IO.readInt(); }
while (a != 0) {
int c = a - a / b * b;
{ IO.write(a); IO.write(b); IO.write(c); }
{ a = IO.readInt(); b = IO.readInt(); }
}
} // main
} // Silly
This seems to have lost something (the comments) and gained something (extra, apparently unnecessary, braces { } ) - it might be preferable to have generated code like this:
import library.*;
class Silly {
static public void main(String[] args) {
// A rather simple Parva program - but what does it calculate?
int a, b;
IO.write("Supply a and b (0 stops) ");
a = IO.readInt(); b = IO.readInt(); /* first pair of data */
while (a != 0) {
int c = a - a / b * b;
IO.write(a); IO.write(b); IO.write(c);
a = IO.readInt(); b = IO.readInt(); // read the next data pair
}
} // main
} // Silly
(c) Is the loss of the comments critical? Why, or why not? [2]
No, it is not critical - the Java code that is generated does not have to be read by a human (except for fun). The idea is that it is immediately passed to a Java compiler which would have ignored comments in any case. In fact, retaining the comments is in principle easy to do, but in practice a bit messy as they can get separated from the code to which they apply. We may try to show this in a later practical.
(d) Might the extra { braces }, in fact, be necessary in such translations? Explain! [4]
Read and write statements in Parva are translated easily enough into a series of calls to library functions. But they still have to be regarded as single statements. Here's an example of where leaving out the braces would get you into trouble - and the code in the improved program in 3(b) would provide another one.
while (a != 0)
read(a, b);
Were this to be translated as
while (a != 0)
a = IO.readInt(); b = IO.readInt();
the semantics of the while loop would be quite incorrect - even though it might "look" okay. If you can't see why, you'd better come to ask about it, having first cleared your mind of Python funny ideas.
(e) If you executed the sequence of commands
(a) Parva2ToJava Silly.pav -l
(b) Parva Silly.pav -l
(c) Javac Silly.java
(d) Java Silly
at which stage(s) would an error like that suggested earlier in (b) become apparent, and in what way would it be reported? [4]
(b) When the interpreter runs - reports "division by zero at NNN" referred to the PVM address
(d) Raises an exception "division by zero" related to the JVM address - not helpful to the Parva programmer
4. Question 3(e) mentions four systems programs. Classify each one as being either (a) a native code compiler (b) an interpretive compiler (c) an interpreter (d) a high-level compiler (e) an assembler or (f) a decompiler. [4]
(a) Parva2Java High-level compiler - produces Java "object" code
(b) Parva Interpretive compiler - produces PVM code
(c) Javac Interpretive compiler - produces JVM "bytecode"
(d) Java Interpreter - interprets JVM bytecode
5. The Parva2Java translator was developed in C# and translates Parva programs to their Java equivalents. Presumably - since C# and Java are so similar - one could now use it as a model and develop a Parva2ToCSharp (P2C) translator using Java, to translate a Parva program to a C# equivalent (and do this conversion quite quickly !) quickly. Complete the following T Diagrams to show how this might be done and how P2C might be used: [8]
.--------------------------. .--------------------------.
| P2C.java | | P2C.class |
| Parva ----------> C# | | Parva ----------> C# |
| | | |
`-------. .--------------------------. .-------'
| | Javac | |
| Java | Java --------> JVM | JVM |
| | | |
`------------------. .------------------'
| |
| JVM |
| |
|----------|
| JVM |
| Interpr |
| Intel |
|----------|
| |
| Intel |
| |
`----------'
.--------------------------. .--------------------------. .--------------------------.
| Sieve.pav | | Sieve.cs | | Sieve.exe |
| N ----------> Primes| | N -----------> Primes| | N ---------> Primes|
| | | | | |
`-------. .--------------------------. .--------------------------. .-------'
| | P2C.class | | CSC.exe | |
| Parva | Parva --------> C# | C# | C# --------> Intel | Intel |
| | | | | |
`------------------. .--------------------------. .-------+----------|
| | | | | |
| JVM | | Intel | | Intel |
| | | | | |
|----------| |----------| `----------'
| JVM | | |
| Interpr | | Intel |
| Intel | | |
|----------| `----------'
| |
| Intel |
| |
`----------'
6. Here's another simple Parva program - the sort you might find a first year student writing:
bool b(int n) {
return n == i(n);
} // b
int i(int n) {
int r = 0;
while (n != 0) {
r = 10 * r + n % 10;
n = n / 10;
}
return r;
} // i
void main() {
int n;
read("Supply n (0 stops) ", n);
while (n != 0) {
write(b(n));
read(n);
}
} // main
Simplicity is sometimes deceptive!
So it appeared! It was depressing how few people could "decode" this simple algorithm. Have you not learned how to "play computer"?
(a) What do you suppose the program is meant to achieve? [2]
It reads a list of integers and tells you whether each is a palindrome (like 12321 or 44 or 686)
(b) Suggest better names for the identifiers used for the functions/methods. [2]
Function b would be better named isPalindrome
Function i would be better named reverse
(c) Why would this code not compile with the Parva compiler you have been using? [2]
Because in Parva all identifiers, even methods, must be declared before use, and because there is no
% operator - as you should have discovered in the recent prac. In fact many submissions recognized
this, but I don't know that anyone spotted that the "declare before use" requirement" had not been
met. Surely you knew this from the Parva programs you had been asked to write? There were some
interesting wrong answers (guesses?). One does not need parentheses around the expression in a
return statement, for example.
(d) How could you correct it so that it would compile and execute satisfactorily? No, you don't have to rewrite it completely. The answer is very simple! [3]
int reverse(int n) {
// Returns the number formed by reversing the decimal digits of n
int r = 0;
while (n != 0) {
r = 10 * r + n - n / 10 * 10; // order important!
n = n / 10;
}
return r;
} // reverse
bool isPalindrome(int n) {
// Returns true if and only if n is a decimal palindrome like 12321 or 556655
return n == reverse(n);
} // isPalindrome
void main() {
// Examines a list of integers to see which are palindromes
int n;
read("Supply n (0 stops) ", n);
while (n != 0) {
write(isPalindrome(n));
read(n);
}
} // main
(e) What do you suppose is the Big Idea I am trying to get across to you in this question? [1]
That all programs should have adequate commentary and well chosen identifiers. I suspect that had I
added commentary and given the methods decent names you would immediately have "understood"
what was intended.