Complete solutions (sources) can be found on the course WWW pages in the file PRAC16A.ZIP
Start off by considering the following gem of a Clang program (SEARCH0.CLN)
PROGRAM Search;
(* 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, 2001 *)
VAR
List[10], Item, I;
BEGIN
(* First read 10 numbers into List[1] .. List[10] *)
I := 1;
WHILE I <= 10 DO BEGIN
Read(List[I]);
I := I + 1
END;
(* Now start the interrogation loop *)
Read(Item); (* first search item *)
WHILE Item <> 99 DO BEGIN
I := 1;
WHILE List[I] <> Item DO I := I + 1;
Write('Found in position', I);
Read(Item) (* next search item *)
END
END.
Firstly, decide why it is an awful program.
It's an awful program because the array subscript goes out of bounds if the Item cannot be located.
PROGRAM Search;
(* Read a list of 10 numbers, and then a further list terminated by 99
and determine which of the numbers in the second list appear in the
first list.
P.D. Terry, Rhodes University, 2001 *)
VAR
List[10], Item, I;
BEGIN
(* First read 10 numbers into List[1] .. List[10] *)
I := 1;
WHILE I <= 10 DO BEGIN
Read(List[I]);
I := I + 1
END;
(* Now start the interrogation loop *)
Read(Item); (* first search item *)
WHILE Item <> 99 DO BEGIN
List[0] := Item; (* post as a sentinel *)
I := 10;
WHILE List[I] <> Item DO I := I - 1; (* must terminate! *)
IF I = 0 THEN Write('Not found');
IF I <> 0 THEN Write('Found in position', I);
Read(Item) (* next search item *)
END
END.
This is much better because it uses a sentinel technique for the linear search. However, it can still be broken if
you give it data that is out of range of the INTEGER type, give it non-numeric data, or supply 99 as one of the
initial list of 10 numbers.
0 DSP 13 ; From SEARCH1.CLN
2 ADR -13 ;
4 LIT 1 ;
6 STO ; I := 1;
7 ADR -13 ;
9 VAL ;
10 LIT 10 ;
12 LEQ ;
13 BZE 35 ; WHILE I <= 10 DO BEGIN
15 ADR -1 ;
17 ADR -13 ;
19 VAL ;
20 LIT 11 ;
22 IND ;
23 INN ; Read(List[I]);
24 ADR -13 ;
26 ADR -13 ;
28 VAL ;
29 LIT 1 ;
31 ADD ;
32 STO ; I := I + 1
33 BRN 7 ; END;
35 ADR -12 ;
37 INN ; Read(Item);
38 ADR -12 ;
40 VAL ;
41 LIT 99 ;
43 NEQ ;
44 BZE 119 ; WHILE Item <> 99 DO BEGIN
46 ADR -1 ;
48 LIT 0 ;
50 LIT 11 ;
52 IND ;
53 ADR -12 ;
55 VAL ;
56 STO ; List[0] := Item;
57 ADR -13 ;
59 LIT 10 ;
61 STO ; I := 10;
62 ADR -1 ;
64 ADR -13 ;
66 VAL ;
67 LIT 11 ;
69 IND ;
70 VAL ;
71 ADR -12 ;
73 VAL ;
74 NEQ ;
75 BZE 88 ; WHILE (List[I] <> Item DO BEGIN
77 ADR -13 ;
79 ADR -13 ;
81 VAL ;
82 LIT 1 ;
84 SUB ;
85 STO ; I := I - 1
86 BRN 62 ; END;
88 ADR -13 ;
90 VAL ;
91 LIT 0 ;
93 EQL ;
94 BZE 99 ; IF I = 0 THEN
96 PRS 'Not found' ; Write('Not found');
98 NLN ;
99 ADR -13 ;
101 VAL ;
102 LIT 0 ;
104 NEQ ;
105 BZE 114 ; IF I <> 0 THEN
107 PRS 'Found in position' ; Write('Found in position', I)
109 ADR -13 ;
111 VAL ;
112 PRN ;
113 NLN ;
114 ADR -12 ; Read(Item)
116 INN ;
117 BRN 38 ; END
119 HLT ;
This asked whether it was possible to accomplish Boolean (NOT, AND and OR) operations using the current instruction set. Yes, you can fudge them to some extent, but they are easily added.
Adding operations to the machine to allow you to read and write Boolean values and also allow you to perform the logical operations was required.
The AND, OR and NOT operations caused few problems. Several people incorporated checks to ensure that the valuese to be combined were indeed 0 and/or 1, which is a useful extension, though not really necessary, as the underlying implementation treats 0 as "false" and anything else as "true" in any case.
case STKMC_not:
if (inbounds(cpu.sp)) mem[cpu.sp] = 1 - mem[cpu.sp];
break;
case STKMC_and:
cpu.sp++;
if (inbounds(cpu.sp))
mem[cpu.sp] = mem[cpu.sp] && mem[cpu.sp - 1];
break;
case STKMC_orr:
cpu.sp++;
if (inbounds(cpu.sp))
mem[cpu.sp] = mem[cpu.sp] || mem[cpu.sp - 1];
break;
The input and output operations were badly done by all but a few groups. I guess it is over exposure to C that has made people believe that the whole world knows that 0 and 1 are the same as FALSE and TRUE, but it really does not have to be like that. The I/O routines should convert to and from text string representations of the values; as shown below. If for no other reason this would ensure that if one of your programs wrote out Boolean results these same results could be read in as data in a subsequent program.
case STKMC_inb:
if (inbounds(cpu.sp) && inbounds(mem[cpu.sp]))
{ char tempstr[100];
if (fscanf(data, "%s", tempstr) == 0) ps = baddata;
else
{ if (stricmp(tempstr, "true") == 0) mem[mem[cpu.sp]] = 1;
else if (stricmp(tempstr, "false") == 0) mem[mem[cpu.sp]] = 0;
else ps = baddata;
cpu.sp++;
}
}
break;
case STKMC_prb:
if (tracing) fputs(BLANKS, results);
cpu.sp++;
if (inbounds(cpu.sp))
{ if (mem[cpu.sp - 1] == 1) fprintf(results, " TRUE ");
else fprintf(results, " FALSE");
}
if (tracing) putc('\n', results);
break;
In testing these operations it was suggested that you try programs like those shown, for which the stack machine equivalents are easily written down:
PROGRAM BooleanDemo;
(* This won't compile, but the idea should be obvious
P.D. Terry, Rhodes University, 2001 *)
BOOL
X, Y;
BEGIN
Read(X, Y);
Write(X, Y, NOT X, X AND Y, X OR Y)
END.
0 DSP 2 ;
2 ADR -1 ;
4 INB ; ReadBool(X);
5 ADR -2 ;
7 INB ; ReadBool(Y);
8 ADR -1 ;
10 VAL ;
11 PRB ; WriteBool(X);
12 ADR -2 ;
14 VAL ;
15 PRB ; WriteBool(Y);
16 ADR -1 ;
18 VAL ;
19 NOT ;
20 PRB ; WriteBool(NOT Y);
21 ADR -1 ;
23 VAL ;
24 ADR -2 ;
26 VAL ;
27 AND ;
28 PRB ; WriteBool(X AND Y);
29 ADR -1 ;
31 VAL ;
32 ADR -2 ;
34 VAL ;
35 ORR ;
36 PRB ; WriteBool(X OR Y);
37 HLT ;
The next one is intended to print out a little truth table to demonstrate De Wossname's law (BOOL2.CLN)
PROGRAM DeMorganDemo;
(* This won't compile, but the idea should be obvious
P.D. Terry, Rhodes University, 2001 *)
BOOL
X, Y;
BEGIN
Write(' X Y (X.Y)'' X'' + Y''');
X := FALSE;
REPEAT
Y := FALSE;
REPEAT
Write(X, Y, NOT (X AND Y), NOT X OR NOT Y);
(* Keen types might also try
Write(X, Y, NOT (X OR Y), NOT X AND NOT Y);
*)
Y := NOT Y;
UNTIL Y = FALSE (* again *);
X := NOT X
UNTIL X = FALSE (* again *)
END.
0 DSP 2 ; De Morgan's Law demo
2 PRS " X Y (X AND Y)' X' OR Y'"
4 NLN
5 ADR -1 ; X := FALSE
7 LIT 0
9 STO
10 ADR -2 ; REPEAT
12 LIT 0
14 STO ; Y := FALSE
15 ADR -1
17 VAL REPEAT
18 PRB ; WriteBool(X)
19 ADR -2
21 VAL
22 PRB ; WriteBool(Y)
23 ADR -1
25 VAL
26 ADR -2
28 VAL
29 AND
30 NOT
31 PRB ; WriteBool(not (X and Y))
32 ADR -1
34 VAL
35 NOT
36 ADR -2
38 VAL
39 NOT
40 ORR
41 PRB ; WriteBool((not X) or (not Y))
42 NLN
43 ADR -2
45 ADR -2
47 VAL
48 NOT
49 STO ; Y := not Y
50 ADR -2
52 VAL
53 LIT 0
55 EQL
56 BZE 15 ; UNTIL Y = FALSE
58 ADR -1
60 ADR -1
62 VAL
63 NOT
64 STO ; X := not X
65 ADR -1
67 VAL
68 LIT 0
70 EQL
71 BZE 10 ; UNTIL X = FALSE
73 HLT
You were invited to have a look at SEARCH2.CLN, which is yet another variation on the searching program given earlier, and asked whether this would benefit from the new found ability to use Boolean operations. If so, how; if not, why not?
PROGRAM Search;
(* Read a list of 10 numbers, and then a further list terminated by 99
and determine which of the numbers in the second list appear in the
first list.
P.D. Terry, Rhodes University, 2001 *)
VAR
List[10], Item, I;
BEGIN
(* First read 10 numbers into List[1] .. List[10] *)
I := 1;
WHILE I <= 10 DO BEGIN
Read(List[I]);
I := I + 1
END;
(* Now start the interrogation loop *)
Read(Item); (* first search item *)
WHILE Item <> 99 DO BEGIN
I := 1;
WHILE (I <= 10) AND (List[I] <> Item) DO I := I + 1;
(* Okay, but can I also write it like this?
WHILE (List[I] <> Item) AND (I <= 10) DO I := I + 1;
*)
IF I > 10 THEN Write('Not found');
IF I <= 0 THEN Write('Found in position', I);
Read(Item) (* next search item *)
END
END.
At the heart of this version lay the search loop:
I := 1;
WHILE (I <= 10) AND (List[I] <> Item) DO I := I + 1;
or an apparent alternative:
I := 1;
WHILE (List[I] <> Item) AND (I <= 10) DO I := I + 1;
Writing the search loop in the first way only succeeds if one can assume short circuit evaluation of the WHILE loop condition. Writing it in the second way is bound to cause trouble, short circuit or not! This code will not benefit from the simple application of the AND operation. It would have to be coded to look like this (we give an extract from the code only):
46 ADR -13 ;
48 LIT 1 ;
50 STO ; I := 1;
51 ADR -13 ; WHILE loop starts here
53 VAL ;
54 LIT 10 ;
56 LEQ ;
57 BZE 85 ; Short circuit if I > 10
59 ADR -1 ;
61 ADR -13 ;
63 VAL ;
64 LIT 11 ;
66 IND ;
67 VAL ;
68 ADR -12 ;
70 VAL ;
71 NEQ ;
72 BZE 85 ; Exit if List[I] <> ITEM
74 ADR -13 ;
76 ADR -13 ;
78 VAL ;
79 LIT 1 ;
81 ADD ;
82 STO ; I := I + 1
83 BRN 51 ; END;
You were asked to investigate the provision of an alternative opcode to IND that did no bounds check.
Some people did not realise that if one wanted to do this, then one would not need to push the array size onto the stack. In fact, the operation becomes a straightforward one, for which there is already a "case arm". So all that is needed, if one wants to introduce the INX operation, is to attach another label onto the SUB arm (besides the addition of the mnemonic and constant into the various look up tables, of course):
case STKMC_sub:
case STKMC_inx:
cpu.sp++;
if (inbounds(cpu.sp)) mem[cpu.sp] -= mem[cpu.sp - 1];
break;
Most real machines have "condition codes" or "status bits" (like the CPU.Z and CPU.P ones that you learned about in our previous encounters last year). Suppose you added status flags to the machine and then modified the semantics of the opcode set, or (preferably) added to it, so as to be able to take advantage of them. How would you do this, and what would this buy you when you came to write code for it?
This was not very well answered, except by a few rather perceptive groups. Adding the condition codes is not difficult; one can, for example, write code like
case STKMC_sub:
cpu.sp++;
if (inbounds(cpu.sp)) mem[cpu.sp] -= mem[cpu.sp - 1];
cpu.z = mem[cpu.sp] == 0; cpu.p = mem[cpu.sp] >= 0;
break;
case STKMC_eql:
cpu.sp++;
if (inbounds(cpu.sp)) mem[cpu.sp] = (mem[cpu.sp] == mem[cpu.sp - 1]);
cpu.z = mem[cpu.sp] == 0;
break;
The problem comes about when one wants to use conditional branch operations. Currently we have one that reads
case STKMC_bze:
cpu.sp++;
if (inbounds(cpu.sp))
{ if (mem[cpu.sp - 1] == 0) cpu.pc = mem[cpu.pc]; else cpu.pc++; }
break;
This has the "side effect" of popping a number from the stack. If one were simply to replace it with
case STKMC_bze:
if (cpu.z) cpu.pc = mem[cpu.pc]; else cpu.pc++;
break;
then one would get items left on the stack that shouldn't be there! One might argue for modifying other oerations so that they simply set the flags, and did not leave a result on the stack; for example:
case STKMC_eql:
cpu.sp += 2; cpu.z = (mem[cpu.sp - 2] == mem[cpu.sp - 1]);
break;
but if you think about this for a bit you will see that this sort of thing would lead to trouble were you to want to code assignments involving booleans, for example
a := (f > g) AND (x <> y);
unless, of course, you then also went to the trouble of discarding the AND and OR operations and replacing all the code you might at first have thought of writing with equivalent code using short circuit evaluation and branch opcodes.