Hand in this prac sheet before lunch time on your next practical day, correctly packaged in a transparent folder with your solutions and the "cover sheet". Unpackaged and late submissions will not be accepted - you have been warned. Please do NOT come to a practical and spend the first hour printing or completing solutions from the previous week's exercises. Since the practical will have been done on a group basis, please hand in one copy of the cover sheet for each member of the group. These will be returned to you in due course, signed by the marker.
In this practical you are to
You will need this prac sheet and your text book. Copies of the prac sheet and of the Parva report are also available at http://www.cs.ru.ac.za/CSc301/Translators/trans.htm.
When you have completed this practical you should understand
This week you are required to hand in, besides the cover sheet:
Keep the prac sheet and your solutions until the end of the semester. Check carefully that your mark has been entered into the Departmental Records.
You are referred to the rules for practical submission which are clearly stated in our Departmental Handbook. However, for this course pracs must be posted in the "hand-in" box outside the laboratory and not given to demonstrators.
A rule not stated there, but which should be obvious, is that you are not allowed to hand in another group's or student's work as your own. Attempts to do this will result in (at best) a mark of zero and (at worst) severe disciplinary action and the loss of your DP. You are allowed - even encouraged - to work and study with other students, but if you do this you are asked to acknowledge that you have done so. You are expected to be familiar with the University Policy on Plagiarism, which you can consult at:
http://www.scifac.ru.ac.za/plag.htm
There are several files that you need, zipped up this week in the file PRAC20.ZIP.
md prac20
cd prac20
copy i:\csc301\trans\prac20.zip
unzip prac20.zip
This will create several other directories "below" the prac20 directory:
J:\prac20
J:\prac20\Assem
J:\prac20\Library
containing the Java classes for the I/O Library, and the Java sources for an assembler/interpreter system equivalent to the C# one described in Chapter 4. The differences between C# and Java are very minimal and it is hoped that you will have no problems in this regard.
Start off by considering the following gem of a Parva program (SEARCH0.PAV)
void main() {
// Read a list of 10 numbers, and then a further list terminated by 99
// find where the numbers in the second list appear in the first list.
// P.D. Terry, Rhodes University, 2007
int item, i;
int[] list = new int[11];
// First read 10 numbers into list[1] .. list[10]
i = 1;
while (i <= 10) {
read(list[i]);
i = i + 1;
}
// Now start the interrogation loop
read("Search for (99 stops)? ", item); // first search item
while (item != 99) {
i = 1;
while (list[i] != item) i = i + 1;
write("Found in position", i, "\n");
read(item); // next search item
}
}
You can compile this (PARVA SEARCH0.PAV) at your leisure to make quite sure that it works.
Firstly, decide why it is an awful program. If you can't see why, try running it - run it anyway, and see if you can break it. What happens? (By "break" I mean "can you run it with some sort of data that allows it to work, and then run it with some data that makes it bomb out?")
In the prac kit there is a better version of the program in the file SEARCH1.PAV. Compile that one, and see if you can break it. If not, you haven't thought hard enough!
In the directory prac20\Assem you will find Java files that give you a minimal assembler and emulator for the PVM stack machine (described in Chapter 4.7). The files have the names
PVMAsm.java a simple assembler
PVM.java an interpreter/emulator very close to the one on page 63
Assem.java a driver program
You can compile and make this assembler/interpreter system by issuing the batch command
MAKEASM
It takes as input a "code file" in the sort of format shown in the examples in section 4.5. There are three very simple example programs in the kit, so make up the minimal assembler/interpreter and try to run them with the ASM batch command:
ASM hello.pvm
ASM lsmall.pvm
ASM divzero.pvm
Wow! Isn't Science wonderful? Try the interpretation with and without the trace option.
Time to do some creative work at last. Task 5 is to produce an equivalent program to the mysterious one below (task.pav), but written directly in the PVM stack-machine language (task.pvm). In other words, "hand compile" the Parva algorithm directly into the PVM machine language. You may find this a bit of a challenge, but it really is not too hard, just a little tedious, perhaps. It might help to try to puzzle out what this program actually does before you begin!
void main () {
// Prac 20 task x
// This comment says it all
// Shud Remeign-Anonymous, Rhodes University, 2007
int a, b;
read(a);
int c = 0;
while (a != 0) {
int d = a;
int e = 1;
read(a);
while (a == d) {
e = e + 1;
read(a);
}
if (e > c) {
b = d;
c = e;
}
}
write(b);
write(c);
}
Health warning: if you get the logic of your program badly wrong, it may load happily, but then go beserk when you try to interpret it. You may discover that the interpreter is not so "user friendly" as all the encouraging remarks in the book might have led you to believe interpreters all to be. Later we shall improve it quite a bit. (Of course, if your machine-code programs are correct you won't need to do so. As it has been said: "Any fool can write a translator for source programs that are 100% correct".)
The most tedious part of coding directly in PVM code is computing the destination addresses of the various branch instructions. As a side effect of assembly, the ASM system writes a new file with a .COD extension showing what has been assembled and where in memory it has been stored. Study of this code will often give you a good idea of what the targets of branch instructions should be.
---- The task.pvm file must be submitted for assessment.
Several of the remaining tasks in this prac require you to examine the machine emulator to learn how it really works, and to extend it to improve some opcodes and to add others.
In the prac kit you will discover two programs deliberately designed to cause chaos. DIVZERO.PVM bravely tries to divide by zero, and MULTBIG.PVM embarks on a continued multiplication that soon goes out of range. Try assembling and interpreting them to watch disaster happen.
Now we can surely do better than that! Modify the interpreter (PVM.java) so that it will anticipate division by zero or multiplicative overflow, and change the program status accordingly, so that users will be told the errors of their ways and not left wondering what has happened.
You will have to be subtle about this - you have to detect that overflow is going to occur before things "go wrong", and you must be able to detect it for negative as well as positive overflow conditions.
Hint: After you edit any of the source code for the assembler you will have to issue the MAKEASM command to recompile it, of course. It's easy to forget to do this and then wonder why nothing seems to have changed.
Section 4.9 of the text discusses the improvements that can be made to the system by adding new single-word opcodes like LDC_0 and LDA_0 in place of double-word opcodes for frequently encountered operations like LDC 0 and LDA 0, and for using load and store opcodes like LDL N and STL N (and, equivalently, opcodes like LDL_0 and STL_0 for frequently encountered special cases).
Enhance your PVM by incorporating the following opcodes:
LDL N STL N
LDA_0 LDA_1 LDA_2 LDA_3
LDL_0 LDL_1 LDL_2 LDL_3
STL_0 STL_1 STL_2 STL_3
LDC_M1 LDC_0 LDC_1 LDC_2 LDC_3
Hint: Adding "instructions" to the pseudo-machine is easy enough, especially as several of the above are very similar to one another, but you must be careful to make sure you modify all the parts of the system that need to be modified. Before you begin, study the code in the definition of the stack machine carefully to see where and how the opcodes are defined, how they are mapped to the mnemonics, and in which switch/case statements they are used.
Try out your system by developing an "improved" version of task.pvm, say task1.pvm, that uses these new opcodes.
If the PVM could only handle characters as well as integers and Booleans, we could write a variation on the program above that dealt with character data rather then integer data. Something like this, if only the Parva compiler were extended to support it (later in the course, perhaps?)
void main () {
// Prac 20 task 8
// This comment says it all
// Shud Remeign-Anonymous, Rhodes University, 2007
char a, b;
read(a);
int c = 0;
while (a != '.') {
char d = a;
int e = 1;
read(a);
while (a == d) {
e = e + 1;
read(a);
}
if (e > c) {
b = d;
c = e;
}
}
write(b);
write(c);
}
No time like the present! Add the opcodes you need to the PVM and get the above program to work properly.
---- The final task2.pvm file and the final assembler/emulator must be submitted for assessment.
You might think it is pretty obvious that using as many one-word opcodes as possible should make your programs smaller, faster, better. Carry out some experiments to see how big this effect is.
In the kit you will find two versions of the infamous Sieve program written in PVM code. S1.pvm uses the original opcode set; S2.pvm uses the new opcodes and is consequently rather shorter. Run both versions through your system and obtain timings for a suitable upper limit (say 1000) and number of iterations (say 2000).
Your emulator will have had to assign enumeration values to the new opcodes. If you study the original source you will see that the original opcodes have been mapped onto the numbers 30 .. 62. You could map your new opcodes onto a set of numbers below 30, or above 62. Try the emulator both ways, and time the programs both ways. Write a paragraph or two presenting the results of this experiment, and try to explain the effects you observe.
Interpreters are easy to develop, but this prac should show you that they are not necessarily very "efficient". What changes could one make to improve the efficiency of the interpreter for the PVM still further?
Think carefully about all this. Please don't think you can write two lines of utter rubbish three minutes after you were supposed to hand the prac in, and try to bluff me that you know what is going on!
Hand translate the following program into PVM code to produce a simple truth table for illustrating De Morgan's laws.
void main () {
/* This won't compile, but the idea should be obvious
P.D. Terry, Rhodes University, 2007 */
bool X, Y;
write(" X Y (X.Y)' X'+Y' (X+Y)' X'.Y'\n\n");
X = false;
repeat
Y = false;
repeat
write(X, Y, !(X && Y), !X || !Y, !(X || Y), !X && !Y, "\n");
Y = ! Y;
until (!Y); // again
X = ! X;
until (!X); // again
}
---- The final bool.pvm must be submitted for assessment.
Task 11 is to learn to work with arrays in the PVM by producing an equivalent program to search1.pav, but written directly in PVM code.
---- The final search.pvm must be submitted for assessment.
Have fun, and good luck.