1. I have a memory like my friend Eratosqenes and his sief and cannot remember - remind me of your name (surname) and student number [1]
Pat Terry 63T0884
2. In the prac you were invited to note that sequences like
LDA X and LDA Y LDV <code> STO
occurred so frequently that it might be worth introducing special opcodes LDL X and STL Y instead. By now you will recognise something of the Terry perversity - maybe the machine is defined to have LDA, LDV and STO opcodes rather than simply having only LDL and STL opcodes for no other reason than that it makes for lots of fun late at night to add these opcodes to the machine. But maybe not? If you have LDL and STL, could you completely remove LDA, LDV and STO from the opcode list, or would you still need to have them available? Justify your answer. [2]
If every LDV was preceded by an LDA one could get away with using LDL instead of LDA + LDV, and if every other use of LDA was followed by a STO one could get away without LDA. But this is not the case. Consider the following code:
read(i); list[i] = list[j];
which, even if we use every LDL and STL we can, translates to
LDA i INPI ; read(i) LDL list LDL i INXA ; address of list[i] LDL list LDL j INXA ; address of list[j] LDV ; value of list[j] STO ; list[i = list[j]
3. Translate the following program into PVM code, making use of the INC, LDL and STL opcodes [10]
void main () { int i; bool[] odd = new bool[1000]; for (i = 0; i < 1000; i++) odd[i] = i % 2 != 0; }
Two solutions are given. The one on the left is a literal translation, that on the right is slightly optimized, taking advantage of the fact that a "mod 2" operation yields a 1 for odd numbers, which happens also to be the representation of true. Some submissions showed that their authors are uncomfortable with Boolean assignments.
0 DSP 2 int i; bool[] odd 0 DSP 2 int i; bool[] odd 2 LDC 1000 2 LDC 1000 4 ANEW 4 ANEW 5 STL 1 odd = new bool[1000] 5 STL 1 odd = new bool[1000] 7 LDC 0 7 LDC 0 9 STL 0 i = 0; 9 STL 0 i = 0; 11 LDL 0 11 LDL 0 13 LDC 1000 13 LDC 1000 15 CLT 15 CLT 16 BZE 37 while (i < 1000) { 16 BZE 34 while (i < 1000) { 18 LDL 1 18 LDL 1 20 LDL 0 20 LDL 0 22 LDXA 22 LDXA 23 LDL 0 23 LDL 0 25 LDC 2 25 LDC 2 27 REM 27 REM 28 LDC 0 28 STO odd[i] = i % 2 != 0; 30 CNE 29 LDA 0 31 STO odd[i] = i % 2 != 0; 31 INC i++; 32 LDA 0 32 BRN 11 } 34 INC i++; 34 HALT 35 BRN 11 } 37 HALT
4. From those dim distant maths classes at school you should recall the geometrical theorem of another Great Greek, one Pythagoras, to the effect that if the lengths of the sides of a right angled triangle are denoted by a, b and h (h being the hypotenuse - the side opposite to the right angle) then a2 + b2 = h2.
The following Parva program takes it upon itself to read triples of numbers and determine whether they have this property.
void main () { // Test triples of numbers to see if a right angled triangle // could be constructed from them // P.D. Terry, Rhodes University, 2006 int a, b, h; read(a); while (a > 0) { read(b, h); write(a, b, h); if (a * a + b * b == h * h) write(" form a right angle triangle\n"); else write(" do not form a right angle triangle\n"); read(a); } }
Now if the PVM were given a bit more functionality - an opcode to perform a squaring operation - we might be able to simplify this to:
void main () { // Test triples of numbers to see if a right angled triangle // could be constructed from them // P.D. Terry, Rhodes University, 2006 int a, b, h; read(a); while (a > 0) { read(b, h); write(a, b, h); if (sqr(a) + sqr(b) == sqr(h)) write(" form a right angle triangle\n"); else write(" do not form a right angle triangle\n"); read(a); } }
(a) What changes would you have to make to the switch statement in the PVM emulator in the Assembler system you have been using to support such an additional opcode? [3]
The best solution is simply to provide an opcode for squaring the number on the top of stack. This is better than having an opcode like SQR N where N is the offset of a simple variable, because it allows for easy handling of a square as part of a general expression - for example sqr(a+b) or sqr(a + sqr(c/2)).
case PVM.sqr: // square tos = pop(); push(tos * tos); break;
Several submissions suggested that one should do a range check:, which was impressive:
case PVM.sqr: // square tos = pop(); if (tos != 0 && Math.abs(tos) > maxInt / Math.abs(tos)) ps = badVal; else push(tos * tos); break;
but there were several submissions that popped too many values:
case PVM.sqr: // square - this one is WRONG push(pop() * pop()); break;
(b) Would you have to make any other changes to the PVM.java file to support the extension? Explain your thinking! [2]
We need to add SQR to the list of opcode/string pairs at the end of the PVM.java file, and add a line giving the numeric equivalent to the list near the beginning. Since it is a one-word opcode, no other changes are needed (in contrast to the additon of codes like STL N and LDL N).
(c) Translate the second Parva program above into PVM code, making use of your new opcode, and also of the STL and LDL opcodes discussed in question 2. (Hint: this can be done in about 33 lines.) [12]
This was generally very well done. However, to my dismay, several submissions whose authors should have known better suggested that reading was achieved with code like
LDA 0 INPI read(a); STO WRONG
or even
INPI read(a); STL O WRONG
which rather suggested to me that they could not possibly have had many ideas about how to write the PVM code in the pracs! And, oh dear, there was some dreadful "spaghetti code" submitted. A simple, straightforward translation is actually easier to write and to understand.
; Test triples of numbers to see if a right angled triangle ; could be drawn from them ; P.D. Terry, Rhodes University, 2006 0 DSP 3 int a, b, h; 2 LDA 0 4 INPI read(a); 5 LDL 0 7 LDC 0 9 CGT 10 BZE 51 while (a > 0) { 12 LDA 1 14 INPI read(b); 15 LDA 2 17 INPI read(h); 18 LDL 0 20 PRNI write(a); 21 LDL 1 23 PRNI write(b); 24 LDL 2 26 PRNI write(h); 27 LDL 0 29 SQR // a*a 30 LDL 1 32 SQR // b*b 33 ADD // sqr(a) + sqr(b) 34 LDL 2 36 SQR // h*h 37 CEQ if (sqr(a) + sqr(b) == sqr(h)) 38 BZE 44 write(" form a right angle triangle\n"); 40 PRNS " form a right angle triangle\n" 42 BRN 46 else write(" do not form a right angle triangle\n"); 44 PRNS " do not form a right angle triangle\n" 46 LDA 0 48 INPI read(a); 49 BRN 5 } 51 HALT