Examiners: Time 4 hours Prof P.D. Terry Marks 180 Prof P. Blignaut Pages 14 here
Several of the questions in this paper are designed to probe your insight - your depth of understanding of the important principles that you have studied in this course. If, as we hope, you have gained such insight, you should find that the answers to many questions take only a few lines of explanation. Please don't write long-winded answers - as Einstein put it "Keep it as simple as you can, but no simpler".
Good luck!
QUESTION 1 - Equivalent grammars, Ambiguous grammars, and LL(1) grammars. [19 Marks]
A, B and C represent three attempts to write a grammar to define a list of household pets, such as
cat, dog, dog, dog or dog, cat, dog or cat
A: Pets = Pet { "," Pet } .
Pet = "dog" | "cat" .
B: Pets = Pets "," Pets | Pet .
Pet = "dog" | "cat" .
C: Pets = { Pet "," } Pet .
Pet = "dog" | "cat" .
(a) Define what is meant by the statement "Two grammars are equivalent". [2 Marks]
(b) Which (if any) of grammars A, B and C are equivalent? [3 Marks]
╓─────────┬───╥─────────┬───╥─────────┬───╥─────┬───╥──────┬───╥────────────┬───╖ ║ A and B │ ║ B and C │ ║ C and A │ ║ all │ ║ none │ ║ don't know │ ║ ╙─────────┴───╨─────────┴───╨─────────┴───╨─────┴───╨──────┴───╨────────────┴───╜
(c) Define what is meant by the statement "A grammar is ambiguous"? [2 Marks]
(d) Which (if any) of grammars A, B and C are ambiguous? [3 Marks]
╓───┬───╥───┬───╥───┬───╥─────────┬───╥─────────┬───╥─────────┬───╥─────┬───╥──────┬───╥────────────┬───╖ ║ A │ ║ B │ ║ C │ ║ A and B │ ║ B and C │ ║ C and A │ ║ all │ ║ none │ ║ don't know │ ║ ╙───┴───╨───┴───╨───┴───╨─────────┴───╨─────────┴───╨─────────┴───╨─────┴───╨──────┴───╨────────────┴───╜
(e) For each ambiguous grammar, give a string of pets that would back up your claim, and justify it. [3 Marks]
(f) Which (if any) of grammars A, B and C obeys the LL(1) rules? [3 Marks]
╓───┬───╥───┬───╥───┬───╥─────────┬───╥─────────┬───╥─────────┬───╥─────┬───╥──────┬───╥────────────┬───╖ ║ A │ ║ B │ ║ C │ ║ A and B │ ║ B and C │ ║ C and A │ ║ all │ ║ none │ ║ don't know │ ║ ╙───┴───╨───┴───╨───┴───╨─────────┴───╨─────────┴───╨─────────┴───╨─────┴───╨──────┴───╨────────────┴───╜
(g) For each grammar that is not LL(1), explain why not. [3 Marks]
QUESTION 2 - Suitable/Correct Grammars and LL(1) Grammars. [20 Marks]
The following Cocol grammar attempts to describe a freight train.
COMPILER Trains $C // in file Trains.atg
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Trains = { Train } EOF .
Train = "loco" { "loco" } [ Load ] SYNC "." .
Load = [ Safe { { "fuel" } Safe } ] "brake" .
Safe = "open" | "closed" .
END Trains.
A freight train is headed by one or more locos (which in the simplest case might not have any trucks behind them). Trucks following a loco are of three kinds: fuel trucks, open trucks and closed trucks. A brake van always brings up the rear. There is a safety rule that forbids a fuel truck to be placed immediately behind a loco, or immediately in front of the brake van. Examples of valid trains might be
loco open open closed brake .
loco loco open fuel open fuel closed brake .
while examples of invalid trains might be
loco fuel open fuel fuel open brake .
loco open fuel fuel closed fuel brake .
(a) Give a reason why the LL(1) property for a grammar is desirable. [2 Marks]
(b) Besides just submitting this grammar to Coco/R and getting a clean bill of health, argue in detail in support of its being an LL(1) grammar. [8 Marks]
(c) What is the technical name given to an element like $C that is found in the first line of this grammar? [2 Marks]
(d) What is the effect of including $C in the file Trains.atg? [2 Marks]
(e) What is the effect of including SYNC in the production for Train? [2 Marks]
(f) Why do the following alternatives for the Load production give grammars that fail to define the set of all valid freight trains? Illustrate by giving examples of trains which would either be accepted when they should not be, or would not be accepted when they should be. [4 Marks]
Load = [ Safe { [ "fuel" ] Safe } ] "brake" .
Load = Safe [ { Safe | "fuel" } Safe ] "brake" .
QUESTION 3 - Do the work of the HR division. [15 Marks]
A highly respected university not a million kilometres from here maintains a highly confidential file with details of some highly competent staff members with their highly regarded qualifications. A portion of this reads as follows (filed as STAFF.TXT).
Professor P. D. Terry, MSc(RU), PhD (Cantab) .
George Clifford Wells, BSc(Hons), MSc, PhD .
Greg G. Foster, PhD .
Dr Sizwe G. Mabizela .
Dave A. Sewry, PhD .
Prof Karen Lee Bradshaw, MSc, PhD(Cantab) .
Professor G.E. Gordon, MA(CNAA) .
Mrs Caro Watkins, BSc(UCT) .
Yusuf Motara, MSc (Rhodes).
Your Name One Day Soon, BSc (Rhodes).
Prof Mark Bunting, BSc(InfProc), MCom.
Mx Mic Halse .
Dr Colleen Vassiliou, PhD.
Ms Des Wicks.
The ever-inquisitive HR Division imagines the need to prepare two simple lists, one of all the staff who do have a PhD, and the other of all the professors who don't have a PhD. For the above data the two lists would be something like
Dr Terry Prof Gordon
Dr Wells Prof Bunting
Dr Foster
Dr Mabizela
Dr Sewry
....
Note that some staff with PhDs are addressed as Dr, while others (like professors) may have the qualification explicitly listed. Regardless of any other title they have, such people are always entitled to be called Dr, of course!
Develop an application to satisfy this request, extending the following Cocol specification, which is presently incomplete (filed as STAFF.ATG). Keep it simple - there is no need to parameterize the productions! The CMAKE script can be used to build your system in a familiar way should you wish to test your solution.
using System.Collections.Generic;
using Library;
COMPILER Staff $CN
/* Describe a list of staff at this university for example
Prof G.C. Wells, PhD(Bristol) .
Prof K.L. Bradshaw, MSc(Rhodes), PhD(Cantab) .
Ms Des Wicks.
Original by P.D. Terry, Rhodes University, 2015 */
static List<string> StaffWithPhD = new List<string>();
static List<string> ProfsWithoutPhD = new List<string>();
// Other global variables may be needed here - keep it simple
CHARACTERS
uLetter = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" .
lLetter = "abcdefghijklmnopqrstuvwxyz" .
letter = uLetter + lLetter .
TOKENS
name = uLetter { letter } . // eg Thabo
initial = uLetter "." . // eg X.
varsity = "(" uLetter { letter } ")" . // eg (UCT) or (Stell)
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Staff
= { Person }
EOF // Now display the two lists on standard output
.
Person
= [ Title ] FullName
{ "," Degree [ varsity ] }
SYNC "."
.
FullName
= NameLast { NameLast }
.
NameLast
= InitialsName | name
.
InitialsName
= initial { initial } name
.
Title
= "Professor"
| "Prof"
| "Dr"
| "Mr" | "Mrs" | "Ms"
| "Miss" | "Mx" .
Degree
= "PhD"
| "MA" | "MSc" | "MCom"
| ( "BA" | "BSc" | "BCom" ) [ "(Hons)" ] .
END Staff.
QUESTION 4 - Compatibility, Assignment compatibility and Parameter compatibility. [15 Marks]
Suppose that you attempt to compile a Parva program in which the following entities have been declared and are "in scope" (that is, some variables and some void functions):
int i1, i2;
char c1, c2;
int[] iList1, iList2;
char[] cList1, cList2;
void PassIbyVal (int i) { ... }
void PassCbyVal (char c) { ... }
void PassIbyRef (ref int i) { ... }
void PassCbyRef (ref char c) { ... }
Assuming that any variables have been given values correctly by the stage the following fragments of code are encountered, for which of them should the Parva compiler report a type conflict (that is, regard them as invalid)? Mark these with an X in the box provided. Marks will be deducted for wrong answers, so don't guess! Four of them have been done as illustrations.
╓──────────────────┬───╥──────────────────┬───╥─────────────────────┬───╥─────────────────────┬───╖ ║ Assignment │ ║ Test Equality │ ║ Test Ordering │ ║ Remainder │ ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ i1 = i2; │ ║ i1 == i2 │ ║ i1 > i2 │ ║ i1 % i2 │ ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ i1 = c1; │ ║ i1 == c1 │ ║ i1 > c1 │ ║ i1 % c1 │ ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ c1 = c2; │ ║ c1 == c2 │ ║ c1 > c2 │ ║ c1 % c2 │ ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ c1 = i1; │ ║ c1 == i1 │ ║ c1 > i1 │ ║ c1 % i1 │ ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ iList1 = iList2; │ ║ iList1 == iList2 │ ║ iList1 > iList2 │ ║ iList1 % iList2 │ x ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ iList1 = cList1; │ ║ iList1 == cList1 │ ║ iList1 > cList1 │ ║ iList1 % cList1 │ x ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ cList1 = cList2; │ ║ cList1 == cList2 │ ║ cList1 > cList2 │ ║ cList1 % cList2 │ x ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ cList1 = iList1; │ ║ cList1 == iList1 │ ║ cList1 > iList1 │ ║ cList1 % iList1 │ x ║ ╙──────────────────┴───╨──────────────────┴───╨─────────────────────┴───╨─────────────────────┴───╜ Parameter compatibility: ╓──────────────────┬───╥──────────────────┬───╥─────────────────────┬───╥─────────────────────┬───╖ ║ PassIbyVal(i1); │ ║ PassIbyVal(c1); │ ║ PassIbyVal(ref i1); │ ║ PassIbyVal(ref c1); │ ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ PassCbyVal(i1); │ ║ PassCbyVal(c1); │ ║ PassCbyVal(ref i1); │ ║ PassCbyVal(ref c1); │ ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ PassIbyRef(i1); │ ║ PassIbyRef(c1); │ ║ PassIbyRef(ref i1); │ ║ PassIbyRef(ref c1); │ ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ PassCbyRef(i1); │ ║ PassCbyRef(c1); │ ║ PassCbyRef(ref i1); │ ║ PassCbyRef(ref c1); │ ║ ╟──────────────────┼───╫──────────────────┼───╫─────────────────────┼───╫─────────────────────┼───╢ ║ (int) i1 │ ║ (int) c1 │ ║ (char) i1 │ ║ (char) c1 │ ║ ╙──────────────────┴───╨──────────────────┴───╨─────────────────────┴───╨─────────────────────┴───╜
QUESTION 5 - Code generation for a "while" loop with embedded "break" statements. [20 Marks]
You will recall that the relevant part of the Parva compiler that deals with the WhileStatement is as follows:
WhileStatement<StackFrame frame> (. Label loopExit = new Label(!known);
Label loopContinue = new Label(known); .)
= "while" "(" Condition ")" (. CodeGen.BranchFalse(loopExit); .)
Statement<frame, loopExit> (. CodeGen.Branch(loopContinue);
loopExit.Here(); .) //==================
.
Consider the following, rather pointless program, which illustrates a while loop within which are nested two break statements:
void Main() {
int i;
while (i < 10) {
bool b;
readLine();
break;
writeLine();
break;
i++;
}
} // Main
The code that would be generated by the Parva compiler is shown - slightly incomplete - below.
(a) Complete the table to show what the address fields of the various branch instructions and the DSP instruction would contain immediately before the loopExit.Here() method was invoked (column 2) and then immediately after the loopExit.Here() method was applied (column 3). [12 Marks]
(b) What would these instruction address fields contain by the end of compilation (column 4)? [8 Marks]
address fields
┌───────────┐ ┌──────────────── before "Here()" is called
│ FHDR │ V
├───────────┼─────────┬─────────┬─────────┐
│ CALL │ 4 │ 4 │ 4 │
├───────────┼─────────┴─────────┴─────────┘
│ HALT │
├───────────┼─────────┬─────────┬─────────┐
│ DSP │ │ │ │
├───────────┼─────────┼─────────┼─────────┤
│ LDA │ 4 │ 4 │ 4 │ while (i < 10) {
├───────────┼─────────┴─────────┴─────────┘
│ LDV │
├───────────┼─────────┬─────────┬─────────┐
│ LDC │ 100 │ 100 │ 100 │
├───────────┼─────────┴─────────┴─────────┘
│ CLT │
├───────────┼─────────┬─────────┬─────────┐
│ BZE ?? │ │ │ │
├───────────┼─────────┴─────────┴─────────┘
│ INPL │ readline();
├───────────┼─────────┬─────────┬─────────┐
│ BRN ?? │ │ │ │
├───────────┼─────────┴─────────┴─────────┘
│ PRNL │ writeLine();
├───────────┼─────────┬─────────┬─────────┐
│ BRN ?? │ │ │ │
├───────────┼─────────┼─────────┼─────────┤
│ LDA │ 4 │ 4 │ 4 │
├───────────┼─────────┴─────────┴─────────┘
│ INC │ i++;
├───────────┼─────────┬─────────┬─────────┐
│ BRN ?? │ │ │ │ }
├───────────┼─────────┴─────────┴─────────┘
│ RETV │ ^ address fields
└───────────┘ └────────── after "Here()" has been applied
QUESTION 6 - A potential complication when loops are nested. [10 Marks]
Consider the following specimen of code
do
while ( Condition2 ) ;
while ( Condition2 ) ;
(a) Two excited students come to you with the suggestion that this demonstrates a hitherto undiscovered ambiguity in Parva (and in other C-like languages). Surely, their argument goes, it can be viewed as either a DoWhile loop followed by a While loop, or as a DoWhile loop within which is nested a While loop? How do you react and how do you explain your reaction? [6 Marks]
(b) There must surely be a lesson to be learned from this about poor language design. If you were to redesign Parva, what might you do differently so as to avoid this sort of problem and/or confusion? [4 Marks]
QUESTION 7 - Static semantics for a ForStatement. [15 Marks]
The ForStatement is to be found in many languages. Examples of such statements, if one were tempted to introduce this statement form to Parva, are
for c = 'a' to 'z' write(i); // writes abcdefghijklmnopqrstuvwxyz
for k = 5 downto 0 write(k); // writes 5 4 3 2 1 0
for j = 30 to 10 write(j) // writes nothing at all
i = 5;
for i = i - 2 to i + 3 write(i) // writes 3 4 5 6 7 8
where, it should be noted, (a) the limits of the controlling variable are evaluated before the loop is attempted and are not altered as the controlling variable advances (last example) (b) if the limits forbid it, the loop body is not executed at all (third example) (c) the controlling variable otherwise advances automatically over the range from the first to the last value inclusive.
Within the loop body the value of the controlling variable should not be tampered with, although its value may be used in expressions (as illustrated in all the examples). So code like the following should not be used to achieve a premature exit from a loop!
for i = 1 to 10 {
write(i); // okay
// ...
if (i == 4) i = 20; // naughty-naughty
}
The Parva compiler supplied to you contains partially attributed syntax for a ForStatement :
ForStatement<StackFrame frame> (. int expType1, expType2;
Label loopExit = new Label(!known);
string name; .)
= "for"
Ident<out name>
AssignOp
Expression<out expType1>
( "to" | "downto")
Expression<out expType2>
Statement<frame, loopExit>
.
One school of thought suggests that the controlling variable should be declared automatically after the Ident is encountered, and its scope limited to the Statement that forms the loop body. Show how to add attributes to the above production to achieve this. Note that the type of the variable will have to be determined from the context, also that this type will have to be one that allows for counting operations, and also that the controlling variable should not be allowed to be altered within that associated Statement.
It will come as a relief to learn that you are not required to generate code for the ForStatement, other than to deal with the possibility that the associated Statement forming the loop body may contain one or more BreakStatements. Furthermore, a mechanism for protecting variables from change is already suggested in the Table Handler.
As usual, in the exam kit there are some simple programs incorporating ForStatements that you may use for testing your ideas.
QUESTION 8 - Turtle Graphics. [20 Marks]
(a) A major component of the November examination in this course involved the development of a Turtle Graphics facility for Parva. As with the rest of the system, stress has to be placed on detecting and preventing errors of one sort and another, and the components provided for the examination had some deliberate shortcomings in that regard - such as a lack of precision in computing the co-ordinates of the Turtle (which has been corrected in the version of the TURTLELIB.CS file in the new exam kit, a listing of which appears at the end of this paper).
Aspects that still need attention are related to questions such as the following:
- What should happen if an attempt is made to draw on an unopened canvas?
- What should happen if an attempt is made to open a canvas when one is already open?
- What should happen if an attempt is made to specify a canvas whose width and/or height are zero or negative?
- What should happen if an attempt is made to draw a line or move the Turtle outside the area of the canvas?
It might be best if such problems could be picked up at compile time, but a little thought should show that this is not really practical. This leads to having to decide which should be picked up inside the TurtleLib class, and which should be picked up within the PVM class. Given that error messages should be related to a Parva programmer's view of the world, that tips the balance in favour of run-time checks within the PVM.
Part of the PVM interpreter is given below. Suggest how it might be improved (edit the code, don't waffle!) [10 Marks]
// graphicsInitialised is set to false before the fetch-execute cycle of the
// interpreter gets going.
case PVM.initg: // initialize graphics window
y0 = Pop();
x0 = Pop(); // centre of window is conceptually (x0, y0)
tos = Pop(); // height
sos = Pop(); // width
x0 = sos / 2 - x0; // offsets for PVM.line
y0 = tos / 2 + y0;
Turtle.InitGraphics(sos, tos);
graphicsInitialised = true;
break;
case PVM.stopg: // close graphics window
Turtle.CloseGraphics();
graphicsInitialised = false;
break;
case PVM.homet: // send turtle home
Turtle.Home();
break;
case PVM.turnt: // turn turtle left
Turtle.TurnLeft(Pop());
break;
case PVM.movet: // move turtle forward
Turtle.Forward(Pop());
break;
case PVM.penu: // lift turtle pen
Turtle.PenUp();
break;
case PVM.pend: // lower turtle pen
Turtle.PenDown();
break;
case PVM.line: // draw line
int y2 = y0 - Pop();
int x2 = x0 + Pop();
int y1 = y0 - Pop();
int x1 = x0 + Pop();
Turtle.Line(x1, y1, x2, y2);
break;
(b) Notwithstanding those attempts at user-friendliness, there are aspects of the TurtleLib class that could be made much safer. If for some reason (perhaps during testing) a call is made on the routines in this class to draw on an uninitialised canvas, an exception is likely to be raised - which might make no sense to a simple Parva programmer. Suggest how this library can be improved in that respect (edit the code, don't waffle!). [10 Marks]
QUESTION 9 - Parameter Passing and Run-time Storage Management. [16 Marks]
(a) The intent of the following simple program (PASS1.PAV) should be obvious. The Main routine declares a local array, calls the method Allocate, which allocates space for a small array on the heap, initialises an element in that array, displays the value and then returns to the Main method, which goes on to display the value of an element of the list array.
void Allocate(int[] arr) {
// point B
arr = new int[3];
arr[2] = 2016;
// point C
writeLine(array[2]);
} // Allocate
void Main() {
int[] list = null;
// point A
Allocate(list);
// point D
writeLine(list[2]);
} // Main
Here parameter passing is "by value". Complete the tables below, replacing the values marked ???? with the actual values that would be stored in memory as each of points A, B, C and D are reached. [4 Marks]
Heap --> <- Stack list SM RA DL RV
┌────┬────┬────┬────┬────┬────┬ ┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
A │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ .... │ │ │ │ │ │ │????│ 512│ 3 │ 512│ 0 │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└────┴────┴────┴────┴────┴────┴ ┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
100 101 102 103 104 105 501 502 503 504 505 506 507 508 509 510 511
HB = 100 HP = 100 SP = 507 FP = 512
Heap --> <- Stack arr SM RA DL RV list SM RA DL RV
┌────┬────┬────┬────┬────┬────┬ ┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
B │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ .... │ │????│ 507│ 52 │ 507│ 0 │????│ 512│ 3 │ 512│ 0 │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└────┴────┴────┴────┴────┴────┴ ┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
100 101 102 103 104 105 501 502 503 504 505 506 507 508 509 510 511
HB = 100 HP = 100 SP = 502 FP = 507
Heap --> <- Stack arr SM RA DL RV list SM RA DL RV
┌────┬────┬────┬────┬────┬────┬ ┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
C │????│????│????│????│????│????│ .... │ │????│ 507│ 52 │ 507│ 0 │????│ 512│ 3 │ 512│ 0 │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└────┴────┴────┴────┴────┴────┴ ┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
100 101 102 103 104 105 501 502 503 504 505 506 507 508 509 510 511
HB = 100 HP = ???? SP = 502 FP = 507
Heap --> <- Stack list SM RA DL RV
┌────┬────┬────┬────┬────┬────┬ ┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
D │????│????│????│????│????│????│ .... │ │ │ │ │ │ │????│ 512│ 3 │ 512│ 0 │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└────┴────┴────┴────┴────┴────┴ ┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
100 101 102 103 104 105 501 502 503 504 505 506 507 508 509 510 511
HB = 100 HP = ???? SP = 507 FP = 512
(b) What will be the output, if any, when this program runs? [2 Marks]
(c) Repeat the exercise for the rather similar program below (PASS2.PAV) , where parameter passing is "by reference". [4 Marks]
void Allocate(ref int[] arr) {
// point B
arr = new int[3];
arr[2] = 2016;
// point C
writeLine(array[2]);
} // Allocate
void Main() {
int[] list = null;
// point A
Allocate(ref list);
// point D
writeLine(list[2]);
} // Main
Heap --> <- Stack list SM RA DL RV
┌────┬────┬────┬────┬────┬────┬ ┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
A │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ .... │ │ │ │ │ │ │????│ 512│ 3 │ 512│ 0 │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└────┴────┴────┴────┴────┴────┴ ┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
100 101 102 103 104 105 501 502 503 504 505 506 507 508 509 510 511
HB = 100 HP = 100 SP = 507 FP = 512
Heap --> <- Stack arr SM RA DL RV list SM RA DL RV
┌────┬────┬────┬────┬────┬────┬ ┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
B │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ .... │ │????│ 507│ 52 │ 507│ 0 │????│ 512│ 3 │ 512│ 0 │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└────┴────┴────┴────┴────┴────┴ ┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
100 101 102 103 104 105 501 502 503 504 505 506 507 508 509 510 511
HB = 100 HP = 100 SP = 502 FP = 507
Heap --> <- Stack arr SM RA DL RV list SM RA DL RV
┌────┬────┬────┬────┬────┬────┬ ┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
C │????│????│????│????│????│????│ .... │ │????│ 507│ 52 │ 507│ 0 │????│ 512│ 3 │ 512│ 0 │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└────┴────┴────┴────┴────┴────┴ ┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
100 101 102 103 104 105 501 502 503 504 505 506 507 508 509 510 511
HB = 100 HP = ???? SP = 502 FP = 507
Heap --> <- Stack list SM RA DL RV
┌────┬────┬────┬────┬────┬────┬ ┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
D │????│????│????│????│????│????│ .... │ │ │ │ │ │ │????│ 512│ 3 │ 512│ 0 │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└────┴────┴────┴────┴────┴────┴ ┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
100 101 102 103 104 105 501 502 503 504 505 506 507 508 509 510 511
HB = 100 HP = ???? SP = 507 FP = 512
(d) What will be the output, if any, when this program runs? [2 Marks]
(e) C# has three parameter passing mechanisms - by value, by ref and by out (only the first two of these have been adopted in Parva). Presumably there is a difference between ref and out in C#? Explain briefly what you think it is. [4 Marks]
Hint: You may like to base your discussion on a study and comparison of the following silly programs:
│ │
void Manipulate(int[] supp) { │ void Manipulate(ref int[] supp) { │ void Manipulate(out int[] supp) {
supp[2] = 2016; │ supp[2] = 2016; │ supp[2] = 2016;
writeLine(supp[2]); │ writeLine(supp[2]); │ writeLine(supp[2]);
} // Manipulate │ } // Manipulate │ } // Manipulate
│ │
void Main() { │ void Main() { │ void Main() {
int[] exam = new int[3]; │ int[] exam = new int[3]; │ int[] exam = new int[3];
exam[2] = 2015; │ exam[2] = 2015; │ exam[2] = 2015;
Manipulate(exam); │ Manipulate(ref exam); │ Manipulate(out exam);
writeLine(exam[2]); │ writeLine(exam[2]); │ writeLine(exam[2]);
} // Main │ } // Main │ } // Main
│ │
Appendix. The TurtleLib library written to service the PVM class of Parva
// TurtleGraphics Library for use with Parva and the PVM (C#)
// P.D. Terry, Rhodes University, 2015
// Version for Supplementary Examination 2015
// 2015/11/29
using GraphicsLib;
using System;
public class Turtle {
static private double // Turtle initial location, direction and pen setting
direction = 0.0,
turtleX = 0.0,
turtleY = 0.0,
homeX = 0.0,
homeY = 0.0,
homeD = 0.0;
static private bool
penDown = true;
static private GraphicsWindow w = null;
public static void InitGraphics(int width, int height) {
if (w != null) w.Close();
w = new GraphicsWindow(width, height);
turtleX = homeX = width / 2;
turtleY = homeY = height / 2;
direction = homeD = 0;
} // Turtle.InitGraphics
public static void CloseGraphics() {
if (w != null) w.Close();
} // Turtle.CloseGraphics
public static void Home() {
turtleX = homeX;
turtleY = homeY;
direction = homeD;
} // Turtle.Home()
public static void PenUp() {
penDown = false;
} // Turtle.PenUp
public static void PenDown() {
penDown = true;
} // Turtle.PenDown
public static void TurnLeft(double degrees) {
direction -= degrees;
} // Turtle.TurnLeft
public static void Forward(double distance) {
double rad = 0.0174532925199 * direction;
double newX = turtleX + distance * Math.Cos(rad);
double newY = turtleY + distance * Math.Sin(rad);
if (penDown) w.DrawLine((int) Math.Round(turtleX), (int) Math.Round(turtleY),
(int) Math.Round(newX), (int) Math.Round(newY));
turtleX = newX;
turtleY = newY;
} // Turtle.Forward
public static void Line(int x1, int y1, int x2, int y2) {
w.DrawLine(x1, y1, x2, y2);
} // Turtle.Line
} // class Turtle