There were some very good solutions submitted, and some very energetic ones too - clearly a lot of students had put in many hours developing their code. This is very encouraging. Do learn to put your names into the introductory comments of programs that you write.
Full source for the solutions summarized here can be found in the ZIP file on the Web page - PRAC08A.ZIP.
Most people had seen at least one improvement that could be made to the palindrome checker to ensure that the loop terminated as quickly as possible. Here are some suggestions (there are even more ways of course):
IsPalindrome := TRUE; (* optimist *)
Low := 0; High := N - 1; (* initial indices *)
WHILE Low < High DO BEGIN (* sweep through the List *)
IF List[Low] <> List[High] THEN IsPalindrome := FALSE; (* bad luck *)
Low := Low + 1; High := High - 1; (* adjust indices *)
END;
IsPalindrome := TRUE; (* optimist *)
Checking := TRUE; (* start search *)
Low := 0; High := N - 1; (* initial indices *)
WHILE Checking = TRUE DO BEGIN (* sweep through the List *)
IF List[Low] <> List[High] THEN BEGIN
IsPalindrome := FALSE; (* bad luck *)
Checking := FALSE (* no need to search further *)
END;
Low := Low + 1; High := High - 1; (* adjust indices *)
IF Low >= High THEN Checking := FALSE (* reached middle *)
END;
IsPalindrome := TRUE; (* optimist *)
Low := 0; High := N - 1; (* initial indices *)
WHILE Low < High DO BEGIN (* sweep through the List *)
IF List[Low] <> List[High] THEN BEGIN
IsPalindrome := FALSE; (* bad luck *)
Low := High (* to abort the loop *)
END;
Low := Low + 1; High := High - 1; (* adjust indices *)
END;
IsPalindrome := TRUE; (* optimist *)
Low := 0; Mid := N/2; (* initial indices *)
WHILE Low < Mid DO BEGIN (* sweep through the List *)
IF List[Low] <> List[N - 1 - Low] THEN BEGIN
IsPalindrome := FALSE; (* bad luck *)
Low := Mid (* to abort the loop *)
END;
Low := Low + 1; (* adjust indices *)
END;
One way that requires a little more coding is to use a function that returns as soon as it can:
FUNCTION IsPalindrome(List[], N);
VAR
Low, High; (* indices of items to be compared *)
BEGIN
Low := 0; High := N - 1; (* initial indices *)
WHILE Low < High DO BEGIN (* sweep through the List *)
IF List[Low] <> List[High] THEN RETURN FALSE; (* bad luck *)
Low := Low + 1; High := High - 1; (* adjust indices *)
END;
RETURN TRUE
END;
BEGIN
IF IsPalindrome(List, N) = TRUE THEN Write('Palindromic sequence');
IF IsPalindrome(List, N) = FALSE THEN Write('Non-palindromic sequence');
END.
Most people seemed to get to a solution, or close to a solution. Here is one that matches the original Clang algorithm. Notice the style of commentary - designed to show the algorithm to good advantage, rather than being a statement by statement comment as a mnachine level (which is what most people did). Sadly some people did not realise that the IND opcode is the way to handle array indexing!
; comments are allowed on lines starting with ; ; program to check a sequence for being palindromic ; P.D. Terry, Rhodes University, 2002 0 DSP 106 ; BEGIN 73 BZE 121 ; WHILE Low < N - 1 DO BEGIN 2 ADR -1 ; 75 ADR -6 ; 4 LIT 0 ; 77 ADR -2 ; 6 STO ; N := 0 79 VAL ; 7 ADR -4 ; 80 LIT 101 ; 9 INN ; Read(Item) 82 IND ; 10 ADR -4 ; 83 VAL ; 12 VAL ; 84 ADR -6 ; 13 LIT 0 ; 86 ADR -3 ; 15 NEQ ; 88 VAL ; 16 BZE 44 ; WHILE Item <> 0 DO BEGIN 89 LIT 101 ; 18 ADR -6 ; 91 IND ; 20 ADR -1 ; 92 VAL ; 22 VAL ; 93 NEQ ; 23 LIT 101 ; 94 BZE 101 ; IF List[Low} <> List[High] THEN 25 IND ; 96 ADR -5 ; 26 ADR -4 ; 98 LIT 0 ; 28 VAL ; 100 STO ; IsPalindrome := FALSE 29 STO ; List[N] := Item 101 ADR -2 ; 30 ADR -1 ; 103 ADR -2 ; 32 ADR -1 ; 105 VAL ; 34 VAL ; 106 LIT 1 ; 35 LIT 1 ; 108 ADD ; 37 ADD ; 109 STO ; Low := Low + 1 38 STO ; N := N + 1 110 ADR -3 ; 39 ADR -4 ; 112 ADR -3 ; 41 INN ; Read(Item) 114 VAL ; 42 BRN 10 ; END 115 LIT 1 ; 44 ADR -5 ; 117 SUB ; 46 LIT 1 ; 118 STO ; High := High - 1 48 STO ; IsPalindrome := TRUE 119 BRN 63 ; END 49 ADR -2 ; 121 ADR -5 ; 51 LIT 0 ; 123 VAL ; 53 STO ; Low := 0 124 LIT 1 ; 54 ADR -3 ; 126 EQL ; 56 ADR -1 ; 127 BZE 132 ; IF IsPalindrome = TRUE THEN 58 VAL ; 129 PRS 'Palindromic sequence' 59 LIT 1 ; 131 NLN ; 61 SUB ; 132 ADR -5 ; 62 STO ; High := N = 1 134 VAL ; 63 ADR -2 ; 135 LIT 0 ; 65 VAL ; 137 EQL ; 66 ADR -1 ; 138 BZE 143 ; IF IsPalindrome = FALSE THEN 68 VAL ; 140 PRS 'Non-palindromic sequence' 69 LIT 1 ; 142 NLN ; 71 SUB ; 143 HLT ; END 72 LSS ;
Checking sentences for palindromes can use essentially the same algorithm, but care has to be taken to apply it only to the alphanumeric characters. If one develops simple minded operations for reading and writing characters, as some people successfully did, then one is rather forced to try to write code that corresponds to the following (where, of course, one has to use the magic ASCII numbers for the characters limiting the ends of the valid ranges):
PROGRAM Palindrome;
(* Read a sequence of characters and report whether they form a palindromic
sentence (one that reads the same from either end)
Examples: Madam, I'm Adam. is palindromic
Pat Terry. is non-palindromic
P.D. Terry, Rhodes University, 2002 *)
CONST
TRUE = 1;
FALSE = 0;
VAR
N, (* number of items *)
Low, High, (* indices of items to be compared *)
Item, (* latest item read *)
IsPalindrome, (* Boolean flag *)
List[100]; (* the list of items *)
BEGIN
N := 0;
ReadChar(Item);
WHILE Item <> '.' DO BEGIN
IF Item >= 'A' THEN
IF Item <= 'Z' THEN BEGIN List[N] := Item; N := N + 1 END;
IF Item >= 'a' THEN
IF Item <= 'z' THEN BEGIN List[N] := Item; N := N + 1 END;
IF Item >= '0' THEN
IF Item <= '9' THEN BEGIN List[N] := Item; N := N + 1 END;
ReadChar(Item)
END;
IsPalindrome := TRUE; (* optimist *)
Low := 0; High := N - 1; (* initial indices *)
WHILE Low < High DO BEGIN (* sweep through the List *)
IF List[Low] <> List[High] THEN IsPalindrome := FALSE; (* bad luck *)
Low := Low + 1; High := High - 1; (* adjust indices *)
END;
IF IsPalindrome = TRUE THEN Write('Palindromic sequence');
IF IsPalindrome = FALSE THEN Write('Non-palindromic sequence');
END.
This is all rather tedious to code up, and several people tried to do clever things with the interpreter to cut out having to write all those nasty IF statements out in detail. However, I suspect it is not very clever to restrict the operation for reading characters to handle only letters, or only upper case letters, or to force the characters to be stored in upper case, as some people did. Rather introduce further opcodes for doing this, as was suggested in the prac sheet. The solution below shows how these could have been defined; in terms of them (and other extensions) a rather shorter palindrome checker might be coded as follows:
; comments are allowed on lines starting with ;
; program to check a sentence for being palindromic
; P.D. Terry, Rhodes University, 2002
0 DSP 106 55 PSH -2
2 LIT 0 BEGIN 57 PSH -3
4 POP -1 N := 0 59 LSS
6 ADR -4 60 BZE 93 WHILE Low < High DO BEGIN
8 INA ReadChar(Item) 62 ADR -6
9 PSH -4 64 PSH -2
11 LIT 46 66 LIT 101
13 NEQ 68 IND
14 BZE 40 WHILE Item <> '.' DO BEGIN 69 VAL
16 PSH -4 70 ADR -6
18 ALN 72 PSH -3
19 BZE 35 IF AlNum(Item) THEN BEGIN 74 LIT 101
21 ADR -6 76 IND
23 PSH -1 77 VAL
25 LIT 101 78 NEQ
27 IND 79 BZE 85 IF List[Low] <> List[High] THEN
28 PSH -4 81 LIT 0
30 UPC 83 POP -5 IsPalindrome := FALSE;
31 STO List[N] := UpCase(Item); 85 ADR -2
32 ADR -1 87 INC Low := Low + 1;
34 INC N := N + 1 88 ADR -3
35 ADR -4 END; 90 DEC High := High - 1;
37 INA ReadChar(Item); 91 BRN 46 END;
38 BRN 9 END; 93 PSH -5
40 LIT 1 95 LIT 1
42 POP -5 IsPalindrome := TRUE; 97 EQL IF IsPalindrome THEN
44 LIT 0 98 BZE 104
46 POP -2 High := 0; 100 PRS 'Palindromic sequence'
48 PSH -1 102 BRN 106 ELSE
50 LIT 1 104 PRS 'Non-palindromic sequence'
52 SUB 106 NLN
53 POP -3 Low := N - 1; 107 HLT END.
Some people forgot to introduce the PSH and POP references everywhere. They are needed in the switch statements in
void STKMC::listcode(char *filename, STKMC_address codelen)
and in
void STKMC::trace(FILE *results, STKMC_address pcnow)
and in the assembler file (STKASM.CPP) as well as in the obvious one in the emulator.
Checking for overflow in multiplication was not well done. You cannot multiply and then try to check overflow (it is too late by then) - you have to detect it in a more subtle way. Here is one way of doing it - note the check to prevent a division by zero. This does not use any precision greater than that of the simulated machine itself.
case STKMC_mul:
cpu.sp++;
if (inbounds(cpu.sp)) {
if (mem[cpu.sp] != 0 && abs(mem[cpu.sp-1]) > maxint / abs(mem[cpu.sp]))
ps = overflow;
else mem[cpu.sp] *= mem[cpu.sp - 1];
}
break;
Some students used an intermediate long variable (most of them forgot that they should use the abs function as well!)
case STKMC_mul:
cpu.sp++;
if (inbounds(cpu.sp)) {
long temp mem[cpu.sp] * mem[cpu.sp - 1];
if (abs(temp) > maxint) ps = overflow;
else mem[cpu.sp] *= mem[cpu.sp - 1];
}
break;
Pushing and popping are actually very easy. There were some curious mistakes, showing that no much had been tested properly! Note the form that the inbounds checks take - many people got these wrong:
case STKMC_psh:
cpu.sp--;
if (inbounds(cpu.sp) && inbounds(cpu.bp + mem[cpu.pc]))
{ mem[cpu.sp] = mem[cpu.bp + mem[cpu.pc]]; cpu.pc++; }
break;
case STKMC_pop:
cpu.sp++;
if (inbounds(cpu.sp) && inbounds(cpu.bp + mem[cpu.pc]))
{ mem[cpu.bp + mem[cpu.pc]] = mem[cpu.sp - 1]; cpu.pc++; }
break;
Reading and writing characters was trivially easy, being essentially a simple variation on the cases for numeric input and output. However, the output of numbers was arrranged to have a leading space; this is not as pretty when you see i t a p p l i e d t o c h a r a c t e r s , i s i t ? And note the use of the modulo arithmetic to ensure that only sensible ASCII characters will be printed:
case STKMC_ina:
if (inbounds(cpu.sp) && inbounds(mem[cpu.sp]))
{ if (fscanf(data, "%c", &mem[mem[cpu.sp]]) == 0) ps = baddata;
else cpu.sp++;
}
break;
case STKMC_pra:
if (tracing) fputs(BLANKS, results);
cpu.sp++;
if (inbounds(cpu.sp)) fprintf(results, "%c", abs(mem[cpu.sp - 1]) % 256);
if (tracing) putc('\n', results);
break;
The opcodes for the equivalent of a ++ or -- operation produced interesting answers. There are clearly two approaches that could be used: either increment the value at the top of the stack, or increment the variable whose address is at the top of the stack. I suspect the latter is more useful if you are to have but one of these (one could, of course, provide both versions of the opcodes). Here is my suggestion:
case STKMC_inc:
if (inbounds(cpu.sp) && inbounds(mem[cpu.sp])) mem[mem[cpu.sp]]++;
cpu.sp++;
break;
case STKMC_dec:
if (inbounds(cpu.sp) && inbounds(mem[cpu.sp])) mem[mem[cpu.sp]]--;
cpu.sp++;
break;
With these, one can translate statements like
A++ or List[4]--
into very short sequences
ADR -A ADR -List
INC LIT 4
LIT Size
IND
DEC
The functions for ABS, ODD, IsAlNum and ToUpper are realised by very simple opcodes that do not bump the stack pointer at all (many submitted solutions were clearly very confused here)
case STKMC_abs:
if (inbounds(cpu.sp)) mem[cpu.sp] = abs(mem[cpu.sp]);
break;
case STKMC_odd:
if (inbounds(cpu.sp)) mem[cpu.sp] = (mem[cpu.sp] % 2 != 0);
break;
case STKMC_aln:
if (inbounds(cpu.sp)) mem[cpu.sp] = isalnum(mem[cpu.sp]);
break;
case STKMC_upc:
if (inbounds(cpu.sp)) mem[cpu.sp] = toupper(mem[cpu.sp]);
break;
Finally, it is necessary to add the mnemonics and the opcodes into the look up tables, but obviously most of you had realised this. It is important to leave STKMC_nul as the last opcode in the enumeration, as most people must have realised (or were just lucky, as the quiz question caught a whole lot of you out!)
In terms of these new opcodes programs can become much shorter. Here are some examples:
; comments are allowed on lines starting with ;
; program to find the smallest and largest of a stream of integers
; P.D. Terry, Rhodes University, 2002 (modified to use pop/psh)
0 DSP 3 A is at BP-1, Largest at BP-2, Smallest at BP-3
2 PRS 'Supply list of numbers terminated with 0 '
4 ADR -1
6 INN read A
7 PSH -1
9 POP -3 SMALLEST := A
11 PSH -1
13 POP -2 LARGEST := A
15 PSH -1
17 LIT 0
19 NEQ
20 BZE 49 while A <> 0
22 PSH -1
24 PSH -2
26 GTR
27 BZE 33 if A > LARGEST
29 PSH -1
31 POP -2 LARGEST := A
33 PSH -1
35 PSH -3
37 LSS
38 BZE 44 if A < SMALLEST
40 PSH -1
42 POP -3 SMALLEST := A
44 ADR -1
46 INN read A
47 BRN 15
49 NLN output answers
50 PSH -3
52 PRN print SMALLEST
53 PRS ' is the smallest and '
55 PSH -2
57 PRN print LARGEST
58 PRS ' is the largest'
60 NLN
61 HLT
; comments are allowed on lines starting with ;
; program to examine the hailstone sequence
; P.D. Terry, Rhodes University, 2002
0 DSP 3 Term is at Mem[BP-1], N is at Mem[BP-2]
2 PRS 'What is the first number? '
4 NLN
5 ADR -1
7 INN Read(Term)
8 PSH -1
10 ABS
11 POP -1 Term := ABS(Term)
13 LIT 1
15 POP -2 N := 1
17 PSH -1
19 PRN Write(Term)
20 NLN WriteLn
21 PSH -1
23 LIT 1
25 GTR
26 BZE 61 WHILE Term > 1 DO BEGIN
28 ADR -2
30 INC N := N + 1;
31 PSH -1
33 ODD
34 BZE 48 IF ODD(Term)
36 LIT 3 THEN
38 PSH -1
40 MUL
41 LIT 1
43 ADD
44 POP -1 Term := 3 * Term + 1
46 BRN 55
48 PSH -1 ELSE
50 LIT 2
52 DVD
53 POP -1 Term := Term / 2;
55 PSH -1
57 PRN Write(Term);
58 NLN WriteLn;
59 BRN 21 END;
61 PSH -2
63 PRN Write(Terms)'
64 PRS ' terms' Write(' terms');
66 NLN WriteLn;
67 HLT END.
Several people did the obvious thing - simply knocked out (commented out) the calls to the inbounds function to produce a dangerous, but faster interpreter. One can knock out the calls to the tracing routine, and speed up the IND opcode as well. Note that maximum speed is obtained by knocking out the calls to the function, not by calling a function that simply returns immediately, as one or two groups tried.
Results are quite interesting. On my system (a 200MHz Pentium) I got the following timings. SIEVE1.STK was a version with PSH/POP operations which resulted in even less code. The times are given in seconds, and one can see that omitting the calls to inbounds speeds things up by about 35%:
Sieve.stk Sieve1.stk
400 iterations
full checks 30.41 20.50 0.67
no stack chk 18.74 12.24 0.06
0.62 0.60
200 iterations
full checks 15.60 10.68 0.68
no stack chk 9.79 6.50 0.67
0.63 0.61
100 iterations
full checks 8.27 5.80 0.70
no stack chk 5.34 3.68 0.69
0.65 0.63