(a) Develop stack machine code equivalents of the following simple programs:
(1) void main () {
for (int i = 0; i <= 10; i++) write(i, "\n")
}
0 DSP 1
2 LDA 0
4 LDC 0
6 STO
7 LDA 0
9 LDV
10 LDC 10
12 CLE
13 BZE 32
15 LDA 0
17 LDV
18 PRNI
19 PRNS "\n"
21 LDA 0
23 LDA 0
25 LDV
26 LDC 1
28 ADD
29 STO
30 BRN 7
32 HALT
(2) void main () { // demonstrate hailstone series
int m;
read("what is the first term of the series? ", m);
write(m);
int n = 1;
while (m != 1) {
if (m % 2 == 0) m = m / 2;
else m = 3 * m + 1;
n = n + 1;
write(m);
}
write("\n", n , " terms in that sequence");
}
0 DSP 2
2 PRNS "what is the first term of the series? "
4 LDA 0
6 INPI read(m);
7 LDA 0
9 LDV
10 PRNI write(m);
11 LDA 1
13 LDC 1
15 STO n = 1;
16 LDA 0
18 LDV
19 LDC 1
21 CNE
22 BZE 73 while (m != 1) {
24 LDA 0
26 LDV
27 LDC 2
29 REM
30 LDC 0
32 CEQ
33 BZE 46 if (m%2 == 0)
35 LDA 0
37 LDA 0
39 LDV
40 LDC 2
42 DIV
43 STO m = m / 2 ;
44 BRN 58
46 LDA 0 else
48 LDC 3
50 LDA 0
52 LDV
53 MUL
54 LDC 1
56 ADD
57 STO m = 3 * m + 1;
58 LDA 1
60 LDA 1
62 LDV
63 LDC 1
65 ADD
66 STO n = n + 1;
67 LDA 0
69 LDV
70 PRNI write(m)
71 BRN 16 } // while
73 PRNS "\n" write("\n")
75 LDA 1
77 LDV
78 PRNI write(n);
79 PRNS " terms in that sequence"
81 HALT return;
(b) The following code is supposed to check to see whether the elements of an array form a non-decreasing sequence. Does it do so correctly? If not, how would you fix it, and what would the resulting PVM code look like?
void main () {
// Check to see whether an array has elements in ascending order
const size = 20;
int[] list = new int[size];
int i = 0;
list[5] = -1;
bool inOrder;
while (i < size) {
if (list[i] > list[i+1])
inOrder = false;
else
inOrder = true;
i = i + 1;
}
write(inOrder);
}
It is incorrect, and embodies two classic mistakes - the loop executes the loop body once too often, and the
logic for checking that the elements are in order is badly wrong. Here is a better solution:
void main () {
// Check to see whether an array has elements in ascending order
const size = 20;
int[] list = new int[size];
int i = 0;
list[5] = -2;
bool inOrder = true;
while (inOrder && (i < size - 1)) {
if (list[i] > list[i+1]) inOrder = false;
i = i + 1;
}
write(inOrder);
}
and this could be coded as follows (there are other ways - this one does
not use short circuit logic, and you might like to think how that would be
incorporated
0 DSP 3
2 LDA 0
4 LDC 20
6 ANEW int[] list = new int{size];
7 STO
8 LDA 1
10 LDC 0
12 STO i = 0;
13 LDA 0
15 LDV
16 LDC 5
18 LDXA
19 LDC 2
21 NEG
22 STO list[5] = -1;
23 LDA 2
25 LDC 1
27 STO inOrder = true;
28 LDA 2 while (inOrder
30 LDV
31 LDA 1 &&
33 LDV
34 LDC 20
36 LDC 1
38 SUB (i < size - 1)
39 CLT
40 AND ) {
41 BZE 81
43 LDA 0
45 LDV
46 LDA 1
48 LDV
49 LDXA
50 LDV
51 LDA 0
53 LDV
54 LDA 1
56 LDV
57 LDC 1
59 ADD
60 LDXA
61 LDV
62 CGT if (list[i] > list[i+1])
63 BZE 70
65 LDA 2
67 LDC 0 inOrder = false;
69 STO
70 LDA 1
72 LDA 1
74 LDV
75 LDC 1
77 ADD
78 STO i = i + 1;
79 BRN 28 } // while
81 LDA 2
83 LDV
84 PRNB write(inorder);
85 HALT return;
(c) Consider the following general form of T diagram. Although it uses the letters A through I in the various arms of the Ts, one could draw the diagram with fewer letters. How?
---------------------------- ----------------------------
| | | |
| A ----------> B | | C -----------> D |
| | | |
--------- ---------------------------- ---------
| | | |
| E | F --------> G | H |
| | | |
-------------------- --------------------
| |
| I |
| |
------------
Because of the rule that the "input" is semantically the same as the "output"
it follows that we can draw this
---------------------------- ----------------------------
| | | |
| A ----------> B | | A -----------> B |
| | | |
--------- ---------------------------- ---------
| | | |
| F | F --------> G | G |
| | | |
-------------------- --------------------
| |
| I |
| |
------------
(d) In the practical sessions you should have used the Extacy Modula-2 to C translator. This was developed in Russia by a team who used the JPI Modula-2 compiler available for the PC. But the demonstration system we downloaded from the Internet came with the file XC.EXE and a few other modules written in Modula-2 (but not the source of the XC executable itself). Draw T-diagrams showing the process the Russians must have used to produce this system, and go on to draw T-diagrams showing how you managed to take the program SIEVE.MOD and run it on the PC using the Borland C++ system as your time-waster of choice.
The XC program was written in Modula-2 and compiled:
---------------------------- ----------------------------
| XC.MOD | | XC.EXE |
| M-2 ----------> C | | M-2 -----------> C |
| | | |
--------- ---------------------------- ---------
| | JPI.EXE | |
| M-2 | M-2 --------> 8086 | 8086 |
| | | |
-------------------- --------------------
| |
| 8086 |
| |
------------
| |
| 8086 |
| |
------------
Using XC.EXE can be depicted as follows:
---------------------------- ---------------------------- ----------------------------
| SIEVE.MOD | | SIEVE.C | | SIEVE.EXE |
| N ----------> Primes| | N -----------> Primes| | N -----------> Primes|
| | | | | |
--------- ---------------------------- ---------------------------- ---------
| | XC.EXE | | BCC.EXE | |
| M-2 | M-2 --------> C | C | C --------> 8086 | 8086 |
| | | | | |
-------------------- ---------------------------- --------------------
| | | | | |
| 8086 | | 8086 | | 8086 |
| | | | | |
------------ ------------ ------------
| | | |
| 8086 | | 8086 |
| | | |
------------ ------------