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 - in the same format? [2]
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. Here is a simple C# statement sequence
if (s != 0 && t/s > 8) ; else IO.WriteLine("wrong");
Is this sequence syntactically correct? If not, why not? [2]
Yes, it is correct, if a little odd. The "stray" semicolon is actually an empty statement. The effect is that if the condition evaluates to true, nothing is executed; if it is false the "else" clause executes and the string "wrong" will be output. Stray semicolons can be a source of very hard to find bugs. How about this empty while loop:
i = 2;
while (i < 10) ;
IO.WriteLine(++i):
which forms an infinite loop and never reaches the write statement (I hope you see why). And if we were to try to compile a similar example, but with another semicolon:
if (s != 0 && t/s > 8) ; ; else IO.WriteLine("wrong");
the compiler would see it as an "if" statement with no "else" part, and then complain because the
else IO.WriteLine("wrong");
is not an acceptable statement - an "else" clause cannot form a standalone statement, it can only be part of an "if-else" statement.
Assuming it is syntactically correct, is this sequence necessarily statically semantically correct? If not why not? [2]
No. If s and t had been declared as arithmetic types of some sort the statement would be statically semantically correct. But if one or the other or both had been declared to be of types on which arithmetic could not be performed the compiler would indicate some breach of static semantic rules. Interestingly, besides allowing int, float, double types in mathematical expressions, C# would allow you to intermingle char values as well, which would be anathema in some other programming languages.
Assuming correctness so far, is it possible for its dynamic semantics to be in error? Explain. [2]
Yes. If the compiler did not implement "short-circuit" semantics (most do, but there are some languages that don't insist on them) then, were s to have the value 0, some sort of "division by zero" catastrophe should occur.
3. What distinguishes a compiler from an assembler? [2]
Generally speaking a compiler can be assumed to be a translator that converts programs written in a high level language to semantically equivalent programs in machine code. An assembler converts programs written in an assembler-level source language to their semantic equivalents in a machine code. The word compiler is also used with descriptors like "high-level" or "cross" or "self-resident".
4. What distinguishes a self-resident compiler from a cross-compiler? [2]
A self-resident compiler (or assembler) generates code ready to run on the same machine as hosted the compiler itself; a cross-compiler generates code for a different sort of machine. Cross compilers are useful in "porting" compilers to run on new architectures (as discussed in question 6).
5. Suppose that you submit the following simple program to the ParvaToCSharp system.
const first = 75, second = 60;
void Main() {
// Simple example of Parva program to be converted to C#
int class = 3;
int mark, firsts;
read("Supply mark earned", mark);
if (mark >= first) { class = 1; firsts = firsts + 1; };
if (mark >= second) class = 2;
write(mark, " falls in class ", class);
} // Main
It would produce the following output. Criticize the translation. What does this tell you about using a tool like this? Do you suppose the tool could have been improved? How? [8]
using Library;
class demo {
static const int first = 75;
const int second = 60;
static public void Main(string[] args) {
int class = 3;
int mark, firsts;
{ IO.Write("Supply mark earned"); mark = IO.ReadInt(); }
if (mark >= first) {
class = 1;
firsts = firsts + 1;
};
if (mark >= second)
class = 2;
{ IO.Write(mark); IO.Write(" falls in class "); IO.Write(class); }
} // Main
} // demo
One is quickly aware that this seems to have lost something (the comments) and gained something (extra, apparently unnecessary, braces { } ), and many students commented on those aspects, but not always accurately.
Nobody noticed that it would be impossible to be awarded a first class (a mark greater than a first is also greater than a second, and the tests are done in the wrong order) although that is irrelevant here. There were some complaints about the stray semi-colon after a closing brace in the while loop, but it was in the original and causes no harm in the derived program either.
The output is quite badly non-C# when you look a little closer. In C# the word "class" is a key word and cannot be used as a variable name. The "static const" modifier for "first" is just plain wrong. Rather more subtly, the statement incrementing firsts would be picked up by a C# compiler as an illegal attempt to use the value of an uninitialized variable when forming the expression firsts + 1. Very few people would spot that one.
Okay, so what about the other points?
The comments. Well, I guess it all depends on how one is going to use a tool of this nature. There are two possibilities, each with a different emphasis. One might want to use it to translate readable Parva into highly readable C#, perhaps because one was rewriting a Parva text book. In that case you would probably want the converter to retain the comments. But you might also consider using it simply to act as a compilation front end to a C# compiler - for example to allow you to develop programs in Parva and then compile their C# equivalents for greater run time efficiency. In that case it wouldn't matter if the comments were there, because compilers ignore comments anyway.
In either case, you would want a correct translation. The incorrect "static" modifier is just a bug left in the system that wasn't picked up in initial testing. Maybe I (or even you) will fix this later in the course as a prac exercise.
More annoying is the fact that some words acceptable to Parva as identifiers (like class) are not acceptable to C#. What can we do about this? Well, two strategies suggest themselves. One might check every identifier as the translation process went along to see if it was in the list of banned keywords - or one could simply alter every identifier internally, say by putting an underscore at the end of it, which would also get around the problem. The resulting code might look_ a_ bit_ funny_, but hey, does it matter? All you want is a correct C# program with the correct semantics.
The discussions about the extra { braces } were interesting, but often displayed a naïvity which is understandable at this stage. Extra { braces } in the source code won't slow execution down at all. They are just punctuation marks for the benefit of the compiler as it tries to analyse the statement structure. They don't generate code at all!
Turning a Parva "write" statement with multiple parameters into multiple write statements each with single parameters is also unlikely to do much damage. When you think about it, a statement like
IO.WriteLine("The answer is " + answer + " which is " + correct);
really has to be able to handle four parameter values - string, integer, string, boolean - each of which will call on specialist services in some sort of library.
So why insert the extra { braces }? Might they, in fact, be necessary in some translations?
You have to be quite astute to see why. The apparently redundant { braces } in this example preserve the atomicity of the translated read and write statements, which in Parva can have multiple parameters, unlike the single-parameter ones in the IO library. In the above example they don't matter, but consider the example:
Expressed in Parva which becomes, in C#, if the braces are discarded
if (a > b) if (a > b)
write(a, b, a/b); IO.Write(a);
IO.Write(b);
IO.Write(a/b);
6. Suppose in your first job as a professional compiler writer you are provided with (a) a compiler for the C language that can run on the PC and (b) the source code of this compiler, also written in C. Draw T diagrams to represent these tools:
Fortunately most students got this first step. Any who didn't must be badly confused.
┌──────────────────────────┐ ┌──────────────────────────┐
│ Compiler (a) │ │ Compiler (b) │
│ C ──────────> PC │ │ C ──────────> PC │
│ │ │ │
└───────┐ ┌───────┘ └───────┐ ┌───────┘
│ │ │ │
│ PC │ │ C │
│ │ │ │
└──────────┘ └──────────┘
The "native code" compiler (Self resident) The source version which can act as a model
You are asked to write a compiler for the popular new language D (similar to C) to run on the PC and compile D programs to run on the PC. Draw T diagrams showing what you decide to do:
Write a compiler that will translate D code to PC code, using the source of the C compiler (b) as a model - change the front end to accept the new syntax for D. With luck the back end will be very similar since you are targetting the same machine. Compile this with compiler (a) and in principle you are in business.
┌──────────────────────────┐ ┌──────────────────────────┐
│ │ │ Compiler (n) │
│ D ──────────> PC │ │ D ──────────> PC │
│ │ │ │
└───────┐ ┌───────┴──────────┴───────┐ ┌───────┘
│ │ Compiler (a) │ │
│ C │ C ────────> PC │ PC │ <──── This is the new compiler (call it n), and
│ │ │ │ now you will be able to run this one
└──────────┴───────┐ ┌───────┴──────────┘ too - on the PC of course.
│ PC │
│ │
├──────────┤ <─────── This is Compiler (a), the only one you can run initially
│ │
│ PC │
└──────────┘
Your supervisor is most impressed at what you produce. So she should be, as you are a survivor of CSC 301. She now sets you another task - write a D compiler for the new HVZ computers that are the latest craze and will replace the PCs next year. Continue to impress her - draw and annotate T diagrams to show how you intend to proceed.
Many students were hopelessly confused about what to do next. It had all been discussed on the handout which you were given, which described how to generate a compiler for the Great language on the new Tiny machine. So you might like to look at that one again too. Handouts are there to study, not to ignore!
We now have two compilers that we can run - (a) and (n) - as well as the source of both of these compilers, both expressed in C. Compiler (n) can't be used to compile its source, because it can only compile programs written in D.
Now take the source code of (n) and rewrite it manually in D (D is similar to C so this should not be too hard to do. At the time you are doing this, change the back end of compiler (n) to produce HVZ code, and realize that you have somehow to use that to produce a D to HVZ compiler that can run on an HVZ machine.
┌──────────────────────────┐ ┌──────────────────────────┐
│ (source for D to HVZ) │ │ Compiler (d) │
│ D ──────────> HVZ │ │ C ──────────> PC │
│ │ │ │
└───────┐ ┌───────┘ └───────┐ ┌───────┘
│ │ │ │
│ D │ │ C │
│ │ │ │
└──────────┘ └──────────┘
The D source of a D to HVZ compiler Wanted: A self-resident D compiler for the new machine
Two steps are needed. Firstly, we compile the D source using Compiler (n) on the PC which is at our disposal. This only gets part of the way - in fact, it produces a cross-compiler.
┌──────────────────────────┐ ┌──────────────────────────┐
│ (source for D to HVZ) │ │ Compiler (x) │
│ D ──────────> HVZ │ │ D ──────────> HVC │
│ │ │ │
└───────┐ ┌───────┴──────────┴───────┐ ┌───────┘
│ │ Compiler (n) │ │
│ D │ D ────────> PC │ PC │
│ │ │ │
└──────────┴───────┐ ┌───────┴──────────┘
│ PC │
│ │
├──────────┤
│ PC │
└──────────┘
One more step to go. Run Compiler (x) on the PC (the only machine that can run it) and let it compile the same source that was used to create this cross compiler itself:
┌──────────────────────────┐ ┌──────────────────────────┐
│ (source for D to HVZ) │ │ Compiler (d) │
│ D ──────────> HVZ │ │ D ──────────> HVZ │
│ │ │ │
└───────┐ ┌───────┴──────────┴───────┐ ┌───────┘
│ │ Compiler (x) │ │
│ D │ D ────────> HVZ │ HVZ │ <── We got it at last - a nice new
│ │ │ │ self-resident D to HVZ compiler!
└──────────┴───────┐ ┌───────┼──────────┤
│ PC │ │ HVZ │
│ │ └──────────┘
├──────────┤
│ PC │
└──────────┘
Several students suggested using some tool that would convert PC code to HVZ code at the low level. Well, one could follow this approach though it is not ideal. You would first have to develop that translator, and students who tried this route invariably assumed its existence and didn't show how to develop it...
7. A reminder of the methods in the IntSet class appears below.
public class IntSet {
public IntSet()
public IntSet(BitSet s)
public IntSet(params int[] members) {
public IntSet(int ... members)
public void Incl(int i)
public void Excl(int i)
public bool Contains(int i)
public bool 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 program below should be easy enough to understand!
// A class tries to guess their lecturer's age
// P.D. Terry, Rhodes University, 2016
using Library;
class AgeGuess {
public static void Main (string [] args) {
int total = 0, guesses = 0;
int guess = IO.ReadInt("Supply first guess (0 stops) ");
while (guess > 0) {
total = total + guess;
guesses++;
IO.Write("Supply next guess (0 stops) ");
guess = IO.ReadInt("Supply next guess (0 stops) ");
}
int average = total / guesses;
int actualAge = IO.ReadInt(""Supply lecturer's actual age");
if (average <= actualAge)
IO.WriteLine("You flatter me");
else
IO.WriteLine("Some DPs will have to be withdrawn");
} // Main
} // AgeGuess
Without changing the order of any of the code given here, show how the use of a set can give a very simple way of detecting and reporting (a) whether any students actually guessed the average age (b) whether any students correctly guessed the lecturer's age (c) how many different guesses were made. (Simply add the few necessary extra statements into their correct places.) [8]
This problem is ideally suited to being solved by using a set. Think of a set as a kind of bag into which you can throw similar things - in this case, numbers. The important thing about a set is that a "thing" is either in the bag or is not. You can try to add another "copy" of a "thing" already there, but it makes no attempt to record how many of each thing have been included, just whether any of that thing have been included. So, as many students saw, we just declare an appropriately named IntSet object, and then include each guess made at the lecturer's age as they are read. At the end of this loop, the number of elements in the set will then be exactly what we want - the number of different guesses. To compute the average we still have to have added all the guesses together and divided by the total number of guesses. In general, we can't simply divide the total by the number of members of the set (the number of different guesses): this would only give the right answer if all the guesses happened to be different. Notice also that we take care not to include the zero at the end of the list, which isn't supposed to be a guess at all.
A disappointing number of students made no attempt to answer this question. Probably many of them had not got very far with the Sudoku-based problem in the practical either?
// A class tries to guess their lecturer's age
// P.D. Terry, Rhodes University, 2016
using Library;
class AgeGuess {
public static void Main (string [] args) {
int total = 0, guesses = 0;
IntSet uniqueGuesses = new IntSet(); // create the set of guesses
int guess = IO.ReadInt("Supply first guess (0 stops) ");
while (guess > 0) {
uniqueGuesses.Incl(guess); // record this guess - maybe again
total = total + guess;
guesses++;
guess = IO.ReadInt("Supply next guess (0 stops) ");
}
int average = total / guesses; // still compute the average the hard way
int actualAge = IO.ReadInt("Supply lecturer's actual age");
if (average <= actualAge)
IO.WriteLine("You flatter me");
else
IO.WriteLine("Some DPs will have to be withdrawn");
if (uniqueGuesses.Contains(average)) // now report on the statistics
IO.WriteLine("At least one student guessed the average of all the guesses");
if (uniqueGuesses.Contains(actualAge))
IO.WriteLine("At least one student guessed the lecturer's age correctly");
IO.WriteLine(uniqueGuesses.Members() + " different guesses were made by " + guesses + " students");
} // Main
} // AgeGuess